Ambiente di programmazione intera
Risolvi un piccolo programma lineare intero con branch and bound esatto e visualizza ogni nodo della ricerca. Il punto migliore è dichiarato ottimo solo dopo aver esplorato l’intero albero.
I programmi sono limitati a 4.000 caratteri e 40 righe, 8 variabili e 8 vincoli con almeno due variabili; il limite dei nodi va da 1 a 5.000 e la ricerca si interrompe dopo 3.000.000 di passaggi di aritmetica esatta. Tutto viene calcolato sul dispositivo in background, con un limite di 15 secondi. Download: un rapporto JSON e un CSV dei nodi. Prima riga: maximize o minimize e l’obiettivo. Poi inserisci un vincolo per riga. Fino a 4.000 caratteri. Controlla le impostazioni prima di eseguire.
Il tuo risultato
Ambiente di programmazione intera
- Scrivi l’obiettivo sulla prima riga, come maximize 5x + 4y.
- Inserisci un vincolo per riga, limiti come x, y >= 0 e righe facoltative come integer x oppure binary z.
- Imposta il limite dei nodi e avvia la ricerca.
- Leggi lo stato, l’incumbent, il miglior limite e lo scarto, poi scarica il rapporto JSON o il CSV dei nodi.
Cosa aspettarsi
I programmi sono limitati a 4.000 caratteri e 40 righe, 8 variabili e 8 vincoli con almeno due variabili; il limite dei nodi va da 1 a 5.000 e la ricerca si interrompe dopo 3.000.000 di passaggi di aritmetica esatta. Tutto viene calcolato sul dispositivo in background, con un limite di 15 secondi. Download: un rapporto JSON e un CSV dei nodi.
Branch and bound
Ogni nodo risolve esattamente il rilassamento lineare con il metodo del simplesso. Una variabile intera frazionaria viene suddivisa in due rami, x <= floor e x >= ceiling. I nodi vengono potati se il rilassamento è inammissibile o non può migliorare il miglior punto intero trovato. Metodo: Wolsey, Integer Programming, 2ª edizione, capitolo 7 (2020).
Cosa significa “dimostrato”
Quando ogni nodo è stato risolto o potato con un limite esatto, l’incumbent è dimostrato ottimo oppure il problema è dimostrato inammissibile. Se il limite dei nodi o dei passaggi interrompe prima la ricerca, l’incumbent è solo il miglior punto trovato finora e il rapporto mostra il miglior limite e il divario.
Regole di input
Le variabili sono intere, a meno che alcune non siano dichiarate intere con integer x, y, nel qual caso le altre sono continue. I vincoli con una sola variabile diventano limiti. Un rilassamento illimitato interrompe la ricerca, perché il programma intero potrebbe essere illimitato o inammissibile.