数理最適化Solverいろいろ
定期的に開催されているOptimization Nightの#9がSolver回だそう。
久しぶりに参加しようかと思いきや、どうやら参加が難しい日に開催されるらしい。残念。
説明を見ると、PRINTEMPSという面白そうなSolverが紹介されていたので少し寂しく思いながら試してみた。
PRINTEMPS自体は厳密解を出すSolverでなく、高速に近似解を出すメタヒューリスティクスなSolverということで、どうせ厳密解を求めるのが難しいような問題にはとても良い選択な気がしたので試してみました。
Solver開発している人いるんですね… すげーな。
結論 First
厳密解を求めることができるCBCとPRINTEMPSを線形計画問題（Jobshop）で性能比較しました。
個人的な感想も踏まえて結論を述べると、
- 総じて、PRINTEMPSは超高速にそこそこの解を出してくれました
- 問題が大きくなると、解が悪くなる傾向にはある（測定範囲で最大＋26％）
- 問題が大きくなると、処理時間の開きは大きくなります(Max100倍。PRINTEMPSの高速性が光る)
- C++でアプリを作ることが前提ですがMPSファイルを読み込むこともできるスタンドアロンツールあります
- つづりがおぼえられません…
| Size | CBCの解 | CBCの処理時間 | PRINTEMPS解 | PRINTEMPS処理時間 | 最適解からの誤差 | 処理時間比 |
|---|---|---|---|---|---|---|
| 7 | 65.4 | 1.8 | 73.6 | 0.3 | 12.54% | 16.46% |
| 8 | 75.0 | 14.8 | 82.8 | 0.4 | 10.40% | 2.50% |
| 9 | 84.2 | 20.0 | 95.6 | 1.1 | 13.54% | 5.27% |
| 10 | 89.0 | 63.3 | 108.6 | 2.2 | 22.02% | 3.52% |
| 11 | 98.7 | 433.0 | 124.7 | 4.3 | 26.35% | 1.00% |
*乱数Seedを変更しながら、5回ずつ実施して平均を取得
*最適解からの誤差は厳密解であるCBCの解と近似解のPRINTEMPS解の誤差を出しています。
*処理時間比はCBCの処理時間を基準に何パーセントの時間で処理できているかを示しています。
*PRINTEMPSはデフォルトパラメータで動作しています。変更もできるようです→パラメータ詳細はこちら。
設定パラメータについては開発者の方からのコメントもいただいたのでぜひそちらもご参照ください。
PRINTEMPS
紹介
ググると「フランス語で春」とかポエムな内容しか出てこない。そうか、プランタン銀座って銀座の春とかいう意味だったんか。それは良しとして…
オープンソフトウェアと記載があったので、「PRINTEMPS Github」で調べると無事出てきました。
インストール
簡単にインストールできないかなと思ったけど、なさそう。
$ apt-cache search PRINTEMPS
ドキュメントは 別ページ にあり、それによればインストールは
PRINTEMPSのインストールは、リポジトリをクローンする（または最新のアーカイブをダウンロードする）ことで完了します。その後、リポジトリ内の printemps/ ディレクトリを適切な場所にコピーするだけです。
とのこと。git cloneで取得します。
ダウンロード
$ git clone https://github.com/snowberryfield/printemps.git
Cloning into 'printemps'...
remote: Enumerating objects: 9874, done.
remote: Counting objects: 100% (3447/3447), done.
remote: Compressing objects: 100% (908/908), done.
remote: Total 9874 (delta 2453), reused 3183 (delta 2417), pack-reused 6427 (from 1)
Receiving objects: 100% (9874/9874), 3.95 MiB | 8.50 MiB/s, done.
Resolving deltas: 100% (7047/7047), done.
exampleを見ると比較的容易な記載で、問題を解くことができるようです。
「とはいえ、C++で個別開発が必要かぁ」と思っていたら下の方に"Standalone Solver"の文字が！
翻訳
スタンドアロンソルバー
PRINTEMPSに基づくスタンドアロン実行可能ソルバーも提供されています。MPS（数理計画システム）形式の純粋な整数計画問題を近似的に解きます。以下のコマンドでビルドできます：
$ make -f makefile/Makefile.application [CC=gcc CXX=g++]
ビルド後のソルバーは build/application/Release/mps_solver.exe に生成されます。次のコマンドで実行可能です：
$ ./mps_solver.exe mps_file [-p option_file] [--accept-continuous]
オプションファイルとして application/dat/option.json が例として提供されています。
とのことでしたので、実際にコンパイルします。
ちゃんとbuild/application/Releaseディレクトリ下にmps_solver.exeが生成されました。
コンパイル
monta@JIJI:~/printemps$ make -f makefile/Makefile.application
mkdir -p /home/monta/printemps/build/application/Release && \
cd /home/monta/printemps/build/application/Release && \
cmake -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_COMPILER=g++ -DCMAKE_C_COMPILER=gcc -DTOP_DIR=/home/monta/printemps /home/monta/printemps/cmake/application
-- The C compiler identification is GNU 11.4.0
-- The CXX compiler identification is GNU 11.4.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/gcc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/g++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Found OpenMP_C: -fopenmp (found version "4.5")
-- Found OpenMP_CXX: -fopenmp (found version "4.5")
-- Found OpenMP: TRUE (found version "4.5")
-- Configuring done
-- Generating done
-- Build files have been written to: /home/monta/printemps/build/application/Release
cmake --build /home/monta/printemps/build/application/Release
gmake[1]: Entering directory '/home/monta/printemps/build/application/Release'
gmake[2]: Entering directory '/home/monta/printemps/build/application/Release'
gmake[3]: Entering directory '/home/monta/printemps/build/application/Release'
gmake[3]: Leaving directory '/home/monta/printemps/build/application/Release'
gmake[3]: Entering directory '/home/monta/printemps/build/application/Release'
[ 50%] Building CXX object CMakeFiles/mps_solver.exe.dir/home/monta/printemps/application/mps_solver/main.cpp.o
[100%] Linking CXX executable mps_solver.exe
gmake[3]: Leaving directory '/home/monta/printemps/build/application/Release'
[100%] Built target mps_solver.exe
gmake[2]: Leaving directory '/home/monta/printemps/build/application/Release'
gmake[1]: Leaving directory '/home/monta/printemps/build/application/Release'
monta@JIJI:~/printemps$ build/application/Release/mps_solver.exe
PRINTEMPS v2.5.0 (https://snowberryfield.github.io/printemps/)
Usage: ./mps_solver.exe [-p OPTION_FILE_NAME] [-i INITIAL_SOLUTION_FILE_NAME] [-m MUTABLE_VARIABLE_FILE_NAME] [-f FIXED_VARIABLE_FILE_NAME] [-s SELECTION_CONSTRAINT_FILE_NAME] [-x FLIPPABLE_VARIABLE_PAIR_FILE_NAME][-c MINIMUM_COMMON_ELEMENT] [--accept-continuous] [--extract-flippable-variable-pairs] [--include-mps-loading-time] [--export-json-instance] mps_file
-p OPTION_FILE_NAME: Specify option file name.
-i INITIAL_SOLUTION_FILE_NAME: Specify initial solution file name.
-m MUTABLE_VARIABLE_FILE_NAME: Specify mutable variable file name.
-f FIXED_VARIABLE_FILE_NAME: Specify fixed variable file name.
-s SELECTION_CONSTRAINT_FILE_NAME: Specify user-defined selection constraint file name.
-x FLIP_VARIABLE_PAIR_FILE_NAME: Specify flippable variable pair file name.
-c MINIMUM_COMMON_ELEMENT: Specify the number of minimum common element between two constraints, which is used as the threshold for extracting flippable variable pairs. (default: 5)
--accept-continuous: Accept continuous variables as integer variables.
--extract-flippable-variable-pairs: Extract 2-flippable variable pairs.
--include-mps-loading-time: Include MPS file loading time in the calculation time.
--export-json-instance: Export the target instance as JSON format.
性能評価
Jobshopで試してみましょう。
比較用CBCコード
まず、Pulpで解くアプリをささっと１分で作ります(OpenAI-o1がね！)。mpsファイルを出力するようにしておきましょう。
微妙に具合が悪かったところなどは手を入れています。なお、肝心の制約などはチェックしていないので間違えていたらごめんなさい。
# 必要なモジュールをインポート
import pulp
import random
import argparse
def generate_jobs_data(num_jobs=10, min_machines=4, max_machines=6):
"""
ランダムなジョブデータを生成する関数
Parameters:
----------
num_jobs : int
生成するジョブの数
min_machines : int
使用するマシンの最小数
max_machines : int
使用するマシンの最大数
Returns:
-------
jobs_data : dict
ジョブのデータ。キーがジョブ名、値が（マシン名、処理時間）のリスト
machines : list
使用するマシンのリスト
"""
# マシンの数を決定
num_machines = random.randint(min_machines, max_machines)
machines = [f"M{i+1}" for i in range(num_machines)]
jobs_data = {}
for j in range(1, num_jobs+1):
# 各ジョブの操作数をランダムに決定（例：マシン数と同じに設定）
num_operations = num_machines
# マシンの順序をランダムに決定
machine_sequence = random.sample(machines, num_operations)
# 各操作の処理時間をランダムに決定（例：1から10の間）
processing_times = [random.randint(1, 10) for _ in range(num_operations)]
# ジョブデータを作成
ops = list(zip(machine_sequence, processing_times))
jobs_data[f"Job{j}"] = ops
return jobs_data, machines
def solve_jobshop(jobs_data, machines):
"""
ジョブショップ問題を解く関数
Parameters:
----------
jobs_data : dict
ジョブのデータ。キーがジョブ名、値が（マシン名、処理時間）のリスト。
machines : list
使用するマシンのリスト
Returns:
-------
None
最適化結果を出力し、MPSファイルを保存します。
"""
# 問題を定義
prob = pulp.LpProblem("JobShopScheduling", pulp.LpMinimize)
# ジョブとマシンのセットを作成
jobs = list(jobs_data.keys())
# 各操作に対して開始時間の変数を定義
# vars[(job, task_index)] = 開始時間
vars = {}
for j in jobs:
for i, (m, p) in enumerate(jobs_data[j]):
vars[(j, i)] = pulp.LpVariable(f"Start_{j}_{i}", lowBound=0, cat='Integer')
# 最適化の目的関数：全体の完了時間を最小化
makespan = pulp.LpVariable("Makespan", lowBound=0, cat='Integer')
prob += makespan, "Objective: Minimize Makespan"
# 制約を追加
# 1. 各ジョブ内の操作は順序通りに処理される
for j in jobs:
ops = jobs_data[j]
for i in range(len(ops)-1):
current_op = vars[(j, i)]
next_op = vars[(j, i+1)]
proc_time = ops[i][1]
# 次の操作は現在の操作が終了してから開始
prob += next_op >= current_op + proc_time, f"Precedence_{j}_{i}"
# 2. 同じマシン上では同時に1つの操作しか処理できない
# マシンごとに全ての操作の組み合わせについて制約を追加
for m in machines:
# そのマシンを使用する全ての操作を取得
ops_on_m = []
for j in jobs:
for i, (machine, proc_time) in enumerate(jobs_data[j]):
if machine == m:
ops_on_m.append((j, i, proc_time))
# 操作のペアごとに相互に排他的であることを強制
for idx1 in range(len(ops_on_m)):
for idx2 in range(idx1+1, len(ops_on_m)):
j1, i1, p1 = ops_on_m[idx1]
j2, i2, p2 = ops_on_m[idx2]
s1 = vars[(j1, i1)]
s2 = vars[(j2, i2)]
# バイナリ変数を導入してリニア化
y = pulp.LpVariable(f"Y_{m}_{j1}_{i1}_{j2}_{i2}", cat='Binary')
M = 1000 # 十分大きな定数
# s1 + p1 <= s2 + M*(1 - y)
prob += s1 + p1 <= s2 + M*(1 - y), f"Disjunctive1_{m}_{j1}_{i1}_{j2}_{i2}"
# s2 + p2 <= s1 + M*y
prob += s2 + p2 <= s1 + M*y, f"Disjunctive2_{m}_{j1}_{i1}_{j2}_{i2}"
# 3. 全てのジョブの最終操作の終了時間はmakespan以下
for j in jobs:
last_op_index = len(jobs_data[j]) -1
last_op = vars[(j, last_op_index)]
proc_time = jobs_data[j][last_op_index][1]
prob += makespan >= last_op + proc_time, f"Makespan_{j}"
# 問題をMPSファイルとして保存
prob.writeMPS("jobshop.mps")
# 問題を解く
prob.solve()
# 最適化結果を出力
print("最適化ステータス:", pulp.LpStatus[prob.status])
print("最小の完了時間(Makespan):", pulp.value(makespan))
print("\n各操作の開始時間:")
for j in jobs:
for i in range(len(jobs_data[j])):
start_time = pulp.value(vars[(j, i)])
machine = jobs_data[j][i][0]
proc_time = jobs_data[j][i][1]
print(f"ジョブ {j} の操作 {i}（マシン: {machine}, 処理時間: {proc_time}）の開始時間: {start_time}")
def main():
"""
メイン関数
"""
# コマンドライン引数の解析
parser = argparse.ArgumentParser(description='ジョブショップスケジューリング問題を解くプログラム')
parser.add_argument('--num_jobs', type=int, default=10, help='ジョブの数（デフォルト: 10）')
parser.add_argument('--min_machines', type=int, default=4, help='マシン数の最小値（デフォルト: 4）')
parser.add_argument('--max_machines', type=int, default=6, help='マシン数の最大値（デフォルト: 6）')
parser.add_argument('--seed', type=int, default=None, help='乱数シード（デフォルト: None）')
args = parser.parse_args()
# 乱数シードを設定（再現性のため）
if args.seed is not None:
random.seed(args.seed)
# ランダムなジョブデータを生成
jobs_data, machines = generate_jobs_data(args.num_jobs, args.min_machines, args.max_machines)
# 生成されたジョブデータを表示
print("生成されたジョブデータ:")
for j in jobs_data:
print(f"{j}: {jobs_data[j]}")
# 問題を解く
solve_jobshop(jobs_data, machines)
if __name__ == "__main__":
main()
Pulp(CBC)での実行結果
適当な処理時間となるよう問題サイズを調整しながら実行してみました。
実行時間 14.65秒
最適解：78
(.venv) monta@JIJI:~/PyCode/jobshop$ /home/monta/PyCode/jobshop/.venv/bin/python /home/monta/PyCode/jobshop/basic_jobshop.py --num_job 8 --min_machines 7 --max_machines 8 --seed 1
生成されたジョブデータ:
Job1: [('M5', 7), ('M1', 4), ('M3', 2), ('M6', 8), ('M2', 1), ('M7', 7), ('M4', 7)]
Job2: [('M5', 6), ('M1', 1), ('M4', 1), ('M3', 1), ('M7', 9), ('M6', 1), ('M2', 7)]
Job3: [('M6', 8), ('M2', 9), ('M4', 4), ('M1', 6), ('M3', 4), ('M5', 4), ('M7', 8)]
Job4: [('M3', 6), ('M1', 9), ('M4', 7), ('M6', 9), ('M5', 4), ('M2', 5), ('M7', 5)]
Job5: [('M5', 4), ('M4', 7), ('M7', 7), ('M6', 3), ('M3', 6), ('M1', 9), ('M2', 6)]
Job6: [('M1', 8), ('M4', 1), ('M5', 8), ('M7', 1), ('M6', 5), ('M2', 10), ('M3', 10)]
Job7: [('M5', 4), ('M4', 9), ('M2', 9), ('M7', 4), ('M3', 7), ('M1', 9), ('M6', 6)]
Job8: [('M7', 9), ('M5', 3), ('M3', 9), ('M4', 9), ('M2', 4), ('M1', 7), ('M6', 1)]
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
…中略…
Result - Optimal solution found
Objective value: 78.00000000
Enumerated nodes: 2276
Total iterations: 149761
Time (CPU seconds): 12.89
Time (Wallclock seconds): 14.65
Option for printingOptions changed from normal to all
Total time (CPU seconds): 12.89 (Wallclock seconds): 14.66
最適化ステータス: Optimal
最小の完了時間(Makespan): 78.0
各操作の開始時間:
ジョブ Job1 の操作 0（マシン: M1, 処理時間: 10）の開始時間: 0.0
ジョブ Job1 の操作 1（マシン: M7, 処理時間: 4）の開始時間: 10.0
…後略…
Pulp(CBC)での実行結果 全量
(.venv) monta@JIJI:~/PyCode/jobshop$ /home/monta/PyCode/jobshop/.venv/bin/python /home/monta/PyCode/jobshop/basic_jobshop.py --num_job 8 --min_machines 7 --max_machines 8 --seed 2
生成されたジョブデータ:
Job1: [('M1', 10), ('M7', 4), ('M3', 10), ('M2', 1), ('M5', 10), ('M4', 3), ('M6', 7)]
Job2: [('M6', 1), ('M4', 1), ('M5', 6), ('M3', 8), ('M7', 6), ('M2', 7), ('M1', 7)]
Job3: [('M5', 3), ('M2', 6), ('M7', 3), ('M6', 3), ('M1', 9), ('M3', 9), ('M4', 6)]
Job4: [('M5', 10), ('M6', 6), ('M7', 6), ('M2', 8), ('M4', 3), ('M3', 7), ('M1', 8)]
Job5: [('M6', 8), ('M5', 8), ('M2', 6), ('M4', 10), ('M7', 9), ('M3', 8), ('M1', 8)]
Job6: [('M6', 5), ('M2', 5), ('M3', 9), ('M7', 9), ('M5', 9), ('M4', 9), ('M1', 10)]
Job7: [('M5', 6), ('M4', 1), ('M3', 4), ('M2', 2), ('M6', 1), ('M7', 10), ('M1', 1)]
Job8: [('M3', 4), ('M5', 4), ('M2', 1), ('M1', 7), ('M7', 1), ('M4', 1), ('M6', 6)]
Welcome to the CBC MILP Solver
Version: 2.10.3
Build Date: Dec 15 2019
command line - /home/monta/PyCode/jobshop/.venv/lib/python3.10/site-packages/pulp/solverdir/cbc/linux/64/cbc /tmp/b7b0875a71bb4fd5915052ba5ed31768-pulp.mps -timeMode elapsed -branch -printingOptions all -solution /tmp/b7b0875a71bb4fd5915052ba5ed31768-pulp.sol (default strategy 1)
At line 2 NAME MODEL
At line 3 ROWS
At line 453 COLUMNS
At line 2249 RHS
At line 2698 BOUNDS
At line 2952 ENDATA
Problem MODEL has 448 rows, 253 columns and 1288 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Continuous objective value is 57 - 0.00 seconds
Cgl0003I 0 fixed, 97 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 48 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 8 tightened bounds, 0 strengthened rows, 0 substitutions
Cgl0004I processed model has 448 rows, 253 columns (253 integer (196 of which binary)) and 1288 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0045I 1 integer variables out of 253 objects (253 integer) have cost of 1 - high priority
Cbc0045I branch on satisfied Y create fake objective Y random cost Y
Cbc0038I Initial state - 113 integers unsatisfied sum - 1.871
Cbc0038I Pass 1: suminf. 0.00000 (0) obj. 232 iterations 121
Cbc0038I Solution found of 232
Cbc0038I Cleaned solution of 232
Cbc0038I Before mini branch and bound, 90 integers at bound fixed and 0 continuous
Cbc0038I Full problem 448 rows 253 columns, reduced to 320 rows 153 columns - too large
Cbc0038I Mini branch and bound did not improve solution (0.01 seconds)
Cbc0038I Round again with cutoff of 213.6
Cbc0038I Pass 2: suminf. 0.01900 (4) obj. 213 iterations 4
Cbc0038I Pass 3: suminf. 12.79752 (33) obj. 213.6 iterations 13
Cbc0038I Pass 4: suminf. 12.79752 (33) obj. 213.6 iterations 0
Cbc0038I Pass 5: suminf. 24.29587 (136) obj. 213.6 iterations 132
Cbc0038I Pass 6: suminf. 23.64187 (104) obj. 213.6 iterations 44
Cbc0038I Pass 7: suminf. 15.30758 (46) obj. 213.6 iterations 61
Cbc0038I Pass 8: suminf. 15.19658 (38) obj. 213.6 iterations 16
Cbc0038I Solution found of 213.6
Cbc0038I Branch and bound needed to clear up 38 general integers
Cbc0038I Full problem 449 rows 253 columns, reduced to 0 rows 0 columns
Cbc0038I Cleaned solution of 142
Cbc0038I Before mini branch and bound, 58 integers at bound fixed and 0 continuous
Cbc0038I Full problem 448 rows 253 columns, reduced to 448 rows 195 columns - 13 fixed gives 448, 182 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.03 seconds)
Cbc0038I Round again with cutoff of 124.2
Cbc0038I Pass 9: suminf. 9.19680 (64) obj. 124.2 iterations 23
Cbc0038I Pass 10: suminf. 11.03920 (59) obj. 124.2 iterations 45
Cbc0038I Pass 11: suminf. 4.40556 (24) obj. 124.2 iterations 14
Cbc0038I Pass 12: suminf. 2.60184 (14) obj. 124.2 iterations 5
Cbc0038I Pass 13: suminf. 2.60184 (14) obj. 124.2 iterations 0
Cbc0038I Pass 14: suminf. 1.52924 (62) obj. 124.2 iterations 96
Cbc0038I Pass 15: suminf. 9.61356 (65) obj. 124.2 iterations 65
Cbc0038I Pass 16: suminf. 10.84312 (58) obj. 124.2 iterations 37
Cbc0038I Pass 17: suminf. 2.00460 (11) obj. 124.2 iterations 11
Cbc0038I Pass 18: suminf. 1.60444 (9) obj. 124.2 iterations 3
Cbc0038I Pass 19: suminf. 12.26556 (115) obj. 124.2 iterations 106
Cbc0038I Pass 20: suminf. 9.48656 (55) obj. 124.2 iterations 95
Cbc0038I Pass 21: suminf. 9.00360 (45) obj. 124.2 iterations 20
Cbc0038I Solution found of 124.2
Cbc0038I Branch and bound needed to clear up 45 general integers
Cbc0038I Full problem 449 rows 253 columns, reduced to 0 rows 0 columns
Cbc0038I Cleaned solution of 110
Cbc0038I Before mini branch and bound, 58 integers at bound fixed and 0 continuous
Cbc0038I Full problem 448 rows 253 columns, reduced to 448 rows 195 columns - 31 fixed gives 448, 164 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.06 seconds)
Cbc0038I Round again with cutoff of 93.4001
Cbc0038I Pass 22: suminf. 3.59796 (41) obj. 93.4001 iterations 25
Cbc0038I Pass 23: suminf. 19.70683 (62) obj. 93.4001 iterations 46
Cbc0038I Pass 24: suminf. 21.62998 (60) obj. 93.4001 iterations 27
Cbc0038I Pass 25: suminf. 21.62598 (59) obj. 93.4001 iterations 15
Cbc0038I Pass 26: suminf. 21.62598 (59) obj. 93.4001 iterations 16
Cbc0038I Pass 27: suminf. 1.33507 (57) obj. 93.4001 iterations 106
Cbc0038I Pass 28: suminf. 3.49616 (35) obj. 93.4001 iterations 50
Cbc0038I Pass 29: suminf. 2.02855 (11) obj. 93.4001 iterations 36
Cbc0038I Pass 30: suminf. 11.22916 (33) obj. 93.4001 iterations 21
Cbc0038I Pass 31: suminf. 8.02560 (25) obj. 93.4001 iterations 16
Cbc0038I Pass 32: suminf. 8.41767 (27) obj. 93.4001 iterations 24
Cbc0038I Pass 33: suminf. 4.41597 (17) obj. 93.4001 iterations 17
Cbc0038I Pass 34: suminf. 4.43797 (17) obj. 93.4001 iterations 13
Cbc0038I Pass 35: suminf. 1.51307 (63) obj. 93.4001 iterations 105
Cbc0038I Pass 36: suminf. 20.24910 (72) obj. 93.4001 iterations 86
Cbc0038I Pass 37: suminf. 1.24481 (16) obj. 93.4001 iterations 30
Cbc0038I Pass 38: suminf. 6.06165 (25) obj. 93.4001 iterations 33
Cbc0038I Pass 39: suminf. 1.23081 (13) obj. 93.4001 iterations 25
Cbc0038I Pass 40: suminf. 0.83774 (12) obj. 93.4001 iterations 28
Cbc0038I Pass 41: suminf. 17.63868 (51) obj. 93.4001 iterations 29
Cbc0038I Pass 42: suminf. 22.03045 (59) obj. 93.4001 iterations 17
Cbc0038I Pass 43: suminf. 1.21581 (6) obj. 93.4001 iterations 19
Cbc0038I Pass 44: suminf. 0.80774 (5) obj. 93.4001 iterations 16
Cbc0038I Pass 45: suminf. 0.81574 (6) obj. 93.4001 iterations 11
Cbc0038I Pass 46: suminf. 2.01855 (10) obj. 93.4001 iterations 14
Cbc0038I Pass 47: suminf. 0.81574 (6) obj. 93.4001 iterations 19
Cbc0038I Pass 48: suminf. 2.01755 (11) obj. 93.4001 iterations 16
Cbc0038I Pass 49: suminf. 1.11107 (47) obj. 93.4001 iterations 94
Cbc0038I Pass 50: suminf. 10.87949 (41) obj. 93.4001 iterations 55
Cbc0038I Pass 51: suminf. 2.04495 (12) obj. 93.4001 iterations 31
Cbc0038I Pass 52: suminf. 12.42277 (36) obj. 93.4001 iterations 19
Cbc0038I Pass 53: suminf. 7.62093 (23) obj. 93.4001 iterations 12
Cbc0038I Pass 54: suminf. 6.01665 (19) obj. 93.4001 iterations 17
Cbc0038I Pass 55: suminf. 7.62693 (23) obj. 93.4001 iterations 15
Cbc0038I Pass 56: suminf. 11.22756 (31) obj. 93.4001 iterations 8
Cbc0038I Pass 57: suminf. 4.40737 (13) obj. 93.4001 iterations 8
Cbc0038I Pass 58: suminf. 4.41137 (13) obj. 93.4001 iterations 2
Cbc0038I Pass 59: suminf. 23.75499 (113) obj. 93.4001 iterations 93
Cbc0038I Pass 60: suminf. 10.12175 (40) obj. 93.4001 iterations 85
Cbc0038I Pass 61: suminf. 17.23061 (49) obj. 93.4001 iterations 27
Cbc0038I Pass 62: suminf. 17.22061 (47) obj. 93.4001 iterations 9
Cbc0038I Pass 63: suminf. 17.21561 (46) obj. 93.4001 iterations 8
Cbc0038I Pass 64: suminf. 17.61368 (48) obj. 93.4001 iterations 7
Cbc0038I Pass 65: suminf. 23.68099 (117) obj. 93.4001 iterations 105
Cbc0038I Pass 66: suminf. 1.70288 (21) obj. 93.4001 iterations 81
Cbc0038I Pass 67: suminf. 1.63588 (11) obj. 93.4001 iterations 39
Cbc0038I Pass 68: suminf. 3.61323 (14) obj. 93.4001 iterations 11
Cbc0038I Pass 69: suminf. 6.81279 (22) obj. 93.4001 iterations 12
Cbc0038I Pass 70: suminf. 1.44907 (63) obj. 93.4001 iterations 96
Cbc0038I Pass 71: suminf. 0.88407 (43) obj. 93.4001 iterations 46
Cbc0038I Pass 72: suminf. 2.12195 (21) obj. 93.4001 iterations 53
Cbc0038I Pass 73: suminf. 6.02465 (18) obj. 93.4001 iterations 33
Cbc0038I Pass 74: suminf. 15.21026 (40) obj. 93.4001 iterations 9
Cbc0038I Pass 75: suminf. 1.20481 (5) obj. 93.4001 iterations 12
Cbc0038I Pass 76: suminf. 10.40242 (27) obj. 93.4001 iterations 4
Cbc0038I Pass 77: suminf. 10.40242 (27) obj. 93.4001 iterations 0
Cbc0038I Pass 78: suminf. 23.57799 (108) obj. 93.4001 iterations 94
Cbc0038I Pass 79: suminf. 3.09049 (39) obj. 93.4001 iterations 45
Cbc0038I Pass 80: suminf. 17.65428 (57) obj. 93.4001 iterations 53
Cbc0038I Pass 81: suminf. 13.27591 (44) obj. 93.4001 iterations 30
Cbc0038I Pass 82: suminf. 12.45177 (39) obj. 93.4001 iterations 30
Cbc0038I Pass 83: suminf. 11.62663 (35) obj. 93.4001 iterations 20
Cbc0038I Pass 84: suminf. 9.62828 (30) obj. 93.4001 iterations 17
Cbc0038I Pass 85: suminf. 13.22091 (39) obj. 93.4001 iterations 15
Cbc0038I Pass 86: suminf. 1.45807 (69) obj. 93.4001 iterations 117
Cbc0038I Pass 87: suminf. 0.86907 (39) obj. 93.4001 iterations 54
Cbc0038I Pass 88: suminf. 20.45377 (65) obj. 93.4001 iterations 58
Cbc0038I Pass 89: suminf. 9.23181 (33) obj. 93.4001 iterations 34
Cbc0038I Pass 90: suminf. 22.46892 (64) obj. 93.4001 iterations 25
Cbc0038I Pass 91: suminf. 8.02460 (29) obj. 93.4001 iterations 18
Cbc0038I Pass 92: suminf. 7.65293 (26) obj. 93.4001 iterations 13
Cbc0038I Pass 93: suminf. 8.03660 (27) obj. 93.4001 iterations 14
Cbc0038I Pass 94: suminf. 1.09207 (47) obj. 93.4001 iterations 77
Cbc0038I Pass 95: suminf. 0.83634 (10) obj. 93.4001 iterations 67
Cbc0038I Pass 96: suminf. 1.23481 (10) obj. 93.4001 iterations 28
Cbc0038I Pass 97: suminf. 1.23381 (9) obj. 93.4001 iterations 27
Cbc0038I Pass 98: suminf. 4.06130 (16) obj. 93.4001 iterations 13
Cbc0038I Pass 99: suminf. 1.84014 (69) obj. 93.4001 iterations 140
Cbc0038I Pass 100: suminf. 1.25014 (41) obj. 93.4001 iterations 48
Cbc0038I Pass 101: suminf. 8.83974 (31) obj. 93.4001 iterations 69
Cbc0038I Pass 102: suminf. 4.02290 (16) obj. 93.4001 iterations 26
Cbc0038I Pass 103: suminf. 0.81774 (8) obj. 93.4001 iterations 18
Cbc0038I Pass 104: suminf. 12.81984 (37) obj. 93.4001 iterations 18
Cbc0038I Pass 105: suminf. 0.81574 (7) obj. 93.4001 iterations 17
Cbc0038I Pass 106: suminf. 23.59699 (111) obj. 93.4001 iterations 95
Cbc0038I Pass 107: suminf. 1.09174 (34) obj. 93.4001 iterations 45
Cbc0038I Pass 108: suminf. 20.43917 (57) obj. 93.4001 iterations 58
Cbc0038I Pass 109: suminf. 4.02330 (14) obj. 93.4001 iterations 23
Cbc0038I Pass 110: suminf. 3.22916 (13) obj. 93.4001 iterations 14
Cbc0038I Pass 111: suminf. 4.02330 (14) obj. 93.4001 iterations 16
Cbc0038I Pass 112: suminf. 3.23016 (13) obj. 93.4001 iterations 15
Cbc0038I Pass 113: suminf. 1.24707 (65) obj. 93.4001 iterations 94
Cbc0038I Pass 114: suminf. 2.79642 (39) obj. 93.4001 iterations 48
Cbc0038I Pass 115: suminf. 2.51662 (24) obj. 93.4001 iterations 32
Cbc0038I Pass 116: suminf. 15.22226 (44) obj. 93.4001 iterations 34
Cbc0038I Pass 117: suminf. 12.82784 (36) obj. 93.4001 iterations 13
Cbc0038I Pass 118: suminf. 8.00960 (24) obj. 93.4001 iterations 7
Cbc0038I Pass 119: suminf. 1.44307 (69) obj. 93.4001 iterations 110
Cbc0038I Pass 120: suminf. 0.92707 (47) obj. 93.4001 iterations 46
Cbc0038I Pass 121: suminf. 1.30907 (65) obj. 93.4001 iterations 82
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 3 integers at bound fixed and 0 continuous
Cbc0038I Full problem 448 rows 253 columns, reduced to 448 rows 250 columns - 31 fixed gives 448, 219 - still too large
Cbc0038I Mini branch and bound did not improve solution (0.17 seconds)
Cbc0038I After 0.17 seconds - Feasibility pump exiting with objective of 110 - took 0.15 seconds
Cbc0012I Integer solution of 110 found by feasibility pump after 0 iterations and 0 nodes (0.17 seconds)
Cbc0038I Full problem 448 rows 253 columns, reduced to 400 rows 165 columns - 31 fixed gives 386, 137 - still too large
Cbc0031I 79 added rows had average density of 9.8481013
Cbc0013I At root node, 79 cuts changed objective from 57 to 66 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 2872 row cuts average 3.9 elements, 37 column cuts (37 active) in 0.172 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 727 row cuts average 34.7 elements, 0 column cuts (0 active) in 0.084 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.022 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.002 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 30 row cuts average 2.4 elements, 0 column cuts (0 active) in 0.015 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.034 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 665 row cuts average 13.5 elements, 0 column cuts (0 active) in 0.020 seconds - new frequency is 1
Cbc0014I Cut generator 7 (ZeroHalf) - 1 row cuts average 3.0 elements, 0 column cuts (0 active) in 0.001 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, 110 best solution, best possible 66 (1.11 seconds)
Cbc0038I Full problem 448 rows 253 columns, reduced to 405 rows 157 columns - 20 fixed gives 399, 137 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 329 rows 96 columns - 1 fixed gives 328, 95 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 229 rows 94 columns
Cbc0038I Full problem 448 rows 253 columns, reduced to 320 rows 93 columns - 1 fixed gives 319, 92 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 207 rows 86 columns
Cbc0016I Integer solution of 86 found by strong branching after 31871 iterations and 294 nodes (4.95 seconds)
Cbc0038I Full problem 448 rows 253 columns, reduced to 401 rows 166 columns - 17 fixed gives 395, 149 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 396 rows 148 columns - 2 fixed gives 396, 146 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 375 rows 138 columns - 4 fixed gives 375, 134 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 364 rows 128 columns - 2 fixed gives 363, 126 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 298 rows 125 columns - too large
Cbc0004I Integer solution of 82 found after 77194 iterations and 986 nodes (9.48 seconds)
Cbc0038I Full problem 448 rows 253 columns, reduced to 329 rows 131 columns - 8 fixed gives 325, 123 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 280 rows 120 columns - too large
Cbc0010I After 1000 nodes, 8 on tree, 82 best solution, best possible 77 (9.59 seconds)
Cbc0038I Full problem 448 rows 253 columns, reduced to 345 rows 136 columns - 7 fixed gives 342, 129 - still too large
Cbc0038I Full problem 448 rows 253 columns, reduced to 288 rows 127 columns - too large
Cbc0016I Integer solution of 80 found by strong branching after 111808 iterations and 1581 nodes (12.19 seconds)
Cbc0010I After 2000 nodes, 10 on tree, 80 best solution, best possible 78 (13.77 seconds)
Cbc0016I Integer solution of 78 found by strong branching after 149761 iterations and 2276 nodes (14.65 seconds)
Cbc0001I Search completed - best objective 78, took 149761 iterations and 2276 nodes (14.65 seconds)
Cbc0032I Strong branching done 11416 times (165231 iterations), fathomed 59 nodes and fixed 173 variables
Cbc0035I Maximum depth 39, 0 variables fixed on reduced cost
Cuts at root node changed objective from 57 to 66
Probing was tried 2260 times and created 46251 cuts of which 0 were active after adding rounds of cuts (1.930 seconds)
Gomory was tried 1400 times and created 20193 cuts of which 0 were active after adding rounds of cuts (0.428 seconds)
Knapsack was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.022 seconds)
Clique was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.002 seconds)
MixedIntegerRounding2 was tried 100 times and created 30 cuts of which 0 were active after adding rounds of cuts (0.015 seconds)
FlowCover was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.034 seconds)
TwoMirCuts was tried 1400 times and created 5831 cuts of which 0 were active after adding rounds of cuts (0.160 seconds)
ZeroHalf was tried 1 times and created 1 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
ImplicationCuts was tried 46 times and created 16 cuts of which 0 were active after adding rounds of cuts (0.003 seconds)
Result - Optimal solution found
Objective value: 78.00000000
Enumerated nodes: 2276
Total iterations: 149761
Time (CPU seconds): 12.89
Time (Wallclock seconds): 14.65
Option for printingOptions changed from normal to all
Total time (CPU seconds): 12.89 (Wallclock seconds): 14.66
最適化ステータス: Optimal
最小の完了時間(Makespan): 78.0
各操作の開始時間:
ジョブ Job1 の操作 0（マシン: M1, 処理時間: 10）の開始時間: 0.0
ジョブ Job1 の操作 1（マシン: M7, 処理時間: 4）の開始時間: 10.0
ジョブ Job1 の操作 2（マシン: M3, 処理時間: 10）の開始時間: 27.0
ジョブ Job1 の操作 3（マシン: M2, 処理時間: 1）の開始時間: 38.0
ジョブ Job1 の操作 4（マシン: M5, 処理時間: 10）の開始時間: 47.0
ジョブ Job1 の操作 5（マシン: M4, 処理時間: 3）の開始時間: 58.0
ジョブ Job1 の操作 6（マシン: M6, 処理時間: 7）の開始時間: 61.0
ジョブ Job2 の操作 0（マシン: M6, 処理時間: 1）の開始時間: 5.0
ジョブ Job2 の操作 1（マシン: M4, 処理時間: 1）の開始時間: 6.0
ジョブ Job2 の操作 2（マシン: M5, 処理時間: 6）の開始時間: 13.0
ジョブ Job2 の操作 3（マシン: M3, 処理時間: 8）の開始時間: 19.0
ジョブ Job2 の操作 4（マシン: M7, 処理時間: 6）の開始時間: 35.0
ジョブ Job2 の操作 5（マシン: M2, 処理時間: 7）の開始時間: 41.0
ジョブ Job2 の操作 6（マシン: M1, 処理時間: 7）の開始時間: 52.0
ジョブ Job3 の操作 0（マシン: M5, 処理時間: 3）の開始時間: 10.0
ジョブ Job3 の操作 1（マシン: M2, 処理時間: 6）の開始時間: 13.0
ジョブ Job3 の操作 2（マシン: M7, 処理時間: 3）の開始時間: 22.0
ジョブ Job3 の操作 3（マシン: M6, 処理時間: 3）の開始時間: 25.0
ジョブ Job3 の操作 4（マシン: M1, 処理時間: 9）の開始時間: 31.0
ジョブ Job3 の操作 5（マシン: M3, 処理時間: 9）の開始時間: 48.0
ジョブ Job3 の操作 6（マシン: M4, 処理時間: 6）の開始時間: 61.0
ジョブ Job4 の操作 0（マシン: M5, 処理時間: 10）の開始時間: 0.0
ジョブ Job4 の操作 1（マシン: M6, 処理時間: 6）の開始時間: 10.0
ジョブ Job4 の操作 2（マシン: M7, 処理時間: 6）の開始時間: 16.0
ジョブ Job4 の操作 3（マシン: M2, 処理時間: 8）の開始時間: 24.0
ジョブ Job4 の操作 4（マシン: M4, 処理時間: 3）の開始時間: 32.0
ジョブ Job4 の操作 5（マシン: M3, 処理時間: 7）の開始時間: 37.0
ジョブ Job4 の操作 6（マシン: M1, 処理時間: 8）の開始時間: 44.0
ジョブ Job5 の操作 0（マシン: M6, 処理時間: 8）の開始時間: 16.0
ジョブ Job5 の操作 1（マシン: M5, 処理時間: 8）の開始時間: 24.0
ジョブ Job5 の操作 2（マシン: M2, 処理時間: 6）の開始時間: 32.0
ジョブ Job5 の操作 3（マシン: M4, 処理時間: 10）の開始時間: 39.0
ジョブ Job5 の操作 4（マシン: M7, 処理時間: 9）の開始時間: 49.0
ジョブ Job5 の操作 5（マシン: M3, 処理時間: 8）の開始時間: 58.0
ジョブ Job5 の操作 6（マシン: M1, 処理時間: 8）の開始時間: 70.0
ジョブ Job6 の操作 0（マシン: M6, 処理時間: 5）の開始時間: 0.0
ジョブ Job6 の操作 1（マシン: M2, 処理時間: 5）の開始時間: 5.0
ジョブ Job6 の操作 2（マシン: M3, 処理時間: 9）の開始時間: 10.0
ジョブ Job6 の操作 3（マシン: M7, 処理時間: 9）の開始時間: 25.0
ジョブ Job6 の操作 4（マシン: M5, 処理時間: 9）の開始時間: 38.0
ジョブ Job6 の操作 5（マシン: M4, 処理時間: 9）の開始時間: 49.0
ジョブ Job6 の操作 6（マシン: M1, 処理時間: 10）の開始時間: 59.0
ジョブ Job7 の操作 0（マシン: M5, 処理時間: 6）の開始時間: 32.0
ジョブ Job7 の操作 1（マシン: M4, 処理時間: 1）の開始時間: 38.0
ジョブ Job7 の操作 2（マシン: M3, 処理時間: 4）の開始時間: 44.0
ジョブ Job7 の操作 3（マシン: M2, 処理時間: 2）の開始時間: 48.0
ジョブ Job7 の操作 4（マシン: M6, 処理時間: 1）の開始時間: 50.0
ジョブ Job7 の操作 5（マシン: M7, 処理時間: 10）の開始時間: 58.0
ジョブ Job7 の操作 6（マシン: M1, 処理時間: 1）の開始時間: 69.0
ジョブ Job8 の操作 0（マシン: M3, 処理時間: 4）の開始時間: 0.0
ジョブ Job8 の操作 1（マシン: M5, 処理時間: 4）の開始時間: 19.0
ジョブ Job8 の操作 2（マシン: M2, 処理時間: 1）の開始時間: 23.0
ジョブ Job8 の操作 3（マシン: M1, 処理時間: 7）の開始時間: 24.0
ジョブ Job8 の操作 4（マシン: M7, 処理時間: 1）の開始時間: 34.0
ジョブ Job8 の操作 5（マシン: M4, 処理時間: 1）の開始時間: 35.0
ジョブ Job8 の操作 6（マシン: M6, 処理時間: 6）の開始時間: 36.0
printempsでの実行結果
近似解を出すSolverということで、解は最適解ではなくなっていますが(2割ぐらい悪化している)、圧倒的に高速ですね。
実行時間 0.1秒
最適解：93
monta@JIJI:~/printemps$ time build/application/Release/mps_solver.exe /home/monta/PyCode/jobshop/jobshop.mps
real 0m0.246s
user 0m1.041s
sys 0m0.035s
実行しても標準出力に何も表示されませんがファイルが3つ作成され、incumbent.solに解が含まれています。
monta@JIJI:~/printemps$ ls -rlt
～中略～
-rw-r--r-- 1 monta monta 64941 Oct 22 21:12 status.json
-rw-r--r-- 1 monta monta 5037 Oct 22 21:12 incumbent.sol
-rw-r--r-- 1 monta monta 57828 Oct 22 21:12 incumbent.json
monta@JIJI:~/printemps$ head incumbent.sol
=obj= 9.3000000000e+01
Makespan 93
Start_Job1_0 0
Start_Job1_1 16
Start_Job1_2 27
～後略～
留意事項
PRINTEMPSは連続変数があるとデフォルトでは対応してくれませんでした。
変数はIntegerとするか、試していませんが--accept-continuousオプションを付けると良いようです。
連続変数を含むMPSファイルを処理しようとしたときのエラー
(.venv) monta@JIJI:~/PyCode/jobshop$ time ~/printemps/build/application/Release/mps_solver.exe ./jobshop.mps
terminate called after throwing an instance of 'std::logic_error'
what(): /home/monta/printemps/printemps/model/model.h, line 3488, function import_mps: The MPS file includes continuous variables.
Aborted (core dumped)
real 0m0.012s
user 0m0.004s
sys 0m0.000s