A Lagrangian decomposition approach to computing feasible solutions for quadratic binary programs

In this paper, we develop a Lagrangian decomposition based heuristic method for general quadratic binary programs (QBPs) with linear constraints. We extend the idea of Lagrangian decomposition by Chardaire and Sutter (Manag Sci 41(4):704–712, 1995) and Billionnet and Soutif (Eur J Oper Res 157(3):565–575, 2004a, Inf J Comput 16(2):188–197, 2004b) in which the quadratic objective is converted to a bilinear function by introducing auxiliary variables to duplicate the original complicating variables in the problem. Instead of using linear constraints to assure the equity between the two types of decision variables, we introduce generalized quadratic constraints and relax them with Lagrangian multipliers. Instead of computing an upper bound for a maximization problem, we focus on lower bounding with Lagrangian decomposition based heuristic. We take advantage of the decomposability presented in the Lagrangian subproblems to speed up the heuristic and identify one feasible solution at each iteration of the subgradient optimization procedure. With numerical studies on several classes of representative QBPs, we investigate the sensitivity of lower-bounding performance on parameters of the additional quadratic constraints. We also demonstrate the potentially improved quality of preprocessing in comparison with the use of a QBP solver.