Optimization Methods and Algorithms - Appunti completi (Programmazione Lineare, Grafi, Branch & Bound, Scheduling)

Corso di Laurea Magistrale in Informatica

Appunti di Optimizations methods and

algorithms

Anno Accademico 2025/2026

Studente: Emmanuel Messina

Politecnico Di Torino

Indice

1 Programmazione Lineare (PL) 4

1.1 Introduzione: L’Arte di Prendere la Decisione Ottimale . . . . . . . . . . . . . . . . 4

1.2 Che cos’è la programmazione lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Tecniche di Linearizzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.4 Generalizzazione delle Tecniche di Linearizzazione . . . . . . . . . . . . . . . . . . . 21

1.5 Linearizzazione di Espressioni Quadratiche per Variabili Binarie . . . . . . . . . . . . 28

1.5.1 Problema Multiperiodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.5.2 Problema della Campagna Pubblicitaria . . . . . . . . . . . . . . . . . . . . . 30

1.5.3 Problema dei Giornali e delle Escursioni . . . . . . . . . . . . . . . . . . . . . 33

1.6 La Prospettiva più Ampia nel Processo di Ottimizzazione . . . . . . . . . . . . . . . 35

2 Grafi 38

2.1 Introduzione ai Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.2 Problemi Classici sui Grafi: Percorsi che coprono spigoli o vertici . . . . . . . . . . . 40

2.3 Ricerca di un Percorso in un Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.4 Il Problema del Percorso Minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

2.5 Algoritmo di Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

2.6 Il Problema dell’Albero Ricoprente di Costo Minimo . . . . . . . . . . . . . . . . . . 52

2.7 Algoritmi di Kruskal e Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

2.8 Fattorizzazione di un Grafo Completo . . . . . . . . . . . . . . . . . . . . . . . . . . 55

2.9 Algoritmo Costruttivo (Metodo ”Necklace” o Poligono) . . . . . . . . . . . . . . . . 56

2.10 Il Problema del Flusso Massimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2.11 L’Algoritmo di Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

2.12 Il Problema della Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

3 Complessità 80

3.1 Introduzione alla complessità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.2 Esempi sulla complessità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

3.3 Teoria della NP-completezza e Classificazione dei Problemi . . . . . . . . . . . . . . 89

4 Project Management 95

4.1 Definizioni Fondamentali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

4.2 WBS, Pianificazione e Grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

4.3 Algoritmo di Kahn per l’Ordinamento Topologico . . . . . . . . . . . . . . . . . . . . 100

4.4 Diagramma di Gantt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

4.5 Activity on Arc (AoA) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.6 Latest Start Time (LST) e Float . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

4.7 Relazioni di Precedenza Generalizzate . . . . . . . . . . . . . . . . . . . . . . . . . . 105

4.8 Algoritmo per il Percorso Massimo in PM (con cicli) . . . . . . . . . . . . . . . . . . 108

4.9 Gestione dei Costi (Cost Management) . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.10 Resource Constrained Project Scheduling (RCPS) . . . . . . . . . . . . . . . . . . . . 112

4.11 Formulazione LP per l’RCPS: Il Modello di Kaplan . . . . . . . . . . . . . . . . . . . 114

1

5 Programmazione Dinamica 117

5.1 Introduzione alla Programmazione Dinamica . . . . . . . . . . . . . . . . . . . . . . 117

5.2 Il Problema del Cammino Minimo: Algoritmo di Bellman-Ford . . . . . . . . . . . . 117

5.3 Algoritmo per il Cammino Massimo nel Project Management . . . . . . . . . . . . . 120

5.4 Il Problema del Cammino Minimo: Algoritmo di Dijkstra . . . . . . . . . . . . . . . 120

5.5 Programmazione Dinamica vs Algoritmi Ricorsivi . . . . . . . . . . . . . . . . . . . . 121

5.6 Programmazione Dinamica per un Problema ILP 0/1 Speciale . . . . . . . . . . . . . 121

5.7 Il Problema dello Zaino 0/1 (Knapsack Problem) . . . . . . . . . . . . . . . . . . . . 122

6 Branch and Bound 127

6.1 Risoluzione dei Problemi di Ottimizzazione Combinatoria (COP) . . . . . . . . . . . 127

6.2 Il Metodo Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

6.3 I Passi del Metodo Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . 130

6.4 Regole di Esplorazione del Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

6.5 Regole di Decisione del Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

6.6 Esempio di Strategia di Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132

