LP avanzata per la risoluzione

Nonostante la maturità della tecnologia LP, alcuni casi d'uso richiedono tecniche più avanzate. Ad esempio, sono disponibili una serie di implementazioni e algoritmi di LP diversi, ognuno dei quali presenta punti di forza e punti deboli. Inoltre, l'instabilità numerica può causare il rallentamento o il mancato superamento di alcuni modelli da parte dei risolutori.

Questa guida introduce i concetti e fornisce esempi per aiutarti a ottenere le massime prestazioni e affidabilità dai risolutori LP.

Concetti

Questa sezione illustra i concetti chiave per l'utilizzo avanzato dei risolutori LP. Partiamo dal presupposto che i lettori conoscano il concetto di dualità in LP.

Famiglie di algoritmi LP

Le seguenti classi di algoritmi per LP sono accessibili tramite OR-Tools.

  1. L'algoritmo Simplex è stato il primo algoritmo LP pratico e rimane il più popolare. L'algoritmo cammina lungo i vertici (punti angolari) della regione fattibile, migliorando iterativamente il valore della funzione obiettivo fino a raggiungere una soluzione ottimale. Esistono due tipi di algoritmi simplex:

    1. Primal simplex intraprende passaggi lungo i vertici della prima regione possibile. Questa variante è particolarmente efficace nel risolvere una sequenza di problemi LP con diverse funzioni oggettive, ovvero dove viene fissata la regione principale fattibile.
    2. Dual simplex cammina lungo i vertici di una regione doppia. Questa variante è particolarmente efficace nel risolvere una sequenza di problemi relativi alla fase di destinazione in cui è fissata la doppia regione fattibile, ad esempio quando cambiano solo i limiti delle variabili. Per questo motivo, dual simplex è ampiamente utilizzato nei risolutori MIP.

  2. I metodi barriera o punto interno sono stati la seconda famiglia pratica di algoritmi per la LP. I metodi a barriera associano le garanzie teoriche di convergenza efficiente (tempo polinomiale) a prestazioni affidabili nella pratica. Complementano l'algoritmo simplex quando le sue prestazioni sono scarse. Ad esempio, alcuni risolutori offrono di eseguire in parallelo sia il Simplex che la barriera, restituendo la soluzione dall'algoritmo che termina per primo.

  3. I metodi del primo ordine sono una famiglia di algoritmi che utilizzano esclusivamente informazioni sul gradiente (ovvero le derivate del primo ordine) per guidare le iterazioni. La discesa del gradiente è un esempio ben noto. Questi metodi sono molto diffusi nell'ottimizzazione non lineare e nel machine learning. Per LP, i metodi del primo ordine possono scalare a problemi più grandi rispetto a simplex e barriera e possono anche avere requisiti di memoria molto più ridotti. D'altro canto, sono più sensibili ai problemi numerici e potrebbero faticare a ottenere soluzioni estremamente accurate.

La tabella seguente elenca i risolutori LP disponibili in OR-Tools e indica quale delle tre famiglie di algoritmi è implementata in ciascun risolutore.

Risolutore Simplex Barriera di sicurezza Primo ordine
Battito X X
CPLEXL X X
GlopG X
GLP X X
GurobiL X X
PDLPG X
XpressL X X

G indica che il risolutore è sviluppato da Google. L indica che il risolutore richiede una licenza rilasciata dal rispettivo sviluppatore di terze parti.

Consulta i consigli per suggerimenti su quali risolutori e algoritmi utilizzare.

Cosa significa davvero risolvere?

Per ottenere il massimo dai risolutori LP è importante capire cosa implica quando un risolutore afferma di aver trovato una soluzione a un problema di LP. Questa sezione illustra le nozioni di base necessarie per rispondere a questa domanda, in particolare a causa dell'imprecisione numerica e della non univocità delle soluzioni.

Tolleranze

I risolutori LP utilizzano quasi sempre l'aritmetica in virgola mobile, il che rende le loro soluzioni soggette a imprecisioni numerica. Per tenere conto di ciò e per migliorare il rendimento evitando di passare a soluzioni già abbastanza valide, i risoltori accettano le soluzioni (e dichiarano di aver risolto un problema) quando soddisfano le condizioni entro determinate tolleranze.

