共同研究・競争的資金等の研究課題

本研究課題の主題,研究代表者が1990年代の中頃から提唱している離散凸解析の応用開拓である.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている. (1)数理経済学において,離散凸解析の応用研究として3つの成果を上げた.第1の成果は,複数の不可分財と貨幣からなる市場において競争均衡が存在するための十分条件を与えるなど,理論構築を行なった.第2の成果は,離散凸解析のおいて中心的役割をなすM凸関数の新しい特徴付けを与えた.この特徴付けは,数理経済学では良く知られた粗代替性や単改良性を用いたものである.第3の成果は,先に述べた不可分財と貨幣からなる市場において,競争均衡を求めるアルゴリズムの開発である.このアルゴリズムは,離散凸解析における最適化問題の一つであるM凸劣モジュラ流問題を利用したもので,多項式時間で均衡の存在判定を行ない,均衡が存在する場合はその一つを求める. (2)離散凸解析において中心的な役割を果たすM凸関数の最小化問題に対する近接定理を示すとともに,高速なアルゴリズムを開発した. (3)工学システムのもつ組合せ構造を離散凸解析の立場から論じた.特に,電気回路や制御システムの取扱いを目的として,混合多項式行列を考察し,効率的な組合せ緩和アルゴリズムを提案した. (4)オペレーションズ・リサーチの諸問題に対し,離散凸解析の結果を利用した解法が適用可能か否かを検証した.その結果を踏まえて,ネットワークデザインや最大カット問題に対して効率的な解法を提案した.

まず,数理経済学における離散凸関数の応用について研究を進めた.不可分な財を含む経済均衡モデルにおいて,供給者の費用関数がM凸関数かつ消費者の効用関数がM凹関数の場合に競争均衡が存在することが,研究代表者らの昨年度までの研究において証明されていた.本年度はさらにこの研究を進めて,競争均衡を実際に求める方法について検討し,多項式時間で競争均衡が求められることを示した.具体的には,競争均衡を求める問題を元にしてM凸劣モジュラ流問題をつくり,これを既存の多項式時間アルゴリズムで解いて得られた出力を適切に変換することで競争均衡が得られる,という手法である.これはM凸劣モジュラ流問題の応用としても興味深い結果である. 次に,最適配分問題に対する効率的な解法の研究を行った.生産ラインでのバッファ配分や労働力・資源の配分など,生産システム設計の際に頻繁に現れる最適配分問題は,離散準凸性の理論を適用しやすい問題の一つである.離散準凸関数の理論を踏まえて,現実に現れる最適配分問題を定式化し,その離散構造を明らかにすると共に効率的な解法を提案した,具体的には,劣モジュラ制約の元での最適配分問題に対するHochbaumの高速解法がなぜうまく働くのかを離散凸性の視点から検討し,その結果を元にM凸関数に対する高速な最小化アルゴリズムを提案した. また,dial-a-ride transit system, isotone regressionなどに応用をもつ,双対最小費用流問題について研究を進めた.この問題が準L凸関数最小化問題の特殊ケースである,という事実を踏まえ,既存の解法を見直し,準L凸関数に対する解法へと拡張した.

本研究課題の目的は,経済学,システム工学,オペレーションズ・リサーチ,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立することにある.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている. (1)離散双対性に関わる最適化問題,とくに,M凸関数を目的関数に含む劣モジュラ流問題に対して,容量スケーリング手法に基づくアルゴリズムを提案した.一般のM凸劣モジュラ流問題に対して,このアルゴリズムはこれまでで最良の時間計算量をもつ. (2)離散凸解析の枠組みとは独立に研究されてきたマルチモジュラー性という概念が,実質的にL凸性と等価な概念であることを示した.この結果をふまえ,整数格子点上で定義されたマルチモジュラー関数に対する離散分離定理などの諸性質を導いた. (3)2次のM凸関数と木距離の間の密接な関係を示した.より具体的には,2次のM凸関数のヘッセ行列は実質的に木距離行列(にマイナスを掛けたもの)であることを証明した. (4)整凸集合上の離散不動点定理を与えた.これは,数理経済学における一般均衡理論ならびに非協力ゲームへの応用をもつ. (5)M凸関数の概念が,数理経済学で良く知られた粗代替性や単改良性と等価であることを明らかにした. (6)離散凸解析の数理経済学への応用として,複数の不可分財と貨幣からなる市場において競争均衡が存在するための条件を与えるなどの理論構築を行うとともに,競争均衡を求めるアルゴリズムをM凸劣モジュラ流問題の枠組みを利用して開発した.

工学や社会科学の諸分野における最適化の理論と応用を「離散凸パラダイム」に よって統合する研究を行った．離散凸解析の理論と応用を， 連続・離散軸，凸・非凸軸，分野横断軸，の３つの観点から整理することによって，個々の数 理的技法や応用諸問題の相互関係を明確にし，数理の深化，応用の開拓，ソフト ウェアの整備の３つの観点から研究を行い，新たな展開を達成した．とくに，数理の深化については，Ｌ凸関数最小化アルゴリズムの詳細な解析やＤＣ計画の枠組みの提示などの成果をあげた．