6.7 Efficacia del Bounding e Criteri di Potatura . . . . . . . . . . . . . . . . . . . . . . . 133

6.8 Elementi Essenziali del Branch and Bound: Sintesi . . . . . . . . . . . . . . . . . . . 134

6.9 Il Problema del Knapsack e il Metodo Branch and Bound . . . . . . . . . . . . . . . 134

6.10 Calcolo del Lower Bound per Problemi di Minimizzazione . . . . . . . . . . . . . . . 137

6.11 Confronto tra Rilassamento Lagrangiano e Rilassamento Surrogato . . . . . . . . . . 140

6.12 Branch and Bound per il Traveling Salesman Problem (TSP) . . . . . . . . . . . . . 142

6.13 Esercizi Branch and Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

6.14 Branch and Bound per il Problema della Massima Clique . . . . . . . . . . . . . . . 153

7 Metodi Euristici 156

7.1 Introduzione ai problemi di Ottimizzazione Combinatoria . . . . . . . . . . . . . . . 156

7.2 Classificazione delle Euristiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156

7.3 Algoritmi Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157

7.4 Il Problema del p-Median non capacitato . . . . . . . . . . . . . . . . . . . . . . . . 159

7.5 Beam Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

7.6 Ricerca Locale (Local Search) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

7.7 Estensioni del TSP e Nuovi Problemi Combinatori . . . . . . . . . . . . . . . . . . . 165

7.8 Strategie di Ricerca Locale Classica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

7.9 Limiti della Ricerca Locale e Introduzione alle Metauristiche . . . . . . . . . . . . . 169

7.10 Algoritmi Genetici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

7.11 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182

8 Ottimizzazione Multi-Obiettivo 198

8.1 Introduzione ai problemi reali e obiettivi conflittuali . . . . . . . . . . . . . . . . . . 198

8.2 Dominanza e Ottimo di Pareto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200

8.3 Il Principio di Pareto e Approcci Risolutivi . . . . . . . . . . . . . . . . . . . . . . . 201

8.4 Metodi A Priori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

8.5 Metodi A Posteriori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

8.6 Caso di Studio: Problema dello Zaino Bi-obiettivo . . . . . . . . . . . . . . . . . . . 204

2

Emmanuel Messina - Optimizations methods and algorithms 2025/2026

9 Sequencing and Scheduling 210

9.1 Definizioni e Notazioni di Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

9.2 Classificazione dei Problemi di Scheduling: La Notazione . . . . . . . . . . . . 213

α|β|γ

9.3 Misure di Performance e Schedulazioni Semi-Attive . . . . . . . . . . . . . . . . . . . 215

9.4 Algoritmi per Problemi a Macchina Singola: Minimizzazione della Lateness e Com-

pletion Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

9.4.1 Il Problema 1|prec|L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216

max

9.4.2 Minimizzazione del Weighted Completion Time (1|| ) . . . . . . . . . 218

P w C

j j

9.4.3 Il Problema 1||L e la Regola di Jackson . . . . . . . . . . . . . . . . . . . 220

max

9.4.4 Problema 1|r : Release Times . . . . . . . . . . . . . . . . . . . . . . . 220

|C

j max

9.4.5 Algoritmo di Moore per 1|| . . . . . . . . . . . . . . . . . . . . . . . . . 221

P U

j

9.4.6 Algoritmo di Johnson per 2||C . . . . . . . . . . . . . . . . . . . . . . . 221

F max

9.5 Complessità e Euristiche (Dispatching Rules) . . . . . . . . . . . . . . . . . . . . . . 222

Prima di iniziare a studiare da questi appunti è necessario che tu sappia che, nonostante

Premessa

si sia cercato di fare gli appunti nel miglior modo possibile sia per ripassare al meglio e sia per poter

creare un materiale utile per altri studenti, che ci potrebbero ugualmente essere imprecisioni, errori

di scrittura o altro. In caso di problemi si prega di contattarmi via mail: s333951@studenti.polito.it,

su instagram: oppure sul canale telegram: Se vuoi

@emmanuelmessina00 CLICCA QUI.

sostenere il lavoro svolto, puoi offrirmi un caffè (1 euro) qui: CLICCA QUI.

3

Emmanuel Messina - Optimizations methods and algorithms 2025/2026

1 Programmazione Lineare (PL)

1.1 Introduzione: L’Arte di Prendere la Decisione Ottimale

Ogni giorno prendiamo decisioni cercando di fare del nostro meglio con risorse limitate. Che si

