L1.14 Kapitola K1 — ILP modelování (Slot 1) · [MUST]

Sousednost a prostorová omezení — Toys [FOTO]

Jedna nová věc Prostorové vztahy v řadě pozic — „hned vlevo“, „hned vedle“, „ne na kraji“ — se zapisují posunem indexu přiřazovacích binárek: $x_{1,j} = x_{2,j+1}$, zákaz pozice = vynulovaná binárka, a „vedle $t_5$ NEBO $t_6$“ implikací do součtu sousedních binárek.

Prerekvizity: [L1.2] Přiřazovací struktura, [L1.3] Modelování logiky, [L1.4] big-M, [L0.6] Párování a perfektní párování. Nosná úloha je zkoušková Toys assignment (termín 09.07.2021): hračky $t_1, \dots, t_n$ rozházené po pokoji se ukládají do řady boxů $b_1, \dots, b_n$ u zdi — a právě ta řada (box $b_j$ je vlevo od $b_{j+1}$) dává smysl slovům „vlevo“, „vedle“ a „na kraji“.

Kostra: přiřazení hraček do boxů

Data: vzdálenost hračky $t_i$ k boxu $b_j$ je konstanta $d_{ij} \ge 0$. Elementární rozhodnutí: která hračka skončí ve kterém boxu?

$$x_{ij} \in \{0,1\}, \qquad i, j \in 1 \dots n, \qquad x_{ij} = 1 \iff \text{hračka } t_i \text{ je v boxu } b_j.$$
Zkus sám: podmínky (i) „each box contains exactly one toy and each toy is stored in one box“ a kritérium (ii) „total distance minimized“ jsou čistá [L1.2]. Napiš je.

Oboustranná přiřazovací struktura — každý řádek i sloupec matice $x$ má součet 1:

$$\sum_{j=1}^{n} x_{ij} = 1 \quad \forall i \in 1 \dots n, \qquad\qquad \sum_{i=1}^{n} x_{ij} = 1 \quad \forall j \in 1 \dots n,$$

a kritérium je lineární součet konstanta × binárka:

$$\min\; z = \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}\, x_{ij}.$$

Tohle je assignment problem (přiřazovací problém) v čisté podobě — zapamatuj si ho, na konci lekce se k němu vrátíme jako ke grafové úloze.

Nová věc: poloha v řadě = index boxu

Podmínka (iii): „toy $t_1$ is assigned to the box immediately left to the box where $t_2$ is assigned“. Klíčový postřeh: boxy jsou očíslované podle polohy — $b_j$ je hned vlevo od $b_{j+1}$. Prostorový vztah dvou hraček je tedy vztah indexů jejich boxů.

Zkus sám: jak svázat binárky $x_{1,\cdot}$ a $x_{2,\cdot}$, aby $t_1$ byla hned vlevo od $t_2$?

„$t_2$ v boxu $b_{j+1}$ ⟺ $t_1$ v boxu $b_j$“ — události se musí trefit do posunutých indexů. Nejkratší zápis je rovnost binárek s posunem:

$$x_{1,j} = x_{2,j+1} \qquad \forall j \in 1 \dots n-1.$$

Stejně dobře funguje implikace $x_{1,j} \le x_{2,j+1}$ (spolu s řádkovými součty vystřelí přesně jednou) — rovnost je ale na písemce obvyklý a bezpečný zápis (přesně takhle je ve vzorovém řešení).

Zkus sám: stačí to? Najdi přiřazení, které všechny rovnosti $x_{1,j} = x_{2,j+1}$ splní, a přitom $t_1$ vlevo od $t_2$ NENÍ.

Polož $t_1$ do posledního boxu: $x_{1,n} = 1$. Pak $x_{1,j} = 0$ pro $j \le n-1$, takže všechny rovnosti říkají jen $x_{2,j+1} = 0$ — a $t_2$ tedy skončí v $b_1$. Všechny rovnosti platí, ale $t_1$ je na pravém kraji a $t_2$ na levém („přetečení“ přes okraj řady). Musíš okraj explicitně zakázat:

