Research projects

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.

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

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.

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.

経済学,システム工学,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立し,それを広範囲の応用分野に浸透させる研究を行った.「離散凸パラダイム」の横糸を成す,構造定理やアルゴリズムを代表とする離散関数に関する数理の研究と,縦糸を成す,諸応用分野における具体的な諸問題に対する研究を行った.

How to allocate precious resources becomes critical due to various pressing social issues, including energy, environmental, and aging population issues. The goal of this project is developing the theory of resource allocation mechanism design, which aims to make desirable decisions considering economic, social, and environmental needs when multiple agents exist, by synthesizing/extending technologies from computer science and micro economics. More specifically, we developed design, analytic, and representation technologies for resource allocation. In particular, we made notable contributions on mechanism design for constrained two-sided matching, equilibrium analysis for repeated games in noisy environments, and concise and efficient representations for coalitional games. The summary of publications of this project is as follows: refereed international conferences 87, international journals 74, domestic journals 11, research monographs 8, textbooks 4, invited talks 40.

Discrete allocation problems (i.e., allocation of students to departments, allocation of residents to hospitals) are important practical problems. The aim of the project is to generalize the stable matching model by using discrete structures such as graphs and discrete convex analysis, and to analyze developed models. We develop a new mechanism for a discrete allocation problem with distributional constraints, and propose and analyze new generalizations of the stable matching model to directed networks, and so on. These results are summarized as six papers published in academic journals, two submitted papers, and two papers during preparations.

This research project had three aims on algorithms in discrete convex analysis : (1)development of a polynomial time algorithm for minimization of M_2 convex function ; (2)study on algorithms for minimizing continuous M-/L-convex functions ; and (3)study on relations between discrete convex analysis and convex function minimization problems. Our group achieved the first aim. Murota who is one of our group together with Iwata and Moriguchi, developed a polynomial time algorithm for solving M-convex submodular flow problem which is equivalent to M_2 convex function minimization. We are investigating the second aim. On the third aim, we obtained several results and future works. These are divided into two subjects. The first subject is an application of discrete convex analysis to two-sided matching market models. Fujishige and Tamura proposed several two-sided matching models by utilizing discrete convex analysis. These models contain many known models as special cases. They proved that their models always have pairwise-stable outcomes by modifying an algorithm for M_2-convex function minimization. Moreover, the proofs give polynomial time algorithms for finding pairwise-stable outcomes in the case where effective domains are contained in 0-1 hypercubes. Tamura together with Farooq investigated properties of M-convex functions in terms of mathematical economics. The second subject is M-convex functions in jump systems. Murota gave a concept of M-convex functions in jump systems, an optimality criterion of these functions, a minimization algorithm. Moreover, Tamura proposed a polynomial time algorithm for minimizing an M-convex function by using coordinatewise scaling technique which is a new idea in combinatorial optimization.

We obtained several results on semidefinite programming and discrete convex analysis and presented these results at international conferences, e.g., International Symposium on Algorithms and Computation, Conference on Integer Programming and Combinatorial Optimization and so on. Here we explain seven results among these. 1) Fujie and Tamura generalized the theory of a convex set relaxation for the maximum weight stable set problem to the generalized stable set problem. They also gave simple proofs for several results for the maximum weight stable set problem. 2) Murota et al. proved that the numerically obtained solution of group symmetric semidefinite program is group symmetric. 3) Murota et al. gave a framework of exploiting the aggregate sparsity pattern over all data matrices of large scale and sparse semidefinite programs. 4) Murota and Tamura gave an efficient algorithm to decide whether a competitive equilibrium exists or not in some economic model by utilizing M-convex submodular flow problem. 5) Tamura devised a new scaling technique and an efficient algorithm for M-convex function minimization problem. 6) Murota and Tamura proved proximity theorems for several discrete convex functions, for example, M2-convex functions, L2-convex functions and so on. 7) Tamura showed a technical result that any L2-convex function can be represented by the convolution of two L-convex functions attaining the infimum in the definition of the convolution. This result gives simple proofs for several known results on L2-convex functions.

