【書評】室田一雄編

離散構造とアルゴリズムⅠⅤ
近代科学社 230頁
馳散構造を有する情報の効率的処理はオペレーショ

1995年刊 定価3，000円
る有向マトロイド（のベクトルの族）を定義している．

ンズリサーチの分野でも古くからその重要性が認識さそして，線形部分空間における線形■計画問題に対応しれ研究されてきたが，最近では計算機の高速化・低廉て，有向マトロイド（のベクトルの族）における有向化に伴い今後の高度情報化社会を念頭においてより高マトロイド計画問題を紹介している．このように有向品質の情報処理が要求されてきて，離散構造とアルゴマトロイド計画問題は線形計画問題を一般化した問題

リズムの研究はますます活発に精力的に遂行されていであるが，線形計画法における基本的なアルゴリズムる．このことは，この分野で研究する者にとっては大や性質，たとえば，シンプレックス法，基本定理，双変うれしいことであると同時に，研究の黄先端を概観対定理，相補性定理などは，有向マトロイド計画法でするのが限りなく困難になっているという側面もはらも成立し，むしろそれが自然であることを示している．
そして有向マトロイド計画法で提案された最小添字んでいる．

本書は，このような状況を克服しさらにこの分野の規則に基づくシンプレックス法では退化した巡回が生発展に貢献することを目的として，最新の離散システじないことを示している（従って最小添字規則に基づ

ムに関する理論的成果・実際的成果を既存の学会の枠く線形計画法のシンプレックス法では巡回が生じないを超えていち早く研究者が共有できるようにとして開ことがいえて有限回の反復（ピボット）で終了するこ催されている日本応用数理学会の「離散システム研究とがいえる）．これは有向マトロイド計画法で得られた部会」の第4回講演会（1994年6月15日統計数理研究所

成果が線形計画法に応用された例であるが，実は有向にて開催）の講演内容をまとめたもので，以下の5編マトロイド計画法では線形計画法では生じることのなの解説論文からなっている．

かった非退化の巡回が存在し，▲最小添字規則に基づい1 線形計画法と有向マトロイド計画法

たシンプレックス法では有限回の反復で終了しないこ

2 線形相補性問題の内点法ともありうる．これに対する解決策として十文字法を3 点列のdiscrepancyについて紹介し，十文字法では巡回は生じないことを証明して4 0−1多面体における端点の隣接性有限回の反復で終了することを示している．
十文字法の計算幾何学や有向マトロイド相補性問題

5 メタヒューリスティックス

いずれの論文も，それぞれの専門分野で現在最高にへの応用についてもふれている．特に，有向マトロイ活躍している研究者が研究の背景を綿密に調査し今後ド相補性問題に対する十文字法は，ある種の条件付きの研究動向も見据えて書いたもので，内容はかなり高で解を求めるように拡張できるが，この条件を除くこ度であるが，この分野の専門家のみならずこれから新とが有向マトロイド相補性問題の大きな関心事になっしくこの分野の研究を始めようとする読者にも十分にていることを紹介している．

配慮されたものになっている．ここでは，1と4を中

この解説の圧巻は，Farkasの補題に対応する二者択

心にその内谷を紹介し，その後2，3，一性の概念に関係する深い洞察である．線形部分空間

単に触れ，最後に読後の感想を述べたい．の用語を用いてFarkasの補題を言い直し，それに基づ

1は田村明久氏（電気通信大学）によるもので，線いて符号付きベクトルの集合に対してFarkas性を定形計画法のシン70レックス法，基本定理，双対定理，義し，関連してMintyの彩色補題を一般化した形の彩相補性定理などの重要な概念の復習から始め，Farkas

色性，すなわち，2彩色性，3彩色性，4彩色性を導の補題と双対定理の等価性の証明と進み，さらに線形入しそれらの概念で規定されるクラスのl曙層構造を解空間の本質的な性質を抽出して符号付きベクトルの集析している．そしてそれに基づいて，符号付きベクト合を考え，線形部分空間を自然に抽象化した概念であルの集合においてはFarkas性と双対定理は等価でな

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

（43）403

