Fondamenti di Ricerca Operativa: Problemi, Istanze e Funzioni Obiettivo

Author

Your Name

Published

January 30, 2025

Introduction

In questa lezione, introduciamo alcuni concetti fondamentali della Ricerca Operativa, in particolare la distinzione tra problema e istanza di un problema. Esploreremo due tipi principali di problemi: problemi di ottimizzazione e problemi di decisione. Per i problemi di ottimizzazione, definiremo formalmente la struttura di un problema, inclusi l’insieme delle istanze, le soluzioni ammissibili e la funzione obiettivo. Infine, illustreremo questi concetti con esempi concreti come il problema del commesso viaggiatore (TSP), il bin packing e il problema della clique pesata.

Problemi e Istanze

Nella Ricerca Operativa, è cruciale comprendere la differenza tra un problema e un’istanza di un problema.

Un problema è definito in modo astratto da un insieme di dati che ne rappresentano l’input e da una descrizione di come è fatta una soluzione al problema. In altre parole, un problema descrive in termini generali le caratteristiche dell’input e delle soluzioni ammissibili, senza specificare i valori numerici concreti.

Un’istanza di un problema si ottiene specificando i valori concreti di tutti i parametri del problema. Un’istanza rappresenta quindi un caso specifico del problema generale, con dati numerici ben definiti.

Consideriamo il problema del commesso viaggiatore (TSP). Il problema, in generale, consiste nel trovare il percorso più breve che un commesso viaggiatore deve compiere per visitare un insieme di città e tornare al punto di partenza. Un’istanza del TSP è definita da un numero specifico di città e dalle distanze tra ogni coppia di città. Ad esempio, un’istanza con quattro città potrebbe avere le seguenti distanze:

Città 1 - Città 2: 5 km
Città 1 - Città 3: 10 km
Città 1 - Città 4: 8 km
Città 2 - Città 3: 6 km
Città 2 - Città 4: 9 km
Città 3 - Città 4: 7 km

I problemi nella Ricerca Operativa si dividono in due categorie principali:

Problemi di Ottimizzazione: A ogni soluzione è associato un costo (o valore numerico). L’obiettivo è trovare la soluzione di valore ottimo (minimo o massimo a seconda dei casi). Ad esempio, nel TSP, il costo di una soluzione è la lunghezza totale del percorso, e l’obiettivo è trovare il percorso di lunghezza minima.
Problemi di Decisione: Non c’è un costo associato alle soluzioni. L’obiettivo è verificare l’esistenza di almeno una soluzione che soddisfi determinati requisiti. Fondamentalmente, si tratta di problemi di tipo "sì/no". Ad esempio, un problema di decisione correlato al TSP potrebbe essere: "Esiste un percorso che visita tutte le città e ha una lunghezza totale inferiore a 25 km?".

Problemi di Ottimizzazione

Un problema di ottimizzazione $\pi$ è definito da una tripla:

Un insieme $I_\pi$ di istanze.
Per ogni istanza $i \in I_\pi$, un insieme $S_i$ di soluzioni ammissibili.
Una funzione obiettivo $f_\pi: \{(i, x) | i \in I_\pi, x \in S_i\} \to \mathbb{R}$ che associa a ogni coppia (istanza, soluzione) un valore reale.

La funzione obiettivo $f_\pi$ associa un valore numerico a ogni possibile soluzione $x$ di un’istanza $i$ del problema $\pi$. È importante notare che il valore di una soluzione dipende non solo dalla soluzione stessa, ma anche dai dati specifici dell’istanza.

Obiettivo: Dato un problema di ottimizzazione $\pi$ e un’istanza $i \in I_\pi$, trovare una soluzione $x^* \in S_i$ tale che:

Per problemi di minimizzazione: $f_\pi(i, x^*) \le f_\pi(i, x), \forall x \in S_i$
Per problemi di massimizzazione: $f_\pi(i, x^*) \ge f_\pi(i, x), \forall x \in S_i$

Una soluzione $x^*$ che soddisfa la condizione sopra è detta soluzione ottima.

Un problema di ottimizzazione può avere più soluzioni ottime, anche infinite. In molti casi, è sufficiente trovare una qualsiasi soluzione ottima, poiché tutte le soluzioni ottime hanno lo stesso valore della funzione obiettivo.

