Kombinatorisk optimering er et felt inden for optimeringsteori i anvendt matematik forbundet med operationsforskning , algoritmeteori og beregningsmæssig kompleksitetsteori . Kombinatorisk optimering består i at finde det optimale objekt i et begrænset sæt af objekter [1] , hvilket minder meget om diskret programmering . Nogle kilder [2] forstår diskret programmering som heltalsprogrammering , der modsætter sig kombinatorisk optimering, der beskæftiger sig med grafer , matroiderog lignende strukturer. Begge udtryk er dog meget nært beslægtede og er ofte sammenflettet i litteraturen. Kombinatorisk optimering handler ofte om at bestemme den effektive allokering af ressourcer, der bruges til at finde den optimale løsning.
I mange kombinatoriske optimeringsproblemer er udtømmende søgning urealistisk. Kombinatorisk optimering omfatter optimeringsproblemer, hvor sættet af mulige løsninger er diskrete eller kan reduceres til et diskret sæt.
Kombinatorisk optimering bruges til:
Anvendelsen af kombinatorisk optimering er dog ikke begrænset til disse eksempler.
Der er en stor mængde litteratur om tidspolynomiske algoritmer, der virker på nogle klasser af diskrete programmeringsproblemer, og en betydelig del af disse algoritmer tilhører teorien om lineær programmering . Nogle eksempler på kombinatorisk optimering, der falder inden for dette område, er problemet med at finde den korteste vej og den korteste vej træ , bestemme det maksimale flow , finde spændende træer , finde matchninger , problemer med matroider .
Kombinatoriske optimeringsproblemer kan ses som søgning efter det bedste element i et diskret sæt, så i princippet kan alle søgealgoritmer eller metaheuristiske algoritmer bruges . Generelle søgealgoritmer garanterer dog hverken en optimal løsning eller en hurtig løsning (i polynomisk tid). Da nogle diskrete optimeringsproblemer er NP-komplette , ligesom problemet med rejsende sælger, kan det samme forventes for andre problemer (hvis ikke P=NP ).