研究者詳細 - 田村　明久

競争的研究費の研究課題 - 田村　明久

分割表示 19 件中 1 - 19 件目／全件表示 >>

2020年04月

2023年03月

科学研究費助成事業, 横尾真, 神取道宏, 田村明久, 関口格, 牧野和久, 川越敏司, 鹿島久嗣, 基盤研究(A), 補助金, 未設定

本研究では，種々のインセンティブ／誘因に対する人々の反応を解明すると共に，人々に適切なインセンティブを与えることにより，個人の目的と社会の目的を適切に調和させて持続可能な発展を可能とする社会制度の設計に関する「インセンティブ設計科学」と名付けた新しい文理融合型の学問領域を創出する．具体的には，中核となる人工知能／最適化技術に社会科学の知見を統合し，インセンティブ設計科学に関する理論構築，被験者実験による評価を行う．さらに，学校選択制，研修医マッチング，公共事業入札，周波数オークションなどの応用分野において，政策提言とソフトウェアライブラリの開発準備，webアプリケーションの提供を行う．
2022年度および繰越の2023年度を合わせて18件の査読付き論文出版と，16件の学会発表 (内3件が招待講演) を行った．マッチンググループでは，両方向マッチングにおいて，学校の定員が外生的に与えられるのではなく，資源割当によって内生的に与えられるモデルを提案し，公平性と効率性を高いレベルで両立可能な耐戦略的なメカニズムを設計した．本成果は人工知能分野のトップジャーナルであるArtificial Intelligence に採録されている．オークショングループでは，ソーシャルネットワークを通じて，メカニズムの参加者を募り，その際に本来はライバルとなり得る他の参加者をメカニズムに招待する誘因を与え，耐戦略性を満たす交換メカニズムを設計した．本成果はエージェント分野の最難関の国際会議である Int. Conf. on Autonomous Agents and Multiagnt Systems (AAMAS) において論文が採録されている．人工知能／最適化グループでは，最適化問題を解く際に敵対者が存在し，解の一部を改竄する可能性がある状況で，改竄の影響を最小限に留めることを目的とする，敵対者が存在する場合のMaxSAT問題についての理論的検討を行った．本成果は人工知能分野の難関国際会議であるPacific Rim International Conference on Artificial Intelligence (PRICAI)に採録されている．行動／実験経済学グループでは，両方向マッチングにおいて参加者が複数のタイプに分割され，タイプごとの上下限制約が存在する場合のメカニズムについて実験的考察を行った．
令和4年度が最終年度であるため、記入しない。
令和4年度が最終年度であるため、記入しない。

マーケットデザインの実践的理論の構築

2017年04月

2020年03月

九州大学, 横尾真、神取道宏, 櫻井祐子, 船木由喜彦, 田村明久, 東藤大樹, 安田洋祐, 関口格, 岩崎敦, 基盤研究(A), 補助金, 研究分担者

平成29年度は主に，(a) TTCメカニズムの一般化，(b) 一般化受入保留メカニズムの代替メカニズムの提案，(c) 繰返しオークションにおける協調行動の解析，および (d) 均衡解析プログラムの拡張の4つの課題に関して研究を推進した．本年度の成果は，招待講演3件，論文出版10件，国際会議発表19件，および国際共同研究2件に上る．
課題 (a) では，TTC の拡張に成功し，初期保有がある環境において下限制約を満足するマッチングメカニズムを提案した．提案メカニズムは耐戦略性とパレート効率性を厳密な意味で満足する一方で，既存のメカニズムの単純な拡張と比較すると，期待値的により公平なマッチングを保証する．本研究成果は，人工知能分野で最も権威ある論文誌である Artificial Intelligence より出版されている．また，国際共同研究として複数の初期保有があるケースへのTTCの拡張を行い，その成果が国際論文誌 Journal of Artificial Intelligence Research に採択されている．
課題 (b) では，割当数の比率に関する制約を新たに考案し，一般化受入保留メカニズムを拡張することによって，この制約の下で公平なマッチングを保証するメカニズムを設計した．本研究成果は，エージェント分野で最も権威ある国際会議であるAAMAS-2018にて報告予定である．さらに，割当制約の一般化についても，計画を前倒して検討を開始しており，既にいくつかの成果を得ている．
課題 (c) および (d) では，均衡検証プログラムを，他者の行動の（不完全な）観測の構造がサイクルを構成するケースに対して拡張し，新たな均衡戦略の発見に成功した．本研究成果は国際ワークショップ AGT-2017 にて報告し，フィードバックを経て現在英文論文誌への投稿を準備中である．
各研究課題について，計画した内容を順調に達成できた．また，課題 (a) では副次的な成果として，TTC の異なる拡張に成功し，その成果が人工知能分野の一流論文誌である JAIR に採択されるなど，計画以上に進展している．さらに課題 (b) では，予想以上に順調に研究が進んだことから，計画を前倒しし，平成30年度に予定していた研究を既に開始している．特に，割当制約の一般化について，既にいくつかの結果を得ており，こちらも計画以上に進展している．
平成30年度は，平成29年度の研究成果を拡張・一般化するとともに，割当制約の一般化（担当：マッチング理論班・検証班），三角取引の均衡解析（担当：設計班・オークション理論班），離散構造上の社会選択（担当：設計班・検証班・マッチング理論班）の3つの研究項目に取り組む．設計したメカニズムは，アルゴリズムとして定式化し，ソースコードを公開する．得られた研究成果は，学術論文として，計算機科学・経済学分野の論文誌や，AAMAS/AAAI/IJCAI などの国際会議録より出版し，関連研究コミュニティに発信する．メカニズムの設計が計画どおりに進まない場合には，既存の様々なメカニズムの評価を重点的に行う．特に，検証班を中心とする被験者実験によって，現行の制度と既存のメカニズムにおける人間の振舞いの違いを洗い出し，ゲーム理論の均衡概念の実問題・各事例における信頼性を詳細に議論する．また，既存メカニズムの実行時間を計算複雑性の理論に基づいて明らかにし，大規模な問題への適用を可能にする近似アルゴリズムの提案を行う．

