权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

計算困難な整数計画問題に対する主算法アプローチに基づく厳密解法の構築

基于素数算法方法构建计算困难整数规划问题的精确求解方法

基本信息

批准号：
15740050
负责人：
塩浦昭義
金额：
$ 1.73万
依托单位：
Tohoku University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

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

The purpose of this study is to construct efficient solutions for computationally difficult integer programming problems. General non-linear integer planning problems are the result of the research on the efficiency of the project. The content of the article is as follows: The problem of non-linear integer programming with M convex numbers,L convex numbers, discrete convex numbers, and close connections. The results of this paper were published. The result of this is that the solution of the general nonlinear integer program problem is constructed by using the method of good structure. In September 2005, Kolmogorov proposed a proposal to minimize the number of L projections. In 2003, Muroda's proposal was compared with Kolmogorov's proposal to minimize the number of L projections. Kolmogorov proposed a proposal to minimize the number of L projections. Muroda's proposal to minimize the number of L projections was compared with Muroda's proposal to minimize the number of L projections.Kolmogorov proposed a proposal to minimize the number of L projections. For example, if you want to use this to solve a general problem, you can use it to solve it. The problem of minimizing the number of separated convexities on the list of problems is discussed. Minimization of the number of convex separations on a base polyhedron is a generalization of the concept of polynomial time. Research representatives have proposed the domain reduction method, the minimization method, and the application possibility.