狠狠撸

双対性
JOI春合宿 2018
岩田陽一 (NII)

2
自己紹介
? 東大情報科学科→情報理工(2016年3月博士卒)
? 国立情報学研究所助教
? 離散アルゴリズムの研究をしている
世界 1 位 (2010)
世界 2 位 (2011)
世界 3 位 (2009)3回優勝
(2013,2015,2016)
競プロ： wata Twitter: @wata_orz
ICFPC

（最適化問題の）双対性とは？
3

(強)双対性
? 「〇〇の最小値＝□□の最大値」という形の定理
効率的に解ける様々な組合せ最適化問題の背後に
隠れている
? 「〇〇を最小化せよ」という問題を直接解く代わりに、
□□を最大化すれば良い
→解ける問題の範囲が広がる
? ○○と□□の解のペアで値が等しいものを手に入れ
たら、それぞれ最小値?最大値であると確信出来る
→アルゴリズムを考える?正しさの証明に便利
4

最適化問題
例：最小?-?カット問題
最小何本の辺を取り除けば?-?パスが無くなるか？
5
s t
min
?∈?
?(?)
?の範囲で?(?)を最小化せよ

判定問題
Yes の場合には簡単に検証可能な「証明」が存在
(?を実際に与えれば良い)
? NP (Non-deterministic Polynomial time)と言う
6
min
?∈?
?(?) ≤ ??
? ? ≤ ? となる ? ∈ ? があるか
s t
2本は可能？
はい。この2本を取
り除けば良いです。

補問題
No の場合に簡単に検証可能な「証明」は存在？
? 存在するような問題は co-NP と言う
7
min
?∈?
?(?) ≤ ??
? ? ≤ ? となる ? ∈ ? があるか
s t
1本は不可能？
多分出来ないと思う
けど???

P ? NP ∩ co-NP
Noを示すもっと簡単な証明はないだろうか？
8
P
NP co-NP
s t
1本は不可能？
最小値を計算したら
2だったので無理です
多項式時間で解ける（P）ならば
アルゴリズムの実行自体が効率
的に検証可能な証明といえる。

最大流＝最小カット
最大?-?フロー問題
最大何個の辺を共有しない?-?パスを選べるか？
任意の ?-?フロー ? = {?1, … , ??} と ?-? カット ? に対し、
|?| ≤ |?| が成り立つ。（∵ ? ?? ∩ ? ≠ ?）
実は、max |?| = min |?| が成り立つ。
9
s t
1本は不可能？
この２本のパスがあ
るので無理です。

双対問題
min
?∈?
? ? = max
?∈?
?(?)
となるように ?, ? を設計出来れば、?を与えることでNo
が証明可能！
10
min
?∈?
?(?)
?の範囲で?(?)を最小化せよ
max
?∈?
?(?)
?の範囲で?(?)を最大化せよ
一致
?(?)の範囲
?(?)の範囲

よくあるパターン
1. ? ? ≥ ?(?) (?? ∈ ?, ?? ∈ ?) が簡単に示せる
2. アルゴリズムの停止時に ? ? = ?(?) となる ? ∈ ?
と ? ∈ ? が得られることが示せる
→ 強双対定理とアルゴリズムの正当性が導かれる
11
（強）双対定理
min
?∈?
?(?) = max
?∈?
?(?)

扱う内容
1. 双対LP
2. 最短路?負閉路
3. 最小費用流
4. ラグランジュ双対
? 最小費用流などのアルゴリズムの解説はしない
? 双対を考えることでどんな問題が解けるようになる
のかの解説がメイン
12

更に勉強したい人向け参考書
? ネットワークフロー入門（JOI 2014-2015 春合宿）
? 保坂和宏、http://hos.ac/slides/20150319_flow.pdf
? 最大流?最小費用流の入門に
? プログラミングコンテストチャレンジブック
? 秋葉拓哉、岩田陽一、北川宜稔
? 競プロ向け最大流?最小費用流の基礎と応用例
? 離散凸解析と最適化アルゴリズム
? 室田一雄、塩浦昭義
? 最適化アルゴリズムを離散凸という観点から一般化
? Graphs, Networks and Algorithms
? D. Jungnickel
? フローの色々なアルゴリズムが載ってる
? Combinatorial Optimization
? A. Schrijver
? 3部からなる超大作（オススメ）
13

線形計画問題（LP: Linear Programming）
? 目的関数と制約が全て一次式な連続最適化問題
? 整数性条件は無し
? 多項式時間で解ける
maximize ?1 + 2?2
subject to ?1 + ?2 ≤ 4
?2?1 + ?2 ≤ 2
?1 ≤ 3
?1, ?2 ≥ 0
15
Max =
22
3
? =
2
3
,
10
3
本当に最大？

