Unimodulárne matice v operačnom výskume - Liška, Andrej (2020)
Úloha celočíselného programovania je NP obtiažny problém (NP-hard), neexistuje teda polynomiálny algoritmus pre riešenie tejto úlohy. Pritom väčšina optimalizačných úloh operačného výskumu riešiacich úlohy ekonomickej praxe vedú na úlohy celočíselného programovania. Pokiaľ ale úloha celočíselného programovania je taká, že obmedzujúce podmienky v tvare rovníc a nerovností obsahujú unimodolárnu maticu, je možné úlohu celočíselného programovania riešiť polynomiálne, metódami lineárneho programovania. Charakteristické problémy obsahujúce totálne unimodulárnu maticu sú napríklad dopravný problém, priraďovací problém, alebo problém maximálneho toku. Existujú aj problémy, ktoré je možné relaxovať na úlohu s unimodulárnou maticou a pomocou tejto relaxácie nájsť suboptimálne riešenie alebo zefektívniť metódu riešení celočíselnej úlohy, napríklad metódu vetvenia a hraníc (branch and bound). Do tejto skupiny spadá napríklad problém obchodného cestujúceho. Z bežného života je potom možné prispieť k riešeniu veľkého množstva reálnych problémov.