Branch and Bound – Introduzione Prima di Codificare l’Algoritmo Da Zero

Branch and Bound - Introduzione all'Algoritmo

Un’introduzione ai Problemi Interi e Uno dei Metodi per Risolverli

Introduzione

Foto di Possessed Photography su Unsplash

La programmazione intera (IP) è un caso particolare della programmazione lineare (LP) in cui le variabili decisionali sono limitate a valori interi. Cioè, valori come 2,5 o 4,2 non sono soluzioni possibili per questi problemi.

Questo requisito viene trattato come un vincolo aggiuntivo alla LP e, a sua volta, rende il processo di trovare l’ottimo più sfidante.

Nella vita reale, molti dei problemi che affrontiamo assumono la forma di IP. Ad esempio, l’assegnazione e l’allocazione del capitale, dove decidiamo quali investimenti fare richiedono che le variabili decisionali siano binarie e assumano solo i valori di 0 e 1. Anche i problemi di selezione del sito nell’immobiliare, i percorsi dei veicoli e persino i problemi di pianificazione probabilmente rientrano in questa categoria.

In questo articolo, esploreremo uno degli algoritmi utilizzati per risolvere problemi interi (IP), chiamato algoritmo Branch and Bound.

Prenderò spunto dagli esempi tratti dal libro “Metodi di Ottimizzazione in Finanza” di Cornuejols e Tütüncü, ma aggiungerò le mie spiegazioni intuitive e naturalmente, l’implementazione in Python di tali algoritmi.

Algoritmo Branch and Bound

L’algoritmo Branch and Bound è uno dei metodi più popolari per risolvere un IP. L’algoritmo suddivide il problema principale o originale in sottoproblemi più piccoli (branching) e, facendo ciò, è in grado di provare alcune di queste soluzioni ed eliminare successivamente alcuni di questi sottoinsiemi di soluzioni (bounding / potatura) quando questi non contribuiscono a un risultato migliore rispetto a quello che abbiamo attualmente/inizialmente.

È molto da comprendere, ma sarà più facile con un esempio.

Problema 0: Il problema intero originale

Problema 0 sopra è il nostro problema intero originale. Nota che è un semplice problema di programmazione lineare con un vincolo aggiuntivo nell’ultima riga.

Passo 1 – Rilassamento della Programmazione Lineare