Julia のすばらしい JuMP パッケージを使用して、Gurobi 6.0.4 をソルバーとして線形計画法を解いています。目的関数は決定変数の合計であり、非負として明確に定義されており、問題ではそれを最小化する必要があります。何らかの理由で、Gurobi はモデルが無限であると考えています。
変数と目的の定義は次のとおりです。
@defVar(model, delta2[i=irange,j=pair[i]] >= 0)
@setObjective(model, Min, sum{delta2[i,j], i=irange, j=pair[i]})
奇妙な観察 #1: これは最小化問題ですが、Gurobi の BarrierSolve メソッドのログは、反復ごとに目的関数が増加していることを明確に示しています。さらに、Gurobi は行数と列数の間で切り替えを行うようです。事前解決ステップの前に、モデルには 50,000 行と 25,000 列があります。解決前のステップ (1,000 行と 1,000 列未満を削除) の後、24,000 行と 50,000 列になりました。ログは次のようになります。
Optimize a model with 50422 rows, 24356 columns and 1846314 nonzeros
Coefficient statistics:
Matrix range [1e-04, 2e+00]
Objective range [1e+00, 1e+00]
Bounds range [9e-02, 2e+02]
RHS range [6e+00, 4e+03]
Presolve removed 164 rows and 635 columns
Presolve time: 0.79s
Presolved: 24192 rows, 49787 columns, 1836247 nonzeros
Ordering time: 1.60s
奇妙な観察 #2: BarrierSolve は最終的に status で終了しますInfeasibleOrUnbounded。次に、InfUnbdInfo=1Gurobi の均一 BarrierSolve メソッドを設定して使用することを提案しますBarHomogeneous=1。これらの両方を行うと、目的関数は増加し続け (!)、バリア ログは次のようになります。
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 -6.95693531e+06 1.94975493e+02 1.10e+01 9.79e+02 1.39e+03 4s
1 -3.18487510e+06 7.02065119e+06 5.50e-01 5.57e+02 3.45e+02 5s
2 -8.43175324e+05 2.31465924e+06 4.81e-02 1.60e+02 9.32e+01 6s
3 -2.37967254e+05 6.66124613e+05 6.51e-03 3.69e+01 2.35e+01 8s
4 -7.49693243e+04 1.81252940e+05 1.64e-03 9.49e+00 6.46e+00 9s
5 -3.20211009e+04 8.98339452e+04 6.25e-04 5.30e+00 3.11e+00 10s
6 -1.04312874e+04 5.17677474e+04 2.06e-04 3.06e+00 1.65e+00 11s
7 4.58252702e+02 4.04538611e+04 1.24e-04 2.19e+00 1.23e+00 12s
8 3.40831629e+04 5.42543944e+04 7.65e-05 1.87e+00 1.54e+00 13s
9 3.10110459e+05 2.25902448e+05 5.50e-05 1.87e+00 6.81e+00 15s
10 1.59299448e+06 9.88980682e+05 5.73e-05 1.85e+00 3.37e+01 16s
11* 1.88981433e+07 1.28711401e+07 2.93e-06 6.92e-01 1.14e-03 17s
12* 1.65096505e+08 3.73470456e+08 5.57e-06 5.73e-02 1.40e-04 18s
13* 7.18252597e+09 3.21890978e+09 2.62e-06 2.01e-03 4.60e-06 20s
14* 1.15822505e+12 7.53575462e+10 1.50e-05 6.18e-06 8.50e-09 21s
15* 1.08512896e+13 2.57735417e+12 2.92e-06 6.99e-08 1.22e-10 22s
16* 3.03152292e+14 7.54681485e+13 1.21e-07 7.50e-10 1.28e-12 23s
Barrier performed 16 iterations in 23.41 seconds
Unbounded model
非負変数の和の最小化を伴う線形計画法がどのように無制限になるのか理解できません。これは Gurobi の問題ですか、それとも LP の設定に何か問題がありましたか? 何らかの数値エラーであると思われますが、トラブルシューティング方法がわかりません。
編集:いくつかの制約を緩め、実現可能領域を人為的に改善することで、問題の部分的な修正を見つけました。問題は実際には実行可能性の問題であり、無限の問題ではなかったようです。つまり、Gurobi は実際には双対の無限性に言及していた可能性があります。
ご協力いただきありがとうございます！