Considera il problema della programmazione lineare

$$ \begin{align*} \min\quad & -2x_1 - x_2 \\ \text{s.t.}\quad& x_1 + x_2 \le 1\\ & x_1, x_2 \ge 0 \end{align*} $$

e il corrispondente duplice problema

$$ \begin{align*} \max\quad& y \\ \text{s.t.}\quad& -2 - y \ge 0\\ &-1 - y \ge 0 \\ &y \le 0 \end{align*} $$

Questa coppia di problemi ha una soluzione primale ottimale unica $ x_1 = 1, x_2 = 0 $ e una doppia soluzione $ y = -2 $. Quali soluzioni potrebbe essere accettata come ottimale da un risolutore? Per rispondere a questa domanda, definiamo le seguenti quantità:

  • Il divario di dualità è la differenza tra il valore dell'obiettivo principale e il valore del duplice obiettivo, in questo caso $ |(-2x_1 - x_2) - y| $.
  • Le infattibilità principali sono le violazioni dei vincoli principali, in questo caso $ (\max\{ (x_1+x_2) - 1, 0 \}, \max\{-x_1, 0\}, \max\{-x_2, 0\}) $.
  • Le doppie infattibilità sono le violazioni dei due vincoli, in questo caso $ (\max\{ 2 + y, 0 \}, \max\{ 1 + y, 0 \}, \max\{ y, 0 \}) $.

Un risolutore dichiara una soluzione ottimale se il divario di dualità, l'inattuabilità primale e l'inapplicabilità doppia sono inferiori a una determinata tolleranza.1

In particolare, l'applicazione delle tolleranze varia per motivi sia naturali che idiosincratici nei vari risolutori e algoritmi. Ad esempio, il divario di dualità nell'algoritmo simplex è determinato solo dall'imprecisione numerica, mentre l'inattuabilità principale e doppia sono presenti anche nell'aritmetica esatta. Per alcuni metodi con $coordinasi associati $ x_1 \ge 0, x_2 \ge 0, $ e $ y \le 0 $, altri metodi considerano le violazioni dei vincoli associati in modo diverso rispetto alle violazioni dei vincoli lineari come $x_1 + x_2 \le 1$. Per alcuni risolutori, le tolleranze sono assolute.

Per un esempio dell'effetto delle tolleranze, considera una tolleranza assoluta di $ \epsilon = \frac{1}{2} $ applicata alla coppia primo-doppia sopra riportata. La soluzione $ x_1 = 1,5, x_2 = 0, y = -3 $ ha un divario di dualità pari a zero e delle infattibilità tutte inferiori o uguali a $ \epsilon $, per cui un risolutore potrebbe dichiarare questa soluzione "ottimale". Tuttavia, il suo valore obiettivo (-3) differisce di 1 dal vero valore obiettivo ottimale di -2. I valori predefiniti tipici di $ \epsilon $ sono compresi tra $10^{-6}$ e $10^{-8}$, il che rende gli esempi estremi rari ma non impossibili.

Tipi di soluzioni

I problemi di LP possono avere più di una soluzione ottimale, ancora di più se si tiene conto delle tolleranze. Parliamo brevemente delle proprietà delle soluzioni restituite dalle tre diverse famiglie di algoritmi di LP presentate sopra.

Gli algoritmi semplici restituiscono sempre vertici o punti d'angolo dell'area geografica disponibile. Queste soluzioni sono preferite in alcune situazioni perché tendono a essere più scarse.

