Come implementare filiale e prezzo?
Ho sentito una volta che l'algoritmo di branch and price (B&P) è tra i più difficili in OR, ma se è implementato bene, potrebbe essere molto efficiente. Esistono altri algoritmi altrettanto complicati?
Voglio implementare B&P su un problema. Allora come scelgo un problema non troppo complesso? Sentiti libero di suggerire più di un problema se pensi che abbia un impatto sul modo in cui l'algoritmo è implementato, cioè se imparerò principi diversi da problemi diversi.
Ho anche bisogno di una guida. Come iniziare? Quali sono le insidie da evitare? Sarebbe apprezzata anche qualsiasi risorsa che abbia un codice open source ben documentato. Voglio scegliere Python o C ++.
Risposte
Prima di iniziare l'implementazione, mi assicurerei di essere a mio agio con tutti gli aspetti teorici, che sono anch'essi un po 'complicati. Questo è un argomento abbastanza avanzato in sala operatoria e richiede una certa esperienza. Ti senti a tuo agio con il branch-and-bound, con l'algoritmo simplex, con la decomposizione di Dantzig-Wolfe, la generazione di colonne, ecc.?
Stai esitando tra Python e C ++. C'è una ragione per questo? Python è molto più semplice, ma C ++ sarà più veloce. Quindi è per il mondo accademico o per l'industria?
È anche possibile cassa dippy , che è un'estensione di polpa (quindi il suo Python) che permette agli utenti di specificare decomposizioni e personalizzare la ramificazione, generazione taglio, e la generazione di colonna DIP , all'interno di un modello polpa. Tutto è open source.
Usare un framework come SCIP può essere una buona idea per iniziare. In questo modo, puoi implementare rapidamente la tua formulazione. Ha interfacce sia su C ++ che su Python. La documentazione contiene esempi di branch-and-price, ti consiglio di dare un'occhiata a loro. Per qualsiasi problema a portata di mano, puoi utilizzare il metodo di decomposizione di Dantzig-Wolfe per generare uno schema di filiale e prezzo.
Nah. Costruire un'interfaccia ASL è difficile , BnP va bene. Supponendo che tu abbia familiarità con i suoi elementi costitutivi (proprio come con qualsiasi altro algoritmo), la sfida sta nei dettagli di implementazione.
Ci sono alcune cose da tenere presenti per BnB in generale e per BnP in particolare:
BnB
- Euristica dell'accelerazione: gli algoritmi BnB funzionano bene solo se combinati con determinate euristiche dell'accelerazione come la riduzione del dominio (ad es. Propagazione dei vincoli) o buone strategie di ramificazione (ad es. Pseudocosti).
- Per problemi di grandi dimensioni sono necessarie strutture di dati buone e scalabili per evitare che l'algoritmo si riduca a una scansione, soprattutto se i problemi sono abbastanza grandi da richiedere la generazione di colonne.
- Pure Python sarà 1.000-10.000 volte più lento di C ++ per qualsiasi problema di dimensioni decenti. Il modo corretto per farlo è codificare le librerie C ++ per i calcoli ad alte prestazioni e importarle come oggetti Python utilizzando API Python-> C ++ come boost Python. Questo può farti diventare 100 volte più lento di C ++.
- Per i due motivi sopra, Python ha i suoi limiti a causa della larghezza di banda limitata nel trasferimento dei dati tra le diverse parti del codice. In particolare, molte API Python-> C ++ innescano inevitabilmente i costruttori di copie C ++ che possono essere un grosso problema se le strutture dei dati sono grandi. Anche la memoria può diventare un problema.
- Dato che siamo in argomento, anche se sai davvero cosa stai facendo in C ++, il meglio che puoi fare con il codice ibrido è 100 volte più lento del C ++. Tuttavia, se sei a quel livello di sapere cosa stai facendo, potresti anche fare l'intera cosa in C ++.
- MINOTAUR è il codice BnB open source C ++ più ben scritto che abbia visto finora (anche se non molto ben documentato fino a pochi anni fa).
- Una cosa che la maggior parte delle persone trascura all'inizio è che hai bisogno di un modo per ottenere la matematica nel tuo codice. Pensa a come lo farai fin dall'inizio poiché influenzerà molte delle tue decisioni sull'architettura.
BnP
- Una considerazione importante per l'implementazione qui è che è necessario aggiungere colonne al rilassamento man mano che la procedura di soluzione procede. Questa può essere un'operazione molto costosa, specialmente con matrici di grandi dimensioni, quindi sarà necessario ricercare il modo più veloce supportato dal risolutore lineare per aggiungere nuove colonne. Ricostruire la matrice è ovviamente il modo più semplice ed è effettivamente ok per molti algoritmi, ma è un no-no per la generazione di colonne.
Dalla tua descrizione sembra che il tuo obiettivo sia imparare cose nuove, quindi Python o C ++ vanno bene per quello scopo. Se vuoi usare il tuo codice per qualcosa di "reale", usare il C ++ in una certa misura sarà inevitabile, quindi sta a te decidere cosa vuoi imparare dal punto di vista della programmazione. Tieni presente però che la migrazione del codice ibrido in C ++ può essere piuttosto dolorosa, quindi se vedi che devi andare con C ++ è meglio farlo all'inizio dello sviluppo.
In ogni caso, preparati mentalmente per un grande investimento di tempo e divertiti!
Se vuoi guardare il codice sorgente C ++, ci sono alcuni progetti COIN-OR che forniscono framework per "branch price and cut" o "branch cut and price" come a volte è noto. Due che mi vengono in mente sono BCP e Symphony .
Una delle idee principali alla base del nostro risolutore di decomposizione GCG (gcg.or.rwth-aachen.de/dev) è di farti risparmiare il tempo di sperimentare con il tuo codice B&P solo per scoprire che B&P non è l'approccio giusto al tuo problema. Un'altra idea principale del nostro risolutore è che una volta scoperto che B&P è un buon approccio, puoi semplicemente usare GCG per fare il lavoro per te. Provalo, si spera che ti farà risparmiare alcune ore. Scarica con SCIP su scipopt.org.