Когда мы решаем задачу максимизации MIP с помощью cplex, может ли эвристика cplex повлиять на верхнюю границу целевого значения?
насколько я понимаю, эвристика cplex может улучшить нижнюю границу оптимального значения, но НЕ верхнюю границу. но в моем тесте, если я отключу эвристику cplex, это дает очень плохую верхнюю границу. разница в верхних границах (включение / выключение эвристики) очень велика, чтобы ее игнорировать. Помоги мне :-(
В качестве базового примера для этого исследования давайте предположим, что ваш MIP представляет собой чистую двоичную линейную программу (BLP) с переменными решения только с двоичными значениями (без непрерывных переменных). Кроме того, предположим, что CPLEX решает вашу MIP, используя только базовые методы ветвления и привязки (BAB), исключая расширенные методы ветвления и выбора узлов.
Поскольку ваша программа является программой максимизации, как вы упомянули, хорошая эвристика, естественно, повлияет на нижнюю границу значения целевой функции оптимального решения.
В нашем простом примере верхняя граница будет в основном основана на наилучшем на данный момент (наилучшем с максимальным значении функции объекте) решении постоянно ослабляемых подзадач BLP. То есть решение LP для активных узлов (еще не обрезанных или разветвленных) в вашем BAB-дереве, где ограничение бинеарности для ваших переменных решения, скажем x_i ∈ {0, 1}^n, было заменено его непрерывным ослаблением, скажем x_i ∈ [0, 1]^n.
На этом этапе (мета) эвристика может иметь большое влияние, например, на
Выбор узлов имеет большое влияние на продвижение верхней границы (макс. Проблема) в процессе решения, и то же самое; естественно, меньшее пространство решений (из-за большого количества сокращенных узлов) увеличит вероятность / «скорость» улучшения верхней границы проблемы.
Другой момент в процессе, где хорошая эвристика может повлиять на процесс решения в целом, естественно, находится на стадии предварительной обработки; перед началом обхода дерева BAB. Действительно умная эвристика может существенно сократить пространство для решения, особенно если мы пытаемся решить проблему, которая допускает очевидный рефакторинг / декомпозицию в менее сложную проблему. Возможно, что такие шаги предварительной обработки не являются эвристикой (и поэтому не деактивируются при отключении эвристики CPLEX) сами по себе, но я бы сказал, что они находятся в одной семье.
