Принуждение CPLEX к переходу на оптимальное решение LP

Все обсуждение ниже относится к двойной проблеме.

Неосновные переменные с нулевой приведенной стоимостью могут входить в базис на положительном уровне и формировать альтернативные оптимальные решения. Таким образом, если оптимальное целевое значение задачи равно z * и c'x является связанной целевой функцией, вы можете добавить ограничение c'x = z*, изменить целевую функцию на другую, позволить симплексу выполнить одну итерацию и повторить итерацию. Каждая итерация после второй должна (i) генерировать новое оптимальное решение или (ii) генерировать уже сгенерированное оптимальное решение, и в этом случае мы можем изменить целевую функцию и выполнить итерацию.

Этот метод описан здесь со ссылкой на C Функции API:

Для линейных программ уменьшенные до нуля затраты для небазовых переменных указывают на существование альтернативного оптимального базиса. Кроме того, вы можете использовать подпрограммы CPXgetgrad и CPXgetx, чтобы определить, является ли связанная опорная точка вырожденной (в этом случае значения решения остаются неизменными, но изменяется базис) или нет (в этом случае меняются и значения решения, и базис). Обратите внимание, что снижение затрат на резервные переменные является отрицательным из связанных двойных переменных. Кроме того, процедура CPXaddrows предоставляет простой способ перечислить альтернативные оптимальные решения. Предположим, что оптимальное целевое значение исходной задачи - z *, а c'x - соответствующая целевая функция. Используйте CPXaddrows, чтобы добавить следующее ограничение:

c'x = z*

Измените целевую функцию на другую цель; установить предел симплексной итерации 1 (один) (или предел решения 1 в случае MIP); затем несколько раз оптимизируйте проблему. Каждое возможное решение этой модифицированной проблемы является оптимальным решением исходной проблемы. Эта процедура предоставит некоторые, но не обязательно все, альтернативные оптимальные решения исходной проблемы. Обратите внимание, что этот метод добавления ограничения также будет работать на непрерывной модели с квадратичной целью, тогда как метод фиксации небазовых переменных с нулевыми сокращенными затратами не может быть легко распространен на нелинейные цели. Поскольку CPLEX решает выпуклые квадратичные программы, ограничение на квадратичную цель должно быть неравенством, а не равенством, как описано выше в случае линейной цели. Поскольку при переходе приложения от одного альтернативного оптимального решения к другому могут изменяться только небазовые переменные с уменьшенными затратами, равными 0 (нулю), вы также можете перечислить альтернативные оптимальные решения, используя подпрограммы CPXgetdj и CPXgetpi для определения небазовых структурных переменных и резервов с ненулевыми значениями. снижение затрат. Затем установите для этих структурных переменных их текущие значения с помощью CPXchgbds и исправьте переменные резерва с помощью CPXchgsense. Установите предел симплексной итерации равным 1 (один); поменять цель как раньше; и вы можете перечислить некоторые, но не все альтернативные оптимальные решения.

Другой способ, очень похожий, состоит в том, чтобы добавить небольшой случайный вектор к соответствующим коэффициентам целевой функции (т. Е. «Нарушить» цель), решить проблему и убедиться, что новая вершина не совпадает со старой вершиной и что она дает то же значение целевой функции, что и у старой вершины (если нет, возмущайте еще раз и повторите). Этот метод хорошо описан в этом посте от Пола Рубина.

Для проблем MIP CPLEX предоставляет пул решений, в котором хранится определенное количество уже найденных решений, и функцию populate, которая ищет другие решения. Этот пост (снова Пол Рубин) объясняет, как это работает в Java API.

Обновить

Продолжение комментария ниже:

1. Мне нужно мое оптимальное решение, чтобы оставаться неизменным, даже если есть другие решения. Я только хочу, чтобы основание изменилось в вырожденном случае.

Значение целевой функции останется прежним, поскольку мы добавляем ограничение, согласно которому цель должна быть равна своему оптимальному значению (c'x = z*). Когда я говорю «сгенерируйте новое оптимальное решение» выше, я имею в виду новый набор оптимальных двойственных значений, то есть другой оптимальный двойственный базис. Первичное решение останется тем же (при условии, что основная задача является вырожденной и для нее не существует нескольких оптимальных решений).

2. После изменения основы я хочу переоценить двойственные переменные. Если я добавлю c'x = z * в качестве ограничения, все мои двойники будут равны 0.

Тот факт, что все дуалы равны нулю, звучит как проблема реализации. Вы проверили, что полученный LP возможен и что возвращается конечное оптимальное решение? Кроме того, я не уверен, что понимаю первую часть приведенного выше утверждения (после изменения ... переменных). Изменение (двойственного) базиса по определению является переоценкой двойственных переменных. Когда проблема является первично вырожденной (что является текущим случаем), существует несколько двойственных оптимальных решений, поэтому смена базиса в двойственном пространстве приводит к тому же оптимальному значению решения и к тому же самому прямому решению. базис (если проблема не имеет как прямого, так и двойственного вырождения).

3. Я бы хотел воздержаться от решения, поскольку это то, чего я пытаюсь избежать в первую очередь: я мог бы напрямую рассчитать теневые цены, решив мою проблему с возмущенным b.

Это правда, но в этом случае нам нужно решить проблему 2 * n раз, где n - это размер b: нам нужно заменить каждый компонент b на b - 1 и b + 1 за раз.

Мне неизвестен какой-либо метод, который может сделать то, что вы ищете, без разрешения .. Я нашел соответствующее сообщение Тобиаса Ахтерберга, главного разработчика CPLEX, который, по сути, описывает тот же метод. Кроме того, эта статья восстанавливает оптимальное первичное решение из оптимального двойного решения с помощью разрешение LP снова. Это возможно без решения, если вы воспользуетесь структурой сетевого потока вашей проблемы, но это потребует создания индивидуального алгоритма для этой конкретной проблемы. Несколько лет назад я проделал нечто подобное для составления большого количества размеров, и это требует некоторых усилий.

Надеюсь, это поможет!