Publication Date:
2018-03-05
Description:
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.
Print ISSN:
1619-4500
Electronic ISSN:
1614-2411
Topics:
Mathematics
