OR40年（16）日本OR学会会長
中央大学 教授

ないが，これは 専門家の中もピンキり16．整数計画法の大逆転ということの証明である．

1970年末から80年代初めにかけて，私は整数計画法の理論研究に はまりこんで今野

さて，この訳本が出た頃日本を訪れたのが，カーネーギー・メロン大学のエゴン・バラス教授である．こいた．

私がこの分野を本格的に研究することになったきっの人は，1965年に発表した0−1整数計画法問題に対かけは，69年に出たT．C．Huの教科書，「整数計画する「加法的解法」で一躍有名になった八であるが，法とネットワーク・フロー」の翻訳作業を行ったこと70年代に入ってからは，ゴモリーが先鞭を付けてまである．著者であるフ一教授は，ウィスコンシン大学もなく手を引いた整数多面体……整数計画問題の実行

数学研究所の教授で，IBMワトソン研究所時代に，可能点集合の凸包……のファセット構造の研究をやっ

整数計画法の創始者であるラルフ・ゴモリーと，ネッてし、た．

トワーク・フローの分野で歴史に残る論文を書いた

情報処理開発協会の招きで訪日したバラス教授は，分枝限定法や整数多面体のファセットに関する一連の「超」秀才である．

さてこの本は，第1部「線形計画法」，第2部「ネ講義で，若い研究者たちを魅了した．そしてこれを機ットワーク・フロー」，第3部「整数計画法」の3部

会に設立されたのが，OR学会の「整数計画法研究部構成であるが， 教科書会」である．

として採点すると，第1部は○，第2部は◎，しかし第3部には×を付けざるをここに集まった十数人のメンバの関心の対象は，得ないできだった．×をつけた理由は，役に立ちそう分枝限定法だったが，私はバラス・グループ（R．

もない代数的な解法に多くのスペースを割く一方で，Jeroslow，M．Padberg，LWoIsey，R．Blairら）の代実肝性の高い分杖限定法に関する記述が，たったの5数的方法の研究に集中した．しかし残念なことに，こページしかないことである．のグループの研究成果をロ及収するのに精一杯で，その分枝限定法には数学的な探味がない，というのがそ先を行く成果を挙げることはできなかった．の理由だったが，結果的にこの人は，70年代以降のこの研究部会は3年にわたって継続し，全メンバの分枝限定法の大発展と，代数的方法の衰退を見誤った協力の下で「整数計画法と組み合わせ最適化」（日科のである．急激に変化する分野の教科書を書くことが技連，1982年）をまとめて散会した．そしてほとん

し−かにリスキーかを示す見本のような本である．このどのメンバは，別の分野に転進していった．各自それためこの本は，72年に出たGarfinkel−Nemhauserの，ぞれの理由があったのだろうが，ともかくこの時代は，より分かりやすくバランスの取れた教科書に完敗して計算機が高価な上にとても遅かったから，実用規模のしまった．

問題はなかなか解けなかったし，自分で考案したアル当然ながら，75年に出た訳書はまったく売れなかゴリズムを検証するのも容易でなかったのである．

った．ところが，この本を翻訳したということ（だ私が転進（撤退）した理由は，バラス・グループのけ）で，私は整数計画法（の中の代数的方法）の専門研究の後追いに疲れてしまったことと，コーネル大学家ということになってしまうのである．実際，この頃のネムハウザーが，バラスたちの研究を， 悪しき（そして今も）この本の内容を完全に理解している人ORの見本はほとんどいなかったから，全くの嘘というわけでは受けたためである．

2005年10月ぢ・と批判しているのを耳にしてショックを© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（41）T19

こうして私は整数計画法から手を引いた．

しかしこの頃バラスの理論的研究は，実用規模の組み合わせ最適化問題に応用され，成果を挙げ始めてし−たのであは，98年のDiscreteAppliedMathematics誌に招待論文として掲載された）．

それから15年間，私は整数計画法とは無縁な生活を続けていた．金融工学と大域的最適化法の研究に集る．

