• Previous Article
    A trust-region filter-SQP method for mathematical programs with linear complementarity constraints
  • JIMO Home
  • This Issue
  • Next Article
    Global convergence of an inexact operator splitting method for monotone variational inequalities
October  2011, 7(4): 1027-1039. doi: 10.3934/jimo.2011.7.1027

Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems

1. 

Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC 27606, United States

2. 

Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Received  October 2010 Revised  July 2011 Published  August 2011

In this paper, we study a mixed integer constrained quadratic programming problem. This problem is NP-Hard. By reformulating the problem to a box constrained quadratic programming and solving the reformulated problem, we can obtain a global optimal solution of a sub-class of the original problem. The reformulated problem may not be convex and may not be solvable in polynomial time. Then we propose a solvability condition for the reformulated problem, and discuss methods to construct a solvable reformulation for the original problem. The reformulation methods identify a solvable subclass of the mixed integer constrained quadratic programming problem.
Citation: Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027
References:
[1]

K. Allemand, K. Fukuda, T. M. Liebling and E. Steiner, A polynomial case of unconstrained zero-one quadratic optimization,, Math. Program, 91 (2001), 49.   Google Scholar

[2]

A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications," 2nd edition,, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 15 (2003).   Google Scholar

[3]

A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem,, European Journal of Operational Research, 92 (1996), 310.  doi: 10.1016/0377-2217(94)00229-0.  Google Scholar

[4]

A. Billionnet, A. Faye and E. Soutif, A new upper bound for the 0-1 quadratic knapsack problem,, European Journal of Operational Research, 113 (1999), 664.  doi: 10.1016/S0377-2217(97)00414-1.  Google Scholar

[5]

D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems,, Math. Program, 74 (1996), 121.  doi: 10.1007/BF02592208.  Google Scholar

[6]

I. M. Bomze, Global optimization: A quadratic programming perspective,, in, 1989 (2010), 1.   Google Scholar

[7]

I. M. Bomze and F. Jarre, A note on Burer's copositive representation of mixed-binary QPs,, Optimization Letter, 4 (2010), 465.  doi: 10.1007/s11590-010-0174-1.  Google Scholar

[8]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Math. Program., 120 (2009), 479.  doi: 10.1007/s10107-008-0223-z.  Google Scholar

[9]

S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs,", Manuscript, (2008).   Google Scholar

[10]

S.-C. Fang, D. Y. Gao, R.-L. Sheu and S.-Y. Wu, Canonical dual approach to solving 0-1 quadratic programming problems,, Journal of Industrial and Management Optimization, 4 (2008), 125.   Google Scholar

[11]

D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization,, J. Global Optimization, 17 (2000), 127.  doi: 10.1023/A:1026537630859.  Google Scholar

[12]

