CodeIQ MAGAZINECodeIQ MAGAZINE

最適化問題を「線形計画法と整数計画法」で解く─プログラマのための数学勉強会5

2015.07.13 Category:勉強会・イベント Tag: , ,

  • 156
  • このエントリーをはてなブックマークに追加

「プログラマのための数学勉強会」レポート第5回目は、エウレカでpairsなどの開発に携わっているkaneshin氏による「線形計画法と整数計画法」 について。

本来はカーマーカーの話を予定していたというkaneshin氏の講義をダイジェクトで紹介する。
by 馬場美由紀 (CodeIQ中の人)

線形計画法と整数計画法

本来はカーマーカーの話を予定していたが、「誰得?」ということで、整数計画法の話に変更したというエウレカの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の生産量を変量とすると次の式が立つ。

2x_1+5x_2

これを最大化する。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

CodeIQ高校 教育実習生 Lala*さんからの問題

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

当日の資料はこちら

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

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

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

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

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

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

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

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

  • 156
  • このエントリーをはてなブックマークに追加

■関連記事

ヤフー・クックパッド・ピクシブの現場エンジニアが語った、HTTPS化の裏側と対応のコツとは?... 3名の登壇者と川田氏によるパネルディスカッション 2014年にGoogleがHTTPS化対応サイトを検索結果で優遇するロジックを実装したが、日本ではなかなかHTTPS化が進んでこなかった。 セキュリティリスクの低減、開発・運用の効率化、安全性や信頼性のアピールなどHTTPS化には多くのメリットが...
ソフトバンク・ヤフー・HDE人事責任者が明かした「最先端の採用手法」とは?... 事業とともに変化する採用への挑戦―ソフトバンク 第一部のセッションを務めたのはソフトバンクの小山亮氏。セッションタイトルは「新たな道を切り開け!『事業とともに変化する採用への挑戦』」。 小山氏は5年前にソフトバンクに転職。3年前より新卒採用をメインに担当している。 ▲ソフトバンク株式会社 人事...
ヤフーがAndroidアプリに関する技術や開発事例を共有する「CAMPFIRE Android」を開... Yahoo!知恵袋をRxJavaでフルリニューアル ヤフーのAndroidにおける技術情報を共有するMeetup「CAMPFIRE Android #1」が、4月19日にヤフーのコワーキングスペース「LODGE」で開催された。 「Yahoo! Japanでの取り組みや開発のコツを知ることができる...
営業・事務職もプログラミングを学びたい!「TECH::CAMP」イベントに96人の女性が参加... 女性がITの力で活躍する場を拡げるイベント「TECH LADY HOLYDAY」 「TECH LADY HOLYDAY」は、女性がITスキルの習得の魅力を知る機会、およびスキル習得アクションの機会を提供する女性のためのイベントだ。 ITの力で活躍する場を拡げることを目的に、「世の中にサービスを生...
データビジュアライゼーションから圏論・Haskellまで──プログラマのための数学勉強会【第6回】... 今回のテーマと目次 「プログラマのための数学勉強会」第6回のセッションテーマは以下のとおり。 心地よさと数字 難易度★☆☆ 数学がデジタルアートに! 高速なシェーダで可視化する数学の世界 難易度★☆☆ Wolfram Language コトハジメ ~ Wolfram Alpha って聞いたこと...
まつもとゆきひろ氏がSpeeeで語った、勉強会・英語・プログラミングの話... まつもとゆきひろ氏とコードを競うコードゴルフ大会 今回訪問したSpeeeの社内勉強会が開催されたのは、同社のカフェスペース「SpeeeLounge」。とても素敵なカフェだ。 そこでは、エンジニアたちが真剣にコードを書いていた。 今回の勉強会で行われたのは、与えられたお題に対して、誰がも...

今週のPickUPレポート

新着記事

週間ランキング

CodeIQとは

CodeIQ(コードアイキュー)とは、自分の実力を知りたいITエンジニア向けの、実務スキル評価サービスです。

CodeIQご利用にあたって
関連サイト
codeiq

リクルートグループサイトへ