作　　者： ; ;

机构地区： 复旦大学管理学院

出　　处： 《运筹学学报》 2014年第1期39-68,共30页

摘　　要： 整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究,是运筹学和管理科学中应用最广泛的优化模型之一.首先简要回顾整数规划的历史和发展进程,概述线性和非线性整数规划的一些经典方法.然后着重讨论整数规划若干新进展,包括0-1二次规划的半定规划(SDP)松弛和随机化方法,带半连续变量和稀疏约束的优化问题的整数规划模型和方法,以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划(SDP)逼近.最后,对整数规划未来研究方向进行展望并对一些公开问题进行讨论. Integer programming deals with optimization problems with decision vari- ables being all integer or partly integer. Integer programming has been one of the most ac- tive research directions in optimization due to its wide applications in operations research and management science. In this survey paper, we first briefly review the background of integer programming and summarize the fundamental results of linear and nonlin- ear integer programming. We then focus on some recent progress in several research topics, including semi-definite programming relaxation and randomized methods for 0-1 quadratic programs, optimization problems with cardinality and semi-continuous vari- ables, and co-positive cone program representations and approximations of 0-1 quadratic programs. Finally, we indicate some research perspectives and open problems in integer programming.

关 键 词： 整数规划 二次规划 半定规划 方法 半连续变量和稀疏约束 协正锥 规划 协正锥半定规划 层级逼近

领　　域： [理学] [理学]