Modelli di Programmazione Lineare Intera

Author

Your Name

Published

January 30, 2025

Introduction

In questa lezione affronteremo il problema di come scrivere modelli di programmazione lineare intera. Discuteremo di come scegliere le variabili in modo appropriato, considerando sia variabili numeriche che booleane. Vedremo anche come evitare di trattare etichette come numeri e illustreremo questi concetti con alcuni esempi, tra cui il problema del Sudoku, la pianificazione di test per componenti elettroniche e di un calendario per un campionato di calcio. L’obiettivo principale è imparare a formulare modelli che siano efficienti e risolvibili in modo efficace dai solver.

La scelta delle variabili è cruciale nella programmazione lineare intera.
Variabili numeriche sono adatte per quantità misurabili.
Variabili booleane sono utilizzate per decisioni binarie (sì/no) o per rappresentare l’assegnazione di etichette a oggetti.
Evitare di trattare etichette come numeri per prevenire distorsioni nel modello.
L’efficienza del modello è fondamentale per la risoluzione tramite solver.

Scelta delle Variabili nei Modelli

La prima fase nella scrittura di un modello è la scelta delle variabili. Questa fase è cruciale e può essere affrontata in modi diversi a seconda del problema. Non esiste un insieme di regole fisse per la scelta delle variabili; è un processo creativo simile alla scrittura di un tema. L’esperienza e la conoscenza di modelli che hanno funzionato in passato sono fondamentali per imparare a scrivere modelli efficaci.

Variabili Numeriche

In molti problemi, le variabili del problema reale sono numeriche. Ad esempio:

Gestione di un ristorante: decidere le quantità di ingredienti (zucchero, farina, uova) da tenere in magazzino. In questo caso, le variabili rappresentano quantità fisiche e sono naturalmente espresse come numeri reali non negativi. Potremmo usare variabili come $x_s$ per la quantità di zucchero, $x_f$ per la quantità di farina e $x_e$ per il numero di uova.
Piazzamento di trasmettitori: determinare le coordinate $(x, y)$ dove posizionare i trasmettitori. Qui, le variabili rappresentano coordinate geografiche e possono essere numeri reali. Ad esempio, $x_i$ e $y_i$ potrebbero rappresentare le coordinate del trasmettitore $i$.
Assunzione di personale: decidere il numero di persone da assumere. In questo caso, le variabili rappresentano un conteggio e sono naturalmente espresse come numeri interi non negativi. Potremmo usare una variabile $p$ per indicare il numero di persone da assumere.

In questi casi, le variabili sono naturalmente numeriche e spesso non negative. Tuttavia, in alcuni casi, le variabili possono assumere valori negativi, come nel caso delle coordinate, dove un trasmettitore potrebbe essere posizionato a ovest o a sud rispetto a un’origine.

Variabili Booleane e a Scelta Multipla

In altri problemi, le variabili decisionali non sono numeriche, ma booleane (sì/no) o a scelta multipla. Ad esempio:

Iniziare la produzione di un prodotto: sì o no? Qui, la decisione è binaria e può essere rappresentata da una variabile booleana $x$, dove $x=1$ se si inizia la produzione e $x=0$ altrimenti.
Scegliere quali prodotti produrre tra A, B, C, D. In questo caso, abbiamo una scelta multipla. Potremmo usare variabili booleane $x_A, x_B, x_C, x_D$, dove $x_A=1$ se si produce A e $x_A=0$ altrimenti, e così via.

Queste variabili devono essere mappate in domini numerici. Le scelte booleane vengono spesso mappate nell’insieme $\{0, 1\}$, dove 0 rappresenta falso e 1 rappresenta vero. Le scelte multiple possono essere mappate in insiemi come $\{1, 2, 3, 4, 5\}$.

Trasformare etichette in numeri può introdurre problemi. Ad esempio, se A diventa 1 e E diventa 5, la differenza numerica tra 1 e 5 non riflette la natura delle etichette originali. Questo può influenzare i calcoli successivi e portare a risultati errati.

Variabili Intere e Continue

Un modello può contenere sia variabili intere che continue. La programmazione lineare intera richiede che almeno alcune variabili siano intere. Se nessuna variabile è obbligata ad essere intera, si parla di programmazione lineare. Se tutte le variabili sono intere, si parla di programmazione lineare intera pura. Ad esempio, nel problema del ristorante, potremmo avere la variabile $x_s$ (quantità di zucchero) come variabile continua, mentre la variabile $x_e$ (numero di uova) come variabile intera.

