Compact linearization for binary quadratic problems subject to assignment constraints
Mallach, Sven
(2017)
Compact linearization for binary quadratic problems subject to assignment constraints.
Published in:
4OR : Quarterly Journal of Operations Research.
pp. 1-14.
ISSN 1614-2411
This is the latest version of this item.
Abstract
We introduce and prove new necessary and sufficient conditions to carry out a compact linearization approach for a general class of binary quadratic problems subject to assignment constraints that has been proposed by Liberti (4OR 5(3):231–245, 2007, https://doi.org/10.1007/s10288-006-0015-3). The new conditions resolve inconsistencies that can occur when the original method is used. We also present a mixed-integer linear program to compute a minimally sized linearization. When all the assignment constraints have non-overlapping variable support, this program is shown to have a totally unimodular constraint matrix. Finally, we give a polynomial-time combinatorial algorithm that is exact in this case and can be used as a heuristic otherwise.
ZAIK Number: | UNSPECIFIED |
---|---|
Depositing User: | Sven Mallach |
Date Deposited: | 07 Dec 2017 12:39 |
Last Modified: | 13 Mar 2018 09:28 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/910 |
Available Versions of this Item
-
Compact Linearization for Binary Quadratic Problems subject to Assignment Constraints. (deposited 19 Oct 2016 08:15)
- Compact linearization for binary quadratic problems subject to assignment constraints. (deposited 07 Dec 2017 12:39) [Currently Displayed]