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

平成3年度および4年度に計画した研究目標は以下通りであった。 1.主双対内点法の計算効率の向上および評価に関する基礎研究。 2.非凸型2次計画問題および組合せ最適化問題への内点法の適用に関する基礎研究。 3.内点法を中心とする線形計画法のソフトウェアに関する基礎研究。 4.内点法の一般化に関する基礎研究。 研究目標1に関しては, (1)内点法の各反復でのステップ長をコントロールする新手法の提案, (2)内点法の初期点に関する研究 を行い理論的な成果を得るとともに,研究目標3と関連して,これらの成果を主双対内点法のソフトウェアに組み込んだ計算実験を行いその有効性を検証した。研究目的2に関しては、非凸型2次計画問題および組合せ最適化問題そのものについての研究成果はあげたが、内点法を適用出来るまでには研究は進んでいない。これはこれらの問題がもともと非常に難しい問題であることが主な原因であり、今後もこの方向で研究を続ける必要がある。研究目標の4に関しては、上述の線形計画問題に関する結果を一般の凸型計画問題に拡張することが出来、充分な成果をあげたと言える。

連続体および連続体近似できる自然現象の数理モデル方程式を数学解析し, 次のような研究成果が得られた(主要なもののみ記す). (1) Navier-Stokes方程式, Stokes 方程式に対して, 区分的に連続な境界を持つ領域, 角領域での強解の一意存在 ; (2) Navier-Stokes方程式に対して, 滑り境界条件(Navier型, 閾値型) 下での強解の一意存在 ; (3) 水の波(渦なし非圧縮Euler方程式の自由境界問題) の長波近似, 浅水波近似の正当化 ; (4) 自己重力作用下での流体星(化学的に活性な圧縮性粘性流体) の1次元問題および3次元球対称問題の滑らかな時間大域解の一意存在 ; (5) 弾性体に対するいくつかの亀裂問題の可解性.

1.研究代表者を中心として得られた知見 (1)正定値自己共役作用素を近似する有界自己共役作用素列の分数巾の収束率と一様有界性 近似作用素の列の収束率が近似作用素の分数巾の列の収束率に適切に反映されることを示し、この結果から分数巾の列のある意味での一様有界性がしたがうことを示した。(2)水の波線形非定常問題の有限要素離散化問題の収束性と誤差評価の方法の抽象的展開 (1)の結果を手がかりにして、研究を展開した。支配作用素が一階の擬微分作用素であることから生ずる興味ある知見を得た。(3)スチェクロフ作用素を用いた透過境界条件の設定とその数値的取り扱い 外部領域におけるポアッソン問題などの有限要素近似問題に適用しその方法を正当化した。(4)軸対称容器内の水の波固有値問題の有限要素計算 理論解析結果の正しさを確認するとともに、理論の適用出来ない場合の問題点を整理した。 2.分担者が著しい成果を収めた研究課題(分担者名) (1)凸汎関数に対する劣微分作用素の固有値問題の列における解の列の収束性(渡辺二郎、海津總)。(2)積分半群の理論の追究とその線形関数微分方程式の解半群への応用(内藤敏機)。(3)3次精度上流型有限要素近似による自動搬送車廻りの気流解析(田端正久)。(4)高レイノルズ数円柱回り流れにおける流脈線のシミュレーションと近似流脈線の誤差評価(田端正久)。(5)抵抗性磁気流体作用素のスペクトル的性質の解明とその近似解法(加古孝)。(6)ある種の凸最小最大問題に対する再帰的アルゴリズム(田村明久)。 3.電気通信大学数値解析研究会の継続開催と研究資料「電気通信大学数値解析研究会講演題目集」の作成 本年度21回に亘っておおむね金曜午前に実施し、3月4日には一日研究会「恩故知新の集い」を開催した。研究資料には1977年から現在にいたるこの研究会とその前身の会での講演題目を収録した。

