Branch & Bound e Branch & Cut per problemi di Programmazione Lineare Intera.

Introduzione La Ricerca Operativa e una disciplina presente nel panorama scientico mon- diale da un periodo di tempo relativamente breve. Il suo scopo e quello di risolvere problemi di ottimizzazione, i quali consistono nel prendere decisioni circa l’utilizzo di risorse disponobili in quantit a limitate, in modo da perse- guire, nella miglior maniera possibile, il ne pressato. Per far ci o, si ricorre alla formulazione matematica di tali problemi e la successiva ideazione di metodi e algoritmi in grado di risolverli. I primi passi in tale disciplina vennero compiuti per scopi puramente milita- ri durante la Seconda Guerra Mondiale: il Regno Unito stava lavorando ad un progetto sui radar come difesa antiaerea, ma era tuttavia importante che fosse eciente la localizzazione, la successiva intercettazione e rientro a terra dei velivoli; un aspetto indispensabile era quindi rappresentato dalla ricerca dell’ottimale distribuzione delle apparecchiature radar sul territorio. Dopo la conclusione del conitto, le tecniche sviluppate vennero riconverti- te per essere applicate in campo economico e industriale; nacquero dunque gruppi di ricerca che formalizzarono tale disciplina, arricchendola di oppor- tuni strumenti matematici. Oggi come allora, la Ricerca Operativa e una disciplina scientica in continua evoluzione e, grazie alla sua duttilit a, sono molteplici le questioni che trovano una soluzione per mezzo dell’applicazione dei suoi strumenti; tra queste, in tale elaborato ci si limiter a ad illustrarne alcune relative a problemi di otti- mizzazione esprimibili come problemi di Programmazione Lineare Intera, e che possono essere risolte utilizzando i metodi Branch & Bound e Branch & Cut. Questi ultimi, entrambi appartenenti alla famiglia degli algoritmi di bran- ching, vengono ampiamente descritti nel seguito, in primo luogo illustrando gli elementi preliminari della Programmazione Lineare Intera, e successiva- mente, per ciascuno dei due metodi, gli strumenti necessari per la compren- sione degli stessi. Inoltre, sia per il Branch & Bound che per il Branch & Cut, e fornita una schematizzazione del relativo algoritmo di risoluzione, e l’analisi di partico- 3