経済学,システム工学,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立し,それを広範囲の応用分野に浸透させる研究を行った.「離散凸パラダイム」の横糸を成す,構造定理やアルゴリズムを代表とする離散関数に関する数理の研究と,縦糸を成す,諸応用分野における具体的な諸問題に対する研究を行った.

本研究プロジェクトでは、我が国の持続可能な発展のために、計算機科学とミクロ経済学の技術を統合／発展させ、経済的、社会的、環境的な観点からの要求をバランスした、希少な資源の望ましい配分を実現するメカニズムの設計理論を構築することを目的としている。具体的には、資源配分メカニズムの設計、解析、表現技術に関して研究を推進し、特に、制約付き両方向マッチングにおけるメカニズム設計、ノイズのある繰り返しゲームの均衡解析、協力ゲームに関する表現技術に関して顕著な成果が得られている（査読付き国際会議87件、国際論文誌74件、国内論文誌11件、著書8件、教科書の執筆4件、招待講演40件）。

学生の学科への配属や研修医の病院への配属の決定という離散資源配分問題は実用性の高い重要な問題である．グラフ構造や離散凸解析などの離散構造を導入し，安定マッチングモデルを一般化して適用範囲の広い離散資源配分問題を構築し，その解析を行うことを目的とした． 包括的な離散資源配分問題に対する戦略的頑健性をもつメカニズムの構築，安定マッチングモデル（2部グラフ上のモデル）の一般の有向グラフへの拡張等の研究を実施し，雑誌論文6編，投稿中の論文2編，執筆中論文2編の成果を得た．

本研究課題では、「M2凸関数最小化に対する多項式時間の開発」、「連続M凸関数最小化と連続L凸関数最小化に対する解法の研究」、「離散凸解析と効率的に解ける凸関数最小化問題との関連性の解明」という3つの研究目的を設定した。 第1の目的に関しては、研究分担者である室田と岩田、森口が、等価な問題であるM凸劣モジュラ流問題に対する多項式時間解法を開発した。 第2の目的については、研究を継続中である。 第3の目的に対しては、関連した幾つかの研究成果を得た。大きく分けて2つの流れができた。 第1の流れは、マッチングモデルと呼ばれる数理経済モデルにM凹評価関数を導入することで、既存の多くのモデルを含む幾つかのモデルを提案した(主に研究代表者の田村と分担者の藤重が担当)。さらにM2凸関数最小化アルゴリズムのアイデアを応用することで、これらのモデルに安定マッチングが常に存在することを構成的に示した。また、この構成法は擬似多項式時間アルゴリズムとなっており、実効定義域が0-1超立方体に含まれるとする多くの既存のモデルの状況では多項式時間アルゴリズムとなる。また、田村とFarooqはM凸関数の持つ数理経済的特性についての研究も付随して行った。 第2の流れとして、室田はジャンプシステム上にM凸性という概念を拡張し、その最小性基準を示し、最小化アルゴリズムを提案した。ジャンプシステム上のM凸関数最小化やその拡張は今後も引き続き研究するべき課題である。 その他として、田村はM凸関数最小化問題に対し、座標軸ごとにスケーリング係数を独立して持たせるという今までにないアイデアを用いて多項式時間解法を開発した。

研究実績は以下のとおり. 本研究課題では、半正定値計画問題と離散凸解析に関連したいくつかの結果を得た。これらの結果は、International Symposium on Algorithms and Computation, Conference on Integer Programming and Combinatorial Optimizationなどの国際会議で成果発表をするとともに学術雑誌に投稿し、その内の幾つかは掲載あるいは掲載予定となった。ここでは、これらの結果の内7つについて概要を説明する。 1)藤江と田村は、最大重み安定集合問題の凸緩和の理論を一般化安定集合問題へと拡張し、さらに最大重み安定集合問題での幾つかの結果に対する簡単な証明を与えた。 2)室田らは、群論的対称性を持つ半正定値計画問題に対して内点法が求める解も群論的対称性を持つことを示した。 3)室田らは、行列の疎性を生かした半正定値計画問題に対する技法を提案した。 4)室田と田村は、M凸劣モジュラ流問題を利用することで、ある種の経済モデルの競争均衡の存在判定を効率的に行なうアルゴリズムを構築した。 5)田村は、M凸関数最小化問題に対する新たなスケーリング技法とこれを用いた効率的なアルゴリズムを構築した。 6)田村と室田は、M2凸関数、L2凸関数といった各種の離散凸関数に対する近接定理を示した。 7)田村は2つのL凸関数の合成和として定義されるL2凸関数に対して、合成和を等号で達成するような新たなL凸関数の合成和が存在することを示した。この性質を用いることで、L2凸関数に関する近接性などの諸性質が容易に証明できる。

