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

Question

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

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

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

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

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

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

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

Answer 1

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

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

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} , который укажет, какой диапазон значений х был выбран. Ограничения выше, может быть заменены (я покажу случай индекс 1, но вы должны были бы это для все п индексов):

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 будут влиять на приемлемость решения вашей модели.

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