数理計画法の実用モデリングについて
草刈 君子…ll……ll……ll……lll……l11……ll…l…l……ll……lll…lllll……llll…lll……ll……lltl…llll…Illl……lll……l………‖‖＝‖‖‖‖‖‖‖＝‖‖‖‖＝‖‖‖＝‖‖‖＝‖‖‖‖‖‖＝‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖‖＝‖‖‖＝州……l………1…llll……llt…lII…

る），Dash社の設立は1989年であることからも推測

1．はじめにいただけると思う．

ずっと生きているような気がする．それでいて，い1990年代初めまで，国産のメインフレームメーカつも知りたいことが溢れている．そんな気持ちのままに勤務していることは，アルゴリズムを自分たちで考数理計画法とつきあっている．学生時代を除けば，研え，改良して，計算機を十分利用した数値実験ができ究機関に身をおいたことがないこともあり，いつも実る特権を意味していた．数理計画法の計算エンジンそ用を追ってきた．この過程で何を知りたかったのか，のものを「より速く，より大きな問題を，より安定的今，何を求めているのかを，次の4点を軸に記述する．に解く」ように作ることに最大の視点を置いていた．

・数理計画法のアルゴリズム

それが，数理計画法を利用する顧客の最大の要望であ・制約プログラミングとの融合ると信じていた．アルゴリズムの改良は，①線形計画・自動モデリング単独，②線形計画と混合整数計画の融合，③混合整数・データ，シナリオとの関連計画単独の3通りで進んだ．①，③については論文も世の中の他の職業を知らないまま，数理計画法とそ多いが，②線形計画と混合整数計画の融合はあまりなれを使うシステムに結んだ職業生活を送ってきた．こかったように思う．そうした中で，特定条件の場合のんなに面白い仕事を自分がしたいと生きている人間の逆行列生成の抑制，基底情報の入れ替えなど，実デー狭い世界の意見かと思いつつ書かせていただいた．文

タを調べ，改善しては効果を測定していた［2］．

章の背景を整理するため略歴を書くと，現在の勤務先に至るまでの前職は次の通りである．

当時は顧客側にモデルを作成する部門があり，お手伝いすることと言えば，顧客から語られるモテリレの目・富士通㈱の数理計画法エンジンの開発部門に在籍，的と，作成された数式を見て，数理計画のエンジンの混合整数計画法を担当，SE部門の要請があれば内部ロジックとうまくマッチするようにエンジンのパコンサルティングも担当．

ラメタを紹介したり，場合によっては入力形式を変更

・アイログ（ILOG）㈱にて最適系のシニアコンサして黄ったりという内容である．当時，モデルと密接に関係するアルゴリズムで一番感激したものは，SOSルタントとして勤務．

（specialorderedsets）である［1］．混合整数計画問題

2．数理計画法のアルゴリズムを最適化する方法に分枝限定法がある．通常は，整数アイログ時代，海外のメンバに数理計画法のエンジ変数を対象とするこのアルゴリズムを（順序の概念をンの開発をしていたと自己紹介すると，「なぜ？

入れることで），自然に有限の要素集合に拡張していCPLEXがあるのに？」と言われた．今となっては信る．SOSは論理的な組み合わせの数を激減するが，じていただけないとも思うが，1990年代初めまで実かわりに計算コストが高くつく場合もある．面白いの用的に数理計画法のエンジンを実行しようとすればメは（アルゴリズム上は当然のことなのだが），順序をインフレームを使わざるを得ない状況が続いていた．

定義する係数データに依存して動きが変わることであ

例えば，CPLEX社の設立が1988年であり（混合整る．適当に入れたデータではうまく動かないのに，実数計画法の提供はアイログ社のwebには1991年とあ

データではきれいに動くといったことを通して，数理モデルにおける，モデル構造とデータの関連性に傾い

くさかり きみこ

SASInstituteJapan㈱〒104−0054中央区勝どき1−13−1
238（20）ていた．

