我正在使用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似乎在行数和列数之间切换。在预求解步骤之前,模型有50k行和25k列。在presolve步骤(删除少于1k的行和列)之后,我们有24k的行和50k的列。日志如下所示:
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最终以状态
InfeasibleOrUnbounded
终止。然后建议设置InfUnbdInfo=1
并通过设置BarHomogeneous=1
使用Gurobi的齐次BarrierSolve方法。当我同时执行这两项操作时,目标函数不断增加(!),并且屏障日志如下所示: 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实际上可能是在指双重性的无边界?
谢谢你的帮助!
最佳答案
您的问题由于“狭窄”的范围约束而无法很好地解决。如果确实需要限制范围,请考虑重新调整您的问题。如果它们更像是“近似”等式约束,请考虑添加一个松弛变量并将其变为实际的等式约束,然后对目标中的松弛进行惩罚。