Tipi di programmazione in base alle variabili
Tipo di Programmazione	Tipo di Variabili	Esempio
Programmazione Lineare	Continue	Quantità di farina
Programmazione Lineare Intera Mista	Continue e Intere	Quantità di zucchero (continua), Numero di uova (intera)
Programmazione Lineare Intera Pura	Intere	Numero di persone da assumere

Numeri come Etichette: Il Problema del Sudoku

Consideriamo il gioco del Sudoku come esempio di problema di ottimizzazione. L’obiettivo potrebbe essere completare un Sudoku parziale minimizzando l’uso di un certo numero in caselle specifiche (colorate di rosso).

Supponiamo che le caselle rosse siano quelle in cui vogliamo minimizzare l’uso del numero 9.

Modello 1: Variabili Numeriche per Casella

Un possibile modello per il problema del Sudoku prevede una variabile $x_C$ per ogni casella $C$, che rappresenta il numero da inserire nella casella.

Variabili: $x_C \in \{1, 2, ..., 9\}$ per ogni casella $C$.
Esempio: Se nella casella $C$ in posizione $(1,1)$ vogliamo inserire il numero 5, allora $x_C = 5$.

Modello 2: Variabili Booleane per Casella e Valore

Un modello migliore per il problema del Sudoku prevede una variabile booleana $x_{C,J}$ per ogni casella $C$ e possibile valore $J$, che indica se il valore $J$ è inserito nella casella $C$.

Variabili: $x_{C,J} \in \{0, 1\}$ per ogni casella $C$ e per ogni possibile valore $J \in \{1, 2, ..., 9\}$.
Significato: $x_{C,J} = 1$ se il valore $J$ è inserito nella casella $C$, $x_{C,J} = 0$ altrimenti.
Esempio: Se nella casella $C$ in posizione $(1,1)$ vogliamo inserire il numero 5, allora $x_{C,5} = 1$ e $x_{C,J} = 0$ per tutti gli altri valori di $J$.

Il secondo modello è migliore perché tratta i numeri come etichette. Usare variabili numeriche introduce un "bias" che confonde il solver, poiché i numeri nel Sudoku non hanno un vero significato numerico: potrebbero essere sostituiti da colori o simboli senza alterare la natura del problema.

Confronto tra i due modelli:

Il Modello 1 usa $81$ variabili numeriche, una per ogni casella.
Il Modello 2 usa $81 \times 9 = 729$ variabili booleane, una per ogni possibile combinazione di casella e valore.

Nonostante il Modello 2 utilizzi un numero maggiore di variabili, risulta più efficiente in termini di risoluzione del problema da parte del solver. Questo perché il Modello 1, trattando i numeri come valori numerici anziché come etichette, introduce una struttura artificiale nel problema che rende più difficile trovare la soluzione ottima.

Esempio: Test di Componenti Elettroniche

Supponiamo di dover testare componenti elettroniche e di avere $n$ possibili test. Ogni test $i$ ha un costo $c_i$ e identifica un sottoinsieme di difetti $T_i$.

Primo Problema: Coprire Tutti i Difetti

Vogliamo scegliere un insieme di test che copra tutti i difetti, ovvero tale che l’unione dei sottoinsiemi $T_i$ dei test scelti sia uguale all’insieme di tutti i possibili difetti. Variabili: una variabile binaria $x_i$ per ogni test $i$, che indica se eseguire o meno il test.

$x_i = 1$ se il test $i$ viene eseguito.
$x_i = 0$ se il test $i$ non viene eseguito.

Secondo Problema: Massimizzare la Copertura con Budget Limitato

Vogliamo massimizzare il numero di difetti coperti con un budget limitato $B$, ovvero vogliamo massimizzare il numero di difetti che sono identificati da almeno uno dei test scelti, rispettando il vincolo che la somma dei costi dei test scelti non superi $B$. Variabili:

Variabili $x_i$ per ogni test $i$ (come nel primo problema):
- $x_i = 1$ se il test $i$ viene eseguito.
- $x_i = 0$ se il test $i$ non viene eseguito.
Variabili booleane $y_j$ per ogni difetto $j$, che indicano se il difetto è coperto dai test scelti:
- $y_j = 1$ se il difetto $j$ è coperto da almeno un test scelto.
- $y_j = 0$ altrimenti.

