A kombinatorikus optimalizálás az optimalizálási elmélet egyik területe az alkalmazott matematikában , amely a műveletek kutatásához , az algoritmuselmélethez és a számítási komplexitás elméletéhez kapcsolódik . A kombinatorikus optimalizálás abból áll, hogy véges objektumok halmazában találjuk meg az optimális objektumot [1] , ami nagyon hasonlít a diszkrét programozáshoz . Egyes források [2] az egészszámú programozást diszkrét programozásként értelmezik , szemben a gráfokkal , matroidokkal és hasonló struktúrákkal foglalkozó kombinatorikus optimalizálással . Mindazonáltal mindkét kifejezés nagyon szorosan összefügg, és gyakran összefonódik a szakirodalomban. A kombinatorikus optimalizálás gyakran az optimális megoldás megtalálásához használt erőforrások hatékony allokációjának meghatározásán múlik.
Számos kombinatorikus optimalizálási probléma esetén a kimerítő keresés irreális. A kombinatorikus optimalizálás olyan optimalizálási problémákat foglal magában, amelyekben a megvalósítható megoldások halmaza diszkrét vagy diszkrét halmazzá redukálható.
A kombinatorikus optimalizálást a következőkre használják:
A kombinatorikus optimalizálás alkalmazása azonban nem korlátozódik ezekre a példákra.
Nagy mennyiségű irodalom létezik az időpolinomiális algoritmusokról, amelyek a diszkrét programozási problémák bizonyos osztályaira dolgoznak, és ezen algoritmusok jelentős része a lineáris programozás elméletéhez tartozik . Néhány példa a kombinatorikus optimalizálásra, amelyek ebbe a területbe tartoznak: a legrövidebb út és a legrövidebb útfa megtalálása, a maximális áramlás meghatározása , a feszítőfák keresése, az egyezések keresése, a matroidokkal kapcsolatos problémák .
A kombinatorikus optimalizálási feladatok úgy is felfoghatók, mint a legjobb elem keresése valamilyen diszkrét halmazban, így elvileg bármilyen keresési algoritmus vagy metaheurisztikus algoritmus használható . Az általános keresési algoritmusok azonban nem garantálják sem az optimális megoldást, sem a gyors megoldást (polinomiális időben). Mivel néhány diszkrét optimalizálási probléma NP-teljes , mint például az utazó eladó probléma, ugyanez várható más problémáknál is (ha nem P=NP ).