線形計画法と整数計画法

本来はカーマーカーの話を予定していたが、「誰得？」ということで、整数計画法の話に変更したというエウレカのkaneshin氏。

「最適化問題を認知してもらうきっかけになると嬉しい」と語り発表をスタートさせた。実は大学時代最適化問題の非線形計画法を専攻していたというが、「今日は久しぶりの数学」なのだそうだ。

kaneshin氏が担当している「pairs」は、マッチングアルゴリズムが重要になるという。豊富なユーザーのデータを活用するため、エンジニアがビジネス面からアルゴリズムを考える必要になる。そこで同社ではR勉強会や統計学の社内勉強会を開催している。

まずはオペレーションズ・リサーチ（OR）について。会場の参加者で知っていると答えた人は1割程度。ORは、相当広い分野を指すが、さまざまな計画に対して最も効率的になるよう意志決定するである。そのために活用するのが数学・統計的モデル、アルゴリズムである。

「シミュレーションの確立はORが立役者だ」とkaneshin氏。ORでは現実の問題を数理モデルに置き換えるため、最適化や待ち行列、確率などが用いられる。また、軍事的関心と経済的関心が強い分野でもある。

ORの事例としてkaneshin氏が紹介したのが経路検索。例えば「Yahoo路線」の裏側では、経路効率やコスト効率の考慮がされている。また、家から駅までに要する時間を計算して、駅であまり電車を待つことのないように出発を計画したりする。

山手線などの過密ダイヤが組めるのは、シミュレーションを何万回も繰り返した結果だが、実はこれも「ORの一種」。つまり、ORは身近なものというわけだ。

最適化問題はORの一要素である。

最適化問題とは数理計画問題とも呼ばれ、与えられた条件の下で何らかの関数を最小化・最大化する問題である。

制約条件の下で目的関数の最適解を実行可能領域から探す。これが最適化問題の定義である。「目的関数と制約条件が重要で、目的関数と制約条件によって最適化問題は分類される」とkaneshin氏は語る。

最適化問題の分類は以下の通りである。

• 線形計画問題：目的関数と制約条件の集合が一次式（線形）だった場合
• 非線形計画問題：目的関数と制約条件の間に非線形の式が存在する場合
• 整数計画問題：制約条件の一部またはすべての変数が整数の場合。一部の場合は混合整数、すべての場合は純整数計画問題という。
• 2次計画問題：目的関数が2次式、制御条件の集合が1次式の場合

これを図で表すと次のようになる。

「今回は整数計画問題と非線形計画問題の具体例を話す」とkaneshin氏は語り、説明を続けた。

線形計画問題とは目的関数と制約条件の集合が1次式のみというものである。例としては生産計画問題が有名だ、とkaneshin氏。3種類の原料を用いてある2つのプロダクト（P1、P2）を生産している会社を例に取り説明。

原料（M1,M2、M3）にはそれぞれ次のような利用可能量がある（制約条件）。

M1≦27t、M2≦45t、M3≦15t

• P1の生産には、M1を2t、M2を8t、M3を3t必要。利潤は2万円。
• P2の生産には、M1を6t、M2を6t、M3を1t必要。利潤は5万円。

利潤を最大化できる生産計画を立ててほしい、というのだ。これをマトリクスで表すと次のようになる。

P1とP2の生産量を変量とすると次の式が立つ。

2ｘ_１＋5x_2

これを最大化する。

制約条件を考えると次のような式になる。

これを線形計画問題として定式化する。この式が表す集合の中で最大化するのが線形計画問題となる。

これで最適解を求めていくのだが、ここで考えるのは「製品は連続値か」ということ。例えばおもちゃを作るということは整数値で非連続である。このときは整数計画問題で考えることになる。整数計画問題とは制約条件の一部またはすべてが変数のとる値が整数であるときの解法だ。

先の例に当てはめると、P1とP2は個数：これは整数という条件となる。x1、x2は整数という条件が加わる。グラフとして表すと次の通り。

白線（関数）は3本。制約条件を表す集合が薄い白の部分である（関数の直線に囲まれた部分）。

赤線は目的関数の等高線である。二変数の場合は等高線を下ろしてくると答えが出るが、n変数になると非常に大変になる。線形計画問題は二変数では収まらない。

例えば某航空会社のクルーのスケジューリングを線形計画問題で行おうとすると、1700万変数もの次元があったという。これはもう人では対応できない。

先のように2次元だと一通りしかないので、端点をたどっていき、目的関数が大きくなっているかをチェックして最終的に最適解となるところに矢印を移動していけば最適解が求められる。

「これはシンプルな考えでシンプレックス法（単体法）とも呼ばれる。1940年代後半ぐらいに提案されて、実用的に使われている優れた線形計画法の解法だ」

一方の整数計画問題の場合、領域は点（ドット）で表されているところが実行可能解である。線形計画問題の最適解と近いところが最適解になるのでは思いがちだが、実際の最適解は線形計画問題の最適解とは離れたところにあるという。

しかも、整数計画問題については解き方もいろいろある。

線形計画と整数計画の違いとは何か。線形計画問題の最適解は単体法という辺を辿っていく方法で求めることが一般的だ。ただ多項式時間で解けないときがある。「実際100変数の問題で単体法を使うと、多項式時間では解けない」とkaneshin氏。

またカーマーカーという人が考えた内点法（カーマーカー法）という解法もある。これは実行領域の内部から最適解を探る方法だ。カーマーカーは線形計画問題を多項式時間で解けるという理論を提唱している。

そして整数計画の最適解は線形計画問題で得られた最適解に近い整数の点が最適解にならないということも忘れてはならない。

「最適化問題は数理モデル二落とすための数学の知識がないと難しい。数理システムなどは専門的な企業が独占している感がある。プログラムがバリバリ書けて最適化問題などに関心のある人は、まずは取り組んでみてほしい。とはいえ、それぞれの計画問題は考えることが違うので、自分の研究したい分野を絞ることをお勧めする」と最後に語り、kaneshin氏の発表は終了した。

「プログラマのための数学勉強会」バックナンバー

• 線形代数・時計の整数論・フーリエ変換・証明プログラミング・エニグマ暗号…どこまでわかる？
• 線形代数入門『基底変換と固有値・固有ベクトル』を理解する
• 五次方程式は、なぜ解けないのか？
• 球体のつながり方・まがり方・大きさの関係を幾何学的に捉える

当日の資料はこちら

【動画】線形計画法と整数計画法

自分の書いたコードを誰かに評価されたいエンジニアは、けっこう多い？

ITエンジニアのための実務スキル評価サービス『CodeIQ』で出題されている「コード銀行」問題に挑戦すると、あなたのコードが評価されます。

評価(1)出題者からの評価　　⇒評価フィードバック例を見る

• 企業ではたらくという観点からあなたのコードをチェックします
• フィードバックされた観点をふまえてコードを書くと世の中の企業にとって「いいコード」が書けるようになります

評価(2)企業からの評価　　⇒評価フィードバック例を見る

• 「あなたと一緒にはたらきたい」という企業からスカウトが届きます
• あなたのコードが社会でどこまで通用するか、リアルな評価が得られます

興味を持った方はこちらからチャレンジを！