Programare în numere întregi

Programarea în numere întregi (PNÎ; engl. integer programming, IP) — este o ramură a optimizării matematice în care sunt studiate problemele în care unele sau toate variabilele trebuie să ia doar valori întregi.

Cazul particular cel mai studiat este programarea liniară în numere întregi (PLNÎ; engl. integer linear programming, ILP), în care funcția obiectiv și restricțiile sunt liniare. Spre deosebire de programarea liniară, unde variabilele pot lua orice valori reale, cerința de integritate face problemele PNÎ semnificativ mai dificile de rezolvat.

Programarea în numere întregi este utilizată pe scară largă în economie, logistică, planificarea producției și în alte domenii în care variabilele sunt prin natura lor discrete (de exemplu, numărul de unități de produs fabricate sau numărul de angajați).

Definiție și terminologie

Problema generală a programării liniare în numere întregi poate fi formulată astfel:

Se caută vectorul $x$ care:

maximizează (sau minimizează) $c^{T}x$

cu condiițiile:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (toate componentele vectorului $x$ sunt numere întregi)

unde $x$ — vectorul variabilelor, $c$ și $b$ — vectori, iar $A$ — matricea coeficienților.

În funcție de cerințele față de variabile, se disting următoarele tipuri de probleme:

• Programare complet în numere întregi: toate variabilele trebuie să fie întregi.
• Programare mixtă în numere întregi (engl. mixed-integer programming, MIP): doar o parte dintre variabile trebuie să fie întregi.
• Programare booleană (0-1): variabilele iau doar valorile 0 sau 1, ceea ce permite modelarea deciziilor logice de tip „da/nu".

Proprietăți cheie și complexitate

Complexitatea computațională

Problema programării liniare în numere întregi este, în cazul general, NP-dificilă. Aceasta înseamnă că nu există niciun algoritm cunoscut capabil să găsească soluția optimă exactă pentru o problemă arbitrară de PNÎ în timp polinomial. Complexitatea este determinată de natura combinatorică a problemei, deoarece numărul soluțiilor întregi posibile poate crește exponențial odată cu creșterea numărului de variabile.

Relația cu programarea liniară (relaxarea LP)

Pentru orice problemă de PNÎ, se poate formula relaxarea sa liniară — o problemă de programare liniară (PL) în care cerința de integritate a variabilelor este eliminată. Soluția relaxării LP are două proprietăți importante:

1. Poate fi găsită semnificativ mai rapid (în timp polinomial).
2. Valoarea optimă a funcției obiectiv a relaxării LP oferă o estimare (limită superioară pentru problema de maximizare și inferioară pentru minimizare) a valorii optime a problemei inițiale în numere întregi.

Totuși, simpla rotunjire a soluției fracționare a relaxării LP la cele mai apropiate numere întregi nu conduce, în general, la o soluție optimă sau chiar admisibilă a problemei în numere întregi.

Proprietatea de unimodularitate totală

Există o clasă importantă de probleme PLNÎ care se rezolvă la fel de ușor ca și relaxările lor LP. Acestea sunt problemele în care matricea restricțiilor $A$ este total unimodulară (adică determinantul oricărei submatrice pătrate a sa este egal cu 0, +1 sau −1). Dacă matricea $A$ este total unimodulară, iar vectorul $b$ este întreg, atunci toate vârfurile poliedrului soluțiilor admisibile ale relaxării LP vor fi automat întregi. Prin urmare, soluția găsită prin metoda simplex va fi în numere întregi. Exemple de astfel de probleme sunt problema de transport și problema de atribuire.

Metode de rezolvare

Pentru rezolvarea problemelor generale de PNÎ care nu posedă proprietatea de unimodularitate totală, au fost dezvoltate metode exacte bazate pe ideile enumerării implicite.

• Metoda branch and bound (engl. Branch and Bound) — principala metodă exactă, bazată pe descompunerea sistematică a mulțimii soluțiilor admisibile în submulțimi (ramificare) și eliminarea acelor submulțimi care în mod cert nu conțin soluția optimă. Pentru evaluarea perspectivelor submulțimilor se utilizează relaxarea LP.

• Metoda planurilor de tăiere (metoda Gomory; engl. Cutting Plane Method) — o abordare iterativă care adaugă succesiv noi restricții liniare (\"tăieturi\") la problemă. Aceste tăieturi \"elimină\" soluțiile fracționare ale relaxării LP fără a afecta nicio soluție întreagă admisibilă, apropiind treptat domeniul soluțiilor admisibile ale relaxării LP de învelișul convex al soluțiilor întregi.

Solverii moderni utilizează, de regulă, algoritmi hibrid, precum metoda branch and cut (engl. Branch and Cut), care combină avantajele ambelor abordări.

Exemple și domenii de aplicare

Programarea în numere întregi permite modelarea multor probleme clasice de optimizare combinatorică.

• Problema rucsacului: problemă clasică de programare 0-1, în care trebuie să se selecteze un set de obiecte cu valoare totală maximă, fără a depăși restricția privind greutatea totală.
• Problema comis-voiajorului: problema găsirii celui mai scurt traseu care trece printr-un set dat de orașe. Poate fi formulată ca o problemă de programare în numere întregi, în care variabilele indică includerea muchiilor grafului în traseul final.

Datorită flexibilității sale, PNÎ este unul dintre cele mai solicitate instrumente în cercetarea operațională și este aplicată în domenii precum:

• Logistică și managementul lanțului de aprovizionare: optimizarea rutelor de transport, amplasarea depozitelor, gestionarea stocurilor.
• Planificarea producției: elaborarea graficelor de producție, alocarea resurselor, încărcarea echipamentelor.
• Finanțe și economie: formarea portofoliului de investiții, bugetarea capitalului.
• Telecomunicații și energetică: proiectarea rețelelor de comunicații, planificarea funcționării unităților energetice.

Vezi și

• Programare liniară
• Metoda branch and bound