Я пытаюсь решить MILP, который может иметь несколько ответов (все дают одинаковое значение для целевой функции). Является ли алгоритм на основе ветвей и границ, способный находить все решения?Найти все ответы на Mixed-Integer-Linear-Program используя ветку и границу?
Возможно ли найти все решения для такого MILP с использованием MATLAB (с использованием, например, intlinprog).
Спасибо.
Стандартный алгоритм, связанный с ветвями и границами, определяет узел, если объективное значение его релаксации LP больше или равно текущей верхней верхней границе (при условии, что проблема минимизации). Теоретически вы можете изменить это, чтобы вы только поняли узел, если значение LP равно , строго больше, чем текущий UB. Затем вы можете сохранить список всех решений, которые связывают текущий UB. Когда вы найдете новый лучший UB, очистите список и начните строить новый.
Очевидно, что это замедлит поиск, особенно если, по словам TimChippingtonDerrick, существует много оптимумов.
Для этого необходимо настроить код B & B. Я уверен, что вы могли бы не делать это в MATLAB, если вы не напишете свой собственный код с веткой и перекрестием, а затем вызовите из него решатель LP MATLAB. Возможно, вы сможете это сделать в API CPLEX или другом решателе. Вероятно, вам придется в конце концов написать собственный код B & B.
Имейте в виду, что для любого нетривиального MILP может быть только несколько или огромное количество эквивалентных решений. Очень легко построить проблемы, которые имеют значительную внутреннюю симметрию, которые проявляют это поведение, а некоторые проблемы реального мира имеют схожие характеристики. Например. Телевизионные рекламные прорези, где замена разных, но похожих рекламных объявлений между перерывами дает другое решение с той же целью. – TimChippingtonDerrick