Compact Linearization for Binary Quadratic Problems subject to\n Assignment Constraints

2016/10/17 by Sven Mallach, Mallach, Sven
Mathematics · Engineering · Computer Science · #Advanced Optimization Algorithms Research #Optimization and Packing Problems #Advanced Graph Theory Research

paper · pdf · doi:10.48550/arxiv.1610.05375

Abstract

We prove new necessary and sufficient conditions to carry out a compact\nlinearization approach for a general class of binary quadratic problems subject\nto assignment constraints as it has been proposed by Liberti in 2007. The new\nconditions resolve inconsistencies that can occur when the original method is\nused. We also present a mixed-integer linear program to compute a\nminimally-sized linearization. When all the assignment constraints have\nnon-overlapping variable support, this program is shown to have a totally\nunimodular constraint matrix. Finally, we give a polynomial-time combinatorial\nalgorithm that is exact in this case and can still be used as a heuristic\notherwise.\n

Related

• Compact Linearization for Binary Quadratic Problems Comprising Linear Constraints
• Compact Linearization for Binary Quadratic Problems subject to Linear Equations
• The linearization problem of a binary quadratic problem and its applications
• The quadratic assignment problem: the linearization of Xia and Yuan is weaker than the linearization of Adams and Johnson and a family of cuts to narrow the gap
• A Polynomial-Time Algorithm for Unconstrained Binary Quadratic\n Optimization