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

• 作者: 李炯城 鲍江宏
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: 组合优化 整数规划 线性规划 数论 不定方程
• 年，卷（期）: 2009,（5）
• 所属期刊栏目: 计算机应用
• 页码范围: 1276-1278
• 页数: 3页
• 分类号: TP301.6
• 字数: 2880字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李炯城	广东省电信规划设计院有限公司信息系统研究院	18	61	6.0	6.0
2	鲍江宏	华南理工大学数学科学学院	12	74	5.0	8.0