整数规划的新算法  

Polynomial Algorithm for Integer Programming with a Fixed Number of Variables

作　　者：李肯立[1] 李庆华[1] 

机构地区：[1]湖南大学计算机与通讯学院,湖南长沙410082

出　　处：《小型微型计算机系统》2004年第7期1298-1302,共5页Journal of Chinese Computer Systems

基　　金：国家"8 63"高技术研究发展规划 (863 -3 06-ZD11-0 1-6)资助;国家高性能计算基金资助

摘　　要：整数规划是 NP困难的经典问题之一 ,将传统的二分搜索方法推广应用到整数规划的解空间中 ,提出一种求解整数规划的新算法 .当问题变量数固定时 ,算法的时间复杂性为 O(L log L ) ,其中 L 为问题实例的输入规模 .理论分析和实验结果表明 :新算法不仅初步解决了目前求解系数呈指数增长的整数规划问题时存在的实质性困难 ,可直接用于此类大规模问题的求解 .同时由于其特别适合并行处理的算法结构 。Integer Programming is a famous NP hard problem. This paper presents a new algorithm, in which the method of similar dimidiate is adopted. When the dimension of problem is fixed, the complexity of the new algorithm is O(Llog L) where L is the input length of the problem instance. Theoretical analysis and experimental results show that it not only overcomes the hardness in solution of the problem with exponentially growing coefficients. But can be expected to supply a new method for the solution of general large scale problem because of its high parallelism.

关 键 词：整数规划 算法复杂性 类二分方法 NP-HARD 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]