Optimizarea combinatorie este un domeniu al teoriei optimizării în matematica aplicată asociat cu cercetarea operațională , teoria algoritmilor și teoria complexității computaționale . Optimizarea combinatorie constă în găsirea obiectului optim într-un set finit de obiecte [1] , ceea ce este foarte asemănător cu programarea discretă . Unele surse [2] înțeleg programarea cu numere întregi ca programare discretă , opunând-o optimizării combinatorii care se ocupă de grafice , matroizi și structuri similare. Cu toate acestea, ambii termeni sunt foarte strâns legați și sunt adesea împletite în literatură. Optimizarea combinatorie se reduce adesea la determinarea alocării eficiente a resurselor utilizate pentru găsirea soluției optime.
În multe probleme de optimizare combinatorie , căutarea exhaustivă este nerealistă. Optimizarea combinatorie include probleme de optimizare în care setul de soluții fezabile este discret sau poate fi redus la o mulțime discretă.
Optimizarea combinatorie este utilizată pentru:
Cu toate acestea, aplicarea optimizării combinatorii nu se limitează la aceste exemple.
Există o cantitate mare de literatură despre algoritmi polinomi în timp care lucrează pe unele clase de probleme de programare discretă, iar o parte semnificativă a acestor algoritmi aparține teoriei programării liniare . Câteva exemple de optimizare combinatorie care se încadrează în această zonă sunt problema găsirii celei mai scurte căi și a arborelui cu calea cea mai scurtă , determinarea debitului maxim , găsirea arborilor de întindere , găsirea potrivirilor , probleme cu matroizii .
Problemele de optimizare combinatorie pot fi privite ca căutarea celui mai bun element dintr-o mulțime discretă, astfel încât, în principiu, se pot utiliza orice algoritmi de căutare sau algoritmi metaeuristici . Totuși, algoritmii generali de căutare nu garantează nici o soluție optimă, nici o soluție rapidă (în timp polinomial). Deoarece unele probleme de optimizare discrete sunt NP-complete , cum ar fi problema vânzătorului ambulant, același lucru este de așteptat pentru alte probleme (dacă nu P=NP ).