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.


Actions:
Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
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