解の上界を示す
maximize ?1 + 2?2
subject to ?1 + ?2 ≤ 4 (1)
?2?1 + ?2 ≤ 2 (2)
?1 ≤ 3 (3)
?1, ?2 ≥ 0
(1) + (2) + 2(3): ?1 + 2?2 ≤ 12
2 1 : ?1 + 2?2 ≤ 2?1 + 2?2 ≤ 8
5
3
1 +
1
3
(2): ?1 + 2?2 ≤
22
3
16
22
3
より大は無理

maximize ?1 + 2?2
subject to ?1 + ?2 ≤ 4 (1)
?2?1 + ?2 ≤ 2 (2)
?1 ≤ 3 (3)
?1, ?2 ≥ 0
より一般に、(1)を?1倍、(2)を?2倍、(3)を?3倍して足すと、
?1 ? 2?2 + ?3 ?1 + ?1 + ?2 ?2 ≤ 4?1 + 2?2 + 3?3
17

maximize ?1 + 2?2
subject to ?1 + ?2 ≤ 4 (1)
?2?1 + ?2 ≤ 2 (2)
?1 ≤ 3 (3)
?1, ?2 ≥ 0
より一般に、(1)を?1倍、(2)を?2倍、(3)を?3倍して足すと、
?1 ? 2?2 + ?3 ?1 + ?1 + ?2 ?2 ≤ 4?1 + 2?2 + 3?3
目的関数: 1?1 + 2?2
18
≥
≥
2つの ≥ が成り立てば、
右辺が最大値の上界

双対LP
出来るだけ良い上界を示す問題もLPとなる。
19
maximize ?1 + 2?2
subject to ?1 + ?2 ≤ 4 (× ?1)
?2?1 + ?2 ≤ 2 (× ?2)
?1 ≤ 3 (× ?3)
?1, ?2 ≥ 0
minimize 4?1 + 2?2 + 3?3
subject to ?1 ? 2?2 + ?3 ≥ 1
?1 + ?2 ≥ 2
?1, ?2, ?3 ≥ 0
双対
主問題
双対問題

双対LP
出来るだけ良い上界を示す問題もLPとなる。
もう一回双対を取ると元に戻る。
20
maximize ?1 + 2?2
subject to ?1 + ?2 ≤ 4 (× ?1)
?2?1 + ?2 ≤ 2 (× ?2)
?1 ≤ 3 (× ?3)
?1, ?2 ≥ 0
minimize 4?1 + 2?2 + 3?3
subject to ?1 ? 2?2 + ?3 ≥ 1 (× ?1)
?1 + ?2 ≥ 2 (× ?2)
?1, ?2, ?3 ≥ 0
双対双対
主問題
双対問題

強双対性
21
maximize ??
subject to ?? ≤ ?
? ≥ ?
minimize ??
subject to ?T ? ≥ ?
? ≥ ?
=
? 双対LPの意味（制約の線形和で出来るだけ良い上
界?下界を示す）さえ理解すれば簡単に双対が取れ
るので標準形を暗記する必要はない。
? 双対LPの作り方から ≤ は明らかだが、実は常に等号
が成立する（強双対性）
? もしくは (∞, 解なし)、(解なし、 ? ∞)
? ただし、等号が成立する整数解があるとは限らない
標準形

他の標準形
（標準形を暗記するより意味を理解しよう）
→: 等号なので、負の係数をかけて足しても良い
? ?? ≤ ? を ?1 倍したら ??? ≥ ?? で不等号が逆に
←: 非負制約がないので、係数は一致させないとダメ
? ? ≥ ? ならば、?′ ≤ ? から ?′ ? ≤ ?? が言える
22
maximize ??
subject to ?? = ?
? ≥ ?
minimize ??
subject to ?T ? ≥ ?
? ≥ ?
=

LP双対ゲーの解き方
二通りの方針
1. とりあえずLPで書いてみてから双対を取り、知ってる
問題じゃないか考える
? ダメなLPを書くとうまくいかないので結構試行錯誤が必要
2. 双対問題の形を予め覚えておいて、その形になるよ
うに定式化
? 多くの場合こっちの方が簡単
23

例題: Min-Max (出典: POJ Monthly)
? (≤ 50000)次元の非負実数ベクトル (?1, … , ? ?) が
あり、 σ? ?? = 1 を満たしている。２つのベクトル ?, ? と
実数?が与えられる。σ? ?? ?? = ? であるとき、σ?? ?? の
取りうる値の最小値?最大値を求めよ。
24
http://poj.org/problem?id=2595

最小値を求める問題をLPで書くと、
min ? σ? ?? ??
σ? ?? = 1
σ? ?? ?? = ?
?? ≥ 0
双対LPを作ってみると、
25

最小値を求める問題をLPで書くと、
min ? σ? ?? ??
σ? ?? = 1
σ? ?? ?? = ?
?? ≥ 0
双対LPを作ってみると、
max
?,?
? + ??
? + ?? ? ≤ ?? (× ??)
26
× ?
(× ?)