内点法が実用化され線形計画法が安定的に最適化を© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

行うのに反して，混合整数計画法は下手なモデリング

クト指向，ER分析が定着していたこともあり，装置や，乱数生成の無機的なデータを使用すると敦命的に産業向けと物流ネットワークの2通りに展開した．

性能が悪化する．全体を通しての最通性と，要求されGUIも付けた［5］．この背景には，数理計内法の中でる細かさを数理モデルとしてどう実現するのか，SOSも線形計画法については，ある程度冗長なモデリングとは別の形の選択肢に列生成法があり，制約プログラをしても，必要程度の高速に最適化が行える段階にあミングとの融合があった．

るという背景がある（数理計画法の前処理でマトリクス解析がこの手の冗長性を除去するという自fi‡もあ3．制約プログラミングとの融合る）．

数理計画法と同じく宣言的な最適化手法に制約プロ
グラミングがある．アイログ社がCPLEX社を買収

4．1物流ネットワーク間題
生産から販売までにわたって考慮する問題を考える

し，Concert，OPL上で両手法の融合を行ったように，（図1）．この間題では複数の生産ラインを持つ裡数の現在ではDash社，SAS社の製品でこれらの両手法工場と，生産を委託している委託工場が複数存在し，を利用できる．

それらの商品は，複数の倉庫で保管し，マーケットに数理計画法は全体を，目的関数を活用して最適化する．制約プログラミングは原理的には（確かに小さな出荷する．

きちんと教科書的にモデル表現するなら，解を得る

問題サイズであれば）全体をまとめて解くが，目的関必要がある変数を鼓低限度定義し，それらの関係を数数の扱いが数理計画法と異なる［9］．少し曖昧な書き式で表現していく．一方，プログラムで自動的に処理方を許して貰えば，数理計画法は全体を見渡す力があをする場合は多少の冗長性（数理計画法の前処理で除るが，細かい条件が離散である場合には性能的に辛く去される）を覚悟し汎用的に表現する．例えば，このなる．それに，整数変数の定式化は慣れるまでは面倒モデルであれば，モデル構成要素として，ノードを表だとも言われる（本当は，ほんの少し慣れてしまえば現するための要素とアークを表現するための要素の2楽しい世界が続くのだが）．反面，制約プログラミン通りに区分し，それぞれ，ノードについては図2にホ

グは，モデル表現は比較的容易である．ただどうしてす形の4変数（搬入をXin，搬出をXout，期常在棒も，大型の最適化には向かない．結局，数理計画法でをXstart，期末在韓をXendとして表現する）を川全体を見た配分を行い，探索領域を適度に縮めておい意し，関連を定義すること，アークについては医13にてから，制約プログラミングで細かい配置を立案する

示す形で図2に示すⅩoutまたはⅩinと結びつける変形が一番だと考えている［3］．

数を各アーク上に用意することで，自動的にモデルを生成する．

4．自動モデリング

つまり，物流ネットワークを構成するノードを次のモデル構造をエンジン側が把握できれば，より高速3通りに区分する．に適切にエンジンが動くことができるかもしれないと・Supplyノード（その拠点からの「出」のみ注力）いう思いをもって1990年代に入った．また，ワーク・Demandノード（その拠点への「入」のみ注力）

ステーションの台頭により，数理計画法のエンジンはすでにメインフレームから離れ始めワークステーションに軸を移していた．そうなれば，メインフレーム時代のように毎月レンタル料金が入ることを前提とした顧客コンサルティング（無償，無制限）は続けられな
し1

今まで使わなかった層に数理計画法を広めること，より手離れの良い提供が課題となった．慣れてしまえ
ば何のこともない数式モデルの構築がもしかしたら分かりにくいのではないか，構築に時間がかかることが原因か，の判断のもとに，次の視点は，「より簡単に，より分かりやすく表現すること」になった．オブジェ© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

2005年4月号（21）239

ノード

