RAMP シンポジウムルポ
電気通信大学田村明久
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111

街路樹は赤や賞に染まり，歩道にも落ち葉が目立つ

晩秋を思わせる筑波大学において，1993年 10月 21 日(木)・ 22 日(金)の両日にわたり第 5 回 RAMP シンポ

フィンスケーリング法の理論的解析」と題してトップバッターを務めた.講演の最初に見せた OHP を紹介するとジウムは開催された.今回のシンポジウムでは， r数理・アフィンスケーリング法とは?

計画の理論J r数理計画のモデリングと応用 J r計算幾

.これまでの研究紹介

何とその応用」という 3 つのセッション，計 11件の講・主定理「ステップ幅 2/3 の大域的収束性j

演が企画された.参加者は，一般98名，学生31名，合-局所ポテンシャル関数による収束性の証明の概要

計 129名であった.約 4 分の l が学生であることは，後.2/3 の最適性について継者が着実に育っているということだろう.

-超 1 次収束をもっロングアフィンスケーリング法

1 日目午後 1 時 25分，主査の今野浩氏(東京工業大というような内容が書かれていた.このように講演内学)の挨拶によりシンポジウムは幕を開けた.その中容を簡単に説明してもらうと細かいところはわからずで氏は，rRAMP シンポジウムはたった 2 日間で 1 年とも話の大枠が理解できるので，r うん面白かった」と分の成果を知ることができる有意義なものであるこいえる.まさにトップノ〈ッターからして好演であった.と J，では，講演内容を簡単に説明したい.

r小島政和氏(東京工業大学)，水野真治氏(統計数理研究所)，野間俊人氏(防衛庁)，古瀬章子氏(筑波大学)，

Nimrod Megiddo 氏(l BMAlmaden

アフィンスケーリング法は，1967年にI. I. Di kin によって提案された線形計画問題に対する世界て最初のResearchCenter) がORSA よりランチェスター賞を受内点法である. (この意味で，内点法を研究する方は特賞されたという報告J r カーマーカ一法(アフィンス許申議されたカーマーカ一法の新規性に疑問をもたれケーリング法)が日本において特許を得てしまった」ている. )まず，この方法の大域的収束性に関するいくという 3 つのことを話きれた.第 1 の話はまきにそのつかの結果が紹介された.この方法では現在の内点かとおりであった.各分野一流の講演者を集め，立派なら次に進むべき方向の決定にアフィン変換を利用し，会場(筑波大学・大学会館)を準備された実行委員お主定理では， r この方向に進み，実行可能領域の境界まよびオーガナイザーの方々の熱意の一端でも以下で伝での 2/3 以内に次の点を定めれば大域的収束性が保えられればと思う.ランチェスター賞の受賞に関して証される j ことを主張している.さらに，これ以上境は日本人として初めてで，受賞された方々の精力的な界に近づくと収束しないという例が示された.またこ

研究が名実ともに世界に認められたことは大変喜ばしの大域的収束性の証明には双対定理を用いていないのい.第 3 点に関しては，カーマーカ一法はあくまで数で，双対定理が導かれるとの紹介があった.

学的アルゴリズムであり数学は特許にしないという特2 番目の講演は，奈良先端科学技術大学院大学の福許の原則に反し，カーマーカ一法の新規性という点で島雅夫氏による「数理計画問題に対する並列アルゴリもこの特許には問題があることを氏は指摘している.

ズム j であった.

(氏本人が何度も言うのを嫌がるくら

的確に要点を押さえ人を引きつける今野主査の開会のいに長い所属であるが，キーボードから入力するのも挨拶を毎回楽しみにしていたが，今回限りかと思うと楽ではない. )最初に，オベレーションズ・リサーチに少々寂しい思いがする.

おいて並列アルゴリズムが重要な役割を果たすことに

第 1 セッション (21 日午後) :ォーガナイザー小島政和氏(東京工業大学)，

r数理計画の理論」では4件の講演が行なわれた.

算機の説明をした.講演では，多くの問題が帰着される単調な点

このセッションでは，都合により第 1 講演者と第 3講演者が入れ替わり，統計数理研究所の土谷隆氏が「ア1994 年 1 月号なるだろうとの紹介， SIMD型， MIMD型などの並列計集合写像の零点を求める問題を対象とし話が進み，この問題に対する近接点法，

Douglasｭ