max
?,?
? + ??
? + ?? ? ≤ ??
これは、二次元の多角形内部で、(1, ?)方向に一番遠
い点を求める問題。多角形を?(? log ?)で構築して端
点を全て調べれば良い。
27
実は定数次元のLPは線形時間で
解けることが知られている。
(Seidel’s LP algorithm など)

まとめ
? 双対LPを構築出来るようになろう
? 制約式の線形和で出来るだけ良い上界(下界)を
作る、ということだけ覚えておけば自然に作れる
? LPでは強双対性が成り立ち、双対LPを解くことで元の
LPも解ける
? ただし、整数解で成り立つとは限らないので注意
? LPで書ける問題は、そのままだと解き方が分からなく
ても、双対を取ってみると知ってる問題になるかも
28

?-?最短路問題をLPで書いてみる
辺 ? を通る回数を表す変数 ??
?? ? 辺?の長さ
?+ ? ? ?から出る辺集合、?? ? ? ?へ入る辺集合
? ? ? σ ?∈? ??
minimize σ ?∈? ?? ??
subject to ? ?? ? ? ? ?+ ? = ?
?1 (? = ?)
1 (? = ?)
0 (otherwise)
?? ≥ 0 (?? ∈ ?)
（注意：負の閉路があると最小値は ? ∞になる）
30
?
??
(?) ?+(?)

双対LP
minimize ? σ ?∈? ?? ??
s.t. ? ?? ? ? ? ?+ ? = ?
?1 ? = ? (× ??)
1 ? = ? (× ??)
0 otherwise (× ? ?)
?? ≥ 0
maximize ? ?? ? ??
s.t. ? ? ? ? ? ≤ ? ?? (× ???)
31
= ただし、整数解で一致するとは
まだ言っていない
目的関数?制約ともに「二変数の差」の形
二変数の差が現れたら双対ゲーを疑おう！

距離関数
?から?への最短距離を? ?とすると、
1. ?? ? ?? = ???最短路の長さ
2. ??? ∈ ?に対して、? ? ≤ ? ? + ? ??
が成り立つので、?は双対LPの最適解である。つまり、
? 最短路アルゴリズムで双対LPが解ける。
? ?が整数なら整数解が求まる。
ただし、負閉路がある場合に注意
32
maximize ? ?? ? ??
s.t. ? ? ? ? ? ≤ ? ?? for ??? ∈ ?

負閉路検出
負閉路にそって??を増やすことで、主問題の解は幾らで
も小さくなるので、双対問題は解なしとなる。つまり、
を満たす?が存在する?負閉路が存在しない。
そのような?は「ポテンシャル」と呼ばれる。
? 最適化の場合も、通常の最短路アルゴリズムだと?から到
達不能な負閉路を見逃すので注意が必要。
? Bellman-Fordで? ? = 0, ? ? = ?(十分大きな値)から開始す
れば良い。
33
? ? ? ? ? ≤ ? ?? for ??? ∈ ?

解ける問題
? 目的関数が ?? ? ?? の形
? ? から ? への最短距離を求める
? 制約が全て ? ? ? ? ? ≤ ? ?? の形
? ? から ? へ長さ ? ?? の辺を張る
? ? ?? ≤ ? ? ? ? ? の形も ? ? ? ? ? ≤ ?? ?? と書けるので ? か
ら ? へ長さ ?? ?? の辺を張れば良い
Bellman-Fordの更新式を思い出せばグラフは自然に作れる
? ? ← min(? ?, ? ? + ? ??) だから停止時に ? ? ≤ ? ? + ? ?? が成立
34
maximize ? ?? ? ??
s.t. ? ? ? ? ? ≤ ? ?? for ??? ∈ ?

「二変数の差」を作る頻出テク
1. 絶対値上限制約: ? ? ? ? ? ≤ ? ??
? ?? ?? ≤ ? ? ? ? ? ≤ ? ??
2. 一変数制約: ?? ≤ ??
? 新しい変数 ?0 を導入し、全ての変数??を?? ? ?0
で置き換えると、?? ? ?0 ≤ ?? となる
? 既存の二変数制約 ?? ? ?? ≤ ??? は変化しない
3. 二部グラフ
? ?? + ?? 型のときは、全ての?の符号を反転させる
ことで、?? ? ??型になる
? グリッドグラフとかで頻出
35

「二変数の差」を作る頻出テク
4. 区間の和: ?? + ??+1 + ? + ?? ≤ ???
? ?? ? ?0 ? ?1 + ? + ?? とおくと、?? ? ???1 ≤ ???
5. 円形区間和: ?? + ??+1 + ? + ? ? + ?1 + ? + ??
? 総和 ? ? ?1 + ? + ? ? を全通り試す?二分探索
などにより固定し、制約 ?1 + ? + ? ? = ? を追加
? ? ? (??+1 + ? + ???1) と通常の区間和になる
（?は変数でなく定数なことに注意）
36
= ?

