Programmazione intera

Formulazioni della Programmazione Intera

Traduzione e Appunti da Wolsey - Capitolo 1

1.2 Cos’è un Programma Intero?

Supponiamo di avere un programma lineare: ≤ ≥

max{cx : Ax b, x 0}

×

dove A è una matrice m n, c un vettore riga n-dimensionale, b un vettore colonna m-

dimensionale e x un vettore colonna n-dimensionale di variabili o incognite. Aggiungiamo

ora il vincolo che determinate variabili debbano assumere valori interi.

Se alcune variabili, ma non tutte, sono intere, abbiamo un Programma Misto Intero

(Lineare), scritto come: (MIP) max cx + hy ≤

s.t. Ax + Gy b

≥ ≥

x 0, y 0 e intero

× ×

dove A è ancora m n, G è m p, h è un vettore riga p-dimensionale e y è un vettore

colonna p-dimensionale di variabili intere.

Se tutte le variabili sono intere, abbiamo un Programma Intero (Lineare), scritto

come: (IP) max cx ≤

s.t. Ax b

≥

x 0 e intero,

− −

e se tutte le variabili sono limitate a valori 0 1, abbiamo un Programma Intero 0 1

o Binario: (BIP) max cx ≤

s.t. Ax b n

∈ {0,

x 1} .

Formulazioni e Problemi Combinatori

Un altro tipo di problema che desideriamo studiare è il ”problema di ottimizzazione com-

{1,

binatoria”. In questo contesto viene tipicamente dato un insieme finito N = . . . , n},

∈ F

pesi c per ogni j N , e un insieme di sottoinsiemi ammissibili di N . Il problema di

j 1

trovare un sottoinsieme ammissibile di peso minimo è un Problema di Ottimizzazione

Combinatoria: {︄ }︄

∑︂ ∈ F

(COP) min c : S .

j

S⊆N j∈S

Nelle sezioni successive vedremo vari esempi di IP e COP, e vedremo anche che spesso

un COP può essere formulato come un IP o un BIP.

Dato che i programmi interi assomigliano molto ai programmi lineari, non sorprende

che la teoria e la pratica della programmazione lineare siano fondamentali per compren-

dere e risolvere i programmi interi. Tuttavia, la prima idea che viene in mente, ovvero

l’”arrotondamento”, è spesso insufficiente, come mostra il seguente esempio.

Esempio 1.1 Si consideri il programma intero:

max 1.00x + 0.64x

1 2

≤

s.t. 50x + 31x 250

1 2

− ≥ −4

3x 2x

1 2

≥

x , x 0 e interi.

1 2

La soluzione di programmazione lineare (376/193, 950/193) è molto lontana dalla

soluzione intera ottimale (5, 0).

Per i BIP la situazione è spesso ancora peggiore. La soluzione di programmazione

lineare potrebbe essere (0.5, . . . , 0.5), senza fornire alcuna informazione. Inoltre, in ge-

−

nere è molto difficile anche solo rispondere alla domanda se esista una soluzione 0 1

ammissib