整数规划新进展

Abstract

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

CLC Number:

O221.4

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

References

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]	YANG Muming, HUANG Yakui, DAI Yuhong. Linear relaxation solution based heuristics for a class of multi-product facility location problems [J]. Operations Research Transactions, 2019, 23(3): 15-26.
[2]	ZHU Zhenglu, LU Xiwen. Minimizing makespan on two parallel machines with learning effects [J]. Operations Research Transactions, 2018, 22(1): 55-66.
[3]	WU Peipei, GAO Yuelin. A new single parameter filled function method for nonlinear integer programming [J]. Operations Research Transactions, 2017, 21(3): 111-118.
[4]	DONG Zhenyu, FENG Enmin, YIN Hongchao, ZHANG Yuduo. International crude prices forecast of double random integer programming model,algorithm and application [J]. Operations Research Transactions, 2015, 19(3): 18-25.
[5]	SUN Xiaoling, BAI Xiaodi, ZHENG Xiaojin. A survey on probabilistically constrained optimization problems [J]. Operations Research Transactions, 2012, 16(3): 65-74.
[6]	TIAN Jing, WU Zhi-You, J. Ugon. Optimization Methods for a Class of Integer Polynomial Programming Problems [J]. Operations Research Transactions, 2011, 15(4): 23-35.

Recent advances in integer programming

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 6

Recommended Articles

Metrics

Comments