Вычислить относительный разрыв оптимальности в задаче MIP GAMS

Я хочу рассчитать разрыв относительной оптимальности проблемы MIP, а также хочу прервать запуск в определенное время выполнения. Этот способ:

F(1)    
abs(mymodel.objest - mymodel.objval)/max(abs(mymodel.objest),abs(mymodel.objval))

не согласуется с пробелом, который GAMS рассчитывает в журнале. GAMS использует наилучшее целое число, чтобы найти разрыв, не являющийся текущим целевым значением. который правильный? и как сохранить текущее наилучшее целое число в параметре (например, .objval).

и, наконец, вычисление разрыва относительной оптимальности в алгоритме изгибов является правильным?

rgap = (upperBound - lowerBound)/(1 + abs(upperBound));

Что GAMS рассчитывает с помощью решения MIP

MIP Solution:   3334501534.000555    (1625 iterations, 0 nodes)
Final Solve:      56330158.829040    (2561 iterations)

Best possible:    48915652.476336
Absolute gap:   3285585881.524219
Relative gap:            0.985330

F (1) рассчитал разрыв с использованием mymodel.objval (mymodel.objval return Final Solve), поэтому расчетный разрыв составляет% 13, а значение mymodel.objval - 5,633016E + 7 (расчетный разрыв GAMS составляет% 98). поэтому мне нужно сохранить решение MIP в параметре, чтобы экспортировать его в файл Excel.


mixed-integer-programming gams-math
person mohammad reza sourati    schedule 16.08.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Существуют разные формулы для расчета разрыва относительной оптимальности. Это зависит от того, какой решатель вы используете. Некоторую информацию об этом можно найти в описании опции GAMS optCR. Руководство решателя, которое вы используете, может содержать более подробную информацию о фактически применяемой формуле.

ИЗМЕНИТЬ после обновления вопроса:

Как вы писали, mymodel.objval возвращает значение Final Solve. Если вы хотите вместо этого увидеть значение MIP Solution (поскольку ссылка Cplex делает это внутри), вы можете деактивировать окончательное решение. Однако, если Final Solve и MIP Solution настолько сильно отличаются, как в вашем примере, это часто указывает на некоторую проблему (обычно они (почти) идентичны). Часто это указывает на плохо масштабируемую модель. Возможно, вы могли бы улучшить ситуацию, ужесточив допуски Cplex (см. Параметры Cplex epopt, eprhs, epint) и активировав агрессивное масштабирование (параметр Cplex scaind 2). Активация mipkappastats (https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXmipkappastats) и quality (https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXquality) может предоставить вам дополнительную информацию. DataCheck=2 (https://www.gams.com/latest/docs/S_CPLEX.html#CPLEXdatacheck) могут возникнуть проблемы.

person Lutz    schedule 17.08.2020
comment
Привет, спасибо за ответ, проблема в том, что mymodel.objval не возвращает наиболее известное целочисленное значение решения. мне нужно последнее наиболее известное целочисленное значение для расчета rgap. см. это: support.gams.com/solver:what_is_optca_optcr - person mohammad reza sourati; 17.08.2020
comment
Итак, что вам возвращает mymodel.objval? Какой решатель вы используете? Можете поделиться, что пробовали? - person Lutz; 17.08.2020
comment
Я использовал Cplex 12.5.1.0, добавил к основному вопросу. - person mohammad reza sourati; 17.08.2020
comment
Спасибо, проблема настолько велика по количеству ограничений и переменных, что я очень быстро ее прерываю, разрыв между окончательным решением и решением MIP сокращается с течением времени. деактивация окончательного решения - хорошая идея, но каковы его последствия, кроме отсутствия надлежащих предельных значений, влияет ли это на время решения или что-то еще? - person mohammad reza sourati; 19.08.2020
comment
Это влияет на общее время решения, так что вы экономите время на окончательное решение. Таким образом, вы экономите время, а цена, которую вы платите, заключается в том, что вы не получаете обратно маржинальные выплаты. - person Lutz; 19.08.2020