|
 
|
[BE01] Best reduction of the quadratic semi-assignment problem
Revue Internationale avec comité de lecture : Journal Discrete Applied Mathematics, vol. 109(3), pp. 197-213, 2001
motcle:
Résumé:
Abstract: 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 by Hammer, Hansen and Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization (Math. Programming, 28 (1984), pp. 121-195) to constrained quadratic 0-1 optimization. Finally, computational experiments proving the practical usefulness of this reduction are reported.
BibTeX
| @article { | |||
| BE01, | |||
| title | = | "{Best reduction of the quadratic semi-assignment problem}", | |
| author | = | "A. Billionnet and S. Elloumi", | |
| journal | = | "Discrete Applied Mathematics", | |
| year | = | 2001, | |
| volume | = | 109, | |
| number | = | 3, | |
| pages | = | "197-213", | |
| } | |||
