整数計画法で「≠」は表現不可能なのか?

注: この話の文脈が分かってる人は「分かってる事」の節まで飛ばすのが吉。
x,y が次の条件を全て満たすとき、\(143x + 60y\) の最大値を求めよ:
\[
120x + 210y \le 15000\\
110x + 30y \le 4000\\
x + y \le 75\\
x \ge 0\\
y \ge 0
\]↑こんな風に、線形不等式を満たすよう線形式 (ここでは143x + 60y) の最大値や最小値を求める問題を線形計画問題 (linear program, LP) といい、特に変数が全て整数値を取るという条件で解く物を整数計画問題 (integer linear program, ILP) と言う。ILP は NP 完全問題であり、他の NP 完全問題と同じく

• もの凄く沢山の「制約を満たすアレコレを見つけよ」式の問題が ILP に帰着できる
• 一般に速く解く方法は知られていない、多分存在しない
• でも経験的に、実際に起きるケースでは大抵速く解けるソルバが充実してる

という特徴がある。特に ILP 自身が足し算を含むので、足し算を含む問題は ILP に帰着させやすい (カックロとか、何かのコストの合計を最小化する問題とか)。

ここ数日、この ILP で「否等式」とでも呼べばいいのか、$x \neq y$ という形の制約を一般に扱うことが出来るかどうか考えてたんだけど、手詰まりになったので、分かってること、分かってないこと、考えたことを一旦ここにまとめました。何かわかる方はコメントお願いします。

問題

ILP では、制約式は全て
\[
a_1x_1 + a_2x_2 + \cdots + a_n x_n \le c
\]
の形の non-strict な線形不等式 (ここで $a_i$ と $c$ は (整数) 定数で $x_i$ は変数) に制限されてるので、何か問題を ILP に帰着させる時は「不等式ではない制約を如何にして不等式で表現するか」に腐心することになる。

例えば $x = y$ と書きたければ $x \le y, y \le x$ と二つの式に分割する。$x < y$ は $x \le y - 1$ に置き換え、「$x_1,x_2,\ldots,x_n$ の内ただひとつが 1 に等しく、残りは全部 0」というような排他条件は $0 \le x_i \le 1$ という条件に加えて $x_1 + x_2 + \cdots + x_n = 1$ (この = は更に二つの不等号にバラす) で表す。

このように線形不等式は結構色んな制約を表現することが出来るんだけど、このノリで否等式 $x \neq y$ を不等式に翻訳しようとすると途端に詰まるのだ。話を簡単にするため変数の値を一つ 0 で固定して $x \neq 0$ を表現することを考えてみよう。この式を満たす整数の集合は $\mathbb{Z}-\{0\}$。これは穴が空いた(一次元の)図形なので、明らかに線形不等式の集まりで定義できる集合ではない。

一般に、n 個の変数についての連立線形不等式を満たす点の集合は、$\mathbb{R}^n$ 上で解いた場合は凸多胞体 (注: 多角形とか多面体みたいに真っ直ぐな面で区切られた図形の n 次元版) を成す。ILP では $\mathbb{Z}^n$ 上で解くので、凸多胞体に含まれる格子点全ての集合が不等式の解の集合になる。ただし、普通多胞体と言えば有限の大きさを持った閉じた図形を指すけど、ここで言う多胞体は無限に大きい物も含む。例えば $\mathbb{R}^2$ で $0 \le x \le 1, 0 \le y$ を満たす $(x,y)$ の集合は普通多角形とは言わないけど、ここでは直線で囲まれてるので多角形に含める。

しかしながら $\mathbb{Z}-\{0\}$ というのは -1,1 を含むのにその内分点の 0 を含まないので、明らかに連立線形不等式の解ではない。要するに否等式は非線形の制約なので、線形の制約に変換するのが難しいのだ。

これが、単に「難しいから、自分が思いつかないだけ」なのか、「そもそも不可能」なのかというのがこの記事で問いたい問題。形式化するならこんな感じ。

問: $x$ を含むいくつかの変数について整数係数の連立線形不等式があり、その連立不等式の整数解から $x$ の値だけを抜き出した集合が $\mathbb{Z}-\{0\}$ である。このような連立線形不等式は存在するか。

