摘要
整数规划属于计算机组合优化中的重要方法。目前求解整数规划的方法主要有割平面法和分枝定界法。前者往往收敛很慢甚至不收敛,后者不适用自变量较多的问题。从一种全新的视角出发,使用数论中的不定方程理论,来提出一种高效的整数规划新解法。该方法先把目标函数可能取的整数值添加作一个新的约束条件,然后让依次增大。使用不定方程理论,并结合自变量的取值范围,该方法能迅速发现没有意义的,从而大大减少计算量。该方法还不用求解整数规划相应的松弛线性规划问题。因此这种基于数论的整数规划解法速度很快,是一种较有前途的方法。最后针对典型的问题给出算例进行分析验证。
Integer programming is most important method of computer combinatorial optimization. The prime methods for integer pro- gramming are the cutting plane method and the branch-and-bound method. The former converges rather slowly, even does not converge. The latter is not competent for the situations where there exist many variables. Having taken a novel view into account, a new efficient method for integer programming is proposed in this work, on the basis of indeterminate equation of number theory. The value k of objective function is considered as a new constraint, then it is increased gradually. Using the indeterminate equation theory and taking the domain of variables into account, the new method could fast find the unmeaning k, so that it could decrease a larger amount of calculation. It is not required to solve the associated linear programming relaxation of an integer programming in the new method. Consequently, the method is rather fast and promising. Finally, a classical example is used for analysis and test.
出处
《计算机工程与设计》
CSCD
北大核心
2009年第5期1276-1278,共3页
Computer Engineering and Design
关键词
组合优化
整数规划
线性规划
数论
不定方程
combinatorial optimization
integer programming
linear programming
number theory
indeterminate equation