Consideriamo di nuovo il TSP. Un’istanza $i$ del TSP è definita da un grafo completo con pesi sugli archi. Le soluzioni ammissibili $S_i$ sono tutti i possibili circuiti hamiltoniani in quel grafo. La funzione obiettivo $f_\pi(i, x)$ calcola la lunghezza totale del circuito $x$ nell’istanza $i$. L’obiettivo è trovare il circuito hamiltoniano di lunghezza minima.

Problemi di Decisione

Un problema di decisione $\pi$ è definito da:

Un insieme $I_\pi$ di istanze.
Un sottoinsieme $Y_\pi \subseteq I_\pi$ di istanze "sì".

Le istanze "sì" ($Y_\pi$) sono quelle istanze per le quali la risposta al problema di decisione è affermativa. In altre parole, sono le istanze che soddisfano una certa proprietà o condizione specifica del problema.

Obiettivo: Dato un problema di decisione $\pi$ e un’istanza $i \in I_\pi$, determinare se $i \in Y_\pi$, ovvero stabilire se l’istanza $i$ appartiene all’insieme delle istanze "sì".

Consideriamo il problema del Circuito Hamiltoniano. Le istanze di questo problema sono grafi. Le istanze "sì" sono quei grafi che contengono un circuito hamiltoniano. Dato un grafo specifico, il problema decisionale consiste nel determinare se questo grafo contiene un circuito hamiltoniano oppure no.

Esempi

Problemi di Ottimizzazione

The Traveling Salesman Problem is a classic optimization problem.

Nome: TSP
Input: Un grafo completo orientato $G = (V, A)$ con $n = |V|$ nodi e costi $c_{ij} \in \mathbb{R}$ associati agli archi $(i, j) \in A$.
Goal: Trovare un circuito hamiltoniano di costo minimo, ovvero una permutazione $(v_1, v_2, \dots, v_n)$ dei nodi tale che $\sum_{i=1}^{n-1} c_{v_i v_{i+1}} + c_{v_n v_1}$ sia minimo.

Questa figura rappresenta un’istanza del TSP con 4 nodi. I numeri sugli archi rappresentano i costi $c_{ij}$.

The Bin Packing problem aims to minimize the number of bins used.

Nome: Bin Packing
Input: Un insieme di $n$ numeri $d_1, d_2, \dots, d_n$ con $0 < d_i < 1$ per $i = 1, \dots, n$, che rappresentano le dimensioni di $n$ oggetti.
Goal: Trovare il minimo numero di contenitori (bin) di capacità 1 in cui è possibile inserire tutti gli oggetti, rispettando il vincolo che la somma delle dimensioni degli oggetti in ogni contenitore non superi 1.

The Weighted Clique problem seeks the clique with the maximum total weight.

Nome: Clique Pesata
Input: Un grafo non orientato $G = (V, E)$ con pesi $w_i \ge 0$ associati ai nodi $i \in V$.
Goal: Trovare una clique (un sottografo completo) di peso massimo, ovvero un insieme di nodi $C \subseteq V$ tale che ogni coppia di nodi in $C$ sia adiacente e $\sum_{i \in C} w_i$ sia massimo.

Problemi di Decisione

The 3-SAT problem asks whether a satisfying assignment exists.

Input: Un insieme di clausole $C_1, C_2, \dots, C_m$, dove ogni clausola $C_i$ è un OR di tre letterali (una variabile booleana $x_j$ o la sua negazione $\neg x_j$).
Istanze "sì": Le istanze per cui esiste un assegnamento di verità alle variabili booleane $x_1, x_2, \dots, x_n$ che rende vere tutte le clausole.

Un’istanza del problema 3-SAT potrebbe essere la seguente:

$C_1 = x_1 \vee \neg x_2 \vee x_3$
$C_2 = \neg x_1 \vee x_2 \vee x_4$
$C_3 = x_2 \vee \neg x_3 \vee \neg x_4$

In questo caso, un possibile assegnamento di verità che rende vere tutte le clausole è: $x_1 = \text{vero}$, $x_2 = \text{vero}$, $x_3 = \text{falso}$, $x_4 = \text{falso}$. Quindi, questa istanza è un’istanza "sì".

The Hamiltonian Cycle problem asks if a Hamiltonian cycle exists in a graph.

Input: Un grafo $G = (V, E)$.
Istanze "sì": I grafi che contengono un circuito hamiltoniano (un circuito che visita ogni nodo esattamente una volta).

Conclusion

