researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

researchmap

Committee type：Academic society

日本オペレーションズリサーチ学会編集委員会

researchmap

Committee type：Academic society

日本オペレーションズ・リサーチ学会東北支部

researchmap

Committee type：Academic society

日本オペレーションズ・リサーチ学会研究普及委員会

researchmap

Committee type：Academic society

電子情報通信学会英文論文誌A離散数学とその応用小特集号編集委員会

researchmap

Committee type：Academic society

日本オペレーションズ・リサーチ学会

researchmap

Grant amount：\4550000 （ Direct Cost: \3500000 、 Indirect Cost：\1050000 ）

本研究では，整数格子点上で定義される非線形な関数（以下，離散関数）が与えられ，それを最小化する整数ベクトルを求める，という非線形整数計画問題を扱う．本研究では，離散関数の多面体構造に注目し，効率的に最小化可能な離散関数のクラスを，その凸閉包関数の多面体構造によって特徴付けることを目的とする．
本年度は，ある種のスケジューリング問題から生じる非線形整数計画問題の解法構築に取り組んだ．このスケジューリング問題では，機械の消費エネルギー量を増やすことにより，処理スピードを上げることができる．したがって，各ジョブの処理時間は変化させることができるが，処理時間を短くすると消費エネルギー量が増えることになる．このスケジューリング問題の目的は，各ジョブの処理開始時間，処理締切時間に関する制約を守りつつ，消費エネルギー量の総量が最小になるようなスケジュールを求めよ，という問題である．
この問題に対し，昨年度の研究で得られた，スケジューリング問題の解集合が劣モジュラ多面体というよい構造をもつという結果を利用して，効率的な解法を得ることができた．このスケジューリング問題は，劣モジュラ多面体上での分離凸関数最小化問題の特殊ケースとみることができるので，後者の問題に対する各種解法がスケジューリング問題に適用できることがわかった．さらに問題の特殊性を利用することにより，それらの解法の計算時間を短縮することに成功した．また，この研究の副産物として，扱ったスケジューリング問題に対する既存のアルゴリズムが，劣モジュラ多面体上での分離凸関数最小化問題のある種の解法と密接な関係をもつことが判明した．

researchmap

Grant amount：\4030000 （ Direct Cost: \3100000 、 Indirect Cost：\930000 ）

本研究では，劣モジュラ関数を様々な制約条件の下で最小化または最大化するという離散最適化問題（劣モジュラ最適化問題）を扱った．劣モジュラ性は様々な状況で自然に現れる概念であり，数多くの応用をもつことから，近年アルゴリズム開発の研究が盛んに行われている．しかし，その問題の数学的構造や計算複雑度については十分に解明されていない． 本研究の目的は，劣モジュラ最適化問題を離散凸解析の視点から調査することにより，劣モジュラ最適化問題の計算限界を明らかにすることである．研究代表者は科研費による援助を受けながら，離散凸解析の研究に10年以上携わってきた．その成果を踏まえ，この問題の構造解析および計算複雑度の解明に取り組んだ．
本年度は，昨年度に引き続き，L凸関数の最小化問題に対する，最急降下アルゴリズムの解析を行った．昨年度は整数格子点集合上で定義されたL凸関数の場合を主に扱ったが，本年度は実数空間上で定義された多面体的L凸関数の場合へ一般化して解析を行った．最小費用流問題に対し Hassin (1983) が提案した双対アルゴリズムでは，双対変数を最急上昇方向へ繰り返し更新する．離散凸解析においては，最小費用流問題の双対問題は，多面体的L凸関数の最小化として定式化できることが知られており，Hassinのアルゴリズムは多面体的L凸関数に対する最急降下アルゴリズムと見なすことができる．本研究では，多面体的L凸関数に対する最急降下アルゴリズムのもつ様々な単調性を明らかにした．まず，最急降下アルゴリズムがHassinのアルゴリズムと同様の単調性を持つことを示した．また，任意の初期点から出発したときに，最急降下アルゴリズムが初期点から「最も近い」最適解を求めると共に，アルゴリズムで生成された解の軌跡が初期点から最適解への「最短路」であることを証明した．

researchmap

Grant amount：\5330000 （ Direct Cost: \4100000 、 Indirect Cost：\1230000 ）

