Почему CPLEX устанавливает для несвязанных переменных значение 1?

Question

Я работал над проблемой комбинаторной оптимизации, которую можно смоделировать как целочисленное линейное программирование. Я реализовал его как проект на c ++ в Visual Studio 2017 и CPLEX1271. Поскольку существует экспоненциально много ограничений, я реализовал ленивые ограничения с помощью IloCplex :: LazyConstraintCallbackI. На мой взгляд, следующая процедура представляет собой создание оптимального решения: каждый раз, когда определяется целочисленное решение, LazyConstraintCallbackI будет проверять его и добавлять некоторые нарушенные ограничения в модель, пока не будет получено оптимальное целочисленное решение.

Однако объективные значения, данные моей реализацией для разных входов, не всегда верны. После почти годичной периодической отладки и тестирования я наконец выяснил причину, которая очень связана с проблемами, но может быть объяснена (надеюсь) следующим крошечным примером: целочисленное линейное программирование с использованием четырех переменных типа bool x1, x2, x3 и x4

minimize x1
subject to: 
x1  ≥  x2
x1  ≥  x3
x1  ≥  x4
x2  + x3  ≥ 1
x1, x2, x3 and x4  ∈ {0, 1}​

Результат, выдаваемый cplex:

Solution status = Optimal
Objective value = 1
x1 = 1
x2 = 1
x3 = 1
x4 = 1​

Несомненно, объективное значение верное. Странно то, что cplex устанавливает x4 = 1. Несмотря на то, что x4 равно 1 или 0 не влияет на объективную ценность этого программирования. Но когда используется ленивый обратный вызов ограничений, это может привести к проблеме, добавив некорректного ограничения, а целочисленное программирование решается путем итеративного добавления нарушенных ограничений. Я хотел бы знать:

1. почему cplex устанавливает "несвязанную" переменную x4 равной 1, а не 0?
2. Что мне делать, чтобы сообщить CPLEX, что я хочу оставить такую ​​"несвязанную" переменную равной 0?

Answer 1

Поскольку нет ничего, что заставляло бы x4 = 0 в оптимальном решении, нет гарантии, что CPLEX установит x4 = 0? С чего бы это? Почему 0 предпочтительнее 1? Модель имеет два оптимальных решения: одно с x4 = 0 и одно с x4 = 1. Оба имеют объективное значение 1. CPLEX может свободно выбрать один из них.

Как сказал Саша в своих комментариях, единственный способ заставить x4 = 0 в оптимальном решении - добавить это ограничение в модель, например, установив для объективного коэффициента небольшое положительное значение.

Однако кажется странным, что ваш ленивый обратный вызов ограничения генерирует недопустимые ограничения из целочисленных возможных решений. Это похоже на ошибку: либо обратный вызов делает неверные предположения о модели (а именно, что x4 = 0 в любом оптимальном решении), либо есть ошибка где-то в logi c обратного вызова. Обратите внимание, что в рассматриваемой модели было бы нормально, если бы обратный вызов отключил решение с x4 = 1, так как это по-прежнему оставляет эквивалентное оптимальное решение с x4 = 0, и CPLEX в конечном итоге обнаружит это.