Programmazione Lineare Intera

NP-arduo

Una PL in cui le variabili devono essere intere, perché contano oggetti indivisibili come camion o persone. La regione ammissibile è X=P∩ZnX=P\cap\mathbb{Z}^n, i punti interi del poliedro P={x∈Rn:Ax=b, x≥0}P=\{x\in\mathbb{R}^n : Ax=b,\ x\ge 0\}.

min⁡ c′xs.a. Ax=bx≥0, x∈Zn\begin{aligned} \min\ & c'x\\ \text{s.a.}\ & Ax=b\\ & x\ge 0,\ x\in\mathbb{Z}^n \end{aligned}

Perché è difficile

L'ottimo intero in genere non è un vertice di PP, quindi il simplesso da solo non basta, e provare tutti i punti interi richiede tempo esponenziale. Piani di taglio e Branch & Bound trovano l'ottimo, ma nel caso peggiore in tempo esponenziale.

Da ricordare

  • X⊆PX\subseteq P: il rilassamento continuo dà un lower bound nel minimo e un upper bound nel massimo.
  • Se l'ottimo del rilassamento è intero è ottimo per la PLI; arrotondarlo quando è frazionario può dare un punto non ammissibile o lontano dall'ottimo.
  • AA unimodulare e bb intero: tutti i vertici sono interi (Teorema 3.2.1) e basta il simplesso.
  • Prima delle slack si eliminano le frazioni, così anche le slack sono intere.

Algoritmi

Fonti: dispensa §3.1-3.4, appunti Lezione 6, §1-4, appunti Lezione 7, appunti Lezione 1, §6.