「非線形最適化手法による組合せ最適化問題の効率的解法の開発」という目的で本年度は研究を進めて来た。組合せ最適化問題の中でも安定集合問題を双向グラフ上に一般化した問題に(一般化安定集合問題と呼ぶ)対しては、本研究の目的を完全に達成した。具体的には、双向グラフのパ-フェクト性を導入し、無向グラフのパ-フェクト性との関係を明らかにし、さらにパ-フェクト双向グラフに対する一般化安定集合問題を半正定値計画問題として定式化する方法を示した。この半正定値計画問題に対する多項式時間解法である楕円体法や内点法を用いることでパ-フェクト双向グラフに対する一般化安定集合問題に対する多項式時間解法を構築した。これらの結果は3編の論文としてまとめ、1編はJ.of the Operations Resarch Society of Japanに掲載予定であり、他の2編はMathematical Programming誌と国際会議の査読付きProceedingsに投稿中である。 その他の組合せ的な問題点に対しては、グラフのバンド幅を求める問題について、木グラフのバンド幅の上界値を与える方法を提案した。この上界は既知の結果であるChavatalovaの上界より良く、頂点数が10^9以下の木グラフについてはChunnの上界よりもよいものであった。この結果Discrete Mathematics誌に掲載された。また、グラフのある種の変換についての同型性の研究や符号理論や暗号理論に関する研究を進めた。 非線形を専門とする分担者は、人工ニューラルネットワークの逆問題解析への応用についての研究を進め、核融合プラズマの位置決定問題に適用し良好な結果を得た。これをFusion Technology誌に発表した。

数論に現れるアルゴリズムを中心にその可測力学系としての性質を研究し、エルゴード理論、ディオファンタス近似論、一様分布論の新しい研究成果を導き出した。とりわけ、非アルキメデス的数体上の非同次ディオファンタス近似論、非アルキメデス数体を係数とする多項式に対するユークリッドアルゴリズムの計算回数の評価、区間交換に対するRauzy inductionのエルゴード理論的性質、実数に関する多次元連分数アルゴリズム、一様分布の誤差の広がりに関して新しい所見を得た。

極値グラフ理論の問題は，グラフ H を固定するとき，与えられたグラフ G が H と同型な部分グラフを含むための辺数あるいは最小次数に関する最善の十分条件を求めることである．本研究では，因子問題，マイナー，部分グラフに関する問題を統一的な視点から俯瞰することにより，新たな問題提起を行い，展開研究を行った．とくに，森グラフの極値問題，弦付きサイクルやシータグラフを点素に見つける問題，マッチング拡張性などを重点的に扱った．また，グラフ理論の大きな未解決問題の一つであるHadwiger予想との関連において，グラフのρ彩色の概念を導入し，次数列に関するHadwiger予想の簡潔な証明を与えた．

グラフ論、離散最適化、計算幾何学の諸分野に渡る本研究の研究成果の概要を以下に示す。 計算幾何学の分野の直線成分の抽出問題では従来用いられてきたハフ変換の性能の限界を理論的に示し,理論的に最適な方法を提案した。画像の等高線表現では、整数格子の性質を研究し、グラフ論、離散最適化を適用した問題解決法を提案した。ディジタルハーフトーニングを数学的最適化問題として定義し,ある種の測度を基礎にした実数要素行列の整数要素行列への変換法を導入することにより、ある制約のもとで効率よく実行できるアルゴリズムの開発に成功した。 離散最適化の分野では有向グラフの一般化として双向グラフを定義し、双向グラフ上で安定集合問題の一般化を定式化した。クローフリーグラフの最大重み独立集合を求めるMintyのアルゴリズムの訂正版を提案した。離散凸解析における重要な基本問題の一つであるM-凸関数の最小化問題に対する新しい多項式時間アルゴリズムを提案した。 グラフの距離構造についてはk-辺ワイド直径はグラフの直径のk次式のオーダーであることを示した。グクフの連結度については先行の結果を含むk-可縮辺の存在を保証するより一般的な禁止部分グラフ条件を示した。5-可縮臨界グラフでは少なくともその1/5の頂点が次数5であること、6-可縮臨界グラフでは少なくともその1/7の頂点が次数6であることを示した。与えられた任意のグラフをその誘導部分グラフに含む5-可縮臨界グラフの存在を示した。 極値グラフ理論の分野では新しい擬確率的手法を開発して当該分野の基本定理であるErdos-Stoneの拡張、Bollobas-Kohayakawa予想を肯定的に解決した。グラフを同型な部分グラフで敷き詰めることができるための次数条件を述べたAlon-Yusterの定理を必ずしも同型でない部分グラフの場合に拡張し、長年未解決であったEl-Zahar予想など多くの定理、予想を近似的に含む一般的な結果を得た。