Rachford の分割法などの解法および専門用語の説明© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

51をした.特に(凸目的関数最小化)輸送問題に対する並列アルゴリズムとその計算機実験の結果が示され，CM-5 という並列計算機を用い，100:万変数の問題を30秒て解いたと報告した.発表もきることながら，シンポジウム論文集には 95編の参考文献が載っている.
今後，この分野を研究しようと思う人には良い道しるべになるだろう.
3 番目は，東京工業大学の渡辺治氏による INP型問題の近似解法の可能性について」であった.氏は 1992
年 IBM科学賞を受賞され，計算の理論に関する日本の第一人者の 1 人である.講演では， INP判定問題JINP探索問題J INP最適化問題 J (これらの総称、を NP 型問の提案を受理したときのみこの提携が成立し報酬が分題と呼ぶ)の各々に対して，I近似問題 J I疑似多項式配されるというものである.ただし、ピリオドが進む

時間アルゴリズム J I 平均的な解析」という近似のアプにつれ報酬が一定割合 ô(O<ô<l) ずつ減額きれてローチから，現在どのような結果が知られているかがいし講演では，このゲームに対するある種の均衡純紹介きれた.その中から， 2 つ IP 宇 NP ならばP-close戦略についての結果が紹介された.最後に 3 人ゲーム

近似不可能な NP 問題が存在するJi P 宇 NP ならばクラの場合にはこの均衡戦略が 3 種しかなし

ス MAXSNP (重要な最適化問題のほとんどが入るクが被験者となった実験の結果が示された.

ラス)のすべての最適化問題は弱近似不可能である J

第 2 セッション (22 日午前) :ォ --11'ナイザー森戸晋を紹介しておく.実際に NP 困難な問題を解いている氏(早稲田大学)，

人にとっては，3 件の講演が行なわれた.

INP 困難な問題はやはり難しい j という否定的な結果の紹介であったが.1だからと言って悲観も楽観もするべきではない」という氏の結論が印象

3 人の学生I数理計画モデリングと応用 J では，このセッションの 1 番目は，

TERRY の前田英次郎氏による「数理計画ユーザー支援システム」であった.

的だった.キーワードの説明を全くしなかったが興味

数理計画法を利用して現実の問題を解くには，実態調をもたれた方は，シンポジウム論文集または講演者著

査，数学モデルの作成，データ収集，計算機への入力の計算可能性・計算の複雑き入門，近代科学社を参照

作成，数値解の計算，モデル/解の検証という過程をされたい.盛り沢山な内容を整理し，初学者にもわか経る.以前とは異なり現在では数値解の計算は人件費りやすく，ユーモアある講演にはいつもながら脱帽すに比べコストが安くなり，入力作業がより楽にできる

る.また講演を聴きたいという欲求に駆られてしまう.

モデル記述言語の必要性を説いたのが主題である.講

このセッションの最後は，京都大学の岡田章氏によ

演では， MPS フォーマットの不十分きやそれを補うた

る IA noncooperativecoalitionalbargaininggame

めの支援システムであるマトリックスジェネレータ，withrandomproposersJ であった.

数式型モデル記述言語，図表型モデル作成システムな

RAMPでは

2，AMPL, GAMS, XPRESS-MP, LINGO

3 年に一度ゲーム理論の講演が行なわれ最近の話題がどに触れ，紹介きれるが，今回もこの分野の第一人者が招かれた.

といったシステムを紹介した.ユーザー支援システム

ゲーム理論の発展: 60年代は協力ゲーム，70-80年代の紹介のような内容に対して，実物を見せられないとは均衡点の理論の発展，経済学の新展開といった非協いうのは講演者にとっても歯がゆいことと思う.特別力ゲーム革命があり，現在では，非協力ゲーム理論とな施設がない会場でも，カラー液晶パネルと OHP に協力ゲーム理論の統合，協力行動の非協力ゲーム分析

よって計算機の画面をスクリーンに投影できるので，が行なわれているとの紹介から始まった.提携形成にこのような機材が簡単に利用できるようになればと願関する n 人ゲームやコアといった基本的な概念や今回7.

扱うゲームの説明を行なった.このゲームは，各ピリ

2 番目の講演は， I セメント最適生産計画と整数計画

オドで 1 人のプレーヤーが等確率で選ばれ，この人が法J と題し小野田セメントの相沢健実氏により行なわ

