Fourier–Motzkinの消去法

同義語:Fourier-Motzkinの消去法フーリエ・モツキンの消去法Fourier–Motzkin eliminationFourier-Motzkin elimination

概要

Fourier–Motzkinの消去法(Fourier–Motzkin elimination)とは、連立 1 次不等式から変数を 1 つずつ消す方法である。消す変数の上界と下界の組ごとに不等式に正の数を掛けて足すと、得られた系の解の全体はもとの解の全体の射影に等しいので、多面体の射影はまた多面体であり、全部の変数を消せば解の有無が判定できる。結合の係数を追うと、解がないことの証拠が得られ、Farkas の補題の形の択一定理が位相を使わずに示せる。不等式の本数は指数的に増えることがあるが、$k$ 回の消去のあとの射影は、もとの不等式を高々 $k+1$ 本使った結合だけで書ける。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 多面体, 線形計画法, Gaussの消去法

Fourier–Motzkinの消去法(Fourier–Motzkin elimination)は、連立 1 次不等式から変数を 1 つずつ消していく方法である。連立 1 次方程式を Gaussの消去法 で解くのと同じように、変数の少ない系へ順に直し、最後に残った系から解を求める。
小さい例を見る。$x,y$ の不等式系
$$ x+y\le4,\qquad -x+y\le2,\qquad -y\le-1 $$
から $x$ を消す。最初の 2 つは $x\le4-y$ と $x\ge y-2$ である。この 2 つを満たす $x$ があることは、下界が上界以下であること、すなわち $y-2\le4-y$ と同じである。これは $y\le3$ である。$x$ を含まない不等式 $-y\le-1$ はそのまま残すので、$x$ を消した系は $1\le y\le3$ になる。図で見ると、この系は三角形の領域 $P$ を $y$ 軸に射影した線分である。$y$ を $[1,3]$ から選べば、$x$ は区間 $[y-2,4-y]$ から選べる。
不等式の表す三角形 P と、その y 軸への射影 1 ≤ y ≤ 3 の図。 不等式の表す三角形 P と、その y 軸への射影 1 ≤ y ≤ 3 の図。
変数を 1 つ消すことは、多面体 を座標軸に沿って射影することである。この記事では次を証明する。

  • 1 変数の消去で得られる系の解の全体は、もとの系の解の全体の射影に等しい(thm-fm-step)。
  • 消去の各段の不等式は、もとの不等式に $0$ 以上の数を掛けて足したものである。これを追うと、解がないことの証拠が得られる(thm-fm-certificate)。
  • 不等式の数は爆発しうる(ex-fm-octahedron)が、$k$ 回の消去のあとの射影は、もとの不等式を高々 $k+1$ 本使った結合だけで書ける(thm-fm-support)。

定義と手順

