关于 model.optimize() 和 model.feasRelaxS(1, True, False, True) 输出的混淆

Question

我已经对 MILP 问题进行了建模。

执行代码时

m.Optimize()

Output looks like this:

Optimize a model with 798001 rows, 312006 columns and 2117780 nonzeros
Variable types: 1920 continuous, 310086 integer (310080 binary)
Coefficient statistics:
 Matrix range [3e-01, 2e+04]
 Objective range [1e-01, 9e+02]
 Bounds range [1e+00, 3e+04]
 RHS range [3e-01, 3e+04]
Presolve removed 725090 rows and 191031 columns
Presolve time: 3.22s

Explored 0 nodes (0 simplex iterations) in 3.59 seconds
Thread count was 1 (of 8 available processors)

Solution count 0

Model is infeasible
Best objective -, best bound -, gap -

但是当执行下面的代码时：

copy1 = m.copy()

if m.status == GRB.INFEASIBLE:
 copy1.feasRelaxS(1, True, False, True)
 copy1.optimize()

Output looks like this:

Solve phase I feasrelax model to determine minimal relaxation

Optimize a model with 798001 rows, 1114022 columns and 2919796 nonzeros
Model has 802016 quadratic objective terms
Variable types: 803936 continuous, 310086 integer (310080 binary)
Coefficient statistics:
  Matrix range     [3e-01, 2e+04]
  Objective range  [0e+00, 0e+00]
  QObjective range [2e+00, 2e+00]
  Bounds range     [1e+00, 3e+04]
  RHS range        [3e-01, 3e+04]
Found heuristic solution: objective 3.175944e+24
Presolve removed 1620 rows and 64056 columns (presolve time = 6s) ...
Presolve removed 1620 rows and 64056 columns
Presolve time: 5.59s
Presolved: 796381 rows, 1049966 columns, 2909656 nonzeros
Presolved model has 800396 quadratic objective terms
Found heuristic solution: objective 3.169464e+24
Variable types: 802316 continuous, 247650 integer (247650 binary)

此处指定模型具有二次 Objective 项。

谁能指导我这两者到底有什么区别？以及为什么它给模型提供二次项？

Answer 1

您使用参数 (1, True, False, True) 调用 feasRelaxS。 docs 说：

feasRelaxS ( relaxobjtype, minrelax, vrelax, crelax )

If you specify relaxobjtype=1, the objective of the feasibility relaxation is to minimize the sum of the squares of the bound and constraint violations.

所以平方和不是线性的，Gurobi 需要使用一些非线性求解方法。如果是 QP 或 SOCP 或其他什么，那是 Gurobi 的决定。

这是引入二次项的地方：边界和约束违规的平方和。

输出：

Found heuristic solution: objective 3.169464e+24

看起来你的模型离可行还很远。

编辑： 或者可能不是。作为非 Gurobi 用户，我的印象是，这就是最终结果。但是你修剪了你的输出，这只是一个早期的启发式结果，我们现在不能对未知的最终结果说太多！

关于它在做什么的一般问题由文档句子回答：

The feasibility relaxation is a model that, when solved, minimizes the amount by which the solution violates the bounds and linear constraints of the original model

意思是：你不再关心你原来的 objective，而是关心一个新的，它表达了一些解决方案在违反约束和变量边界方面有多糟糕。

（旁注：所有这些都在文档中进行了解释，老实说：在我看来，与某些竞争对手相比，Gurobi 拥有非常好的文档！所以请使用它并且不要在不知道它们在做什么的情况下调用函数)

关于 model.optimize() 和 model.feasRelaxS(1, True, False, True) 输出的混淆

Confusion regarding model.optimize() and model.feasRelaxS(1, True, False, True) output

python

gurobi

mixed-integer-programming