いことを示している．すなわち，実行可能解集合としての端点が隣接していることを紹介している．このこて符号付きベクトルの集合が与えられたとき，その中とは線形計画法のシンプレックス法に対応する局所探で目的関数を最大にする問題およびその双対問題にお索法では効率化がうまくいかないことを意味し，多面いて最通解が存在すれば目的関数の値は一致するとい体理論の研究の人気がなくなった理由でもあると分析

うのが双対定理であるが，Farkas性が成立しても双対している．

定理が成立しないことがありうることを示している

ノ

そこで著者およびその周辺では従来の研究がピボッ（実行可能解集合として符号付きベクトルの集合が有ト操作に注目していたことを見直して，新たにピボッ向マトロイドとなるときは，Farkas性と双対定理は等ト操作によらないという観点からの多面体理論の研究価である）．

が今後の研究方向ではないかと提案し，自分たちの得このようなことからも有向マトロイドの重要性が理た研究成果の紹介もしている．この方面の研究の重要解できるだろう．紹介された成果は著者を含めた著者性を認識していながらどのように研究調査してよいのの周辺で得られたもので，有向マトロイドの最先端のかわからなかった私にとっては極めて参考になった論

内容が極めて理解しやすい形で述べられていて，読者文である．

はその心配りに目を見張ってしまうだろう．さらに，2つの解説論文の内答を紹介したが，他の3編の論著者の自信がひしひしと伝わってきて本当に刺激にな

文もこの2つの論文に劣らず素晴らしい傑作である．

る解説論文である．

今後の研究動向のコメントや参考文献もふんだんに盛

4は松井知己氏（東京大学）によるもので，0−1り込まれていて，読者にはとても有用である．

多面体，すなわち0−1整数計画問題の実行可能解（を2は水野眞治氏（統計数理研究所）によるもので，表す特性ベクトル）の集合に対する凸包の理論を扱っ

線形計画問題，二次計画問題の主問題と双対問題を同ている．初めに0−1整数計画問題を効率的に解くた

時に定式化した相補性計画問題に対する各種内点法をめ線形計画法のシン70レックス法に対応する手法の可解説している．この解説で紹介した成果に関する研究

能性を探って発展したこの研究分野の成果を概観してで水野氏は小島政和氏らとともに1992年度Lanches−いる．すなわち，0−1多面体のいずれかの端点で最ter賞を受賞し，1995年秋季研究発表会では共同受賞の適解が実現されることに注目して隣接する端点間を移吉瀬章子氏（筑波大学）の招待講演があった．
3は手塚集氏（日本IBM）によるもので，「無限」を動していきながら最終的に最通解を求める局所探索法を適用する際多面体の端点同士の隣接関係が重要にな「有限」に置き換えたときに生じる一様分布からの「ズるので，そこで，一般の多面体での隣接関係から始め，レ（discrepancy）」を扱っている．discrepancyは，多等式制約0−1多面体での隣接関係，集合分割多面体重積分，コンピュータグラフィックスの分野で重要なでの隣接関係と多面体のクラスを制限していきながら，概念であるが，それについての最近の研究動向が概観

隣接関係の特徴付けを精密化している．また，集合充されている．一様乱数とも密接に関係しているので，填多面体と集合分割多面体では隣接関係を保存するよ

乱数の大家である手塚氏が単独で善かれた「Uniform

うな端点同士の1対1対応が存在することも示していRandom Numbers：Theory and Practice（Kluwerる．

AcademicPublishers，1995）」も参考にするとより役
これらのことから，集合充填多面体の端点に対応すに立つだろう．

るグラフのマッチングとかグラフの独立集合では，多5は久保幹雄氏（東京商船大学）によるもので，特面体での2つの端点に対応するマッチングあるいは独にNP困難な組み合わせ最適化問題を解くための立集合の隣接関係の特徴付けが得られ，その特徴付けヒューリスティックスを扱っているが，単なるヒューに基づけば隣接関係を判定することは多項式時間ででリスティックスではなく，パラメータをうまくコントきることを示している．一方，隣接関係判定が難しくロールし実用的なツールとなるようなメタヒューリスNP困難となる場合も多く，実際，等式制約0−1多面ティックスを紹介している．そのメタヒューリス