In this research, we consider integer programming problems with nonlinear objective functions and nonlinear inequality constraints, and aimed at developing approximation algorithms with theoretical guarantee for quality of solutions and running times. As the main results of this research, we proposed an approximation algorithm for the maximization of M-concave function with multiple knapsack constraints, and showed that the proposed algorithm finds an approximate solution that is arbitrarily close to an optimal solution in polynomial time. The proposed algorithm is developed based on a continuous relaxation approach. We also consider the maximization of the sum of two M-concave functions, and showed that an approximate solution that is arbitrarily close to an optimal solution can be obtained in polynomial time by using a Lagrangian relaxation approach.

researchmap

Grant type：Competitive

researchmap

Grant amount：\17810000 （ Direct Cost: \13700000 、 Indirect Cost：\4110000 ）

This research integrated the theory and application of optimization in various fields of engineering and social sciences by Discrete Convex Paradigm. We analyzed the theory and applications of discrete convex analysis, to clarify the mutual relationship of the individual mathematical techniques and problems in applications, from three aspects of the continuous-discrete axis, the convex-nonconvex axis, and the fields-transversal axis. Also we conducted research from three aspects of mathematical deepening, applications development, and software development, and achieved the new developments in Discrete Convex Paradigm. In particular, mathematical deepening includes the results of detailed analysis in L-convex function minimization algorithm and presentation of a framework of discrete DC programming.

researchmap

Grant amount：\4420000 （ Direct Cost: \3400000 、 Indirect Cost：\1020000 ）

The aim of this research is to develop algorithms with theoretical guarantee for both of computational time and quality of solutions by using the theory of discrete convex analysis. During the three years of the research period, I have obtained various new results. In particular, I developed a polynomial-time approximation scheme for the maximization of an M-concave function under multiple knapsack constraints. In addition, I revealed the structure of a general solution set called a neighbor system, and showed that the minimization of a separable-convex function over a neighbor system can be solved in polynomial time.

researchmap

Grant amount：\13260000 （ Direct Cost: \11100000 、 Indirect Cost：\2160000 ）

researchmap

Grant amount：\3760000 （ Direct Cost: \3400000 、 Indirect Cost：\360000 ）

researchmap

Grant type：Competitive

researchmap

Grant amount：\13100000 （ Direct Cost: \13100000 ）

本研究の目的はデータマイニングにおける現在の精度限界を打破するための知識抽出モデルの提案と、それに関する理論研究及び実際のシステムの構築である。特に、研究代表者の持つ先端技術である計算幾何学的手法を中心に、計算理論手法による限界突破を目指した。継続中の研究テーマについては研究をさらに進めると共に、過去3年間に行った研究の取りまとめを行った。
新たに得られた研究成果については、国内外の会議や研究会にてを発表するとともに、論文に纏めて学術論文誌に投稿をした。以下、新たに得られた結果について簡単に紹介する。
昨年までの研究における重要な成果として、ゾーン図に関する結果が挙げられるが、これは点と点の間の3等分線によって描かれる図であった。本年度はこれをさらに発展させ、点と線分の間の3等分線について考え、そのような等分線の一意的存在性を示すと共に、3等分線を効率的に計算するアルゴリズムを提案した。
次に、平面上に辺を曲線として描画されたグラフにおいて、辺が交差しない全域部分木を計算する問題を考えた。非交差な全域部分木を持つかどうかの判定はNP困難問題であり、交差数を最小化する問題は近似困難である事が知られている。本研究では、自然なパラメタに対し、パラメトリック計算量(パラメタへの依存度を考慮する計算量)を考察した。対象とするパラメタは、入力されるトポロジカルグラフにおける交差辺対の数、交差辺の数、頂点集合の凸包の内点である頂点数である。また、3-SAT問題への帰着により、この問題に対して計算困難性を示した。

researchmap

Grant amount：\3500000 （ Direct Cost: \3500000 ）

