Производительность MIP: решение найдено быстро, но решатель продолжает поиск

У меня есть линейная задача MIP, для которой Гуроби находит решение за 10 итераций.
Чтобы действительно доказать, что решение является оптимальным, требуется гораздо больше времени.
Журнал находится ниже.

Есть ли способ сказать Гуроби остановиться?

Я попробовал инструмент автоматической настройки.
Он говорит мне установить Heuristics=0.
Если я последую этому совету, общее время поиска решения уменьшится.
Но это общее время намного больше, чем время 10 итераций с включенной эвристикой.

Я новичок в MIP, поэтому из журнала я действительно не знаю, какой параметр будет хорошим критерием остановки (GAP, BestBound, ...).

Optimize a model with 434 rows, 380 columns and 1332 nonzeros
Found heuristic solution: objective -0.667665
Presolve removed 74 rows and 72 columns
Presolve time: 0.00s
Presolved: 360 rows, 308 columns, 1428 nonzeros
Variable types: 188 continuous, 120 integer (120 binary)

Root relaxation: objective 1.454681e+00, 383 iterations, 0.00 seconds

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

     0     0    1.45468    0   80   -0.66764    1.45468   318%     -    0s
H    0     0                      -0.2958055    1.45468   592%     -    0s
     0     0    1.33723    0   87   -0.29581    1.33723   552%     -    0s
H    0     0                      -0.0360081    1.33723  3814%     -    0s
     0     0    1.32350    0   88   -0.03601    1.32350  3776%     -    0s
     0     0    1.31284    0   62   -0.03601    1.31284  3746%     -    0s
     0     5    1.31284    0   62   -0.03601    1.31284  3746%     -    0s
H  407   237                      -0.0223424    1.12204  5122%  13.3    0s
H  606   348                      -0.0139589    1.09397  7937%  12.8    0s
H 1209   691                       0.0000905    1.00647     -   12.2    0s
H 1543   852                       0.0000935    1.00647     -   15.4    1s
 12464  8280    0.31259   37   45    0.00009    0.83003     -   16.1    5s
 32517 21750     cutoff   44         0.00009    0.75633     -   15.8   10s
 41026 27530    0.15234   45   67    0.00009    0.40720     -   15.7   15s
 67008 28123    0.00079   87    9    0.00009    0.00252  2599%  12.1   20s
 123660 32561    0.00088   82   13    0.00009    0.00197  2008%   8.0   25s
 183205 53085    0.00111   80   14    0.00009    0.00175  1766%   6.5   30s
 242669 70749    0.00115   82   13    0.00009    0.00160  1611%   5.6   35s
 300464 86096    0.00016   83   14    0.00009    0.00150  1499%   5.2   40s
 360002 99530    0.00116   77   12    0.00009    0.00141  1407%   4.8   45s
 419747 111348    0.00092   82   11    0.00009    0.00134  1330%   4.5   50s
 479404 121404    0.00094   78   18    0.00009    0.00128  1265%   4.4   55s
 538670 130127    0.00061   86    9    0.00009    0.00122  1206%   4.2   60s
 599541 137721    0.00071   87   10    0.00009    0.00117  1152%   4.1   65s
 659419 143977    0.00049   81   13    0.00009    0.00113  1104%   4.0   70s
 719366 148872    0.00090   82    7    0.00009    0.00108  1058%   3.9   75s
 778800 152645     cutoff   81         0.00009    0.00104  1015%   3.8   80s
 838419 155900    0.00064   82   12    0.00009    0.00101   975%   3.7   85s
 898257 157892    0.00038   82   11    0.00009    0.00097   937%   3.7   90s
 959133 158950    0.00064   82    9    0.00009    0.00093   898%   3.6   95s
 1019118 158672     cutoff   86         0.00009    0.00090   863%   3.6  100s
 1077389 157263    0.00034   79   16    0.00009    0.00087   828%   3.5  105s
 1136559 154819    0.00015   83    6    0.00009    0.00084   795%   3.5  110s
 1197408 151286    0.00033   79   11    0.00009    0.00080   760%   3.5  115s
 1256981 146998    0.00058   85   11    0.00009    0.00077   726%   3.4  120s
 1315053 141986    0.00015   87    9    0.00009    0.00074   693%   3.4  125s
 1369901 136123     cutoff   84         0.00009    0.00071   662%   3.4  130s
 1423732 129573    0.00042   84   11    0.00009    0.00068   631%   3.3  135s
 1483143 120871    0.00036   86   11    0.00009    0.00065   593%   3.3  140s
 1541197 111293    0.00020   84   11    0.00009    0.00061   553%   3.3  145s
 1598804 100832    0.00030   81   15    0.00009    0.00057   511%   3.3  150s
 1655909 89315    0.00039   84   11    0.00009    0.00053   466%   3.2  155s
 1704245 77614    0.00018   82   15    0.00009    0.00049   420%   3.2  160s
 1750024 63910    0.00014   83   12    0.00009    0.00044   367%   3.2  165s
 1795438 46988     cutoff   78         0.00009    0.00037   299%   3.2  170s
 1847433 21718    0.00012   82   10    0.00009    0.00026   178%   3.2  175s

Cutting planes:
  Gomory: 54
  MIR: 14
  Flow cover: 28

Explored 1875647 nodes (5924527 simplex iterations) in 178.11 seconds
Thread count was 4 (of 4 available processors)

Optimal solution found (tolerance 1.00e-04)
Best objective 9.353429694370e-05, best bound 9.353429694481e-05, gap 0.0%

gurobi mathematical-optimization linear-programming
person Community    schedule 19.02.2014    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Если вы хотите доказать, что решение является оптимальным, не прекращайте работу раньше срока. Инструмент настройки параметров grbtune очень полезен, но похоже, что вы сможете добиться большего, сосредоточив внимание на перемещении границы. Рекомендации по перемещению границы см. В разделе MIP документа Рекомендации по настройке параметров. Например, я бы попытался увеличить параметр Cuts, установив MIPFocus на 2 или 3 и / или установив Presolve на 2.

Отказ от ответственности: я отвечаю за техническую поддержку Gurobi.

person Greg Glockner    schedule 19.02.2014
comment
Ваши предложения помогли. У меня есть еще один вопрос. Есть ли параметр, который говорит Гуроби остановиться, когда |last_incumbent - current_incumbent|<1e-4? Или мне следует реализовать это с помощью обратного вызова? - person ; 19.02.2014
comment
Вам понадобится обратный звонок. Учтите, что у вас нет гарантии, что это приведет к оптимальному решению; мы видели много случаев, когда это приводило к неоптимальному решению. - person Greg Glockner; 19.02.2014
comment
Ссылка на раздел MIP больше не доступна. - person hola; 28.04.2019

arrow_upward
2
arrow_downward

Я просто хочу добавить несколько пояснений:

Эвристика Гуроби нашла решение за 10 итераций. Нет никакой гарантии, что это решение является оптимальным, в частности, остальное время уходит на то, чтобы доказать это.

При отключении эвристики указанное решение (просто) обнаруживается позже. Предлагаемая настройка параметров является успешной в том отношении, что общее время выполнения (решение доступно и доказано, что оно является оптимальным) уменьшается (даже если фактическое решение будет доступно позже).

Как указано выше Грегом Глокнером, поскольку большая часть времени уходит на доказательство оптимальности вашего решения, акцент / акцент на этом может ускорить время решения. Вы также можете определить критерии остановки, мои настройки параметров Toleranze / Gap, как описано здесь .

person Martin    schedule 26.02.2014