ダンツイクの一番弟子であるE．Johnsonと，バラ中していたからである．そして90年代半ば以降，私スの一番弟子であるM．Padbergが協力して，大規模は残された最大の難問， 凹型取引コストの下でのポな巡回セールスマン問題を解くことに成功したのは，ートフォリオ最適化問題 に取り組んだ．そして6080年代前半のことである．そしてそこに使われたの年半ばに提案された，J．Falkらの超直方体分割法をが，バラス・グループの研究……ファセット・カット改良することによって，幸運にも，この問題を解くことその持ち上げ技術，および離接かソト……だった．とに成功した．提案された当時は，全く役に立たない

しかしこの話を聞いても，私はこの分野に戻る気にはなれなかった．なぜならここで使われたファセッ
ト・カットは，巡回セールスマン問題のネットワークと思われていた方法が復活したのだから，世の中は何が起こるか分からないものである．

一方，凹型関数最小化問題を解く方法としては，古構造を利用した巧妙かつ難解なもので，私にはそのくからよく0−1整数変数を導入して折れ線近似する方かけらも理解できなかったからである．一方，E．

法が知られている．しかしこの方法は，実際にはうまJohnsonらが80年代半ばに，5，000変数からなるスくいかなかった．非線形関数を折線近似するには，一ューリング問題を解いたときには心が揺れた．な

つの変数につき最低でも5個の0−1変数が必要となる

ぜならそこに使われたのは，私が十分に理解したナッから，変数が1，000個あれば，数千個の0−1変数を取プサック多面体のファセットと，離接カットだったかり扱わなくてはならない．こんな問題は絶対に解けならである．

い．これが80年代初めの常識だった．

ケジ

ナップサック問題はNP完全問題であるが，ほとところが，この解けなし、はずの問題を，新たにリリんどの問題は分枝限定法で簡単に解ける．それにもかpスされたCPLEX8．1に食べさせたところ，大域的かわらず，なぜバラス教授はこの問題のファセット構最適化法より10倍速く解けてしまったのである．シ

造を研究しているのか．理由はよく分からなかったが，ョックを受けた私は，この前年に出た労作，「応用数私にとってとてもおもしろい研究だった．

理計画法事典」（朝倉書店，2002年）の整数計画法の一方の離接カットは，1974年に発表されたものだ

章を執筆した松井知己氏にメールを打った．

が，バラス教授から送られてくるおびただしい論文群の中でも，突出して難解かつ長大なものだった．全部松井兄で31個の定理が埋まっているこの論文を読破するにその後如何お過ごしでしょうか．少々お尋は，1年以上の時間が必要だった．やっと理解はした

ねしたいことがありメールします．このとこ

ものの，これが実用上どのような意味があるのかはよろ取引コストの下でのポートフォリオ最適化

く分からなかった．数学的に奥深いが，実刷生がある問題を0−1整数計画問題として定式化して，かどうか分からない理論．おそらくネムハウザーのタCPLEXで解かせたところ，その余りの速さーゲットは，この論文だったのではないだろうか．にビックリしています．こんなことは常識な

ところがこれらの理論が，大規模スケジューリングのでしょうか．貴兄が書かれた整数計画法の問題を解く上で，決定的な役割を果たしたというので章を読み直してみましたが，一言もその種のある．ネムハウザーの批判をものともせず，バラス・記述がないのが気になります．またこのソフグループがこの研究を継続したのは，いずれ実用上重トは，一体どんな方法を使っているのでしょ

要な役割を果たすことが分かっていたからだろう．

うか．

ちなみに，74年に書かれた離接計画法論文が日の目を見たのは，24年後の98年のことである．長い間わずか10分後にトロントから戻ってきた返事は，放置されていたのは，ある有力ジャーナルで拒絶査定驚くべきものだった（それにしても，インターネットを受けたためだが，この論文は整数計画法の歴史を書はありがたいものです）．

きかえる記念碑的論文だったのである（なおこの論文
丁20（42）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

オペレーションズ・リサーチ究所長に就任した後，IBM副社長，スローン財団理今野先生

