The travelling salesman problem with neighbourhoods: MINLP solution

DOI10.1080/10556788.2011.648932zbMath1270.90055OpenAlexW2141708863MaRDI QIDQ4924121

Margot, François, Iacopo Gentilini, Kenji Shimada

Publication date: 30 May 2013

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556788.2011.648932

zbMATH Keywords

spatial branch-and-boundnon-convex and nonlinear optimizationtravelling salesman problem with neighbourhoods

Mathematics Subject Classification ID

Mixed integer programming (90C11) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Related Items

Global optimization advances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO, Constrained optimization with integer and continuous variables using inexact restoration and projected gradients, Guided dive for the spatial branch-and-bound, Minimum spanning trees with neighborhoods: mathematical programming formulations and solution methods, Virtuous smoothing for global optimization, Facility location problems on graphs with non-convex neighborhoods, Ordered \(p\)-median problems with neighbourhoods, On hub location problems in geographically flexible networks, Unmanned aerial vehicles/drones in vehicle routing problems: a literature review, Shortest Paths in Graphs of Convex Sets, More Virtuous Smoothing, QPLIB: a library of quadratic programming instances, Routing for unmanned aerial vehicles: touring dimensional sets, Minimum cost \(b\)-matching problems with neighborhoods, Spatial coverage in routing and path planning problems, Solving the traveling delivery person problem with limited computational time

Uses Software

• BARON
• AMPL
• Couenne
• COIN-OR
• Bonmin
• Concorde

Cites Work

• Unnamed Item
• A Modeling Language for Mathematical Programming
• An algorithmic framework for convex mixed integer nonlinear programs
• Approximation algorithms for the Geometric Covering Salesman Problem
• The traveling salesman problem and its variations
• BARON: A general purpose global optimization software package
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Integer Programming Formulation of Traveling Salesman Problems
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Branching and bounds tighteningtechniques for non-convex MINLP
• Heuristic Approaches for a TSP Variant: The Automatic Meter Reading Shortest Tour Problem
• APPROXIMATION ALGORITHMS FOR THE EUCLIDEAN TRAVELING SALESMAN PROBLEM WITH DISCRETE AND CONTINUOUS NEIGHBORHOODS
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem