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

【研究領域課題番号】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千円)

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

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2009 - 2011

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

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

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2006 - 2008

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

【研究分野】工学基礎

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

【研究キーワード】

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

【研究成果の概要】

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

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

【研究期間】2003 - 2005

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

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

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

【研究キーワード】

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

【研究成果の概要】

本研究の目的は,組合せ凸解析の理論に基づいて,生産システム設計に現れる最適化問題の組合せ構造を明確にすると共に,最適な生産システムを設計するための実用的な解法を構築することである.この目的を実現するため,本年度は以下の研究を行った.
・スケーリング技法によるM凸関数最小化アルゴリズムの研究.M凸関数の最小化問題に対しては,最急降下法や領域縮小法が提案されているが,本研究においては,組合せ最適化のアルゴリズムにおいて基本的な技法であるスケーリング技法をM凸関数最小化に用いる可能性を研究した.一般にM凸関数はスケーリングに関して閉じていないが,ツリー型M凸関数や2次のM凸関数などのクラスのM凸関数がスケーリングに関して閉じていることを示すとともに,スケーリング技法と最急降下法とを組み合わせた効率的な算法を提案した.
・M凸関数の運搬経路問題への応用.時間枠制約つき運搬経路問題とは,各顧客への訪問時間枠制約をなるべく満たし,かつ運搬費用を最小にする経路及びスケジュールを求める問題である.経路決定とスケジューリングを分離するタイプのヒューリスティックにおいて,最適なスケジュールを求める問題がツリー型M凸関数の最小化問題として定式化できることを示した.
・2次のM凸関数・L凸関数の特徴付け.一般に2次の凸関数は半正定値対称行列で表現されるが,本研究では,どのような付加的条件がM凸性・L凸性を特徴づけかという問題意識をもち,この問題に対して完全な解答を与えた.その副産物として,確率過程論などで研究されてきたディリクレ形式との関連が明らかとなった.

【研究種目】萌芽的研究

【研究期間】1999 - 2000

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