組合せ最適化問題の中でも最も研究されているものの一つが無向グラフ上の安定集合問題である。一般にこの問題はNP完全クラスに属し、多項式時間解法はおそらく存在しないであろう。しかし、パーフェクトグラフ、クローフリーグラフなどの幾つかのグラフクラスに対しては多項式時間解法が存在する。特にパーフェクトグラフに対する多項式時間解法の特徴は、安定集合問題がその半正定値緩和問題と一致するところにある。またGrotschel-Lovasz-Schrijverは、その逆命題も成立することを証明した。すなわち、安定集合問題とその半正定値緩和問題が一致するための必要十分条件が無向グラフがパーフェクトであることを示した。 本年度の研究成果は、このGrotschel-Lovaz-Schrijverの結果の別証明を与えたことと、この結果を一般化安定集合問題へと拡張したという2つである。彼らの証明では、無向グラフの補グラフとアンチブロッカーという概念を用いている。我々は、半正定値計画問題に対する2次計画問題表現を利用することで、補グラフなどの概念を導入しない別証明を与えた。 一方、一般化安定集合問題は安定集合問題を双向グラフ上へと自然な形で拡張したものであるが、双向グラフに対しては補グラフという概念がない。そのため「双向グラフがパーフェクト」と「一般化安定集合問題とその半正定値緩和が一致」という命題が同値であることを示すには、彼らの証明法を拡張することは困難であるが、補グラフという概念を用いない我々の証明法は、拡張された命題の同値性証明まで適用できるものであった。 これらの結果は国際会議において発表し、論文としてまとめ学術雑誌に投稿した。

「双向グラフに対する最適化問題とその解法の研究」という目的で昨年度に引き続き本年度は研究を進めて来た。 昨年度の研究成果“The generalized stable set problem for claw-free bidirected graphs"について、1998年の6月に開催された国際会議Integer Programming and Combinatorial Optimization(査読付き)にて口頭発表を行った。その際の旅費として本年度の研究費を用いた。また本論文はこの会議のプロシーディングスに掲載された。 本年度の研究成果は“A linear time algorthm for the generalized stable set problem on triangulated bidirected graphs"としてまとめ、Journal of the Operations Research Society of Japanに投稿し、1999年3月17〜19日に京都大学で開催されるJapan-Hungarian Symposium on Discrete Mathematics and Its Applicationsにて口頭発表する。また、この成果については来年度開催される国内外の学術会議、研究会においても口頭発表を行う予定である。この成果は本年度計画していた「一般の双向グラフについて一般化安定集合問題に対する効率的な解放の開発」を含むものである。もう一つの計画「平面上の与えられた点集合の最小重み三角形分割問題へのこの解法の応用」については現在研究中でありまだ成果を得るに至っていない。 また開発した解法については、当研究費によって購入した計算機を用いてその実用面での有効性の検証も行った。

今年度は以下の3つ (a)「0-1多面体の構造解析」 (b)「重み付きグラフにおける全域木の重み順全列挙アルゴリズムの開発」 (c)アルゴリズムの平均的な振る舞いの評価に関する研究」 を研究目的とした。 (a)に関しては、グラフの最大安定集合問題、グラフの辺(または頂点)の彩色問題に関連した0-1多面体の特殊な面がある半順序集合のイデアル全体から作られる0-1多面体と合同であるという構造を明らかにした。また、この構造を利用し、最大安定集合問題などに対する発見的な方法を提案した。この成果は論文としてまとめ、アメリカ合衆国のミシガン大学で開催された第15回数理計画国際シンポジウム(15th International Symposium on Mathematical Programming)や福岡で開催された第3回アジア太平洋地区オペレーションズ・リサーチ会議(The Thrid Conference of the Association of Asian-Pacific Operational Societies within IFORS)など国内外の会議において口頭発表し、国際的論文誌であるMathematical Programmingに掲載されることになった。 (b)に関しては、重み順ではないがグラフの全域木を列挙する時間計算量の意味でも空間計算量の意味でも最適なアルゴリズムを開発した。既存のアルゴリズムで二つの計算量の意味で最適なものはなく、このアルゴリズムが初めてのものである。この研究成果は、論文としてまとめ、第15回数理計画国際シンポジウムや第3回アジア太平洋地区オペレーションズ・リサーチ会議など国内外の会議において口頭発表し、国際的な論文誌であるSIAM Journal on Computingに投稿した。 研究目的(c)に関しては、今年度中には論文として発表できるような成果は残念ながら得られなかったが、今後も継続して研究をしていく。 本年度は、補助金によって設備としてX端末を購入し、現有設備であるワークステーション(平成4年度科研費により購入)と接続し、論文や発表原稿・OHPの作成、実験結果のグラフィック表示など有効利用した。