Получение лучших решений для ILP

Я хотел бы использовать решатель ILP (например, lp_solve), чтобы найти решение проблемы оптимизации.

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

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

Существует ли решатель, который дает не только оптимальное решение, но и наилучшие n решений относительно заданной целевой функции?


person lynix    schedule 21.10.2013    source источник


Ответы (1)


Да, есть:

  1. Либо решатель поддерживает его через пул решений,

  2. или вам нужно создать этот пул решений самостоятельно с помощью функций обратного вызова, предоставляемых API решателя.

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

Еще по этой теме:

person Ali    schedule 21.10.2013
comment
Спасибо за эту подсказку! Проблема в том, что CPLEX коммерческий, и я не могу найти другого решателя с таким обратным вызовом (или пулом решений)... - person lynix; 21.10.2013
comment
@lynix Все известные мне решатели имеют такой обратный вызов. Какой решатель вы используете? - person Ali; 21.10.2013
comment
Мне больше всего нравится lpsolve, но это утверждает, что невозможно получить лучшие n решений из-за обрезки ветвей. - person lynix; 21.10.2013
comment
@lynix Хорошо, дайте мне немного времени, я постараюсь найти необходимые функции. Я не использовал lp_solve API, поэтому не могу рассказать вам больше об этом конкретном решении. - person Ali; 22.10.2013