Lower bounding procedure for the asymmetric quadratic traveling salesman problem

DOI10.1016/j.ejor.2016.03.031zbMath1346.90717OpenAlexW2308191028MaRDI QIDQ323214

Borzou Rostami, Stefano Gualandi, Pietro Belotti, Federico Malucelli

Publication date: 7 October 2016

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

Full work available at URL: http://hdl.handle.net/11311/1030651

zbMATH Keywords

column generationtraveling salesmanlower boundreformulation-linearization techniquecycle cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

Minimization and maximization versions of the quadratic travelling salesman problem, A linear time algorithm for the \(3\)-neighbour travelling salesman problem on a Halin graph and extensions, Geometric and LP-based heuristics for angular travelling salesman problems in the plane, Branch-Price-and-Cut Algorithms for the Vehicle Routing Problem with Stochastic and Correlated Travel Times, A class of exponential neighbourhoods for the quadratic travelling salesman problem

Uses Software

• AMPL
• LEMON

Cites Work

• Unnamed Item
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem
• On minimum reload cost cycle cover
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• An analytical comparison of different formulations of the travelling salesman problem
• Stabilized column generation
• A descent method with linear programming subproblems for nondifferentiable convex optimization
• A revised reformulation-linearization technique for the quadratic assignment problem
• The symmetric quadratic traveling salesman problem
• Lagrangian duality applied to the vehicle routing problem with time windows
• Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics
• Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• On minimum reload cost paths, tours, and flows
• A Linear Programming Approach to the Cutting-Stock Problem
• Integer Programming Formulation of Traveling Salesman Problems
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• The B<scp>oxstep</scp> Method for Large-Scale Optimization
• The Angular-Metric Traveling Salesman Problem
• An Analysis of the Asymmetric Quadratic Traveling Salesman Polytope
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II