複雑な制約下での離散資源配分問題：離散凸解析を武器としての探求

2016年04月

2020年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久、野寺隆, 基盤研究(C), 補助金, 研究代表者

本研究課題は，離散凸解析という良い離散構造をもつ枠組みを武器として，離散的な配分において，プレイヤーが複数存在する状況下で，プレイヤー全体やその部分集合が設定する複雑な制約を満たしつつ，個々のプレイヤーが満足する配分とは何かという解概念とそれを求めるアルゴリズムを研究し，現実問題へフィードバックすることを目的としている.
平成29年度については，武器である離散凸解析の強化という意味で，昨年度提案した整凸関数のサブクラス（離散中点凸関数）についてさらに研究を進め，2近傍定理とよぶ性質を明らかにし，離散中点凸関数に関する最小化アルゴリズムを構築した．昨年度示したスケーリングに関して閉じている性質，近接定理と合わせて論文としてまとめ学術雑誌に投稿した．また，研究集会でもこの成果を発表した．
またTTC（トップトレーディングサイクルメカニズム）に離散凸解析を導入したメカニズムを開発した研究成果が査読付き国際会議であるThe 7th International COnference on Autonomous Agents and Multiagent Systems に採択された．
学術雑誌に投稿した2編の論文「学生にグループ分けのある学科配属問題 - 離散凸解析の適用例」と「Scaling, proximity, and optimization of integrally convex functions」がそれぞれ掲載または掲載受理となった．また前者の研究において作成したプログラムが平成29年度にも利用され，現実へのフィードバックという意味においても貢献した．
学術雑誌に投稿した論文については掲載または掲載受理となり，離散凸解析の強化という意味で取り組んだ研究も最小化アルゴリズム構築まで至り，学術雑誌に投稿した．現実へのフィードバックも継続中であり，おおむね順調に進展している．
平成30年度以降の当初予定の研究（テーマ1c）「3つのM#凹関数を用いたモデルに対する完全なアルゴリズムの構築」，(テーマ1d)「M#凹関数を用いたモデルに対する代替性への拡張」，（テーマ3）「複雑な制約下での戦略的頑健性をもつアルゴリズム設計」を推進するとともに，昨年度から取り組んだ「離散凸解析の強化」についても（テーマ4）「他の離散資源配分問題への適用」を念頭に研究を進める．

持続可能な発展のための資源配分メカニズム設計理論の構築

2012年05月

2017年03月

九州大学, 横尾真、神取道宏, 田村明久, 船木由喜彦, 関口格, 坂井豊貴, 平山勝敏, 尾山大輔, 安田洋祐, 岡本吉央, 岩崎敦, 川崎雄二郎, 小野廣隆, 櫻井祐子, 東藤大樹, 上田俊, 伊藤孝行, 小島武仁, 小原一郎, 基盤研究(S), 補助金, 研究分担者

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

離散構造の導入による離散資源配分問題の深化

2012年04月

2015年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久、太田克弘，小田芳彰，南美穂子, 基盤研究(B), 補助金, 研究代表者

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

離散凸パラダイムによる最適化統一理論

2009年04月

2015年03月

東京大学, 室田一雄、田村明久, 岩田覚, 塩浦昭義, 森口聡子, 垣村尚徳, 小林佑輔, 土村展之, 基盤研究(B), 補助金, 研究分担者

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

離散凸パラダイムの深化と拡大

