APPLICATIONS OF PARAMETRIC PROGRAMMING AND EIGENVALUE MAXIMIZATION TO THE QUADRATIC ASSIGNMENT PROBLEM

被引：43

作者：

RENDL, F ^{[1
]}

WOLKOWICZ, H ^{[1
]}

机构：

[1] UNIV WATERLOO,DEPT COMBINATOR & OPTIMIZAT,WATERLOO N2L 3G1,ONTARIO,CANADA

来源：

MATHEMATICAL PROGRAMMING | 1992年 / 53卷 / 01期

关键词：

QUADRATIC ASSIGNMENT PROBLEM; RELAXATION; LOWER BOUNDS; EIGENVALUE DECOMPOSITION; STEEPEST ASCENT;

D O I：

10.1007/BF01585694

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We investigate new bounding strategies based on different relaxations of the quadratic assignment problem. In particular, we improve the lower bound found by using an eigenvalue decomposition of the quadratic part and by solving a linear program for the linear part. The improvement is accomplished by applying a steepest ascent algorithm to the sum of the two bounds.

引用

页码：63 / 78

页数：16

共 21 条

[1]

BURKARD RE, 1980, LECTURE NOTES EC MAT, V184

[2]

Clarke F.H., 1983, OPTIMIZATION NONSMOO

[3] ON LINEAR-PROGRAMS WITH RANDOM COSTS [J].

DYER, ME ;

FRIEZE, AM ;

MCDIARMID, CJH .

MATHEMATICAL PROGRAMMING, 1986, 35 (01) :3-16

[4]

FINKE G, 1987, ANN DISCRETE MATH, V31, P61

[5]

FINKE G, 1987, APPROXIMATION APPROA

[6]

Gill P. E., 1981, PRACTICAL OPTIMIZATI

[7]

GOLLAN B, 1987, MATH PROGRAM STUD, V30, P67, DOI 10.1007/BFb0121155

[8]

HADLEY S, 1988, HESSIAN FUNCTION EIG

[9]

Held M., 1974, Mathematical Programming, V6, P62, DOI 10.1007/BF01580223

[10] THE VARIATION OF THE SPECTRUM OF A NORMAL MATRIX [J].

HOFFMAN, AJ ;

WIELANDT, HW .

DUKE MATHEMATICAL JOURNAL, 1953, 20 (01) :37-39

← 1 2 3 →