I metodi di barriera e del primo ordine non restituiscono in genere i vertici. (La teoria fornisce caratterizzazioni aggiuntive che non rientrano nell'ambito di questa guida.)

Per motivi storici e poiché le soluzioni di vertice hanno proprietà interessanti, spesso i risolutori, per impostazione predefinita, applicano una procedura di crossover per passare a un vertice ottimale da una soluzione trovata da un algoritmo di barriera. Il crossover non è attualmente offerto per le soluzioni trovate con i metodi del primo ordine.

Suggerimenti

Forniamo le seguenti raccomandazioni per l'uso avanzato dei risolutori LP.

Scalabilità dei dati dei problemi

I risolutori possono riscontrare una lenta convergenza o errori nei modelli a causa di problemi numerici. Questi problemi possono presentarsi per diversi motivi; di seguito ne riportiamo un esempio.

È comune che costanti numeriche molto piccole o grandi vengano visualizzate nei modelli LP. Estendendo l'esempio precedente, se \(x_1\) e \(x_2\) rappresentano la frazione di clienti assegnata a "fornitore 1" o "fornitore 2" e se vogliamo massimizzare i vantaggi derivanti dal fornire questi clienti, potremmo scrivere la seguente funzione obiettivo:

$$ \min -c_1x_1 - c_2x_2 $$

dove:

  • $ c_1 $ è il vantaggio derivante dall'assegnazione di clienti al fornitore 1
  • $ c_2 $ è il vantaggio derivante dall'assegnazione di clienti al fornitore 2

I doppi che soddisfano i seguenti vincoli verrebbero considerati fattibili con una tolleranza assoluta $ \epsilon $:

  • $ y \le -c_1 + \epsilon $,
  • $ y \le -c_2 + \epsilon $.

Se le unità del vantaggio di $ c_1 $ e $ c_2 $ sono piccoli valori frazionari che potrebbero essere sulla stessa scala di $ \epsilon $, allora le condizioni di duplice fattibilità diventano piuttosto inefficaci, quindi un valore primale molto non ottimale può essere dichiarato ottimale.

Se, d'altra parte, le unità di benefit sono "microDollari" (1 000 000 microDollari = 1 dollaro), i risultanti valori assoluti molto grandi richiedono una precisione molto elevata nella soluzione, forse irragionevolmente elevata dati i limiti dei numeri in virgola mobile. I risolutori potrebbero non convergere se il problema è formulato in questo modo. Al fine di formulare un problema ben posto, i creatori di modelli avanzati devono valutare se i dati del problema vengono scalati in modo coerente con le tolleranze del risolutore.

Oltre a evitare errori numerici, le tolleranze possono anche essere ottimizzate per migliorare le prestazioni. I metodi semplici e barriera non sono troppo sensibili alle tolleranze, ma a volte possono trarre vantaggio da tolleranze più ampie se si osserva che il progresso si blocca alla fine della risoluzione. D'altra parte, i metodi del primo ordine sono in genere molto più sensibili. Gli utenti che usano i metodi del primo ordine possono trarre vantaggio da soluzioni più rapide, allentando le tolleranze, a seconda del contesto.

Per le tolleranze di Glop, vedi primal_feasibility_tolerance, dual_feasibility_tolerance e solution_feasibility_tolerance in GlopParameters. Tieni presente che primal_feasibility_tolerance e dual_feasibility_tolerance sono utilizzati all'interno dell'algoritmo, mentre solution_feasibility_tolerance viene controllato dopo la risoluzione per segnalare problemi numerici. Per PDLP, consulta eps_optimal_absolute e eps_optimal_relative.

Per ulteriori informazioni su questi tipi di problemi, consulta le linee guida per le questioni numeriche di Gurobi. Sebbene le linee guida siano scritte per gli utenti di Gurobi, molti principi si applicano in generale.

Scelta di risolutori e algoritmi

Partiamo con un esempio di quanto può essere elevato l'impatto della scelta di risolutori e algoritmi, quindi presentiamo una guida per la scelta dei risolutori LP.

Variabilità pratica

Mostriamo la variabilità delle prestazioni negli algoritmi e nei risolutori LP confrontando i tempi di risoluzione su una selezione di istanze che sono state utilizzate da Hans Mittelmann per il benchmarking dei risolutori LP. Le istanze vengono scelte esplicitamente per mostrare i valori estremi delle prestazioni relative e non sono necessariamente rappresentativi del comportamento tipico.

I metodi primali e dual simplex di Glop vengono confrontati con il metodo della barriera di Gurobi (con e senza crossover, che trova una soluzione di vertice) e con PDLP, un metodo di primo ordine, con precisione elevata e bassa. I report della tabella riportata di seguito risolvono tempi in secondi, con un limite di 20 minuti (1200 secondi).

Istanza Glop
Primal Simplex		 Glop
doppio Simplex		 Barriera di Gurobi
con crossover		 Barriera Gurobi
senza Crossover		 Alta precisione
PDLP		 PDLP
- Bassa precisione
ex10 >1200 >1200 79.7 63.5 8.2 2.7
nug08-3° >1200 252.8 144,6 3.2 1.1 0,9
savsched1 >1200 >1200 156.0 22,6 46.4 32.4
wide15 >1200 20,8 >1200 >1200 916,4 56.3
energia edilizia 178.4 267.5 12,8 12.3 >1200 157.2
S250r10 12.1 520.6 15.2 16.4 >1200 >1200
Versione del risolutore OR-Strumenti 9.3 OR-Strumenti 9.3 Gurobi 9.0 Gurobi 9.0 OR-Strumenti 9.3 OR-Strumenti 9.3
solver_specific_parameters (valore predefinito) use_dual_simplex: true Method 2, Threads 1 Method 2, Crossover 0, Threads 1 termination_criteria { eps_optimal_absolute: 1e-8 eps_optimal_relative: 1e-8 } termination_criteria { eps_optimal_absolute: 1e-4 eps_optimal_relative: 1e-4 }

Da questi risultati concludiamo quanto segue.

  • Le prestazioni relative degli algoritmi e dei risolutori possono variare per ordini di grandezza su una singola istanza.
  • Nessun singolo algoritmo e risolutore è uniformemente migliore di altri.
  • Il crossover (attivato per impostazione predefinita) aumenta il tempo di risoluzione, a volte notevolmente.
  • La risoluzione PDLP può risolvere i problemi con una precisione bassa, a volte 10 volte più veloce rispetto a una precisione elevata.

Una breve guida alla scelta dei risolutori LP

Dato che nessun algoritmo o risolutore LP è i migliori, ti consigliamo di seguire i passaggi seguenti per scoprire cosa è meglio per il tuo caso d'uso. Inizia dal primo passaggio e procedi con quello successivo se le prestazioni non sono sufficienti.

  1. Prova Glop. Perché: Glop è l'implementazione interna di Google dei metodi semplici primali e dual simplex. Glop è open source e affidabile per i carichi di lavoro di produzione di Google.
    • Se la configurazione predefinita (base semplice principale) non funziona bene, prova a passare alla modalità dual simplex utilizzando use_dual_simplex: true.
  2. Se è disponibile una licenza, prova un risolutore commerciale (CPLEX, Gurobi o Xpress). Sperimenta con i metodi simplex e di barriera. Perché: si tratta di risolutori standard di settore altamente ottimizzati. Inoltre, i metodi di barriera completano gli algoritmi simplex offerti da Glop.
    • Se utilizzi la barriera, disabilita "crossover" se non ti serve una soluzione di vertice.
  3. Prova PDLP. Adatta le tolleranze di convergenza alla tua applicazione. Perché: la funzionalità PDLP è progettata per i problemi più grandi, in cui i metodi simplex e di barriera superano i limiti della memoria o sono troppo lenti. PDLP funziona meglio quando è preferibile una soluzione approssimativa, ma veloce, rispetto a una soluzione lenta.
  4. Se hai raggiunto questo obiettivo, ora sei un utente LP avanzato. Per ulteriore assistenza, vedi le opzioni di assistenza OR-Tools.

  1. Spesso è più complesso. I risolutori solitamente controllano queste condizioni su una versione trasformata/semplificata del problema, chiamata problema presolved. In alcuni casi, una soluzione al problema prerisolto potrebbe essere lontana da una soluzione al problema di input. Questa situazione può portare a stati insoliti come CPLEX OptimalInfeas o Glop IMPRECISE.↩