2006年

2008年

東京大学, 室田一雄、田村明久, 岩田覚, 土村展之, 森口聡子, 塩浦昭義, 基盤研究(B), 補助金, 研究代表者

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

離散凸解析を用いた数理経済モデル

2005年04月

2006年03月

慶応工学会, 研究援助費, 田村　明久, 補助金, 研究代表者

大規模離散最適化問題の劣モジュラ的構造に基づく解析と高速アルゴリズム開発

2004年

2007年

京都大学, 藤重悟、田村明久, 牧野和久, 平井広志, 基盤研究(B), 補助金, 研究分担者

平成16年度〜19年度に亘る本研究において,劣モジュラ的な新しい構造の発見,知見及び新しい効率的なアルゴリズムの開発などの多くの成果が得られた.主要な成果としては,以下のものが挙げられる.
1.離散凹関数と上下限付き手付を導入することにより,安定結婚モデルや割当モデルの統一モデルを提案し,さらにはこのモデルが常に安定な解を持つことを構成的に示した.この統一モデルは既存の多くのモデルを包含するものであり,既存のモデルの有する離散構造の本質を明らかにした.
2.木構造ネットワークにおける動的フローと施設配置問題を複合した1-センター問題の動的フロー版として考えられる問題に対して,動的に構造変更が可能な平衡2分木である区間木を用いた高速アルゴリズムを導出した.
3.劣モジュラ関数を一般化した双劣モジュラ関数を最小化する多項式時間アルゴリズムを求め,さらに,その強多項式時間アルゴリズムを初めて構築した.
4.木構造ネットワークに対する単調なmin-max型連結分割問題の初めての多項式時間アルゴリズムを開発した.また,単調でない場合のmin-max型連結分割問題,min-sum型連結分割問題は,NP困難であることを示した.
5.グラフ上の半教師付き学習のための学習機械「電気回路判別器」を提案した.この判別器は非線形電気回路理論に基づいて構成され,データセットを電位の符号によって分類するものである.
6.ネットワーク設計問題として広く研究されているソース配置問題や外部ネットワーク問題などの自然な拡張として最小横断問題を考察し,ある種の劣モジュラ的な条件の下での最小横断問題に対する多項式時間アルゴリズムを開発した.また,このアルゴリズムを用いることで無向ネットワークにおける外部ネットワーク問題も効率的に解けることを示した.

離散凸解析におけるアルゴリズムの研究

2003年04月

2005年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久、藤重悟，室田一雄，太田克弘, 基盤研究(C), 補助金, 研究代表者

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

離散凸パラダイムの確立

2003年

2005年

東京大学, 室田一雄、田村明久, 岩田覚, 土村展之, 塩浦昭義, 松浦史郎, 基盤研究(B), 補助金, 研究分担者

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

半正定値計画の組合せ最適化への応用と解法の研究

2001年04月

2002年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久、降旗大介，藤江哲也，室田一雄，大浦拓也, 基盤研究(C), 補助金, 研究代表者

研究実績は以下のとおり.
本研究課題では、半正定値計画問題と離散凸解析に関連したいくつかの結果を得た。これらの結果は、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凸関数に関する近接性などの諸性質が容易に証明できる。

離散最適化における準凸性の理論の構築と社会工学への応用

2001年

2003年

京都大学, 室田一雄、塩浦昭義, 田村明久, 萌芽研究, 補助金, 研究分担者

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

大規模離散最適化問題に対する劣モジュラ的構造に基づく高速アルゴリズムの基礎研究

2001年

2003年

大阪大学, 藤重悟、田村明久, 高畑貴志, 牧野和久, 基盤研究(B), 補助金, 研究分担者

