整数规划新进展

摘要/Abstract

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

关键词: 整数规划, 0-1二次规划, 半定规划 (SDP) 方法, 半连续变量和稀疏约束, 协正锥规划, 协正锥半定规划 (SDP) 层级逼近

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.

Key words: integer programming, 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

中图分类号:

O221.4

孙小玲，李端. 整数规划新进展[J]. 运筹学学报, 2014, 18(1): 39-68.

SUN Xiaoling, LI Duan. Recent advances in integer programming[J]. Operations Research Transactions, 2014, 18(1): 39-68.

参考文献

Dantzig G B, Fulkerson D R, Johnson S M. Solution of a large-scale traveling salesman problem [J]. Operations Research, 1954, 2: 393-410.

Gomory R E. Outline of an algorithm for integer solutions to linear programs [J]. Bulletin of the American Mathematical Society, 1958, 64: 275-278.

Garey M R, Johnson D S. Computer and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: Freeman, 1979.

Schrijver A. Theory of Linear and Integer Programming [M]. New York: Wiley, 1986.

Nemhauser G L, Wolsey L A. Integer and Combinatorial Optimization [M]. New York: Wiley, 1988.

Wolsey L A. Integer Programming [M]. New York: Wiley, 1998.

Nemhauser G L, Wolsey L A. Integer and Combinatorial Optimization [M]. New York: Wiley, 1988.
孙小玲, 李端. 整数规划 [M]. 北京: 科学出版社, 2010.

J\"unger M, Liebling T, Naddef D, et al. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art [M]. Berlin: Springer-Verlag, 2010.

Barnhart C, Johnson E L, Nemhauser G L, et al. Branch-and-price: Column generation for solving huge integer programs [J]. Operations Research, 1998, 46: 316-329.

Lenstra H W. Integer programming with a fixed number of variables [J]. Mathematics of Operations Research, 1983, 8: 538-548.

Li D, Sun X L. Nonlinear Integer Programming [M]. New York: Springer-Verlag, 2006.

Goemans M X, Williamson D P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J]. Journal of the ACM, 1995, 42: 1115-1145.

Lasserre J B. Global optimization with polynomials and the problem of moments [J]. SIAM Journal on Optimization, 2001, 11: 796-817.

Parrilo P A. Semidefinite programming relaxations for semialgebraic problems [J]. Mathematical Programming, 2003, 96: 293-320.

Vandenberghe L, Boyd S. Semidefinite programming [J]. SIAM Review, 1996, 38: 49-95.

Ye Y. A 699-approximation algorithm for Max-Bisection [J]. Mathematical Programming, 2001, 90: 101-111.

方述诚, 邢文训. 线性锥优化 [M]. 北京: 科学出版社, 2013.

Nesterov Y. Semidefinite relaxation and nonconvex quadratic optimization [J]. Optimization Methods and Software, 1998, 9: 141-160.

Ye Y. Approximating quadratic programming with bound and quadratic constraints [J]. Mathematical Programming, 1999, 84: 219-226.

Frieze A, Jerrum M. Improved approximation algorithms for max k-cut and max bisection [J]. Algorithmica, 1997, 18: 67-81.

Ye Y. A 699-approximation algorithm for Max-Bisection [J]. Mathematical Programming, 2001, 90: 101-111.

Halperin E, Zwick U. A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems [J]. Random Structures \rm \& Algorithms, 2002, 20: 382-402.

Bienstock D. Computational study of a family of mixed-integer quadratic programming problems [J]. Mathematical Programming, 1996, 74: 121-140.

Gao J J, Li D. A polynomial case of the cardinality-constrained quadratic optimization problem [J]. Journal of Global Optimization, 2013, 56: 1441-1455.

Bonami P, Lejeune M A. An exact solution approach for portfolio optimization problems under stochastic and integer constraints [J]. Operations Research, 2009, 57: 650-670.

Bertsimas D, Shioda R. Algorithm for cardinality-constrained quadratic optimization [J]. Computional Optimization and Applications, 2009, 43: 1-22.

Cui X T, Zheng X J, Zhu S S, et al. Convex relaxations and MIQCQP reformulations for a class of cardinality-constrained portfolio selection problems [J]. Journal of Global Optimization, 2013, 56: 1409-1423.

