A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems

By M. Padberg, Giovanni Rinaldi. 1991

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks (2017, methodology): “The näıve approach mentioned at the beginning of this section can be simulated by applying the ReluSplit rule eagerly until it no longer applies and then solving each derived sub-problem separately (this reduction trivially guarantees termination just as do branch-and-cut techniques in mixed integer”
Neural Combinatorial Optimization with Reinforcement Learning (2016, neutral): “Concorde (Applegate et al., 2006), widely accepted as one of the best exact TSP solvers, makes use of cutting plane algorithms (Dantzig et al., 1954; Padberg & Rinaldi, 1990; Applegate et al., 2003), iteratively solving linear programming relaxations of the TSP, in conjunction with a…”
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning (2016, methodology): “The algorithm of Padberg and Rinaldi [89] is specific to the well-known traveling salesman problem, but in [90] a generalization of branch-and-cut for binary integer programs is presented.”
Branching and bounds tighteningtechniques for non-convex MINLP (2009, unknown): “When f is linear and all of the g j are aﬃne, we have a Mixed Integer Linear Programming (MILP) problem, a class of diﬃcult problems for which practical Branch-and-Cut methods have been successfully developed [40, 63, 85].”
Symmetry in Integer Linear Programming (2010, background): “(We assume that the reader is familiar with these procedures, as excellent introductions can be found in [38, 59, 90 , 117].) The trouble comes from the fact that many subproblems in the enumeration tree are isomorphic, forcing a wasteful duplication of effort.”
Static pickup and delivery problems: a classification scheme and survey (2007, methodology): “The method is similar to the TSP algorithm of Padberg and Rinaldi (1991) .”
Certification of an optimal TSP tour through 85, 900 cities (2009, methodology): “The Concorde TSP code follows a branch-and-cut scheme [14,18], embedding the cutting-plane algorithm within a branchand-bound search.”
An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (2019, background): “Today, state-of-the-art TSP solvers such as Concorde [Applegate et al., 2006] make use of cutting plane algorithms [Dantzig et al., 1954, Padberg and Rinaldi, 1991, Applegate et al., 2003] to iteratively solve linear programming relaxations of the TSP in addition to a branch-and-bound approach that…”
Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems (2003, methodology): “A different approach was adopted by Padberg and Rinaldi (1991), taking advantage of the form of their tour-finding heuristic.”
Concave Quadratic Cuts for Mixed-Integer Quadratic Problems (2015, background): “Generic methods such as branch-and-bound [LD60] or branch-and-cut [PR91] can be used to solve (1) globally, but they all have an exponential time complexity.”
Active-constraint variable ordering for faster feasibility of mixed integer linear programs (2007, methodology): “Padberg and Rinaldi [ 31 ] used a combination of the objective function coefficient and the fractional part of the candidate variable in their branch-and-cut algorithm for solving large-scale traveling salesman problems.”
Improved solutions for inventory-routing problems through valid inequalities and input ordering (2014, background): “8: end if 9: while the solution of the current LP relaxation contains subtours do 10: Identify connected components as in Padberg and Rinaldi [20].”
A Branch-and-Cut Algorithm for a Vendor-Managed Inventory-Routing Problem (2007, methodology): “n (17) (18) (19) (20) (21) (22) (23)–(24)”
On renewable sensor networks with wireless energy transfer (2011, unknown): “…vac s.t. j =i j∈N f ij +f iB − k =i k∈N f ki = R i (i ∈ N ) (15) C k =i k∈N f ki + j =i j∈N C ij f ij + C iB f iB − Uη i = 0 (i ∈ N ) (16) η vac ≤ 1 − k∈N η k − U ·τ TSP E max −E min · η i · (1 − η i ) (i ∈ N ) (17) f ij , f iB ≥ 0, 0 ≤ η i , η vac ≤ 1 (i, j ∈ N , i = j) In this problem, f ij , f…”
An effective implementation of the Lin-Kernighan traveling salesman heuristic (2000, methodology): “The most effective exact algorithms are cutting-plane or facet-finding algorithms [6, 7, 8].”
Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems (2001, methodology): “An LP subproblem p for the proposed algorithm has the form min cT x s t Ax+By+Cv ≤ a Qx ≤ q Cuts xLBp ≤ x ≤ xUBp yLBp ≤ y ≤ yUBp x ∈ n y ∈ m v ∈ p xLBp x UB p y LB p y UB p ∈ 0 1 The difference in various LP subproblems is only in the upper and lower bounds for all the integer variables.”
Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches (2010, background): “This work, which has fostered the growth of polyhedral theory and of branch-and-cut, was mainly conducted by (Padberg and Hong, 1980; Crowder & Padberg, 1980; Grötschel & Padberg, 1985; Padberg & Grötschel, 1985; Padberg & Rinaldi, 1987, 1991; Grötschel & Holland, 1991).”
Local Search and the Traveling Salesman Problem: A Feature-Based Characterization of Problem Hardness (2012, background): “It follows a branch-and-cut scheme [17], embedding the cutting-plane algorithm within a branch-and-bound search.”