$$x_{1,n} = 0 \qquad (\text{a tím i } x_{2,1} = 0 \text{ — plyne z rovností a řádkových součtů; klidně napiš obě}).$$
Nebezpečná polopravda: „posun indexu stačí“

Každé omezení s posunutým indexem ($j+1$, $j-1$) má okrajový problém: pro $j = n$ index $j+1$ neexistuje, pro $j = 1$ neexistuje $j-1$. Samotné rovnosti/nerovnosti přes $j \in 1 \dots n-1$ nechají krajní binárky volné — a solver díru najde. Vždy se ptej: co se děje na krajích řady? Buď chybějící členy ber jako nulu, nebo krajní pozici explicitně vynuluj ($x_{1,n} = 0$).

Zkus sám (předkrm na [L1.15]): šlo by (iii) zapsat přes „číslo boxu hračky $t_i$“ jako jedno číslo?

Ano — číslo boxu hračky $t_i$ je lineární výraz $\sum_j j \cdot x_{ij}$ (právě jeden sčítanec je nenulový). Podmínka (iii) pak je jediná rovnost:

$$\sum_{j=1}^{n} j \cdot x_{2,j} = \sum_{j=1}^{n} j \cdot x_{1,j} + 1.$$

Elegantní — ale pozor: pro (v) „hned vedle“ bys potřeboval $|{\rm pozice}_4 - {\rm pozice}_5| = 1$ nebo $|{\rm pozice}_4 - {\rm pozice}_6| = 1$, a absolutní hodnota rovná se je sama o sobě disjunkce — zápis se rozpadne. Posun indexů je tady praktičtější. Systematicky se „výrazům z indexovaných binárek“ věnuje příští lekce [L1.15].

Zákaz krajních pozic

Podmínka (iv): „neither $t_5$ nor $t_6$ can be assigned to $b_1$ or $b_n$“.

Zkus sám: tohle je nejlevnější podmínka celé úlohy. Napiš ji.

Zakázaná volba = fixace binárky na nulu ([L1.3]):

$$x_{5,1} = x_{5,n} = x_{6,1} = x_{6,n} = 0.$$

Žádná logika, žádné big-M — čtyři proměnné prostě škrtneš. (Grafově řečeno: z úplného bipartitního grafu hračky–boxy odebereš čtyři hrany; hned se to bude hodit.)

Disjunkce: „vedle $t_5$ NEBO $t_6$“

Podmínka (v): „$t_4$ is in the box immediately next to $t_5$ or $t_6$“. „Immediately next“ = box o jedna vlevo, nebo o jedna vpravo — a k tomu volba svědka ($t_5$, nebo $t_6$). Vypadá to na ošklivou disjunkci; uvidíš, že má jednořádkové řešení.

Zkus sám: nejdřív jen „$t_4$ hned vedle $t_5$“. Když je $t_4$ v boxu $b_j$, co musí platit?

Pak $t_5$ sedí v $b_{j-1}$, nebo v $b_{j+1}$ — implikace „binárka ⟹ aspoň jedna z binárek“. Univerzální recept z [L1.3] (zakázaný řádek: $x_{4,j}=1$ a oba sousedi 0) dá:

$$x_{4,j} \;\le\; x_{5,j-1} + x_{5,j+1} \qquad \forall j \in 1 \dots n.$$

Pro $x_{4,j} = 0$ omezení nic nechce; pro $x_{4,j} = 1$ vynutí jedničku u souseda. Žádné big-M — pravá strana je součet binárek, sama je „dost velká“.

Zkus sám: a teď přidej „… NEBO $t_6$“. A nezapomeň na okraje řady.

NEBO mezi svědky = další sčítance na pravé straně (čím víc povolených svědků, tím volnější implikace):

$$x_{4,j} \;\le\; x_{5,j-1} + x_{5,j+1} + x_{6,j-1} + x_{6,j+1} \qquad \forall j \in 1 \dots n,$$