離散最適化問題は,生産計画,ロジスティクス,システム設計,ファイナンスなどの様々な応用分野で現れるが,最適解を効率的に求めることは多くの場合に困難である.本研究では,研究代表者によって提唱された離散凸解析という理論体系を踏まえて,非線形離散関数の離散凸関数による近似の理論構築を目的とした.さらに,この離散凸近似理論を基にして,非線形目的関数に関する離散最適化問題という扱いにくい問題を,離散凸関数最小化という扱いやすい問題で繰り返し近似して解くという新たなアプローチを提案する.しかし離散凸関数最小化は,連続凸関数の場合と異なり,より詳細な細分化を行わないと,扱いやすい問題が得られない.離散凸近似による効率的な最適化アプローチの実現には,離散凸関数の細分化の緻密さと,与えられた非線形目的関数に対してどの離散凸性による近似を採用するかが,重要な鍵となる.このため,本年度行った具体的な研究内容は以下の通りである.
・これまで離散凸解析で扱ってきたM凸性という概念を,ジャンプシステム上で定義された関数にまで拡張した.ジャンプシステム上のM凸関数最小化問題に対する最適性規準を導出した.
・離散関数に対するヘッセ行列および局所2次展開の概念を導入し,これらを用いたL凸関数およびM凸関数の特徴づけを与えた.この特徴づけは,連続凸関数に対する特徴づけとよく対応している.さらに,離散凸解析とは独立して研究されてきたmultimodularityという概念が,実質的にL凸性と等価な概念であることを,L凸関数の特徴づけを用いて簡単に示した.
・上記の結果に基づき,2次のL凸,M凸関数を用いた凸近似手法を構築した.さらに,一般のL凸,M凸関数による最良凸近似について検討を行った.

researchmap

Grant amount：\2700000 （ Direct Cost: \2700000 ）

本研究の目的は,計算困難な整数計画問題に対して,主算法によるアプローチを使って,効率的な厳密解法を構築する,というものである.一般の非線形整数計画問題に対する効率的なアルゴリズムの完成には至らなかったが,それまでの研究において効率的なアルゴリズムの構築に有用と思われる興味深い結果を得ることができた.その内容を以下に述べる.
・完全ユニモジュラ行列と呼ばれる行列により制約条件が表現される非線形整数計画問題が,M凸関数,L凸関数などの離散凸関数と密接な関係をもつことがわかった.この結果は論文誌に掲載された.この結果のように,一般の非線形整数計画問題も局所的には何らかの良い構造をもっていることが期待され,これを利用することで効率的な解法が構築できるのではないかと考えられる.
・L凸関数最小化アルゴリズムに対する検討を行った.2005年9月にKolmogorovにより提案されたアルゴリズムと,2003年の室田のアルゴリズムの比較を行い,室田のアルゴリズムはKolmogorovのアルゴリズムを特殊化したものと見なせることを明らかにした.Kolmogorovのアルゴリズムは各反復での探索方向に自由度があるので,それを利用してより一般的な問題が解けるかどうかさらに検討した.
・ジャンプシステム上の分離凸関数最小化問題について検討を行った.基多面体上での分離凸関数最小化についてはすでに多項式時間アルゴリズムが知られているが,基多面体を一般化した概念であるジャンプシステムについてはまだ多項式時間で解けるかどうかわかっていない.そのため,研究代表者がこれまでに提案した領域縮小法やスケーリング法などの最小化手法が適用可能かどうか調べた.

researchmap

Grant amount：\10200000 （ Direct Cost: \10200000 ）

The main aim of this research project is to establish a novel paradigm of discrete convexity by exploiting applications of the theory of discrete convex analysis to fundamental problems in economics, system engineering, operations research, optimization, algorithm science, and others. In this research project, we obtained a number of results described below. All of the results are presented at refereed international conference or accepted for publications in international scientific journals.
(1)For optimization problems related to discrete convexity (in particular, for the submodular flow problem with M-convex cost function), we developed a number of efficient algorithms using the capacity scaling technique. The obtained algorithm has the best known complexity bound.
(2)We pointed out that the concept of multimodular functions, which had been conceived independently of discrete convex analysis, is essentially equivalent to the concept of L-convex functions. On the basis of this observation we derived some properties including discrete separation.
(3)We revealed a close relationship between M-convex functions and tree metrics. Specifically, we proved that the Hessian matrix of a quadratic M-convex function is essentially the same as the negative of the tree metric matrix.
(4)We established a discrete fixed point theorem for functions defined on integrally convex sets. The theorem finds applications in mathematical economics and game theory.
(5)We provided new characterizations of M-convex functions in terms of gross substitution and single improvement property known in mathematical economics.
(6)As applications of discrete convex analysis to mathematical economics, we developed a theory for economic equilibrium models with indivisible goods. We also developed an algorithm for computing a competitive equilibrium using the framework of M-convex submodular flow problem.

