Ranking scalar products to improve bounds for the quadratic assignment problem (Q1058988): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0377-2217(85)90009-8 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1979166098 / rank | |||
Normal rank | |||
Revision as of 22:21, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Ranking scalar products to improve bounds for the quadratic assignment problem |
scientific article |
Statements
Ranking scalar products to improve bounds for the quadratic assignment problem (English)
0 references
1985
0 references
The eigenvalue bound for the quadratic assignment problem (QAP) is successively improved by considering a set of k-best scalar products, related to the QAP. An efficient procedure is proposed to find such a set of k-best scalar products. A class of QAPs is described for which this procedure in general improves existing lower bounds and at the same time generates good suboptimal solutions. The method leaves the user with a large flexibility in controlling the quality of the bound. However, since the method is sensitive to input data it should only be used in combination with other bounding rules.
0 references
ranking procedure
0 references
quadratic assignment
0 references
k-best scalar products
0 references
lower bounds
0 references
suboptimal solutions
0 references