1.研究代表者を中心として得られた知見 (1)スチェクロフ作用素を用いた透過境界条件の設定とその数値的取り扱い ラプラス方程式とポアッソン方程式の数値解法におけるスチェクロフ作用素の取扱いについて考察を深めた。スチェクロフ作用素を用いることによって、無限領域問題および角のある有界領域等の特異性のある領域での有限要素近似計算法を確立して、その数学解析と数値計算を実施した。完全流体における一様流の中の物体まわり流れの精密計算法を考察した。本研究は研究分担者小山大介と共同して実施した。(2)移流拡散非定常問題の差分近似問題の安定性と誤差評価 数値流体力学における基本問題である移流拡散問題の差分近似問題の安定性と誤差評価を研究した。空間一次元問題における等間隔五点差分公式を対象とした。 2.分担者が著しい成果を収めた研究課題(分担者名) (1)遅れをもつ線形微分方程式の線形作用素の半群の理論による取り扱い(内藤敏機)。(2)構造と音場の連成系の振動スペクトルとその有限要素法による近似理論(加古孝)。(3)狭い間隔をもつ同軸円筒管流のテイラー・クエット渦の数理解析と有限要素数値計算(海津聡)。(4)均質化理論による多孔質媒質における非線形固有値問題の取り扱い(海津聡)。(5)遅延微分方程式のルンゲ・クッタ法による数値解法とその代数的安定性の有効性の確立(小藤俊幸)。(6)グラフの全域木を列挙する効率的方法の開発(田村明久)。(7)組み合わせ最適化問題における実行可能多面体のフェイス構造(田村明久)。(8)交互境界条件法による領域分割計算法(竹田辰興、福原誠)。 3.電気通信大学数値解析研究会の継続開催 本年度15回にわたっておおむね金曜午前に実施し、2月9日には、応隆安北京大教授を囲む特別研究会、3月1日には一日研究会「陽春謳歌の会社」をそれぞれ開催した。

研究実績内容は各分担について以下の通りである: (1)山口耕平:最近話題となっている(ラベル付き)Configuration-空間のトポロジーを調べることを第1の目標とした。とくにArnold達によって研究されてきた,(ラベル付きConfiguration-空間の典型例のひとつである)次数d重複度がn未満の複素係数多項式の空間SP^d_n(C)のトポロジーの研究によりそれまでの結果を含む一般的な結果を得た。(これに関しては論文準備中であり,今春の日本数学会の特別講演で講演予定である。)またこれに関連して,F.Cohen,R.CohenやVassiliev達のこれらの空間に関する安定ホモトピー型に関する結果の別証明も得られた。(それについても論文準備中である。)さらにそれに類似した結果として複素係数有利関数の空間に関する結果も類似の方法で得られた。(これについては論文投稿中である。)またそのために必要となる向き付きConfiguration-空間のトポロジーに関する結果も得られた。(これについての論文が今年中に発行される予定である。)最後に,これらに関連して特異点論の研究および数式処理の研究も行った。 (2)内藤敏機:バナッハ空間上で無限の送れを持つ場合の線形関数微分方程式の研究を行った。とくに,その解半群のスペクトル分解が成立することを一般的の場合で証明した。またその具体例を一般に調べそれらの解の安定性を調べた。 (3)大久保謙二郎:常微分方程式の研究とそれに関する数式処理の研究を行った。とくに数式処理の工学的応用および教育的応用の研究も行った。

