仅通过不分枝的切割来证明最优性 (gurobi)

计算科学 混合整数规划
2021-12-10 03:37:26

我有一个 MIP,我几乎可以肯定地知道解决方案。我想用 gurobi 来证明真正的解决方案(即使它不是我提供的解决方案)与我给出的解决方案的偏差不应超过 0.5%。我相信简单地继续切割而不分支可能会节省更多时间。你知道我可以简单地进行切割而不在 gurobi 中分支的方法吗?谢谢!

这是代码性能:

Changed value of parameter LogFile to 
   Prev: gurobi.log   Default: 

Changed value of parameter MIPFocus to 3
   Prev: 0   Min: 0   Max: 3   Default: 0

Changed value of parameter Cuts to 3
   Prev: -1   Min: -1   Max: 3   Default: -1

Optimize a model with 1794 rows, 673 columns and 4180 non zeros

Found heuristic solution: objective -22.8549

Presolve removed 18 rows and 17 columns
Presolve time: 0.01s
Presolved: 1776 rows, 656 columns, 4464 nonzeros

Loaded MIP start with objective -342.641

Variable types: 592 continuous, 64 integer (64 binary)
Presolved: 1776 rows, 656 columns, 4464 nonzeros

Root relaxation: objective -6.775689e+02, 682 iterations, 0.02 seconds

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

     0     0 -677.56892    0   64 -342.64109 -677.56892  97.7%     -    0s
     0     0 -666.45290    0   72 -342.64109 -666.45290  94.5%     -    0s
     0     0 -658.68050    0   72 -342.64109 -658.68050  92.2%     -    1s
     0     0 -540.92023    0   72 -342.64109 -540.92023  57.9%     -    3s
     0     0 -503.36031    0   72 -342.64109 -503.36031  46.9%     -    4s
     0     0 -485.13025    0   72 -342.64109 -485.13025  41.6%     -    6s
     0     0 -472.73790    0   72 -342.64109 -472.73790  38.0%     -    8s
     0     0 -461.23185    0   72 -342.64109 -461.23185  34.6%     -    9s
     0     0 -453.99476    0   72 -342.64109 -453.99476  32.5%     -   10s
     0     0 -452.23014    0   72 -342.64109 -452.23014  32.0%     -   10s
     0     3 -452.23014    0   72 -342.64109 -452.23014  32.0%     -   11s
   642   586 -397.07656   12   54 -342.64109 -429.76289  25.4%   120   15s
  1425  1290 -397.34606   11   60 -342.64109 -422.53417  23.3%   114   20s
  1716  1553 -382.83438   18   72 -342.64109 -420.42709  22.7%   111   25s
  1727  1560 -376.17473   16   72 -342.64109 -420.42709  22.7%   110   30s
  1733  1564 -410.28764   10   72 -342.64109 -420.42709  22.7%   110   35s
  1744  1571 -382.83438   18   72 -342.64109 -420.42709  22.7%   109   40s
  1750  1577 -412.59771   12   69 -342.64109 -416.84728  21.7%   113   45s
  1817  1602 -380.32997   19   60 -342.64109 -404.73090  18.1%   120   50s
  2618  2045 -375.99924   18   62 -342.64109 -391.32863  14.2%   126   55s
  3159  2315 -369.40052   22   59 -342.64109 -386.33088  12.8%   127   60s
  3808  2595 -362.27693   20   60 -342.64109 -382.29310  11.6%   127   65s
  4503  2903 -350.90325   24   54 -342.64109 -379.52932  10.8%   126   71s
  4895  3078 -349.90847   23   55 -342.64109 -378.33598  10.4%   126   78s
  5339  3242 -363.26836   21   59 -342.64109 -376.77299  10.0%   126   80s
  6421  3664 -366.32746   21   56 -342.64109 -374.20072  9.21%   126   85s
  7560  4450 -357.93456   21   59 -342.64109 -371.61876  8.46%   126   90s
  8849  5297 -355.57657   21   59 -342.64109 -369.33074  7.79%   125   95s
 10004  6042 -357.02223   24   55 -342.64109 -367.63772  7.30%   124  100s
 11274  6819 -352.14570   23   55 -342.64109 -365.95440  6.80%   122  105s
 12362  7437 -357.95155   22   55 -342.64109 -364.73335  6.45%   122  110s
 13134  7882 -352.18831   25   47 -342.64109 -363.91508  6.21%   121  115s
 ...
1个回答

看Gurobi官网的可控属性列表和Gurobi官网的可控属性列表,我觉得不可能您可以关闭切割,但不能关闭分支,可能是因为分支定界仍会产生收敛算法,而我不知道只有切割的通用混合整数线性规划算法。削减也使你的 LP 松弛更大,而分支(没有削减)使得更小,以增加子问题为代价。

您可以改为尝试提供一个好的初始猜测(如果您知道;您的问题建议您这样做),然后使用 Gurobi 的参数调整启发式作为第一遍。然后,来自调整启发式的信息可以为更好地选择控制分支方向(和变量选择)和切割选择的参数提供信息。