Linearizace absolutní hodnoty (min vs. max)

Pokrytí hodiny $i$ označme $c_i = \sum_{j=i-7}^{i} x_{j \bmod 24}$ (lineární výraz v $x$). Na každou z 24 absolutních hodnot jedna pomocná proměnná $z_i$:

$$\begin{aligned} \min \quad & \sum_{i=0}^{23} z_i \\ \text{subject to:} \quad & d_i - \sum_{j=i-7}^{i} x_{j \bmod 24} \;\le\; z_i \qquad i \in 0..23 \\ & \sum_{j=i-7}^{i} x_{j \bmod 24} - d_i \;\le\; z_i \qquad i \in 0..23 \\ \text{variables:} \quad & x_{j \in 0..23} \in \mathbb{Z}_{\ge 0}, \qquad z_{i \in 0..23} \ge 0 \end{aligned}$$

Komentáře:

• Dvě nerovnosti na $z_i$ říkají $z_i \ge |d_i - c_i|$; minimalizace $\sum z_i$ pak v optimu každé $z_i$ stlačí přesně na $|d_i - c_i|$. Absolutní hodnota je v minimalizačním kritériu — trik je validní.
• Sčítací index $j \bmod 24$ řeší cykličnost: hodinu 2 pokrývají i směny začínající v 19, 20, …, 23 předchozího dne.
• $z_i \ge 0$ je zde redundantní (plyne z obou nerovností), ale zdrojový recept Eq. (2) ho uvádí — klidně ho piš taky.
• Sanity check ze zdroje: pro ukázkový vektor $\mathbf{d}$ z Lab 3 vyjde optimum $28$ (zatímco původní model „minimalizuj počet směn při pokrytí $\ge d_i$“ dává 55 směn s velkými přebytky kolem 4.–5. hodiny ranní).

Proměnné: $x_1, \ldots, x_4 \in \mathbb{Z}$; $y \in \{0,1\}$ (přepínač disjunkce), $s \in \{0,1\}$ (znaménkový přepínač pro $x_2$), $z_2 \in \mathbb{Z}$ (role $|x_2|$). Konstanta $M = 11000$ (zdůvodnění níže).

$$\begin{aligned} \max \quad & x_1 + z_2 \\ \text{subject to:} \quad & x_1 + x_2 + x_3 + x_4 \le 1000 + M y \\ & 3x_1 + 5x_2 + x_3 + 2x_4 \le 500 + M (1 - y) \\ & x_1 \ge 2 x_2 \\ & x_1 \ge x_3 \\ & x_1 = 4 x_4 \\ & z_2 \le x_2 + M(1 - s) \\ & z_2 \le -x_2 + M s \\ & -5000 \le x_i \le 1000 \quad i \in \{1,2,3\} \\ & 1 \le x_4 \le 1000 \\ \text{variables:} \quad & x_{i \in 1..4} \in \mathbb{Z}, \;\; z_2 \in \mathbb{Z}, \;\; y, s \in \{0,1\} \end{aligned}$$

Komentáře po podmínkách:

• Kritérium, $|x_1|$: z $x_1 = 4x_4$ a $x_4 \ge 1$ plyne $x_1 \ge 4 > 0$, takže $|x_1| = x_1$ — píšeme rovnou $x_1$, bez pomocné proměnné. To je přesně případ „vynucené znaménko“ z výkladu.
• Kritérium, $|x_2|$: znaménko $x_2$ vynucené NENÍ (meze dovolují $-5000$ až $1000$, omezení $x_1 \ge 2x_2$ ho neurčí). Maximalizujeme, takže $z_2$ musí být přivázané shora: pro $s = 1$ platí $z_2 \le x_2$ (větev $x_2 \ge 0$), pro $s = 0$ platí $z_2 \le -x_2$; druhá nerovnost je vždy uvolněná o $M$. Solver zvolí $s$ podle znaménka $x_2$ a maximalizace vytlačí $z_2 = |x_2|$. Pozor: zápis „$|x_2| \ge x_2$, $|x_2| \ge -x_2$“ z ručního řešení 2023 by při maximalizaci nechal $|x_2|$ utéct na horní mez (v jednom z přepisů řešení je ostatně přeškrtnutý) — viz nebezpečná polopravda této lekce.
• (1) disjunkce: big-M přepínač [L1.4]: $y = 1$ vypne první nerovnost, $y = 0$ druhou. Volba $M$: vypnutá nerovnost musí být splnitelná pro všechny hodnoty v mezích (5). Nejhorší levá strana první nerovnosti je $4 \cdot 1000 = 4000$ (potřeba $M \ge 3000$), druhé $3000 + 5000 + 1000 + 2000 = 11000$ (potřeba $M \ge 10500$). Bereme $M = 11000$. Ruční řešení 2023 psalo $M = 4 \cdot 1000$ — to pro druhou nerovnost nestačí a zbytečně by ořezalo přípustnou množinu.
• (2) maximum: $x_1 \ge \max\{2x_2, x_3\}$ ⟺ $x_1 \ge 2x_2$ A ZÁROVEŇ $x_1 \ge x_3$ — „aspoň maximum“ = „aspoň každý z výrazů“, konjunkce je v ILP zadarmo (srovnej [L1.8]; systematicky v [L1.11]).
• (3) poměr: $\frac{x_1}{x_4} = 4$ ⟺ $x_1 = 4 x_4$. Dělení nulou nehrozí, protože (5) vynucuje $x_4 \ge 1$ — obecné ošetření „$x_4 \ne 0$“ ukáže [L1.11].
• Sanity check: optimum je $x_1 = 1000$ ($x_4 = 250$), $x_2 = -5000$ ($s = 0$, $z_2 = 5000$), např. $x_3 = -5000$, $y = 1$ (platí druhá nerovnost: $3000 - 25000 - 5000 + 500 = -26500 \le 500$ ✓); hodnota kritéria $1000 + 5000 = 6000$.