『しっかり学ぶ数理最適化』の定式化の話。

昨日、『しっかり学ぶ数理最適化』の勉強会に参加してきたことを書いた。

しっかり学ぶ数理最適化　モデルからアルゴリズムまで (ＫＳ情報科学専門書)

作者:梅谷俊治
講談社

Amazon

この中で定式化についていくつか気になったところがあったことも書いた。今日はそれについて詳しく書いてみたい。

これは数理最適化 Advent Calendar 2025の3日目の記事です。

生産計画問題

まずは線形計画問題の定式化の一例として挙げられていた生産計画問題に関して。

これは複数期間に渡る生産を考えて、生産量と在庫量をどうするか決める問題なんだけど、フローのように考えて各期間をノードとして表現し、入ってくる量（＝生産量と前期の在庫量）と出ていく量（＝次期への在庫量と需要量）が一致するという制約があるよねという話をしている。これ自体は納得いくんだけど、一緒に載っていた図2.3についていろいろ議論があった。

この図を見ると最後の期間 $T$ について次期への在庫 $s_{jT}$ の矢印が出てるけど、これって必要なの？ということ。

最適化した結果として、在庫を残すことに意味はないのでこの値は結局0になるんだけど、それならこの矢印は不要なのでは？というのが出た意見。これはもっともな意見で、反論するならそれは最適化の結果として分かることだから、とりあえず矢印を書いてるとか、他との様子を揃えるために矢印を書いてるとなりそう。ただ、それであるなら $s_{j0}$ の矢印が1期のノードに入ってくる方が自然で、ここも制約によって結局は0にはなるんだけど、0になるから書かないというのであれば、最後の $s_{jT}$ も同じように書いてない方が統一性が出てくる。さらに致命的なのが一番上にあるノードに入ってきてる $\sum_{t=1}^T d_{jt}$ という量で、これはつまりフローとして流れている総量が保存されてるよということを言いたかったんだろうと思うけど、情報としては冗長だし（各ノードから出てる $d_{jt}$ がまとめられてないのだから、各ノードに入ってくる $x_{jt}$ も別にまとまってる必要はない）、この図で出ていく量に注目するならここは $\sum_{t=1}^T d_{jt} + s_{jT}$ でなければならないので、整合性が取れてない。

おそらく、この図で書くなら $s_{jT}$ はない方がスッキリしそう。それか、一番上のノードをなくしてしまって、一番左には $s_{j0}$ が入ってくる矢印、一番右には $s_{jT}$ が出ていく矢印を書くと、数式を一番適切に表現できて、図としてもキレイな感じがする。

凸な非線形関数の近似

これも線形計画問題の定式化の話で、凸な非線形関数の最小化問題を線形計画問題で近似的に表現して解こうというもの。いくつかの点をサンプリングして隣接する2点を通る直線を使えば近似できるよね、というもので、多くの人は納得してた。

けど、どうして線形計画問題として考える必要があるのか分からないという人がいて、議論してみるとたしかにそうだねとなった。

というのも、サンプリングした点を線分で結んでいくので、近似した区分線形関数の最小値はサンプリングした点よりも下がることがないから。サンプリングした点の中で関数値が最小値になっているものが、線形計画問題として解くまでもなく最小と分かる。

実際にはこの凸な区分線形関数を単に最小化するわけではなく、制約として現れてきたり、他の制約によって領域が限定されたりするので、線形計画問題の制約として表現すること自体は意味がないわけではないんだけど、この例のように単純化しすぎてしまってると、たしかに線形計画問題として考える必要がそもそもなくなってしまうというのはちょっと盲点だった。

公平な予算分配の問題

絶対値やmin/maxを含む式を線形計画問題として定式化する例の一つとして、予算を公平に分配する問題が紹介されてた：

ただこれ、 $a_{ij}$ や $b_i$ が何を意味しているのかの説明が完全に漏れてる（＾＾；いまだに修正されてないので、みんなこういったところは流し読みしてるんだろうなぁ・・・（自分も一人で読んでたら絶対気にしてなかったと思う）

この $a_{ij}$ や $b_i$ が何を意味するのか、どこかに記述があるんじゃないかとみんなで探し回ったけど、見つからず。まぁ、意味合いは解釈できたので、自分の方からみんなに説明しておいた。

ここでは $n$ 個の事業があり、それぞれへの配分額を $x_j$ 、そして予算の合計を $B$ としてるんだけど、 $i$ が何を意味するのか、そして $a_{ij}$ と $b_i$ が何を意味するのかが説明されてない。

おそらく、事業をやることで達成すべき指標（たとえば売上とか、顧客満足度とか、環境への貢献とか）が $m$ 個あり、それぞれの達成目標が $b_i$ として与えられていて、各事業に予算 $x_j$ を与えることでそれぞれの指標が $a_{ij}x_j$ 伸びるので、その合計で目標を達成できるようにしよう、という感じ。その中で、予算が一番小さいものを最大化することで、指標を達成する配分の中で、最も公平な配分を得ようとしている、という感じなのかなぁと。

最短経路問題の完全単模性

これは直近の勉強会でやったところで、最短経路問題は完全単模行列になってるから、線形計画問題に緩和して単体法で解けばいいよ、という話。その直前には（有向グラフの）隣接行列は完全単模になることが紹介されていて、なるほど、これは最短経路問題の行列は隣接行列になってるということなのね、というのが自然な理解。

けど、ここで実際に示された式はこれ：

ここでみんな、「ん？これって隣接行列になってるの？」と止まることになった。

これも少し考えて解決したからみんなに説明したけど、本で説明があるともっとよかったなぁという気はする。まぁ、なるほどねと分かった嬉しさもあったけど。

これは2つ目の制約の符号が逆になってた方が分かりやすくて、 $-\sum_{e \in \delta^{-}(t)} x_e = -1$ となっていた方がよさそう。そうすると、1つ目の制約は $(\overbrace{1 \cdots 1}^{\delta^{+}(s)}\, 0 \cdots 0) \boldsymbol{x} = 1$ 、2つ目の制約は $(0 \cdots 0 \, \overbrace{-1 \cdots -1}^{\delta^{-}(t)}) \boldsymbol{x} = -1$ 、それ以外の制約は $(0 \cdots 0\, \overbrace{1 \cdots 1}^{\delta^{+}(v)}\, 0 \cdots 0\, \overbrace{-1 \cdots -1}^{\delta^{-}(v)}\, 0 \cdots 0) \boldsymbol{x} = 0$ と書けるので、この行ベクトルを積み重ねて作った行列で今度は逆に一つの有向辺 $e$ に注目してその列を見ると、その始点にあたる頂点での係数は1、終点にあたる頂点での係数は-1になるので、たしかに隣接行列になってる。