  The objective function of a quadratic combinatorial optimization problem
(QCOP) can be represented by two data points, a quadratic cost matrix Q and a
linear cost vector c. Different, but equivalent, representations of the pair
(Q, c) for the same QCOP are well known in literature. Research papers often
state that without loss of generality we assume Q is symmetric, or
upper-triangular or positive semidefinite, etc. These representations however
have inherently different properties. Popular general purpose 0-1 QCOP solvers
such as GUROBI and CPLEX do not suggest a preferred representation of Q and c.
Our experimental analysis discloses that GUROBI prefers the upper triangular
representation of the matrix Q while CPLEX prefers the symmetric representation
in a statistically significant manner. Equivalent representations, although
preserve optimality, they could alter the corresponding lower bound values
obtained by various lower bounding schemes. For the natural lower bound of a
QCOP, symmetric representation produced tighter bounds, in general. Effect of
equivalent representations when CPLEX and GUROBI run in a heuristic mode are
also explored. Further, we review various equivalent representations of a QCOP
from the literature that have theoretical basis to be viewed as strong and
provide new theoretical insights for generating such equivalent representations
making use of constant value property and diagonalization (linearization) of
QCOP instances.
