\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 90C26, 90C20, 90C11; Secondary: 49M37.

    Citation:

    \begin{equation} \\ \end{equation}
  • [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-52.

    [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, Springer-Verlag, New York, 2003.

    [3]

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

    [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-672.doi: 10.1016/S0377-2217(97)00414-1.

    [5]

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

    [6]

    I. M. Bomze, Global optimization: A quadratic programming perspective, in "Nonlinear Optimization," Lecture Notes in Mathematics, 1989, Springer, Berlin, (2010), 1-53.

    [7]

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

    [8]

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

    [9]

    S. Bundfuss and M. Dür, "An Adaptive Linear Approximation Algorithm for Copositive Programs," Manuscript, Department of Mathematics, Technische Universitat Darmstadt, Darmstadt, Germany, 2008.

    [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-142.

    [11]

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

    [12]

    D. Y. GaoAdvances in canonical duality theory with applications to global optimization, Available from: http://www.math.vt.edu/people/gao/papers/focapo08.pdf.

    [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, W. H. Freeman and Co., San Francisco, CA, 1979.

    [14]

    G. T. Herman, "Image Reconstruction from Projections: The Fundamentals of Computerized Tomography," Computer Science and Applied Mathematics. Academic Press,Inc., New York-London, 1980.

    [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-541.doi: 10.1007/s10107-006-0012-5.

    [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-892.doi: 10.1137/S1052623401383248.

    [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.

    [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-793.doi: 10.3934/jimo.2010.6.779.

    [19]

    C. Lemaréchal and F. Oustry, SDP relaxations in combinatorial optimization from a Lagrangian viewpoint, in "Advances in Convex Analysis and Global Optimization" (eds. N. Hadijsavvas and P. M. Paradalos), Nonconvex Optim. Appl., 54, Kluwer Acad. Publ., Dordrecht, (2001), 119-134.

    [20]

    J. B. LasserreGlobal optimization with polynomials and the problem of moments, SIAM J. Optimization, 11 (2001/01), 796-817. doi: 10.1137/S1052623400366802.

    [21]

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

    [22]

    P. Parrilo, "Structured Semidefinite Programs and Semi-Algebraic Geometry Methods in Robustness and Optimization," Ph.D. Thesis, California Institute of Technology, 2000.

    [23]

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

    [24]

    X. Sun, C. Liu, D. Li and J. GaoOn duality gap in binary quadratic programming, Available from: http://www.optimization-online.org/DB_FILE/2010/01/2512.pdf.

    [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-225.doi: 10.3934/jimo.2008.4.213.

    [26]

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

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(129) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return