私が試したソルバー (CPLEX、CBC) で解決するのに非常に時間がかかる整数線形計画法の問題があります。彼らはそれを完全に証明するのに永遠にかかります.
最小化問題の客観的な値の自明な下限を計算するのは簡単ですが、CPLEX の出力 (Best Bound 列) を見ると、長い間、その下限に近づいていないことがわかります。すぐに本当に良い解を見つけますが、最適な解がもっと優れている可能性があると誤って考えます。
これらのソルバーがどのように機能するかはよくわからないことを認めざるを得ませんが、信じられないほど楽観的なソリューションを探して、途方もなく弱い下限を改善しようとして時間を無駄にしているようです。だから私の質問は：
ソルバーに適切な目的の下限を伝えることで、より速く実行できるでしょうか?
もしそうなら、どのソルバーが追加入力として提供された既知の下限を受け入れることができますか?
例として、実行例からの CPLEX の出力の最初の数行を貼り付けます (目標のさらなる改善と最良の境界の非常に遅い改善なしで、はるかに長く続きます)。
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
0 0 -388.6997 178 -388.6997 9
* 0+ 0 297.0000 -388.6997 9 230.88%
* 0+ 0 275.0000 -388.6997 9 241.35%
0 2 -388.6997 178 275.0000 -387.8106 9 241.02%
* 20+ 20 185.0000 -307.6363 80 266.29%
* 30+ 30 135.0000 -307.6363 90 327.88%
* 30+ 30 94.0000 -307.6363 90 427.27%
* 60+ 60 90.0000 -307.6363 120 441.82%
* 160+ 126 77.0000 -307.6363 272 499.53%
* 200+ 93 12.0000 -307.4836 325 ---
300 182 -135.2988 107 12.0000 -268.6638 466 ---
1200 934 -50.6022 85 12.0000 -206.2938 1480 ---
2197 1755 -96.9612 93 12.0000 -189.8013 2470 ---
3226 2600 -2.8316 87 12.0000 -179.9669 3480 ---
4374 3521 -156.2442 110 12.0000 -170.4183 4567 ---
5490 4421 -128.0871 97 12.0000 -167.3696 5623 ---
6971 5603 -147.5022 108 12.0000 -162.4180 7055 ---
8739 6997 -103.5374 113 12.0000 -156.3532 8673 ---
ソルバーに、目的が 10 未満の解を探す必要がないように (より単純な方法でそれを証明できるため)、特に負の目的値を使用しないように (私のモデルでは不可能なため) 教えてくれたらいいのにと思います。