以下、$\mathbb{R}^n$ の点を縦ベクトルとみなし、内積を $a\cdot x$ と書く。$m\times n$ 行列 $A$ の第 $i$ 行を $a_i^{\mathsf T}$ とし、$Ax\le b$ は $m$ 個の不等式 $a_i\cdot x\le b_i$ がすべて成り立つことを表す。ベクトルの不等号は成分ごとの不等号である。$n\ge2$ のとき $x=(x',x_n)$($x'\in\mathbb{R}^{n-1}$)、$a_i=(a_i',a_{in})$ と書く。

1 変数の消去

不等式系 $Ax\le b$ の行の番号を、$x_n$ の係数の符号で
$$ I_+:=\{i\mid a_{in}>0\},\qquad I_-:=\{i\mid a_{in}< 0\},\qquad I_0:=\{i\mid a_{in}=0\} $$
に分ける。次の 2 種類の不等式からなる $x'$ の系を、$Ax\le b$ から $x_n$ を消去した系 という。
(a) $i\in I_0$ について、$a_i'\cdot x'\le b_i$。
(b) $i\in I_+$ と $j\in I_-$ の組ごとに、$i$ 行の $(-a_{jn})$ 倍と $j$ 行の $a_{in}$ 倍の和
$$ \bigl(-a_{jn}a_i'+a_{in}a_j'\bigr)\cdot x'\le-a_{jn}b_i+a_{in}b_j. $$
$n=1$ のときは $x'$ がないものと読み、$x_1$ を消去した系は、変数を含まない不等式 $0\le\beta$ の集まりである。

(b) の不等式で $x_n$ の係数は $-a_{jn}a_{in}+a_{in}a_{jn}=0$ である。掛ける数 $-a_{jn}$、$a_{in}$ はどちらも正である。$I_+$ または $I_-$ が空なら (b) の不等式はなく、$I_0$ の行だけが残る。
計算の手順は次のとおりである。

  1. 消す順を決める:等式があれば、先に Gaussの消去法 と同じ代入で変数を減らす。残った変数のうち、$\lvert I_+\rvert\lvert I_-\rvert-\lvert I_+\rvert-\lvert I_-\rvert$ が小さいものから消すと、不等式の増え方が抑えられる。
  2. 消去する:def-fm-step で変数を 1 つ消す。同じ不等式の重複と、ほかの不等式から従うことが分かる不等式は捨ててよい。
  3. 判定する:すべての変数を消すと $0\le\beta$ の形だけが残る。$\beta< 0$ のものがあれば解はない。すべて $\beta\ge0$ なら解がある。
  4. 解を戻す:残った最後の変数から順に値を決める。各段で、すでに決めた値を代入すると、次の変数の範囲は区間 $[\max_jL_j,\min_iU_i]$ になる($L_j,U_i$ は thm-fm-step の証明のもの)。そこから好きな値を選ぶ。
3 変数の系を解く

次の系の解を 1 つ求める。
$$ x+y+z\le6,\quad x-y\le1,\quad -x+z\le2,\quad -y-z\le-3,\quad -z\le0 $$
答え:$(x,y,z)=(1,1,2)$ は解である。消去の結果、$x$ の範囲は $-2\le x\le3$ である。

途中の計算を開く

$z$ の上界は 2 本($z\le6-x-y$、$z\le2+x$)、下界も 2 本($z\ge3-y$、$z\ge0$)である。4 つの組から次の不等式を得て、$z$ を含まない $x-y\le1$ を残す。

$$x\le3,\quad x+y\le6,\quad -x-y\le-1,\quad -x\le2,\quad x-y\le1$$

次に $y$ を消す。上界は $y\le6-x$、下界は $y\ge x-1$ と $y\ge1-x$ である。組から $2x\le7$ と $0\le5$ を得る。$x$ の系は $-2\le x\le3$ で($2x\le7$ は $x\le3$ から従う)、ここで解があることが分かる。

解を戻す。$x=1$ とする。$y$ の範囲は $\max\{0,0\}\le y\le5$ なので $y=1$ とする。$z$ の範囲は $\max\{2,0\}\le z\le\min\{4,3\}$ なので $z=2$ とする。

主定理

消去と射影

$P=\{x\in\mathbb{R}^n\mid Ax\le b\}$ とする。$n\ge2$ のとき、$P$ の $x'$ への射影
$$ \pi(P):=\{x'\in\mathbb{R}^{n-1}\mid(x',x_n)\in P\text{ となる }x_n\in\mathbb{R}\text{ がある}\} $$
は、$x_n$ を消去した系の解の全体に等しい。とくに $\pi(P)$ は $\mathbb{R}^{n-1}$ の多面体である。$n=1$ のとき、$P\ne\emptyset$ であることと、$x_1$ を消去した系の不等式 $0\le\beta$ がすべて成り立つことは同値である。

