mathematical-optimization - 尽管数学上不可能，但 Gurobi 报告了无限模型

Question

我正在使用 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 列。在预求解步骤(删除少于 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 实际上可能指的是对偶的无界性？

感谢您的帮助!

Answer 1

由于“窄”范围限制，您的问题条件很差。如果他们确实需要范围限制，请考虑重新调整您的问题。如果它们更像是“近似”等式约束，请考虑添加松弛变量并使其成为实际等式约束，并对目标中的松弛变量施加惩罚。