凸最適化・組合せ最適化の問題

1. $s$–$t$ 有向道の列挙. $s$ から出る辺は $s\to a,s\to b$ のみで、$c$ から $b$ への辺はないので、$s$–$t$ 有向道は次の 6 本である。

• $P_1:s\to a\to t$ : $c=2+1=3$, $d=3+7=10$
• $P_2:s\to a\to b\to t$ : $c=2+1+4=7$, $d=3+1+2=6$
• $P_3:s\to a\to b\to c\to t$ : $c=2+1+1+2=6$, $d=3+1+2+1=7$
• $P_4:s\to a\to c\to t$ : $c=2+3+2=7$, $d=3+1+1=5$
• $P_5:s\to b\to t$ : $c=5+4=9$, $d=1+2=3$
• $P_6:s\to b\to c\to t$ : $c=5+1+2=8$, $d=1+2+1=4$

2. 主問題の最適値. $d(P)\le 6$ を満たすのは $P_2,P_4,P_5,P_6$ で、費用はそれぞれ $7,7,9,8$。よって $p^{\ast }=7$。

3. 双対関数. 各道について $c(P)+\lambda (d(P)-6)$ を書くと
$$P_1:3+4\lambda ,P_2:7,P_3:6+\lambda ,P_4:7-\lambda ,P_5:9-3\lambda ,P_6:8-2\lambda .$$
$\phi$ はこれら 6 本の 1 次関数の最小値なので、区分的 1 次の凹関数である（各 $\lambda$ で $\phi (\lambda )$ は辺重み $c_e+\lambda d_e$ に関する最短路長から $6\lambda$ を引いたものでもある）。

$3+4\lambda$ と他の各直線を比べると
$$3+4\lambda \le 7-\lambda ⟺\lambda \le \frac{4}{5},3+4\lambda \le 6+\lambda ⟺\lambda \le 1,3+4\lambda \le 9-3\lambda ⟺\lambda \le \frac{6}{7},$$
$$3+4\lambda \le 8-2\lambda ⟺\lambda \le \frac{5}{6},3+4\lambda \le 7⟺\lambda \le 1.$$
したがって $0\le \lambda \le \frac{4}{5}$ では $\phi (\lambda )=3+4\lambda$ で、これは増加し $\phi (\frac{4}{5})=\frac{31}{5}$。一方 $\lambda \ge \frac{4}{5}$ では $\phi (\lambda )\le 7-\lambda \le 7-\frac{4}{5}=\frac{31}{5}$。ゆえに
$$d^{\ast }=\underset{\lambda \ge 0}{\max }\phi (\lambda )=\phi \left(\frac{4}{5}\right)=\frac{31}{5}.$$
（確認: $\lambda =\frac{4}{5}$ で各値は $P_1:\frac{31}{5},P_2:7,P_3:\frac{34}{5},P_4:\frac{31}{5},P_5:\frac{33}{5},P_6:\frac{32}{5}$ で、最小は $\frac{31}{5}$。）

4. 幾何的解釈. 点 $(d(P),c(P))$ の下側凸包の $d=6$ における高さが $d^{\ast }$ である。凸包の該当部分は $P_4=(5,7)$ と $P_1=(10,3)$ を結ぶ線分（傾き $-\frac{4}{5}$）で、その $d=6$ での値は $7-\frac{4}{5}=\frac{31}{5}$。$d=6$ に対応する整数解（道）が凸包上にないため、双対ギャップ $p^{\ast }-d^{\ast }=\frac{4}{5}>0$ が生じる。弱双対性 $d^{\ast }\le p^{\ast }$ とも整合する。

以上より $(p^{\ast },d^{\ast })=\left(7,\frac{31}{5}\right)$。

$s$ から $t$ への有向道は次の 6 本である（$(c(P),d(P))$ の順に記す）。

• $P_1$: $s\to a\to t$ $(3,10)$
• $P_2$: $s\to a\to b\to t$ $(7,6)$
• $P_3$: $s\to a\to b\to c\to t$ $(6,7)$
• $P_4$: $s\to a\to c\to t$ $(7,5)$
• $P_5$: $s\to b\to t$ $(9,3)$
• $P_6$: $s\to b\to c\to t$ $(8,4)$

$p^{\ast }$: $d(P)\le 6$ を満たすのは $P_2,P_4,P_5,P_6$ で、費用はそれぞれ $7,7,9,8$ である。よって $p^{\ast }=7$。

$d^{\ast }$: 各道について $c(P)+\lambda (d(P)-6)$ を求める。

• $P_1$: $3+4\lambda$
• $P_2$: $7$
• $P_3$: $6+\lambda$
• $P_4$: $7-\lambda$
• $P_5$: $9-3\lambda$
• $P_6$: $8-2\lambda$

$\phi (\lambda )$ はこれら 6 本の 1 次関数の最小値であり、凹関数である。傾きが正の $P_1$ と傾きが負の $P_4$ が交わる点は $3+4\lambda =7-\lambda$ より $\lambda =4/5$ で、値は $31/5$ である。

$\lambda =4/5$ での他の直線の値を確認する。

• $P_2$: $7$
• $P_3$: $6.8$
• $P_5$: $6.6$
• $P_6$: $6.4$

いずれも $6.2$ より大きいので、$\phi (4/5)=31/5=6.2$ である。この点の左側では傾き $4$ の直線 $P_1$ が最小で増加し、右側では傾き $-1$ の直線 $P_4$ が最小で減少する。したがって最大値は $d^{\ast }=31/5$ で、$d^{\ast }<p^{\ast }$ なので双対ギャップがある。

答えは $(p^{\ast },d^{\ast })=(7,31/5)$。