例題: Asteroids2 (出典: UTPC 2013)
https://utpc2013.contest.atcoder.jp/tasks/utpc2013_08
?次元ベクトル?, ?と ? × ?行列?, ? が与えられるので
0 ≤ ?? ≤ ?? ? ∈ ?
0 ≤ ?? ≤ ? ? (? ∈ [?])
??? ≤ ?? + ?? ≤ ??? ?, ? ∈ N
を満たす整数ベクトル ?, ? が存在するか判定せよ。
37
∞
?∞
3
2
1
1
7
5
3
1 2
4
No

例題: Asteroids2 (出典: UTPC 2013)
新たに変数?を導入し、?? → ?? ? ?, ?? → ? ? ?? と置き
直すと、
0 ≤ ?? ? ? ≤ ?? ? ∈ ?
0 ≤ ? ? ?? ≤ ? ? (? ∈ [?])
??? ≤ ?? ? ?? ≤ ??? ?, ? ∈ N
全て差の形になったので負閉路検出して終了
38

例題: Cashier Employment (出典: Tehran 2000)
24時間営業のスーパーが店員を募集している。? 時か
ら ? + 8 時までの8時間働く（日を跨ぐ可能性あり）こと
を希望する応募者が??人居る。? 時から ? + 1 時の間は
少なくとも ?? 人の店員が必要である。最小何人の店員
を雇えばよいか？
? 時から ? + 8 時希望の応募者から ?? 人を雇うとすると、
σ ?=0
7
?(???) mod 24 ≥ ?? が満たされる必要がある。
? 円形区間和
39

例題: Cashier Employment (出典: Tehran 2000)
雇う人数の最小値を二分探索で求めよう。
?? ? ?0 ? ?0 + ? + ???1 とすると、? 人で可能かは以
下のLPで判定できる。
?24 ? ?0 = ?
0 ≤ ??+1 ? ?? ≤ ?? (? = 0, … , 23)
??+1 ? ???7 ≥ ?? (? = 7, … , 23)
? ? ?17+? ? ??+1 ≥ ?? ? = 0, … , 6
全て差の形になったので負閉路検出して終了
40
類題: YamanoteLine (SRM553Hard)
円形区間和の上限?下限制約で総和の取りうる値の総数を求める

まとめ
? 目的関数?制約が全て「二変数の差」 (? ? ?) の形
? 最短路?負閉路検出の双対
? 辺の向きに迷ったらBellmanFordの更新式を思い出そう
? 「二変数の差」を作る頻出テクを覚えておこう
41

フロー
各辺?に容量? ?(≥ 0)のある有向グラフと供給需要関数
?: ? → ? に対して、以下を満たす?: ? → ?≥0 を「許容
フロー」という。
? ?? ? ? ? ?+ ? = ?? ?
0 ≤ ?? ≤ ? ? ?? ∈ ?
43
?
??
(?) ?+(?)
? ? > 0な点では
? ?湧き出る
? ? = 0な点では
入る量＝出る量
?を通して最大? ?
まで流せる
? ? < 0な点では
?? ?消費する

最小費用流問題
最小重みの許容フローを求める問題
? 最短路(?? = 1, ?? = ?1, ? ? = 0)の自然な拡張
subject to ? ?? ? ? ? ?+ ? = ?? ?
0 ≤ ?? ≤ ? ? (?? ∈ ?)
多項式時間で解ける
? アルゴリズムの解説は省略
? 他の資料で勉強してね
44

双対LP
s.t. ? ??
? ? ? ?+
? = ?? ? (× ? ?)
0 ≤ ?? ≤ ? ? (× ? ?)
maximize ?,? ? σ ? ? ? ? ? ? σ ? ? ? ? ?
s.t. ? ? ? ? ? ? ? ?? ≤ ? ?? (× ???)
? ? ≥ 0
?が整数なら、?も整数最適解が存在
? 最短路反復法で使うポテンシャル?が実は双対最適解
45
=

もう少し整理
maximize ?,? ? σ ? ? ? ? ? ? σ ? ? ? ? ?
s.t. ? ? ? ? ? ? ? ?? ≤ ? ??
? ? ≥ 0
minimize ?,? σ ? ? ? ? ? + σ ? ? ? ? ?
s.t. ? ? ? ? ? ? ? ?? ≤ ? ??
? ? ≥ 0
minimize ? σ ? ? ? ? ? + σ ?? ? ??max(0, ? ? ? ? ? ? ? ??)
46
?1倍
=
? ?? の値は ? ?, ? ? から定まる

解ける問題
47
minimize ? σ ? ? ? ? ? + σ ?? ? ??max(0, ? ? ? ? ? ? ? ??)
? 線形関数とmax(0, 二変数の差 ? 定数)の和
? ? ? ? ?
0 ? ??
傾き = ? ?? > 0

