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.
| Editorial actions: |  View Item (Login required) |
|---|
| 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]