researchmap

Grant amount：\2100000 （ Direct Cost: \2100000 ）

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

researchmap

Grant amount：\1800000 （ Direct Cost: \1800000 ）

本年度は,組合せ凸関数の理論を構築するとともに,様々な組合せ最適化問題に対して非線形計画アプローチを用いた効率的なアルゴリズムを提案することを目指した.
1.組合せ凸関数の理論において中心的な役割を果たすのがM凸関数という概念であるが,組合せ凸関数理論に基づく効率的な解法の基礎として,M凸関数最小化に対する高速算法の構築が必須となる.本年度はM凸関数最小化およびその特殊ケースに対する高速算法を提案し,下記の論文にまとめた.
A.Shioura : Fast Scaling Algorithms for M-convex Function Minimization with Application to the Resource Allocation Problem, S.Moriguchi, A.Shioura : On Hochbaum's Scaling Algorithm for the General Resource Allocation Problem
2.これまで組合せ凸関数の概念は主に整数格子点上で定義された関数を対象としていたが,組合せ最適化問題の中には実変数に関する問題が少なくない.この事実を踏まえて,組合せ凸関数の概念を実数空間上の関数へと拡張し,その関数に関する様々な性質を導いた.この結果は下記の論文にまとめられている.
K.Murota, A.Shioura : M-convex and L-convex Functions over the Real Space : Two Conjugate Classes of Combinatorial Convex Functions
3.組合せ凸関数の理論を利用して一般の組合せ最適化問題を解くためには,その問題の部分的な構造からM凸性,L凸性のような良い構造を見出すことが必要である.本年度は,最小費用流問題という,組合せ最適化においては基本的な問題からM凸性,L凸性が生じることがわかり,下記の論文にまとめた.
K.Murota, A.Shioura : Substitutes and Complements in Network Flows Viewed as Discrete Convexity

researchmap

Grant amount：\7600000 （ Direct Cost: \7600000 ）

The main aim of this research project is to exploit applications of the theory of discrete convex analysis proposed by the head investigator in the last decade. In this research project, we obtained various results described below. All of the results are presented at refereed international conferences and/ or accepted for publications in international scientific journals.
(1) In the area of mathematical economics we obtained three results as applications of discrete convex analysis. First of all, we developed a theory for economic equilibrium models with indivisible goods ; in particular, we investigated sufficient conditions for the existence of competitive equilibrium in an exchange economy with indivisible goods. Secondly, we provide new characterizations of M-convex functions which play a central role in discrete convex analysis. These characterizations are based on well-known concepts in mathematical economics such as the gross substitutes condition and the single improvement condition. Thirdly, we developed an algorithm for computing a competitive equilibrium in an exchange economy with indivisible goods. This algorithm is based on M-convex submodular flow problem which is an optimization problem in discrete convex analysis.
(2) We showed a proximity theorem for M-convex function minimization and developed fast algorithms.
(3) We discussed combinatorial structure in engineering system from the viewpoint of discrete convex analysis. In particular, we investigated the delta matroid parity problem with the aim of determining the solvability of electrical circuits, and developed an efficient algorithm.
(4) We verified applicability of the algorithms in discrete convex analysis to several problems in operations research. Based on this result, we developed efficient algorithms for the network design problem and the max cut problem.

researchmap

Grant amount：\1400000 （ Direct Cost: \1400000 ）

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

researchmap

Grant amount：\1600000 （ Direct Cost: \1600000 ）

