整数計画の線形計画緩和と整数性

整数計画問題の線形計画緩和を作り、緩和の頂点が整数になるか（完全単模性）や、安定集合問題の緩和の頂点が ${0, \frac{1}{2}, 1}$ に値をとること（半整数性）を使って、頂点の個数や緩和の最適値と整数最適値の差を求められる

前提

多面体の頂点（基底解）（大学院数学凸最適化・組合せ最適化）
線形計画の双対定理（大学院数学凸最適化・組合せ最適化）
最大独立集合と最小頂点被覆（大学数学グラフ理論）

この技能までの道筋（58 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

三角形の角の大きさ（算数平面図形）
対頂角と平行線の同位角・錯角（中学数学平面図形）
三角形の外角と角の組み合わせ（中学数学平面図形）
小数の四則計算（算数計算と数のきまり）
分数のたし算・ひき算（算数計算と数のきまり）
分数のかけ算・わり算（算数計算と数のきまり）
小数と分数のまじった計算（算数計算と数のきまり）
逆算（□ を求める）（算数計算と数のきまり）
正負の数の加法・減法（中学数学数と式）
四則の混じった計算の順序（算数計算と数のきまり）
正負の数の乗除・累乗と四則混合（中学数学数と式）
分配法則を使った計算のくふう（算数計算と数のきまり）
文字式の計算（同類項・分配法則）（中学数学数と式）
1 次方程式の解き方（中学数学方程式）
二等辺三角形の角（中学数学平面図形）
平行四辺形と特別な四角形の性質（中学数学平面図形）
三角形・四角形の面積（算数平面図形）
約数の見つけ方（算数整数の性質）
素因数分解と約数の個数（算数整数の性質）
平方根の意味と根号の簡単化（中学数学数と式）
三平方の定理（中学数学相似と三平方の定理）
乗法公式による展開（中学数学数と式）
折り返した図形の角と長さ（中学数学平面図形）
三平方の定理と平面図形（中学数学相似と三平方の定理）
ベクトルの演算と成分（数学C ベクトル）
行列の和・積と 2 次の逆行列（大学数学線形代数）
掃き出し法と連立 1 次方程式（大学数学線形代数）
行列の階数と解の存在（大学数学線形代数）
最大公約数と最小公倍数（算数整数の性質）
比の性質と簡単な比（算数割合と比）
相似な三角形と長さの比（算数平面図形）
三角形の相似条件と対応する辺の長さ（中学数学相似と三平方の定理）
平行線と線分の比（中学数学相似と三平方の定理）
2点間の距離と内分点・外分点（数学II 図形と方程式）
比例・反比例の式とグラフ（中学数学関数）
関数 $y = a x^{2}$ の式と変域（中学数学関数）
因数分解（中学数学数と式）
平方完成と 2 次関数のグラフ（数学I 2次関数）
円の方程式（数学II 図形と方程式）
連立方程式の解き方（加減法・代入法）（中学数学方程式）
1 次関数の式の求め方（中学数学関数）
直線の方程式（数学II 図形と方程式）
不等式の表す領域（数学II 図形と方程式）
多面体の頂点（基底解）（大学院数学凸最適化・組合せ最適化）
点と直線の距離（数学II 図形と方程式）
2 次不等式（数学I 2次関数）
円と直線の位置関係と弦の長さ（数学II 図形と方程式）
2直線の平行・垂直（数学II 図形と方程式）
円の接線（数学II 図形と方程式）
領域における最大・最小（数学II 図形と方程式）
線形計画の双対定理（大学院数学凸最適化・組合せ最適化）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）
最大独立集合と最小頂点被覆（大学数学グラフ理論）

説明

変数が整数に限られる最適化問題（整数計画問題）から、整数条件だけを外した線形計画問題（線形計画緩和）を作り、その最適値で整数最適値を評価できるようになります。さらに、制約行列が完全単模なら緩和の頂点がすべて整数になること、安定集合（独立集合）問題の緩和の頂点は各成分が $0, \frac{1}{2}, 1$ のどれかになること（半整数性）を使い、緩和の頂点の様子や、緩和の最適値と整数最適値の差（整数性ギャップ）を求められるようになります。組合せ最適化の問題が「線形計画で解けるか」「どのくらい近似できるか」を判断する基本の考え方です。