Li D, Sun X L, Wang J. Optimal lot solution to cardinality constrained mean-variance formulation for portfolio selection [J]. Mathematical Finance, 2006, 16: 83-101.

Shaw D X, Liu S, Kopman L. Lagrangian relaxation procedure for cardinality-constrained portfolio optimization [J]. Optimizaion Methods and Software, 2008, 23: 411-420.

Cesarone F, Scozzari A, Tardella F. Efficient algorithms for mean-variance portfolio optimization with hard real-world constraints [J]. Giornale dell'Istituto Italiano degli Attuari, 2009, 72: 37-56.

Blog B, Hoek Van der G, Rinnooy Kan A H G, et al. The optimal selection of small portfolios [J]. Management Science, 1983, 29: 792-798.

Jacob N L. A limited-diversification portfolio selection model for the small investor [J]. Journal of Finance, 1974, 29: 847-856.

Jobst N J, Horniman M D, Lucas C A, et al. Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints [J]. Quantitative Finance, 2001, 1: 489-501.

Mitra G, Ellison F, Scowcroft A. Quadratic programming for portfolio planning: insights into algorithmic and computational issues. part II: Processing of portfolio planning models with discrete constraints [J]. Journal of Asset Management, 2007, 8: 249-258.

Xie J, He S, Zhang S. Randomized portfolio selection, with constraints [J]. Pacific Journal of Optimization, 2008, 4: 89-112.

Frangioni A, Gentile C. Perspective cuts for a class of convex 0-1 mixed integer programs [J]. Mathematical Programming, 2006, 106: 225-236.

Frangioni A, Gentile C, Lacalandra F. Tighter approximated MILP formulations for unit commitment problems [J]. IEEE Transactions on Power Systems, 2009, 24: 105-113.

Frangioni A, Gentile C. SDP diagonalizations and perspective cuts for a class of nonseparable MIQP [J]. Operations Research Letters, 2007, 35: 181-185.

Frangioni A, Gentile C. A computational comparison of reformulations of the perspective relaxation: SOCP vs. cutting planes [J]. Operations Research Letters, 2009, 37: 206-210.

G\"unl\"uk O, Linderoth J. Perspective reformulations of mixed integer nonlinear programs with indicator variables [J]. Mathematical Programming, 2010, 124: 183-205.

Hiriart-Urruty J B, Lemar\'echal C. Convex Analysis and Minimization Algorithms: Fundamentals [M]. New York: Springer-Verlag, 1993.

Alizadeh F, Goldfarb D. Second-order cone programming [J]. Mathematical Programming, 2003, 95: 3-51.

Ben-Tal A, A S Nemirovski. Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications [J]. MPS-SIAM Series on Optimization. Society for Industrial Mathematics, 2001.

Zheng X J, Sun X L, Li D. Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach [J]. INFORMs Journal on Computing, 2013. To appear.

Frangioni A, Gentile C, Grande E, et al. Projected perspective reformulations with applications in design problems [J]. Operations Research, 2011, 59: 1225-1232.

Farias Jr de I R, Zhao M. A polyhedral study of the semi-continuous knapsack problem [J]. Mathematical Programming, 2012, Doi: 10.1007/s10107-012-0566-3.

Farias Jr de I R, Nemhauser G L. A polyhedral study of the cardinality constrained knapsack problem [J]. Mathematical Programming, 2003, 96: 439-467.

Gao J J, Li D. Optimal cardinality constrained portfolio selection [J]. Operations Research, 2013, 61: 745-761.

Jansen R, Dijk Van R. Optimal benchmark tracking with small portfolios [J]. The Journal of Portfolio Management, 2002, 28: 33-39.

文再文, 印卧涛, 刘歆, 等. 压缩感知和稀疏优化简介~[J]. 运筹学学报, 2012, 16(3): 49-64.

Bach F, Ahipasaoglu S D, d'Aspremont A. Convex relaxations for subset selection [J]. arXiv preprint, arXiv: 1006.3601, 2010.

Jokar S, Pfetsch M E. Exact and approximate sparse solutions of underdetermined linear equations [J]. SIAM Journal on Scientific Computing, 2008, 31: 23-44.

