Какие ограничения делают мою проблему неосуществимой? - PullRequest
Новая
       37

Какие ограничения делают мою проблему неосуществимой?

0 голосов
/ 15 мая 2018

Я использую CPLEX 12.8 для моделирования своего дипломного проекта, и у меня есть проблема, которую я не могу решить.Я получаю следующий вывод: 

CPLEX 12.8.0.0: integer infeasible.
1828 MIP simplex iterations
316 branch-and-bound nodes
No basis.

Есть ли способ узнать, какие ограничения противоречат друг другу?

1 Ответ

0 голосов
/ 15 мая 2018

Добро пожаловать в ТАК!

CPLEX и аналогичные решатели способны генерировать "неприводимый неосуществимый набор" ограничений (IIS) для неосуществимых задач. Это подмножество исходных ограничений, которое имеет следующие свойства:

  • Невозможно решить проблему со всеми активными ограничениями IIS.
  • Снятие любого из этих ограничений позволит решить проблему.

Изучение IIS часто помогает найти противоречивые ограничения. Обратите внимание, что некоторые проблемы могут иметь более одного IIS; решатель будет находить только один IIS каждый раз, когда вы его запускаете, поэтому при наличии нескольких конфликтов вам может понадобиться повторить процесс несколько раз, пока вы не найдете и не исправите их все. Поиск IIS может быть довольно медленным.

Исходя из ваших тегов, я предполагаю, что вы используете CPLEX через AMPL. Вот некоторая документация , в которой рассматривается, как получить доступ к возможностям CPLEX IIS через AMPL. В основном, вставьте следующие команды до и после «решить»: 

option cplex_options 'iisfind 1';
solve;
display {i in 1.._ncons: _con[i].iis <> "non"} (_conname[i], _con[i].iis);

В этом списке будут перечислены ограничения, связанные с неосуществимостью. Вы также можете использовать «iisfind 2», который работает медленнее, но пытается найти меньший IIS.

Иногда возможность предварительного разрешения AMPL мешает использовать IIS finder. AMPL выполняет «предварительный» шаг, который пытается уменьшить размер проблемы путем выявления избыточных ограничений и так далее.

Обычно это полезно, поскольку снижает требования к памяти и время решения, но может помешать устранению неисправностей. Предварительная оценка может означать, что не все ограничения передаются в решатель (в этом случае ваш IIS может не быть истинным IIS, поскольку решатель не видит избыточные ограничения), а иногда AMPL идентифицирует невозможность в presolve, и в этом случае никогда не отправляет его солверу, поэтому вы не можете использовать возможности IIS.

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

 option presolve 0; #set to 10 to re-enable presolve

Надеюсь, это поможет с вашей проблемой.

...