Un potente algoritmo per risolvere problemi di ottimizzazione discreta
Branch and bound è l’algoritmo principale dietro molti solutori di programmazione intera mista (MIP). Si tratta di un’ottima aggiunta al tuo kit di strumenti di ottimizzazione matematica, particolarmente utile per problemi più piccoli o quando il problema presenta numerosi vincoli. Inoltre, la sua natura semplice lo rende accessibile, senza bisogno di formule matematiche complesse.
In questo articolo pratico, approfondiremo un problema di ottimizzazione matematica. Lo affronteremo con l’algoritmo branch and bound, un’ottima tecnica per risolvere tali problemi. La nostra attenzione si concentrerà su un problema a tema felino: perché ammettiamolo, chi non ama i gatti? Tuttavia, se preferisci i cani, sentiti libero di sostituire mentalmente “cane” ogni volta che incontri “gatto” nella nostra discussione. I principi e i metodi si applicano esattamente allo stesso modo!
Immagina di essere il proprietario di un rifugio per gatti. Ogni giorno i proprietari di animali domestici possono portare i loro gatti e tu ti prendi cura di loro. Molte persone hanno adottato un gatto durante il COVID, ma ora tutti devono tornare in ufficio. Per questo motivo la tua azienda sta andando alla grande.
In realtà, un po’ troppo. Hai difficoltà a sistemare tutti i gatti nelle stanze del tuo edificio. A volte è necessario rifiutare delle persone perché ci sono troppe richieste. Ecco perché hai deciso di creare un algoritmo di ottimizzazione per aiutarti a trovare il minor numero di stanze possibile per tutte le registrazioni dei gatti.
Diamo un’occhiata a un esempio. Immagina che 3 gatti abbiano chiesto di soggiornare nel tuo rifugio. I loro nomi sono Lily, Charlie e Meowster. Come possiamo dividere questi tre gatti in stanze diverse? Abbiamo bisogno di tre stanze al massimo, ed ecco tutte le possibili soluzioni per raggruppare i gatti:
Partizioni e numero di campanello
Come puoi vedere, ci sono 5 modi possibili per raggruppare i 3 gatti. In matematica, il nome di un modo di raggruppare gli elementi di un insieme è a partizione. IL Numero di campanello corrisponde al numero totale di…
Fonte: towardsdatascience.com
