We introduce a polyhedral framework for characterizing instances of quadratic combinatorial optimization programs (QCOPs) that are linearizable, meaning that the quadratic objective can be equivalently rewritten as linear in such a manner that preserves the objective function value at all feasible solutions. In particular, we show that an instance is linearizable if and only if the quadratic cost coefficients can be used to construct a linear equation, in a lifted variable space, that is valid for the affine hull of a specially structured discrete set. In addition to developing this result for general QCOPs, we illustrate its utility in the specific context of the quadratic minimum spanning tree problem (QMSTP). As a consequence of this new polyhedral perspective on the concept of linearizability, we are able to make progress on a recent open question regarding linearizable QMSTP instances defined on biconnected graphs.
Article
View A Polyhedral Characterization of Linearizable Quadratic Combinatorial Optimization Problems