我正在使用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实际上可能是在指双重性的无边界?

谢谢你的帮助!

最佳答案

您的问题由于“狭窄”的范围约束而无法很好地解决。如果确实需要限制范围,请考虑重新调整您的问题。如果它们更像是“近似”等式约束,请考虑添加一个松弛变量并将其变为实际的等式约束,然后对目标中的松弛进行惩罚。

10-06 05:24