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

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

基本信息

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

项目摘要

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

这项研究的目的是使用主要算法方法为计算困难的整数规划问题构建一种有效的精确解决方法，尽管我们无法完成该过程，但我们获得了有趣的结果，这些结果被认为对构建有效的算法有用。到目前为止，我们的研究正在进行中。详细信息如下所述。发现用列表示约束的非线性整数规划问题与M凸函数和L凸函数等离散凸函数有密切关系，因此，一般非线性整数规划问题有望得到解决。局部具有某种良好的结构，并且认为通过利用它，可以构建有效的解决方法。・L-凸函数最小化算法考虑我们将 Kolmogorov 于 2005 年 9 月提出的算法与 Murota 算法于 2003 年进行了比较，发现 Murota 算法可以认为是 Kolmogorov 算法的专门版本。Kolmogorov 算法由于每次迭代时搜索方向存在一定的自由度，因此我们进一步研究是否可以使用它来解决更普遍的问题。我们研究了最小化跳跃系统上的单独凸函数的问题。多项式时间算法已知用于最小化基多面体上的单独凸函数，但跳跃系统是基多面体的广义概念，尚不清楚是否可以解决这个问题。因此，主要研究者研究了是否可以应用迄今为止提出的面积缩减和缩放方法等最小化方法。