Assignment problem přes MCF + min-weight perfect matching
Tahle lekce splácí dluh, který se táhne od [L0.6] („min-weight perfect matching — výpočet až v K4“), přes Toys assignment v [L1.14] až po Christofidese [L3.10]. Ingredience už máš všechny: v [L4.9] jsi bipartitní párování počítal přes max flow (ale bez cen — šlo jen o kolik hran), v [L4.10] jsi tokům přidal ceny a v [L4.11] ses naučil MCF řešit. Dnes to celé sesadíme dohromady — a uvidíš, že „nejlevnější přiřazení“ je jen MCF v síti, kterou už umíš nakreslit.
Problém d) ze slidu 38: assignment = min-weight perfect matching
Slide 38 vyjmenoval čtyři párovací problémy (citovali jsme je v [L4.9], kde jsme vyřešili problém b). Dnes je na řadě poslední z nich:
d) Minimum Weight Perfect Matching in a complete bipartite graph whose parts have the same number of nodes. This problem is also called an Assignment Problem and it is a special case of problem c) and also a special case of the minimum cost flow problem. These problems can be solved in polynomial time.
Vstupem je úplný bipartitní graf $K_{n,n}$ s partitami $X$, $Y$, $|X| = |Y| = n$, a cena $d_{ij} \ge 0$ pro každou hranu $(i, j) \in X \times Y$. Hledáme perfektní párování [L0.6] s nejmenším součtem cen — tedy bijekci $X \leftrightarrow Y$, kde každé spárování $i \leftrightarrow j$ stojí $d_{ij}$. Slide rovnou prozrazuje strategii: je to speciální případ minimum cost flow.
Zkus sám: konstrukci vlastně už znáš. Z [L4.9] umíš síť $s \to X \to Y \to t$ s kapacitami 1, která počítá kardinalitu párování (žádné ceny). Z [L4.10] víš, že MCF přidává hranám ceny $c$ a uzlům bilance $b$. Jak ty dvě věci složit, aby z optimálního toku vypadlo nejlevnější perfektní párování?
Vezmi síť z [L4.9] beze změny kapacit (všude $l = 0$, $u = 1$) a dvě věci dolaď: ① ceny — prostřední hrana $i \to j$ dostane cenu $c(i,j) = d_{ij}$, krajní hrany $s \to i$ a $j \to t$ cenu $0$ (samotné „zapojení“ úkolu nic nestojí); ② perfektnost vynutíš bilancemi — $b(s) = n$, $b(t) = -n$, ostatní uzly $0$. Každý přípustný tok pak musí protlačit $n$ jednotek, tj. nasytit všechny krajní hrany — každé $i$ se s někým spáruje. MCF mezi takovými toky vybere ten s nejmenším $\sum d_{ij}$. Kdybys bilance nedal a chtěl jen „co nejlevnější tok“, vyhraje nulový tok za 0 — prázdné párování!
Konstrukce ze slidu 41
We have $n$ employees and $n$ tasks and we know the cost of execution for each possible employee-task pair.
Goal: Assign one task per employee while minimizing the total cost.
Can be solved by transformation to Minimum Cost Flow problem. Example: costs of execution of tasks 1, 2, 3 by employees A, B, C:
$$\begin{array}{c|ccc} & A & B & C \\ \hline 1 & 6 & 2 & 4 \\ 2 & 3 & 1 & 3 \\ 3 & 5 & 3 & 4 \end{array}$$
Add source $s$, sink $t$ and related edges with weight and orientation.
Síť pro příklad ze slidu (úkoly $1, 2, 3$ = partita $X$, zaměstnanci $A, B, C$ = partita $Y$):
Formálně: $G' = (\{s, t\} \cup X \cup Y,\ E')$ s hranami $s \to i$ pro $i \in X$, $i \to j$ pro $(i,j) \in X \times Y$ a $j \to t$ pro $j \in Y$; všude $l = 0$, $u = 1$; ceny $c(s,i) = c(j,t) = 0$ a $c(i,j) = d_{ij}$; bilance $b(s) = n$, $b(t) = -n$, jinde $0$. Pětice $(G', l, u, c, b)$ je přesně vstup MCF z [L4.10].
Zkus sám: proč je optimální tok téhle sítě vždycky rovnou párování — tedy proč z něj přečteš $x_{ij} = f(i,j) \in \{0, 1\}$ a žádná „půlka úkolu“ ti nevyleze?
Dva kroky. ① Celočíselnost: meze i bilance jsou celočíselné, takže existuje celočíselný optimální tok (Integral Flow Theorem, slide 17 — citovali jsme ho v [L4.5]; cycle canceling ho navíc sám od sebe najde, protože startuje z celočíselného toku a augmentuje o celé $\gamma$). S kapacitou $u = 1$ pak $f(i,j) \in \{0, 1\}$. ② Stupně: do uzlu $i \in X$ přiteče po hraně $s \to i$ právě 1 (krajní hrany jsou nasycené, protože $b(s) = n$ a hran ze zdroje je přesně $n$), takže z Kirchhoffa [L4.1] odteče právě 1 — uzel $i$ si vybere právě jednoho partnera $j$. Symetricky každé $j$ pošle do $t$ právě 1. Hrany s $f = 1$ uprostřed tedy tvoří perfektní párování a cena toku $= \sum_{(i,j):\, f(i,j)=1} d_{ij}$ je přesně jeho váha.
„Alternatively we can solve the assignment problem by Hungarian Alg.“ — Maďarský (Hungarian) algoritmus (slidy 42–48) je ale ze zkoušky 2026 výslovně vyloučen. U zkoušky assignment řeš výhradně přes MCF + cycle canceling; Hungarian tu proto nevykládáme vůbec.
Běh: cycle canceling na příkladu ze slidu 41
Krok 1 cycle cancelingu [L4.11] chce přípustný tok. Tady ho máš zadarmo: libovolné přiřazení (permutace) je přípustný tok — žádnou redukci z [L4.6] nepotřebuješ. Vezmeme „diagonálu“ $1 \to A$, $2 \to B$, $3 \to C$ za $6 + 1 + 4 = 11$ a necháme algoritmus, ať ji zlevní.
Zkus sám: reziduální graf $G_f$ téhle sítě má i uzly $s$, $t$ a jejich hrany. Rozmysli, proč při hledání záporného cyklu můžeme $s$ a $t$ úplně ignorovat a kreslit jen bipartitní prostředek.
Každý přípustný tok nasytí všechny krajní hrany ($b(s) = n$ = počet hran ze zdroje). Dopředné reziduální hrany $s \to i$ a $j \to t$ mají tedy $u_f = u - f = 0$ a v $E_f$ nejsou; existují jen zpětné $i \to s$ a $t \to j$. Jenže pak do $s$ hrany jen vstupují a žádná z něj nevychází — $s$ nemůže ležet na žádném cyklu (a $t$ zrcadlově: jen výstupní hrany). Všechny cykly $G_f$ tedy žijí mezi $X$ a $Y$: střídají dopřednou nepárovací hranu $i \to j$ (cena $+d_{ij}$) a zpětnou párovací $j' \to i'$ (cena $-d_{i'j'}$). To je přesně M-alternating cyklus ze slidu 39 — augmentace po záporném cyklu je výměna párovacích hran, která sníží váhu párování.
Zkus sám: ověř výsledek hrubou silou — permutace tří prvků je jen šest. Vyjde opravdu 9 jako minimum?
$1A2B3C: 6+1+4=11$; $1B2A3C: 2+3+4=\mathbf{9}$; $1B2C3A: 2+3+5=10$; $1C2A3B: 4+3+3=10$; $1C2B3A: 4+1+5=10$; $1A2C3B: 6+3+3=12$. Minimum je jediné: $\{1{-}B,\ 2{-}A,\ 3{-}C\}$ za $\mathbf{9}$ — přesně to, co vrátil cycle canceling. (Pro $n = 3$ si to enumerací ověříš, pro $n = 50$ už ne — proto polynomiální MCF.)
Nebezpečné polopravdy1) Hungarian algoritmus u zkoušky nepoužívej — je vyloučen; assignment = MCF + cycle canceling. 2) Bez bilancí $b(s) = n$, $b(t) = -n$ to nefunguje: „nejlevnější tok“ bez požadavku na množství je nulový tok za 0. Perfektnost párování vynucují právě bilance (ekvivalentně lze dát $l = 1$ na krajní hrany). 3) Ceny $d_{ij}$ patří jen na prostřední hrany; krajní mají $c = 0$. Kdo napíše ceny i na krajní hrany, posune cenu každého řešení o konstantu — optimum přežije, ale hodnota „minimální ceny“ bude špatně. 4) Min-weight perfect matching (d) ≠ min-weight matching (c): problém c) hledá nejlevnější mezi párováními maximální kardinality v libovolném grafu; d) chce perfektní párování v $K_{n,n}$ se stejně velkými partitami. U zkoušky cituj přesně problém d). 5) „Seřaď a spáruj“ není univerzální recept: pravidlo „$i$-tý nejkratší s $i$-tým nejdelším“ je optimální jen pro speciální struktury cen (School Bus, úloha T03 — funguje díky tvaru $\max\{0, x - D\}$). Pro obecnou matici $d_{ij}$ žádné třídicí pravidlo neexistuje — musíš spustit MCF.
Key takeaways — L4.12- Assignment problem = min-weight perfect matching v $K_{n,n}$ se stejně velkými partitami [L0.6] = speciální případ MCF (slide 38 d); řešitelný polynomiálně.
- Konstrukce (slide 41): síť $s \to X \to Y \to t$; všude $l = 0$, $u = 1$; ceny $c = d_{ij}$ jen uprostřed, krajní $c = 0$; bilance $b(s) = n$, $b(t) = -n$. Celočíselnost [L4.5] + Kirchhoff [L4.1] ⟹ tok = perfektní párování, $x_{ij} = f(i,j)$.
- Řeš cycle cancelingem [L4.11]: start = libovolná permutace; $s$ a $t$ na žádném cyklu neleží, záporné cykly jsou M-alternating cykly v bipartitní části a augmentace = výměna párovacích hran.
- Hungarian algoritmus je ze zkoušky vyloučen — assignment se řeší výhradně přes MCF.
- Třídicí pravidlo „$i$-tý nejkratší ranní + $i$-tý nejdelší odpolední“ je optimální pro overtime ceny $\max\{0, m_i + a_j - D\}$ (exchange argument, T03) — pro obecné $d_{ij}$ nic takového neplatí.
We have $n$ employees and $n$ tasks and we know the cost of execution for each possible employee-task pair. Goal: Assign one task per employee while minimizing the total cost. The assignment problem can be solved by transformation to the minimum cost flow problem. The source slide uses the example of execution costs of tasks $1, 2, 3$ by employees $A, B, C$:
$$\begin{array}{c|ccc} & A & B & C \\ \hline 1 & 6 & 2 & 4 \\ 2 & 3 & 1 & 3 \\ 3 & 5 & 3 & 4 \end{array}$$
Study task: Formulate the minimum-cost assignment problem as a minimum-cost flow problem. Define the source, sink, balances, capacities, costs, and how the chosen employee-task pairs are read from the flow.
a) Co je v zadání?
Učebnicová podoba dnešní lekce: vzít přiřazovací problém (matice cen $3 \times 3$) a předvést kompletní převod na MCF — síť, meze, ceny, bilance — plus říct, jak se z optimálního toku přečte výsledné přiřazení.
b) Co k tomu budeme potřebovat?
- Tato lekce — konstrukce + běh (takeaways).
- [L4.10] Minimum Cost Flow + reziduální graf s cenami — co je pětice $(G, l, u, c, b)$.
- [L4.11] Cycle canceling — když chce zkoušející i výpočet.
- [L4.5] — Integral Flow Theorem (proč tok = párování).
c) Jak nad úlohou uvažovat?
Odpověz strukturovaně po složkách pětice $(G', l, u, c, b)$ — zkoušející chce vidět, že žádnou nezapomeneš. Pak jedna věta o celočíselnosti (bez ní není jasné, proč tok dává $x_{ij} \in \{0,1\}$) a jedna o čtení výsledku. Pokud se chce i vyřešit příklad: start = libovolná permutace, cycle canceling.
d) Úplné řešení (konstrukce dle slidu 41; běh = stepper výše)
Konstrukce. $G' = (\{s, t\} \cup X \cup Y,\ E')$, kde $X$ = úkoly, $Y$ = zaměstnanci, $|X| = |Y| = n$:
- Hrany: $s \to i$ pro všechna $i \in X$; $i \to j$ pro všechny dvojice $(i, j) \in X \times Y$; $j \to t$ pro všechna $j \in Y$.
- Kapacity: $l(e) = 0$, $u(e) = 1$ pro všechny hrany.
- Ceny: $c(s, i) = 0$, $c(i, j) = d_{ij}$, $c(j, t) = 0$.
- Bilance: $b(s) = n$, $b(t) = -n$, $b(v) = 0$ jinak.
Proč to funguje: bilance vynutí tok velikosti $n$, takže všechny krajní hrany jsou nasycené; z Kirchhoffa si pak každý úkol vybere právě jednoho zaměstnance a naopak. Meze a bilance jsou celočíselné ⟹ existuje celočíselné optimum (Integral Flow Theorem, [L4.5]), tedy $f(i,j) \in \{0,1\}$. Čtení výsledku: $x_{ij} = f(i, j)$ — úkol $i$ dělá zaměstnanec $j$ právě když prostřední hranou $i \to j$ teče 1; cena toku $=$ cena přiřazení.
Výpočet na příkladu (cycle canceling, viz stepper v lekci): start $1{\to}A, 2{\to}B, 3{\to}C$ za 11; záporný cyklus $1 \to B \to 2 \to A \to 1$ s cenou $2 - 1 + 3 - 6 = -2$, $\gamma = 1$ → přiřazení $\{1{-}B, 2{-}A, 3{-}C\}$ za $\mathbf{9}$; v novém $G_f$ už žádný záporný cyklus není (všechny alternating cykly mají cenu $+1$ až $+3$) ⟹ optimum.
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^+ \ \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).
a) Co je v zadání?
Část (a) — plný ILP model s podmínkami (iii) a (v) — jsi vyřešil už v [L1.14]. Dnešní část (b) zahodí „polohové“ podmínky a ptá se přesně na dnešní pojem: zformalizuj zbytek (podmínky (i), (ii), (iv)) jako assignment problem, tj. min-weight perfect matching v úplném bipartitním grafu se stejně velkými partitami.
b) Co k tomu budeme potřebovat?
- Tato lekce — definice problému d) + MCF síť (takeaways).
- [L0.6] Párování a perfektní párování — pojmy.
- [L1.14] — část (a) a trik se zakázanými hranami.
- [L4.11] — kdyby se chtělo i „a jak to spočítáš?“.
c) Jak nad úlohou uvažovat?
Podmínky (i)+(ii) jsou doslova definice assignment problemu — stačí pojmenovat partity, váhy a co je přípustné řešení. Jediná práce je podmínka (iv): zákaz čtyř konkrétních dvojic. Graf má ale zůstat úplný (tak zní zadání) — jak zakázat hranu, aniž ji smažeš? Vzpomeň na big-M z [L1.14].
d) Úplné řešení (formulace dle vzorového rukopisného řešení zkoušky; úprava zákazů přes M a MCF dovětek — přiznáno)
Formulace. Bipartitní graf $K_{n,n} = (T \cup B, E)$: partita $T$ = hračky, partita $B$ = boxy, $|T| = |B| = n$; hrana $(t_i, b_j)$ s váhou $w_{ij} = d_{i,j}$ znamená „hračka $i$ leží v boxu $j$“. Přípustné uspořádání dle (i) = každá hračka v právě jednom boxu a obráceně = perfektní párování; (ii) = minimalizace $\sum_{(i,j) \in P} d_{i,j}$ → hledáme minimum weight perfect matching.
Podmínka (iv): dvojice $(t_5, b_1), (t_5, b_n), (t_6, b_1), (t_6, b_n)$ jsou zakázané. Buď tyto čtyři hrany z grafu odstraníme (vzorové řešení: „kompletní provázání s výjimkou hran $d_{5,1}, d_{5,n}, d_{6,1}, d_{6,n}$, $n \ge 6$“ — graf je pak „skoro kompletní“), nebo — chceme-li doslova úplný bipartitní graf, jak žádá zadání — jim necháme existenci a dáme prohibitivní váhu $w_{5,1} = w_{5,n} = w_{6,1} = w_{6,n} = M$ (dost velké, např. $M > \sum_{i,j} d_{i,j}$), takže do optima nikdy nevstoupí (stejný trik jako v [L1.14]).
Jako MCF síť (vzorové řešení ji kreslí; viz obrázek): $s \to$ hračky $\to$ boxy $\to t$; krajní hrany s kapacitou 1 a cenou 0, prostřední $t_i \to b_j$ s kapacitou 1 a cenou $d_{i,j}$; $b(s) = n$, $b(t) = -n$. Vzorové řešení uzavírá (1:1, CZ): „z tohoto grafu můžeme najít reziduální graf a v něm odstranit záporné cykly, abychom dostali min flow“ — tedy přesně cycle canceling [L4.11].
A bus company has $n$ morning runs and $n$ afternoon runs that it needs to assign them to its $n$ drivers. The runs are of different duration. If the total duration of the morning and afternoon runs assigned to a driver is more than a specified $D$, the driver receives a premium payment for each hour of overtime. The company would like to assign the runs to the drivers to minimize the total number of overtime hours.
(a) Formulate this problem as an appropriate matching problem. Formally specify input parameters of the problem.
(b) Suppose that we arrange the morning runs in the non-decreasing order of their duration and the afternoon runs in the non-increasing order of their duration. If we assign each driver $i$ to the $i$th morning run and the $i$th afternoon run, do we obtain the optimal assignment? Outline the proof or find a counterexample.
a) Co je v zadání?
Každý řidič dostane jeden ranní a jeden odpolední běh; přesčas řidiče = o kolik součet délek přesáhne $D$. (a) chce převod na párovací problém včetně formálních vstupů; (b) testuje, jestli umíš o párovací heuristice rozhodnout: „nejkratší ranní + nejdelší odpolední“ — je to optimum, nebo najdeš protipříklad?
b) Co k tomu budeme potřebovat?
- Tato lekce — assignment problem = min-weight perfect matching (takeaways).
- [L0.6] — perfektní párování.
- Exchange argument (výměnný argument) — stejná technika jako u Dantzigova greedy v [L3.11].
c) Jak nad úlohou uvažovat?
(a): klíčové rozhodnutí je, co jsou partity. Ne řidiči × běhy! Řidiči jsou zaměnitelní — páruješ ranní běhy s odpoledními a dvojice = jeden řidič. Cena dvojice musí zachytit přesčas: jaká funkce z $m_i$, $a_j$ a $D$ to je? (b): nejdřív si zkus pár malých případů — zjistíš, že prohození dvou dvojic celkový součet délek nemění, jen ho jinak rozloží. Otázka tedy zní: škodí přesčasům vyváženost, nebo pomáhá? Porovnej $o(A) + o(A + \Delta + \Gamma)$ s $o(A + \Gamma) + o(A + \Delta)$.
d) Úplné řešení (dle banky #7)
(a) Formulace. Vstupy: $n \in \mathbb{Z}^+$, limit $D \in \mathbb{R}^+$, délky $m_i$ (ranní běh $i$) a $a_j$ (odpolední běh $j$), $i, j \in 1..n$. Přesčasová funkce $o(x) = \max\{0,\ x - D\}$. Spáruje-li jeden řidič ranní $i$ s odpoledním $j$, stojí to $c_{ij} = o(m_i + a_j) = \max\{0,\ m_i + a_j - D\}$ přesčasových hodin. Postav úplný bipartitní graf $K_{n,n} = (M \cup A, E)$, kde $M$ = ranní a $A$ = odpolední běhy; hrana $(i, j)$ = jeden řidič jede $i$ ráno a $j$ odpoledne. Přípustné přiřazení = perfektní párování ⟹ minimum-weight perfect matching v $K_{n,n}$ — dnešní assignment problem, řešitelný přes MCF. Ekvivalentně ILP: $\min \sum_i \sum_j c_{ij} x_{ij}$ za podmínek $\sum_j x_{ij} = 1\ \forall i$, $\sum_i x_{ij} = 1\ \forall j$, $x_{ij} \in \{0,1\}$.
(b) Ano — seřazené protiběžné párování je optimální. Seřaď $m_1 \le \cdots \le m_n$ a $a_1 \ge \cdots \ge a_n$ a páruj $m_i$ s $a_i$. Důkaz výměnným argumentem: vezmi libovolné přiřazení, v němž existuje „inverze“ — běhy $m_i \le m_j$ spárované souhlasně, tj. kratší s kratším: dvojice $(m_i, a_p)$, $(m_j, a_q)$ s $a_p \le a_q$. Označ $A = m_i + a_p$, $\Delta = m_j - m_i \ge 0$, $\Gamma = a_q - a_p \ge 0$. Souhlasné dvojice mají součty $A$ a $A + \Delta + \Gamma$; po prohození (kratší ranní s delším odpoledním) vyjdou $A + \Gamma$ a $A + \Delta$ — stejný celkový součet, jen vyváženější rozdělení. Stačí ukázat, že vyvážení přesčasy nezvýší:
$$o(A + \Gamma) + o(A + \Delta)\ \le\ o(A) + o(A + \Delta + \Gamma). \tag{1}$$
Substituce $\alpha = A - D$ převede (1) na $\max\{0, \alpha + \Gamma\} + \max\{0, \alpha + \Delta\} \le \max\{0, \alpha\} + \max\{0, \alpha + \Delta + \Gamma\}$ a rozbor tří případů:
- $\alpha \ge 0$: všechny čtyři členy kladné, obě strany $= 2\alpha + \Delta + \Gamma$. ✓
- $\alpha + \Delta + \Gamma \le 0$: všechny čtyři členy nulové. ✓
- $\alpha < 0 < \alpha + \Delta + \Gamma$: pravá strana $= \alpha + \Delta + \Gamma$; jsou-li oba levé členy kladné, levá strana $= 2\alpha + \Delta + \Gamma \le \alpha + \Delta + \Gamma$ (protože $\alpha \le 0$); je-li kladný jen jeden, je levá strana ještě menší. ✓
Výměna tedy nikdy nezhorší účelovou funkci; opakovaným prohazováním odstraníš všechny inverze a doiteruješ přesně k seřazenému protiběžnému párování ⟹ je optimální. Pozor na zobecnění: důkaz stojí na konvexním tvaru $o(x) = \max\{0, x - D\}$ — pro obecnou matici cen $d_{ij}$ žádné třídicí pravidlo nefunguje a musíš spustit MCF (viz polopravda 5 v lekci).