Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem

DOI10.1016/J.EJOR.2017.04.061zbMath1375.90223OpenAlexW2611447099MaRDI QIDQ1683126

Markus Leitner, Mario Ruthmair, Luís Gouveia

Publication date: 6 December 2017

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2017.04.061

zbMATH Keywords

traveling salesman probleminteger linear programmingbranch-and-cutlayered graphdistance constraint

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items (4)

Layered graph approaches for combinatorial optimization problems ⋮ Reformulations and branch-and-price algorithm for the minimum cost hop-and-root constrained forest problem ⋮ Corrigendum to: ``Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem ⋮ A generic exact solver for vehicle routing and related problems

Uses Software

• Concorde

Cites Work

• Unnamed Item
• Unnamed Item
• Hop constrained Steiner trees with multiple root nodes
• A new formulation and approach for the black and white traveling salesman problem
• Load-dependent and precedence-based models for pickup and delivery problems
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• Natural and extended formulations for the time-dependent traveling salesman problem
• On implementing the push-relabel method for the maximum flow problem
• A classification of formulations for the (time-dependent) traveling salesman problem
• Design of survivable networks with vulnerability constraints
• Heuristics for the black and white traveling salesman problem
• The time dependent traveling salesman problem: polyhedra and algorithm
• The two-level diameter constrained spanning tree problem
• Modeling and solving the rooted distance-constrained minimum spanning tree problem
• The Four-Day Aircraft Maintenance Routing Problem
• A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems
• On Solving the Rooted Delay- and Delay-Variation-Constrained Steiner Tree Problem
• An algorithm for designing rings for survivable fiber networks
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• The Black and White Traveling Salesman Problem
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs
• Variable neighborhood search: Principles and applications
• Solving the asymmetric travelling salesman problem with time windows by branch-and-cut

This page was built for publication: Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem