Generarea coloanelor - Column generation

Generarea coloanei sau generarea întârziată a coloanelor este un algoritm eficient pentru rezolvarea programelor liniare mari .

Ideea generală este că multe programe liniare sunt prea mari pentru a lua în considerare explicit toate variabilele. Premisa este că majoritatea variabilelor vor fi non-de bază și își asumă o valoare zero în soluția optimă. Din această cauză, numai un subset de variabile trebuie luat în considerare în teorie atunci când se rezolvă problema. Generarea coloanelor valorifică această idee pentru a genera doar variabilele care au potențialul de a îmbunătăți funcția obiectivă - adică pentru a găsi variabile cu cost redus negativ (presupunând fără pierderea generalității că problema este o problemă de minimizare).

Problema rezolvată este împărțită în două probleme: problema master și subproblema. Problema master este problema inițială, având în vedere doar un subset de variabile. Subproblema este o nouă problemă creată pentru a identifica o nouă variabilă. Funcția obiectivă a subproblemei este costul redus al noii variabile în raport cu variabilele duale actuale, iar constrângerile necesită ca variabila să respecte respectarea constrângerilor naturale.

Procesul funcționează după cum urmează. Problema master este rezolvată - din această soluție, putem obține prețuri duale pentru fiecare dintre constrângerile din problema master. Aceste informații sunt apoi utilizate în funcția obiectivă a subproblemei. Subproblema este rezolvată. Dacă valoarea obiectivă a subproblemei este negativă, a fost identificată o variabilă cu cost redus negativ. Această variabilă este apoi adăugată la problema master, iar problema master este rezolvată din nou. Rezolvarea problemei master va genera un nou set de valori duale, iar procesul se repetă până când nu sunt identificate variabile de cost reduse negative. Subproblema returnează o soluție cu cost redus non-negativ, putem concluziona că soluția la problema master este optimă.

În multe cazuri, acest lucru permite rezolvarea unor programe liniare de mari dimensiuni care anterior au fost considerate intratabile. Exemplul clasic al unei probleme în care aceasta este utilizată cu succes este problema stocului tăietor . O tehnică specială în programarea liniară care folosește acest tip de abordare este algoritmul de descompunere Dantzig-Wolfe . În plus, generarea de coloane a fost aplicată multor probleme, cum ar fi programarea echipajului , direcționarea vehiculelor și problema capacităților p-mediane .