尽管数学上不可能，古罗比报告了无界模型 [英] Gurobi reports unbounded model despite mathematical impossibility

问题描述

我正在使用Julia出色的JuMP软件包以Gurobi 6.0.4作为求解器来求解线性程序. 目标函数是决策变量的总和，明确定义为非负数，问题要求将其最小化.出于某种原因，Gurobi认为该模型是无界的.

I'm using Julia's wonderful JuMP package to solve a linear program with Gurobi 6.0.4 as a solver. The objective function is a sum of decision variables, clearly defined as nonnegative, and the problem requires it to be minimized. For some reason, Gurobi thinks the model is unbounded.

这是变量和目标的定义:

Here is the definition of the variables and the objective:

@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列.在预求解步骤(删除少于1k的行和列)之后，我们有24k的行和50k的列.日志如下所示:

Strange observation #1: although this is a minimization problem, the log for Gurobi's BarrierSolve method clearly shows the objective function increasing at each iteration. In addition, Gurobi seems to pull a switcheroo between the number of rows and the number of columns. Before the presolve step, the model has 50k rows and 25k columns. After the presolve step (which removes less than 1k rows and columns), we have 24k rows and 50k columns. The log looks like this:

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方法.当我同时执行这两项操作时，目标函数不断增加(！)，并且屏障日志如下所示:

Strange observation #2: BarrierSolve eventually terminates with the status InfeasibleOrUnbounded. It then suggests setting InfUnbdInfo=1 and using Gurobi's homogeneous BarrierSolve method by setting BarHomogeneous=1. When I do both of these things, the objective function keeps increasing(!) and the barrier log looks like this:

                      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时做错了什么?我怀疑这可能是某种数字错误，但是我不确定如何解决它.

I don't understand how a linear program can be unbounded when it involves the minimization of a sum of nonnegative variables. Is this an issue with Gurobi or did I do something wrong in setting up the LP ? I suspect it might be some sort of numerical error, but I'm not sure how to troubleshoot it.

我发现该问题的部分解决方法是放宽一些约束，并人为地使可行性区域变得更好.看来问题实际上是一个可行性问题，而不是一个无边界问题，这意味着Gurobi可能实际上是在指对偶的无边界?

I found a partial fix to the problem by loosening some constraints and making the feasibility region artificially better. It seems the problem was really a feasibility issue and not an unboundedness issue, which means Gurobi might actually have been referring to an unboundedness of the dual ?

感谢您的帮助！

推荐答案

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

Your problem is poorly conditioned due to "narrow" range constraints. If they really need to be range constraints, consider rescaling your problem. If they are more like "approximate" equality constraints, consider adding a slack variable and making it an actual equality constraint, and put a penalty on the slacks in the objective.

这篇关于尽管数学上不可能，古罗比报告了无界模型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！