Model Building in Mathematical Programming: 9.2

Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。

9.2 Logical conditions and 0–1 variables

9.1 で、 0-1変数を使って 'if - then' を表せることがわかった。本章では、それを組み合わせてより複雑な論理式を記述できることが示されている。具体的には、まず各条件に対応する indicator variable をつくっておき、それらの間に制約を入れる。具体的には以下の様になる。

論理式	indicator variables による表現
$X _ 1 \vee X _ 2$	$\delta _ 1 + \delta _ 2 \geq 1$
$X _ 1 \cdot X _ 2$	$\delta _ 1 = 1,\ \delta _ 2 = 1$
$\sim X _ 1$	$\delta _ 1 = 0$
$X _ 1 \to X _ 2$	$\delta _ 1 - \delta _ 2 \leq 0$
$X _ 1 \leftrightarrow X _ 2$	$\delta _ 1 - \delta _ 2 = 0$

ここで、それぞれの記号の意味は、

記号	意味
$\vee$	or (A or B or both)
$\cdot$	and
$\sim$	not
$\to$	implies (if ... then)
$\leftrightarrow$	if and only if

こういうのはパズルっぽいので好きなんだけど、プログラムで自動化できそうな気がするし、条件式を記述しているだけだよと solver に伝えてあげたほうが、解きやすそう（計算量を落とせそう）な気がなんとなくする。他人が indicator variable を使って記述した複雑な論理式を読み解くなんて絶対にやりたくない。論理式をそのまま取り扱ってくれる solver ってあるんだろうか。気になる。

宿題: 12.12 Logical design

NORゲート（NOR は NOT OR ですね）を用いて論理回路を設計する問題。入力と出力が与えられて、それを満たす回路を出力する。まさに論理式を記述してみよう、という問題。パズルみたいで面白かった。本当に頭の体操という感じ。

colab.research.google.com