尽管数学上不可能，Gurobi 报告了无限模型 [英] 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 列.在 presolve 步骤(删除少于 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.

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