kde členy s neplatným indexem ($j-1 = 0$, $j+1 = n+1$) bereš jako nulu — tedy pro $j=1$ zůstanou jen členy $x_{\cdot,2}$, pro $j=n$ jen $x_{\cdot,n-1}$. To je přesně vzorové řešení z banku. Okraje tady fungují samy: $t_4$ v $b_1$ prostě potřebuje svědka v $b_2$.

Zkus sám: obecná zbraň na „NEBO mezi omezeními“ je big-M disjunkce [L1.4]. Jak by vypadala tady — a proč je horší?

(v) je disjunkce čtyř scénářů: $t_4$ hned vlevo od $t_5$ / vpravo od $t_5$ / vlevo od $t_6$ / vpravo od $t_6$. Čtyři scénáře vybereš dvěma selektorovými binárkami $y_1, y_2 \in \{0,1\}$ a tři nevybrané systémy vypneš přes $M$ — takhle to (s drobnými otazníky hodnotitele) stojí v reálné písemce z 09.07.2021:

$$\begin{aligned} y_2 M + y_1 M + x_{4,j} &\ge x_{5,j+1} \\ y_2 M + (1-y_1) M + x_{4,j} &\ge x_{5,j-1} \\ (1-y_2) M + y_1 M + x_{4,j} &\ge x_{6,j+1} \\ (1-y_2) M + (1-y_1) M + x_{4,j} &\ge x_{6,j-1} \end{aligned} \qquad \forall j$$

Čti první řádek pro $y_1 = y_2 = 0$: $x_{5,j+1} \le x_{4,j}$ pro všechna $j$, tedy „kdekoli je $t_5$, hned vlevo od ní sedí $t_4$“ — scénář aktivní. Pro ostatní volby $(y_1, y_2)$ ho člen $M$ vypne. Protože vše jsou binárky, stačí $M = 1$ — a velikost big-M vždy zdůvodni ([L1.4]). Okraje tu nezlobí jen díky (iv): $t_5$, $t_6$ nikdy nesedí v $b_1$ ani $b_n$, takže posunuté indexy pokryjí všechny jejich možné pozice.

Verdikt: funguje to, ale je to 4× víc nerovností, dvě proměnné navíc, kvantifikátor a okraje k pohlídání — hodnotitel u téhle verze nechal otazníky („$\le$ ?“, „kvantifikátor ?“): verze je delší, hůř čitelná a riskuješ, že hodnotitele nepřesvědčíš. Jednořádková součtová implikace je kratší a bezpečnější. Big-M disjunkci si šetři na případy, kdy NEBO spojuje obecné nerovnosti, ne binárky.

Most do K4: přiřazení = perfektní párování

Část (b) zadání říká: zahoď (iii) a (v) a „formalize the problem as an assignment problem (i.e., minimum weight perfect matching in complete bipartite graph whose sets have the same cardinality)“. Vzpomeň na [L0.6]: tam jsme si přesně tohle propojení slíbili.

Zkus sám: jak vypadá graf? Co jsou vrcholy, hrany, váhy — a kam se poděje podmínka (iv)?

Bipartitní graf $G = (T \cup B, E)$: nalevo hračky, napravo boxy, hrana $(t_i, b_j)$ s váhou $w(t_i, b_j) = d_{ij}$ pro každé povolené přiřazení. Perfektní párování vybere ke každé hračce právě jeden box a naopak — to je přesně dvojice součtových podmínek (i); minimalizace váhy párování = kritérium (ii).

Podmínka (iv) zůstává v platnosti (zadání škrtá jen (iii) a (v)) — a grafově je triviální: čtyři hrany prostě odebereš: $(t_5,b_1), (t_5,b_n), (t_6,b_1), (t_6,b_n) \notin E$. Pokud odpověď musí stát na úplném $K_{n,n}$, necháš je tam s prohibitivní váhou $w = M$ (dost velkou, aby do optima nikdy nevstoupily).

Tohle je klasický assignment problem (přiřazovací problém) a je řešitelný polynomiálně. Jak přesně — min-cost flow formulace a výpočet — je látka kapitoly K4 (lekce [L4.12]); dnes stačí umět převod: ILP (i)+(ii) ⟷ minimum weight perfect matching v $K_{n,n}$, zákazy pozic ⟷ odebrané hrany.

