Parametric convex quadratic relaxation of the quadratic knapsack problem

作     者：Fampa, M. Lubke, D. Wang, F. Wolkowicz, H. 

作者机构：Univ Fed Rio de Janeiro PESC COPPE Caixa Postal 68511 BR-21941972 Rio De Janeiro RJ Brazil Royal Inst Technol Dept Math Stockholm Sweden Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada 

出 版 物：《EUROPEAN JOURNAL OF OPERATIONAL RESEARCH》 (欧洲运筹学杂志)

年 卷 期：2020年第281卷第1期

页      面：36-49页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：CNPq (National Council for Scientific and Technological Development) [303898/2016-0] CAPES (Brazilian Federal Agency for Support and Evaluation of Graduate Education) [88881.131629/2016-01] CNPq [142143/2015-4] PSR -Power Systems Research, Rio de Janeiro, Brazil 

主　　题：Quadratic knapsack problem Quadratic binary programming Convex quadratic programming relaxations Parametric optimization Valid inequalities 

摘      要：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. (C) 2019 Elsevier B.V. All rights reserved.