1.前年度に開発した無交差ラーマングラフをすべて列挙するアルゴリズムにおいて、実用的な観点から、出力されるグラフのクラスに制限を課した列挙アルゴリズムを開発した。一つは最大次数の上限が与えられている場合で、もう一つはあらかじめ辺集合を指定し、それらを含まないグラフに限定するものである。これらは、いずれも計算困難であることが予想されるが、実用的なアルゴリズムを開発した。 2.逆探索法によって列挙された静定構造物(ラーマングラフ)に対して,節点座標と部材断面積を連続変数として,指定された性能(大変形挙動)を満たすコンプライアントメカニズムを求めた。また,節点数と計算量の関係を検討し,最適な解を求める際の計算量限界を明らかにした。 3.無交差全域木の高速列挙アルゴリズムを開発した。その計算時間の理論的性能評価とともに、計算機実験をおこない、その実用的な性能を評価した。 4.火災等の発生時における建物内部から安全な外部への最適避難経路(最大移動時間最小化問題)や、津波や大地震発生時に安全な建物・地域への最適避難経路を求める問題を考察した。実用的な観点から、格子状ネットワーク、木構造ネットワークに限定し、通路幅一定、途中での枝分かれを許さない、経路が交差しない等の制約下での最適経路群を求めた。またGISや実データを利用し、通行可能経路が確率的に定まるような実際的な問題への導入も検討した。 5.LRTなどを模した線的施設配置問題について研究した。駅と線路からなる平面上の全域木において、利用者の総移動時間を最小化するような、ネットワークのトポロジーを求めるヒューリスティクスを開発した。

(1) 線形計画法と2次計画法における内点法の研究(小島、水野、田村) 線形計画法に対するランク1更新法の開発、主・双対内点法の開発とその収束特性に関する吟味、非線形相補性問題に対する内点法の研究などを行なった。 (2) 理財工学における最適化法の研究(今野、白川) マ-コビッツのMVモデルの改良版でいあるMADモデルを開発し、その特性を調べた。またこのモデルを一般化したMADSモデルを開発し、その特性を検討した。これらのモデルの新しいところは、少ない手間で最適ポ-トフォリオの計算ができること、収益率分布の3次のモ-メント(歪度)の定量的取扱いを可能にしたことなどである。また、多期間ポ-トフォリオ・配当最適化問題を分析する一般的枠組みの構成を行うとともに、これらを解くためのアルゴリズムの開発を行った。これによって従来よりも複雑かつ大規模な問題を解くことが可能となった。 (3) 非凸型最適化問題の大域的最適解を求めるアルゴリズムの研究(今野、久野) 数種類の非凸型最小化問題の効率的解法の開発に成功した。具体的には、線形乗法計画問題、分数関数の和と積の最小化問題、ランク2およびランク3の双線形計画問題、凸乗法計画問題、複数の凸関数の積の最小化問題、非凸型コスト関数をもつロット・サイズ問題、凸乗法制約式の下での凸関数最小化問題などに対する効率的な解法を提案した。これらの問題はポ-トフォリオ最適化、LSI設計、形算幾何学等の分野に広い応用をもつ非凸型問題であり、これらの問題が実用的に解けることは、工学上大きな意味をもつものと思われる。 なお、これらのの研究成果は約30編の論文として公表されており、その大部分は世界の一流の専の門誌に掲載もしくは受理されている。

エルゴード理論の研究はその初期から現在に至るまで数論の研究と密接な関わり合いを持ってきた。とりわけ、実数の2進あるいは10進展開や連分数展開の研究は依然として多くの未解決な問題があり、また一方で情報科学における暗号理論、通信理論などからの要請による新しい研究課題も多く存在する。本研究では連分数展開などの収束、近似の問題あるいはユークリッドアルゴリズムの計算コストの評価を確率論的に取扱い、新たな知見を得ることができた。また、一様分布論など関連する周辺分野についてもいくつかの新しい結果を得た。

与えられたグラフの部分グラフから,辺の縮約を繰り返して得られるグラフを,元のグラフのマイナーと呼ぶ.平面グラフなど重要なグラフの族はマイナーに関して閉じており,禁止マイナーによって特徴づけされる.これまでに知られていた平面グラフなどにおける閉路,全域木,因子に関する問題を,禁止マイナーの観点から拡張することを行った.とくに完全2部グラフをマイナーとして含まないグラフのタフネス,全域木に関する性質で顕著な成果が上がった.加えて,禁止部分グラフによる同種の問題にも成果があった。