Key takeaways — L1.14
T01 Toys Assignment FOTO checkpoint zdroj: zkouška KO, termín 09.07.2021 (bank T02a)
Assignment (original, EN)

“There is a set of toys $T = \{t_1, t_2, \ldots, t_n\}$ scattered all around the room. By one of the walls, there is a row of boxes $B = \{b_1, b_2, \ldots, b_n\}$, where box $b_i$ is located left to $b_{i+1}$ for all $i \in \{1, 2, \ldots, n-1\}$. Distance of toy $t_i$ to box $b_j$ is $d_{i,j} \in \mathbb{R}_0^+ \quad \forall t_i \in T, b_j \in B$.

(a) Your goal is to design an ILP model to organize the toys to the boxes such that: (i) each box contains exactly one toy and each toy is stored in one box, (ii) the total distance between the toys and their assigned boxes is minimized, (iii) toy $t_1$ is assigned to the box immediately left to the box where $t_2$ is assigned, (iv) neither $t_5$ nor $t_6$ can be assigned to $b_1$ or $b_n$, (v) $t_4$ is in the box immediately next to $t_5$ or $t_6$.

(b) Disregard constraints (iii) and (v). Then, formalize the problem as an assignment problem (i.e., minimum weight perfect matching in complete bipartite graph whose sets have the same cardinality).”

FOTO checkpoint

Tuhle ú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; úloha byla za 4.75 bodu). Pak mi pošli fotku — zkontroluju ti ji a vytknu chyby přesně jako hodnotitel.

a) Co je v zadání?

$n$ hraček a řada $n$ boxů u zdi ($b_j$ je vlevo od $b_{j+1}$); vzdálenosti $d_{ij}$ jsou data. Část (a): postav ILP — (i) bijekce hračky↔boxy, (ii) minimalizuj součet vzdáleností, (iii) $t_1$ hned vlevo od $t_2$, (iv) $t_5$ a $t_6$ nesmí na kraje ($b_1$, $b_n$), (v) $t_4$ hned vedle $t_5$ nebo $t_6$. Část (b): bez (iii) a (v) úlohu zformuluj jako assignment problem — minimum weight perfect matching v úplném bipartitním grafu se stejně velkými partitami.

b) Co k tomu budeme potřebovat?

  • Tato lekce — posun indexu pro „hned vlevo/vedle“, okrajové pojistky, zákaz pozic, disjunkce svědků součtem.
  • [L1.2] Přiřazovací struktura — binárky $x_{ij}$ a oba součty $=1$.
  • [L1.3] Modelování logiky — implikace „binárka ⟹ aspoň jedna z binárek“, fixace na 0.
  • [L1.4] big-M — jen pokud zvolíš disjunkční variantu (v) se selektory $y_1, y_2$.
  • [L0.6] Párování — perfect matching a jeho čtení jako přiřazení (část b).

c) Jak nad úlohou uvažovat?

Kostra je čistá [L1.2]: binárka hračka × box, dva součty, lineární kritérium. Pak ber podmínky po jedné a každou přelož na indexy: (iii) je posun o $+1$ — kterým směrem, a co se stane na kraji řady ($j = n$)? (iv) jsou čtyři škrtnuté proměnné. U (v) si nejdřív napiš implikaci „$t_4$ v $b_j$ ⟹ soused obsahuje svědka“ jen pro $t_5$, pak rozšiř NEBO o $t_6$ — a rozmysli, co s členy $x_{\cdot,0}$ a $x_{\cdot,n+1}$. V části (b) se ptej: které ILP podmínky jsou „matching zadarmo“ (i)+(ii), která se promítne do množiny hran (iv) — a proč (iv) pořád platí, když zadání škrtá jen (iii) a (v)?

d) Úplné řešení

