×

Parametric convex quadratic relaxation of the quadratic knapsack problem. (English) Zbl 1430.90452

Summary: We consider a parametric convex quadratic programming (CQP) relaxation for the quadratic knapsack problem (QKP). This relaxation maintains partial quadratic information from the original QKP by perturbing the objective function to obtain a concave quadratic term. The nonconcave part generated by the perturbation is then linearized by a standard approach that lifts the problem to matrix space. We present a primal-dual interior point method to optimize the perturbation of the quadratic function, in a search for the tightest upper bound for the QKP. We prove that the same perturbation approach, when applied in the context of semidefinite programming (SDP) relaxations of the QKP, cannot improve the upper bound given by the corresponding linear SDP relaxation. The result also applies to more general integer quadratic problems. Finally, we propose new valid inequalities on the lifted matrix variable, derived from cover and knapsack inequalities for the QKP, and present separation problems to generate cuts for the current solution of the CQP relaxation. Our best bounds are obtained alternating between optimizing the parametric quadratic relaxation over the perturbation and applying cutting planes generated by the valid inequalities proposed.

MSC:

90C20 Quadratic programming
90C10 Integer programming
90C27 Combinatorial optimization

Software:

Knapsack
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Armand, P.; Gilbert, J. C.; Jégou, S. J., A feasible BFGS interior point algorithm for solving convex minimization problems, SIAM Journal on Optimization, 11, 1, 199-222 (2000) · Zbl 0990.90092
[2] Atamtürk, A., Cover and pack inequalities for (mixed) integer programming, Annals of Operations Research, 139, 1, 21-38 (2005) · Zbl 1091.90053
[3] Balas, E., Facets of the knapsack polytope, Mathematical Programming, 8, 1, 146-164 (1975) · Zbl 0316.90046
[4] Balas, E.; Zemel, E., Facets of the knapsack polytope from minimal covers, SIAM Journal on Applied Mathematics, 34, 1, 119-148 (1978) · Zbl 0385.90083
[5] Billionnet, A.; Calmels, F., Linear programming for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 92, 2, 310-325 (1996) · Zbl 0912.90221
[6] Billionnet, A.; Elloumi, S.; Lambert, A., Extending the QCR method to the case of general mixed integer programs, Mathematical Programming, 131, 1, 381-401 (2012) · Zbl 1235.90100
[7] Billionnet, A.; Elloumi, S.; Lambert, A., Exact quadratic convex reformulations of mixed-integer quadratically constrained problems, Mathematical Programming, 158, 1-2, 235-266 (2016) · Zbl 1358.90082
[8] Billionnet, A.; Elloumi, S.; Plateau, M., Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method, Discrete Applied Mathematics, 157, 6, 1185-1197 (2009) · Zbl 1169.90405
[9] Billionnet, A.; Faye, A.; Soutif, E., A new upper bound for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 112, 3, 664-672 (1999) · Zbl 0933.90049
[10] Caprara, A.; Pisinger, D.; Toth, P., Exact solution of the quadratic knapsack problem, INFORMS Journal on Computing, 11, 2, 125-137 (1999) · Zbl 1034.90521
[11] Chaillou, P.; Hansen, P.; Mahieu, Y., Best network flow bounds for the quadratic knapsack problem, (Simeone, B., Combinatorial optimization: Lectures given at the 3rd session of the centro internazionale matematico estivo (C.I.M.E.) Held at Como, Italy (1989), Springer: Springer Berlin, Heidelberg), 225-235
[12] Cunha, J. O.; Simonetti, L.; Lucena, A., Lagrangian heuristics for the quadratic knapsack problem, Computational Optimization and Applications, 63, 1, 97-120 (2016) · Zbl 1342.90159
[13] Danskin, J. M., The theory of max-min, with applications, SIAM Journal on Applied Mathematics, 14, 4, 641-664 (1966) · Zbl 0144.43301
[14] Fampa, M.; Lee, J.; Melo, W., On global optimization with indefinite quadratics, EURO Journal on Computational Optimization, 5, 3, 309-337 (2017) · Zbl 1384.90075
[15] Fiacco, A. V., Introduction to sensitivity and stability analysis in nonlinear programming, Mathematics in science and engineering (1983), Academic Press, 165 · Zbl 0543.90075
[16] Gallo, G.; Hammer, P. L.; Simeone, B., Quadratic knapsack problems, (Padberg, M. W., Combinatorial optimization (1980), Springer: Springer Berlin, Heidelberg), 132-149 · Zbl 0462.90068
[17] Gu, Z.; Nemhauser, G. L.; Savelsbergh, M. W.P., Lifted cover inequalities for 0-1 integer programs: Computation, INFORMS Journal on Computing, 10, 4, 427-437 (1998)
[18] Hammer, P. L.; Johnson, E. L.; Peled, U. N., Facet of regular 0-1 polytopes, Mathematical Programming, 8, 1, 179-206 (1975) · Zbl 0314.90064
[19] Helmberg, C.; Rendl, F.; Weismantel, R., Quadratic knapsack relaxations using cutting planes and semidefinite programming, Integer programming and combinatorial optimization (Vancouver, BC, 1996). Integer programming and combinatorial optimization (Vancouver, BC, 1996), Lecture notes in comput. sci., pages 190-203, 1084 (1996), Springer: Springer Berlin · Zbl 1415.90073
[20] Helmberg, C.; Rendl, F.; Weismantel, R., A semidefinite programming approach to the quadratic knapsack problem, Journal of Combinatorial Optimization, 4, 2, 197-215 (2000) · Zbl 0970.90075
[21] Hogan, W. W., The continuity of the perturbation function of a convex program, Operations Research, 21, 351-352 (1973) · Zbl 0265.90042
[22] Horn, R. A.; Zhang, F., Basic properties of the Schur complement, (Zhang, F., The Schur complement and its applications. Numerical methods and algorithms, 4 (2005), Springer: Springer Boston, MA, USA)
[23] Horst, R.; Thoai, N. V., DC programming: Overview, Journal of Optimization Theory and Applications, 103, 1-43 (1999) · Zbl 1073.90537
[24] Jolliffe, I., Principal component analysis (2010), Springer: Springer Berlin · Zbl 1011.62064
[25] Lemarchal, C.; Oustry, F., Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization (1999), INRIA Rhones-Alpes
[26] Lewis, A. S.; Overton, M. L., Nonsmooth optimization via quasi-newton methods, Mathematical Programming, 141, 1, 135-163 (2013) · Zbl 1280.90118
[27] McCormick, G. P., Computability of global solutions to factorable nonconvex programs: part i convex underestimating problems, Mathematical Programming, 10, 147-175 (1976) · Zbl 0349.90100
[28] Michelon, P.; Veillieux, L., Lagrangean methods for the 0-1 quadratic knapsack problem, European Journal of Operational Research, 92, 2, 326-341 (1996) · Zbl 0912.90222
[29] Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization (1988), John Wiley & Sons: John Wiley & Sons New York, NY · Zbl 0652.90067
[30] Pisinger, D., The quadratic knapsack problem: A survey, Discrete Applied Mathematics, 155, 5, 623-648 (2007) · Zbl 1143.90028
[31] Turlach, B. A.; Wright, S. J., Quadratic programming, Wiley interdisciplinary reviews: Computational statistics, 7, 153-159 (2015), John Wiley & Sons, Inc
[32] Wolsey, L. A., Faces for a linear inequality in 0-1 variables, Mathematical Programming, 8, 1, 165-178 (1975) · Zbl 0314.90063
[33] Wolsey, L. A., Integer programming (1998), Wiley-Interscience: Wiley-Interscience New York, NY, USA · Zbl 0930.90072
[34] Zemel, E., Easily computable facets of the knapsack polytope, Mathematics of Operations Research, 14, 4, 760-764 (1989) · Zbl 0689.90057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.