Compact Linearization for Binary Quadratic Problems subject to Linear Equations

Publication date 15 December 2017

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)

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.

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)