Kombinatorická optimalizace
Kombinatorická optimalizace je součást (matematické) optimalizace, která hledá optimální řeření z konečné množiny variant určené předepsanými omezeními a použitím diskrétních proměnných. Proto se také často nazývá diskrétní optimalizace.
Původně vznikla pro řešení problémů vznikajících v teorie grafů a vycházela z teoretických poznatků této teorie, později v ní našly uplatnění formulace a algoritmy z lineárního programování. Úzce ouvisí s operačním výzkumem, celočíselným lineárním programováním, ale také souvisí s teoretickou informatikouy, konkrétně s teorií algoritmů a teorií výpočetní složitosti.
Mezi typické problémy patří například problémy hledání minimální kostry, optimální toky v sítích, úloha o batohu, problém ochodního cestujícího (TSP), řezné problémy, plánovací problémy a další. Pro některé z těchto problémů jsou známé rychlé exaktmí algoritmy, jiné problémy naopak mají exponenciální složitost a patří mezi NP-úplné úlohy. Proto se zabývá také aproximačními algoritmy, často označovanými jako heuristiky.