Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
From MaRDI portal
Solution techniques for optimization problems often require bounds of the objective function. In this paper lower bounds are given for the quadratic assignment problem using an eigenvalue decomposition of the quadratic part and solving a linear program for the linear part. Applying ideas of parametric programming the sum of the two bounds is increased by a steepest ascent algorithm. There are numerical results showing the power of the new method.
Recommendations
Cites work
- A parallel branch and bound algorithm for the quadratic assignment problem
- Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
- Bounds for eigenvalues using traces
- Convex Analysis
- Eigenvalue perturbations and nonlinear parametric optimization
- scientific article; zbMATH DE number 3982880 (Why is no real title available?)
- scientific article; zbMATH DE number 4076973 (Why is no real title available?)
- scientific article; zbMATH DE number 3793774 (Why is no real title available?)
- Matrix Analysis
- On linear programs with random costs
- On Minimizing the Maximum Eigenvalue of a Symmetric Matrix
- Optimization and nonsmooth analysis
- P-Complete Approximation Problems
- The spread of a matrix
- The variation of the spectrum of a normal matrix
- Validation of subgradient optimization
Cited in
(27)- Ranking scalar products to improve bounds for the quadratic assignment problem
- Special cases of the quadratic assignment problem
- A parallel depth first search branch and bound algorithm for the quadratic assignment problem
- Network-based formulations of the quadratic assignment problem
- Strengthening Gilmore's bound for the quadratic assignment problem
- Lower bounds for the quadratic assignment problem
- A new exact algorithm for the solution of quadratic assignment problems
- Best ellipsoidal relaxation to solve a nonconvex problem.
- Lower bounds based on linear programming for the quadratic assignment problem
- Solving the max-cut problem using eigenvalues
- A projection technique for partitioning the nodes of a graph
- Lower bounds for the quadratic assignment problem via triangle decompositions
- A survey of hidden convex optimization
- Diffusion bank networks and capital flows
- scientific article; zbMATH DE number 6902579 (Why is no real title available?)
- On improving convex quadratic programming relaxation for the quadratic assignment problem
- Graph similarity and approximate isomorphism
- Stochastic consensus dynamics for nonconvex optimization on the Stiefel manifold: mean-field limit and convergence
- scientific article; zbMATH DE number 232498 (Why is no real title available?)
- Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem
- Norms on complex matrices induced by complete homogeneous symmetric polynomials
- Sinkhorn Algorithm for Lifted Assignment Problems
- Laplace eigenvalues of graphs---a survey
- Selected topics on assignment problems
- A survey for the quadratic assignment problem
- Bounds for the quadratic assignment problem using the bundle method
- A new relaxation framework for quadratic assignment problems based on matrix splitting
This page was built for publication: Applications of parametric programming and eigenvalue maximization to the quadratic assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1184337)
