Implikace mezi skupinami — Loot [FOTO]
Prerekvizity: [L1.3] Modelování logiky, [L1.4] big-M, [L1.8] Omezení rozptylu. Nosná úloha této lekce je ostrá zkoušková Loot distribution (zkouška 2023): Alibaba a jeho $k$ mužů rozdělují $n$ pokladů ze čtyř skupin. Dvě podmínky zadání jsou logika mezi skupinami — a přesně ty se dnes naučíš. Zbytek modelu jsou techniky, které už máš.
Kostra modelu: kdo nese co
Základní rozhodnutí úlohy je „muž $j$ nese poklad $t_i$“. To je klasická přiřazovací struktura [L1.2]: binární proměnné
$$m_i^j \in \{0,1\}, \qquad i \in \{1,\dots,n\},\; j \in \{1,\dots,k\},$$kde $m_i^j = 1$ ⟺ muž $j$ odnese poklad $t_i$. (Značení $m_i^j$ drží ruční řešení zkoušky 2023.)
Zkus sám: v [L1.2] bylo „každý objekt právě jednou“: $\sum_j x_{ij} = 1$. Platí to tady taky? Co se stane, když omezení vynecháš úplně?
Rovnost je tu špatně — nikdo neříká, že se musí odnést všechny poklady (těžké a laciné kusy se klidně nechají v hrobce; kritérium chce jen maximální cenu odneseného). Správně je nejvýš jednou:
$$\sum_{j=1}^{k} m_i^j \le 1 \qquad \forall i \in \{1,\dots,n\}.$$A vynechat to nejde: bez omezení by mohl tentýž poklad „nést“ víc mužů najednou a v kritériu $\max \sum_j \sum_i p_i\, m_i^j$ by se jeho cena započítala vícekrát — solver by toho okamžitě zneužil.
Druhý kus kostry je nosnost (capacity): muž $j$ unese nejvýš $u_j$, tedy pro každého muže rozpočtové omezení [L1.1] přes váhy:
$$\sum_{i=1}^{n} w_i\, m_i^j \le u_j \qquad \forall j \in \{1,\dots,k\}.$$Zkus sám: zadání pořád mluví o „hideouts“ (skrýších). Kde jsou v modelu?
Nikde — a to je správně. Zadání říká „to any of his hideouts“: žádná podmínka nerozlišuje, do které skrýše co putuje. Skrýše jsou kulisa navíc; model je nepotřebuje. Umět v zadání rozpoznat informaci, která žádné omezení negeneruje, je zkoušková dovednost — neztrácej čas modelováním kulis.
Příslušnost do skupiny jsou data, ne proměnná
Každý poklad patří do jedné ze skupin $G = \{1,2,3,4\}$ a zadání skupinu $g_i$ dává. Ruční řešení 2023 si proto předpočítalo binární konstanty
$$q_{i,g} = \begin{cases}1 & g_i = g,\\ 0 & \text{jinak,}\end{cases} \qquad i \in \{1,\dots,n\},\; g \in G.$$Zkus sám: výraz $q_{i,4} \cdot m_i^j$ vypadá jako součin — smí tohle do lineárního modelu?
Smí. $q_{i,4}$ je konstanta (číslo známé předem, ne proměnná), takže $q_{i,4} \cdot m_i^j$ je konstanta × proměnná — přesně to, z čeho se lineární výrazy skládají. Zakázaný je jen součin dvou proměnných. Díky tomu umíš lineárně „vyfiltrovat“ skupinu: součet $\sum_j \sum_i q_{i,4}\, m_i^j$ počítá jen odnesené poklady skupiny 4.
Označme si pro skupinu $g$ počet odnesených kusů (jen zkratka zápisu, ne nová proměnná):
$$S_g \;=\; \sum_{j=1}^{k} \sum_{i=1}^{n} q_{i,g}\, m_i^j.$$Zkus sám: podmínka (a) chce „aspoň jeden poklad ze skupiny 1 a aspoň jeden ze skupiny 2“. Jak to zapíšeš přes $S_g$?
„Aspoň jeden ze skupiny“ = OR přes všechny binárky skupiny — a OR už znáš z [L1.3] jako $\sum \ge 1$. Tady tedy rovnou:
$$S_1 \ge 1, \qquad S_2 \ge 1.$$Žádná pomocná proměnná, žádné big-M. „Aspoň jeden z mnoha“ je v ILP ta levná strana logiky. A protože zadání nerozlišuje skrýše ani konkrétní muže („to any of his hideouts“), sčítá se přes všechny muže $j$ — je jedno, kdo to ponese.
Implikace mezi skupinami: „skupina 4 jen se skupinou 3“
Podmínka (b): „transport any treasure from group 4 only if at least some treasure from group 3 is being transported“. Přeloženo do řeči součtů:
$$\big(S_4 \ge 1\big) \;\Longrightarrow\; \big(S_3 \ge 1\big).$$Zkus sám: v [L1.3] byla implikace $x \Rightarrow y$ hotová jedinou nerovností $y \ge x$. Můžeš sem napsat $S_3 \ge S_4$ a mít hotovo?
Nemůžeš! Trik $y \ge x$ stojí na tom, že $x, y \in \{0,1\}$. Tady jsou ale obě strany součty — celá čísla klidně 0 až $n$. Nerovnost $S_3 \ge S_4$ říká „skupiny 3 se veze aspoň tolik kusů co skupiny 4“ — to je mnohem přísnější podmínka než zadání. Příklad: odnést 5 pokladů skupiny 4 a 1 poklad skupiny 3 zadání povoluje („at least some treasure from group 3“), ale $S_3 \ge S_4$ by to zakázalo ($1 \ge 5$ neplatí) — a uřízl by sis přípustná (možná optimální!) řešení.
Implikace tu není mezi proměnnými, ale mezi událostmi „$S_4 \ge 1$“ a „$S_3 \ge 1$“. Události nejdřív musíš zhmotnit do binárek.
Nebezpečná polopravda: „implikace = $y \ge x$, vždycky“$y \ge x$ je implikace jen mezi binárkami. Jakmile jsou strany implikace tvrzení o součtech/skupinách („něco ze skupiny 4 se veze“), napsat nerovnost přímo mezi součty ($S_3 \ge S_4$) model zpřísní — vyžaduješ počet kusů, ne existenci. Správný postup: každou stranu nejdřív převést na indikátorovou binárku přes big-M [L1.4] a teprve mezi binárkami použít $y \ge x$ z [L1.3].
Zaveď tedy indikátory skupin $\delta_3, \delta_4 \in \{0,1\}$ (ruční řešení 2023 jim říkalo $trans_3, trans_4$) s významem „ze skupiny se něco veze“. Otázka za všechny body: kterým směrem musíš binárku k součtu přivázat?
Zkus sám: plná ekvivalence „$\delta_g = 1 \iff S_g \ge 1$“ potřebuje dvě vazby. Pro implikaci $(S_4 \ge 1) \Rightarrow (S_3 \ge 1)$ ale stačí z každé strany jen jedna. Která — a proč právě ta?
Rozmysli, co která strana implikace potřebuje vynutit:
- Levá strana (předpoklad): jakmile se veze cokoli ze skupiny 4, musí se $\delta_4$ zvednout na 1 — tedy „$S_4 \ge 1 \Rightarrow \delta_4 = 1$“. To je big-M vazba $$S_4 \le M \cdot \delta_4$$ (pro $\delta_4 = 0$ vynucuje $S_4 = 0$; pro $\delta_4 = 1$ nic neomezuje). Opačný směr „$\delta_4 = 1 \Rightarrow S_4 \ge 1$“ nepotřebuješ: kdyby solver nastavil $\delta_4 = 1$ zbytečně, jen by si přidal povinnost vézt skupinu 3 — nikdy si tím nepomůže, tak to neudělá.
- Pravá strana (závěr): jakmile $\delta_3 = 1$, musí se skupina 3 opravdu vézt — tedy „$\delta_3 = 1 \Rightarrow S_3 \ge 1$“: $$\delta_3 \le S_3.$$ Opačná vazba ($S_3 \le M\delta_3$) je tu zase zbytečná: vézt skupinu 3 „navíc“ při $\delta_3 = 0$ nikdy neporuší zadání.
A mezi binárkami už klasicky [L1.3]: $\delta_4 \Rightarrow \delta_3$, tedy
$$\delta_4 \le \delta_3.$$Řetěz dohromady: $S_4 \ge 1 \Rightarrow \delta_4 = 1 \Rightarrow \delta_3 = 1 \Rightarrow S_3 \ge 1$. ✓
Zkus sám: jak velké musí být $M$ ve vazbě $S_4 \le M\delta_4$?
Při $\delta_4 = 1$ musí být nerovnost splnitelná pro každou dosažitelnou hodnotu $S_4$. Maximum $S_4$ je počet pokladů skupiny 4, tedy $M = \sum_i q_{i,4}$ (hrubší, ale vždy bezpečná volba je $M = n$). Jako vždy u big-M [L1.4]: dost velké, aby „vypnuté“ omezení nic neřezalo, ale ne nesmyslně obří.
Elegantní zkratka: big-M bez binárky
U téhle konkrétní implikace se dá ušetřit celý indikátorový aparát. Podívej se na jedinou nerovnost:
$$S_4 \;\le\; M \cdot S_3, \qquad M = \textstyle\sum_i q_{i,4}.$$Zkus sám: proč tohle funguje, i když $S_3$ není binárka? Co se stane pro $S_3 = 0$ a co pro $S_3 \ge 1$?
$S_3$ je nezáporný celočíselný součet — umí jen hodnoty $0, 1, 2, \dots$ A to stačí:
- $S_3 = 0$: nerovnost dá $S_4 \le 0$, tedy nic ze skupiny 4 se neveze — přesně kontrapozice implikace;
- $S_3 \ge 1$: pravá strana je aspoň $M$ = maximum dosažitelného $S_4$, nerovnost nic neomezuje.
Roli binárního přepínače tu sehrál sám součet $S_3$ — big-M trik [L1.4] s „přepínačem zadarmo“. Obě varianty (indikátory i zkratka) jsou ekvivalentní a obě jsou korektní ILP formulace zadání; zkratka je rychlejší na napsání a má méně míst, kde udělat chybu.
Zbytek úlohy už znáš
Podmínka (c) — „maximal difference in the total prices transported by the individual men is at most $P_{max}$“ — je doslova rozptyl max−min přes jednu pevnou množinu hodnot z [L1.8]: hodnoty jsou ceny nákladů jednotlivých mužů $P_j = \sum_i p_i\, m_i^j$.
Zkus sám: kolik je „total price transported by man $j$“, když muž $j$ nenese vůbec nic? Počítá se do rozdílu?
$P_j = \sum_i p_i \cdot 0 = 0$ — a počítá se: zadání mluví o „individual men“, tedy o všech $k$ mužích. Konstrukce z [L1.8] ($P^{+} \ge P_j$, $P^{-} \le P_j$ pro všechna $j$, $P^{+} - P^{-} \le P_{max}$) to zachytí sama od sebe, protože nerovnosti běží přes všechny muže včetně prázdných. Prakticky to znamená: jakmile jeden muž nese hodně a jiný nic, rozdíl je celý náklad toho prvního.
Kritérium (d) je prostá maximalizace ceny odneseného [L1.1] — díky omezení „každý poklad nejvýš jednou“ bez dvojího započtení. Celý model poskládáš v úloze T01 níže.
Key takeaways — L1.12- Příslušnost do skupin = předpočítané konstanty $q_{i,g} \in \{0,1\}$ (ne proměnné!). Součin $q_{i,g} \cdot m_i^j$ je lineární (konstanta × proměnná) a umí „vyfiltrovat“ skupinu: $S_g = \sum_j \sum_i q_{i,g}\, m_i^j$ = počet odnesených kusů skupiny $g$.
- „Aspoň jeden ze skupiny“: $S_g \ge 1$ — OR přes mnoho binárek je obyčejný součet, žádné big-M.
- Implikace mezi skupinami NENÍ $y \ge x$ na součtech: $S_3 \ge S_4$ vyžaduje počet, ne existenci — zpřísňuje model. Správně přes indikátory $\delta_4, \delta_3 \in \{0,1\}$: $S_4 \le M\delta_4$, $\;\delta_3 \le S_3$, $\;\delta_4 \le \delta_3$ [L1.3]+[L1.4].
- Z vazby binárka↔součet stačí jen směr, který implikace potřebuje: předpoklad tlačí indikátor nahoru ($S \le M\delta$), závěr tlačí součet nahoru ($\delta \le S$). Druhé směry solver nikdy nezneužije.
- Zkratka bez binárky: $S_4 \le M \cdot S_3$ — funguje, protože $S_3$ je nezáporné celé číslo ($S_3 = 0 \Rightarrow S_4 = 0$, $S_3 \ge 1 \Rightarrow$ volno). $M$ = počet pokladů skupiny 4.
FOTO checkpoint
zdroj: zkouška KO 2023 (T04)
“Alibaba and his $k$ men have raided an ancient tomb. Inside, there were $n$ treasures $T = \{t_1, \ldots, t_n\}$. Each treasure $t_i$ has some weight $w_i \in \mathbb{R}^+$ and price $p_i \in \mathbb{R}^+$. Each treasure belongs to one of four groups $G = \{1, 2, 3, 4\}$, where $g_i \in G$ denotes the group of treasure $t_i$. Each of Alibaba's $k$ men will move part of the loot to one of the Alibaba's hideouts. The maximal weight that man $j \in \{1, 2, \ldots, k\}$ can carry is $u_j \in \mathbb{R}^+$.
Alibaba wants to:
a) transport at least one treasure from group 1 and at least one treasure from group 2 to any of his hideouts;
b) transport any treasure from group 4 only if at least some treasure from group 3 is being transported to any of the hideouts;
c) distribute the loot such that the maximal difference in the total prices transported by the individual men is at most $P_{\max} \ge \max_i\{p_i\} - \min_i\{p_i\}$;
d) maximize the total price of the transferred treasures.
Design an ILP model to solve the given loot distribution problem.”
FOTO checkpointTuhle úlohu vyřeš celou NA PAPÍR — od prázdného listu, bez koukání do lekce ani do řešení, ideálně na čas (na zkoušce zhruba 15–20 minut). Pak mi pošli fotku — zkontroluju ti ji a vytknu chyby přesně jako hodnotitel.
a) Co je v zadání?
$n$ pokladů (váha $w_i$, cena $p_i$, skupina $g_i \in \{1,2,3,4\}$ — vše dané), $k$ mužů s nosnostmi $u_j$. Rozhoduješ, kdo odnese co (něco smí zůstat v hrobce). Čtyři požadavky: (a) veze se aspoň jeden kus ze skupiny 1 a aspoň jeden ze skupiny 2; (b) skupina 4 smí jet jen tehdy, jede-li i něco ze skupiny 3; (c) rozdíl cen nákladů mezi muži nejvýš $P_{max}$ (daný parametr; nerovnost $P_{max} \ge \max_i\{p_i\} - \min_i\{p_i\}$ je vlastnost dat, ne tvoje omezení); (d) maximalizuj cenu odneseného. Skrýše („hideouts“) jsou kulisa — žádná podmínka je nerozlišuje, v modelu se neobjeví.
b) Co k tomu budeme potřebovat?
- Tato lekce — konstanty $q_{i,g}$, „aspoň jeden ze skupiny“ ($S_g \ge 1$), implikace mezi skupinami (indikátory / zkratka $S_4 \le M S_3$).
- [L1.2] Přiřazovací struktura — proměnné $m_i^j$ a součtové omezení (tady „nejvýš jednou“).
- [L1.1] Rozpočtové omezení — nosnost mužů.
- [L1.3] + [L1.4] — implikace binárek a big-M vazby.
- [L1.8] Omezení rozptylu — rozdíl max−min cen nákladů ≤ $P_{max}$.
c) Jak nad úlohou uvažovat?
Postupuj jako u Wedding planu [L1.9]: rozsekej zadání na věty a každé přiřaď techniku. Kostra: jaké je elementární rozhodnutí? (muž × poklad → binárka; rovnost, nebo „nejvýš jednou“?) Pak věta po větě: (a) je levná strana logiky ($\sum \ge 1$), (b) je implikace mezi událostmi o součtech — pozor, ať ji nenapíšeš jako nerovnost mezi součty; rozmysli, kterým směrem vázat indikátory. U (c) si ujasni, čí hodnoty porovnáváš (cena nákladu každého muže — i prázdného) a použij pomocné $P^{+}, P^{-}$. Nezapomeň na nosnosti — jsou schované v úvodním odstavci, ne v seznamu (a)–(d).
d) Úplné řešení
Data (předpočítaná): $q_{i,g} = 1$, pokud $g_i = g$, jinak $0$; $\;M = \sum_{i} q_{i,4}$ (počet pokladů skupiny 4).
Proměnné:
$$m_i^j \in \{0,1\} \;\; \forall i, \forall j \;\;(\text{muž } j \text{ nese } t_i), \qquad \delta_3, \delta_4 \in \{0,1\}, \qquad P^{+}, P^{-} \in \mathbb{R}.$$Kostra — každý poklad nejvýš jednou a nosnosti:
$$\sum_{j=1}^{k} m_i^j \le 1 \quad \forall i, \qquad\qquad \sum_{i=1}^{n} w_i\, m_i^j \le u_j \quad \forall j.$$(a) aspoň jeden ze skupiny 1 a aspoň jeden ze skupiny 2: (zkratka $S_g = \sum_j \sum_i q_{i,g}\, m_i^j$)
$$S_1 \ge 1, \qquad S_2 \ge 1.$$(b) skupina 4 jen se skupinou 3 — indikátorová varianta:
$$S_4 \le M\,\delta_4, \qquad \delta_3 \le S_3, \qquad \delta_4 \le \delta_3.$$Řetěz: veze-li se cokoli ze 4, pak $\delta_4 = 1$ → $\delta_3 = 1$ → $S_3 \ge 1$. Ekvivalentní úsporná varianta (stejně korektní formulace): jediná nerovnost $S_4 \le M \cdot S_3$.
(c) rozdíl cen nákladů ≤ $P_{max}$ — konstrukce z [L1.8] nad hodnotami $P_j = \sum_i p_i\, m_i^j$:
$$P^{+} \ge \sum_{i=1}^{n} p_i\, m_i^j \quad \forall j, \qquad P^{-} \le \sum_{i=1}^{n} p_i\, m_i^j \quad \forall j, \qquad P^{+} - P^{-} \le P_{max}.$$Nerovnosti běží přes všechny muže — muž bez nákladu přispívá hodnotou $0$, takže $P^{-} \le 0$, a rozdíl ho korektně zahrne. Pro omezení „rozptyl ≤“ jsou jednostranné meze $P^{+}, P^{-}$ přesně to pravé (viz [L1.8]).
(d) kritérium:
$$\max \; \sum_{j=1}^{k} \sum_{i=1}^{n} p_i\, m_i^j.$$Dvojí započtení nehrozí — každý poklad nese nejvýš jeden muž. Tím je model kompletní: binárky $m_i^j$, dva indikátory, dvě spojité pomocné proměnné a samá lineární omezení.