CPLEXが驚くほど速いという話は，今で事長，大統領特別顧問を務めたゴモリーが，70歳にも良く耳にしますので，まだ常識とはいえななったのを機にすべての公職を辞し，整数計画法の研いでしょう．しかし少なくとも，あの本に関究に復帰したのである．

わった若手たちの間では常識です．私は先生

ゴモリーは，91年に次のように書いている． 私のから引き継いだT社の実務家研修では，整数計画法に関する研究は，IBMの研究部門のヘッ

3000変数までの0−1整数計画問題は，何もドに就任した1970年に打ち切られた．そしてそれか考えずにCPLEXに食わせればし−いと言っら後，少なくとも現在まではそのままになっていると．

ところがそれから10年ほどして，米国OR学会のています．

さて何故速いかですが，その秘密は単体法誕生50周年を記念して発行された，『Operations

ルーチンの中のピボット選択と，分枝カットResearch』詰の50巻第1号の中で，ゴモリーはこの法におけるゴモリー・カットだということで文章を引用しながら次のように書いている．

す．しかしこのあたりの事は良く分かりませ「私は1991年に， 少なくとも現在までのところこのとき私は，いつの日か未完のままになん．大きな問題が解けることは事実ですが，と書いた．

それができるのはCPLEXという商品だけっている研究に復帰したいと考えていた．その希望はで，他にそれと太刀打ちできるソフトがないついに実現された．今私は，かつての同僚であるエリため，出てきた答が正しいかどうか検証しよス・ジョンソンらと研究活動を再開した．そして近々，うがありません．ここでCPLEXが速いと整数多面体（コーナー多面体）の理論と実用性に関す書くと，ILOG社の宣伝になってしまうので，る論文を発表する予定である．」

学術的な記述の中にはそのことを書くわけにはいかなかったのです．

私はこの論文が出るのを首を長くして待っていた．
そして2003年の秋，Johnson，Araozと共著で書いた3篇の論文が『MathematicalProgramming』誌に発40年前のゴモリー・カットが決定的役割を果たしていると聞いて，私は仰天した．この方法は，60年表されたのを見て，ゴモリーのあふれるばかりの情熱に圧倒された．

代半ばに理論倒れの代表と批判され，ORの地盤沈下

ゴモリーは書いている．「ここには大きな鉱脈が埋に→役員った方法だからである．この手紙の数カ月後，まっている．みんなで力をあわせて宝物を掘り出そ

私はCPLEXを開発したライス大学のR．Bixby教授

う」と．残された時間が少ないことを考えれば，自分の講演を聞いて，松井氏の言っていることが事実であたちだけでは掘りつくせそうもない．だから皆さん一ることを確認した．

緒にやりましょう，と若者たちに呼びかけているのでその後間もなく，CPLEX以上に強力と称せられるある．パーティでのスピーチならともかく，正式の論ソフトウェアXPRESSが登場した．実際に使ってみ文の中でこのような呼びかけを行うのは，異例のことると，噂どおりこちらの方が少しばかり早い上に，打である．

ち出してくる答は全く同じである．この結果，一般の果たしてゴモリーの研究は，新たなブレークスルー整数計画問題に対する比較検証を行うことが可能になに結びつくのだろうか．そして2002年にBixbyが書った．今後は，かつて線形計画法の分野で繰り広げらいたように，誰かが10年後に再び， 10年前には誰れた，単体法ベースのCPLEXと内点法ベースのも解けるとは思わなかった問題が解けるようになっOB−1のバトルが，整数計画法の分野で繰り返されるたことになるのかもしれない．事実，2003年にリリーとはできないが，せいぜい健康に注意して，10年後スされたCPLEX9．0は，8．1より数倍速い．

を見届けたいものだと考えている．と書くのだろうか．私はもうこの研究に加わるこ最後に，整数計画法におけるもう一つの仰天ニュー（なお，整数計画法に関わるドラマについては，10スを紹介することにしよう．それはスーパースター，月末に刊行予定の「役立つ1次式：整数計画法の物ゴモリーの現役復帰である．60年代末にワトソン研語」（日本評論社）を御覧いただきたい．）

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

（43）丁21