Matheuristiky

Matheuristiky jsou třída optimalizačních metod, která kombinuje techniky matematického programování s heuristikami a metaheuristikami. Jejich cílem je využít sílu matematického modelování a strukturovaného vyhledávání pro problémy, které jsou příliš velké nebo složité pro čisté celočíselné programování, a přitom zachovat kvalitu řešení a podporu pro odhad mezních hodnot.

Mezi typické přístupy patří kombinace řešení podproblémů pomocí matematického programování (např. MILP/MIQP) s heuristickým prohledáváním prostoru. Často se využívá relaxací a reoptimace, řezání (cutting planes), generování sloupců (column generation) a Lagrangeova relaxace k získání dobrých mezí a vodících signálů pro vyhledávání. Matheuristiky také často vytvářejí sousedství řešení či postupy iterativní zlepšování na základě řešení menších MP problémů, která lze řešit velmi rychle. Hybridní metody kombinují silné stránky modelování s rychlostí heuristik.

Používají se v široké škále problémů z operativního výzkumu a průmyslu, jako jsou dopravní a logistické problémy (např. Vehicle Routing Problem), plánování výroby a rozvrhování, alokace zdrojů, návrh sítí či problémy v energetice a telekomunikacích. Příkladem může být řešení VRP, kdy se velké problémové instance řeší kombinací MILP modelů a lokálních vyhledávacích kroků nebo kolonek generovaných subproblémy.

Matheuristiky představují kompromis mezi tvrdými metodami a flexibilními heuristikami: často nabízejí kvalitní řešení a použitelné horní/dolní odhady, ale jejich návrh a ladění bývá tematicky náročné a závislé na konkrétním problému.