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. 114.
ISSN 16142411
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/s1028800600153). The new conditions resolve inconsistencies that can occur when the original method is used. We also present a mixedinteger linear program to compute a minimally sized linearization. When all the assignment constraints have nonoverlapping variable support, this program is shown to have a totally unimodular constraint matrix. Finally, we give a polynomialtime 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://earchive.informatik.unikoeln.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]