本年度は,前年度の研究結果に基づき,離散最適化問題に対するアルゴリズムの枠組みを提案するとともに,これまでの研究結果を論文誌や学会にて発表した.
1.平成11年度の計画のうち,予定通りに終了しなかった部分については継続して研究を進めた.
2.前年度の結果を踏まえて,付値マトロイドの理論に基づいた,離散最適化問題に対する解法の枠組みを提示した.さらに,その手法を現実の大規模な問題に適用するために必要なアルゴリズムを開発した.特に,スケーリングという技法を用いた効率的な算法を提案した.
3.上記で得られたアルゴリズムをプログラム化し,その特徴を得るために実験により解析を行った.さらに,その結果を元にして,理論的な解析へ繋げようと試みている.
4.以上の成果を専門分野の研究者に紹介し,討論を通じてその意義を明かにし,学術論文として学術論文誌に投稿した.いくつかの結果についてはDiscrete Applied Mathematics,Advances in Applied Mathematicsなどの論文誌に掲載されており,その他の論文については現在審査中である.また,2000年8月の国際数理計画シンポジウム,2000年11月の京都大学数理解析研究所の研究集会など,国内外の学会にて研究結果を発表するとともに,他の研究者と有意義な討論を行った.2001年2月には研究のまとめを行うために,カナダ・ブリティッシュコロンビア大学のMcCormick教授を訪問し,数多くの議論を行った.

researchmap

Grant amount：\5800000 （ Direct Cost: \5800000 ）

In the area of nonlinear programming, the theory of convex analysis provides a unified framework for well-solved problems. In the area of discrete optimization, on the other hand, we do not have such a unified framework. Matroidal structure, however, is known to be a well-behaved structure in discrete optimization. The theory of "discrete convex analysis" is proposed by the head investigator with a view to capturing the continuous optimization and the discrete optimization from a common viewpoint. Discrete convex analysis is a theoretical framework connecting the theory of convex analysis and the theory of matroids.
It is often the case that discrete optimization problems appearing in the real world do not have nice combinatorial structure such as matroids. Therefore, we need to use enumeration-type algorithms such as the branch-and-bound method or approximation algorithms such as meta heuristics. In either approach, it is essential to extract tractable part from the discrete structure of the problems to be solved. For example, it is often effective to extract network-like structure as subproblems when we solve general discrete optimization problems.
The fundamental idea of our research is to extract certain structure which can be dealt with discrete convex analysis as subproblems when we solve general discrete optimization problems. We summarize the main results as follows :
・The concepts of M-convex and L-convex functions play a central role in the framework of discrete convex analysis. We showed various properties of these functions.
・We proposed efficient algorithms for the minimization of M-convex functions.
・We extended the concepts of M-convex and L-convex functions defined over the integer lattice to functions over the real space.
・We generalized the concepts of M-convex and L-convex functions to quasi M-convex/L-convex functions.
・We obtained some results on the application of discrete convex analysis to economic equilibrium such as the equivalence of gross substitutes property and M-convexity.

researchmap

Grant amount：\900000 （ Direct Cost: \900000 ）

離散凸解析は,連続変数に関する最適化(非線形計画)と離散変数に関する最適化(組合せ最適化)を統一的な視点から捉える枠組みとして代表者によって構築された数理計画理論であるが,本研究では,離散凸解析の理論的成果を都市工学や数理経済学という社会科学の分野に応用することを目標として,以下の成果を得た.
(1) 不可分な財を含む経済均衡理論における効用関数として従来考察されたものの多くがM凸関数であることを指摘した.他方,効用関数にM凸性を仮定することによって一般的な均衡存在定理が得られることを示した.この結果は,M凸性の概念が,経済学でも有用かつ妥当なものであることを示している.以上の知見を,Danilov氏,Koshevoy氏との共著論文の形にまとめて,数理経済学の学術誌に投稿した.
(2) 離散凸解析は,元来,整数格子点上で定義された整数値関数に関する理論であったが,実数空間上で定義された関数に対してもM/L凸関数の概念を定義し,M凸性とL凸性の共役性を中心に,その基本的な性質を調べた.
(3) 凸関数を費用関数にもつネットワーク流問題に関するRockafellarの理論を,実数空間上で定義されたM/L凸関数(上記の(2))を用いて拡張することを試みた.費用関数が区分的に線形な(多面体的な)M/L凸関数の場合には厳密な理論を構築できたが,一般の非線型M/L凸関数に対しては,双対定理の解析的な部分の議論にまだ数学的に不完全な点を残している.しかし,少なくとも,これによってネットワーク流問題の枠組みに非分離関数(nonseparable function)を導入することが可能になった.なお,この結果は,実数空間上のM/L凸関数に関する双対定理として位置づけることができる.

researchmap

Grant type：Competitive

researchmap

Grant type：Competitive

researchmap