10 Význam a řešení úloh MIP
Předchozí neformální uvedení způsobu řešení úloh celočíselné optimalizace je v následující lekci
postaveno na pevné matematické zálady.
Osvojíme si pojem celočíselné mříže, která popisuje přípustná (celočíselná) řešení úloh MIP,
a ukážeme význam konvexního obalu celočíselných řešení úlohy. Dále si popíšeme obecné
schéma metody větvení a její implementaci pomocí mezí lineárních relaxací úlohy. Na příkladě
rozvrhování si ukážeme i alternativní způsob relaxace úlohy v této metodě.
Stručný přehled lekce
ˇ Pojem celočíselné mříže.
ˇ Obecné schéma metody větvení.
ˇ Implementace metody větvení pomocí lineárních relaxací coby mezí.
ˇ Účinné postupy při volbách větvení a relaxace.
ˇ Alternativní implementace relaxací na příkladě úlohy rozvrhování.
Petr Hliněný, FI MU 1 IA102 "OU": Řešení úloh MIP
10.1 Celočíselná mříž
Definice: Celočíselná mříž v Rd
(dimenze d) je množina všech bodů s celočíselnými
souřadnicemi
Md
= {(z1, . . . , zd) : z1, . . . , zd  Zd
} .
Definice: Rozšířená celočíselná mříž dimenze d + r je množina všech bodů
Md,r
= {(x1, . . . , xr, z1, . . . , zd) : (z1, . . . , zd)  Md
, x1, . . . , xr  R} .
Je to tedy sjednocení všech disjunktních podprostorů dimenze r, jejichž posledních d
souřadnic jsou fixní celočíselné hodnoty.
Fakt: Mějme úlohu IP U s omezenými celočíselnými proměnnými. Pak množina pří-
pustných řešení U (jako podmnožina mříže Md
) je konečná a její konvexní obal je
polytop. Podle Věty 4.12 lze tudíž konvexní obal Q přípustných řešení úlohy U zapsat
jako polyedr Q, na kterém pak můžeme použít běžnou lineární optimalizaci:
Jelikož řešením LP je některý krajní bod polyedru, je výsledkem lineární optimalizace
na Q jedno z přípustných řešení U.
Pozor, uvedený fakt však neznamená, že bychom rázem měli efektivní metodu řešení
úloh IP, neboť v obvyklých příkladech složitost zápisu polyedru Q obrovským způsobem
vzroste oproti původní úloze (oproti původnímu polyedru lineární relaxace).
Petr Hliněný, FI MU 2 IA102 "OU": Řešení úloh MIP
Tvrzení 10.1. Mějme úlohu MIP U s omezenými proměnnými. Pak konvexní obal K
množiny přípustných řešení U (jako podmnožiny mříže Md,r
) je polyedrem.
Důkaz: Nechť P je (omezený) polyedr definovaný nerovnostma úlohy U, tedy že P 
Md,r
jsou přípustná řešení U. Nechť z je vektor celočíselných proměnných. Pak díky
omezenosti může z nabývat jen konečně mnoha hodnot z podmříže z  M. Z definice
polyedru je P  {z : z = z1
} omezeným polyedrem pro každou volbu z1
 M, tedy i
polytopem s konečnou množinou vrcholů V (z1
). Položíme V = z1M V (z1
), což je
také konečná množina, a K je konvexním obalem V , tudíž je K polytopem i polyedrem.
2
Poznámka: Idea hledání polyedru, který je konvexním obalem přípustných řešení úlohy MIP,
stojí za obecným schématem tzv. "cutting-plane" algoritmů pro řešení MIP.
Základním krokem je postupné přidávání platných nerovností k původní formulaci úlohy, tj.
přidávání takových nerovností, které nevyplývají z lineárních kombinací ostatních nerovností
úlohy, ale které zachovají množinu přípustných celočíselných řešení. (Toto si lze představit
jako "uříznutí" neceločíselných vrcholů polyedru.) Důležitým původním příkladem takových
nerovností jsou Gomoryho řezy, které v konečném počtu kroků konvergují k optimálnímu
řešení úlohy IP.
Petr Hliněný, FI MU 3 IA102 "OU": Řešení úloh MIP
10.2 Obecná metoda větvení
Níže popsaná obecná metoda větvení rozšiřuje pojetí Algoritmu 9.7 na různé typy rela-
xací úlohy MIP, které nemusí být lineární ani nemusí být řešeny simplexovou metodou.
Definice: Nechť U je úlohou MIP s reálnými proměnnými x = (x1, . . . , xr) a ce-
ločíselnými proměnnými z = (z1, . . . , zd), které patří do rozšířené celočíselné mříže
(x, z)  Md,r
. Označme P množinu přípustných řešení U. Množinu R (libovolnou)
nazveme množinou relaxovaných řešení úlohy U, pokud P = R  Md,r
je průnikem R
s celočíselnou mříží Md,r
.
Algoritmus 10.2. Obecná metoda větvení pro řešení úloh MIP
Mějme dánu obecnou úlohu MIP s reálnými proměnnými x = (x1, . . . , xr) a celočísel-
nými proměnnými z = (z1, . . . , zd), ve které je účelovou funkcí max c  (x, z).
Nechť f je globální proměnná inicializovaná f = - a nechť M je podmnožina
celočíselné mříže obsahující všechny přípustné hodnoty z.
Petr Hliněný, FI MU 4 IA102 "OU": Řešení úloh MIP
Procedura branch&bound( U: úloha MIP, M  Md
)
1. Pokud M má jediný prvek, pak fixujeme zo
 M a řešíme úlohu LP U  z = zo