解ける問題
実は任意の下に凸な折れ線が表現可能
? 傾き負と正に分け、傾きの変化を係数とすれば良い
?1 + max 0, ?? + max 0, ? ? 1 + 2 max(0, ? ? 3)
48
? = ? ? ? ? ?
0
?1
傾き3
?1 1
1
3
傾き1
傾き0
傾き?1

解ける問題
49
minimize ? σ ? ? ? ? ? + σ ?? ? ??max(0, ? ? ? ? ? ? ? ??)
「二変数の差に関する下に凸な折れ線」の和
の最小化は最小費用流で解ける。
? 折れ線を分解して上の形にしてからグラフを構築すれば
良い
? σ ? ? ? = 0 なことを考えると、σ ? ? ? ? ?の部分もこの形
? 最短路のときの「二変数の差」を作る頻出テクがこっちで
も役に立つ
? 途中で?1倍したので、最小値 = ?最小費用流なことに
注意

例題: How to Create a Good Game （出典: JAG Summer 2010）
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2230
?(≤ 100)点?(≤ 1000)辺のDAGが与えられる。点0か
ら点? ? 1へのLongest Pathの長さを変えないように、
出来るだけ辺の重みを増やしたい。増やす重みの和の
最大値を求めよ。
Longest Pathの長さを?、辺?の重みを??、増やす量を
? ?とすると、
max
?≥0
σ ? ? ?
s.t. Longest Pathの長さが?
50

最短路の双対から、Longest Pathの長さが?以下
? 以下を満たす?が存在。
? ??1 ? ?0 ≤ ?
? ? ? ? ? ≥ ? ?? + ? ??
よって、解きたい問題は
max
?,?
σ ? ? ?
? ??1 ? ?0 ≤ ?
? ? ? ? ? ≥ ? ?? + ? ??
? ? ≥ 0
51

52
min
?,?
σ ?? ?
? ??1 ? ?0 ≤ ?
? ? ? ? ? ≥ ? ?? + ? ??
? ? ≥ 0
? ? ? ? ?
0 ? ??
傾き?1
∞
?? ??
下に凸なので分解して最小費用流で終了
?1倍して
= ∞ max 0, ? ? ? ? ? + ? ??
+ ? ? ? ? ? + ? ??

例題: じょうしょうツリー (出典: UTPC 2012)
各頂点?が値??を持つ?(≤ 105)点の根付き木が与えら
れる。コストを1払うことで一つの頂点の値を±1変更で
きる。各点?とその子供?について、? ? > ? ?が成り立つ
ように変更する最小コストを求めよ。
53
コスト8

簡単な変形で、 ? ? > ? ?ではなく ? ? ≥ ? ? を目指す問題に出来る。
? ? ? 変更後の?の値、とすると
min
?
σ ? |? ? ? ? ?|
s.t. ? ? ≥ ? ?
|? ? ? ? ?|が一変数なので? ? → ? ? ? ?0と置き直すと
min ? σ ? |? ? ? ?0 ? ? ?|
s.t. ? ? ≥ ? ?
54
? ? ? ?0
0 ? ?
|? ? ? ?0 ? ? ?|
下に凸なので分解して最小費用流で終了
…と言いたいところだが?が大きいのでTLE

min ? σ ? |? ? ? ?0 ? ? ?|
s.t. ? ? ≥ ? ?
分解すると、
min
?
σ ? max(0, ? ? ? ?0 ? ? ?)
0から?へ容量1重み? ?
+ σ ? max(0, ?0 ? ? ? + ? ?)
?から0へ容量1重み?? ?
+ σ ?? ∞max(0, ? ? ? ? ?)
?から?へ容量∞重み0
55
?
?
0 0
? ?
?? ?
? ?
?? ?

需要供給無しなので、負閉路を詰め込む問題。
グラフの形から全ての負閉路は0 → ? → 子供 → ? → ? → 0という形をして
おり、葉から根に向かって以下の貪欲法で解ける。
? … ?0というパスでまだ使えるものの長さをヒープで管理する。
?を以下のようにして処理する
1. 子供のヒープを全てマージ
2. ヒープにパス?0の長さ?? ?を突っ込む
3. ? ? + ヒープの最小値 < 0 ならばヒープからpopして貪欲に使う
データ構造をマージする一般的テクで?(? log2
?)
マージ可能ヒープを用いると?(? log ?)
56
?
?
0 0
? ?
?? ?
? ?
?? ?

? … ?0というパスでまだ使えるものの長さをヒープで管理する。
?を以下のようにして処理する
1. 子供のヒープを全てマージ
2. ヒープにパス?0の長さ?? ?を突っ込む
3. ? ? + ヒープの最小値 < 0 ならばヒープからpopして貪欲に使う
57
6
2 10
3 5 8
9 5
?9 ?5
?3 ?5
?9, ?8, ?5 → ?8, ?5
?5, ?3, ?2 → ?3, ?2 ?10, ?8, ?5
?10, ?8, ?5, ?3, ?2
答え: 9 ? 8 + 5 ? 2 + 10 ? 6 = 8