(a) ILP model. Proměnné: $x_{ij} \in \{0,1\}$ $\forall i, j \in 1 \dots n$, $x_{ij} = 1$ ⟺ hračka $t_i$ je v boxu $b_j$. Parametry: $d_{ij} \in \mathbb{R}_0^+$, $n \in \mathbb{Z}^+$ (podmínky (iii)–(v) mluví o $t_1 \dots t_6$, předpokládáme tedy $n \ge 6$).

(ii) Kritérium:

$$\min\; z = \sum_{i=1}^{n} \sum_{j=1}^{n} d_{ij}\, x_{ij}.$$

(i) Každý box právě jedna hračka, každá hračka právě jeden box:

$$\sum_{i=1}^{n} x_{ij} = 1 \quad \forall j \in 1 \dots n, \qquad\qquad \sum_{j=1}^{n} x_{ij} = 1 \quad \forall i \in 1 \dots n.$$

(iii) $t_1$ hned vlevo od $t_2$ — posun indexu + okrajová pojistka:

$$x_{1,j} = x_{2,j+1} \quad \forall j \in 1 \dots n-1, \qquad x_{1,n} = 0, \qquad x_{2,1} = 0.$$

(Bez $x_{1,n} = 0$ by prošlo $t_1$ v $b_n$ a $t_2$ v $b_1$ — všechny rovnosti by platily naprázdno — říkaly by jen $0 = 0$.)

(iv) $t_5, t_6$ ne na krajích:

$$x_{5,1} = x_{5,n} = x_{6,1} = x_{6,n} = 0.$$

(v) $t_4$ hned vedle $t_5$ nebo $t_6$ — implikace do součtu sousedních binárek:

$$x_{4,j} \;\le\; x_{5,j-1} + x_{5,j+1} + x_{6,j-1} + x_{6,j+1} \quad \forall j \in 1 \dots n,$$

kde členy s neplatným indexem ($j - 1 = 0$, $j + 1 = n + 1$) se berou jako nula. Pro $x_{4,j} = 1$ musí mít aspoň jeden sousední box $t_5$ nebo $t_6$; pro $x_{4,j} = 0$ omezení nic nevynucuje.

Alternativa (v) přes big-M disjunkci [L1.4]: selektory $y_1, y_2 \in \{0,1\}$ vyberou jeden ze čtyř scénářů (vlevo/vpravo × $t_5$/$t_6$) a zbylé tři vypne $M$ (zde stačí $M = 1$, vše jsou binárky):

$$\begin{aligned} y_2 M + y_1 M + x_{4,j} &\ge x_{5,j+1} \\ y_2 M + (1-y_1) M + x_{4,j} &\ge x_{5,j-1} \\ (1-y_2) M + y_1 M + x_{4,j} &\ge x_{6,j+1} \\ (1-y_2) M + (1-y_1) M + x_{4,j} &\ge x_{6,j-1} \end{aligned} \qquad \forall j \in 1 \dots n.$$

Funguje (okraje kryje (iv)), ale součtová verze je kratší a na písemce bezpečnější.

(b) Assignment problem / minimum weight perfect matching. Bipartitní graf $G = (T \cup B, E)$; pro každé povolené přiřazení hrana $(t_i, b_j)$ s váhou $w(t_i, b_j) = d_{ij}$. Podmínka (iv) zůstává (škrtnuty jsou jen (iii) a (v)) a promítne se do množiny hran:

$$(t_5, b_1),\; (t_5, b_n),\; (t_6, b_1),\; (t_6, b_n) \;\notin\; E \qquad (n \ge 6),$$

nebo — má-li odpověď stát na úplném $K_{n,n}$ — tyto čtyři hrany dostanou prohibitivní váhu $w = M$ (dost velkou, aby do optima nevstoupily). Perfektní párování vybírá právě jednu hranu u každé hračky i každého boxu, je tedy přesně bijekce hračky↔boxy; minimalizace váhy párování minimalizuje celkovou vzdálenost při respektování (iv). Úloha je řešitelná polynomiálně — výpočet přes min-cost flow v K4 [L4.12].

← Předchozí L1.13 · Worst-case omezení přes kombinace