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

Question

У меня есть проблема оптимизации, которая имеет в целевой функции 2 умноженные переменные, делая модель квадратичной.

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

, Первая переменная является действительной, в диапазоне [0, 1], вторая - действительной, в диапазоне от 0 до inf. Этот может без проблем быть целым числом.

Критическая часть в целевой функции выглядит следующим образом:

max ... + var1 * var2 + ...

У меня были похожие проблемы в ограничениях, но они были легко решаемы.

Как я мог решить такую ​​проблему в целевой функции?

Answer 1

Модели в таком виде на самом деле называются задачами билинейной оптимизации. Типичный подход к линеаризации билинейных терминов заключается в том, что называется оболочкой Маккормика.

Рассмотрим переменные x и y, где вы хотите x*y в целях вашей проблемы максимизации. Если мы предположим, что x и y ограничены xL <= x <= xU а также yL <= y <= yUтогда мы можем заменить x*y с wверхняя граница для количества со следующими ограничениями (вы можете посмотреть деривацию здесь):

w <= xU*y + x*yL - xU*yL
w <= x*yU + xL*y - xL*yU
xL <= x <= xU
yL <= y <= yL

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

Если вы хотите более жесткую привязку x*yВы можете разделить интервал по одной из переменных (здесь я буду использовать x) на диапазоны [xL1, xU1], [xL2, xU2], ..., [xLn, xUn], вводя вспомогательные непрерывные переменные {x1, x2, ..., xn} и {w1, w2, ..., wn}, а также вспомогательные двоичные переменные {z1, z2, ..., zn}, которые будут указывать, какой диапазон значений x был выбран. Приведенные выше ограничения могут быть заменены на (я покажу случай индекса 1, но они понадобятся для всех n индексов):

w1 <= xU1*y + x1*yL - xU1*yL*z1
w1 <= x1*yU + xL1*y - xL1*yU*z1
xL*z1 <= x1 <= xU*z1

По сути, вы будете иметь x1=0 и w1 <= 0 всякий раз, когда z1=0 (иначе эта часть диапазона не выбрана), и у вас будет нормальный конверт Маккормика, если z1=1 (иначе эта часть диапазона выбрана),

Последний шаг - генерировать x и w из зависящих от диапазона версий этих переменных. Это можно сделать с помощью:

x = x1 + x2 + ... + xn
w = w1 + w2 + ... + wn

Чем больше вы сделаете n, тем точнее будет оценка для билинейного члена. Однако большие значения n будут влиять на возможность решения вашей модели.

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