体や集合被覆多面体での隣接関係判定はNP困難であティックスとしては，SimulatedAnnealing法，Tabuることを示している．同様に，ハミルトンサイクル多Search，GeneticAlgorithm，Quickerそして著者の提面体での隣接関係判定問題などもNP困難である．こ案したLifeSpanMethod，および，GenericLocal

れに対して完全グラフのカットセット多面体ではすべSearchを解説している．さらに実験的解析のための十404（44）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

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

戒やそのための方法およびベンチマーク問題の入手法

書評を書くためにかなり時間を割いて読んでみたわけにも触れていて，これからこの分野の研究を行う読者であるがとても参考になり勉強になった．あるところにはバイブルともいえる解説である．

では深い感激も味わった．現在は私の来年度の大学院

この「離散構造とアルゴリズム」のシリーズはすでの講義「離散アルゴリズム」で教科書として採用しよに3冊刊行されているが，いずれもこの分野の現役のうかと検討している．その意味でも，この分野に関心最高の研究者が執筆したもので，研究成果を概観したのあるOR学会の会員にはぜひお薦めしたい本である．

い読者には大変便利な書籍である．私自身も今回この（浅野孝夫 中央大学）

学会に届いたORの本さった方には，その本を進呈いたします．学会誌

最近，出版社各位より学会宛に下表のような本が届いています．ご興味をお持ちになり，「書評をを活性化するための具体的な試みです．なにとぞしてみたい」とお考えの読者諸兄におかれましてご協力をお願い申しあげます．加えて，読者諸氏は，どうぞご連絡ください．郵便またはFaxにて，による書評の投稿も歓迎します．皆さんがお手元（1）氏名，（2）連絡先住所・電話番号，（3）所属，（4）にお持ちの本の中から，OR学会誌に相応しいもの専門分野，をご連絡くだされば書籍をお送りいたについて書評をお寄せください．

します（基本的に先着順）．もしも，その本にOR連絡先 栗田 治（OR誌編集委員・書評欄担当）

誌の読者に紹介すべき見所がある，と判断なさっ〒223横浜市港北区日吉3−14−1た場合は，その書評をお寄せください．お読みに慶應義塾大学理工学部管理工学科

なったうえで，1カ月以内に書評をお寄せくだ

Fax：045−563−5979（学科事務局）
OR献本リスト

書著 者

名

出 版社

出版年月日

頁数 価格（税込み）

436

5，600

保田勝通

ソフトウェア品質保証の考え方と実際

日科技連出版社

95年11月新村秀一

パソコンによるデータ解析

講談社

95年11月

318

800

高木晴夫・
木島恭一他

マルチメディア時代の人間と社会

日科技連出版社

95年11月

293

3，000

高木晴夫

ネットワークリーダーシップ

日科技連出版社

95年11月

199

2，500

豊田秀樹

非線形多変量解析一ニューラルネットによ

朝倉書店

96年2月

174

3，296

日科技連出版社

96年2月

234

4，300

95年11月

165

2，987

現代数学社

95年3月

331

4，429

日刊工業新聞社95年12月

204

2，800

95年6月

171

2，000

95年7月

182

3，300

るア70ローチー
木島正明・長l1Jいずみ他
宮村裁夫

ファイナンス工学入門 第lII部
シリーズ【現代人の数理】9．PL制度と製品安全技術

西田俊夫／田畑吉雄編
中川零夫・三通弘明

生産管理理論と実践12．オペレーンョ

木下栄蔵

情報処理入門シリーズオペレーションズ・リサーチ

松村幸輝

基礎からのORシミュレーション

南石晃明

確率的計画法（不確実性に挑む知恵と技術） 現代数学社

95年12月

167

2，987

児玉正憲

確率モデルの数理分析（生産・在庫モデル

96年4月

371

6，386

96年4月

286

3，708

ンズ・リサーチ

オーム社と信頼性・待ち行列モデル）
児玉正憲

1996年7 月号

生産・在庫管理システムの基礎

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

（45）405