自分を含み報酬が正となる 1 つの提携とそのメンバーれた.原料工程，焼成工程，製品工程というセメントへの報酬の分割を提案し，すべての提携メンバーがこ製造工程の説明に始まり，エネルギーの多消費型産業，

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

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

F
ujis
hig
eandZhanの方多品種化の進行といった製造工程の特徴に触れ，製造る 3 つの方法， Wolfの方法，電力費用最小化に関する実例を紹介した.必要な電力法，を自家発電，排熱発電，買電にいかに割り振るか，特の方法の有限終了性を簡単に説明した. (独断的と思えに夜間の安価な買電をどうするかが問題であるというるところも少々あったが， )氏なりに噛み砕き解釈し，SekitaniandYamamotoの方法の紹介をし，各々指摘があった.混合整数計画問題としての定式化，運超平面の回転という観点からの，上記 3 つの方法の関転の連続性の表現に対する工夫など説明した.計画日係の説明は圧巻であった.絵や図をなるべく多く用い数が 5 日で計算時間約 3 分

7 日で 5 分という計算実験結果が，教科書的定式化(それぞれ 4 5 分3 時間6 分)に比べ改善されていることが示された.また最後に，輸送計画や生産計画との相互関連を考慮し，偲々て人にわかってもらおうという姿勢に立った氏のプレゼンテーションは，学生だけでなくわれわれも見習うべきことと常々思う.
2 番目の講演は，中央大学の今井桂子氏によっての最適化システムを総合化したいという抱負が述べら

IDiscretegeometryanditsrelatedproblemsJ といれた.きすがにセメント生産システムの実物を持ってう題で行なわれた.計算幾何学の初期では，凸包問題，きて「これです」とは見せられないが，写真や図を多最小包囲円問題などが研究されていたが，近年は対象用してのプレセ守ンテーションはわかりやすい.

が動く動的計算幾何学が研究されているとの紹介がこのセッション最後の講演は，東海大学の羽田隆男あった.例として，動的ボロノイ図，その組合せ的複氏による「数理計画法にもとづく多品種中小量生産の雑度，幾何的フィッティング問題への応用等を説明しライン設計j であった.多品種中小量生産化にも柔軟た.複雑度の解析に重要な役割を果すのがDavenport­に対応するために，類似部品をグループ化し共通的に加工する GT(GroupTechnology)

ラインの活用といSchinzel 列(定義は論文集参照)で，この列に関する組合せ的理論の幾何的問題への応用が本講演の主題でう動機説明に始まり， GT ラインと GT フローラインのある.互いに交わる回数が高々 S である n個の 1 変数連

1 つの設計方法を提案した.前者では，加工順序が機続関数五の集合において，下側エンベロープを構成す

械の順序と逆流する部品の総移動量を最小とするライる関数の添字列の最大長が，パラメータ n と s によってン設計を目指し(機械の順序とそこに流す部品の集合定まる Davenport-Schinzel 列の最大長に等しくなる.

を求める) ，逆流最小化という問題を解くことでこれをこの最大長がパラメータ s を固定したときに ， nlこ関し行なう.後者では，部品の逆流を許さない GT ラインのてどのような関数になるかの紹介があった.以前，研設計を目的とし，このためには正日l頂序が互いに矛盾究部会 (SMO部会)における講演で、は動的ボロノイ図しない部品集合で負荷量最大のものを見つけるの応用をいろいろ聞けたが，今回はもう少し時間があ(GTフローライン構成問題) J と「ラインを構成するに値すればよいと思った.

る負荷量を持ち，使用機械数を最小とする部品部分集

第 3 発表者の東京大学阿部篤行氏は， I 空間的階層の合を求める(部品ファミリー構成問題) J の解法を提案

分析と最適化j と題して講演した.都市構造には空間した.逆流最小化問題と GT フローライン構成問題は的階層が見受けられ，そのパターンは経験的に六角形集合被服問題として定式化でき，切除平面法による最であるという話から始まった. 1 つの階層抽出方法「隣適解法と実際問題への応用結果が示きれた.

接した(ボロノイ図を用いる)都市より規模の大きい

第 3 セッション (22 日午後) :ォーかナイザー杉原厚吉氏(東京大学)，

