Jak przekonwertować program kwadratowy na liniowy?

Question

Mam problem z optymalizacją, który w zmiennej celu celu 2 zwielokrotnia zmienne, co powoduje, że model jest kwadratowy.

Obecnie używam Zimpl, do parsowania modelu i glpk, aby go rozwiązać. Ponieważ nie obsługują programowania kwadratowego, musiałbym przekonwertować to na MILP.

. Pierwsza zmienna jest prawdziwa, w zakresie [0, 1], druga jest prawdziwa, od zakresu od 0 do inf. Ten może bez problemu być liczbą całkowitą.

Krytycznym elementem w obiektywnej funkcji wygląda następująco:

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

miałem podobne problemy z ograniczeniami, ale były one łatwo rozwiązywalne.

Jak mogę rozwiązać ten problem w funkcji celu?

Answer 1

Modele w tej formie są w rzeczywistości zwane problemami optymalizacji bilinearnej. Typowe podejście do linearyzacji dwuliniowych określeń to coś, co nazywa się kopertą McCormicka.

Rozważ zmienne x i y, gdzie chcesz x*y w celu Twojego problemu z maksymalizacją. Jeśli założymy, X i Y są rozgraniczone xL <= x <= xU i yL <= y <= yU, to możemy wymienić x*y z w, górna granica dla ilości, z następującymi ograniczeniami (widać wyprowadzenie here):

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

Należy pamiętać, że wszystkie te ograniczenia są liniowe w zmiennych decyzyjnych. W kopercie McCormicka znajdują się odpowiednie dolne krawędzie, ale ponieważ maksymalizujesz, nie są one ważne w twoim przypadku.

Jeśli chcesz mocniej ograniczyć x*y, możesz podzielić przedział na jedną ze zmiennych (użyję x tutaj) na zakresy [xL1, xU1], [xL2, xU2], ..., [xLn, xUn], wprowadzając pomocnicze ciągłe zmienne {x1, x2, ..., xn} i {w1, w2, ..., wn} oraz pomocnicze zmienne binarne {z1, z2, ..., zn} , który wskaże, który zakres wartości x został wybrany. Ograniczenia powyżej mogą być zastąpione przez (pokażę sprawę indeks 1, ale trzeba je dla wszystkich indeksów n):

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

Zasadniczo trzeba będzie x1 = 0 i w1 < = 0 gdy z1 = 0 (aka tej części zakresu nie jest wybrana), a będziesz miał normalną obwiednię McCormick, jeśli z1 = 1 (jest to aka ta część zakresu).

Ostatnim krokiem jest wygenerowanie X i W poza wersjami tych zmiennych dla poszczególnych zakresów. Można to zrobić z:

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

Im większa dokonać n, tym dokładniejsze od oszacowania trzeba będzie na okres dwuliniowa. Jednak duże wartości n będą miały wpływ na podatność rozwiązania twojego modelu.

Ostatnia uwaga - wskazuje się, że jedna z zmiennych jest nieograniczona, ale obwiednia McCormick wymaga obwiedni dla obu zmiennych. Powinieneś ustalić granice, rozwiązać i jeśli twoja optymalna wartość znajduje się na granicy, powinieneś ponownie rozwiązać z inną granicą.