Come convertire il programma da quadratico a lineare?

Question

Ho un problema di ottimizzazione che ha nella funzione obiettivo 2 variabili moltiplicate, rendendo il modello quadratico.

Attualmente sto usando zimpl, per analizzare il modello e glpk per risolverlo. Dato che non supportano la programmazione quadratica, avrei bisogno di convertirlo in un MILP.

. La prima variabile è reale, nell'intervallo [0, 1], la seconda è reale, nell'intervallo da 0 a inf. Questo potrebbe senza problemi essere integer.

La parte critica nella funzione obiettivo appare così:

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

ho avuto problemi simili in vincoli, ma erano facilmente risolvibili.

Come potrei risolvere questo tipo di problema nella funzione obiettivo?

Answer 1

I modelli in questo formato sono in realtà chiamati problemi di ottimizzazione bilineare. L'approccio tipico alla linearizzazione dei termini bilineari è attraverso qualcosa chiamato busta di McCormick.

Considerare le variabili x e y, dove si desidera x*y nell'obiettivo del problema di massimizzazione. Se assumiamo x ed y sono delimitate da xL <= x <= xU e yL <= y <= yU, allora possiamo sostituire x*y con w, un limite superiore per la quantità, con i seguenti vincoli (si può vedere la derivazione here):

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

Si noti che questi vincoli sono tutti lineari nelle variabili decisionali. Ci sono limiti inferiori corrispondenti nella busta di McCormick, ma dal momento che stai massimizzando non sono importanti nel tuo caso.

Se si desidera un limite più stretto su x*y, è possibile dividere l'intervallo su una delle variabili (io userò x qui) in intervalli [xL1, xU1], [xL2, xU2], ..., [xLn, xUn], che introduce le variabili continue ausiliarie {x1, x2, ..., xn} e {w1, w2, ..., wn} così come le variabili binarie ausiliarie {z1, z2, ..., zn} , che indicherà quale intervallo di valori x è stato selezionato. I vincoli di cui sopra potrebbe essere sostituito da (Ti faccio vedere il caso indice 1, ma si avrebbe bisogno di questi per tutti gli indici n):

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

Fondamentalmente si avrà x1 = 0 e W1 < = 0 ogni volta Z1 = 0 (ovvero questa parte dell'intervallo non è selezionata) e avrai la normale busta di McCormick se z1 = 1 (alias questa parte dell'intervallo è selezionata).

L'ultimo passo è generare xe w di versioni specifiche di intervallo di queste variabili. Questo può essere fatto con:

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

Il più grande si fanno n, la più accurata di una stima si avrà per il termine bilineare. Tuttavia, valori elevati di n influenzeranno la capacità di risoluzione del modello.

Una nota finale: si indica che una delle variabili è illimitata, ma l'inviluppo di McCormick richiede limiti su entrambe le variabili. Dovresti correggere i limiti, risolvere, e se il tuo valore ottimale è al limite, dovresti risolvere nuovamente con un limite diverso.