貪欲の証明:
? ? ? ?以下の頂点集合(?を含む)とすると、?を処理し終えた段
階で?[ 0 ∪ ? ?]の最小費用流が求まっていることを示す。
?[ 0 ∪ ? ? ? ? ]の最小費用流は、グラフの形から各子供?につ
いて?[ 0 ∪ ??]の最小費用流の和と等しい。
?を追加したことで生じる新たな閉路は0? … ?0という形のものだ
けであり、0?の容量が1であることから、この中で最小のものを１
つ選べば最小費用流になる。
58
類題: 花火 (第二回ドワンゴからの挑戦状予選）
Farm Village (JAG Asia 2017)
特殊なグラフの最小費用流

まとめ
? 「二変数の差に関する下に凸な折れ線」の和の最小化
? 最小費用流の双対
? 下に凸な折れ線を分解して下の形にすればよい
? ? ? ? 供給 ? 需要
? ? → ? へ重み? ??、容量? ??の辺
? ? ??は負になる場合あり
? 特殊なグラフのフローは速く解ける可能性あり
59
minimize ? σ ? ? ? ? ? + σ ?? ? ??max(0, ? ? ? ? ? ? ? ??)

ラグランジュ緩和
61
? ? = 0 の制約がなければ
解けるんだけど???
max
?∈?
?(?) s.t. ? ? = 0

ラグランジュ緩和
邪魔な制約を「ペナルティ」として目的関数に移動させ
よう。（この操作をラグランジュ緩和という）
任意の ? (ラグランジュ乗数という) に対して次の不等式
が成り立つ。
62
max
?∈?
?(?) s.t. ? ? = 0
max
?∈?
?(?) ? ?? ?
≤
これなら
解ける！max
?∈?
?(?) ? ?? ? s.t. ? ? = 0
=
∵ ? ? = 0 なら ?? ? = 0
∵ 制約が減った

ラグランジュ双対
出来るだけ良い上界を求める問題を考えよう。
(この問題をラグランジュ双対という)
? ? ? max
?∈?
? ? ? ??(?) とすると、?(?)は下に凸となるので、
(三分探索などで)最小化出来る。
? ??1 + 1 ? ? ?2 = ? ?? ? ??1 + 1 ? ? ?2 ?(??)
= ? ? ?? ? ?1 ? ?? + 1 ? ? ? ?? ? ?2 ? ??
≤ ?? ?1 + 1 ? ? ?(?2)
63
max
?∈?
?(?) s.t. ? ? = 0
min
?
max
?∈?
?(?) ? ?? ?≤

強双対性
? ? ? ??(?) を最大化する?の集合を?(?)と定義する。もし、
? ∈ ?(?)であって、? ? = 0 となるものが存在すれば、等号が
成立する。? を小さくすれば?(?)は大きくなり、大きくすれば?(?)
は小さくなるので、二分探索すればちょうど0になるものが見つか
り元の問題が解けるのでは？
? 等号が成立しても全ての ? ∈ ?(?) で? ? = 0 となるとは限らないの
で、実際に?を構築する方法は少し考えないといけない
? 最適値を求めるだけなら二分探索して終了
64
max
?∈?
?(?) s.t. ? ? = 0
min
?
max
?∈?
?(?) ? ?? ?
=
?
一般には成り立たない
が、LPでは成り立つ

強双対性（LPの場合）
?? ≤ ? の多面体中で、(? ? ??)方向に一番遠い点を
求める問題。
? を動かすと、?(?)の範囲も連続的に動くので、ちょう
ど?? = ? となる点が存在する。
65
max
?
??
s.t. ?? ≤ ?
?? = ?
min
?
max
?
?? ? ?(?? ? ?)
s.t. ?? ≤ ?
=
?? ≤ ? ? ? ??
?? = ? ?(?)
整数解に限定したら飛び越すかも

? ? ≤ ? の場合
LPの場合は等号成立
66
max
?∈?
?(?) s.t. ? ? ≤ 0
min
?≥0
max
?∈?
?(?) ? ?? ?
≤
∵ ? ? ≤ 0, ? ≥ 0 なら ??? ? ≥ 0

複数個邪魔な場合
LPの場合は等号成立
67
max
?∈?
?(?) s.t. ?? ? = 0 (? ∈ [?])
min
?1,…,? ?
max
?∈?
?(?) ? σ? ?? ??(?)
≤

双対LPとの関係
全部の制約をラグランジュ緩和すれば双対LPになる。
??の係数は ?? ? ??? ? (??? ? ?の?列ベクトル)
もし、ある ? で ?? ? ??? ? > 0 なら、max
?
? = ∞
逆に、全ての ? で ?? ? ??? ? ≤ 0 なら、max
?
? = ??
68
max
?
?? s.t. ?? ≤ ?, ? ≥ 0
min
?≥0
max
?
?? ? ?T(?? ? ?) s.t. ? ≥ 0
=
min
?
?? s.t. ?T ? ≥ ?, ? ≥ 0
=

双対LPとの関係
LPのラグランジュ双対は「双対LPを作る途中段階」だと
思うと、双対変数とラグランジュ乗数が同じものである
ことがわかる。
? ?? ≤ ? に対応する双対変数が最適双対解で取る
値と ?? ≤ ?を消すラグランジュ双対の最適解でラ
グランジュ乗数が取る値は同じ
? 特に、双対LPが整数解を持つLPに対してラグラン
ジュ双対を作れば、ラグランジュ乗数の最適値も
整数になる
69

ラグランジュゲーの解き方
タイプ1: 解ける問題＋邪魔な制約
? ラグランジュ緩和で制約を消し、二分探索などで双
対問題を解く
タイプ2: min max ~ という形の最適化問題（ゲームとか）
? ラグランジュ双対問題だとみなして元の max ~ の
形に戻して解く
? 等号が成り立つことを確認しよう（特に整数解が必
要な場合)
70