ノードロ
例えば、一期間かつノードでの形態変化がない場合で考えると、コネクタ 0

Xin＋X＄ta止＝Xout＋Xond
ここで、

アーク

Xin＝入t＞

図4

XさtaH＝期首在席

Xout＝出1
Xond＝期末在庫
図2

る（図4）．
ここで表面化すると書いたのは，物流ネットワーク
ではノードタイプによりコネクタ数固定であり，マテリアルバランス式が単純だと考えれば表現上の両者のアーク区分はいらないことになるからである．もちろんノー
Xout＝XtoA＋XtoB＋XtoC

ド内部の関係式はそれなりに異なる．

ここで、

Xout＝出1

5．データ，シナリオとの関連

XtoA＝ノードAへの牡送t●

XtoB＝ノードBへの●送1

今一番の視点は，データにある．「あなたのわがまXtoC＝ノードCへの■送1

ま運びます」という古い言葉にひっかけて愚痴ったことがある．「エンジンを速くして，と言われて速くした．モデリングが難しい，と言われて自動モデリング

首等号 ハ＼もGUIも作った．今度は，入れるべきデータがない
図3から使えない，と言われた」と．エンジンの性能競争が続いていることを理解しているし，それがとても大・Makeノード（その拠点への「入」「出」とも注きな意味を持つことも知っている．自動モデリングのオブジェクト指向のクラス表現は，モデルの視覚化の目）

Supplyノードは，図2のⅩin＝0で表現され，何クラス表現とシームレスに結びつけられる．モデルをも入って釆ない状態になる．Demandノードは，図2維持する顧客層にとって，問題の理解しやすさ，結果のⅩout＝0で表現され，何も出て行かないことになの理解しやすさ，用意されたGUIの範囲でのモデルる．Makeノードは，入ってくる畳も出て行く畳も考

改造の容易さの面で大きな利点となることも実感してえるのでⅩinもⅩoutも値を取る．各ノードで在庫をいる．それでも，どんなに速いエンジンに，どんなに考える必要があればⅩstartとXendも必要になり，素敵なGUIをつけても「GIGO（garbagein，gar−在俸が必要なければどちらも0となる．

bageout）」の言葉からは逃げられない．

ノードにおける原料やBOMなど生産条件を表現し顧客が問題を熟知しているかという話がある．もちたい場合は，図2の関係式を拡張する．複数の輸送手

ろん現実の中で顧客が問題を一番よく知っている．そ段があればアークを複数にするといった拡張が必要にれでいて，商談の初めに要件定義を（数理モデルとしなる．て矛盾のない形で）記述してくれるわけではない．顧4．2 プロセスフロー問題

客が問題をとても難しいと感じている場合に次の状況

石油精製に代表されるプロセスフロー問題の場合，が起こる．（D制約条件が小出しされる場合「こんなに環勿流ネットワークより少しだけノードとアークの表現

条件を言ったら，とても無理だから言わないでおこは複雑になる．物流ネットワークではアーク上に入っう」と，②思いっきり制約条件が入る場合「色々なケた物はそのままアークから出た．プロセスフローでは，ースがあるから全部包含して入れておこう」である．

アーク上で分離や合流が行われるため，マテリアルバ

前者の場合，構築したモデルがうまく行き相互に信頼ランス式が必要になる．このために物流ネットワークができたころ，顧客が「本当はこれもある」と追加しで必要なノードとアークの他に，コネクタが表面化す

た，

2ヰ0（22）

もしかするとその中のたった一つの，顧客は難し© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ

図5

デルヘの移行が必要になる場合がある（そうならなければ辛いである）．後者の場合，必要以上の難しさに卜手をすれば全体が失われていく．それでも，要件がペ∧卜−⊥ぶジ∴下ヽ小hlふてH

いとも思わなかった制約のために，がらりと異なるモ

矛盾している場介はヒアリングで確認できるが，要件とデータがオ盾してくるとI日々面倒になる．
結局，数理計画法の実用モデリングに必要な項目は，

