Co je ILP a LP relaxace
Prerekvizity: žádné — tohle je vstupní brána do celé kapitoly K1 (ILP modelování).
Definice ILP
Ze slidů (02_ILP, slide 3): „The ILP problem is given by matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ and vectors $\mathbf{b} \in \mathbb{R}^m$ and $\mathbf{c} \in \mathbb{R}^n$. The goal is to find a vector $\mathbf{x} \in \mathbb{Z}^n$ such that $\mathbf{A}x \le b$ and $c^T x$ is the maximum.“ Zkráceně:
$$\max \left\{ c^T x \;:\; \mathbf{A}x \le b,\; x \in \mathbb{Z}^n \right\}$$Integer Linear Programming — ILP (celočíselné lineární programování): cílová funkce i omezení jsou lineární, ale proměnné musí být celé. Když smí být část proměnných reálná, mluví se o MIP (mixed integer programming) — slidy ale říkají: „we will use the term ILP when at least one variable has integer domain“, takže ILP říkáme i smíšeným modelům.
Zkus sám: čím se liší LP od ILP — a která z těch dvou úloh je „těžká“?
LP má $x \in \mathbb{R}^n$ — přípustná množina je konvexní mnohostěn a LP se řeší v polynomiálním čase. ILP je NP-těžké: celočíselnost rozbije konvexitu (přípustné body jsou „roztroušená“ mřížka) a žádný polynomiální algoritmus není znám. Paradox kurzu: přidáním omezení (celočíselnost) se úloha stane těžší — ale zároveň díky tomu ILP umí vyjádřit NP-těžké kombinatorické problémy.
LP relaxace: zahodím celočíselnost
LP relaxace ILP problému = tentýž model, ve kterém podmínku $x \in \mathbb{Z}^n$ nahradím $x \in \mathbb{R}^n$. Relaxace se řeší rychle a její optimum je vždy aspoň tak dobré jako optimum ILP (přípustných bodů jen přibylo). Konkrétní příklad ze slidu 17:
$$\begin{aligned} \max\ z = \;& 3x_1 + 4x_2 \\ \text{s.t.}\ & 5x_1 + 8x_2 \le 40 \\ & x_1 - 5x_2 \le 0 \\ & x_1, x_2 \in \mathbb{Z}^+_0 \end{aligned}$$Zkus sám: LP optimum vyšlo $x_1 = 6.06$, $x_2 = 1.21$. Co s tím? Zaokrouhlit na $(6, 1)$?
Zkontroluj omezení pro $(6,1)$: $5 \cdot 6 + 8 \cdot 1 = 38 \le 40$ ✓, ale $x_1 - 5x_2 = 6 - 5 = 1 \not\le 0$ ✗. Zaokrouhlený bod je infeasible — leží mimo přípustnou oblast! A to není jediný problém, viz druhý obrázek.
Proč zaokrouhlování nestačí
Slide 18 („Rounding is not always good choice“) na stejném modelu ukazuje čtyři body:
- a) LP řešení $z = 23.03$ pro $x_1 = 6.06,\ x_2 = 1.21$ — necelé,
- b) zaokrouhlení vede na infeasible $(6, 1)$,
- c) nejbližší přípustný celočíselný bod $(5, 1)$ není optimální: $z = 19$,
- d) skutečné optimum ILP je $z = 21$ pro $x_1 = 3,\ x_2 = 3$ — úplně jinde.
Pozor — nebezpečná polopravda„ILP vyřeším tak, že vyřeším LP a zaokrouhlím.“ NE. Zaokrouhlené řešení může být (b) infeasible, a i nejbližší přípustný celočíselný bod (c) může být daleko od optima (d). LP relaxace je cenná jinak: dává mez (u maximalizace horní, u minimalizace dolní) — na tom stojí Branch & Bound (kapitola K5, [L5.5] Branch & Bound pro ILP).
Zkus sám: může být optimum LP relaxace horší (menší při maximalizaci) než optimum ILP?
Ne. Každé přípustné řešení ILP je i přípustným řešením relaxace (jen jsme zahodili jednu podmínku), takže LP optimum je vždy $\ge$ ILP optimum (při maximalizaci). Tady: $23.03 \ge 21$. Proto LP relaxace funguje jako horní mez — když LP relaxace nějaké větve v Branch & Bound dá míň, než už máme, celou větev lze zahodit.
Key takeaways — L0.7- ILP: $\max\{c^T x : \mathbf{A}x \le b,\ x \in \mathbb{Z}^n\}$ — lineární cíl i omezení, celočíselné proměnné. NP-těžké; přípustná množina není konvexní.
- LP ($x \in \mathbb{R}^n$) je řešitelné polynomiálně; LP relaxace ILP = zahození celočíselnosti.
- Zaokrouhlení LP řešení může být infeasible a nejbližší přípustný celočíselný bod nemusí být optimum (slide 18: LP $23.03$ → ILP optimum $21$ v úplně jiném bodě).
- LP relaxace dává mez na ILP optimum (horní u max, dolní u min) — základ Branch & Bound.
$$\max z = 3x_1 + 4x_2 \quad \text{s.t.} \quad 5x_1 + 8x_2 \le 40,\quad x_1 - 5x_2 \le 0,\quad x_1, x_2 \in \mathbb{Z}^+_0.$$
“What is optimal solution? Can we use LP to solve the ILP problem?” Compute the LP relaxation optimum, show that rounding it leads to an infeasible solution, evaluate the nearest feasible integer point, and find the integer optimum.
a) Co je v zadání?
Malý ILP se dvěma proměnnými. Máš: (1) vyřešit LP relaxaci, (2) ověřit, že zaokrouhlení je nepřípustné, (3) vyhodnotit nejbližší přípustný celočíselný bod, (4) najít skutečné celočíselné optimum.
b) Co k tomu budeme potřebovat?
- Tato lekce — LP relaxace, kontrola přípustnosti dosazením.
c) Jak nad úlohou uvažovat?
LP optimum dvourozměrné úlohy leží ve vrcholu přípustné oblasti — tady v průsečíku obou přímek $5x_1 + 8x_2 = 40$ a $x_1 = 5x_2$ (proč zrovna tam? sleduj směr růstu $c = (3,4)$ na obrázku). Pro ILP optimum projdi celočíselné body uvnitř oblasti s velkým $z$ (mřížka na druhém obrázku).
d) Úplné řešení
(1) LP relaxace: průsečík: $x_1 = 5x_2$ dosadím do $5x_1 + 8x_2 = 40$: $25x_2 + 8x_2 = 33x_2 = 40$, tedy $x_2 = \tfrac{40}{33} \approx 1.21$, $x_1 = \tfrac{200}{33} \approx 6.06$, $z = 3 \cdot 6.06 + 4 \cdot 1.21 \approx \mathbf{23.03}$.
(2) Zaokrouhlení $(6, 1)$: $5 \cdot 6 + 8 \cdot 1 = 38 \le 40$ ✓, ale $6 - 5 \cdot 1 = 1 > 0$ ✗ — infeasible.
(3) Nejbližší přípustný celočíselný bod $(5, 1)$: $25 + 8 = 33 \le 40$ ✓, $5 - 5 = 0 \le 0$ ✓; $z = 15 + 4 = \mathbf{19}$.
(4) Celočíselné optimum $(3, 3)$: $15 + 24 = 39 \le 40$ ✓, $3 - 15 = -12 \le 0$ ✓; $z = 9 + 12 = \mathbf{21} > 19$. Lepší celočíselný bod není (každý bod s $z \ge 22$ porušuje některé omezení — viz mřížka). LP tedy ILP nevyřeší: $23.03 \to$ zaokrouhlení mimo oblast, „opravený” bod dá 19, optimum je 21 jinde.
“The LP problem solution space is convex, since $x \in \mathbb{R}^n$. … Since the ILP solution space is not a convex set, we cannot use convex optimization techniques.” Explain: (i) why the ILP solution space is not convex (give an example), and (ii) why “solve the LP and round” can fail.
a) Co je v zadání?
Teoretická otázka (typický materiál na ústní): zdůvodni nekonvexitu množiny celočíselných řešení a selhání zaokrouhlování.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice ILP, příklad ze slidu 18.
c) Jak nad úlohou uvažovat?
Konvexní množina obsahuje s každými dvěma body i celou úsečku mezi nimi. Vezmi dva celočíselné přípustné body a podívej se na střed úsečky. Pro (ii) máš hotový protipříklad v T01.
d) Úplné řešení
(i) Množina přípustných řešení ILP je množina celočíselných bodů (mřížky) uvnitř mnohostěnu. Vezmi třeba přípustné body $(0,0)$ a $(0,1)$: jejich střed $(0, 0.5)$ není celočíselný, tedy do množiny nepatří — množina neobsahuje úsečku mezi svými body, takže není konvexní. Proto nelze nasadit techniky konvexní optimalizace (které garantují, že lokální optimum je globální).
(ii) Protipříklad ze slidu 18 (úloha T01): LP optimum $(6.06, 1.21)$, zaokrouhlení $(6,1)$ porušuje $x_1 - 5x_2 \le 0$ — infeasible; nejbližší přípustný celočíselný bod $(5,1)$ má $z = 19$, zatímco optimum je $z = 21$ v $(3,3)$, daleko od LP řešení. Zaokrouhlování tedy může dát nepřípustné i výrazně suboptimální řešení.