Celočíselné programování

Celočíselné programování (CP; angl. integer programming, IP) — je odvětví matematické optimalizace, které se zabývá úlohami, kde některé nebo všechny proměnné musí nabývat pouze celočíselných hodnot.

Nejprozkoumanějším speciálním případem je celočíselné lineární programování (CLP; angl. integer linear programming, ILP), kde účelová funkce i omezení jsou lineární. Na rozdíl od lineárního programování, kde proměnné mohou nabývat libovolných reálných hodnot, požadavek celočíselnosti činí úlohy CP výrazně obtížněji řešitelnými.

Celočíselné programování nachází široké uplatnění v ekonomice, logistice, plánování výroby a dalších oblastech, kde jsou proměnné ze své podstaty diskrétní (například počet vyrobených jednotek produkce nebo počet pracovníků).

Definice a terminologie

Obecná úloha celočíselného lineárního programování může být zapsána následovně:

Najít vektor $x$, který:

maximalizuje (nebo minimalizuje) $c^{T}x$

při podmínkách:

$Ax\le b$

$x\ge 0$

$x\in {\mathbb{\mathbb{Z}}}^n$ (všechny složky vektoru $x$ jsou celá čísla)

kde $x$ — vektor proměnných, $c$ a $b$ — vektory a $A$ — matice koeficientů.

V závislosti na požadavcích na proměnné se rozlišují následující typy úloh:

• Čistě celočíselné programování: všechny proměnné musí být celé.
• Smíšeně celočíselné programování (angl. mixed-integer programming, MIP): pouze část proměnných musí být celočíselná.
• Booleovské (0-1) programování: proměnné nabývají pouze hodnot 0 nebo 1, což umožňuje modelovat logická rozhodnutí typu „ano/ne".

Klíčové vlastnosti a složitost

Výpočetní složitost

Úloha celočíselného lineárního programování je v obecném případě NP-těžká. To znamená, že neexistuje žádný známý algoritmus schopný nalézt přesné optimální řešení pro libovolnou úlohu CP v polynomiálním čase. Složitost je dána kombinatorickou povahou úlohy, neboť počet možných celočíselných řešení může s rostoucím počtem proměnných růst exponenciálně.

Vztah k lineárnímu programování (LP-relaxace)

Pro každou úlohu CP lze formulovat její lineární relaxaci — úlohu lineárního programování (LP), v níž je vypuštěn požadavek celočíselnosti proměnných. Řešení LP-relaxace má dvě důležité vlastnosti:

1. Lze jej nalézt výrazně rychleji (v polynomiálním čase).
2. Optimální hodnota účelové funkce LP-relaxace poskytuje odhad (horní hranici pro úlohu maximalizace a dolní pro minimalizaci) optimální hodnoty původní celočíselné úlohy.

Jednoduché zaokrouhlení zlomkového řešení LP-relaxace na nejbližší celá čísla však zpravidla nevede k optimálnímu ani přípustnému řešení celočíselné úlohy.

Vlastnost totální unimodularity

Existuje důležitá třída úloh CLP, které se řeší stejně snadno jako jejich LP-relaxace. Jsou to úlohy, v nichž je matice omezení $A$ totálně unimodulární (tj. determinant každé její čtvercové podmatice se rovná 0, +1 nebo −1). Je-li matice $A$ totálně unimodulární a vektor $b$ celočíselný, pak jsou všechny vrcholy mnohostěnu přípustných řešení LP-relaxace automaticky celočíselné. Řešení nalezené simplexovou metodou tedy bude celočíselné. Příklady takových úloh jsou dopravní úloha a přiřazovací úloha.

Metody řešení

Pro řešení obecných úloh CP, které nevykazují vlastnost totální unimodularity, byly vyvinuty přesné metody založené na myšlence implicitního prohledávání.

• Metoda větví a mezí (angl. Branch and Bound) — hlavní přesná metoda, založená na systematickém rozkladu množiny přípustných řešení na podmnožiny (větvení) a odřezávání těch podmnožin, které zjevně neobsahují optimální řešení. K hodnocení perspektivnosti podmnožin se využívá LP-relaxace.

• Metoda řezných rovinek (Gomoryho metoda; angl. Cutting Plane Method) — iterativní přístup, který postupně přidává k úloze nová lineární omezení („řezy"). Tyto řezy „odřezávají" zlomková řešení LP-relaxace, aniž by se dotkla jediného přípustného celočíselného řešení, a postupně přibližují oblast přípustných řešení LP-relaxace ke konvexnímu obalu celočíselných řešení.

Moderní řešiče zpravidla využívají hybridní algoritmy, jako je metoda větví a řezů (angl. Branch and Cut), která spojuje výhody obou přístupů.

Příklady a oblasti použití

Celočíselné programování umožňuje modelovat řadu klasických úloh kombinatorické optimalizace.

• Úloha o batohu: klasická úloha 0-1 programování, v níž je třeba vybrat sadu předmětů s maximální celkovou hodnotou při nepřekročení omezení na celkovou hmotnost.
• Úloha obchodního cestujícího: úloha hledání nejkratší trasy procházející zadanou množinou měst. Může být formulována jako úloha celočíselného programování, kde proměnné rozhodují o zařazení hran grafu do výsledné trasy.

Díky své flexibilitě je CP jedním z nejžádanějších nástrojů v operačním výzkumu a nachází uplatnění v oblastech, jako jsou:

• Logistika a řízení dodavatelských řetězců: optimalizace tras dopravy, rozmístění skladů, řízení zásob.
• Plánování výroby: sestavování výrobních harmonogramů, alokace zdrojů, vytížení zařízení.
• Finance a ekonomika: tvorba investičního portfolia, kapitálové rozpočtování.
• Telekomunikace a energetika: projektování komunikačních sítí, plánování provozu energetických bloků.

Viz také

• Lineární programování
• Metoda větví a mezí