6533b827fe1ef96bd1286dc5
RESEARCH PRODUCT
Cotas inferiores para el QAP-Arbol
Enrique Benavent Lópezsubject
Statistics and ProbabilityDynamic programmingCombinatoricsDistance matrixGeneralizationQuadratic assignment problemStatistics Probability and UncertaintySpecial caseUpper and lower boundsTravelling salesman problemInteger programmingMathematicsdescription
The Tree-QAP is a special case of the Quadratic Assignment Problem where the flows not equal zero form a tree. No condition is required for the distance matrix. In this paper we present an integer programming formulation for the Tree-QAP. We use this formulation to construct four Lagrangean relaxations that produce several lower bounds for this problem. To solve one of the relaxed problems we present a Dynamic Programming algorithm which is a generalization of the algorithm of this type that gives a lower bound for the Travelling Salesman Problem. A comparison is given between the lower bounds obtained by each ralaxation for examples with size from 12 to 25.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 1985-02-01 | Trabajos de Estadistica y de Investigacion Operativa |