| 整数规划新进展 |
| |
| 引用本文： | 孙小玲,李端. 整数规划新进展[J]. 运筹学学报, 2014, 18(1): 39-68. DOI: 10.1007/s10107-012-0566-3. |
| |
| 作者姓名： | 孙小玲 李端 |
| |
| 作者单位： | 1. 复旦大学管理学院, 上海 200433； 2. 香港中文大学系统工程与工程管理系, 香港新界沙田 |
| |
| 基金项目： | 国家自然科学基金(No.11371103) |
| |
| 摘 要： | 整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.
|
| 关 键 词： | 整数规划 0-1二次规划 半定规划 (SDP) 方法 半连续变量和稀疏约束 协正锥规划 协正锥半定规划 (SDP) 层级逼近 |
Recent advances in integer programming |
| |
| SUN Xiaoling,LI Duan. Recent advances in integer programming[J]. OR Transactions, 2014, 18(1): 39-68. DOI: 10.1007/s10107-012-0566-3. |
| |
| Authors: | SUN Xiaoling LI Duan |
| |
| Affiliation: | 1. School of Management, Fudan University, Shanghai 200433, China; 2. Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N. T., Hong Kong, China |
| |
| Abstract: | 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. |
| |
| Keywords: | 0-1 quadratic programming positive semi-definite programming (SDP method semicontinuous variables and cardinality constraint copositive cone program hierarchies of SDP approximation to copositive cone |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
|
点击此处可从《运筹学学报》下载全文 |
|