$(x',x_n)\in P$ なら、$x'$ は消去した系を満たす。系の不等式は、$P$ の不等式に $0$ 以上の数を掛けて足し、$x_n$ の係数が $0$ になったものだからである。
逆に、$x'$ が消去した系を満たすとする。$i\in I_+$、$j\in I_-$ について
$$ U_i:=\frac{b_i-a_i'\cdot x'}{a_{in}},\qquad L_j:=\frac{b_j-a_j'\cdot x'}{a_{jn}} $$
とおく。$a_{in}>0$ なので $i$ 行は $x_n\le U_i$ と同値であり、$a_{jn}< 0$ なので $j$ 行は $x_n\ge L_j$ と同値である。組 $(i,j)$ の不等式を移項すると
$$ -a_{jn}(b_i-a_i'\cdot x')+a_{in}(b_j-a_j'\cdot x')\ge0 $$
であり、正の数 $-a_{jn}a_{in}$ で割ると $U_i-L_j\ge0$ になる。よって、すべての $i,j$ で $L_j\le U_i$ である。したがって $\max_jL_j\le\min_iU_i$ であり($I_-$ が空なら左辺を $-\infty$、$I_+$ が空なら右辺を $+\infty$ と読む)、この間に実数 $x_n$ をとれる。このとき $I_+$、$I_-$ の不等式が成り立つ。$I_0$ の不等式は $x_n$ によらず、(a) により成り立つ。よって $(x',x_n)\in P$ である。
$n=1$ のときも同じ議論で、$x'$ の項を除いて読めばよい。$\square$

$\max_jL_j\le\min_iU_i$ の間から $x_n$ を選ぶところで、$\mathbb{R}$ の順序だけを使っている。掛ける数と割る数はどれも係数から四則で作られる。したがって、係数がすべて有理数なら消去した系の係数も有理数で、$x'$ が有理数なら $L_j,U_i$ も有理数なので、$x_n$ も有理数にとれる。とくに、有理数係数の系に実数解があれば有理数解がある。同じ証明は任意の 順序体 で成り立つ。
thm-fm-step を繰り返すと、多面体の座標への射影は多面体である。多面体 の系「多面体の線形写像による像」は、これを線形写像の像に広げたものである。

線形計画問題を解く

線形計画法 の例「生産計画」の問題($x+y\le5$、$2x+y\le8$、$x+3y\le12$、$x,y\ge0$ のもとで $4x+3y$ を最大化)を、新しい変数 $z$ と不等式 $z-4x-3y\le0$ を加えて解く。$y$、$x$ の順に消すと、$z$ の範囲が残り、その上限が最適値である。
答え:最適値は $18$、最適解は $(x,y)=(3,2)$ である。

途中の計算を開く

$y$ を消すと、ほかの不等式から従うものを除いて $0\le x\le4$、$z-x\le15$、$z+2x\le24$、$z-3x\le12$ が残る。$x$ を消すと、$z-x\le15$ の $2$ 倍と $z+2x\le24$ の和から $3z\le54$、すなわち $z\le18$ を得る。$z$ の上界のうちこれが最小である。

解を戻す。$z=18$ とすると $x\ge3$、$x\le3$ なので $x=3$ である。$y\le2$、$y\le2$、$y\le3$ と $3y\ge z-4x=6$ から $y=2$ である。

使った結合をもとの不等式まで戻すと、$3z\le54$ は、$x+y\le5$ の $6$ 倍、$2x+y\le8$ の $3$ 倍、$z-4x-3y\le0$ の $3$ 倍の和である。$3$ で割ると、$3$ つの制約に掛ける乗数 $(2,1,0)$ が現れ、これは双対問題の最適解である(線形計画法 の例「生産計画の双対問題」)。

乗数の追跡と解がないことの証拠

消去の各段の不等式は、もとの不等式の $0$ 以上の結合である。その係数を記録しておくと、計算の結果に証拠が付く。以下、$E\subset\{1,\dots,n\}$ を消去する変数の添字の集合とする。

消去の乗数

$Ax\le b$ から $E$ の変数を順に消去した系の各不等式は、ある $y\in\mathbb{R}^m$、$y\ge0$ によって
$$ (A^{\mathsf T}y)\cdot x\le b\cdot y $$
と書ける。ここで $(A^{\mathsf T}y)_j=0$($j\in E$)である。

消去の回数についての帰納法で示す。消去 $0$ 回では、$i$ 行は $y=e_i$ の場合である。ある段の系の各不等式がこの形であるとし、次の変数 $x_l$ を消す。def-fm-step の (a) の不等式は同じ $y$ で書ける。(b) の不等式は、$y^{(1)},y^{(2)}$ に対応する 2 つの不等式の、正の数 $\alpha,\beta$ による和なので、$y:=\alpha y^{(1)}+\beta y^{(2)}\ge0$ で書ける。$x_l$ の係数は $0$ であり、すでに消した変数の係数も $0$ のままである。$\square$

消去から得られる択一定理

$A\in\mathbb{R}^{m\times n}$、$b\in\mathbb{R}^m$ とする。次の 2 つのうち、ちょうど一方が成り立つ。

  1. $Ax\le b$ を満たす $x\in\mathbb{R}^n$ がある。
  2. $y\ge0$、$A^{\mathsf T}y=0$、$b\cdot y< 0$ を満たす $y\in\mathbb{R}^m$ がある。
    $A,b$ の成分が有理数なら、$y$ も有理数にとれる。

両方が成り立つとすると、$y\ge0$ と $Ax\le b$ から $0=(A^{\mathsf T}y)\cdot x=y\cdot(Ax)\le b\cdot y< 0$ となり矛盾する。
1 が成り立たないとする。thm-fm-step を繰り返すと、もとの系に解があることと、$x_n,\dots,x_2$ を消した $x_1$ だけの系に解があることは同値である。後者に $n=1$ の場合を使うと、すべての変数を消した不等式 $0\le\beta$ のうち、$\beta< 0$ のものがある。prop-fm-multiplier により、この不等式は $y\ge0$ によって $(A^{\mathsf T}y)\cdot x\le b\cdot y$ と書け、$E$ はすべての変数なので $A^{\mathsf T}y=0$、$b\cdot y=\beta< 0$ である。これが 2 である。有理数の場合は、消去の計算の掛ける数がすべて有理数であることによる。$\square$

これは Farkasの補題 の系「不等式の形の Farkas の補題」と同じ主張である。その記事の主定理の証明は錐の最短点を使うのに対し、ここでは位相を使わず、消去の計算が $y$ を与える。線形計画法の双対定理はこの主張から導かれる(線形計画法 の定理「線形計画法の双対定理」)。

解のない系と証拠

$x+2y\le2$、$-x+y\le-1$、$-y\le-1$ を考える。$x$ を消すと、最初の 2 つの和 $3y\le1$ と、$-y\le-1$ が残る。$y$ を消すと、$3y\le1$ と $-y\le-1$ の $3$ 倍の和 $0\le-2$ を得る。よって解はない。
結合の係数を追うと $y=(1,1,3)$ である。実際 $A^{\mathsf T}y=(1-1,\ 2+1-3)=(0,0)$、$b\cdot y=2-1-3=-2< 0$ である。読者は消去の過程を見なくても、この $y$ を代入するだけで解がないことを確かめられる。

prop-fm-multiplier から、射影は乗数の錐で書ける。消去する変数の添字の集合 $E$ について
$$ C_E:=\{y\in\mathbb{R}^m\mid y\ge0,\ (A^{\mathsf T}y)_j=0\ (j\in E)\} $$
とおく。$y\in C_E$ なら、不等式 $(A^{\mathsf T}y)\cdot x\le b\cdot y$ は残った変数だけを含む。

射影の乗数による記述

$P=\{Ax\le b\}$ の、$E$ の座標を除く座標への射影は、すべての $y\in C_E$ についての不等式 $(A^{\mathsf T}y)\cdot x\le b\cdot y$ の解の全体に等しい。

射影の点は、$P$ の点から座標を除いたものなので、$P$ の不等式の $0$ 以上の結合をすべて満たす。逆に、すべての $y\in C_E$ の不等式を満たす点は、$E$ の変数を消去した系を満たす。prop-fm-multiplier により、その系の不等式はこの形だからである。thm-fm-step を繰り返すと、この点は射影に属する。$\square$

不等式の数の増え方

1 回の消去で不等式の数は $m$ から $\lvert I_0\rvert+\lvert I_+\rvert\lvert I_-\rvert$ になる。$m\ge4$ なら、これは $m^2/4$ 以下である。評価を繰り返すと、$k$ 回の消去のあとの本数の上界は $4(m/4)^{2^k}$ で、$k$ について 2 重指数である。実際に本数が増える例を見る。

正八面体を消去で作る

$n\ge2$ とする。$(x,t)\in\mathbb{R}^{2n}$ の $2n+1$ 本の不等式
$$ x_i-t_i\le0,\qquad-x_i-t_i\le0\quad(i=1,\dots,n),\qquad t_1+\dots+t_n\le1 $$
の解の全体を $t$ を除く座標へ射影すると、多面体 の例の正八面体 $O_n=\{x\mid\sum_i\lvert x_i\rvert\le1\}$ になる。実際、不等式は $\lvert x_i\rvert\le t_i$ と $\sum_it_i\le1$ であり、$x\in O_n$ なら $t_i:=\lvert x_i\rvert$ とすればよい。
$t_1,\dots,t_n$ を順に消す。$k$ 回の消去のあとの系は
$$ \sum_{i\le k}\varepsilon_ix_i+\sum_{i>k}t_i\le1\quad(\varepsilon\in\{\pm1\}^k),\qquad\pm x_i-t_i\le0\quad(i>k) $$
で、本数は $2^k+2(n-k)$ である。実際、$t_{k+1}$ の下界は $\pm x_{k+1}$ の 2 本、上界は第 1 の型の $2^k$ 本である。消去が終わると $2^n$ 本の不等式 $\varepsilon\cdot x\le1$ が残る。
この $2^n$ 本はどれも除けない。$x=\varepsilon/(n-1)$ で $\varepsilon\cdot x=n/(n-1)>1$ であり、$\varepsilon'\ne\varepsilon$ なら $\varepsilon'\cdot x\le(n-2)/(n-1)< 1$ なので、この点は $\varepsilon$ の不等式だけを満たさない。さらに、$O_n$ を表すどの不等式系も $2^n$ 本以上の不等式を含む。各 $\varepsilon$ について、点 $\varepsilon/(n-1)$ が満たさない不等式を 1 本選ぶ。異なる $\varepsilon,\varepsilon'$ で同じ不等式が選ばれたとすると、2 点の中点もこの不等式を満たさない。しかし中点は成分のうち $\varepsilon_i=\varepsilon_i'$ の高々 $n-1$ 個だけが絶対値 $1/(n-1)$ で、残りは $0$ なので、$O_n$ に属する。これは矛盾である。

$2n+1$ 本から $2^n$ 本になるのは、計算が下手なのではなく、射影という操作そのものの性質である。同じ多面体でも、書き方によって大きさは大きく違う(立方体の 2 通りの記述について BV04 §2.2.4、p. 34)。
一方、2 重指数の上界は、射影を書くのに必要な本数を表しているわけではない。次の定理により、必要な不等式は少数のもとの不等式の結合で足りる。

台の小さい乗数で足りる

$\lvert E\rvert=k$ とする。$C_E$ の元は、$C_E$ の元で 0 でない成分が $k+1$ 個以下のものの、$0$ 以上の係数の和で書ける。したがって $P=\{Ax\le b\}$ の射影は、prop-fm-projection の不等式のうち、$y$ の 0 でない成分が $k+1$ 個以下のものだけで定まる。さらに、そのような $y$ は定数倍を除いて高々 $\sum_{i=1}^{k+1}\binom mi$ 個に限ってよい。

台を 1 つずつ小さくする

$y\in C_E$、$y\ne0$ とし、$T:=\{i\mid y_i\ne0\}$ を $y$ の台とする。$T$ に台が含まれ、$(A^{\mathsf T}z)_j=0$($j\in E$)を満たす $z\in\mathbb{R}^m$ の全体を $N_T$ とする。$N_T$ は、$k$ 本の 1 次方程式で定まる $\mathbb{R}^T$ の部分空間なので、$\dim N_T\ge\lvert T\rvert-k$ である。
$\dim N_T=1$ なら $\lvert T\rvert\le k+1$ であり、$N_T$ は $y$ の定数倍の全体である。この場合を 極小 とよぶ。極小な $y$ は、台 $T$ を決めると定数倍を除いて決まるので、定数倍を除いて高々 $\sum_{i=1}^{k+1}\binom mi$ 個である。
$\dim N_T\ge2$ とする。$\lvert T\rvert$ についての帰納法で、$y$ が台のより小さい $C_E$ の元の $0$ 以上の係数の和であることを示す。$y$ の定数倍でない $z\in N_T$ と $i_0\in T$ をとり、$w:=z-(z_{i_0}/y_{i_0})y$ とおく。$w\in N_T$、$w\ne0$、$w_{i_0}=0$ である。$-w$ に替えてもよいので、$w$ は正の成分をもつとする。$\alpha:=\min\{y_i/w_i\mid w_i>0\}>0$ とおくと、$y':=y-\alpha w\ge0$ で、$y'\in C_E$ の台は $T$ より真に小さい($y'_{i_0}=y_{i_0}>0$ なので $y'\ne0$)。
$w\ge0$ なら、$y=y'+\alpha w$ で、$w\in C_E$ の台も $T$ より真に小さい。$w$ が負の成分ももつなら、$\beta:=\min\{y_i/(-w_i)\mid w_i< 0\}>0$ とおくと $y'':=y+\beta w\ge0$ で、同様に $y''\in C_E$ の台は真に小さく、
$$ y=\frac{\beta}{\alpha+\beta}y'+\frac{\alpha}{\alpha+\beta}y'' $$
である。どちらの場合も、$y$ は台のより小さい元の和である。帰納法により、$y$ は極小な元の $0$ 以上の係数の和である。
最後に、$y=\sum_l\lambda_ly^{(l)}$($\lambda_l\ge0$)なら、$y$ の不等式は $y^{(l)}$ の不等式の $\lambda_l$ 倍の和なので、$y^{(l)}$ の不等式から従う。$\square$

ex-fm-octahedron の $\varepsilon\cdot x\le1$ は、$n$ 回の消去のあとの不等式で、もとの不等式を $n+1$ 本使う。定理の上界 $k+1$ はこの例で達成される。変数の数を固定すれば、$\sum_{i=1}^{k+1}\binom mi$ は $m$ の多項式である。
次の表は、$14$ 本の不等式で変数が $5$ 個の系(係数を $-3$ から $3$ の整数からランダムに選び、右辺を $1$ から $5$ の整数からランダムに選んだもの)から、変数を 3 回消去した計算の例である。各段で余分な不等式を線形計画で除くと、本数はほとんど増えず、残った不等式の乗数の 0 でない成分の個数は $k+1$ 以下である。

消去の回数 $k$0123
そのまま消去した本数142238323
各段で余分な不等式を除いた本数14181612
除いたあとの乗数の 0 でない成分の最大個数1234

狭義の不等式

狭義の不等式の消去

各行が $a_i\cdot x\le b_i$ または $a_i\cdot x< b_i$ である系を考える。def-fm-step と同じ結合を作り、(b) の不等式は、$i$ 行と $j$ 行の少なくとも一方が狭義なら狭義、どちらも非狭義なら非狭義とする。(a) の不等式はもとのままとする。このとき、解の全体の $x'$ への射影は、こうして作った系の解の全体に等しく、$n=1$ の解の有無の判定も thm-fm-step と同じである。ただし射影は閉集合とは限らない。

解の射影が新しい系を満たすことは、不等式の足し算による。逆に、thm-fm-step の証明と同じ $U_i,L_j$ について、$i$ 行は $x_n\le U_i$ または $x_n< U_i$、$j$ 行は $x_n\ge L_j$ または $x_n>L_j$ である。新しい系は、すべての組について $L_j\le U_i$ であり、一方が狭義なら $L_j< U_i$ であることを意味する。$\max_jL_j< \min_iU_i$ なら、その間の点が解である。$\max_jL_j=\min_iU_i$ なら、最大と最小を与える行はどれも狭義でないので、その値が解である($I_+$ または $I_-$ が空のときも同様である)。$\square$

この命題により、$\exists x_n$ のついた 1 次不等式の連言は、$x_n$ を含まない 1 次不等式の連言に直せる。量化子消去 の言葉では、実数の 1 次不等式の論理式では量化子を消せる。否定は $a\cdot x\le b$ を $a\cdot x>b$ に替えて消せ、論理式を連言の選言に直せば $\exists$ は選言に分配できるからである。

使える条件と反例

外す条件反例成り立たなくなること
解が実数(順序体の元)$x$ を整数に限った $1\le2x\le1$消去した不等式 $1\le1$ は成り立つが、解はない
不等式が 1 次$\{(x,y)\mid x\ge0,\ xy\ge1\}$射影 $\{y>0\}$ は閉集合でなく、多面体でない
不等式が有限個$\{(x,y)\mid x\ge0,\ y+x/s^2\ge2/s\ (s>0)\}$射影 $\{y>0\}$ は閉集合でなく、多面体でない
掛ける数が $0$ 以上$x\le1$ と $x\le2$ から $2\cdot(x\le1)-(x\le2)$$x\le0$ が出るが、$x=1$ は解である
狭義の不等式を狭義のまま結合する$x< 0$ と $-x< 0$ を非狭義で結合$0\le0$ が出るが、解はない
表の反例の確かめ

どの行も、その行の条件だけを外している。
実数:$2x\le1$ と $-2x\le-1$ の解は $x=\tfrac12$ だけである。実数では thm-fm-step のとおり解があるが、整数の解はない。$x_n$ を区間から選ぶところで、区間が整数を含むとは限らないのが原因である。
1 次:$x\ge0$、$xy\ge1$ なら $x>0$ で $y\ge1/x>0$ であり、逆に $y>0$ なら $x=1/y$ が解である。不等式は 2 本で有限で、どちらも狭義でない。多面体は閉集合なので、$\{y>0\}$ は多面体でない。
有限個:$x>0$ のとき、$s>0$ についての $2/s-x/s^2$ の最大値は $s=x$ での $1/x$ である。$x=0$ では $2/s$ に上界がない。よってこの集合は、表の 2 行目の集合 $\{x\ge0,\ xy\ge1\}$ と同じである。各不等式は 1 次で、無限個あるだけである。
掛ける数:負の数を掛けると不等号の向きが変わるので、結合は正しい不等式を与えない。
狭義:$x< 0$ と $-x< 0$ を $x\le0$ と $-x\le0$ として結合すると $0\le0$ になり、解 $x=0$ があるように見える。もとの系には解がない。prop-fm-strict のとおりに結合すると $0< 0$ となり、解がないと分かる。

よくある誤り

誤り正しくはなぜ
上界どうし・下界どうしも結合する$I_+$ と $I_-$ の組だけを結合する同じ符号の結合では $x_n$ が消えない
$I_0$ の不等式を捨てるそのまま残す$x_n$ を含まない不等式も射影を制限する(導入の $-y\le-1$)
$I_+$ が空なら解がないとする$I_-$ の不等式を捨てて続ける上界がなければ $x_n$ はいくらでも大きくとれる
消去した系の解だけで答えとする逆の順に代入して消した変数の値を決める消去した系は射影しか表さない
整数計画に使う使えない。緩和の評価にとどまる上の表の 1 行目
不等式の数は多項式で済むと思う射影の不等式そのものが指数本必要なことがあるex-fm-octahedron

補足

Gaussの消去法との比較。

Gaussの消去法この記事の消去
対象連立 1 次方程式連立 1 次不等式
1 回の操作1 本の式で他の式から変数を消す上界と下界の組ごとに結合する
掛ける数任意の数正の数
本数増えない$\lvert I_0\rvert+\lvert I_+\rvert\lvert I_-\rvert$ に変わる
解がない証拠$0=1$ を作る結合$0\le-1$ を作る $0$ 以上の結合(thm-fm-certificate)

線形計画との関係。 ex-fm-lp のように消去で線形計画問題は解けるが、変数が多い問題には向かない。実際の計算には 線形計画法 の節「単体法の仕組み」の方法などを使う。消去の価値は主に理論にあり、多面体の射影が多面体であることや、thm-fm-certificate を、位相を使わずに示せる。
多面体の 2 つの表し方。 多面体 の定理「有限個の点の凸包は多面体」は、凸結合の係数の変数をこの消去で消して示されている。

関連項目

参考文献

[1]

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する