Compact Linearization for Binary Quadratic Problems subject to Linear Equations
From MaRDI portal
Publication:6295331
arXiv1712.05872MaRDI QIDQ6295331FDOQ6295331
Authors: Sven Mallach 
Publication date: 15 December 2017
Abstract: In this paper it is shown that the compact linearization approach, that has been previously proposed only for binary quadratic problems with assignment constraints, can be generalized to arbitrary linear equations with positive coefficients which considerably enlarges its applicability. We discuss special cases of prominent quadratic combinatorial optimization problems where the obtained compact linearization yields a continuous relaxation that is provably as least as strong as the one obtained with an ordinary linearization.
Quadratic programming (90C20) Linear programming (90C05) Nonlinear programming (90C30) General topics of discrete mathematics in relation to computer science (68R01) Integer programming (90C10) Mixed integer programming (90C11) Boolean programming (90C09)
This page was built for publication: Compact Linearization for Binary Quadratic Problems subject to Linear Equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6295331)
