在 B&B 的每个节点上具有最佳边界 = objective 值的大型 MILP，为什么求解器不接受该解决方案？

Question

我正在使用 Gurobi 求解具有 SOS1 约束的大型 LP (MILP)：

Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (mac64)
Thread count: 8 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 3119076 rows, 2032775 columns and 6333365 nonzeros
Model fingerprint: 0x855c8063
Model has 446892 SOS constraints
Variable types: 2032775 continuous, 0 integer (0 binary)
Coefficient statistics:
  Matrix range     [1e-08, 1e+03]
  Objective range  [1e-02, 9e+03]
  Bounds range     [0e+00, 0e+00]
  RHS range        [1e-04, 1e+07]
Presolve removed 2248693 rows and 669948 columns (presolve time = 5s) ...
Presolve removed 2672897 rows and 1094152 columns (presolve time = 10s) ...
Presolve removed 2814218 rows and 1512747 columns (presolve time = 23s) ...
Presolve removed 2820613 rows and 1519174 columns (presolve time = 25s) ...
Presolve removed 2820613 rows and 1519206 columns (presolve time = 39s) ...
Presolve removed 2820613 rows and 1519559 columns (presolve time = 323s) ...
Presolve removed 2815897 rows and 1516923 columns
Presolve time: 323.65s
Presolved: 303179 rows, 515852 columns, 1185283 nonzeros
Presolved model has 243593 SOS constraint(s)
Variable types: 514173 continuous, 1679 integer (1679 binary)

求解器正在快速找到整数松弛解，然后在分支定界（或障碍？）方法中旋转很长时间，只找到与松弛解等效的 objective 值（如以及不可行的解决方案）：

Solved with primal simplex (primal model)

Root relaxation: objective 5.003962e+08, 49227 iterations, 24.29 seconds

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 5.0040e+08    0 10310          - 5.0040e+08      -     -  480s
     0     0 5.0040e+08    0 10310          - 5.0040e+08      -     -  512s
     0     2 5.0040e+08    0 10101          - 5.0040e+08      -     -  838s
     1     2 5.0040e+08    1 8813          - 5.0040e+08      - 38414 1031s
     3     2 5.0040e+08    2 8813          - 5.0040e+08      - 12870 1055s
     5     2 5.0040e+08    3 8806          - 5.0040e+08      -  7724 1074s
     7     2 5.0040e+08    4 8806          - 5.0040e+08      -  5517 1092s
...
 22445     2 infeasible 3856               - 5.0040e+08      -  74.8 17630s
 22474     2 5.0040e+08 3870 2779          - 5.0040e+08      -  74.9 17643s
 22488     2 5.0040e+08 3877 3069          - 5.0040e+08      -  75.1 17653s
 22490     2 5.0040e+08 3878 3069          - 5.0040e+08      -  75.0 17660s
 22534     2 infeasible 3900               - 5.0040e+08      -  75.6 17667s
 22578     2 5.0040e+08 3922 2980          - 5.0040e+08      -  75.9 17674s
 22622     1 infeasible 3944               - 5.0040e+08      -  76.1 17684s
 22663     2 5.0040e+08 3964 2953          - 5.0040e+08      -  76.3 17691s

由于这个特定的问题是为了测试，我知道宽松的objective值也是MILP的最优值。（如果这次测试成功，我将解决更大、更复杂的问题，我不知道最佳值）。

我的问题是：

为什么求解器不接受该解？
有没有办法缩短求解时间？（我知道我可以“ctrl+c”并接受当前的解决方案 - 但也许我应该更改求解器设置？似乎降低 MIPGap 不会影响求解时间，因为它没有显示任何间隙信息。我知道我可以设置截止时间。)

Answer 1

(1) 为什么解算器不接受解法？ 没有解法可以接受。松弛解不是整数可行的（如果是，求解器会立即停止）。

(2) 有没有办法缩短求解时间？ 获得更好性能的最佳方法是使用更好的公式。大量的 SOS1 限制条件有些令人担忧。最好改用二进制变量（可能需要良好的界限）。

在 B&B 的每个节点上具有最佳边界 = objective 值的大型 MILP，为什么求解器不接受该解决方案？

Large MILP with best bound = objective value at every node of B&B, why doesn't solver accept the solution?

optimization

performance

solver

mixed-integer-programming