时间戳

首页 > 解决方案 > 具有最佳界限的大型 MILP = B&B 每个节点的目标值，为什么求解器不接受该解决方案？

performance - 具有最佳界限的大型 MILP = B&B 每个节点的目标值，为什么求解器不接受该解决方案？

问题描述

我正在使用 Gurobi 解决具有 SOS1 约束（MILP）的大型 LP：

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)

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

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

由于这个特殊问题是用于测试的，我知道放松的目标值也是 MILP 的最优值。（如果此测试成功，我将解决我不知道最佳值的更大、更复杂的问题）。

我的问题是：

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

标签： performanceoptimizationsolvermixed-integer-programming

解决方案

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

(2)有没有办法提高求解时间？获得更好性能的最好方法是使用更好的配方。大量的 SOS1 约束有点令人担忧。改用二进制变量可能会更好（可能需要良好的界限）。

推荐阅读