組合せ最適化問題の中でも最も研究されているものの一つが無向グラフ上の安定集合問題である。一般にこの問題はNP完全クラスに属し、多項式時間解法はおそらく存在しないであろう。しかし、パーフェクトグラフ、クローフリーグラフなどの幾つかのグラフクラスに対しては多項式時間解法が存在する。特にパーフェクトグラフに対する多項式時間解法の特徴は、安定集合問題がその半正定値緩和問題と一致するところにある。またGrotschel-Lovasz-Schrijverは、その逆命題も成立することを証明した。すなわち、安定集合問題とその半正定値緩和問題が一致するための必要十分条件が無向グラフがパーフェクトであることを示した。 本年度の研究成果は、このGrotschel-Lovaz-Schrijverの結果の別証明を与えたことと、この結果を一般化安定集合問題へと拡張したという2つである。彼らの証明では、無向グラフの補グラフとアンチブロッカーという概念を用いている。我々は、半正定値計画問題に対する2次計画問題表現を利用することで、補グラフなどの概念を導入しない別証明を与えた。 一方、一般化安定集合問題は安定集合問題を双向グラフ上へと自然な形で拡張したものであるが、双向グラフに対しては補グラフという概念がない。そのため「双向グラフがパーフェクト」と「一般化安定集合問題とその半正定値緩和が一致」という命題が同値であることを示すには、彼らの証明法を拡張することは困難であるが、補グラフという概念を用いない我々の証明法は、拡張された命題の同値性証明まで適用できるものであった。 これらの結果は国際会議において発表し、論文としてまとめ学術雑誌に投稿した。

「双向グラフに対する最適化問題とその解法の研究」という目的で昨年度に引き続き本年度は研究を進めて来た。 昨年度の研究成果“The generalized stable set problem for claw-free bidirected graphs"について、1998年の6月に開催された国際会議Integer Programming and Combinatorial Optimization(査読付き)にて口頭発表を行った。その際の旅費として本年度の研究費を用いた。また本論文はこの会議のプロシーディングスに掲載された。 本年度の研究成果は“A linear time algorthm for the generalized stable set problem on triangulated bidirected graphs"としてまとめ、Journal of the Operations Research Society of Japanに投稿し、1999年3月17〜19日に京都大学で開催されるJapan-Hungarian Symposium on Discrete Mathematics and Its Applicationsにて口頭発表する。また、この成果については来年度開催される国内外の学術会議、研究会においても口頭発表を行う予定である。この成果は本年度計画していた「一般の双向グラフについて一般化安定集合問題に対する効率的な解放の開発」を含むものである。もう一つの計画「平面上の与えられた点集合の最小重み三角形分割問題へのこの解法の応用」については現在研究中でありまだ成果を得るに至っていない。 また開発した解法については、当研究費によって購入した計算機を用いてその実用面での有効性の検証も行った。

今年度は以下の3つ (a)「0-1多面体の構造解析」 (b)「重み付きグラフにおける全域木の重み順全列挙アルゴリズムの開発」 (c)アルゴリズムの平均的な振る舞いの評価に関する研究」 を研究目的とした。 (a)に関しては、グラフの最大安定集合問題、グラフの辺(または頂点)の彩色問題に関連した0-1多面体の特殊な面がある半順序集合のイデアル全体から作られる0-1多面体と合同であるという構造を明らかにした。また、この構造を利用し、最大安定集合問題などに対する発見的な方法を提案した。この成果は論文としてまとめ、アメリカ合衆国のミシガン大学で開催された第15回数理計画国際シンポジウム(15th International Symposium on Mathematical Programming)や福岡で開催された第3回アジア太平洋地区オペレーションズ・リサーチ会議(The Thrid Conference of the Association of Asian-Pacific Operational Societies within IFORS)など国内外の会議において口頭発表し、国際的論文誌であるMathematical Programmingに掲載されることになった。 (b)に関しては、重み順ではないがグラフの全域木を列挙する時間計算量の意味でも空間計算量の意味でも最適なアルゴリズムを開発した。既存のアルゴリズムで二つの計算量の意味で最適なものはなく、このアルゴリズムが初めてのものである。この研究成果は、論文としてまとめ、第15回数理計画国際シンポジウムや第3回アジア太平洋地区オペレーションズ・リサーチ会議など国内外の会議において口頭発表し、国際的な論文誌であるSIAM Journal on Computingに投稿した。 研究目的(c)に関しては、今年度中には論文として発表できるような成果は残念ながら得られなかったが、今後も継続して研究をしていく。 本年度は、補助金によって設備としてX端末を購入し、現有設備であるワークステーション(平成4年度科研費により購入)と接続し、論文や発表原稿・OHPの作成、実験結果のグラフィック表示など有効利用した。