D. Y. Gao, Advances in canonical duality theory with applications to global optimization,, Available from: \url{http://www.math.vt.edu/people/gao/papers/focapo08.pdf}., ().   Google Scholar

[13]

M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness,", A Series of Books in the Mathematical Sciences, (1979).   Google Scholar

[14]

G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography,", Computer Science and Applied Mathematics. Academic Press, (1980).   Google Scholar

[15]

V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions,, Math. Program., 110 (2007), 521.  doi: 10.1007/s10107-006-0012-5.  Google Scholar

[16]

E. de Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming,, SIAM J. Optim., 12 (2002), 875.  doi: 10.1137/S1052623401383248.  Google Scholar

[17]

C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems,, working paper, (2010).   Google Scholar

[18]

C. Lu, Z. Wang, W. Xing and S.-C. Fang, Extended canonical duality and conic programming for solving 0-1 quadratic programming problems,, Journal of Industrial and Management Optimization, 6 (2010), 779.  doi: 10.3934/jimo.2010.6.779.  Google Scholar

[19]

C. Lemaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint,, in, 54 (2001), 119.   Google Scholar

[20]

J. B. Lasserre, Global optimization with polynomials and the problem of moments,, SIAM J. Optimization, 11 (): 796.  doi: 10.1137/S1052623400366802.  Google Scholar

[21]

P. Lötstedt, Solving the minimal least squares problem subject to bounds on the variables,, BIT, 24 (1984), 206.   Google Scholar

[22]

P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization,", Ph.D. Thesis, (2000).   Google Scholar

[23]

J. F. Strum and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[24]

X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming,, Available from: \url{http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf}., ().   Google Scholar

[25]

Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Global extremal conditions for multi-integer quadratic programming,, J. Industrial and Management Optimization, 4 (2008), 213.  doi: 10.3934/jimo.2008.4.213.  Google Scholar

[26]

L. F. Zuluage, J. Vera and J. Peña, LMI approximations for cones of positive semidefinite forms,, SIAM J. Optimization, 16 (2006), 1076.   Google Scholar

show all references

References:
[1]

K. Allemand, K. Fukuda, T. M. Liebling and E. Steiner, A polynomial case of unconstrained zero-one quadratic optimization,, Math. Program, 91 (2001), 49.   Google Scholar

[2]

A. Ben-Israel and T. N. E. Greville, "Generalized Inverses: Theory and Applications," 2nd edition,, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 15 (2003).   Google Scholar

[3]

A. Billionnet and F. Calmels, Linear programming for the 0-1 quadratic knapsack problem,, European Journal of Operational Research, 92 (1996), 310.  doi: 10.1016/0377-2217(94)00229-0.  Google Scholar

[4]

A. Billionnet, A. Faye and E. Soutif, A new upper bound for the 0-1 quadratic knapsack problem,, European Journal of Operational Research, 113 (1999), 664.  doi: 10.1016/S0377-2217(97)00414-1.  Google Scholar

[5]

D. Bienstock, Computational study of a family of mixed-integer quadratic programming problems,, Math. Program, 74 (1996), 121.  doi: 10.1007/BF02592208.  Google Scholar

[6]

I. M. Bomze, Global optimization: A quadratic programming perspective,, in, 1989 (2010), 1.   Google Scholar

[7]

I. M. Bomze and F. Jarre, A note on Burer's copositive representation of mixed-binary QPs,, Optimization Letter, 4 (2010), 465.  doi: 10.1007/s11590-010-0174-1.  Google Scholar

[8]

S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs,, Math. Program., 120 (2009), 479.  doi: 10.1007/s10107-008-0223-z.  Google Scholar

[9]

S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs,", Manuscript, (2008).   Google Scholar

[10]

S.-C. Fang, D. Y. Gao, R.-L. Sheu and S.-Y. Wu, Canonical dual approach to solving 0-1 quadratic programming problems,, Journal of Industrial and Management Optimization, 4 (2008), 125.   Google Scholar

[11]

D. Y. Gao, Canonical dual transformation method and generalized triality theory in nonsmooth global optimization,, J. Global Optimization, 17 (2000), 127.  doi: 10.1023/A:1026537630859.  Google Scholar

[12]

D. Y. Gao, Advances in canonical duality theory with applications to global optimization,, Available from: \url{http://www.math.vt.edu/people/gao/papers/focapo08.pdf}., ().   Google Scholar

[13]

M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness,", A Series of Books in the Mathematical Sciences, (1979).   Google Scholar

[14]

G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography,", Computer Science and Applied Mathematics. Academic Press, (1980).   Google Scholar

[15]

V. Jeyakumar, A. M. Rubinov and Z. Y. Wu, Non-convex quadratic minimization problems with quadratic constraints: Global optimality conditions,, Math. Program., 110 (2007), 521.  doi: 10.1007/s10107-006-0012-5.  Google Scholar

[16]

E. de Klerk and D. V. Pasechnik, Approximation of the stability number of a graph via copositive programming,, SIAM J. Optim., 12 (2002), 875.  doi: 10.1137/S1052623401383248.  Google Scholar

[17]

C. Lu, S.-C. Fang, Q. Jin, Z. Wang and W. Xing, KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems,, working paper, (2010).   Google Scholar

[18]

C. Lu, Z. Wang, W. Xing and S.-C. Fang, Extended canonical duality and conic programming for solving 0-1 quadratic programming problems,, Journal of Industrial and Management Optimization, 6 (2010), 779.  doi: 10.3934/jimo.2010.6.779.  Google Scholar

[19]

C. Lemaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint,, in, 54 (2001), 119.   Google Scholar

[20]

J. B. Lasserre, Global optimization with polynomials and the problem of moments,, SIAM J. Optimization, 11 (): 796.  doi: 10.1137/S1052623400366802.  Google Scholar

[21]

P. Lötstedt, Solving the minimal least squares problem subject to bounds on the variables,, BIT, 24 (1984), 206.   Google Scholar

[22]

P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization,", Ph.D. Thesis, (2000).   Google Scholar

[23]

J. F. Strum and S. Zhang, On cones of nonnegative quadratic functions,, Mathematics of Operations Research, 28 (2003), 246.  doi: 10.1287/moor.28.2.246.14485.  Google Scholar

[24]

X. Sun, C. Liu, D. Li and J. Gao, On duality gap in binary quadratic programming,, Available from: \url{http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf}., ().   Google Scholar

[25]

Z. Wang, S.-C. Fang, D. Y. Gao and W. Xing, Global extremal conditions for multi-integer quadratic programming,, J. Industrial and Management Optimization, 4 (2008), 213.  doi: 10.3934/jimo.2008.4.213.  Google Scholar

[26]

L. F. Zuluage, J. Vera and J. Peña, LMI approximations for cones of positive semidefinite forms,, SIAM J. Optimization, 16 (2006), 1076.   Google Scholar

[1]

Anton Schiela, Julian Ortiz. Second order directional shape derivatives of integrals on submanifolds. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021017

[2]

Qian Liu. The lower bounds on the second-order nonlinearity of three classes of Boolean functions. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020136

[3]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397

[4]

Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

[5]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

[6]

Zemer Kosloff, Terry Soo. The orbital equivalence of Bernoulli actions and their Sinai factors. Journal of Modern Dynamics, 2021, 17: 145-182. doi: 10.3934/jmd.2021005

[7]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[8]

Y. Latushkin, B. Layton. The optimal gap condition for invariant manifolds. Discrete & Continuous Dynamical Systems - A, 1999, 5 (2) : 233-268. doi: 10.3934/dcds.1999.5.233

[9]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[10]

Mansour Shrahili, Ravi Shanker Dubey, Ahmed Shafay. Inclusion of fading memory to Banister model of changes in physical condition. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 881-888. doi: 10.3934/dcdss.2020051

[11]

Yizhuo Wang, Shangjiang Guo. A SIS reaction-diffusion model with a free boundary condition and nonhomogeneous coefficients. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1627-1652. doi: 10.3934/dcdsb.2018223

[12]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[13]

Alexandre B. Simas, Fábio J. Valentim. $W$-Sobolev spaces: Higher order and regularity. Communications on Pure & Applied Analysis, 2015, 14 (2) : 597-607. doi: 10.3934/cpaa.2015.14.597

[14]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094

[15]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212

[16]

Pavel I. Naumkin, Isahi Sánchez-Suárez. Asymptotics for the higher-order derivative nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2021028

[17]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617

[18]

Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206

[19]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825

[20]

A. Aghajani, S. F. Mottaghi. Regularity of extremal solutions of semilinaer fourth-order elliptic problems with general nonlinearities. Communications on Pure & Applied Analysis, 2018, 17 (3) : 887-898. doi: 10.3934/cpaa.2018044

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (36)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]