分かってる事: 凸性だけではダメ

さて、無論「$\mathbb{Z}\setminus\{0\}$ は凸ではないので線形不等式では表せない、ハイ終わり」で済むのかと言えばそうは問屋が卸さない。卸してくれるならこんな記事書かない。なぜなら例えば $x \neq 0$ は表せなくても $x \neq 0 \land -2 \le x \le 2$ なら表せるから。この制約の解は $[-2..2]-\{0\}$ と、穴の空いた集合になるけど、補助変数 $y$ を使えば
\[ y \le \frac{1}{3}x + \frac{2}{3} \\
    y \ge\frac{1}{3}x  + \frac{1}{3} \\
    0 \le y \le 1 \]
という制約で表せる。この連立不等式の整数解は $(-2,0), (-1,0), (2,1), (1,1)$ の四点で、$x$ はちゃんと $[-2..2]-\{0\}$をカバーする。

幾何的に考えると、n 個の変数の制約式を k 個の補助変数を使って表すという事はつまり

• n+k 次元の多胞体を選んで
• それを n 次元に射影する

事に相当するけど、今しがた見たように $\mathbb{Z}^{n+k}$ から $\mathbb{Z}^n$ への射影では ($\mathbb{R}^{n+k}$ から $\mathbb{R}^n$ への射影とは違って) 凸図形が凸でない図形の影を持つことがある。だから $\mathbb{Z}-\{0\}$ が凸図形でないというのは一変数の線形不等式で表せない理由であって、補助変数を使っても表せない理由にはならない。

分かってる事: 補助変数一つでは足りない

補助変数を一つしか使わずに $x \neq 0$ を表すことは不可能である事は割と簡単に証明できる。泥臭いけど。仮に $x,y$ という二つの変数を使った連立線形不等式が $x \neq 0$ を表せたとする、つまり連立不等式の解の集合を $S ⊆ \mathbb{Z}^2$ とすると、$S$ を $x$ 軸上に射影した時の影 $\operatorname{proj}_x(S)$ が $\mathbb{Z}-\{0\}$ だと仮定する。

その連立不等式を実数の範囲で解いた時の解の集合を $S' ⊆ \mathbb{R}^2$ とすると、$S'$ は(非有界)凸多角形で $S'$ の中の格子点の集合が $S$ と一致する。$S$ は y 軸の左にも右にも点を持つので、$S'$ もそうでなくてはならない。しかも $S'$ は凸図形なので y 軸と交わる。ここで \[
l = \inf \{ y | (x,y) \in S' \cap (\mbox{$y$ 軸}) \} \\
u = \sup \{ y | (x,y) \in S' \cap (\mbox{$y$ 軸}) \}
\] とすると、$l,u \not\in \mathbb{Z}$ でかつ $\lfloor u \rfloor = \lfloor l \rfloor$ である。さもなくば $(0,l)$ と $(0,u)$ の間に格子点が含まれ、これを $S'$ が凸性より含んでしまうからである。

よって $l,u$ は有限である。$(0,l)$ と $(0,u)$ は $S'$ の境界に含まれるので、それぞれどれかの不等式を最適化する点でなくてはならない。つまり連立不等式の中に、変数を左辺、定数を右辺に集めると \[
 a_l x + b_l y \le c_l \\
 a_u x + b_u y \le c_u
\] となる二つの不等式が含まれていて、これらの $\le$ を = に置き換えて得られる式の表す直線 $L_l, L_u$ がそれぞれ $(0,l)$ と $(0,u)$ を含む。

さて、もし$L_l,L_u$ が平行であるとすると、これらは共通して有理数の傾き $-a_l/b_l$ を持つ。従ってこれらの直線と $x = b_l$ との交点の y 座標は $l - a_l$ と $u - a_l$ であり、これらの座標はいずれも整数ではなく floor が同じである。よって $(b_l, l - a_l)$ と $(b_l, u - a_l)$ の間には格子点が含まれず、$b_l \not\in \operatorname{proj}_x(S)$ となり $\operatorname{proj}_x (S) = \mathbb{Z}-\{0\}$ と矛盾する。一方、$L_l,L_u$ は平行でないならどこかで交わる。ここでは y 軸の右で交わったとしよう。$S'$ はその交点より右には一つも点を持たないので、 $S$ も交点より大きな x 座標の点を持たないという事になる。これは $\operatorname{proj}_x (S) = \mathbb{Z}-\{0\}$ と矛盾する。

