Problema di ottimizzazione

In matematica e in informatica, un problema di ottimizzazione è il problema di trovare la migliore soluzione fra tutte le soluzioni fattibili. I problemi di ottimizzazione possono essere divisi in due categorie a seconda se le variabili sono continue o discrete. Un problema di ottimizzazione con variabili discrete è noto come un problema di ottimizzazione combinatoria. In un problema di ottimizzazione combinatoria, stiamo cercando un oggetto come un intero, una permutazione o un grafo proveniente da un insieme finito (o possibilmente infinito numerabile).

Problema di ottimizzazione

La forma normale di un problema di ottimizzazione (continua) è^[1]

{\begin{aligned}&{\underset {x}{\operatorname {min} }}&&f(x)\\&\quad &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{i}(x)=0,\quad i=1,\dots ,p\end{aligned}}

dove

$f(x):\mathbb {R} ^{n}\to \mathbb {R}$ è la funzione obiettivo da minimizzare sulla variabile $x$ ,
$g_{i}(x)\leq 0$ sono chiamati vincoli di disuguaglianza,
$h_{i}(x)=0$ sono chiamati vincoli di uguaglianza.

Per convenzione, la forma normale definisce un problema di minimizzazione. Un problema di massimizzazione può essere trattato negando la funzione obiettivo.

Problema di ottimizzazione combinatoria

Formalmente, un problema di ottimizzazione combinatoria $A$ è una quadrupla $(I,f,m,g)$ , dove

$I$ è un insieme di istanze;
data un'istanza $x\in I$ , $f(x)$ è l'insieme delle soluzioni fattibili;
data un'istanza $x$ e una soluzione fattibile $y$ di $x$ , $m(x,y)$ denota la misura di $y$ , che è di solito un reale positivo.
$g$ è la funzione di scopo, ed è o $\min$ o $\max$ .

Lo scopo è allora trovare per qualche istanza $x$ una soluzione ottimale, cioè una soluzione fattibile $y$ con

m(x,y)=g\{m(x,y')\mid y'\in f(x)\}.

Per ciascun problema di ottimizzazione combinatoria, c'è un problema decisionale corrispondente che chiede se c'è una soluzione fattibile per qualche particolare misura $m_{0}$ . Ad esempio, se c'è un grafo $G$ che contiene i vertici $u$ e $v$ , un problema di ottimizzazione potrebbe essere "trovare un cammino da $u$ a $v$ che usa il minor numero di spigoli". Questo problema potrebbe avere una risposta di, diciamo, 4. Un problema decisionale sarebbe "c'è un cammino da $u$ a $v$ che usa 10 o un numero minore di spigoli?" A questo problema si può rispondere con un semplice "sì" o "no".

Nel campo degli algoritmi di approssimazione, gli algoritmi sono progettati per trovare soluzioni quasi-ottimali a problemi difficili. L'abituale versione decisionale è allora una definizione inadeguata del problema poiché specifica soltanto soluzioni accettabili. Anche se potessimo introdurre problemi decisionali idonei, il problema si caratterizza in modo più naturale come un problema di ottimizzazione.^[2]

Problema di ottimizzazione NP

Un problema di ottimizzazione NP (NP-optimization problem, NPO) è un problema di ottimizzazione combinatoria con alcune condizioni aggiuntive.^[3] Si noti che i polinomi citati sotto sono funzioni della dimensione delle entrate delle rispettive funzioni, non della dimensione di qualche insieme implicito di istanze delle entrate. Le condizioni aggiuntive sono le seguenti:

la dimensione di ogni soluzione fattibile $\scriptstyle y\in f(x)$ è limitata polinomialmente nella dimensione dell'istanza data $x$ ,
i linguaggi $\scriptstyle \{\,x\,\mid \,x\in I\,\}$ e $\scriptstyle \{\,(x,y)\,\mid \,y\in f(x)\,\}$ possono essere riconosciuti in tempo polinomiale, e
m è computabile in tempo polinomiale.

Ciò implica che il problema decisionale corrispondente è in NP. In informatica, i problemi di ottimizzazione interessanti hanno di solito le suddette proprietà e sono perciò problemi NPO. Un problema è chiamato inoltre problema di ottimizzazione P (P-optimization, PO), se esiste un algoritmo che trova soluzioni ottimali in tempo polinomiale. Spesso, quando si tratta della classe NPO, si è interessati a problemi di ottimizzazione per i quali le versioni decisionali sono NP-complete. Si noti che le relazioni di difficoltà si pongono sempre rispetto a una qualche riduzione. A causa del collegamento tra gli algoritmi di approssimazione e i problemi di ottimizzazione computazionale, le riduzioni che preservano l'approssimazione sotto qualche aspetto per questo argomento sono preferite alle abituali riduzioni di Turing e di Karp. Un esempio di tale riduzione sarebbe la riduzione L. Per questa ragione, i problemi di ottimizzazione con versioni decisionali NP-complete non sono necessariamente chiamati NPO-completi.^[4]

NPO è divisa nelle seguenti sottoclassi secondo la loro approssimabilità:^[3]

NPO(I): è uguale a FPTAS. Contiene il problema dello zaino.
NPO(II): è uguale a PTAS. Contiene il problema della schedulazione del tempo di produzione.
NPO(III): la classe dei problemi NPO che hanno algoritmi in tempo polinomiale che computano soluzioni con un costo al massimo c volte il costo ottimale (per i problemi di minimizzazione) o con un costo almeno $1/c$ del costo ottimale (per i problemi di massimizzazione). Nel libro di Hromkovič, esclusi da questa classe sono tutti problemi NPO(II) tranne se P=NP. Senza l'esclusione, questa classe è uguale ad APX. Essa contiene MAX-SAT e il TSP metrico.
NPO(IV): la classe dei problemi NPO con algoritmi in tempo polinomiale che approssimano la soluzione ottimale in base a un rapporto che è polinomiale in un logaritmo della dimensione dell'entrata. Nel libro di Hromkovic tutti i problemi NPO(III) sono esclusi da questa classe a meno che P=NP. Contiene il problema della copertura degli insiemi.
NPO(V): la classe dei problemi NPO con algoritmi in tempo polinomiale che approssimano la soluzione ottimale in base a un rapporto limitato da una qualche funzione su n. Nel libro di Hromkovic tutti i problemi NPO(IV) sono esclusi da questa classe a meno che P=NP. Contiene i problemi di TSP e della massima cricca.

Un'altra classe d'interesse è NPOPB, NPO con funzioni di costo polinomialmente limitate (NPO with polynomially bounded cost functions). I problemi con questa condizione hanno molte proprietà desiderabili.

Note

^ Stephen P. Boyd e Lieven Vandenberghe, Convex Optimization (PDF), Cambridge University Press, 2004, p. 129, ISBN 978-0-521-83378-3.
^ (EN) Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M., Complexity and Approximation, Springer, 1999, ISBN 978-3-540-65431-5. URL consultato il 28 agosto 2014.
^ ^a ^b Juraj Hromkovic, Algorithmics for Hard Problems, Texts in Theoretical Computer Science, 2ª ed., Springer, 2002, ISBN 978-3-540-44134-2.
^ Viggo Kann, On the Approximability of NP-complete Optimization Problems, Royal Institute of Technology, Svezia, 1992, ISBN 91-7170-082-X.