社会システムや産業活動に関係して現れる生産計画,環境計画,最適配送計画,スケジューリング,最適投資などを始めとする重要な問題の多くは,大規模かつ離散構造を有するシステムの最適化問題として捉えられる.本研究では,離散最適化問題の有用な構造的性質の抽出,および,その性質に基づいた高速アルゴリズム開発に主眼をおき,最適化分野における基礎理論の構築を試み,研究に取り組んだ.活発な研究活動の結果,新しい離散構造の発見や新しい効率的なアルゴリズムの開発などの多くの成果を得た.主要な成果としては,以下のものが挙げられる.
1.ネットワークのカット関数の劣モジーラ性に基づき,フロー要求条件を満足する供給施設の最適配置問題の効率的アルゴリズムを示した.
2.新しい最大2部マッチングアルゴリズム及び最大隣接順序に基づく新しい最大フローアルゴリズムを提案した.
3.劣モジュラ関数最小化のためのメンバシップ・オラクルに基づく0(n^2)アルゴリズムを提案し,劣モジュラ関数最小化問題への新しいアプローチを示した.
4.経済学における祖代替性と離散凹性の等価性を明らかにし,離散凹効用関数を用いてGale-Shapleyの安定マッチングの概念を拡張し,その安定解の存在を構成的に示した。
5.劣モジュラ構造の基本である基多面体の概念を一般化した複基多面体の概念を創出し,劣モジュラ構造の新しい枠組みを提示した.
6.単調線形システムの極小整数解を列挙する逐次擬多項式時間アルゴリズムを示した.
7.極大頻出集合の列挙が計算量的に難しいこと,ならびに,極小非頻出集合列挙が多項式時間で可能であることを示した.
8.ホーン理論とqホーン理論に対する関数従属性が効率よく求められることを示した.
9.単調論理関数の非双対性判定がo(log n)の推定ビットで可能であることを示した.また,様々な部分クラスの双対化問題を多項式時間で解くことが可能であることを示した.
10.データ解析手法として,データの本質を表す属性集合を求めるアルゴリズムを提案した.また,不完全なデータを説明する問題への拡張に対して,不完全性の度合いを考慮した4つの拡張を提案し,構造的性質,ならびに,計算量的性質を明らかにした.

離散凸解析の応用開拓の研究

2000年

2002年

京都大学, 室田一雄、田村明久, 松浦史郎, 松井知己, 降旗大介, 塩浦昭義, 基盤研究(B), 補助金, 研究分担者

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

双向グラフに対する最適化問題とその応用

1999年04月

2000年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久, 奨励研究(A), 補助金, 研究代表者

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

離散凸解析を軸とする離散最適化アルゴリズム

1998年

2000年

京都大学, 室田一雄、田村明久, 降旗大介, 塩浦昭義, 藤江哲也, 特定領域研究(B), 補助金, 研究分担者

非線形最適化の分野では,凸解析がその理論的なコアとなっている.一方,離散最適化の分野では,このような統一的な視点は存在しない.しかし,マトロイド的構造が良い性質と認知されている.「離散凸解析」は,連続変数に関する最適化と離散変数に関する最適化を統一的視点から捉える試みとして,研究代表者が提唱した理論体系であり,凸解析の理論とマトロイド理論の両者を結ぶ枠組みである.
現実問題として現れる離散最適化問題は,マトロイド的な構造をもつものばかりではないので,分枝限定法のような列挙型の算法や,近似算法などを利用することになる.どのようなアプローチにおいても,問題特有の離散構造の中から扱いやすい部分をうまく抽出することが肝要である.例えば,一般の離散最適化問題を解く際に,ネットワーク的な構造を部分問題として抽出する手法は多くの場合に有効である.
本研究の基本的なアイディアは,一般の離散最適化問題を解くために,離散凸解析で扱える問題を部分問題(子問題)として抽出しようというものである.本研究グループではこのアイディアに基づき,一般の離散最適化問題に対する効率的な解法の構築に取り組んだ.本研究グループの研究活動の成果として、以下のようなものが挙げられる:
●離散凸解析の枠組みにおいて中心的な役割を果たすM凸関数とL凸関数という概念の諸性質を示した。
●M凸関数の最小化問題に対する効率的な算法を提案した。
●整数格子点上で定義されているM凸/L凸関数の概念を、実数空間上の関数へと拡張した。
●M凸/L凸関数の定義を緩和することにより、準M凸/準L凸関数の概念を提案した。
●離散凸解析の経済均衡への応用について粗代替性とM凸性の同値性などの結果を得た。

双向グラフに対する最適化問題とその解法の研究

1997年04月

1998年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久, 奨励研究(A), 補助金, 研究代表者

「双向グラフに対する最適化問題とその解法の研究」という目的で昨年度に引き続き本年度は研究を進めて来た。
昨年度の研究成果“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にて口頭発表する。また、この成果については来年度開催される国内外の学術会議、研究会においても口頭発表を行う予定である。この成果は本年度計画していた「一般の双向グラフについて一般化安定集合問題に対する効率的な解放の開発」を含むものである。もう一つの計画「平面上の与えられた点集合の最小重み三角形分割問題へのこの解法の応用」については現在研究中でありまだ成果を得るに至っていない。
また開発した解法については、当研究費によって購入した計算機を用いてその実用面での有効性の検証も行った。

構造解析を基にした組合せ最適化アルゴリズムの効率化に関する研究

1994年04月

1995年03月

文部科学省・日本学術振興会, 科学研究費助成事業, 田村　明久, 奨励研究(A), 補助金, 研究代表者

今年度は以下の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の作成、実験結果のグラフィック表示など有効利用した。

　前のページ - 次のページ　

田村 明久

競争的研究費の研究課題 - 田村 明久

田村　明久

競争的研究費の研究課題 - 田村　明久