I 計算幾何とその応用」では，最初ものをオーダの 1 つ上の都市として抽出，これらの中からきらにオーダの上の都市を抽出していく操作を都に理論的な 2 件の講演，後半に応用的な 2 件の講演が市が 1 つになるまで続ける」を紹介した.この抽出方行なわれた.

法を用いて，クリスターラの提唱した空間的階層に対第 1 講演は，東京大学の松井知己氏による「最小ノする 3 つの規則性の検証をシミュレーションを用いてId 次元ユー示し，また現実との比較がなされた.第 1 の規則性「都クリッド空間中の n 点集合の凸包中でノルム最小の点市の圏域は六角形である」を聞いていて， 1993年 SSORルム点問題とその周辺」であった.まず，を求める」という最小ノルム点問題の紹介に始まり，での豊橋技術科学大学の大津映二氏の講演を思い出し「この点集合と原点を分離する原点から最も遠い超平た.大津氏はサッカーボール状の炭素分子C 60 の存在を面を求める」最遠分離平面問題との関係を図を用いて最初に予想した方で，講演の中で「自然界には球面状わかりやすく説明した.次に最小ノルム点問題に対すのものは六角形といくつかの五角形で覆われているこ

1994 年 1 月号

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

53

とが多い j と松の木の表面や微生物の写真などを紹介

22 日午後 5 時過ぎ，実行委員長藤重悟氏(筑波大学)した.各面が六角形か五角形である非退化な多面体での閉会の挨拶をもって第 5 回 RAMP シンポジウムはは五角形がちょうど 12個含まれることがオイラーの公閉会した.副委員長の山本芳嗣氏以下実行委員会の式から導ける.平面と球面の違いだろう，自然は締麗方々および手伝いをした学生きんたちに対する感謝のだ.

辞を述べ，また来年は実行委員長石井博昭氏(大阪大本シンポジウムのトリは，筑波大学の岸本一男氏による rr 長さ」の測定とその周辺j であった.

日本国の学)により大阪工業大学を会場として開催きれることが知らされた.

海岸線の総延長が出版物によって異なる実例 (1991年版の朝日年鑑で、は 29751km ，読売年鑑別冊では 33889km)や，求長不可能なフラクタル曲線を示し，講演内容の要点を報告したつもりであるが，専門外

r長き」測定のところもあり講演者の意図に反するところがなけれの困難きをまず説いた.この解決策として氏と伊理正ばよいと願っている.また，ルポの依頼書には「貴台夫氏(中央大学)の提案した「実数p> 0 に対して p J<).の玉稿を頂戴いたしたく」とあったが，下の変動を鮒見した長き L (ρ) J を紹介した.これは，ない方に「来年は RAMP シンポジウムに参加してみょρ に関して単調非増加関数であること，求める曲線のうかな」と思われるような紹介が書けないのが我ながRAMP を知ら長きが求長可能なら L (0) が通常の長さに一致するこら悔しい.昨今，数理計画に関係するシンポジウムやと，測定誤差の理論上の限界を得られるなどの性質や研究会などの数が増えてきている.この分野が盛んに利点を示した.また，これの実用性を日本国の海岸線研究されている証拠として喜ばしいことであるが，こ上の 408832点のデータより計算した海岸線延長の結果のような会にすべて参加をする時間的余裕も金銭的余から示した.最後に，ブラウン運動への応用，デジタ裕もないのが現実である.これらの中から自分にとっル幾何への応用にも触れた.

r 長き」の測定の困難さとて有益なものを取捨選択していかなければならないというのは聞くまで考えもしなかったので，目から鱗が思うが，高い水準の講演内容が維持される限り RAMP落ちる患いがした.

はまさにお勧めのシンポジウムである.

正会員 5 ， 000 人へ向けて!!
111111111111111111111111111111111111111111111111111
11111111111
11111
1111111111
1

会員増強キャンペーンの展開
1
1
11
1111111
111
1
1111
111
111
1
111111111111111111111111111111111111111111111111111
1

創立40周年はもう間近かです. (1997年) 21世紀を目前に世の中は大きく変わりつつあり， OR学会の各分野におけるその使命もますます重要になるるのが，学会を支える会員の数であることは言うまでもありません.
この機会に会員倍増運動を展開いたしましょう.
会員 1 人が 1 人を推薦し，創立40周年は，倍増しものと思われます.
学会諸活動の活発化・活性化の根底，基盤にあ54(庶務幹事会)た構成メンバーでその記念日を祝いたいものです.

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

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