Best reduction of the quadratic semi-assignment problem

We consider the quadratic semi-assignment problem in which we minimize a quadratic pseudo-Boolean function F subject to the semi-assignment constraints. We propose in this paper a linear programming method to obtain the best reduction of this problem, i.e. to compute the greatest constant c such that F is equal to c plus F′ for all feasible solutions, F′ being a quadratic pseudo-Boolean function with nonnegative coefficients. Thus constant c can be viewed as a generalization of the height of an unconstrained quadratic 0-1 function introduced in (Hammer et al., Math. Program. 28 (1984) 121-155), to constrained quadratic 0-1 optimization. Finally, computational experiments proving the practical usefulness of this reduction are reported.