なぜそうしてよいのか

整数計画問題「 $A x \leq b$ , $x \in Z^{n}$ のもとで $c^{⊤} x$ を最大化」から整数条件 $x \in Z^{n}$ を外したものを線形計画緩和といいます。緩和の実行可能領域 $P = {x ∣ A x \leq b}$ は整数解をすべて含むので、最大化なら $z_{LP} \geq z_{IP}$ （最小化なら $z_{LP} \leq z_{IP}$ ）です。 $P$ が有界で空でなければ線形計画の最適値はある頂点で達成されるので、 $P$ の頂点がすべて整数点なら $z_{LP} = z_{IP}$ となり、整数計画を線形計画として解けます。

頂点が整数になる代表的な条件が完全単模性です。行列 $A$ のどの正方部分行列（行と列を同じ個数選んで作る行列）の行列式も $0, 1, - 1$ のどれかであるとき、 $A$ を完全単模といいます。 $P = {x ∣ A x \leq b}$ の頂点 $x ˉ$ では、活性な制約から一次独立な $n$ 本を選ぶと $B x ˉ = b_{B}$ （ $B$ は $A$ の $n$ 行からなる正則な正方行列）が成り立ち、 $x ˉ$ はこの連立方程式のただ 1 つの解です。クラメルの公式 $x ˉ_{j} = det B_{j} / det B$ （ $B_{j}$ は $B$ の第 $j$ 列を $b_{B}$ に置き換えた行列）で、 $A$ が完全単模かつ $b$ が整数なら $det B = \pm 1$ で $det B_{j}$ は整数なので、 $x ˉ$ は整数です。 $x \geq 0$ のような制約を加えても、 $A$ に単位行列を縦に並べた行列はやはり完全単模になります。二部グラフの頂点と辺の接続行列（行が辺、列が頂点で、辺の両端の成分が 1）は完全単模であることが知られています。一方、三角形の接続行列 $101110011$ の行列式は $2$ で、完全単模ではありません。

グラフ $G = (V, E)$ の安定集合問題の緩和 $max \sum_{v} x_{v}$ s.t. $x_{u} + x_{v} \leq 1 (uv \in E)$ , $0 \leq x_{v} \leq 1$ は完全単模とは限りませんが、頂点は半整数（各成分が $0, \frac{1}{2}, 1$ ）です。頂点 $x$ に対し $U_{+} = {v ∣ 0 < x_{v} < \frac{1}{2}}$ , $U_{-} = {v ∣ \frac{1}{2} < x_{v} < 1}$ とし、小さい $ε > 0$ で $y = x + ε (1_{U_{+}} - 1_{U_{-}})$ , $z = x - ε (1_{U_{+}} - 1_{U_{-}})$ を作ります（ $1_{U}$ は $U$ の頂点で 1、他で 0 のベクトル）。等号で成り立つ辺制約 $x_{u} + x_{v} = 1$ では、 $u \in U_{+}$ なら $x_{v} = 1 - x_{u} \in (\frac{1}{2}, 1)$ で $v \in U_{-}$ となり変化が打ち消し合い、他の制約は余裕があるので、 $y, z$ は実行可能です。 $x = \frac{y + z}{2}$ で、 $x$ が頂点であることから $y = z$ 、つまり $U_{+} = U_{-} = \emptyset$ となり、成分は $0, \frac{1}{2}, 1$ に限られます。

手順

整数計画問題の変数・目的関数・制約を書き、整数条件（ $x_{v} \in {0, 1}$ など）を区間の条件（ $0 \leq x_{v} \leq 1$ ）に置き換えて線形計画緩和を作る。
向きを確認する：最大化なら $z_{LP} \geq z_{IP}$ 、最小化なら $z_{LP} \leq z_{IP}$ 。
制約行列が完全単模か調べる（二部グラフの接続行列など）。完全単模で右辺が整数なら、頂点はすべて整数で $z_{LP} = z_{IP}$ 。
安定集合問題の緩和なら、頂点の各成分は $0, \frac{1}{2}, 1$ のどれかであることを使って、候補となる頂点（例：全成分 $\frac{1}{2}$ ）を絞り込む。
緩和の最適値を、実行可能解（下からの評価）と制約の非負結合（上からの評価、双対の実行可能解にあたる）を一致させて確定する。
整数最適値を別に求め（独立数 $α (G)$ など）、差 $z_{LP} - z_{IP}$ を計算する。

