1.2 Categorie di problemi di ottimizzazione combinatoria¶

Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 1 · Capitolo 1: Ottimizzazione combinatoria · Dispensa, volume 1 (PDF) · Slide · Esercizi: Ottimizzazione combinatoria · App: Forza bruta sul problema dello zaino 0/1

Le decisioni di un problema di ottimizzazione combinatoria rientrano in cinque categorie. A ogni categoria sono associati un oggetto combinatorio, che è la forma di una soluzione, e un tipo naturale di variabili decisionali.

1.2.1 Categorie di decisioni¶

IN/OUT (inclusione/esclusione). Ogni elemento è selezionato oppure no: una soluzione è un sottoinsieme degli elementi, descritto da variabili binarie \(x_j \in \{0,1\}\), con \(x_j = 1\) se e solo se l'elemento \(j\) è selezionato.
- Esempi: selezionare i progetti da finanziare con un budget limitato, scegliere i prodotti di un portafoglio, decidere quali clienti visitare in un percorso.
Conteggio (quantità discrete). La decisione è quante unità di ogni elemento usare: una soluzione è un vettore di quantità intere, descritto da variabili intere \(x_j \in \Z_{\ge 0}\).
- Esempi: quante unità di un prodotto produrre, quanti operatori assegnare a un turno, quanti server attivare in un data center.
Assegnamento. Ogni elemento è assegnato a esattamente una fra diverse risorse distinte: una soluzione è una funzione dagli elementi alle risorse, descritta da variabili binarie \(x_{ij} \in \{0,1\}\), uguali a \(1\) se e solo se l'elemento \(j\) è assegnato alla risorsa \(i\).
- Esempi: assegnare compiti a macchine o persone, abbinare studenti a progetti, allocare veicoli ai percorsi di consegna.
Ordinamento e sequenze. La decisione è l'ordine in cui gli elementi sono lavorati o visitati: una soluzione è una permutazione \(\sigma = (\sigma_1,\dots,\sigma_n)\) degli elementi, o un ordinamento ciclico per un giro.
- Esempi: l'ordine in cui sono lavorati i lavori, la sequenza delle operazioni su una macchina, l'ordine di visita dei clienti.
Configurazione e partizionamento. Gli elementi sono suddivisi in gruppi, ciascuno dei quali soddisfa una condizione come una capacità: una soluzione è una partizione degli elementi in gruppi intercambiabili.
- Esempi: suddividere un insieme di elementi in gruppi, impaccare oggetti in contenitori, tagliare materiali minimizzando lo sfrido.

Categoria	Oggetto combinatorio	Variabili naturali
IN/OUT	sottoinsieme	\(x_j \in \{0,1\}\)
conteggio	vettore di quantità intere	\(x_j \in \Z_{\ge 0}\)
assegnamento	funzione (classi etichettate)	\(x_{ij} \in \{0,1\}\), una risorsa \(i\) per ogni \(j\)
ordinamento e sequenze	permutazione, ordinamento ciclico	\(x_{ij} \in \{0,1\}\), uguale a \(1\) se \(j\) segue \(i\)
configurazione e partizionamento	partizione (classi non etichettate)	\(x_{ij} \in \{0,1\}\), elemento \(j\) nel gruppo \(i\)

La tabella riassume le cinque categorie, i loro oggetti combinatori e le loro variabili naturali.
Con un insieme base opportuno ogni categoria rientra nella Definizione 1.1: per un assegnamento l'insieme base è l'insieme delle coppie (elemento, risorsa), per un ordinamento l'insieme delle coppie di elementi consecutivi.
Assegnamento e partizionamento differiscono solo nelle risorse: risorse distinte danno classi etichettate, risorse identiche danno gruppi intercambiabili (Sezione 1.3).

La categoria delle decisioni determina l'oggetto combinatorio delle soluzioni, il numero di soluzioni candidate e le variabili decisionali naturali.

1.2.2 Aree applicative¶

I problemi di ottimizzazione combinatoria nascono in molte aree applicative. Le principali, con le loro decisioni tipiche e alcuni esempi, sono:

Area	Decisioni tipiche	Esempi
pianificazione della produzione	che cosa, quando e quanto produrre, con quali risorse	lot sizing, pianificazione della capacità, bilanciamento delle linee di assemblaggio
scheduling	ordine e tempi delle operazioni sulle risorse	scheduling dei lavori sulle macchine, scheduling di progetti, scheduling della manutenzione
localizzazione di impianti	dove aprire gli impianti e quali clienti serve ciascuno	localizzazione di magazzini, di stabilimenti, di servizi di emergenza
packing	come sistemare oggetti in contenitori	selezione del carico, carico di più veicoli, carico dei pallet
taglio	come tagliare il materiale grezzo nei pezzi richiesti	taglio di barre e lastre, minimizzazione dello sfrido, taglio a ghigliottina
logistica e catena di fornitura	percorsi, flotte e livelli di scorta	instradamento di veicoli, gestione della flotta, gestione delle scorte
trasporti	equipaggi, veicoli e orari di un sistema di mobilità	turnazione degli equipaggi, instradamento degli aerei, orari ferroviari
gestione del personale	assegnamento di persone a compiti, turni e ruoli	pianificazione della forza lavoro, turni degli infermieri, pianificazione dei turni
progettazione di reti	quali nodi e archi di una rete attivare	reti di telecomunicazione, energetiche e di trasporto

Un problema reale combina spesso diverse categorie. Per esempio, la localizzazione di impianti decide quali impianti aprire (IN/OUT) e assegna ogni cliente a un impianto aperto (assegnamento).

1.2.3 I problemi del corso per categoria¶

La tabella colloca i problemi del corso nelle loro categorie; ogni nome rimanda alla sua pagina.

Problema	Soluzione	Categoria
problema dello zaino 0/1 (KP)	sottoinsieme di oggetti	IN/OUT
problema del subset sum (SSP)	sottoinsieme di oggetti	IN/OUT
problema dello zaino limitato (BKP)	numero di copie di ogni oggetto	conteggio
problema dello zaino illimitato (UKP)	numero di copie di ogni oggetto	conteggio
problema dello zaino multidimensionale (MDKP)	sottoinsieme di oggetti	IN/OUT
problema degli zaini multipli (MKP)	ogni oggetto in uno zaino o in nessuno	assegnamento
problema dello zaino a scelta multipla (MCKP)	un oggetto per classe	IN/OUT
problema dello zaino con setup (KPS)	sottoinsieme di classi e di oggetti	IN/OUT
problema del bin packing (BPP)	partizione degli oggetti nei contenitori	partizionamento
problema del cutting stock (CSP)	numero di rotoli tagliati con ogni schema	configurazione, conteggio
problema della colorazione dei vertici (VCP)	partizione dei vertici in insiemi stabili	partizionamento
problema della clique massima (MCP)	sottoinsieme di vertici	IN/OUT
problema dell'insieme stabile massimo (MSSP)	sottoinsieme di vertici	IN/OUT
problema del commesso viaggiatore (TSP)	ordinamento ciclico delle città	ordinamento
problema del commesso viaggiatore asimmetrico (ATSP)	ordinamento delle città su un giro	ordinamento
scheduling su macchine parallele identiche (\(P\\|C_{\max}\))	assegnamento dei lavori alle macchine	assegnamento
problema di lot sizing capacitato (CLS)	periodi di setup e quantità prodotte	IN/OUT, conteggio

Avanti: 1.3 Contare le soluzioni