【研究分野】情報学基礎理論

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

【研究キーワード】

離散資源配分問題 / 離散最適化 / 離散凸解析 / 離散配分問題 / 離散凸関数 / 離散構造 / 情報基礎 / アルゴリズム

【研究成果の概要】

離散凸解析を武器としての複雑な制約をもつ離散資源配分問題の研究と現実問題へのフィードバックを目的とした研究課題ですが，設定した５つのテーマそれぞれについて理論的な研究成果を得ました．また，現実問題へのフィードバックに関しては，提案したアルゴリズムをソフトウエア化し，研究期間初年度末から現在に至るまで所属機関のおける学科分けという現実問題を解くために利用しています．

【研究の社会的意義】

離散資源配分問題は，学生の学科への配属等の現実問題と強い関係があります．現実的な離散資源配分問題は複雑な制約を有することが多く，これらに対する研究は学術的にも社会的にも意義のあるものです．本研究成果では，良い構造を有する離散凸解析を武器として，理論的な研究成果を得た一方で，複雑な制約を有する学科分け問題という現実問題の解決に理論的成果を応用した点であり，他の現実的な問題への拡大利用も可能であることから，その社会的意義は高いと思われます．

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

【研究期間】2016-04-01 - 2022-03-31

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

【研究分野】数理情報学

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

【研究キーワード】

離散凸関数 / 離散凸解析 / 離散DC関数 / 離散最適化 / アルゴリズム / DC関数

【研究成果の概要】

離散ＤＣ関数最小化問題に対して，解きやすい問題クラスの検出や精度保証付き近似アルゴリズムの構築を目指した．また，DC関数を構成するM凸関数，L凸関数自体の構造をより良く理解することを目的として，M凸関数およびL凸関数の最小化問題という，基本的な問題の再検討を行い，アルゴリズムの改良を行うと同時に，計算量の解析方法の改善を実現した．さらに，離散凸関数の制約なし最小化問題と離散DC関数最小化問題の中間に位置する問題についても調査し，これらの問題の構造を明らかにするとともに，その結果を利用して高速なアルゴリズムを提案した．

【研究の社会的意義】

本研究課題で得られた成果により，高速に解くことのできる離散最適化問題の新たな枠組みを提示できた．また，これまで高速なアルゴリズムが知られていなかった様々な離散最適化問題に対して高速なアルゴリズムを提供できたとともに，高速なアルゴリズムが存在していた問題に対しては，より高速なアルゴリズムを提供できた．これらの研究成果が直接，現実の問題に適用できるとは限らないが，現実の複雑な問題を高速に解くことを目指す際，本研究課題で得られたアルゴリズムの活用が期待される．

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

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

【配分額】4,680千円 (直接経費: 3,600千円、間接経費: 1,080千円)

【研究分野】情報学基礎

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

【研究キーワード】

整数計画問題 / 非線形関数 / アルゴリズム / 離散最適化 / 離散凸解析 / 非線形計画問題 / 近似アルゴリズム / 離散凸関数 / 組合せ最適化

【研究成果の概要】

本研究では，非線形な不等式制約の下で非線形関数を最大化するという整数計画問題に対し，解の精度および計算時間に関する理論的な保証を与える近似解法を開発することを目指した．本研究の主結果として，ナップサック制約の下で１つのM凹関数を最大化するという問題に対し，制約が複数個の場合でも，連続緩和アプローチを用いて任意の精度の近似解を多項式時間で求められることを示した．また，目的関数が２つのM凹関数の和の場合には，ラグランジュ緩和アプローチを用いて任意の精度の近似解が得られることを示した．

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

【研究期間】2012-04-01 - 2016-03-31

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

【研究分野】情報学基礎

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

【研究キーワード】

離散最適化 / 離散構造 / 離散凸解析 / 資源配分問題 / マッチング / 戦略的頑健性 / アルゴリズム / 配属問題 / 国際情報交換 / 国際研究者交流 / ハンガリー / 安定結婚 / 安定マッチング / 安定割当

【研究成果の概要】

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

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

【研究期間】2012-04-01 - 2017-03-31

【配分額】5,850千円 (直接経費: 4,500千円、間接経費: 1,350千円)

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

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

【研究キーワード】

組合せ最適化 / 非線形関数 / 整数計画 / 離散凸関数 / 近似解法 / アルゴリズム / マトロイド / 劣モジュラ関数 / 非線形計画 / 凸解析 / 凸関数 / 離散凸解析

【研究成果の概要】

整数計画問題とは,与えられた制約条件を満たす整数ベクトルの中から,与えられた目的関数を最小化(または最大化)する解を求める問題である.一般に整数計画問題は短時間で解くことが困難である,ということが理論的にも現実的にも知られている.とくに,目的関数と条件が非線形関数で与えられる非線形整数計画問題は,解くことが最も困難な整数計画のクラスである.本研究では,様々な非線形整数計画問題に対して,その良質な近似解を短時間で求めるアルゴリズムを提案した.

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

【研究期間】2006 - 2008

【配分額】3,760千円 (直接経費: 3,400千円、間接経費: 360千円)

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

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

【研究キーワード】

離散凸解析 / アルゴリズム / 数理経済学 / ゲーム理論

【研究成果の概要】

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

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

【研究期間】2003 - 2005

【配分額】3,400千円 (直接経費: 3,400千円)

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

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

【研究キーワード】

半正定値計画 / 離散凸解析 / アルゴリズム / 双向グラフ / パーフェクトグラフ

【研究成果の概要】

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

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

【研究期間】2001 - 2002

【配分額】2,400千円 (直接経費: 2,400千円)

【研究分野】工学基礎

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2000 - 2002

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