整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.

Recent advances in integer programming

Integer programming deals with optimization problems with decision variables being all integer or partly integer. Integer programming has been one of the most active 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 nonlinear 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 variables, 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.