例題

完全グラフ $K_{4}$ （頂点 4 個、どの 2 頂点も辺で結ばれている）の安定集合問題の線形計画緩和 $max v = 1 \sum 4 x_{v} s.t. x_{u} + x_{v} \leq 1 (1 \leq u < v \leq 4), 0 \leq x_{v} \leq 1$ の最適値を $z_{LP}$ とする。 $z_{LP} - α (K_{4})$ を求めよ。

例題の解答

手順 1：整数条件 $x_{v} \in {0, 1}$ を $0 \leq x_{v} \leq 1$ に置き換えたものが、問題の線形計画緩和である。

手順 2：最大化なので $z_{LP} \geq α (K_{4})$ となるはずである。

手順 3： $K_{4}$ は三角形を含むので接続行列は完全単模でなく、頂点が整数とは限らない。

手順 4：半整数性より、頂点の成分は $0, \frac{1}{2}, 1$ のどれか。全成分 $\frac{1}{2}$ の点 $x = (\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2})$ は、どの辺でも $\frac{1}{2} + \frac{1}{2} = 1$ で実行可能であり、目的関数値は $2$ 。

手順 5：上からの評価として、6 本の辺制約をすべて足すと、各頂点は 3 本の辺に属するので $3 \sum_{v} x_{v} \leq 6$ 、すなわち $\sum_{v} x_{v} \leq 2$ 。下からの評価 $2$ と一致するので $z_{LP} = 2$ 。

手順 6： $K_{4}$ ではどの 2 頂点も隣接するので、安定集合は頂点 1 個までで $α (K_{4}) = 1$ 。よって $z_{LP} - α (K_{4}) = 2 - 1 = 1$ 。

したがって、求める差は $1$ 。

答え: $1$

よくある誤り

緩和の最適値を切り捨てれば整数最適値になると思ってしまう誤り。 $K_{4}$ では $⌊ z_{LP} ⌋ = ⌊ 2 ⌋ = 2$ だが、 $α (K_{4}) = 1$ 。正しくは $z_{LP}$ は（最大化では）上界を与えるだけで、整数最適値は別に求める必要がある。
不等式の向きを逆にして、最大化問題で $z_{LP} \leq z_{IP}$ としてしまう誤り。緩和は実行可能領域を広げるので、正しくは最大化なら $z_{LP} \geq z_{IP}$ （例：三角形で $z_{LP} = \frac{3}{2} \geq 1 = α$ ）、最小化なら $z_{LP} \leq z_{IP}$ 。
成分がすべて $0, \pm 1$ なら完全単模だと判断してしまう誤り。三角形の接続行列 $101110011$ は成分が $0, 1$ だけだが行列式が $2$ で、対応する緩和には整数でない頂点 $(\frac{1}{2}, \frac{1}{2}, \frac{1}{2})$ がある。正しくはすべての正方部分行列の行列式が $0, \pm 1$ であることを確かめる。
完全単模なら右辺 $b$ に関係なく頂点が整数だと思ってしまう誤り。例えば $A = (1)$ は完全単模だが、 $x \leq \frac{1}{2}$ , $x \geq 0$ の頂点 $x = \frac{1}{2}$ は整数でない。正しくは「 $A$ が完全単模かつ $b$ が整数ベクトル」のとき頂点が整数になる。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

難易度 1（大学院の講義の例題レベル）
頂点集合を $V = {1, 2, 3, 4, 5, 6, 7}$ 、辺集合を
$E = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}, {6, 7}, {7, 1}}$
とする閉路グラフ $C_{7}$ を考える。 $C_{7}$ の最大安定集合問題の整数計画
$(IP) maximize v = 1 \sum 7 x_{v} subject to x_{u} + x_{v} \leq 1 ({u, v} \in E), x_{v} \in {0, 1} (v \in V)$
の最適値を $z_{IP}$ とし、 $x_{v} \in {0, 1}$ を $0 \leq x_{v} \leq 1$ に置き換えた線形計画緩和 $(LP)$ の最適値を $z_{LP}$ とする。 $z_{LP} - z_{IP}$ を求めよ。

整数計画の線形計画緩和と整数性

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題