Funzione obiettivo: massimizzare $\sum_j y_j$, ovvero il numero totale di difetti coperti.

Le variabili $y_j$ sono determinate dalle variabili $x_i$. I vincoli del modello assicureranno che le $y_j$ riflettano correttamente la copertura dei difetti in base ai test scelti. In particolare, se $y_j = 1$, allora almeno un test che copre il difetto $j$ deve essere stato scelto. Viceversa, se nessun test che copre il difetto $j$ è stato scelto, allora $y_j$ deve essere uguale a 0.

Analisi di complessità:

Il numero di variabili $x_i$ è pari al numero di test $n$.
Il numero di variabili $y_j$ è pari al numero di difetti. Se assumiamo che ci siano $m$ difetti, avremo $m$ variabili $y_j$.
Il numero totale di variabili è $n + m$.

In questo caso, l’introduzione delle variabili $y_j$ ci permette di esprimere la funzione obiettivo in modo lineare. Senza le variabili $y_j$, la funzione obiettivo sarebbe non lineare, coinvolgendo l’unione di insiemi.

Esempio: Calendario di un Campionato di Calcio

Supponiamo di avere $n$ squadre di calcio (con $n$ pari, $n=2k$) e di dover pianificare un calendario in cui ogni squadra gioca contro ogni altra squadra due volte (una volta in casa e una volta fuori casa).

Dettagli del Problema

Il campionato richiederà $2(n-1)$ giornate.
In ogni giornata ci sono $n/2 = k$ partite.
Le prime $n-1$ giornate (girone di andata) determinano le successive $n-1$ giornate (girone di ritorno). In altre parole, se la squadra $i$ gioca contro la squadra $j$ in casa nella giornata $h$ del girone di andata, allora la squadra $j$ giocherà contro la squadra $i$ in casa nella giornata $h$ del girone di ritorno.

Obiettivo: decidere il calendario, fissando le partite per ogni giornata del girone di andata. Il girone di ritorno è determinato univocamente da quello di andata.

Modello 1: Variabili a Tre Indici

Un possibile modello per il problema del calendario di un campionato di calcio utilizza variabili booleane $x_{i,j,h}$, dove $i$ e $j$ sono squadre ($i,j \in \{1, ..., n\}$) e $h$ è la giornata ($h \in \{1, ..., n-1\}$).

$x_{i,j,h} = 1$ se la squadra $i$ gioca in casa contro la squadra $j$ nella giornata $h$ del girone di andata.
$x_{i,j,h} = 0$ altrimenti.

Numero di variabili: $n(n-1)(n-1)$. Per ogni giornata $h$, ci sono $n(n-1)$ possibili coppie di squadre $(i, j)$ con $i \neq j$. Poiché ci sono $n-1$ giornate, il numero totale di variabili è $n(n-1)(n-1)$, che è circa $n^3$. Esempio: Se $x_{1,2,3} = 1$, significa che la squadra 1 gioca in casa contro la squadra 2 nella terza giornata del girone di andata.

Modello 2: Variabili con Etichette Numeriche e Segno

Un altro modello per il problema del calendario di un campionato di calcio utilizza variabili $x_{i,j}$ per ogni squadra $i$ ($i \in \{1, ..., n\}$) e giornata $j$ ($j \in \{1, ..., n-1\}$) del girone di andata, che indicano la squadra avversaria. Il segno indica se la partita è in casa (positivo) o fuori casa (negativo).

$x_{i,j} = +k$ se la squadra $i$ gioca in casa contro la squadra $k$ nella giornata $j$ del girone di andata.
$x_{i,j} = -k$ se la squadra $i$ gioca fuori casa contro la squadra $k$ nella giornata $j$ del girone di andata.

Numero di variabili: $n(n-1)$. Per ogni squadra $i$, ci sono $n-1$ giornate nel girone di andata. Quindi, il numero totale di variabili è $n(n-1)$, che è circa $n^2$. Esempio: Se $x_{1,3} = -2$, significa che la squadra 1 gioca fuori casa contro la squadra 2 nella terza giornata del girone di andata.

Questo modello usa etichette come numeri e codifica informazioni aggiuntive nel segno, rendendolo inefficiente e poco chiaro. Inoltre, introduce una struttura ordinale artificiale tra le squadre (rappresentate da numeri) che non è presente nel problema originale.