例題: Min-Max (出典: POJ Monthly) の別解
? (≤ 50000)次元の非負実数ベクトル (?1, … , ? ?) が
あり、 σ? ?? = 1 を満たしている。２つのベクトル ?, ? と
実数?が与えられる。σ? ?? ?? = ? であるとき、σ?? ?? の
取りうる値の最小値?最大値を求めよ。
71
min ? σ? ?? ??
σ? ?? = 1
σ? ?? ?? = ?
?? ≥ 0
←この制約がなければ非常に簡単
（一番小さい??に対して?? = 1とすればよい）

例題: Min-Max (出典: POJ Monthly) の別解
ラグランジュ双対を取ると、
max
?
min ? σ? ?? ?? + ?(σ? ?? ?? ? ?)
σ? ?? = 1
?? ≥ 0
? (?? + ???) が一番小さい ? に対して、?? = 1 とすれば
内側の最小化可能。
? ?? ? ? の符号で二分探索すれば外側の最大化が出
来る。
双対LPで幾何の問題にするより、かなり簡単！
72

例題: Skyland (出典: JAG Spring 2012)
? (≤ 100)個の浮遊島がある。各島の高度は0以上の
任意の実数値に設定できる。? 番目の島を高度?にする
にはコストが???かかる。島?と島?の高度差が?あるとコ
ストが??? ?かかる。高度の合計を?以上にする最小コス
トを求めよ。（本来はそのような?を求める問題）
73
min
?
σ? ???? + σ?? ???|?? ? ??|
σ? ?? ≥ ?
?? ≥ 0
←この制約がなければ
双対最小費用流の形

例題: Skyland (出典: JAG Spring 2012)
? 双対最小費用流で内側の最小化が可能
? よく眺めると全ての重みが0なので、供給需要を満
たすフローがあるか判定問題→最大流
? 許容フローがあるかどうかで二分探索すれば外側の
最大化が可能
? 解の構築はこの方針だともう少し考察が必要
74
max
?≥0
min
?
σ? ???? + σ?? ???|?? ? ??| ??(σ? ?? ? ?)
?? ≥ 0

解の構築方法（プロ向け補足）
解の構築がしたい場合は？
重み0の最小費用流の双対なので、単純には? = 0が
解として求まってしまい、σ? ?? = ? とならないので、別
の最適解を構築する必要がある。
?? → ?? ? ?0 と置き換えてグラフを作ってみると、
75
0
? ?
???
∞ ∞
?0 = ?? ? σ? ??
?? = ?? ? ? ?? = ?? ? ?

解の構築方法（プロ向け補足）
最適な?における許容フロー?を固定する。相補性定理
から、?が最適解 ? ?の残余グラフにおける全ての容
量正の辺??で ? ? ≤ ? ?。もし0から全ての点が到達可能
なら、?を?増やしても許容フローが存在するので矛盾。
到達出来ない点集合?に対して? ∈ ? で ? ? = ?/|?| と
すれば良い。（このような最適解が存在することに先に
気づけば二分探索＋最小カットで直接解ける）
76
0
? ?
???
∞ ∞
?0 = ?? ? σ? ??
?? = ?? ? ? ?? = ?? ? ?

例題: Longest Shortest Path (出典: JAG Asia 2015)
?(≤ 200)点?(≤ 2000)辺の重み付き有向グラフが与
えられる。各辺?について、コスト? ? ? ?(非負実数)支払う
ことで重みを??から?? + ?に増加させることが出来る。
予算?の範囲内で?-?最短路の長さを最大化せよ。
77
max
?
(重み? + ?での???距離)
σ ? ? ? ? ? ≤ ?
? ? ≥ 0

