A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
From MaRDI portal
Publication:4367232
DOI10.1287/opre.45.3.378zbMath0893.90164OpenAlexW2018269848MaRDI QIDQ4367232
Paolo Toth, Matteo Fischetti, Juan-José Salazar-González
Publication date: 1 September 1998
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.45.3.378
polytopesbranch-and-cutlocation-routinginteger linear programfacial structuresymmetric traveling salesmangeneralized traveling salesmanclustered notesheuristic separation procedures
Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10)
Related Items (99)
A Variable Neighborhood Search and its Application to a Ring Star Problem Generalization ⋮ A two-level metaheuristic for the all colors shortest path problem ⋮ Optimal capacitated ring trees ⋮ On the minimum corridor connection problem and other generalized geometric problems ⋮ Layered graph approaches for combinatorial optimization problems ⋮ Efficient elementary and restricted non-elementary route pricing ⋮ Locating median cycles in networks ⋮ The mixed capacitated general routing problem under uncertainty ⋮ An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem ⋮ Particle swarm optimization-based algorithms for TSP and generalized TSP ⋮ Integer programming models and branch-and-cut approaches to generalized \(\{0,1,2\}\)-survivable network design problems ⋮ A hybrid heuristic approach for the multi-commodity pickup-and-delivery traveling salesman problem ⋮ The generalized fixed-charge network design problem ⋮ The production routing problem: a review of formulations and solution algorithms ⋮ Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm ⋮ A random-key genetic algorithm for the generalized traveling salesman problem ⋮ The probabilistic orienteering problem ⋮ MIP neighborhood synthesis through semantic feature extraction and automatic algorithm configuration ⋮ GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem ⋮ Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem ⋮ A pure proactive scheduling algorithm for multiple Earth observation satellites under uncertainties of clouds ⋮ Solving the asymmetric traveling purchaser problem ⋮ Solving a generalized traveling salesperson problem with stochastic customers ⋮ Eulerian location problems ⋮ Modeling and solving the mixed capacitated general routing problem ⋮ An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem ⋮ A Discrete State Transition Algorithm for Generalized Traveling Salesman Problem ⋮ Large multiple neighborhood search for the soft-clustered vehicle-routing problem ⋮ Gotta (efficiently) catch them all: Pokémon GO meets orienteering problems ⋮ Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout ⋮ A heuristic procedure for the capacitated \(m\)-ring-star problem ⋮ A transformation technique for the clustered generalized traveling salesman problem with applications to logistics ⋮ Liner shipping network design ⋮ Mixed integer programming formulations for the generalized traveling salesman problem with time windows ⋮ A learn‐and‐construct framework for general mixed‐integer programming problems ⋮ An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search ⋮ A branch-and-cut algorithm for the generalized traveling salesman problem with time windows ⋮ Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem ⋮ The traveling purchaser problem with stochastic prices: exact and approximate algorithms ⋮ A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem ⋮ Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm ⋮ An adaptive memory matheuristic for the set orienteering problem ⋮ New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem ⋮ Transformations of generalized ATSP into ATSP. ⋮ New mathematical models of the generalized vehicle routing problem and extensions ⋮ The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm ⋮ The cumulative school bus routing problem: Polynomial‐size formulations ⋮ A granular iterated local search for the asymmetric single truck and trailer routing problem with satellite depots at DHL Group ⋮ An integer linear programming based heuristic for the capacitated \(m\)-ring-star problem ⋮ Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem ⋮ A branch-and-cut algorithm for the soft-clustered vehicle-routing problem ⋮ The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm ⋮ A note on the generalized Steiner tree polytope ⋮ The capacitated arc routing problem with intermediate facilities ⋮ Revisiting the Hamiltonian \(p\)-median problem: a new formulation on directed graphs and a branch-and-cut algorithm ⋮ An efficient transformation of the generalized vehicle routing problem ⋮ A tabu search heuristic for the generalized minimum spanning tree problem ⋮ Variable neighborhood search for the set orienteering problem and its application to other orienteering problem variants ⋮ Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm ⋮ Branch-and-bound for the precedence constrained generalized traveling salesman problem ⋮ A pattern recognition lexi search approach to generalized time-dependent travelling salesman problem ⋮ On solving cycle problems with branch-and-cut: extending shrinking and exact subcycle elimination separation algorithms ⋮ Multiple depot ring star problem: a polyhedral study and an exact algorithm ⋮ Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem ⋮ The set orienteering problem ⋮ The prize-collecting generalized minimum spanning tree problem ⋮ Large multiple neighborhood search for the clustered vehicle-routing problem ⋮ Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem ⋮ The undirected \(m\)-capacitated peripatetic salesman problem ⋮ An integer programming-based local search for the covering salesman problem ⋮ A memetic algorithm for the generalized traveling salesman problem ⋮ Branch-and-cut algorithms for the undirected \(m\)-Peripatetic Salesman Problem ⋮ A memetic algorithm with a large neighborhood crossover operator for the generalized traveling salesman problem ⋮ Facets of the \(p\)-cycle polytope ⋮ Exact solution of the soft-clustered vehicle-routing problem ⋮ The clustered team orienteering problem ⋮ A two-stage vehicle routing model for large-scale bioterrorism emergencies ⋮ The generalized minimum edge-biconnected network problem: Efficient neighborhood structures for variable neighborhood search ⋮ Solving the Job Sequencing and Tool Switching Problem as a nonlinear least cost Hamiltonian cycle problem ⋮ Randomized gravitational emulation search algorithm for symmetric traveling salesman problem ⋮ A branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool ⋮ Solving the family traveling salesman problem ⋮ A biased random-key genetic algorithm for the set orienteering problem ⋮ The generalized minimum branch vertices problem: properties and polyhedral analysis ⋮ A Sensitive Metaheuristic for Solving a Large Optimization Problem ⋮ The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances ⋮ A branch-and-cut algorithm for the maximum covering cycle problem ⋮ Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters ⋮ The Generalized Covering Salesman Problem ⋮ An improved hybrid ant-local search algorithm for the partition graph coloring problem ⋮ Generalized network design problems. ⋮ The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm ⋮ Cluster-level operations planning for the out-of-position robotic arc-welding ⋮ Exact and heuristic algorithms for solving the generalized vehicle routing problem with flexible fleet size ⋮ Discrete/Binary Approach ⋮ The Ring Star Problem: Polyhedral analysis and exact algorithm ⋮ Upper and lower bounding procedures for the minimum caterpillar spanning problem ⋮ Spatial coverage in routing and path planning problems ⋮ A new relaxation method for the generalized minimum spanning tree problem
Uses Software
This page was built for publication: A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
