×

Nonlinear approaches for quadratic assignment and graph partition problems. (English) Zbl 0864.90121

Graz: TU Graz, Tech.-Naturwiss. Fak. ix, 125 p. (1995).
Summary: Nonlinear approaches have been successfully applied to NP-hard combinatorial optimization problems in the past. In this work, spectral approaches are used to compute bounds for the quadratic assignment problem (QAP) and the graph equipartition problem (EQP).
We derive semidefinite relaxations for QAP and EQP in the first chapters. Combining these nonlinear relaxations with polyhedral information provides good approximations for both problems. Cutting plane approaches are employed and yield bounds of high quality. We also describe a generic approach for the modeling of discrete optimization problems and that interior point methods can be used to solve the resulting semidefinite programming problems.
Rectilinear QAPs are considered separately in two chapters. We describe a decomposition principle which, in combination with an eigenvalue approach, leads to very strong lower bounds for rectilinear QAPs. For these specially structural problems semidefinite relaxations are proposed as well. We also mention how to extend the approach to solve problems with different structure.

MSC:

90C35 Programming involving graphs or networks

Software:

CUTSDP
PDFBibTeX XMLCite