Modello 3: Variabili con Indici di Giornata

Un terzo modello per il problema del calendario di un campionato di calcio utilizza variabili $x_{i,j}$ per ogni coppia di squadre $i$ e $j$ ($i,j \in \{1, ..., n\}, i < j$), che indicano la giornata in cui $i$ gioca in casa contro $j$.

$x_{i,j} = h$ con $h \in \{1, ..., n-1\}$ se la squadra $i$ gioca in casa contro la squadra $j$ nella giornata $h$ del girone di andata.
$x_{i,j} = h$ con $h \in \{n, ..., 2(n-1)\}$ se la squadra $j$ gioca in casa contro la squadra $i$ nella giornata $h - (n-1)$ del girone di andata.

Numero di variabili: $n(n-1)/2$. Ci sono $n(n-1)/2$ possibili coppie di squadre $(i, j)$ con $i < j$. Esempio: Se $x_{1,2} = 3$, significa che la squadra 1 gioca in casa contro la squadra 2 nella terza giornata del girone di andata. Se $x_{1,2} = n+2 = 12$ (supponendo $n=10$), significa che la squadra 2 gioca in casa contro la squadra 1 nella seconda giornata del girone di andata.

Anche questo modello tratta le giornate (etichette) come numeri, introducendo una struttura ordinale artificiale che non è presente nel problema originale.

Confronto tra i modelli:

Il Modello 1 è il più chiaro e naturale, ma ha il maggior numero di variabili.
Il Modello 2 ha meno variabili, ma è il più complesso e introduce distorsioni.
Il Modello 3 ha il minor numero di variabili, ma è meno chiaro del Modello 1 e introduce anch’esso distorsioni.

La scelta del modello migliore dipende dal trade-off tra semplicità, numero di variabili ed efficienza del solver. In questo caso, il Modello 1 potrebbe essere preferibile nonostante il maggior numero di variabili, grazie alla sua chiarezza e alla sua aderenza alla natura del problema.

Conclusion

In questa lezione abbiamo discusso l’importanza della scelta delle variabili nella programmazione lineare intera. Abbiamo visto come variabili numeriche e booleane possano essere utilizzate per modellare diversi tipi di problemi, e come sia fondamentale evitare di trattare etichette come numeri per non introdurre distorsioni nel modello. Abbiamo analizzato tre esempi: il Sudoku, la pianificazione di test per componenti elettroniche e la creazione di un calendario per un campionato di calcio. In particolare, per l’esempio del campionato di calcio, abbiamo proposto tre modelli alternativi, evidenziandone pregi e difetti. La scelta del modello migliore dipende da vari fattori, tra cui il numero di variabili, la complessità dei vincoli e l’efficienza del solver. Spesso è necessario implementare e testare più modelli per determinare quello più adatto al problema specifico.

La scelta delle variabili è un passo fondamentale nella modellazione di problemi di programmazione lineare intera.
Variabili numeriche sono adatte a rappresentare quantità, mentre variabili booleane sono più adatte a rappresentare scelte binarie o l’assegnazione di etichette.
Trattare etichette come numeri può introdurre distorsioni e rendere il modello meno efficiente.
La scelta del modello migliore è un processo iterativo che può richiedere la sperimentazione con diversi modelli.

Domande per la prossima lezione:

Come si scrivono i vincoli per i modelli presentati?
- Ad esempio, come si esprime il vincolo che ogni squadra deve giocare contro ogni altra squadra esattamente una volta in casa e una volta fuori casa nel modello del campionato di calcio?
- Come si esprime il vincolo che ogni difetto deve essere coperto da almeno un test nel problema dei test di componenti elettroniche?
Quali sono le tecniche per risolvere i modelli di programmazione lineare intera?
- Quali algoritmi vengono utilizzati dai solver?
- Come funzionano questi algoritmi?
Come si valuta l’efficienza di un modello?
- Quali metriche si utilizzano per confrontare diversi modelli?
- Come si misura il tempo di esecuzione di un solver?

