Worst-case omezení přes kombinace
Prerekvizity: [L1.2] Přiřazovací struktura, [L1.4] big-M, [L1.8] Omezení rozptylu (max/min jedné množiny). Nosná úloha je zápočtová School lunch menu design (test 2021): sestavuješ týdenní jídelníček školní jídelny. Tři ze čtyř podmínek zadání jsou techniky, které už máš — čtvrtá („any student orders arbitrary combination of meals“) je dnešní nová věc.
Kostra: jídelníček jako výběrové binárky
Data: $M = \{1,\dots,100\}$ typů jídel, $D = \{1,\dots,5\}$ dnů; jídlo $m$ má proteiny $p_m$, cenu porce $c_m$ a příznak vegetariánství $v_m \in \{0,1\}$ — vše konstanty (vzpomeň na [L1.12]: příslušnost do skupiny jsou data, součin konstanta × binárka je lineární). Elementární rozhodnutí: je jídlo $m$ v den $d$ na menu?
$$x_{m,d} \in \{0,1\}, \qquad m \in M,\; d \in D, \qquad x_{m,d} = 1 \iff \text{jídlo } m \text{ je v den } d \text{ na menu.}$$Zkus sám: podmínky 1 („four different meals, at least one vegetarian“), 3 („each meal at most once per week“) a kritérium 2 („minimize cost, 120 portions of each meal on the menu“) jsou samé staré známé. Napiš je.
Počty na menu jsou součtové podmínky jako v [L1.2]:
$$\sum_{m \in M} x_{m,d} = 4 \quad \forall d \in D, \qquad\qquad \sum_{m \in M} v_m\, x_{m,d} \ge 1 \quad \forall d \in D,$$(„čtyři různá jídla“ je zadarmo — $x_{m,d}$ je jedna binárka na typ jídla, takže 4 jedničky = 4 různé typy; vegetariánský filtr je součin konstanty $v_m$ s binárkou). „Nejvýš jednou za týden“ je součet přes dny:
$$\sum_{d \in D} x_{m,d} \le 1 \quad \forall m \in M.$$A kritérium: každý den se každého jídla na menu uvaří přesně 120 porcí, takže cena týdne je
$$\min\; 120 \sum_{d \in D} \sum_{m \in M} c_m\, x_{m,d}.$$Konstanta 120 optimum nemění (jen škáluje hodnotu kritéria), ale patří do modelu — zadání mluví o ceně týdenního menu.
Podmínka 4: „arbitrary combination of meals“
Zbývá nutriční podmínka: „if any student orders arbitrary combination of meals in the week (exactly one meal per day), his/her total intake of protein must be at least $p^{\min}$“. Tedy: ať si student vybere z menu kterékoli jídlo každý den, součet proteinů jeho pěti jídel musí vyjít aspoň $p^{\min}$. Omezení nekvantifikuje přes jednu množinu čísel, ale přes všechny kombinace voleb.
Zkus sám: první nápad bývá $\sum_{m} p_m\, x_{m,d} \ge \tfrac{1}{5}p^{\min}$ pro každý den — součet proteinů denního menu. Proč je to špatně?
Protože $\sum_m p_m x_{m,d}$ je součet proteinů všech čtyř jídel na menu — ale student sní každý den jen jedno z nich. Tři jídla s obřím proteinem „dotují“ čtvrté nuzné, a student, který si vybere právě to nuzné, limit nesplní. Podmínka se týká každé volby, ne průměru ani součtu nabídky.
Zkus sám: tak tedy vypsat omezení „$\sum$ proteinů $\ge p^{\min}$“ pro každou kombinaci zvlášť. Kolik kombinací to je — a šlo by to vůbec?
Kombinace = 1 jídlo na den z denního menu: $4^5 = 1024$ kombinací — a obecně $4^{|D|}$, exponenciálně v počtu dnů. A je to ještě horší: menu předem neznáš (rozhoduje o něm sám model), takže bys musel vypsat omezení pro každou pětici jídel z $M$ — to je $100^5 = 10^{10}$ podmíněných omezení, každé „aktivní, jen pokud je všech pět jídel na menu“. Slepá ulička; potřebujeme chytřejší myšlenku.
Zkus sám: která kombinace je ze všech nejtěžší na splnění? A co z toho plyne pro všechny ostatní?
Volby v jednotlivých dnech jsou nezávislé — výběr v pondělí nijak neomezuje výběr v úterý. Nejméně proteinů tedy nasbírá student, který si každý den vybere proteinové minimum denního menu:
$$\min_{\text{kombinace}} \sum_{d \in D} p_{\text{volba}(d)} \;=\; \sum_{d \in D}\; \min_{m \,\in\, \text{menu}_d} p_m.$$A to je celá pointa: když nejhorší kombinace splní $\ge p^{\min}$, splní ho každá — všechny ostatní jsou po dnech aspoň tak dobré. Místo $4^5$ omezení stačí ohlídat jediné číslo: součet denních minim.
Nebezpečná polopravda: „min už umím z L1.8“Konstrukce z [L1.8] ($h_{min} \le h_j$ pro všechna $j$) počítá min přes jednu pevnou indexovou množinu (např. všechny muže). Tady je to dvakrát jinak: (1) omezení má platit pro každou kombinaci voleb — to se řeší přechodem na nejhorší případ, žádná „jedna množina hodnot“ tu předem není; (2) denní minimum běží jen přes vybraná jídla ($x_{m,d} = 1$) — množina je sama rozhodnutím modelu, takže nerovnosti se musí pro nevybraná jídla vypnout přes big-M [L1.4]. Kdo na lunch menu napíše holé „L1.8 minimum“, model rozbije (hned uvidíš jak).
Denní minimum přes vybraná jídla: $z_d$ + big-M
Chceme pomocnou proměnnou $z_d$ = „kolik proteinů nejmíň dostane student v den $d$“. Plán podle [L1.8]: svázat $z_d$ shora s hodnotami a součet $\sum_d z_d$ vynutit $\ge p^{\min}$.
Zkus sám: proč nejde napsat prostě $z_d \le p_m$ pro všechna $m \in M$, jako v [L1.8]?
Protože by $z_d$ srazilo minimum přes všech 100 jídel v $M$ — i přes ta, která ten den na menu vůbec nejsou! Jediné nízkoproteinové jídlo v katalogu (klidně nikdy nevařené) by stáhlo všechna $z_d$ dolů a podmínka $\sum_d z_d \ge p^{\min}$ by se stala nesplnitelnou, přestože reálné menu je v pořádku — model by se nesmyslně zpřísnil. Nerovnost $z_d \le p_m$ smí „platit“ jen pro jídla s $x_{m,d} = 1$ — a podmíněné omezení = big-M [L1.4]. Pozor na notaci: symbol $M$ je v tomhle zadání obsazený množinou jídel, big-M konstantu proto výjimečně značíme $K$:
$$z_d \;\le\; p_m + K\,(1 - x_{m,d}) \qquad \forall m \in M,\; \forall d \in D.$$Pro $x_{m,d} = 1$ je to ostré $z_d \le p_m$; pro $x_{m,d} = 0$ se pravá strana zvedne o $K$ a omezení nic neřeže.
Zkus sám: jak velké musí být $K$?
Vypnutá nerovnost ($x_{m,d}=0$) nesmí řezat žádnou dosažitelnou hodnotu $z_d$. Smysluplné $z_d$ je nejvýš minimum vybraných proteinů, tedy nejvýš $\max_{m} p_m$. Protože proteiny jsou nezáporné ($p_m \ge 0$), je vypnutá pravá strana $p_m + K \ge K$, takže stačí
$$K = \max_{m \in M} p_m$$(těsnější — a platné i bez předpokladu $p_m \ge 0$: $K = \max_m p_m - \min_m p_m$, protože vypnutá pravá strana je pak $p_m + K \ge \min_m p_m + K = \max_m p_m$). Jako vždy u big-M [L1.4]: velikost vždy zdůvodni — dost velké, aby vypnuté omezení neřezalo, ne nesmyslně obří.
Zkus sám: nerovnosti tlačí $z_d$ jen shora. Nepotřebuješ ještě vazbu, že $z_d$ to minimum opravdu je (zespodu)?
Nepotřebuješ — stejná jednostranná logika jako v [L1.8]. Celá konstrukce je:
$$z_d \le p_m + K(1 - x_{m,d}) \;\;\forall m, d, \qquad\qquad \sum_{d \in D} z_d \ge p^{\min}.$$Rozmysli oba směry: (⇒) je-li model přípustný, pak pro každý den $z_d \le \min$ vybraných proteinů, takže nejhorší student dostane $\sum_d \min_{m \in \text{menu}_d} p_m \ge \sum_d z_d \ge p^{\min}$ — podmínka 4 platí. (⇐) splňuje-li menu podmínku 4, polož $z_d := \min_{m \in \text{menu}_d} p_m$ a všechna omezení sedí — žádné dobré menu jsme neuřízli. Solver si $z_d$ „nafoukne“ k dennímu minimu sám, protože potřebuje projít součtovým omezením.
Spočítej si i cenu: $|M| \cdot |D| = 500$ nerovností + 1 součtová — místo $4^5$ kombinací. Polynomiální zápis exponenciálního požadavku.
Key takeaways — L1.13- POZOR: tohle NENÍ max/min jedné množiny z [L1.8]. Tam počítáš min/max přes jednu pevnou množinu hodnot; tady musí nerovnost platit pro každou možnou kombinaci voleb (1 jídlo na den) — kombinatoricky jiná konstrukce.
- Klíčová myšlenka: má-li omezení platit pro libovolnou volbu, stačí ho zaručit pro nejhorší dosažitelnou kombinaci — uhlídáš-li worst case, ostatní kombinace jsou v pořádku zadarmo. Díky nezávislosti voleb po dnech je nejhorší kombinace = součet denních minim.
- Minimum přes vybrané položky (množinu volí model): $z_d \le p_m + K(1 - x_{m,d})$ $\forall m, d$ — big-M [L1.4] vypne nerovnost pro nevybraná jídla. Holé $z_d \le p_m$ $\forall m$ (à la [L1.8]) by model zpřísnilo o minimum přes celý katalog.
- Worst-case podmínka pak jednou nerovností: $\sum_d z_d \ge p^{\min}$; big-M konstanta $K = \max_m p_m$ (díky $p_m \ge 0$; symbol $M$ je obsazený množinou jídel, proto $K$). Vazba stačí jednostranná — solver $z_d$ dotlačí k dennímu minimu sám. Exponenciálně mnoho kombinací ⟶ $|M|\cdot|D|$ lineárních omezení.
“Let $M = \{1, \ldots, 100\}$ be a set of different meal types (e.g. schnitzel, lasagne etc.) and let $D = \{1, \ldots, 5\}$ be working days of one specific week. Each portion of meal $m \in M$ provides $p_m$ proteins. For each meal $m \in M$, value $v_m \in \{0, 1\}$ determines whether it is vegetarian or not and value $c_m$ is a cost of cooking one portion of meal $m$.
The goal is to design a school lunch menu for one week such that
1. each day, four different meals from $M$ are on the menu and at least one of them is vegetarian.
2. the cost of the week menu has to be minimized. Every day, exactly 120 portions of each meal on the menu is cooked.
3. each meal $m \in M$ is on the menu at most once per week.
4. to satisfy recommended weekly limits on the nutrition values, it must hold that if any student orders arbitrary combination of meals in the week (exactly one meal per day), his/her total intake of protein must be at least $p^{\min}$.
Formulate this problem as Integer Linear Programming.”
a) Co je v zadání?
Katalog 100 typů jídel (proteiny $p_m$, cena porce $c_m$, vegetariánský příznak $v_m$ — vše data) a 5 pracovních dnů. Rozhoduješ, co bude který den na menu. Čtyři požadavky: (1) každý den přesně 4 různá jídla, z toho aspoň jedno vegetariánské; (2) minimalizuj cenu — každého jídla na menu se vaří přesně 120 porcí; (3) žádné jídlo se za týden neopakuje; (4) každá studentská kombinace (1 jídlo denně z denního menu) dá za týden aspoň $p^{\min}$ proteinů.
b) Co k tomu budeme potřebovat?
- Tato lekce — worst-case přes kombinace: denní minima $z_d$ přes big-M deaktivaci, $\sum_d z_d \ge p^{\min}$.
- [L1.2] Přiřazovací struktura — binárky $x_{m,d}$ a součtové podmínky (přesně 4 denně, nejvýš 1× týdně).
- [L1.4] big-M — podmíněné vypnutí nerovnosti pro $x_{m,d} = 0$.
- [L1.8] max/min jedné množiny — jednostranná vazba pomocné proměnné (a vědomí, čím se dnešní konstrukce liší).
- [L1.1] Lineární kritérium — cena týdenního menu.
c) Jak nad úlohou uvažovat?
Rozsekej zadání po podmínkách. Elementární rozhodnutí: jídlo × den → binárka (jaké součty přes řádky/sloupce podmínky 1 a 3 chtějí — rovnost, nebo nerovnost?). U kritéria nezapomeň na 120 porcí. Celý vtip je podmínka 4: nejdřív si ujasni, čí proteiny počítáš (jednoho studenta a jeho pět voleb, ne součet menu!), pak najdi nejhorší kombinaci (nezávislost po dnech) a postav denní minima přes $z_d$ — pozor, minimum jen přes vybraná jídla, tedy big-M, ne holé nerovnosti z [L1.8]. Nakonec zkontroluj velikost big-M konstanty (a její značení — $M$ je obsazené).
d) Úplné řešení
Proměnné:
$$x_{m,d} \in \{0,1\} \;\; \forall m \in M,\, \forall d \in D \;\;(\text{jídlo } m \text{ na menu dne } d), \qquad z_d \in \mathbb{R} \;\; \forall d \in D.$$(1) Každý den 4 různá jídla, aspoň jedno vegetariánské:
$$\sum_{m \in M} x_{m,d} = 4 \quad \forall d \in D, \qquad\qquad \sum_{m \in M} v_m\, x_{m,d} \ge 1 \quad \forall d \in D.$$(Různost je automatická — jedna binárka na typ jídla; $v_m$ je konstanta, součin je lineární.)
(3) Každé jídlo nejvýš jednou za týden:
$$\sum_{d \in D} x_{m,d} \le 1 \quad \forall m \in M.$$(4) Worst-case proteinová podmínka — denní minimum $z_d$ jen přes vybraná jídla (big-M deaktivace; konstantu značíme $K$, protože $M$ je v zadání obsazené množinou jídel) a součet minim přes týden:
$$z_d \le p_m + K\,(1 - x_{m,d}) \quad \forall m \in M,\, \forall d \in D, \qquad\qquad \sum_{d \in D} z_d \ge p^{\min}, \qquad K = \max_{m \in M} p_m \;(\ge 0).$$Proč to stačí: pro $x_{m,d}=1$ je $z_d \le p_m$, takže $z_d \le \min_{m \in \text{menu}_d} p_m$; součet $\sum_d z_d \ge p^{\min}$ tedy zaručuje, že i student volící každý den nejslabší jídlo nasbírá $\ge p^{\min}$ — a každá jiná kombinace je po dnech aspoň tak dobrá. Obráceně každé vyhovující menu lze doplnit $z_d := \min_{m \in \text{menu}_d} p_m$, takže model žádné dobré menu nezakazuje.
(2) Kritérium — 120 porcí od každého jídla na menu:
$$\min\; 120 \sum_{d \in D} \sum_{m \in M} c_m\, x_{m,d}.$$Celkem $500$ binárek, $5$ spojitých $z_d$ a $O(|M|\cdot|D|)$ lineárních omezení — žádné vypisování kombinací.