In questa lezione, abbiamo introdotto i concetti fondamentali di problema e istanza nella Ricerca Operativa, distinguendo tra problemi di ottimizzazione e problemi di decisione. Abbiamo definito formalmente la struttura di un problema di ottimizzazione ([def:problema_ott]), con particolare attenzione all’insieme delle istanze, alle soluzioni ammissibili e alla funzione obiettivo. Abbiamo inoltre illustrato questi concetti con esempi concreti come il TSP ([ex:tsp]), il bin packing ([ex:bin_packing]) e il problema della clique pesata ([ex:clique_pesata]), e con problemi di decisione come 3-SAT ([ex:3sat]) e il circuito hamiltoniano ([ex:circuito_hamiltoniano]).

Un problema è una descrizione astratta ([def:problema]), mentre un’istanza è una realizzazione specifica del problema ([def:istanza]).
I problemi di ottimizzazione cercano una soluzione che minimizzi o massimizzi una funzione obiettivo ([def:sol_ottima]).
I problemi di decisione verificano l’esistenza di una soluzione che soddisfi determinati criteri ([def:problema_decisione]).
La funzione obiettivo associa un valore a una soluzione, ma dipende anche dall’istanza del problema.

Domande per la prossima lezione:

Come si può misurare la "difficoltà" di un problema?
Cosa significa che un problema è NP-hard o NP-completo?
Quali sono le tecniche algoritmiche per affrontare problemi di ottimizzazione difficili?

