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

DOI10.1016/S0377-2217(01)00159-XzbMATH Open1003.90039OpenAlexW2046494104MaRDI QIDQ1600930FDOQ1600930

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

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

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)

Cites Work

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

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

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)