Abstract
We present a new approach to constrained quadratic binary programming. Dual bounds are computed by choosing appropriate global underestimators of the objective function that are separable but not necessarily convex. Using the binary constraint on the variables, the minimization of this separable underestimator can be reduced to a linear minimization problem over the same set of feasible vectors. For most combinatorial optimization problems, the linear version is considerably easier than the quadratic version. We explain how to embed this approach into a branch-and-bound algorithm and present experimental results.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Assad, A., Xu, W.: The quadratic minimum spanning tree problem. Naval Research Logistics 39(3), 399–417 (1992)
Billionnet, A., Elloumi, S., Plateau, M.-C.: 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)
Buchheim, C., Caprara, A., Lodi, A.: An effective branch-and-bound algorithm for convex quadratic integer programming. Mathematical Programming (Series A) 135(1-2), 369–395 (2012)
Buchheim, C., De Santis, M., Palagi, L., Piacentini, M.: An exact algorithm for quadratic integer minimization using nonconvex relaxations. Technical report, Optimization Online (2012)
Palagi, L., Piccialli, V., Rendl, F., Rinaldi, G., Wiegele, A.: Computational approaches to Max-Cut. In: Handbook on Semidefinite, Conic and Polynomial Optimization, pp. 821–849. Springer (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Buchheim, C., Traversi, E. (2013). Separable Non-convex Underestimators for Binary Quadratic Programming. In: Bonifaci, V., Demetrescu, C., Marchetti-Spaccamela, A. (eds) Experimental Algorithms. SEA 2013. Lecture Notes in Computer Science, vol 7933. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38527-8_22
Download citation
DOI: https://doi.org/10.1007/978-3-642-38527-8_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38526-1
Online ISBN: 978-3-642-38527-8
eBook Packages: Computer ScienceComputer Science (R0)