--- title: "Fondamenti di Ricerca Operativa: Problemi, Istanze e Funzioni Obiettivo" 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, introduciamo alcuni concetti fondamentali della Ricerca Operativa, in particolare la distinzione tra **problema** e **istanza** di un problema. Esploreremo due tipi principali di problemi: problemi di **ottimizzazione** e problemi di **decisione**. Per i problemi di ottimizzazione, definiremo formalmente la struttura di un problema, inclusi l'insieme delle istanze, le soluzioni ammissibili e la funzione obiettivo. Infine, illustreremo questi concetti con esempi concreti come il problema del commesso viaggiatore (TSP), il *bin packing* e il problema della clique pesata. # Problemi e Istanze Nella Ricerca Operativa, è cruciale comprendere la differenza tra un problema e un'istanza di un problema. ::: tcolorbox Un problema è definito in modo astratto da un insieme di dati che ne rappresentano l'input e da una descrizione di come è fatta una soluzione al problema. In altre parole, un problema descrive in termini generali le caratteristiche dell'input e delle soluzioni ammissibili, senza specificare i valori numerici concreti. ::: ::: tcolorbox Un'istanza di un problema si ottiene specificando i valori concreti di tutti i parametri del problema. Un'istanza rappresenta quindi un caso specifico del problema generale, con dati numerici ben definiti. ::: ::: tcolorbox Consideriamo il problema del commesso viaggiatore (TSP). Il problema, in generale, consiste nel trovare il percorso più breve che un commesso viaggiatore deve compiere per visitare un insieme di città e tornare al punto di partenza. Un'istanza del TSP è definita da un numero specifico di città e dalle distanze tra ogni coppia di città. Ad esempio, un'istanza con quattro città potrebbe avere le seguenti distanze: - Città 1 - Città 2: 5 km - Città 1 - Città 3: 10 km - Città 1 - Città 4: 8 km - Città 2 - Città 3: 6 km - Città 2 - Città 4: 9 km - Città 3 - Città 4: 7 km ::: I problemi nella Ricerca Operativa si dividono in due categorie principali: - **Problemi di Ottimizzazione**: A ogni soluzione è associato un costo (o valore numerico). L'obiettivo è trovare la soluzione di valore ottimo (minimo o massimo a seconda dei casi). Ad esempio, nel TSP, il costo di una soluzione è la lunghezza totale del percorso, e l'obiettivo è trovare il percorso di lunghezza minima. - **Problemi di Decisione**: Non c'è un costo associato alle soluzioni. L'obiettivo è verificare l'esistenza di almeno una soluzione che soddisfi determinati requisiti. Fondamentalmente, si tratta di problemi di tipo \"sì/no\". Ad esempio, un problema di decisione correlato al TSP potrebbe essere: \"Esiste un percorso che visita tutte le città e ha una lunghezza totale inferiore a 25 km?\". # Problemi di Ottimizzazione ::: tcolorbox Un problema di ottimizzazione $\pi$ è definito da una tripla: 1. Un insieme $I_\pi$ di istanze. 2. Per ogni istanza $i \in I_\pi$, un insieme $S_i$ di soluzioni ammissibili. 3. Una funzione obiettivo $f_\pi: \{(i, x) | i \in I_\pi, x \in S_i\} \to \mathbb{R}$ che associa a ogni coppia (istanza, soluzione) un valore reale. ::: ::: tcolorbox La funzione obiettivo $f_\pi$ associa un valore numerico a ogni possibile soluzione $x$ di un'istanza $i$ del problema $\pi$. È importante notare che il valore di una soluzione dipende non solo dalla soluzione stessa, ma anche dai dati specifici dell'istanza. ::: **Obiettivo**: Dato un problema di ottimizzazione $\pi$ e un'istanza $i \in I_\pi$, trovare una soluzione $x^* \in S_i$ tale che: - Per problemi di minimizzazione: $f_\pi(i, x^*) \le f_\pi(i, x), \forall x \in S_i$ - Per problemi di massimizzazione: $f_\pi(i, x^*) \ge f_\pi(i, x), \forall x \in S_i$ ::: tcolorbox Una soluzione $x^*$ che soddisfa la condizione sopra è detta soluzione ottima. ::: ::: tcolorbox Un problema di ottimizzazione può avere più soluzioni ottime, anche infinite. In molti casi, è sufficiente trovare una qualsiasi soluzione ottima, poiché tutte le soluzioni ottime hanno lo stesso valore della funzione obiettivo. ::: ::: tcolorbox Consideriamo di nuovo il TSP. Un'istanza $i$ del TSP è definita da un grafo completo con pesi sugli archi. Le soluzioni ammissibili $S_i$ sono tutti i possibili circuiti hamiltoniani in quel grafo. La funzione obiettivo $f_\pi(i, x)$ calcola la lunghezza totale del circuito $x$ nell'istanza $i$. L'obiettivo è trovare il circuito hamiltoniano di lunghezza minima. ::: # Problemi di Decisione ::: tcolorbox Un problema di decisione $\pi$ è definito da: 1. Un insieme $I_\pi$ di istanze. 2. Un sottoinsieme $Y_\pi \subseteq I_\pi$ di istanze \"sì\". ::: ::: tcolorbox Le istanze \"sì\" ($Y_\pi$) sono quelle istanze per le quali la risposta al problema di decisione è affermativa. In altre parole, sono le istanze che soddisfano una certa proprietà o condizione specifica del problema. ::: **Obiettivo**: Dato un problema di decisione $\pi$ e un'istanza $i \in I_\pi$, determinare se $i \in Y_\pi$, ovvero stabilire se l'istanza $i$ appartiene all'insieme delle istanze \"sì\". ::: tcolorbox Consideriamo il problema del Circuito Hamiltoniano. Le istanze di questo problema sono grafi. Le istanze \"sì\" sono quei grafi che contengono un circuito hamiltoniano. Dato un grafo specifico, il problema decisionale consiste nel determinare se questo grafo contiene un circuito hamiltoniano oppure no. ::: # Esempi ## Problemi di Ottimizzazione ::::: tcolorbox The Traveling Salesman Problem is a classic optimization problem. - **Nome**: TSP - **Input**: Un grafo completo orientato $G = (V, A)$ con $n = |V|$ nodi e costi $c_{ij} \in \mathbb{R}$ associati agli archi $(i, j) \in A$. - **Goal**: Trovare un circuito hamiltoniano di costo minimo, ovvero una permutazione $(v_1, v_2, \dots, v_n)$ dei nodi tale che $\sum_{i=1}^{n-1} c_{v_i v_{i+1}} + c_{v_n v_1}$ sia minimo. :::: tcolorbox ::: center ::: Questa figura rappresenta un'istanza del TSP con 4 nodi. I numeri sugli archi rappresentano i costi $c_{ij}$. :::: ::::: ::: tcolorbox The Bin Packing problem aims to minimize the number of bins used. - **Nome**: Bin Packing - **Input**: Un insieme di $n$ numeri $d_1, d_2, \dots, d_n$ con $0 < d_i < 1$ per $i = 1, \dots, n$, che rappresentano le dimensioni di $n$ oggetti. - **Goal**: Trovare il minimo numero di contenitori (bin) di capacità 1 in cui è possibile inserire tutti gli oggetti, rispettando il vincolo che la somma delle dimensioni degli oggetti in ogni contenitore non superi 1. ::: ::: tcolorbox The Weighted Clique problem seeks the clique with the maximum total weight. - **Nome**: Clique Pesata - **Input**: Un grafo non orientato $G = (V, E)$ con pesi $w_i \ge 0$ associati ai nodi $i \in V$. - **Goal**: Trovare una clique (un sottografo completo) di peso massimo, ovvero un insieme di nodi $C \subseteq V$ tale che ogni coppia di nodi in $C$ sia adiacente e $\sum_{i \in C} w_i$ sia massimo. ::: ## Problemi di Decisione :::: tcolorbox The 3-SAT problem asks whether a satisfying assignment exists. - **Input**: Un insieme di clausole $C_1, C_2, \dots, C_m$, dove ogni clausola $C_i$ è un OR di tre letterali (una variabile booleana $x_j$ o la sua negazione $\neg x_j$). - **Istanze \"sì\"**: Le istanze per cui esiste un assegnamento di verità alle variabili booleane $x_1, x_2, \dots, x_n$ che rende vere tutte le clausole. ::: tcolorbox Un'istanza del problema 3-SAT potrebbe essere la seguente: - $C_1 = x_1 \vee \neg x_2 \vee x_3$ - $C_2 = \neg x_1 \vee x_2 \vee x_4$ - $C_3 = x_2 \vee \neg x_3 \vee \neg x_4$ In questo caso, un possibile assegnamento di verità che rende vere tutte le clausole è: $x_1 = \text{vero}$, $x_2 = \text{vero}$, $x_3 = \text{falso}$, $x_4 = \text{falso}$. Quindi, questa istanza è un'istanza \"sì\". ::: :::: ::: tcolorbox The Hamiltonian Cycle problem asks if a Hamiltonian cycle exists in a graph. - **Input**: Un grafo $G = (V, E)$. - **Istanze \"sì\"**: I grafi che contengono un circuito hamiltoniano (un circuito che visita ogni nodo esattamente una volta). ::: # Conclusion In questa lezione, abbiamo introdotto i concetti fondamentali di problema e istanza nella Ricerca Operativa, distinguendo tra problemi di ottimizzazione e problemi di decisione. Abbiamo definito formalmente la struttura di un problema di ottimizzazione ([\[def:problema_ott\]](#def:problema_ott){reference-type="ref+Label" reference="def:problema_ott"}), con particolare attenzione all'insieme delle istanze, alle soluzioni ammissibili e alla funzione obiettivo. Abbiamo inoltre illustrato questi concetti con esempi concreti come il TSP ([\[ex:tsp\]](#ex:tsp){reference-type="ref+Label" reference="ex:tsp"}), il bin packing ([\[ex:bin_packing\]](#ex:bin_packing){reference-type="ref+Label" reference="ex:bin_packing"}) e il problema della clique pesata ([\[ex:clique_pesata\]](#ex:clique_pesata){reference-type="ref+Label" reference="ex:clique_pesata"}), e con problemi di decisione come 3-SAT ([\[ex:3sat\]](#ex:3sat){reference-type="ref+Label" reference="ex:3sat"}) e il circuito hamiltoniano ([\[ex:circuito_hamiltoniano\]](#ex:circuito_hamiltoniano){reference-type="ref+Label" reference="ex:circuito_hamiltoniano"}). ::: tcolorbox - Un problema è una descrizione astratta ([\[def:problema\]](#def:problema){reference-type="ref+Label" reference="def:problema"}), mentre un'istanza è una realizzazione specifica del problema ([\[def:istanza\]](#def:istanza){reference-type="ref+Label" reference="def:istanza"}). - I problemi di ottimizzazione cercano una soluzione che minimizzi o massimizzi una funzione obiettivo ([\[def:sol_ottima\]](#def:sol_ottima){reference-type="ref+Label" reference="def:sol_ottima"}). - I problemi di decisione verificano l'esistenza di una soluzione che soddisfi determinati criteri ([\[def:problema_decisione\]](#def:problema_decisione){reference-type="ref+Label" reference="def:problema_decisione"}). - La funzione obiettivo associa un valore a una soluzione, ma dipende anche dall'istanza del problema. ::: **Domande per la prossima lezione**: - Come si può misurare la \"difficoltà\" di un problema? - Cosa significa che un problema è NP-hard o NP-completo? - Quali sono le tecniche algoritmiche per affrontare problemi di ottimizzazione difficili?