Wie konvertiert man quadratisches in lineares Programm?

Question

Ich habe ein Optimierungsproblem, das in der Zielfunktion 2 multiplizierte Variablen hat, was das Modell quadratisch macht.

Ich verwende zimpl, um das Modell zu analysieren, und glpk, um es zu lösen. Da sie keine quadratische Programmierung unterstützen, müsste ich dies in eine MILP konvertieren.

. Die erste Variable ist real, im Bereich [0, 1], die zweite ist real, vom Bereich 0 bis inf. Dieser könnte problemlos ein Integer sein.

Der kritische Teil in der Zielfunktion sieht wie folgt aus:

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

Ich hatte ähnliche Probleme in den Zwängen, aber sie waren leicht lösbar.

Wie könnte ich diese Art von Problem in der Zielfunktion lösen?

Answer 1

Modelle in dieser Form werden als bilineare Optimierungsprobleme bezeichnet. Der typische Ansatz zur Linearisierung bilinearer Terme ist durch etwas, das McCormick-Hüllkurve genannt wird.

Betrachten Variablen x und y, wo Sie wollen x*y in das Ziel Ihrer Maximierung Problem. Wenn wir x und y annehmen, sind begrenzt durch xL <= x <= xU und yL <= y <= yU, dann können wir x*y mit w ersetzen, eine Obergrenze für die Menge, mit folgenden Einschränkungen (Sie können die Ableitung sehen here):

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

Beachten Sie, dass Diese Einschränkungen sind in den Entscheidungsvariablen alle linear. Es gibt entsprechende untere Grenzen in der McCormick-Hülle, aber da Sie maximieren, sind sie in Ihrem Fall unwichtig.

Wenn Sie eine engere Grenze für x*y möchten, können Sie das Intervall für eine der Variablen (hier verwende ich x) in Bereiche [xL1, xU1], [xL2, xU2], ... aufteilen. [xLn, xUn], Einführung der kontinuierlichen Hilfsvariablen {x1, x2, ..., xn} und {w1, w2, ..., wn} sowie der Hilfs-Binärvariablen {z1, z2, ..., zn} , die anzeigt, welcher Bereich von x-Werten ausgewählt wurde. Die Einschränkungen oben ersetzt werden könnte (ich den Index 1 Fall zeigen werde, aber Sie würden diese für alle n-Indizes müssen):

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

Grundsätzlich werden Sie x1 = 0 und w1 < = 0, wenn z1 haben = 0 (auch dieser Teil des Bereichs ist nicht ausgewählt), und Sie haben die normale McCormick-Hüllkurve, wenn z1 = 1 (auch dieser Teil des Bereichs ausgewählt ist).

Der letzte Schritt besteht darin, x und w out of range-spezifische Versionen dieser Variablen zu generieren. Dies kann gemacht werden:

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

Je größer Sie n machen, desto genauer die Einschätzung werden Sie für den bilinearen Begriff haben. Jedoch beeinflussen große Werte von n die Lenkbarkeit Ihres Modells.

Eine letzte Anmerkung - Sie geben an, dass eine Ihrer Variablen unbegrenzt ist, aber die McCormick-Hüllkurve Grenzen für beide Variablen benötigt. Sie sollten Grenzen festlegen, lösen, und wenn Ihr optimaler Wert an der Grenze ist, sollten Sie mit einer anderen Grenze erneut lösen.