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