tratti di gestire un budget, pianificare il tempo o allocare personale, l’obiettivo è sempre lo stesso:

ottenere il massimo risultato possibile. Ma come facciamo a sapere se la nostra decisione è davvero

la migliore in assoluto? Entra in gioco la Programmazione Lineare (LP), un potente framework

matematico progettato per trovare la soluzione ottimale a problemi di allocazione di risorse scarse,

non solo una soluzione ”abbastanza buona”. Si applica in innumerevoli settori, dalla logistica alla

finanza, dalla produzione all’ingegneria.

Tuttavia, l’aspetto più affascinante non risiede solo nei potenti algoritmi risolutivi. Il vero val-

ore emerge durante il processo di ”modellazione”, ovvero l’arte di tradurre un problema del mondo

reale in un modello matematico. Questo processo ci costringe a pensare in modo rigoroso e, nel

farlo, ci insegna lezioni sorprendenti e controintuitive sulla risoluzione dei problemi.

1.2 Che cos’è la programmazione lineare

Un modello di programmazione lineare è, in sostanza, un modo formale per descrivere un problema

decisionale attraverso poche componenti essenziali: delle variabili che rappresentano le decisioni

possibili, una funzione obiettivo che dobbiamo massimizzare o minimizzare e un insieme di vincoli

che limitano le soluzioni ammissibili. È importantissimo che sia la funzione obiettivo sia i vincoli

siano espressi come funzioni lineari delle variabili: questo significa che compaiono solo termini del

tipo coefficiente·variabile e somme di tali termini, senza prodotti tra variabili, potenze o funzioni

non lineari. Le variabili stesse possono essere di diverso tipo a seconda del problema: continue

quando possono assumere qualsiasi valore reale in un intervallo, intere quando devono essere nu-

meri naturali, binarie quando assumono soltanto 0 o 1; la scelta del dominio delle variabili è parte

integrante della modellazione perché incide sul tipo di algoritmo necessario per risolvere il modello.

I modelli lineari sono particolarmente apprezzati non tanto per la loro semplicità astratta, quanto

perché esistono metodi algoritmici consolidati ed efficienti per risolverli; questo consente di tradurre

il modello in un programma eseguibile e di ottenere in tempi ragionevoli la soluzione ottima. Il

processo di lavoro può essere descritto come una catena: si parte da un problema reale, si costruisce

il modello LP che idealizza il problema, si risolve il modello con un solver e infine si decodifica

la soluzione ottenuta per interpretarla nel contesto reale. Questa catena non è necessariamente

lineare: spesso la fase di decoding e l’analisi dei risultati porta a rivedere il modello (modifica di

variabili, vincoli o pesi nell’obiettivo) in un ciclo iterativo di raffinamento.

4

Emmanuel Messina - Optimizations methods and algorithms 2025/2026

Per modellare concretamente un problema si seguono tre passi pratici che sono anche concettuali:

identificare le variabili che descrivono le decisioni, scrivere la funzione obiettivo che codifica lo scopo

(massimizzare profitto, minimizzare costo, ecc.) e scrivere i vincoli che formalizzano le risorse

disponibili o i requisiti minimi. In senso più formale, le variabili devono essere scelte in modo che,

per qualsiasi possibile assegnazione di valori (ammissibili o meno), sia immediato calcolare il valore

dell’obiettivo e verificare i vincoli: questo criterio guida la scelta delle entità da elevare a variabili

del modello. Per rendere concreti questi concetti consideriamo un

Esempio 1: Il Problema dello Zaino

esempio di tipo ”knapsack” (zaino). Nel caso presentato lo zaino ha capacità 10 chilogrammi e

può essere riempito con sei tipi di prodotti: cioccolato in scatole da 500g, succhi da 1l, birre in

lattina da 0.33l, panini da 100g, acqua minerale da 1l e biscotti in scatole da 500g. Ogni prodotto

porta con sé un punteggio (una sorta di valore/utilità) che va da 1 a 100: per esempio il cioccolato

vale 10 punti per scatola, i succhi 30, la birra 6, i panini 3, l’acqua 20 e i biscotti 8. Inoltre è

stato deciso di soddisfare dei requisiti minimi per ciascun prodotto (per esempio almeno 2 scatole

di cioccolato, 2 succhi, 6 lattine di birra, 10 panini, 1 acqua, 2 biscotti). Nel modello proposto

si definiscono come variabili intere non negative che indicano rispettivamente il

A, B, C, D, E, F