補助変数二つにすると頭が爆発する

で、まあ当然ここまでの証明を三次元以上に拡張できないかと考えたわけですよ。ところが三次元の時点でどうもうまく行かない。まず $z = z_0 (\in \mathbb{Z})$ という形の任意の平面について、二次元の場合と同じ論証で $+x$ 方向か $-x$ 方向に一定距離以上行けば一定間隔で $S'$ と格子点を共有しない y 軸方向の直線がある事が示せる。だから $z=z_0$ 平面が $\operatorname{proj}_x(S)$ に貢献する部分集合は右か左かが一定距離以降一定間隔で歯抜けになっている。

歯抜けが始まる距離は上で言う $L_l,L_u$ の式の左辺の係数だけを含む式で上から抑えられ ($|u-l| < 1$ を使う。詳細は略)、歯抜けの間隔は y の係数の絶対値なので、いずれの数値も高々 $O((\mbox{不等式の個数})^2)$ 程度しかバリエーションが無い。従って全部の公倍数とかを取ってしまえばどの $z=z_0$ 平面でも歯抜けが始まる距離と、どの平面でも歯抜けが最低一回は起きる間隔が計算できるだろう…と思った。

が。よく考えたら $z = z_0$ では $+x$ 方向でだけ歯抜けが起きるけど $z = z_0 + 1$ では $-x$ 方向でだけ歯抜けが起きるという可能性が残っている。もしそうならこの2つの平面のカバーする $\operatorname{proj}_x(S)$ を合わせると $\operatorname{proj}_x(S)$ が全部カバーできてしまうかも知れない。

多分、そういうことが起きないという事を $S'$ の凸性を使って示すんだと思うんだけど、どうしたらそんな事が示せるのか分からない。手詰まり。←今ここ

ググった結果

ILP で否等式を扱う方法を調べようと "integer linear programming disequality" とか "GLPK 'not equal' " とかでググると次のような情報が見つかる:

予め $|x| < u$ となるような定数の上限 $u$ が分かっているならば、$x \neq 0$ は 補助変数 $b,s_1,s_2$ を用いて次のように表せる:\[ s_1 + s_2 \ge 1 \\  0 \le b \le 1 \\ 0 \le s_1 \le u b \\ 0 \le s_2 \le u (1-b) \]

出典1 Re: [Help-glpk] [GLPK] not-equal constraints
出典2 How to specify an unequal constraint with an Integer Linear Programming (ILP) solver 

理路が若干違うけど、まあ「補助変数一つでは足りない」のとこで書いた方法と大体一緒。上限がわからない場合は使えない。

CPLEX ソルバでは indicator constraint という拡張機能を使えばこんな風に表現できるよ! \[0 \le b \le 1 \\ b = 0 \rightarrow x < 0 \\ b = 1 \rightarrow x > 0 \] (訳注: ($\rightarrow$) は "ならば" を表す CPLEX の拡張語彙。)

出典 Question : how to express the constrain "not equal to" effciently

ILP の範囲逸脱してんじゃねーか!
いやまあ、実用上は非常にありがたい機能で、どれぐらいソルバのパフォーマンスへの影響を抑えられるか興味あるんだけども、

• 主に私が使ってる GLPK にはそんな機能は無い
• 「可能なのか?」という数学的な興味に対する答えにはなってない

ので今一つ不服。

というわけで、$x$ の上限が分からない場合 $x \neq 0$ を表す方法は載ってないみたい。なので否等式を表す方法は存在しないか、知られてないかのどっちかだと思うのだけど、どっちなのかは不明。

まとめ

整数計画法で否等式 $x \neq y$ を線形不等式に直すことは可能か知りたい。これはまだ解決してない。ただし $|x - y|$ の上限が分かってるなら線形不等式にすることは出来る。

上限がわかっていない場合、補助変数一つを使った不等式で表すことは不可能。三次元以上でも不可能かどうかは今のところ不明。