【研究分野】数理情報学

【研究領域課題番号】25280004 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 組合せ最適化 / 劣モジュラ関数 / 離散アルゴリズム / アルゴリズム / 劣モジュラ構造 / 数理計画

【研究成果の概要】

劣モジュラ的な離散構造に基づいて、離散最適化・組合せ最適化の理論とアルゴリズムの基礎研究を展開し、多くの研究成果を上げている。中でも、劣モジュラ構造を基礎とする離散凸関数の新たな理論を構築し、最近世界で注目される劣モジュラ的な関数(新たに導入した横断劣モジュラ関数、歪双劣モジュラ関数等）に関連する最大・最小定理を始め、離散最適化・組合せ最適化の理論と効率的アルゴリズムの基礎となる離散構造を解明した。さらに、非分割財の経済やゲーム論的配分の問題における劣モジュラ構造の有用性を明らかにした。

【研究の社会的意義】

大規模な離散最適化・組合せ最適化問題を厳密に、あるいは、近似的に解くための効率的アルゴリズムの構築に向けて、劣モジュラ的な離散構造の有効性を明らかにした。学術的な意義としては、離散最適化・組合せ最適化の理論と効率的アルゴリズムの基礎となる、離散凸関数の新たな理論構築や、新たな劣モジュラ的関数に関連する最大・最小定理の導出等であり、社会的意義としては、非分割財の経済やゲーム論的配分の問題における劣モジュラ構造の有用性の解明等である。

【研究種目】基盤研究(B)

【研究期間】2013-04-01 - 2019-03-31

【配分額】17,420千円 (直接経費: 13,400千円、間接経費: 4,020千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】22710139 (KAKENデータベースで見る）

【研究キーワード】

最適化 / 数理計画 / 時空間領域 / 施設配置問題 / 都市計画 / 都市計画・建築計画 / 交通工学・国土計画 / アルゴリズム / 数理最適化 / 動的モデル / 数量最適化

【研究成果の概要】

施設配置問題は,都市における様々な施設を対象空間にどのように配置すれば利用者や施設経営者にとって望ましいかを追求する問題であり,これまでに様々な研究がなされてきた.本研究では,施設配置問題に時間軸を導入し,時空間的な人の流れを所与とし,施設の配置の決定と同時に望ましいサービス提供時間帯も決定する新しいモデルを開発した.また,基本モデルのいくつかの拡張モデルを考案した.さらに,首都圏鉄道網を対象とし,実流動データを用いて,多くの人がアクセスし易いサービス提供方法の分析を行った.

【研究種目】若手研究(B)

【研究期間】2010 - 2011

【配分額】1,430千円 (直接経費: 1,100千円、間接経費: 330千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】21740060 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / 組合せ最適化 / 数理計画 / 離散凸関数 / 近似アルゴリズム / アルゴリズム / マトロイド / 劣モジュラ関数 / マトロスド

【研究成果の概要】

本研究では, 申請者が近年携わってきた離散凸解析の理論に基づき, 計算時間や解の精度の面で理論的な保証をもつアルゴリズムを構築することを目的とした. 3年間の間に様々な結果を得ることが出来たが, とくに, 複数のナップサック制約の下でのM凹関数の最大化問題に対して, 多項式時間近似スキームを構築することに成功した. また, 近傍システムという, 一般的な解集合の構造を明らかにするとともに, 近傍システムに関する分離凸最適化問題が多項式時間で解けることを示した.

【研究種目】若手研究(B)

【研究期間】2009 - 2011

【配分額】4,420千円 (直接経費: 3,400千円、間接経費: 1,020千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】20310088 (KAKENデータベースで見る）

【研究キーワード】

OR / 離散最適化 / アルゴリズム / 劣モジュラ関数 / 組合せ最適化 / 数理計画 / 細合せ最滴化

【研究成果の概要】

大規模離散最適化問題の有する劣モジュラ的な離散構造に注目し, 効率的なアルゴリズムの構築のために有効な離散構造を研究した.個別には,ネットワーク・フロー, マッチング,多品種フロー, 施設配置問題, 資源配分問題, グラフ連結度,通信網設計,待ち行列ネットワークに関わる離散構造,双対貪欲アルゴリズムに関わる離散構造(双対貪欲多面体, ゾノトープ) ,ホーン論理関数や安定マッチングの離散凸構造,などであり,個別の劣モジュラ的な離散構造の解明に基づき,それらの知見を横断的に総合する基礎理論の構築と高速アルゴリズムの開発を行った.

【研究種目】基盤研究(B)

【研究期間】2008 - 2012

【配分額】19,630千円 (直接経費: 15,100千円、間接経費: 4,530千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】17710126 (KAKENデータベースで見る）

【研究キーワード】

アルゴリズム / 数理計画 / 錐計画問題 / ロバスト

【研究成果の概要】

本研究では、超大規模な錐計画問題を実用的な計算資源でロバストに解くアルゴリズムの開発を目的としている。
2次錐制約を半正定値制約や非負制約と統一的に扱う枠組みを考案した。Iまた、ロバストな解法を実現するため、主双対内点法が破錠しないような計算スキームを提案し、プログラミング言語C++で実装した。その結果、錐計画問題を主双対内点法によって安定的に解くソフトウェアの開発に成功した。
超大規模な対称錐計画問題は、入力データの多くはゼロである。このような疎性を主双対内点法でより有効に利用するための前処理法を提案した。さらに、この前処理を高速に行う方法を実装した。これにより、問題の疎性の利用し、主双対内点法を効率よく実行することが可能となった。
最後に、同様の数理計画問題を解く他のソフトウェアとの比較実験を行うことにより、本研究の有効性を実証するができた.
これらの成果を専門分野の研究者に紹介し、学術交流を通じてその意義を明らかにするため、11月に行われたINFORMS (オペレーションズ・リサーチとマネジメントサイエンスのフォーラム)の年会にて研究課題の発表を行った。また、学術論文として論文誌に投稿する準備中である。
本研究により、主双対内点法などの数理計画法について詳しくない研究者でも、簡便に超大規模な錐計画問題を安定して解くことができるようになる。それは、構造最適化・システム制御・組合せ最適化・非凸計画・量子化学・統計・金融工学のような様々な工学分野における研究や開発に対し、非常に大きなサポートとなる。

【研究種目】若手研究(B)

【研究期間】2005 - 2007

【配分額】1,500千円 (直接経費: 1,500千円)

【研究分野】社会システム工学・安全システム

【研究領域課題番号】16310111 (KAKENデータベースで見る）

【研究キーワード】

離散最適化 / アルゴリズム / 劣モジュラ関数 / 組合せ最適化 / 数理計画

【研究成果の概要】

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

【研究種目】基盤研究(B)

【研究期間】2004 - 2007

【配分額】16,320千円 (直接経費: 15,600千円、間接経費: 720千円)

【研究分野】工学基礎

【研究領域課題番号】15360043 (KAKENデータベースで見る）

【研究キーワード】

凸解析 / 凸関数 / 凸集合 / マトロイド / 離散最適化 / 数理計画 / 非線形計画 / ネットワークフロー / 双対性 / 劣モジュラ関数 / アルゴリズム / 離散凸関数 / 組合せ最適化

【研究成果の概要】

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

【研究種目】基盤研究(B)

【研究期間】2003 - 2005

【配分額】10,200千円 (直接経費: 10,200千円)

【研究分野】工学基礎

【研究領域課題番号】12450040 (KAKENデータベースで見る）

【研究キーワード】

凸解析 / 凸関数 / 凸集合 / マトロイド / 離散最適化 / 数理計画 / 非線形計画 / ネットワークフロー / 離散凸解析 / 数理経済学 / 不可分財市場 / 競争均衡 / M凸関数最小化 / アルゴリズム

【研究成果の概要】

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

【研究種目】基盤研究(B)

【研究期間】2000 - 2002

【配分額】7,600千円 (直接経費: 7,600千円)