(třeba simplexovou metodou). Vrátíme její optimální řešení return (xo
, zo
) .
2. Zvolíme R  Rr+d
: libovolná množina relaxovaných řešení úlohy U  z  M.
3. ro
= max{ct : t  R}, to
 R : ro
= cto
(optimální řešení relaxované úlohy).
4. Pokud ro
 f nebo R = , vrátíme se bez řešení return  .
5. Pokud ro
=  pro nějaké příp. z  M, položíme f =  a vrátíme return  .
6. Pokud je to
 Md,r
, tj. přípustné v U, položíme f = ro
a vratíme return to
.
7. [Příp. heuristicky hledáme přípustné řešení s  Md,r
"blízké" k to
.]
8. [Příp. formulaci úlohy U rozšíříme ("vylepšíme") na U
o další platné podmínky
zjištěné z nepřípustnosti řešení to
. Zavoláme branch&bound( U
, M) .]
9. Krok větvení: S pomocí to
nalezneme (libovolný) rozklad M = M1  M2, kde
M1  M2 =  a M1, M2 = . Zavoláme rekurzivně
t 1
= branch&bound( U, M1) a t 2
= branch&bound( U, M2)
zároveň nedeterministicky. Vracíme lepší z obou řešení return max (t 1
, t 2
) .
Body (7,8) jsou nepovinné. Návratová hodnota procedury je optimálním řešením úlohy
U s účelovou hodnotou f.
Pokud f = -, úloha nemá přípustné řešení, pokud f = , úloha nemá optimální
řešení z důvodu neomezenosti.
Petr Hliněný, FI MU 5 IA102 "OU": Řešení úloh MIP
U tohoto algoritmu se jedná o velmi obecné schéma s různými možnými implementacemi.
Hlavní možnost volby nám poskytuje nedeterminismus v bodě (9); a to jak při volbě roz-
kladu podmříže M, tak i při pořadí volání větví M1, M2. Dále je také možno libovolně volit
implementace bodů (7,8), nebo je jednoduše neimplementovat vůbec.
Poznámka: Důležitým aspektem implementace uvedeného schématu algoritmu je způsob zpra-
cování volaného větvení v bodě (9). Naše schéma je formulováno tak, že větvení je rekurzivním
voláním, avšak to je z hlediska praktické programové implementace sice snadné, ale neefek-
tivní. Pro vylešování implementace totiž potřebujeme mít programovou kontrolu nad pořadím
a způsobem zpracování jednotlivých větví. Proto je vhodné si vytvořit vlastní datovou strukturu
­ úložiště nezpracovaných větví metody.
Věta 10.3. Mějme dánu obecnou úlohu MIP U s omezenými celočíselnými proměn-
nými z konečné podmříže M. Pokud se nepoužije bod (8), nebo pokud je zabráněno
jeho zacyklení, tak Algoritmus 10.2 na branch&bound( U, M) vždy skončí a nalezne
optimální řešení.
Důkaz (náznak): Důkaz jen přímočaře zobecňuje argumenty Tvrzení 9.8. Za prvé,
hloubka rekurze je omezená počtem bodů |M| ­ nejpozději v této hloubce nastane
|M| = 1 a uplatní se bod (1). Proto je algoritmus konečný, ale délka výpočtu je až
exponenciální. Optimální řešení úlohy zřejmě náleží do jedné z prohledávaných větví a
jako takové bude nalezeno a vráceno. 2
Petr Hliněný, FI MU 6 IA102 "OU": Řešení úloh MIP
10.3 Metoda větvení a mezí s lin. relaxacemi
V následujícím oddíle si především vysvětlíme, jak popis konkrétního Algoritmu 9.7 (pro
větvení a meze základní úlohy MIP) zapadá do rámce schématu Algoritmu 10.2.
Algoritmus 10.4. Postup větvení a mezí s lin. relaxacemi
Nechť U je obecná úloha MIP s omezenými celočíselnými proměnnými z  d.
Přirozeně položíme M = {z : 0  z  d}. Při implementaci branch&bound( U, M)
postupujeme dle Algoritmu 10.2 s následujícími implementačními detaily:
ˇ V kroku 2 za relaxovaná řešení volíme lineární relaxaci U.
ˇ V kroku 3 nalezneme ro
, to
simplexovou metodou.
Případně pokud U je úloha IP a M obsahuje jen málo mřížových bodů, je občas
lepší přeskočit relaxaci úlohy úplně a jen dál větvit M až na jednotlivé body.
ˇ V kroku 7 se pro neceločíselné z-složky řešení to
pokusíme získat přípustné řešení
zaokrouhlením (třeba náhodným) těhcto necelých proměnných v to
.
ˇ Větvení kroku 9 určíme takto:
­ Zvolíme libovolnou celočíselnou proměnnou zi, která má necelou hodnotu
zo
i v to
(zi zde nazveme větvící proměnnou).
­ Definujeme
M1 = M  {zi  zo
i } , M2 = M  {zi  zo
i } .
Petr Hliněný, FI MU 7 IA102 "OU": Řešení úloh MIP
Konkrétně výběr větvící proměnné je možný pro příklad následujícími postupy:
ˇ Uživatelem specifikované priority (obvykle vycházející z povahy řešeného pro-
blému).
ˇ Maximální celočíselná nepřípustnost ­ tam vybíráme proměnnou zi, jejíž necelá
část (z0
i - z0
i ) je nejblíže číslu 0.5.
Ve větvení se pak doporučuje nejprve řešit větev M1, pokud necelá část je < 0.5,
jinak M2.
ˇ Zobecněním předchozího je volba podle celočíselné degradace, kdy jsou (nějak)
specifikovány koeficienty p+
i , p-
i (mohou se měnit během výpočtu) a vybíráme
proměnnou zi s necelou hodnotou, pro kterou je maximalizováno min((p-
i (z0
i -
z0
i ), p+
i ( z0
i - z0
i )).
ˇ Jiné, chytřejší metody se v praxi obvykle ukazují jako příliš zdlouhavé.
Petr Hliněný, FI MU 8 IA102 "OU": Řešení úloh MIP
10.4 Řešené příklady IP
Příklad 10.5. Letecká společnost má přepravit 141 lidí z města A do B. K dispozici má čtyři
letadla: kapacita cena letu posádka
L1 90 300 7
L2 60 210 4
L3 50 200 3
L4 33 130 2
Která letadla má zvolit, aby dosáhla nejlevnějšího řešení?
Řešení: Řešíme tutéž úlohu, ale nyní doplníme omezení počtu členů posádky, kterých má
společnost celkem k dispozici 10.
7z1 + 4z2 + 3z3 + 2z4  10
Výsledek: poletí L2, L3 a L4.
Následně doplníme další vlastnost, a to možnost použití aerotaxi s kapacitou 5 a cenou 35
(bez potřeby vlastní posádky).
max - 300z1 - 210z2 - 200z3 - 130z4 - 35z5
90z1 + 60z2 + 50z3 + 33z4 + 5z5  141
7z1 + 4z2 + 3z3 + 2z4  10
zi  {0, 1}
Výsledek: poletí L1, L3 a aerotaxi. 2
Petr Hliněný, FI MU 9 IA102 "OU": Řešení úloh MIP
10.5 Větvení a meze trochu jinak
Příklad 10.6. Jednotlivé nepřerušitelné rozvrhování úloh II.
Mějme stroj, který zpracovává po jedné zadané úlohy. Každá úloha má danou prioritu, je
připravena ke zpracování v určitém čase a její dokončení trvá určitou dobu. Přitom postup
zpracování jedné úlohy nelze přerušit (ostatní úlohy musí čekat na její dokončení).
Vstup: Úloha Ji začne v čase ti s délkou li a prioritou pi, i = 1, 2, . . . , n.
Výstup: Pořadí zpracování, ve kterém úloha Ji je ukončena v čase fi.
Cena řešení je dána souhrnem čekání na dokončení jednotlivých úloh, váženým prioritami úloh
min c =
n
i=1
(fi - ti)  pi .
Řešení: Úlohu budeme řešit specifickou implementací metody větvení a mezí, přičemž jako
relaxační mez nám bude sloužit řešení obdobné úlohy, ve které lze zpracování úloh libovolně
přerušovat.
Jako v Příkladě ?? použijeme formulaci, kdy pořadí zpracování úloh bude určeno jednou z
n! permutací. Na rozdíl od běžných úloh MIP však nebudeme sestavovat soustavu lineárních
nerovnic pro formulaci omezení, ale budeme kombinovat účelovou hodnotu řešení nepřeruši-
telného rozvrhování pro danou permuaci s relaxací úlohy přerušitelným rozvrhováním.
.......... 2
Petr Hliněný, FI MU 10 IA102 "OU": Řešení úloh MIP