组合优化中整数规划的数论解法

摘要：

整数规划属于计算机组合优化中的重要方法.目前求解整数规划的方法主要有割平面法和分枝定界法.前者往往收敛很慢甚至不收敛,后者不适用自变量较多的问题.从一种全新的视角出发,使用数论中的不定方程理论,来提出一种高效的整数规划新解法.该方法先把目标函数可能取的整数值k添加作一个新的约束条件,然后让k依次增大.使用不定方程理论,并结合自变量的取值范围,该方法能迅速发现没有意义的k,从而大大减少计算量.该方法还不用求解整数规划相应的松弛线性规划问题.因此这种基于数论的整数规划解法速度很快,是一种较有前途的方法.最后针对典型的问题给出算例进行分析验证.

关键词：组合优化、整数规划、线性规划、数论、不定方程

所属期刊栏目：30

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2009-04-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：1276-1278