numero di scatole di cioccolato, succhi, lattine di birra, panini, bottiglie di acqua e scatole di

biscotti. La funzione obiettivo, essendo un problema di massimizzazione del punteggio totale, si

scrive sommando i punteggi unitari moltiplicati per le quantità:

= max(10A + 30B + 6C + 3D + 20E + 8F )

f

La linearità dell’obiettivo è esplicita: ogni variabile compare solo con un coefficiente moltiplicativo.

Per trasformare le informazioni sul peso in vincoli occorre convertire le unità in chilogrammi: una

scatola di cioccolato pesa 0,5 kg, quindi contribuisce per 0, 5A; una lattina di birra circa 0, 33C; un

panino 0, 1D e così via. Il vincolo di capacità dello zaino diventa quindi la disuguaglianza:

1 1 1 1

+ + + + + 10

≤

A B C D E F

2 3 10 2

che formalizza il limite di 10 kg complessivi. Accanto al vincolo di capacità bisogna imporre i vincoli

che garantiscono le quantità minime decise dall’organizzazione: per ogni prodotto si impone una

5

Emmanuel Messina - Optimizations methods and algorithms 2025/2026

disuguaglianza del tipo 2, 2, 6, 10, 1, 2. Queste condizioni rendono

≥ ≥ ≥ ≥ ≥ ≥

A B C D E F

il modello realistico rispetto ai requisiti prefissati. È importante notare che, in questo esempio, le

variabili sono definite intere perché ha senso parlare di ”pezzi” indivisibili (scatole, bottiglie, lat-

tine): questo trasforma il problema in un problema di programmazione intera (un caso particolare,

più difficile, della programmazione lineare continua). Se si rilassasse la condizione di integrità delle

variabili (permettere valori reali), il modello diventerebbe un classico LP risolvibile con tecniche

come il Simplex o metodi interior-point; tuttavia la soluzione rilassata potrebbe fornire quantità

non intere che vanno poi arrotondate o gestite con tecniche di branching per trovare l’ottimo intero.

Il modello completo è dunque costituito dalla funzione obiettivo lineare che somma i punteggi

e dal sistema di vincoli formato dalla capacità totale e dalle soglie minime per ogni prodotto, con

la condizione sul dominio delle variabili (A, intere e non negative). Sebbene l’esempio

B, C, D, E, F

sembri semplice, l’identificazione delle variabili non è sempre così immediata nei problemi reali:

occorre riflettere su che cosa rappresenta una decisione elementare e scegliere le entità in modo che

il modello rimanga maneggevole ma completo.

Si considera un impianto siderurgico che deve produrre 1000

Esempio 2: Impianto siderurgico

tonnellate di una particolare lega metallica. Perché la lega abbia le proprietà richieste, è necessario

che la composizione finale contenga almeno l’1% di manganese, almeno il 18% di cromo e almeno il

2% di molibdeno. Tradotto in quantità assolute, significa che nella lega finita devono essere presenti

almeno 10 tonnellate di manganese, 180 tonnellate di cromo e 20 tonnellate di molibdeno, poiché

1% di 1000 tonnellate equivale a 10 tonnellate, 18% a 180 e 2% a 20.

Il problema nasce perché l’impianto non può acquistare i tre metalli puri separatamente a piacimen-

to: i fornitori li vendono soltanto in confezioni predefinite che contengono i tre elementi mescolati

in proporzioni fisse. Esistono tre tipi di confezioni. La prima contiene 2 chilogrammi di manganese,

2 chilogrammi di cromo e 1 chilogrammo di molibdeno, e ha un costo di 20$. La seconda confezione

offre 2 chilogrammi di manganese, 3 chilogrammi di cromo e 1 chilogrammo di molibdeno, e costa

30$. La terza contiene 1 chilogrammo di manganese, 2 chilogrammi di cromo e ben 5 chilogrammi

di molibdeno, con un prezzo di 40$. L’impianto deve quindi stabilire quante confezioni acquistare

di ciascun tipo per soddisfare i requisiti minimi della lega e, allo stesso tempo, minimizzare la spesa

complessiva.

Per tradurre la situazione in un modello di programmazione lineare occorre definire le variabili

decisionali. È naturale introdurre tre variabili che rappresentino il numero di confezioni acquistate

per ciascun tipo: indichiamo con il numero di confezioni del primo tipo, con il numero di

x x

1 2

confezioni del secondo tipo e con il numero di confezioni del terzo tipo. Poiché non si possono

x 3

acquistare quantità negative, si impo