整数計画法(integer programming)とは、線形の条件のもとで線形の目的関数を最適にする問題に、変数が整数であるという条件を加えた問題を解く方法で、人の割当、施設の選択、作るか作らないかの決定の計算に使う。整数の条件を外した線形計画緩和は最大化の問題の上界を与え、これを場合分けと組み合わせた分枝限定法は、有界な問題を有限回で解く。行列が完全単模で右辺が整数なら緩和の頂点は整数で、線形計画だけで解ける。切除平面は整数解を残して緩和の解を切り落とす不等式である。
整数計画法(integer programming)は、線形の不等式の条件のもとで線形の目的関数を最大にする問題に、変数が整数であるという条件を足した問題を解く方法である。機械の台数、人の割当、作るか作らないかの二者択一のように、半分だけ実行することに意味がない決定を扱う。
次の問題を考える。
$$
\text{最大化 } 21x+11y\quad\text{条件 } 7x+4y\le13,\ x,y\ge0,\ x,y\in\mathbb{Z}
$$
整数の条件を外すと、最適解は $(x,y)=(\tfrac{13}7,0)$、最適値は $39$ である。四捨五入した $(2,0)$ は $7x+4y=14$ で条件を破る。切り捨てた $(1,0)$ の値は $21$ である。本当の最適解は $(0,3)$ で、値は $33$ である。この問題では、整数の最適解は、線形計画法 の最適解から $x$ の値が大きく離れている。丸めでは解けないので、別の計算の手順が要る。
導入の問題の実行可能領域。青い三角形が整数の条件を外した領域、青い点が条件を満たす整数点である。星が線形計画の最適解 (13/7, 0)、緑の四角が整数の最適解 (0, 3)、黄の三角が点 (1, 1)。破線は目的関数の値が 39 と 33 の等高線である。
この記事では、次の 3 つの道具を、計算の手順とともに述べる。
$c\in\mathbb{R}^n$、$A\in\mathbb{R}^{m\times n}$、$b\in\mathbb{R}^m$ について、
$$
\text{最大化 } c\cdot x\quad\text{条件 } Ax\le b,\ x\in\mathbb{Z}^n
$$
を 整数計画問題(integer programming problem)という。整数線形計画問題 ともいう。一部の変数だけに整数の条件を課す問題を 混合整数計画問題、すべての変数を $0$ か $1$ に限る問題を 0-1 整数計画問題 という。実行可能解・最適解・最適値の語は 線形計画法 と同じである。最小化は目的関数の符号を変えて最大化に直す。
def-ip-problem の問題から $x\in\mathbb{Z}^n$ の条件を外した線形計画問題を、その問題の 線形計画緩和(LP 緩和、LP relaxation)という。0-1 の条件 $x_j\in\{0,1\}$ は $0\le x_j\le1$ に置きかえる。整数計画問題の最適値を $z_{\mathrm{IP}}$、線形計画緩和の最適値を $z_{\mathrm{LP}}$ と書く。
整数の行列 $A$ のすべての正方部分行列の行列式が $0,1,-1$ のどれかであるとき、$A$ は 完全単模(totally unimodular)であるという。$1\times1$ の部分行列を見ると、成分はすべて $0,\pm1$ である。
すべての実行可能な整数解が満たす不等式を 妥当な不等式 という。妥当な不等式のうち、線形計画緩和の現在の最適解を満たさないものを 切除平面(cutting plane)という。
計算の手順を使える条件は、次のとおりである。
(i) 有界:分枝限定法は、整数の変数に有限の上下限 $L_j\le x_j\le U_j$($L_j,U_j\in\mathbb{Z}$)があるときに使う。このとき候補の整数点は有限個なので、実行可能なら最適解が存在する。
(ii) 完全単模:線形計画緩和だけで解けるのは、行列が完全単模で右辺が整数のときである(十分条件)。
(iii) すべての変数が整数:prop-ip-gomory の切除平面は、スラック変数まで含めて整数であることを使う。
現実の条件を線形の不等式に直す公式である。$z,z_j$ は 0-1 の変数を表す。
| やりたいこと | 定式化 | 使える条件 | 根拠 |
|---|---|---|---|
| 使うときだけ固定費 $f$ がかかる | 費用 $fz$、条件 $x\le Uz$ | $0\le x\le U$ | 下の導出 |
| 2 つの不等式のどちらかが成り立つ | $a\cdot x\le\alpha+Mz$、$a'\cdot x\le\alpha'+M(1-z)$ | $M$ は実行可能領域で $a\cdot x-\alpha$ と $a'\cdot x-\alpha'$ の上界 | 下の導出 |
| $n$ 個の候補から $k$ 個以上選ぶ | $\sum_jz_j\ge k$ | — | 定義どおり |
| 0-1 の積 $w=xy$ | $w\le x$、$w\le y$、$w\ge x+y-1$、$w\ge0$ | $x,y\in\{0,1\}$ | 下の導出 |
| 上界 $U$ の整数を 0-1 で表す | $x=\sum_{i=0}^{L}2^iz_i$、$x\le U$ | $U\le2^{L+1}-1$ | 2 進展開 |
固定費:$z=0$ なら $x\le0$ より $x=0$ で固定費はかからない。$z=1$ なら条件は $x\le U$ だけで、固定費 $f$ がかかる。$x>0$ なのに $z=0$ とすることはできない。どちらか:$z=0$ なら 1 つ目の不等式がそのまま課され、2 つ目は $M$ の分だけ緩んで、$M$ の取り方から自動的に成り立つ。$z=1$ なら役割が入れかわる。積:$x=0$ または $y=0$ なら $w\le0$ と $w\ge0$ で $w=0$ である。$x=y=1$ なら $w\le1$ と $w\ge1$ で $w=1$ である。
| 公式 | 式 | 使える条件 | 根拠 |
|---|---|---|---|
| 緩和の上界 | $z_{\mathrm{IP}}\le z_{\mathrm{LP}}$ | 最大化の問題 | prop-ip-relax |
| 目的関数が整数値のとき | $z_{\mathrm{IP}}\le\lfloor z_{\mathrm{LP}}\rfloor$ | $c\in\mathbb{Z}^n$ | 整数解の値は整数 |
| Chvátal–Gomory の不等式 | $\lfloor u^{\mathsf T}A\rfloor x\le\lfloor u^{\mathsf T}b\rfloor$ | $u\ge0$、$x\ge0$ が整数(床関数は成分ごと) | 下の導出 |
| Gomory の切除平面 | $\sum_{j}f_jx_j\ge f_0$ | すべての変数が非負の整数 | prop-ip-gomory |
| 相対ギャップ | $(\text{上界}-\text{暫定値})/\lvert\text{暫定値}\rvert$ | 暫定値が $0$ でない | 止める判定の定義 |
$u\ge0$ なので $Ax\le b$ から $u^{\mathsf T}Ax\le u^{\mathsf T}b$ である。$x\ge0$ で $\lfloor u^{\mathsf T}A\rfloor\le u^{\mathsf T}A$(成分ごと)だから、$\lfloor u^{\mathsf T}A\rfloor x\le u^{\mathsf T}b$ である。$x$ が整数なら左辺は整数なので、右辺を切り下げてよい。たとえば $2x+3y\le4$($x,y\ge0$ は整数)に $u=\tfrac12$ を使うと $x+y\le2$ を得る。
def-ip-problem の問題と def-ip-relaxation の緩和について、次が成り立つ。
(1) 緩和の実行可能領域は整数計画問題の実行可能領域を含むので、両方に最適解があれば $z_{\mathrm{IP}}\le z_{\mathrm{LP}}$ である。
(2) 緩和の最適解 $x^*$ が整数のベクトルなら、$x^*$ は整数計画問題の最適解で、$z_{\mathrm{IP}}=z_{\mathrm{LP}}$ である。
(3) 実行可能な整数解 $\hat x$ が 1 つあれば $c\cdot\hat x\le z_{\mathrm{IP}}$ である。
上界は (1) から、下界は (3) から得られる。分枝限定法は、この 2 つの間の幅を縮める手順である。
分枝限定法(branch and bound)は、次の手順である。問題は「最大化 $c\cdot x$、条件 $Ax\le b$、$x\in\mathbb{Z}^n$、$L\le x\le U$」とし、場合分けの 1 つの枝を 節(node)とよび、上下限の組 $(\ell,u)$ で表す。
上の手順は有限回で止まる。止まったとき、暫定解があればそれは最適解で $\underline z$ が最適値であり、暫定解がなければ問題は実行不可能である。節の数は、$\Phi:=\sum_j(U_j-L_j)$ として $2^{\Phi+1}-1$ 以下である。
不変条件:手順のどの時点でも、「目的関数の値が $\underline z$ より大きい実行可能な整数解は、節の集まりのどれかの節の上下限の中にある」が成り立つことを示す。
はじめは節 $(L,U)$ がすべての実行可能な整数解を含むので成り立つ。手順の各段で、不変条件が保たれることを確かめる。節を取り出して処理するとき、その節の中の、値が $\underline z$ より大きい実行可能な整数解を $y$ とする。
止まること:節 $(\ell,u)$ に対し $\Phi(\ell,u):=\sum_j(u_j-\ell_j)$ とおく。緩和の解は $\ell_j\le v\le u_j$ を満たし、$v$ は整数でないので、$\ell_j\le\lfloor v\rfloor$ かつ $\lceil v\rceil\le u_j$ で、子の節の上下限は矛盾せず、$\Phi$ は親より $1$ 以上小さい。$\Phi\ge0$ は整数なので、深さは $\Phi(L,U)$ 以下である。各節の子は高々 2 つだから、節の総数は $2^{\Phi(L,U)+1}-1$ 以下である。
止まったときの結論:節の集まりが空なので、不変条件より、値が $\underline z$ より大きい実行可能な整数解はない。暫定解があれば、それは値 $\underline z$ の実行可能な整数解なので最適である。暫定解がなければ $\underline z=-\infty$ なので、実行可能な整数解は 1 つもない。$\square$
混合整数計画問題でも、整数の変数についてだけ手順の 4・5 を判定すれば、同じ証明が成り立つ(連続の変数にも有限の上下限を置き、$\Phi$ は整数の変数についての和とする)。節の数の上界は指数的で、実際に指数的に近い手間がかかる問題もある。手順の効率は、よい暫定解を早く見つけることと、上界が小さい定式化を使うことで決まる。
行列 $\begin{pmatrix}A\\C\end{pmatrix}$ が完全単模で、$b,d$ が整数のベクトルなら、多面体 $P:=\{x\mid x\ge0,\ Ax\le b,\ Cx=d\}$ の頂点はすべて整数のベクトルである。したがって、$P$ の上の線形計画問題に最適解があれば、整数の最適解があり、$z_{\mathrm{IP}}=z_{\mathrm{LP}}$ である。
$A,C$ の行と $-I$ の行を並べた行列を $M$ とする。$P$ を $M$ で表すと、$x\ge0$ は $-x\le0$ である。
$M$ も完全単模であることを示す。$M$ の正方部分行列 $N$ をとる。$-I$ から来た行は、$N$ の中で高々 1 つの非零成分 $-1$ をもつ。非零成分がなければ $\det N=0$ である。あれば、その行で余因子展開すると、$\det N$ は $\pm$ ひとまわり小さい部分行列の行列式になる。これを繰り返すと、$\det N$ は $0$ か、$A,C$ の部分の部分行列の行列式の $\pm1$ 倍(部分行列がなくなれば $\pm1$)になる。よって $\det N\in\{0,\pm1\}$ である。
$z$ を $P$ の頂点とする。頂点では、等号で成り立つ条件の行のうち一次独立な $n$ 本で $z$ が決まる(多面体 の定理「頂点の特徴づけ」)。その $n$ 行からなる $M$ の部分行列を $N$、対応する右辺を $e$ とすると、$Nz=e$ で $\det N=\pm1$ である。$e$ は $b,d,0$ の成分からなる整数のベクトルである。Cramerの公式 より $z$ の各成分は整数成分の行列の行列式を $\pm1$ で割ったもので、整数である。
$P$ は $x\ge0$ の中にあるので直線を含まない。線形計画法 の定理「最適解は頂点でとれる」により、最適解があれば頂点に最適解がある。これは整数のベクトルなので、prop-ip-relax の (2) が使える。$\square$
完全単模であることを定義どおりに確かめるには、すべての正方部分行列を調べることになる。グラフから来る行列では、次の命題がその手間を省く。
どの列も、$+1$ を 1 つと $-1$ を 1 つもち、ほかの成分が $0$ である行列は完全単模である。さらに、どの列にも $1$ がちょうど 2 つあり、行の集合を 2 つに分けると各列の $1$ が別々の組に入る $0$–$1$ 行列も完全単模である。
前半を、正方部分行列 $N$ の大きさに関する帰納法で示す。大きさ $1$ は成分が $0,\pm1$ なのでよい。大きさ $k\ge2$ の $N$ の列を見る。零の列があれば $\det N=0$ である。非零成分がただ 1 つの列があれば、その列で展開して、大きさ $k-1$ の場合に帰着する。残りの場合、$N$ のどの列も $+1$ と $-1$ を 1 つずつもつので、すべての行を足すと零ベクトルになり、$\det N=0$ である。
後半は、2 つの組の一方の行に $-1$ を掛けると前半の形の行列になる。行に $-1$ を掛けても部分行列の行列式の符号が変わるだけなので、完全単模のままである。$\square$
前半の行列は有向グラフの、後半の行列は 二部グラフ の、頂点と辺の接続行列である。割当問題 の条件の行列は後半の形なので、線形計画緩和の頂点はそのまま割当を与える。一般の判定法と、どの整数の右辺でも頂点が整数になることとの同値は、完全単模行列 の定理「Ghouila-Houri の判定法」と定理「Hoffman–Kruskal の定理」にある。
$A,b$ が整数で、すべての変数が非負の整数である問題を考える。スラック変数 $s=b-Ax$ も非負の整数である。単体法 の最適な辞書(線形計画法 の節「単体法の仕組み」)の 1 行を
$$
x_i+\sum_{j\in N}\bar a_jx_j=\bar b
$$
と書く。$x_i$ は基底の変数(スラック変数も変数に数える)、$N$ は非基底の変数の添字の集合である。$\bar b$ は緩和の最適解での $x_i$ の値である。
上の行で $\bar b$ が整数でないとする。$f_j:=\bar a_j-\lfloor\bar a_j\rfloor$、$f_0:=\bar b-\lfloor\bar b\rfloor>0$ とおく。このとき不等式
$$
\sum_{j\in N}f_jx_j\ge f_0
$$
は、すべての実行可能な整数解が満たし、現在の線形計画緩和の最適解は満たさない。
実行可能な整数解をとる。辞書の行は等式の条件の線形結合なので、この解も満たす。
$$
x_i+\sum_{j\in N}\lfloor\bar a_j\rfloor x_j-\lfloor\bar b\rfloor=f_0-\sum_{j\in N}f_jx_j
$$
と書き直す。左辺は整数である。右辺は、$f_j\ge0$、$x_j\ge0$ より $f_0$ 以下で、$f_0< 1$ である。$1$ より小さい整数は $0$ 以下なので、右辺 $\le0$、すなわち $\sum_jf_jx_j\ge f_0$ である。
現在の最適解では非基底の変数がすべて $0$ なので、左辺は $0$ で、$0< f_0$ より不等式を満たさない。$\square$
この命題が保証するのは、1 回の切除の妥当性である。切除を繰り返すだけで有限回で止まることは、この命題からは分からない。実際の計算では、分枝限定法の節ごとに切除平面を足して上界を下げる(分枝切除法)。
整数計画問題は、全体として次の順に解く。
| 緩和の結果 | やること | 理由 |
|---|---|---|
| 実行不可能 | 節を捨てる | 節の中に実行可能な点がない |
| 値が暫定値以下 | 節を捨てる | 節の中に暫定解よりよい点がない |
| 整数解 | 暫定解を更新して節を捨てる | 節の中で最良の点が求まった |
| 値が暫定値より大きく、整数でない | 整数でない変数で分枝する | 2 つの子の節に整数解がすべて入る |
最大化 $21x+11y$、条件 $7x+4y\le13$、$x,y\ge0$、$x,y\in\mathbb{Z}$($x,y\le13$ は条件から従う)。
使う公式:thm-ip-bnb。
答え:最適解は $(x,y)=(0,3)$、最適値は $33$ である。上界 $z_{\mathrm{LP}}=39$ との差は $6$ である。
$x\le\cdot$ の側を先に調べる。
| 節 | 加えた条件 | 緩和の解 | 緩和の値 | 処理 |
|---|---|---|---|---|
| 1 | なし | $(13/7,0)$ | $39$ | $x$ で分枝 |
| 2 | $x\le1$ | $(1,3/2)$ | $37.5$ | $y$ で分枝 |
| 3 | $x\le1,\ y\le1$ | $(1,1)$ | $32$ | 整数解、暫定値 $32$ |
| 4 | $x\le1,\ y\ge2$ | $(5/7,2)$ | $37$ | $x$ で分枝 |
| 5 | $x\le0,\ y\ge2$ | $(0,13/4)$ | $35.75$ | $y$ で分枝 |
| 6 | $x\le0,\ 2\le y\le3$ | $(0,3)$ | $33$ | 整数解、暫定値 $33$ |
| 7 | $x\le0,\ y\ge4$ | — | — | 実行不可能 |
| 8 | $x=1,\ y\ge2$ | — | — | 実行不可能($7+8>13$) |
| 9 | $x\ge2$ | — | — | 実行不可能($14>13$) |
4 つの品物の価値が $16,19,23,28$、重さが $2,3,4,5$ で、重さの合計の上限が $7$ である。価値の合計を最大にする(ナップサック問題 の 0-1 の場合)。
使う公式:thm-ip-bnb。緩和は、価値と重さの比が大きい順(ここでは品物の番号の順)に詰めて、最後の 1 つを端数にすれば解ける。
答え:品物 1 と 4 を選び、最適値は $44$ である。線形計画緩和の値は $46.5$ である。
$x_3=0$ の側を先に調べる。
| 加えた条件 | 緩和の解 | 緩和の値 | 処理 |
|---|---|---|---|
| なし | $(1,1,1/2,0)$ | $46.5$ | $x_3$ で分枝 |
| $x_3=0$ | $(1,1,0,2/5)$ | $46.2$ | $x_4$ で分枝 |
| $x_3=x_4=0$ | $(1,1,0,0)$ | $35$ | 整数解、暫定値 $35$ |
| $x_3=0,\ x_4=1$ | $(1,0,0,1)$ | $44$ | 整数解、暫定値 $44$ |
| $x_3=1$ | $(1,1/3,1,0)$ | $45.33\ldots$ | $x_2$ で分枝 |
| $x_3=1,\ x_2=0$ | $(1,0,1,1/5)$ | $44.6$ | $\lfloor44.6\rfloor=44$ なので限定 |
| $x_3=x_2=1$ | $(0,1,1,0)$ | $42$ | 限定 |
価値が整数なので、$44.6$ の節は切り下げの判定で捨てられる。この判定を使わなければ、$x_4$ で分枝して、値 $39$ の節と実行不可能な節に分かれる。結果は同じである。
工場 1、2 から顧客 1、2、3 へ、需要 $8,6,5$ を満たすように運ぶ。工場を使うと固定費 $20,30$ がかかり、運べる量の上限は $20,15$ である。単位あたりの輸送費は、工場 1 から $2,3,5$、工場 2 から $4,2,1$ である。
使う公式:固定費の定式化。工場 $i$ を使うとき $z_i=1$ とし、$\sum_jx_{ij}\le u_iz_i$ を置く。
答え:工場 1 だけを使い、費用の最小値は $79$ である。線形計画緩和の値は $63$ である。
$(z_1,z_2)$ の 4 通りで調べる。総需要は $19$ なので、工場が 0 個の場合と工場 2 だけの場合は実行不可能である。工場 1 だけなら、固定費 $20$ と輸送費 $2\cdot8+3\cdot6+5\cdot5=59$ で $79$ である。両方を使うと、顧客ごとに安い工場から運べば(上限は超えない)、固定費 $50$ と輸送費 $2\cdot8+2\cdot6+1\cdot5=33$ で $83$ である。緩和の最適解の 1 つは $z_1=0.7$、$z_2=\tfrac13$ である。両方の工場を、使う量に比例した分だけの固定費で使えるので、$79-63=16$ の差が出る。条件 $x_{ij}\le\min\{u_i,d_j\}z_i$ を足して強めると、この例では緩和の値が $79$ に上がり、差が $0$ になる。
費用の行列
$$
\begin{pmatrix}4&2&8\\4&3&7\\3&1&6\end{pmatrix}
$$
で、人と仕事を 1 対 1 に割り当てて費用の和を最小にする。
使う公式:prop-ip-incidence、thm-ip-tu。
答え:最小費用は $12$ である。整数の条件を外した線形計画(条件 $\sum_jx_{ij}=1$、$\sum_ix_{ij}=1$、$x\ge0$)でも最適値は $12$ で、頂点の解は割当になる。
条件の行列は、各列 $x_{ij}$ に人 $i$ の行と仕事 $j$ の行の $1$ が 1 つずつあるので、prop-ip-incidence の後半により完全単模である。$3!=6$ 通りの費用は $13,12,12,12,13,14$ で、最小は $12$ である。最適な割当は 3 通りある(人 1, 2, 3 に仕事 1, 3, 2、または 2, 1, 3、または 2, 3, 1)。整数の計算の方法は 割当問題 のハンガリー法がある。
最大化 $y$、条件 $3x+2y\le6$、$-3x+2y\le0$、$x,y\ge0$、$x,y\in\mathbb{Z}$。
使う公式:prop-ip-gomory。
答え:緩和の最適解は $(1,\tfrac32)$ で値は $\tfrac32$ である。切除平面は $s_1+s_2\ge2$、すなわち $y\le1$ である。これを足すと緩和の最適値は $1$ に下がり、整数解 $(1,1)$ が値 $1$ を達成するので、最適値は $1$ である。
スラック変数を $s_1:=6-3x-2y$、$s_2:=3x-2y$ とする。最適な辞書で $y$ の行は $y+\tfrac14s_1+\tfrac14s_2=\tfrac32$ である。$f_1=f_2=\tfrac14$、$f_0=\tfrac12$ なので、切除平面は $\tfrac14s_1+\tfrac14s_2\ge\tfrac12$、すなわち $s_1+s_2\ge2$ である。$s_1+s_2=6-4y$ を代入すると $y\le1$ である。切除後の緩和の最適解は $y=1$ の線分 $\tfrac23\le x\le\tfrac43$ 全体で、頂点は整数でないが、値 $1$ は整数解 $(1,1)$ で達成されるので、prop-ip-relax の (1) と (3) から最適である。
有限集合 $U=\{e_1,\dots,e_n\}$、その部分集合 $S_1,\dots,S_m$(和集合が $U$)、重み $w_j\ge0$ について、0-1 整数計画問題
$$
\text{最小化 }\sum_{j=1}^mw_jx_j\quad\text{条件 }\sum_{j:\,e_i\in S_j}x_j\ge1\ (i=1,\dots,n),\ x_j\in\{0,1\}
$$
を 集合被覆問題 という($x_j=1$ を「$S_j$ を採る」と読む)。$f$ を、1 つの要素を含む集合の個数の最大値とする。緩和を解いても最適解は分からないが、丸め方を選べば最適値の $f$ 倍以下という保証がつく。
使う公式:prop-ip-relax(最小化の問題なので、向きが逆になり $z_{\mathrm{LP}}\le z_{\mathrm{IP}}$)。
答え:緩和の最適解 $x^*$ について $J:=\{j\mid x^*_j\ge1/f\}$ とおくと、$\{S_j\}_{j\in J}$ は $U$ を覆い、重みは $\sum_{j\in J}w_j\le f\,z_{\mathrm{LP}}\le f\,z_{\mathrm{IP}}$ である(近似アルゴリズム の定理「決定的な丸めによる f-近似」)。グラフ の頂点被覆(辺を要素、頂点 $v$ に接する辺の集合を $S_v$ とみる)では $f=2$ で、$x^*_v\ge\tfrac12$ の頂点を採れば最適値の $2$ 倍以下になる。ex-ip-counterexamples の三角形では、緩和の解 $(\tfrac12,\tfrac12,\tfrac12)$ から 3 頂点すべてを採り、重み $3=2z_{\mathrm{LP}}$ で、$z_{\mathrm{IP}}=2$ の $1.5$ 倍である。
覆うこと:要素 $e_i$ の条件 $\sum_{j:\,e_i\in S_j}x^*_j\ge1$ の左辺の項は $f$ 個以下なので、そのうち少なくとも 1 つは $1/f$ 以上である。その $j$ は $J$ に入り、$e_i$ は覆われる。重み:$j\in J$ なら $1\le fx^*_j$ で、$w_j\ge0$ なので $\sum_{j\in J}w_j\le\sum_{j\in J}w_jfx^*_j\le f\sum_{j=1}^mw_jx^*_j=f\,z_{\mathrm{LP}}$ である。整数の最適解は緩和の実行可能解なので $z_{\mathrm{LP}}\le z_{\mathrm{IP}}$ である。
閾値の選び方:$U=\{e_1\}$、$S_1=S_2=S_3=\{e_1\}$、重みはすべて $1$ とする($f=3$)。$x^*=(\tfrac13,\tfrac13,\tfrac13)$ は値 $1=z_{\mathrm{LP}}$ の緩和の最適解である。四捨五入($\tfrac12$ 以上を採る)ではどの集合も採らず、$e_1$ が覆われない。閾値 $\tfrac13$ では 3 つとも採り、重みは $3=f\,z_{\mathrm{LP}}$ で、評価の $f$ 倍はこの丸め方では改善できない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 有界(最適解の存在) | 最大化 $x-\sqrt2y$、条件 $x-\sqrt2y\le0$、$y\ge1$、$x\ge0$、整数 | 上限 $0$ はとられず、最適解がない |
| 有界(手順の停止) | 最大化 $-x$、条件 $2x-2y=1$、$x,y\ge0$、整数 | 分枝限定法が止まらない |
| 完全単模 | 三角形の頂点被覆:行列の行列式が $2$ | 緩和の頂点が整数でなく、$z_{\mathrm{LP}}\ne z_{\mathrm{IP}}$ |
| 右辺が整数 | 最大化 $x$、条件 $x\le\tfrac12$、$x\ge0$ | 行列 $(1)$ は完全単模だが、頂点 $\tfrac12$ は整数でない |
| すべての変数が整数 | $x+\tfrac32s=\tfrac32$ で $s$ が連続の変数 | Gomory の切除平面が実行可能な点を切り落とす |
最適解の存在:$\sqrt2$ は無理数なので、$y\ge1$ の整数点では $x-\sqrt2y\ne0$ で、値はつねに負である。一方、$\sqrt2$ を下から近似する分数 $x/y$ をとると、$(1,1),(7,5),(41,29),(239,169)$ で値は $-0.4142,\ -0.0711,\ -0.0122,\ -0.0021$ と $0$ に近づく。一般に $x^2-2y^2=-1$ の解 $(x,y)$ から $(3x+4y,2x+3y)$ を作ると同じ式の解になるので、解は無限にあり、$x-\sqrt2y=-1/(x+\sqrt2y)$ はいくらでも $0$ に近づく。実行可能領域が有界でないことだけが条件を破っている。
手順の停止:左辺 $2x-2y$ はつねに偶数なので、整数解はない。緩和の最適解は $(\tfrac12,0)$ である。$x\le0$ の節は実行不可能で、$x\ge1$ の節の解は $(1,\tfrac12)$ である。$y\le0$ の節は実行不可能で、$y\ge1$ の節の解は $(\tfrac32,1)$ である。同じことが続き、節 $(k,k-\tfrac12)$ と $(k+\tfrac12,k)$ が際限なく現れる。$x,y$ に上限を置けば、thm-ip-bnb により有限回で止まる。
完全単模:三角形の 3 辺に対応する条件 $x_1+x_2\ge1$、$x_2+x_3\ge1$、$x_1+x_3\ge1$、$0\le x_i\le1$ の下で $x_1+x_2+x_3$ を最小にする。係数の行列の行列式は $2$ で、完全単模でない。緩和の最適解は $(\tfrac12,\tfrac12,\tfrac12)$ で値は $\tfrac32$、整数の最適値は $2$ である(2 頂点を選ぶ)。二部グラフ でないので、prop-ip-incidence の後半は使えない。
右辺の整数性:緩和の最適値は $\tfrac12$、整数の最適値は $0$ である。
整数の変数:$x+\tfrac32s=\tfrac32$、$x\ge0$ は整数、$s\ge0$ は連続の変数とする。この行で $x$ を基底とすると $f_s=\tfrac12$、$f_0=\tfrac12$ で、prop-ip-gomory の形の不等式は $\tfrac12s\ge\tfrac12$ である。実行可能な点 $(x,s)=(1,\tfrac13)$ では $\tfrac12s=\tfrac16$ なので、この不等式は成り立たない。証明で「左辺は整数」とした段が崩れている。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 線形計画の解を丸めれば最適解だと思う | 丸めた点は実行不可能なことがあり、最適解から遠いこともある | 導入の問題、ex-ip-intro。比の保証がつく丸め方は ex-ip-setcover-round |
| 最大化で緩和の値を下界に使う | 最大化の問題では緩和の値は上界、整数解の値が下界 | prop-ip-relax |
| $M$ をとにかく大きくする | 大きな $M$ は緩和を弱め、数値も不安定にする。必要最小の値にする | ex-ip-fixed |
| $M$ を小さくしすぎる | 上界になっていない $M$ は実行可能解を切り落とす | 公式の表の条件 |
| 暫定値と緩和の値の差が縮まらないので途中の解を最適だと報告する | 節の集まりが空か、ギャップが $0$ になるまで、最適とはいえない | thm-ip-bnb |
| 連続の変数を含む行から Gomory の切除平面を作る | スラック変数まで整数である行だけで使う | ex-ip-counterexamples |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する