近年，その潜在的重要性が増してきた双方向市場のオークションに対する「真に使える」理論の創出を試みる．そのために現実世界の複雑な制約を考慮した汎用的なモデルや評価尺度の数学的定式化を行い，そのモデル・評価尺度のもとで，効率的なアルゴリズムの開発を行う．解析には，離散凸解析やポリマトロイドフロー等の離散最適化の高度な理論を駆使する．得られた成果は，国内・国際学会・査読付きジャーナルへの投稿をとおして世界に発信する． 本研究課題は、双方向市場におけるオークションに対し、現実的な制約を考慮した一般性の高いモデルのもとで優れたアルゴリズムの構築を目指すものである。特に、予算制約という実用上重要な制約に注目し、そのもとでの理論の深化に取り組んだ。こうしたオークションは、これまで可分財を対象とする多面体的クリンチングオークションというアルゴリズムにより発展してきたが、本研究課題では整数制約に対処することで、これを不可分財のモデルへと適用できるように拡張した。さらに、提案アルゴリズムにおける買い手の脱落について構造的な特徴付けを行うことで、パレート最適性・流動的余剰・社会的余剰に係る効率性の理論的保証をそれぞれ与えた。これらの成果をまとめた論文は、2024年度にアルゴリズム的ゲーム理論の主要誌の一つである ACM Transactions on Economics and Computation に掲載された。また、この論文の成果を土台として、より弱い仮定のもとで適用できて優れた性質を満たすアルゴリズムが研究協力者によって提案されている（現在投稿中）。さらに、2024年度には、ミクロ経済学の研究者を対象とする研究集会（第30回DCコンファレンス）において、共著者の招待講演の中でこれらの成果を発表することができ、経済学コミュニティへと本研究課題の成果を展開することができた。その他にも、研究協力者によってクリンチングオークションの効率性および収入の単調性に関する研究が進められた。2024年度には、予算が等しいという仮定のもとで、買い手がオンラインで到着する場合の単調性について新たな成果が得られた。こうした成果は、双方向市場と関係のあるソーシャルネットワーク上のオークションに応用できるものである。研究成果をまとめた論文は、マルチエージェント分野のトップ会議であるAAMAS 2025 に採択された。

本研究では，種々のインセンティブ／誘因に対する人々の反応を解明すると共に，人々に適切なインセンティブを与えることにより，個人の目的と社会の目的を適切に調和させて持続可能な発展を可能とする社会制度の設計に関する「インセンティブ設計科学」と名付けた新しい文理融合型の学問領域を創出する．具体的には，中核となる人工知能／最適化技術に社会科学の知見を統合し，インセンティブ設計科学に関する理論構築，被験者実験による評価を行う．さらに，学校選択制，研修医マッチング，公共事業入札，周波数オークションなどの応用分野において，政策提言とソフトウェアライブラリの開発準備，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年度が最終年度であるため、記入しない。

本研究課題は，離散凸解析という良い離散構造をもつ枠組みを武器として，離散的な配分において，プレイヤーが複数存在する状況下で，プレイヤー全体やその部分集合が設定する複雑な制約を満たしつつ，個々のプレイヤーが満足する配分とは何かという解概念とそれを求めるアルゴリズムを研究し，現実問題へフィードバックすることを目的としている. 平成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）「他の離散資源配分問題への適用」を念頭に研究を進める．

平成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 などの国際会議録より出版し，関連研究コミュニティに発信する．メカニズムの設計が計画どおりに進まない場合には，既存の様々なメカニズムの評価を重点的に行う．特に，検証班を中心とする被験者実験によって，現行の制度と既存のメカニズムにおける人間の振舞いの違いを洗い出し，ゲーム理論の均衡概念の実問題・各事例における信頼性を詳細に議論する．また，既存メカニズムの実行時間を計算複雑性の理論に基づいて明らかにし，大規模な問題への適用を可能にする近似アルゴリズムの提案を行う．

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

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

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