Inductive linearization for binary quadratic programs with linear constraints
Mallach, Sven
(2020)
Inductive linearization for binary quadratic programs with
linear constraints.
Published in:
4OR : Quarterly Journal of Operations Research.
pp. 1-23.
Abstract
A linearization technique for binary quadratic programs (BQPs) that comprise linear constraints is presented. The technique, called “inductive linearization”, extends concepts for BQPs with particular equation constraints, that have been referred to as “compact linearization” before, to the general case. Quadratic terms may occur in the objective function, in the set of constraints, or in both. For several relevant applications, the linear programming relaxations obtained from applying the technique are proven to be at least as strong as the one obtained with a well-known classical linearization. It is also shown how to obtain an inductive linearization automatically. This might be used, e.g., by general-purpose mixed-integer programming solvers.
ZAIK Number: | UNSPECIFIED |
---|---|
Depositing User: | Sven Mallach |
Date Deposited: | 21 Oct 2020 11:52 |
Last Modified: | 21 Oct 2020 11:52 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/949 |