Universität zu Köln

Mallach, Sven ORCID: 0000-0001-5335-0678 (2018). Compact linearization for binary quadratic problems subject to assignment constraints. 4OR-Q. J. Oper. Res., 16 (3). S. 295 - 310. HEIDELBERG: SPRINGER HEIDELBERG. ISSN 1614-2411

Full text not available from this repository.

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, 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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Mallach, Sven UNSPECIFIED orcid.org/0000-0001-5335-0678 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-175458
DOI:	10.1007/s10288-017-0364-0
Journal or Publication Title:	4OR-Q. J. Oper. Res.
Volume:	16
Number:	3
Page Range:	S. 295 - 310
Date:	2018
Publisher:	SPRINGER HEIDELBERG
Place of Publication:	HEIDELBERG
ISSN:	1614-2411
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language POLYNOMIAL PROGRAMMING-PROBLEMS; INTEGER PROBLEMS; OPTIMIZATION; REDUCTION Multiple languages Operations Research & Management Science Multiple languages
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/17545