Bruckstein A M, Donoho D L, Elad M. From sparse solutions of systems of equations to sparse modeling of signals and images [J]. SIAM Review, 2009, 51: 34-81.

Donoho D L, Huo X. Uncertainty principles and ideal atomic decomposition [J]. IEEE Transactions on Information Theory, 2001, 47: 2845-2862.

Cand\`es E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information [J]. IEEE Transactions on Information Theory, 2006, 52: 489-509.

Ge D, Jiang X, Ye Y. A note on complexity of l_p minimization [J]. Mathematical Programming, 2011, 129: 285-299.

Lai M J, Wang J. An unconstrained \ell_q minimization with 0< q\le 1 for sparse solution of under-determined linear systems [J]. SIAM Journal on Optimization, 2010, 21: 82-101.

Fung G M, Mangasarian O L. Equivalence of minimal \ell_0-and \ell_p-norm solutions of linear equalities, inequalities and linear programs for sufficiently small p [J]. Journal of Optimization Theory and Applications, 2011, 151: 1-10.

Chen X, Ge D, Wang Z, et al. Complexity of unconstrained l_2-l_p minimization [J]. Mathematical Programming, 2014, 143(1-2): 371-383.

Chen X, Xu F, Ye Y. Lower bound theory of nonzero entries in solutions of l_2-l_p minimization [J]. SIAM Journal on Scientific Computing, 2010, 32: 2832-2852.

Mangasarian O L. Minimum-support solutions of polyhedral concave programs [J]. Optimization, 1999, 45: 149-162.

Zheng X J, Sun X L, Li D, et al. Successive convex approximations to cardinality-constrained convex programs: A piecewise-linear DC approach [J]. Computational Optimization and Applications, 2013, Doi: 10.1007/s10589-013-9582-3.

Goldstein S, Osher and T. The split Bregman method for \ell_1-regularized problems [J]. SIAM Journal on Imaging Sciences, 2009, 2: 323-343.

Yin W T, Osher S, Goldfarb D, et al. Bregman iterative algorithms for \ell_1-minimization with applications to compressed sensing [J]. SIAM Journal on Imaging Sciences, 2008, 1: 143-168.

B S He, M Tao, X M Yuan. Alternating direction method with Gaussian back substitution for separable convex programming [J]. SIAM Journal on Optimization, 2012, 22: 313-340.

Shen Y, Wen Z Z, Zhang Y. Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization [J]. Optimization Methods and Software, 2012, 29: 239-263.

Wen Z W, Peng X H, Liu X, et al. Asset allocation under the Basel Accord risk measures [O]. Technical report, 2013, Available at: http: //www. optimization-online. org/DB_-FILE/2013/01/3730.pdf.

Bai X D, Sun J, Sun X L, et al. An alternating direction method for chance-constrained optimization problems with discrete distributions [O]. Technical report, School of Management, Fudan University, 2012. http: //www.optimization-online.org/DB_-FILE/2012/04/3448.pdf.

Cui X T, Zhu S S, Sun X L, et al. Portfolio selection with nonparametric value-at-risk [R]. Technical report, School of Management, Fudan University, 2013.

Lu Z, Zhang Y. Penalty decomposition methods for rank minimization [C]//Advances in Neural Information Processing Systems, 2011, 46-54.

Lu Z, Zhang Y. Sparse approximation via penalty decomposition methods [J]. SIAM Journal on Optimization, 2013, 23(4), 2448–2478.

Zheng X J, Sun X L. Alternating direction methods for mathematical programs with cardinality constraint and semicontinuous variables [R]. Technical report, School of Management, Fudan University, 2013.

Sturm J F, Zhang S Z. On cones of nonnegative quadratic functions [J]. Mathematics of Operations Research, 2003, 28: 246-267.

Burer S. On the copositive representation of binary and continuous nonconvex quadratic programs [J]. Mathematical Programming, 2009, 120: 479-495.

Murty K G, Kabadi S N. Some NP-complete problems in quadratic and nonlinear programming [J]. Mathematical Programming, 1987, 39: 117-129.

Parrilo P A. Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization [D]. Pasadena: California Institute of Technology, 2000.

Klerk de E, Pasechnik D V. Approximation of the stability number of a graph via copositive programming [J]. SIAM Journal on Optimization, 2002, 12: 875-892.

Bomze I M, Klerk de E. Solving standard quadratic optimization problems via linear, semidefinite and copositive programming [J]. Journal of Global Optimization, 2002, 24: 163-185.
Quist A J, Klerk de E, Roos C, et al. Copositive realxation for genera quadratic programming [J]. Optimization Methods and Software, 1998, 9: 185-208.

Berman A, Shaked-Monderer N. Completely Positive Matrices [M]. Singapore: World Scientific Publishing, 2003.

Bomze I M, D\"ur M, Klerk de E, et al. On copositive programming and standard quadratic optimization problems [J]. Journal of Global Optimization, 2000, 18: 301-320.

Dong H B, Anstreicher K. A note on 5\times 5 completely positive matrices [J]. Linear Algebra and its Applications, 2010, 433: 1001-1004.

Dong H B, Anstreicher K. Separating doubly nonnegative and completely positive matrices [J]. Mathematical Programming, 2013, 137: 131-153.

Lasserre J B. New approximations for the cone of copositive matrices and its dual [J]. Mathematical Programming, 2013, Doi: 10.1007/s10107-013-0632-5.

Deng Z B, Fang S C, Jin Q W, et al. Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme [J]. European Journal of Operational Research, 2013, 229: 21-28.

Tian Y, Fang S C, Deng Z B, et al. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming [J]. Management, 2013, 9: 703-721.

[1]	孙鑫, 葛冬冬, 付德生, 魏志伟, 董丰莲, 潘师畅. 针对炼油厂系统性运营优化问题的混合分布递归及分支定界算法[J]. 运筹学学报（中英文）, 2025, 29(4): 141-158.
[2]	黄诗语, 陈亮, 寇彩霞. 分段线性的不可分流弧集多面体研究[J]. 运筹学学报（中英文）, 2024, 28(4): 101-110.
[3]	徐博, 马卫民, 柯华, 张浩. 基于秩2矩阵近似的飞机起降多目标调度模型与算法研究[J]. 运筹学学报（中英文）, 2024, 28(4): 29-43.
[4]	兰艳, 丁宁, 李嘉鑫, 元文学, 张明会, 韩鑫. 新中考中的排课问题[J]. 运筹学学报（中英文）, 2021, 25(4): 111-119.
[5]	沈吟东, 钱壮, 李媛媛. 公共交通驾驶员调度研究综述[J]. 运筹学学报, 2021, 25(1): 1-16.
[6]	赵丹, 高岳林. 非线性整数规划问题的无参数填充函数算法[J]. 运筹学学报, 2020, 24(4): 63-73.
[7]	郑宇军, 吴晨昕, 陈恩富, 卢雪琴, 张敏霞. 新冠肺炎疫情条件下的企业复工复产优化规划方法[J]. 运筹学学报（中英文）, 2020, 24(3): 43-56.
[8]	杨沐明, 黄亚魁, 戴彧虹. 一类多商品设施选址问题的基于线性松弛解的启发式方法[J]. 运筹学学报, 2019, 23(3): 15-26.
[9]	陈薪蓓, 朱明康, 陈建利. 基于迭代投影的梯度硬阈值追踪算法[J]. 运筹学学报, 2019, 23(1): 1-14.
[10]	朱征露, 鲁习文. 带学习效应的两台平行机时间表长问题[J]. 运筹学学报, 2018, 22(1): 55-66.
[11]	吴佩佩, 高岳林. 一个新的非线性整数规划问题的单参数填充函数算法[J]. 运筹学学报, 2017, 21(3): 111-118.
[12]	董振宇, 冯恩民, 尹洪超, 张誉铎. 国际原油价格预测的双层随机整数规划模型、算法及应用[J]. 运筹学学报, 2015, 19(3): 18-25.
[13]	何胜学. 无预警紧急疏散中公交车辆路径的确定方法[J]. 运筹学学报, 2014, 18(3): 47-59.
[14]	孙小玲, 白晓迪, 郑小金. 概率约束最优化问题[J]. 运筹学学报, 2012, 16(3): 65-74.
[15]	田静, 吴至友, J. Ugon. 一类特殊多项式整数规划问题的最优化算法[J]. 运筹学学报, 2011, 15(4): 23-35.