? 双対最小費用流で内側の最大化が可能
? σ ? ? ? ? ? ? ?の符号で二分探索すれば外側の最小化
が可能
78
min
?≥0
max
?
(? + ?での???距離) ? ? σ ? ? ? ? ? ? ?
? ? ≥ 0
min
?≥0
max
?,?
?? ? ?? ? ? σ ? ? ? ? ? ? ?
? ? ? ? ? ≤ ? ?? + ? ??
? ? ≥ 0
=
?-?最短路の双対

入力が小さいのでこのままでも解けるが、もう少し高速
化が可能。? → 1/? と置き換えると、
これは(流量?の最小費用流 + ?)/? を最小化する問題
? ? を1ずつ増やしていくことで解ける
79
min
?>0
max
?,?
(??? ? ??? ? σ ? ? ? ? ? + ?)/?
? ? ? ? ? ≤ ? ?? + ? ??
? ? ≥ 0

例題: きたまさの逆襲 (出典: UTPC 2012)
重み付き二部グラフ? = (?, ?)がある。秋葉さんは大きさ|?|の
マッチングで出来るだけ重みの小さいものが欲しい。きたまささ
んは重みを操作することで秋葉さんの妨害をしたい。?の分割
? = ?1 ∪ ? ∪ ? ?があり、コスト??を支払うことで??に接続する全
ての辺の重みを1増えせる(複数回増やして良い)。（秋葉さんの
マッチングの重み）?（きたまささんのコスト）を最大化せよ。
80
max
?1,…,? ?≥0
min
?
σ? σ ?∈? ?
σ ?(? ?? + ??) ??? ? σ? ?? ??
?: 大きさ|?|のマッチング

ラグランジュ双対をとった形だと思うと、
81
max
?1,…,? ?≥0
min
?
σ ? ?? ?? + σ?(σ ?∈? ?
σ ? ??? ? ??)??
=min
?
σ ? ?? ??
σ ?∈? ?
σ ? ??? ≤ ??

これは(双対でなく普通の)最小費用流
82
min
?
σ ? ?? ??
σ ?∈? ?
σ ? ??? ≤ ??
? ?? ? ? ?
重み
容量
0 0 ? ?? 0
?? 1 1 1
この容量制約の双対変数が??
よって整数解が存在
??から出る流量
の和が??以下

例題: Homework (ICPC Asia 2017)
(意訳) ２つの二部グラフ?1 = (?1 ∪ ?, ?1)と?2 = (?2 ∪
?, ?2)が与えられる。? = ?1 ∪ ?2と分割し、(?1, ?1)と
(?2, ?2)の最大マッチングの和を最小化せよ。
83
a b c
1 4 6
2 3 5
A B C
2 3 5
1 4 6
?1
?
?
?2
1 + 1 = 2

?? ? ?をマッチングに含めるか
? ? ? ? を ?1に含めるか
と定義し、min max ~ の形で書くと
84
min
?∈ 0,1 ?
max
?
?
??∈?1
? ? ??? + ?
??∈?2
(1 ? ? ?)???
?: ?1, ?2のマッチング
? ? = 0なら??を使っても意味なし

85
min
?∈ 0,1 ?
max
?
?
?∈?2
?? + ?
?
? ? ?
?∈?1
??? ? ?
?∈?2
???
max
?
σ ?∈?2
??
σ ?∈?1
??? ? σ ?∈?2
??? = 0 ?? ∈ ?
≥
? ∈ 0,1 ?となる最適解があれば等号成立

?1で?を使うなら?2でも?を使うような最大マッチングを
求める、最大流の基礎的な応用問題 (Dining@POJ
3281 と同じ問題)
? 最大流の双対解＝最小カットは0,1の値を取るので
等号成立
? 他にも色々な方法で同じ解法に至れる（マトロイド交
差の双対など）
86
max
?
σ ?∈?2
??
σ ?∈?1
??? ? σ ?∈?2
??? = 0 ?? ∈ ?

87
a b c
1 4 6
2 3 5
A B C
2 3 5
1 4 6
?1
?
?
?2
?
?

まとめ
min max ~ 最適化
? ラグランジュ双対とみなして元に戻してみよう
? 双対LPが最適整数解を持つなら、ラグランジュ乗
数も最適整数解を持つ
88
max
?∈?
?(?) s.t. ? ? = 0
min
?
max
?∈?
?(?) ? ?? ?
≤ LPでは等号成立
解ける問題＋邪魔な制約
? ラグランジュ双対をとって? ? の符号で
二分探索しよう
出来るだけ良い
上界を得たい

全体のまとめ
? LP双対
? 制約式の線形和で出来るだけ良い上界(下界)を作る
? 最短路?負閉路
? 目的関数?制約が「二変数の差」
? 最小費用流
? 「二変数の差に関する下に凸な折れ線」の和の最小化
? minimize ? σ ? ? ? ? ? + σ ?? ? ??max(0, ? ? ? ? ? ? ? ??)
? ラグランジュ双対
? LP双対の途中段階とみなせる
? 邪魔な制約の除去
? min max ~ 型最適化
89

狠狠撸

双対性

More Related Content

双対性