Rozdíl / omezení rozptylu (max−min)
Prerekvizity: [L1.1] Cílová funkce a základní omezení. Navazujeme přímo na [L1.7] — ve Wedding plan nám z modelu zbývá poslední nevyřízená věta.
„Strany se smí lišit nejvýš o $D_{max}$“
Zkouškové zadání Wedding plan říká: „…for the sake of justice, the number of guests invited from the groom's side and the bride's side can differ by at most $D_{max}$.“ Označme počty pozvaných z obou stran (lineární výrazy v binárkách $x_i$ „host $i$ pozván“):
$$a = \sum_{i=1}^{n} gr(g_i)\,x_i \qquad b = \sum_{i=1}^{n} br(g_i)\,x_i.$$Podmínka „liší se nejvýš o $D_{max}$“ je $|a - b| \le D_{max}$. Jenže absolute value (absolutní hodnota) není lineární funkce — do ILP ji takhle napsat nesmíme.
Zkus sám: co přesně říká $|a - b| \le D$ o čísle $a - b$? Umíš to říct bez absolutní hodnoty?
$|t| \le D$ znamená přesně $-D \le t \le D$. Dosaď $t = a - b$ a roztrhni na dvě lineární nerovnosti:
$$a - b \le D \qquad \text{a zároveň} \qquad b - a \le D.$$První hlídá případ „$a$ je větší“, druhá případ „$b$ je větší“. Obě musí platit současně — a „současně“ (průnik, AND) je v ILP zadarmo: prostě napíšeš obě omezení pod sebe. Žádná binárka, žádné big-M.
Zkus sám: a šlo by stejně levně i „strany se musí lišit aspoň o $D$“, tedy $|a - b| \ge D$?
Ne! $|t| \ge D$ znamená „$t \ge D$ NEBO $t \le -D$“ — to je disjunkce, přípustná množina má díru uprostřed (je nekonvexní). „Nebo“ se v ILP platí binárním přepínačem a big-M [L1.4]:
$$a - b \ge D - M y, \qquad b - a \ge D - M(1 - y), \qquad y \in \{0,1\}.$$Zapamatuj si ten kontrast: $|{\cdot}| \le D$ je AND (zadarmo), $|{\cdot}| \ge D$ je OR (big-M). Směr nerovnosti rozhoduje o ceně.
Tím je Wedding plan kompletně pokrytý — celý model složíš v [L1.9]. Ale dvojice hodnot je jen začátek: co když se nesmí „rozjet“ víc než dvě hodnoty najednou?
Z dvojice na celou množinu: max − min
Zápočtový test 2021 chtěl rozdělit bankovky do čtyř skupin $S_1, \dots, S_4$ se součty $h_1, \dots, h_4$ tak, aby rozdíl mezi nejvyšším a nejnižším součtem nepřekročil limit $P$:
$$\max_j h_j \;-\; \min_j h_j \;\le\; P.$$Funkce $\max$ a $\min$ ale lineární nejsou — stejný problém jako u absolutní hodnoty.
Zkus sám: umíš to vyřešit jen tím, co už znáš z první sekce?
Ano — „max − min ≤ P“ platí právě tehdy, když se žádné dvě hodnoty neliší o víc než $P$. Stačí tedy napsat $|h_j - h_k| \le P$ pro všechny dvojice, tj. dvě nerovnosti na dvojici:
$$h_j - h_k \le P \quad \forall j \ne k.$$Pro 4 skupiny je to $\binom{4}{2} \cdot 2 = 12$ nerovností. Funguje to, ale počet omezení roste kvadraticky s počtem skupin — a hlavně existuje elegantnější konstrukce, kterou používá vzorové řešení a kterou musíš umět: pomocné proměnné.
Zkus sám: zaveď novou proměnnou $h_{max}$, která má „držet maximum“. Jakými lineárními omezeními ji přivážeš k hodnotám $h_1, \dots, h_4$?
Maximum je nejmenší číslo, které je $\ge$ všem hodnotám. Lineárně umíme zařídit tu druhou půlku:
$$h_{max} \ge h_j \qquad \forall j \in 1..4.$$Symetricky pro minimum: $h_{min} \le h_j$ pro všechna $j$. A samotné omezení rozptylu je pak jediná nerovnost:
$$h_{max} - h_{min} \le P.$$Celkem $2 \cdot 4 + 1 = 9$ omezení a dvě pomocné proměnné — a počet roste jen lineárně s počtem skupin.
Na konkrétním (nevyhovujícím) rozdělení: součty skupin $h = (9, 12, 10, 14)$, celkový součet $45$, limit $P = 0.1 \cdot 45 = 4.5$:
Pozor: $h_{max}$ NENÍ rovno maximu
V konstrukci je schovaná jemnost, na kterou se u ústní zkoušky dobře ptá.
Zkus sám: omezení říká jen $h_{max} \ge h_j$. Co brání solveru nastavit $h_{max}$ třeba na milion? A vadí to?
Nebrání mu nic — $h_{max}$ je jen horní mez hodnot, ne jejich maximum (a $h_{min}$ jen dolní mez). Ale nevadí to, protože nerovnost $h_{max} - h_{min} \le P$ tlačí proti ulétnutí:
- Pokud řešení splní $h_{max} - h_{min} \le P$, pak skutečný rozptyl je ještě menší: $\max_j h_j - \min_j h_j \le h_{max} - h_{min} \le P$. ✓
- Naopak pokud rozdělení má rozptyl $\le P$, solver smí položit $h_{max} = \max_j h_j$ a $h_{min} = \min_j h_j$ a omezení projde. ✓
Přípustná rozdělení jsou tedy přesně ta správná — konstrukce je korektní, i když se $h_{max}$ maximu jen „umí rovnat“, nemusí.
Zkus sám: a fungovala by stejná konstrukce pro opačný požadavek „rozptyl musí být ASPOŇ $P$“, tedy $h_{max} - h_{min} \ge P$?
Ne! Právě proto, že $h_{max}$ smí ulétnout nahoru (a $h_{min}$ dolů), splní solver $h_{max} - h_{min} \ge P$ vždy — třeba $h_{max} = 10^6$, $h_{min} = 0$ — aniž by skutečné hodnoty cokoli plnily. Omezení by bylo bezzubé.
Stejná logika říká, kdy konstrukci smíš dát do kritéria: $\min\,(h_{max} - h_{min})$ funguje (minimalizace stlačí meze až na skutečné max/min), $\max\,(h_{max} - h_{min})$ ne. Pomocná proměnná funguje jen ve směru, ve kterém ji omezení/kritérium „přitlačí“ k hodnotám. Srovnej s big-M [L1.4]: tam má $M$ tutéž roli jednostranné meze.
Nebezpečná polopravda: „max/min už umím“Konstrukce z této lekce zachycuje max/min přes JEDNU pevnou množinu hodnot — čtyři součty $h_1, \dots, h_4$, které v každém přípustném řešení existují vedle sebe. Něco úplně jiného je požadavek typu „nerovnost musí platit pro každou možnou volbu“ (worst-case přes všechny kombinace, např. „ať si student vybere kterékoli jedno jídlo denně…“). Tam žádná konečná množina hodnot „vedle sebe“ neleží a $h_{max} \ge h_j$ napsat nejde — je to jiná konstrukce, viz [L1.13]. Nezaměňuj!
Key takeaways — L1.8- $|a - b| \le D$ ⟺ dvě lineární nerovnosti $a - b \le D$ a $b - a \le D$ (AND, zadarmo). Pozor: $|a - b| \ge D$ je disjunkce (OR) → big-M [L1.4].
- max přes pomocnou proměnnou: $h_{max} \ge h_j$ pro všechna $j$ z dané množiny; min: $h_{min} \le h_j$; rozptyl pak $h_{max} - h_{min} \le P$ jedinou nerovností.
- $h_{max}$/$h_{min}$ jsou jen jednostranné meze, ne maximum/minimum samo — proto fungují pro „rozptyl $\le P$“ a pro $\min(h_{max} - h_{min})$ v kritériu, ale NE pro „rozptyl $\ge P$“ či $\max(h_{max} - h_{min})$.
- Rozsah platnosti: jedna konkrétní množina hodnot (např. součty skupin). Min/max přes všechny kombinace voleb je jiná konstrukce — viz [L1.13].
“Formulate using ILP:
- Instance: Number of banknotes $n \in \mathbb{Z}^+$ and their values $p_1, \ldots, p_n$, where $p_{i \in 1..n} \in \mathbb{Z}^+$.
- Decision: Is there any division in 4 pairwise disjoint sets $S_1, S_2, S_3, S_4$ such that the difference between the highest value of the set and the lowest value of the set is equal or less than 10% of the sum of all banknotes value? Value of the set $S_j \subseteq \{1, \ldots, 4\}$ is given as $h_j = \sum_{i \in S_j} p_i$.”
Pozn.: zápis „$S_j \subseteq \{1, \ldots, 4\}$“ je takto v originále; míněno je zjevně $S_j \subseteq \{1, \ldots, n\}$ pro $j \in 1..4$ (skupiny jsou množiny bankovek).
a) Co je v zadání?
Rozhodovací (decision) úloha: existuje rozdělení $n$ bankovek do 4 navzájem disjunktních skupin tak, aby rozdíl mezi nejvyšším a nejnižším součtem skupiny byl nejvýš 10 % celkového součtu? „Disjoint division“ = každá bankovka padne právě do jedné skupiny. Nehledáme optimum, jen přípustnost — kritérium může být klidně $\min 0$.
b) Co k tomu budeme potřebovat?
- Tato lekce — $h_{max} \ge h_j$, $h_{min} \le h_j$, $h_{max} - h_{min} \le P$.
- [L1.2] Přiřazovací struktura — $x_{ij}$ a „každé $i$ právě jednou“: $\sum_j x_{ij} = 1$.
- [L1.1] Cílová funkce a základní omezení — jak se zapisuje decision úloha.
c) Jak nad úlohou uvažovat?
Jaká binárka popíše „bankovka $i$ patří do skupiny $j$“? Které omezení vynutí „pairwise disjoint“ a zároveň „každá bankovka někde je“? Jak z binárek lineárně poskládáš součet skupiny $h_j$? Limit „10 % of the sum of all banknotes value“ — je to konstanta, nebo proměnná? (Hodnoty $p_i$ jsou parametry zadání!) A nakonec: dvě pomocné proměnné a tři druhy omezení z této lekce.
d) Úplné řešení
Dle vzorového řešení: $x_{ij} = 1$ ⟺ bankovka $i \in S_j$.
$$\begin{aligned} \min \quad & 0 \\ \text{subject to:} \quad & \\ & \sum_{i \in 1..n} x_{ij} \cdot p_i = h_j \quad j \in 1..4 \\ & \sum_{j \in 1..4} x_{ij} = 1 \quad i \in 1..n \\ & h_{min} \le h_j \quad j \in 1..4 \\ & h_{max} \ge h_j \quad j \in 1..4 \\ & h_{max} - h_{min} \le 0.1 \sum_{i \in 1..n} p_i \\ \text{parameters:} \quad & p_{i \in 1..n} \in \mathbb{Z}^+ \\ \text{variables:} \quad & x_{i \in 1..n,\, j \in 1..4} \in \{0,1\}, \;\; h_{max}, h_{min}, h_{j \in 1..4} \in \mathbb{Z}^+ \end{aligned}$$Komentáře:
- $\min 0$: decision úloha — zajímá nás jen, zda existuje přípustné řešení. Solver vrátí feasible/infeasible, to je odpověď ano/ne.
- $\sum_j x_{ij} = 1$ řeší obojí najednou: bankovka je aspoň v jedné skupině (pokrytí) a nejvýš v jedné (disjunktnost) — polovina přiřazovací struktury [L1.2] (druhou polovinu $\sum_i x_{ij} = 1$ tu nechceme: skupina smí mít víc bankovek).
- Pravá strana $0.1 \sum_i p_i$ je konstanta — hodnoty $p_i$ jsou parametry, ne proměnné. Omezení je tedy lineární; žádné násobení proměnných nehrozí.
- Proměnné $h_j$ jsou formálně zbytečné (jen zkratka za $\sum_i x_{ij} p_i$) — ale model s nimi je čitelnější a vzorové řešení je zavádí. Klidně je u zkoušky zaveď taky.
- Vzorové řešení deklaruje $h_{max}, h_{min}, h_j \in \mathbb{Z}^+$ (kladná celá čísla). Drobnost k zamyšlení: připouští-li instance prázdnou skupinu ($h_j = 0$), bylo by korektnější $\mathbb{Z}_0^+$ — u zkoušky se drž vzoru, ale věz, co píšeš.