--- title: "Modelli di Programmazione Lineare Intera" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction In questa lezione affronteremo il problema di come scrivere modelli di programmazione lineare intera. Discuteremo di come scegliere le variabili in modo appropriato, considerando sia variabili numeriche che booleane. Vedremo anche come evitare di trattare etichette come numeri e illustreremo questi concetti con alcuni esempi, tra cui il problema del Sudoku, la pianificazione di test per componenti elettroniche e di un calendario per un campionato di calcio. L'obiettivo principale è imparare a formulare modelli che siano efficienti e risolvibili in modo efficace dai solver. ::: tcolorbox - La **scelta delle variabili** è cruciale nella programmazione lineare intera. - **Variabili numeriche** sono adatte per quantità misurabili. - **Variabili booleane** sono utilizzate per decisioni binarie (sì/no) o per rappresentare l'assegnazione di etichette a oggetti. - **Evitare di trattare etichette come numeri** per prevenire distorsioni nel modello. - L'efficienza del modello è fondamentale per la risoluzione tramite solver. ::: # Scelta delle Variabili nei Modelli La prima fase nella scrittura di un modello è la **scelta delle variabili**. Questa fase è cruciale e può essere affrontata in modi diversi a seconda del problema. Non esiste un insieme di regole fisse per la scelta delle variabili; è un processo creativo simile alla scrittura di un tema. L'esperienza e la conoscenza di modelli che hanno funzionato in passato sono fondamentali per imparare a scrivere modelli efficaci. ## Variabili Numeriche In molti problemi, le variabili del problema reale sono numeriche. Ad esempio: - **Gestione di un ristorante**: decidere le quantità di ingredienti (zucchero, farina, uova) da tenere in magazzino. In questo caso, le variabili rappresentano quantità fisiche e sono naturalmente espresse come numeri reali non negativi. Potremmo usare variabili come $x_s$ per la quantità di zucchero, $x_f$ per la quantità di farina e $x_e$ per il numero di uova. - **Piazzamento di trasmettitori**: determinare le coordinate $(x, y)$ dove posizionare i trasmettitori. Qui, le variabili rappresentano coordinate geografiche e possono essere numeri reali. Ad esempio, $x_i$ e $y_i$ potrebbero rappresentare le coordinate del trasmettitore $i$. - **Assunzione di personale**: decidere il numero di persone da assumere. In questo caso, le variabili rappresentano un conteggio e sono naturalmente espresse come numeri interi non negativi. Potremmo usare una variabile $p$ per indicare il numero di persone da assumere. In questi casi, le variabili sono naturalmente numeriche e spesso non negative. Tuttavia, in alcuni casi, le variabili possono assumere valori negativi, come nel caso delle coordinate, dove un trasmettitore potrebbe essere posizionato a ovest o a sud rispetto a un'origine. ## Variabili Booleane e a Scelta Multipla In altri problemi, le variabili decisionali non sono numeriche, ma **booleane** (sì/no) o a **scelta multipla**. Ad esempio: - **Iniziare la produzione di un prodotto**: sì o no? Qui, la decisione è binaria e può essere rappresentata da una variabile booleana $x$, dove $x=1$ se si inizia la produzione e $x=0$ altrimenti. - **Scegliere quali prodotti produrre tra A, B, C, D**. In questo caso, abbiamo una scelta multipla. Potremmo usare variabili booleane $x_A, x_B, x_C, x_D$, dove $x_A=1$ se si produce A e $x_A=0$ altrimenti, e così via. Queste variabili devono essere mappate in domini numerici. Le scelte booleane vengono spesso mappate nell'insieme $\{0, 1\}$, dove 0 rappresenta falso e 1 rappresenta vero. Le scelte multiple possono essere mappate in insiemi come $\{1, 2, 3, 4, 5\}$. ::: tcolorbox Trasformare etichette in numeri può introdurre problemi. Ad esempio, se A diventa 1 e E diventa 5, la differenza numerica tra 1 e 5 non riflette la natura delle etichette originali. Questo può influenzare i calcoli successivi e portare a risultati errati. ::: ## Variabili Intere e Continue {#subsec:variabili_miste} Un modello può contenere sia variabili intere che continue. La **programmazione lineare intera** richiede che almeno alcune variabili siano intere. Se nessuna variabile è obbligata ad essere intera, si parla di **programmazione lineare**. Se tutte le variabili sono intere, si parla di **programmazione lineare intera pura**. Ad esempio, nel problema del ristorante, potremmo avere la variabile $x_s$ (quantità di zucchero) come variabile continua, mentre la variabile $x_e$ (numero di uova) come variabile intera. ::: tab:tipi_programmazione **Tipo di Programmazione** **Tipo di Variabili** **Esempio** ------------------------------------- ----------------------- ---------------------------------------------------------- Programmazione Lineare Continue Quantità di farina Programmazione Lineare Intera Mista Continue e Intere Quantità di zucchero (continua), Numero di uova (intera) Programmazione Lineare Intera Pura Intere Numero di persone da assumere : Tipi di programmazione in base alle variabili ::: # Numeri come Etichette: Il Problema del Sudoku Consideriamo il gioco del Sudoku come esempio di problema di ottimizzazione. L'obiettivo potrebbe essere completare un Sudoku parziale minimizzando l'uso di un certo numero in caselle specifiche (colorate di rosso). ::: center ::: Supponiamo che le caselle rosse siano quelle in cui vogliamo minimizzare l'uso del numero 9. ## Modello 1: Variabili Numeriche per Casella ::: tcolorbox Un possibile modello per il problema del Sudoku prevede una variabile $x_C$ per ogni casella $C$, che rappresenta il numero da inserire nella casella. - **Variabili**: $x_C \in \{1, 2, ..., 9\}$ per ogni casella $C$. - **Esempio**: Se nella casella $C$ in posizione $(1,1)$ vogliamo inserire il numero 5, allora $x_C = 5$. ::: ## Modello 2: Variabili Booleane per Casella e Valore ::: tcolorbox Un modello migliore per il problema del Sudoku prevede una variabile booleana $x_{C,J}$ per ogni casella $C$ e possibile valore $J$, che indica se il valore $J$ è inserito nella casella $C$. - **Variabili**: $x_{C,J} \in \{0, 1\}$ per ogni casella $C$ e per ogni possibile valore $J \in \{1, 2, ..., 9\}$. - **Significato**: $x_{C,J} = 1$ se il valore $J$ è inserito nella casella $C$, $x_{C,J} = 0$ altrimenti. - **Esempio**: Se nella casella $C$ in posizione $(1,1)$ vogliamo inserire il numero 5, allora $x_{C,5} = 1$ e $x_{C,J} = 0$ per tutti gli altri valori di $J$. ::: ::: tcolorbox Il secondo modello è migliore perché tratta i numeri come etichette. Usare variabili numeriche introduce un \"bias\" che confonde il solver, poiché i numeri nel Sudoku non hanno un vero significato numerico: potrebbero essere sostituiti da colori o simboli senza alterare la natura del problema. ::: **Confronto tra i due modelli**: - Il Modello 1 usa $81$ variabili numeriche, una per ogni casella. - Il Modello 2 usa $81 \times 9 = 729$ variabili booleane, una per ogni possibile combinazione di casella e valore. Nonostante il Modello 2 utilizzi un numero maggiore di variabili, risulta più efficiente in termini di risoluzione del problema da parte del solver. Questo perché il Modello 1, trattando i numeri come valori numerici anziché come etichette, introduce una struttura artificiale nel problema che rende più difficile trovare la soluzione ottima. # Esempio: Test di Componenti Elettroniche Supponiamo di dover testare componenti elettroniche e di avere $n$ possibili test. Ogni test $i$ ha un costo $c_i$ e identifica un sottoinsieme di difetti $T_i$. ## Primo Problema: Coprire Tutti i Difetti ::: tcolorbox Vogliamo scegliere un insieme di test che copra tutti i difetti, ovvero tale che l'unione dei sottoinsiemi $T_i$ dei test scelti sia uguale all'insieme di tutti i possibili difetti. **Variabili:** una variabile binaria $x_i$ per ogni test $i$, che indica se eseguire o meno il test. - $x_i = 1$ se il test $i$ viene eseguito. - $x_i = 0$ se il test $i$ non viene eseguito. ::: ## Secondo Problema: Massimizzare la Copertura con Budget Limitato ::: tcolorbox Vogliamo massimizzare il numero di difetti coperti con un budget limitato $B$, ovvero vogliamo massimizzare il numero di difetti che sono identificati da almeno uno dei test scelti, rispettando il vincolo che la somma dei costi dei test scelti non superi $B$. **Variabili:** - Variabili $x_i$ per ogni test $i$ (come nel primo problema): - $x_i = 1$ se il test $i$ viene eseguito. - $x_i = 0$ se il test $i$ non viene eseguito. - Variabili booleane $y_j$ per ogni difetto $j$, che indicano se il difetto è coperto dai test scelti: - $y_j = 1$ se il difetto $j$ è coperto da almeno un test scelto. - $y_j = 0$ altrimenti. **Funzione obiettivo:** massimizzare $\sum_j y_j$, ovvero il numero totale di difetti coperti. ::: ::: tcolorbox Le variabili $y_j$ sono determinate dalle variabili $x_i$. I vincoli del modello assicureranno che le $y_j$ riflettano correttamente la copertura dei difetti in base ai test scelti. In particolare, se $y_j = 1$, allora almeno un test che copre il difetto $j$ deve essere stato scelto. Viceversa, se nessun test che copre il difetto $j$ è stato scelto, allora $y_j$ deve essere uguale a 0. ::: **Analisi di complessità**: - Il numero di variabili $x_i$ è pari al numero di test $n$. - Il numero di variabili $y_j$ è pari al numero di difetti. Se assumiamo che ci siano $m$ difetti, avremo $m$ variabili $y_j$. - Il numero totale di variabili è $n + m$. In questo caso, l'introduzione delle variabili $y_j$ ci permette di esprimere la funzione obiettivo in modo lineare. Senza le variabili $y_j$, la funzione obiettivo sarebbe non lineare, coinvolgendo l'unione di insiemi. # Esempio: Calendario di un Campionato di Calcio Supponiamo di avere $n$ squadre di calcio (con $n$ pari, $n=2k$) e di dover pianificare un calendario in cui ogni squadra gioca contro ogni altra squadra due volte (una volta in casa e una volta fuori casa). ## Dettagli del Problema - Il campionato richiederà $2(n-1)$ giornate. - In ogni giornata ci sono $n/2 = k$ partite. - Le prime $n-1$ giornate (girone di andata) determinano le successive $n-1$ giornate (girone di ritorno). In altre parole, se la squadra $i$ gioca contro la squadra $j$ in casa nella giornata $h$ del girone di andata, allora la squadra $j$ giocherà contro la squadra $i$ in casa nella giornata $h$ del girone di ritorno. **Obiettivo:** decidere il calendario, fissando le partite per ogni giornata del girone di andata. Il girone di ritorno è determinato univocamente da quello di andata. ## Modello 1: Variabili a Tre Indici ::: tcolorbox Un possibile modello per il problema del calendario di un campionato di calcio utilizza variabili booleane $x_{i,j,h}$, dove $i$ e $j$ sono squadre ($i,j \in \{1, ..., n\}$) e $h$ è la giornata ($h \in \{1, ..., n-1\}$). - $x_{i,j,h} = 1$ se la squadra $i$ gioca in casa contro la squadra $j$ nella giornata $h$ del girone di andata. - $x_{i,j,h} = 0$ altrimenti. **Numero di variabili:** $n(n-1)(n-1)$. Per ogni giornata $h$, ci sono $n(n-1)$ possibili coppie di squadre $(i, j)$ con $i \neq j$. Poiché ci sono $n-1$ giornate, il numero totale di variabili è $n(n-1)(n-1)$, che è circa $n^3$. **Esempio**: Se $x_{1,2,3} = 1$, significa che la squadra 1 gioca in casa contro la squadra 2 nella terza giornata del girone di andata. ::: ## Modello 2: Variabili con Etichette Numeriche e Segno ::: tcolorbox Un altro modello per il problema del calendario di un campionato di calcio utilizza variabili $x_{i,j}$ per ogni squadra $i$ ($i \in \{1, ..., n\}$) e giornata $j$ ($j \in \{1, ..., n-1\}$) del girone di andata, che indicano la squadra avversaria. Il segno indica se la partita è in casa (positivo) o fuori casa (negativo). - $x_{i,j} = +k$ se la squadra $i$ gioca in casa contro la squadra $k$ nella giornata $j$ del girone di andata. - $x_{i,j} = -k$ se la squadra $i$ gioca fuori casa contro la squadra $k$ nella giornata $j$ del girone di andata. **Numero di variabili:** $n(n-1)$. Per ogni squadra $i$, ci sono $n-1$ giornate nel girone di andata. Quindi, il numero totale di variabili è $n(n-1)$, che è circa $n^2$. **Esempio**: Se $x_{1,3} = -2$, significa che la squadra 1 gioca fuori casa contro la squadra 2 nella terza giornata del girone di andata. ::: ::: tcolorbox Questo modello usa etichette come numeri e codifica informazioni aggiuntive nel segno, rendendolo inefficiente e poco chiaro. Inoltre, introduce una struttura ordinale artificiale tra le squadre (rappresentate da numeri) che non è presente nel problema originale. ::: ## Modello 3: Variabili con Indici di Giornata ::: tcolorbox Un terzo modello per il problema del calendario di un campionato di calcio utilizza variabili $x_{i,j}$ per ogni coppia di squadre $i$ e $j$ ($i,j \in \{1, ..., n\}, i < j$), che indicano la giornata in cui $i$ gioca in casa contro $j$. - $x_{i,j} = h$ con $h \in \{1, ..., n-1\}$ se la squadra $i$ gioca in casa contro la squadra $j$ nella giornata $h$ del girone di andata. - $x_{i,j} = h$ con $h \in \{n, ..., 2(n-1)\}$ se la squadra $j$ gioca in casa contro la squadra $i$ nella giornata $h - (n-1)$ del girone di andata. **Numero di variabili:** $n(n-1)/2$. Ci sono $n(n-1)/2$ possibili coppie di squadre $(i, j)$ con $i < j$. **Esempio**: Se $x_{1,2} = 3$, significa che la squadra 1 gioca in casa contro la squadra 2 nella terza giornata del girone di andata. Se $x_{1,2} = n+2 = 12$ (supponendo $n=10$), significa che la squadra 2 gioca in casa contro la squadra 1 nella seconda giornata del girone di andata. ::: ::: tcolorbox Anche questo modello tratta le giornate (etichette) come numeri, introducendo una struttura ordinale artificiale che non è presente nel problema originale. ::: **Confronto tra i modelli**: - Il Modello 1 è il più chiaro e naturale, ma ha il maggior numero di variabili. - Il Modello 2 ha meno variabili, ma è il più complesso e introduce distorsioni. - Il Modello 3 ha il minor numero di variabili, ma è meno chiaro del Modello 1 e introduce anch'esso distorsioni. La scelta del modello migliore dipende dal trade-off tra semplicità, numero di variabili ed efficienza del solver. In questo caso, il Modello 1 potrebbe essere preferibile nonostante il maggior numero di variabili, grazie alla sua chiarezza e alla sua aderenza alla natura del problema. # Conclusion In questa lezione abbiamo discusso l'importanza della scelta delle variabili nella programmazione lineare intera. Abbiamo visto come variabili numeriche e booleane possano essere utilizzate per modellare diversi tipi di problemi, e come sia fondamentale evitare di trattare etichette come numeri per non introdurre distorsioni nel modello. Abbiamo analizzato tre esempi: il Sudoku, la pianificazione di test per componenti elettroniche e la creazione di un calendario per un campionato di calcio. In particolare, per l'esempio del campionato di calcio, abbiamo proposto tre modelli alternativi, evidenziandone pregi e difetti. La scelta del modello migliore dipende da vari fattori, tra cui il numero di variabili, la complessità dei vincoli e l'efficienza del solver. Spesso è necessario implementare e testare più modelli per determinare quello più adatto al problema specifico. ::: tcolorbox - La scelta delle variabili è un passo fondamentale nella modellazione di problemi di programmazione lineare intera. - Variabili numeriche sono adatte a rappresentare quantità, mentre variabili booleane sono più adatte a rappresentare scelte binarie o l'assegnazione di etichette. - Trattare etichette come numeri può introdurre distorsioni e rendere il modello meno efficiente. - La scelta del modello migliore è un processo iterativo che può richiedere la sperimentazione con diversi modelli. ::: **Domande per la prossima lezione:** - Come si scrivono i vincoli per i modelli presentati? - Ad esempio, come si esprime il vincolo che ogni squadra deve giocare contro ogni altra squadra esattamente una volta in casa e una volta fuori casa nel modello del campionato di calcio? - Come si esprime il vincolo che ogni difetto deve essere coperto da almeno un test nel problema dei test di componenti elettroniche? - Quali sono le tecniche per risolvere i modelli di programmazione lineare intera? - Quali algoritmi vengono utilizzati dai solver? - Come funzionano questi algoritmi? - Come si valuta l'efficienza di un modello? - Quali metriche si utilizzano per confrontare diversi modelli? - Come si misura il tempo di esecuzione di un solver?