Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems

DOI10.1016/S0377-2217(01)00159-XMaRDI QIDQ1600930zbMATH OpenOpenAlexFDO

Authors Marcelo Gonçalves Narciso, Luiz Antonio Nogueira Lorena

Publication date 16 June 2002

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0377-2217(01)00159-x

zbMATH Keywords

combinatorial optimizationtraveling salesman problemsubgradient methodsurrogate relaxationLagrangean relaxationHeld and Karp bound

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Derivative-free methods and methods using generalized derivatives (90C56)

Recommendations

• scientific article; zbMATH DE number 1383814
• Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations
• A modified subgradient algorithm for Lagrangean relaxation
• Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem
• Surrogate gradient algorithm for Lagrangian relaxation

Cites work

• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 193499 (Why is no real title available?)
• scientific article; zbMATH DE number 3542191 (Why is no real title available?)
• scientific article; zbMATH DE number 3557512 (Why is no real title available?)
• scientific article; zbMATH DE number 3614502 (Why is no real title available?)
• scientific article; zbMATH DE number 871931 (Why is no real title available?)
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• A generalization of Polyak's convergence result for subgradient optimization
• A generalized subgradient method with relaxation step
• A surrogate heuristic for set covering problems
• An adaptation of SH heuristic to the location set covering problem
• An improved subgradient method for constrained nondifferentiable optimization
• Calculating surrogate constraints
• Conditional subgradient optimization -- theory and applications
• Convergence of some algorithms for convex minimization
• Estimating the Held-Karp lower bound for the geometric TSP
• Generalized Lagrange Multipliers in Integer Programming
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• Lagrangean/surrogate relaxation for generalized assignment problems
• Minimization of unsmooth functionals
• On convergence rates of subgradient optimization methods
• On the choice of step size in subgradient optimization
• Polyak's subgradient method with simplified projection for nondifferentiable optimization with linear constraints
• Relaxation heuristics for a generalized assignment problem
• Some relationships between lagrangian and surrogate duality in integer programming
• Surrogate Constraint Duality in Mathematical Programming
• Surrogate Constraints
• Surrogate Mathematical Programming
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling salesman problem: An overview of exact and approximate algorithms
• The traveling salesman. Computational solutions for RSP applications
• The traveling-salesman problem and minimum spanning trees: Part II
• Validation of subgradient optimization

Cited in

(4)

• On the existence of duality gaps for mixed integer programming
• Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem
• A Lagrange multiplier and Hopfield-type barrier function method for the traveling salesman problem
• A surrogate-based heuristic for production planning problem of orders in small foundries

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1600930)