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

DOI10.1016/S0377-2217(01)00159-XzbMath1003.90039OpenAlexW2046494104MaRDI QIDQ1600930

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 optimizationLagrangean relaxationsubgradient methodtraveling salesman problemsurrogate relaxationHeld and Karp bound

Mathematics Subject Classification ID

Related Items (2)

On the existence of duality gaps for mixed integer programming ⋮ Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem

Uses Software

• TSPLIB

Cites Work

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

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