Как попросить второе лучшее решение для MIP с использованием JuMP
У меня есть проблема со смешанным целочисленным программированием. Я могу использовать JuMP, чтобы найти оптимальное решение. Но как мне найти второе лучшее решение? Или третий лучший и т. Д.
Это может потенциально быть другим столь же оптимальным решением, или это может быть худшее решение, или это может быть :Infeasible - Там может быть не большинство решений.
Я знаю, что для задачи, подобной TSP, я могу найти дополнительные решения, постепенно удаляя ссылки, которые находятся на оптимальном пути (т. Е. Устанавливая расстояния между некоторыми городами как бесконечные). Для задачи с планировочным типом я также могу постепенно установить доступность временных интервалов, используемых на оптимальном пути, который должен быть запрещен.
Но есть ли общий способ сделать это, не кодируя себя проблемными методами, запрещающими это решение?
2 ответа
Вы можете добавить разрез, чтобы запретить только что найденное оптимальное решение и решить его снова. Скажем, ваша модель имеет бинарные переменные x(i), Позволять a(i):=x*(i) быть оптимальным решением, найденным ранее. Затем добавьте линейное ограничение:
sum(i, x(i) * a(i)) - sum(i, x(i) * (1-a(i))) <= sum(i, a(i)) - 1
и решить снова. (Эта вещь получена здесь). Если x это общая целочисленная переменная, все становится сложнее.
Некоторые решатели, такие как Cplex и Gurobi, также имеют так называемый пул решений, который также может сделать это.
У меня такой же вопрос для PuLP в Python.
Как мы можем получить второе (или несколько последующих) лучших решений, используя PuLP в Python?