Dぬ一−■lnbm鵬On → Knowl鵬go 一−■ 仙抑卿憫
図7

モデル，データ，そしてどう利用したいかのシナリオだと今は考えている．数理計内法のエンジンも，制約プログラミングとの融合モデルも，自動モデリングもすでにDEAが活用され［7］，従来の解析方法に加え図5の「モデル」を支える技術だと思う．て利用されている．

現実の関越に向き合うとき，モデルとシナリオは顧結果を見て解析する，シナリオを立てるといった場

客からヒアリングして作成し，データは顧客から提示

合，様々な視点からの分析が必要となり，初めに形式されるものを使う立場もあると考える．それでも，自を決めてしまうことは難しい．データやシナリオとう分が一番気に人っている方法は，これらを顧客と共にまく連携するようにモデルを作るにはどうするのか，考える．立場である．すなわち，顧客の要件を聞き，デ新しい課題がある．物流ネットワークの問題でこれにータも見て，どう使うかを確認して，モデリングをすトライしたとき，入力データから欠損値を許した汎用ることである（囲6）．

形式（冗長性はあるがノードとアークを区別しないでさて，データとシナリオをどう扱うか，世の中にあ扱う方式）に変換すること，入力と解を同一形式にマとを試みた［4］．こうして，最適化とデーる問題に対するアプローチの仕方には色々ある．個人

ージするこによっても異なるし，手法によっても異なる．例えば，タ解析がシームレスに関連し，モデル，データ，シナデータ解析手法の方がデータへのウエイトは大きいよ

リオを活性化する．より効果的な実用化への段階だとうだ［6］．

感じてし−る．

ビジネスインテリジェンスの世界は，データからインテリジェンスへの流れ（図7）と，データ解析と最6．おわりに適化のシームレスな連携と密接に関連して進展してき「学際（interdisciplinary）」という言葉がある［8］．

た．データ解析側からも最適化とシナリオに対して方数理計画法のアルゴリズムから始めた世界が，どこま向性がついてきた．

で広がれば実用的なモデリングになるのか，尽きなし一数理計画法が対象とするような長期計画を立案する世界だと今も思う．

ための人力データをどのように生成するべきか，数理参考文献

計画法のモデルに人力するデータの精度をどう制御し得るのかに強い興味がある．前述の物流ネットワークであれば，デマンドサイドの需要予測，安全在庫は実績データから生成できる．サプライサイドの評価には［1］Beale，E．M．L．and Forest，J．J．H： Globaloptim−
ization using specialordered sets ，Mathematical
ProgramminglO，pp．52−69，1976．

© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

2005年4‖・り・（23）241

［2］草刈君子，宮崎知明，金指哲也： 富士通AMPSからみモデリングアプローチ ，統計数理研究所共同研究リポー

た最近の混合整数計画法−その性能と通卿列− ，第2回

ト45最適化：モデルとアルゴリズム，pp．136−142，

RAMPシンポジウム論文集，pp．1卜20，1990．

1993．3．

［3］草刈君子，陳界嘉，KATAIFerenc，GOSSELIN Vin−cent： 最適化の基盤としての制約伝播技術の利用について ，第12回RAMPシンポジウム論文集，pp．53−60，
2000．

［6］新村秀一： SAS言語入門 ，1994．

［7］SASInstituteInc．： Optimization with the SASSystem，A SASWhitePaper，2003．

［8］刀根薫： オペレーションズ・リサーチ読本 ，日本評

［4］草刈君子，能島俊夫： サプライチェーンネットワークの設計 ，OR学会春季研究発表会，2005．

論社，2003．

［9］吉川昌澄： 制約最適化技術のスケジューリング問題［5］宮崎知明，中根智美，草刈君子： WS版AMPSによるへの応用，人工知能学会誌，No．3，pp．379−386，1998．

物流最適化及び装置産業用生産計画一数理計内法の自動242（24）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