A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
From MaRDI portal
Publication:3362088
DOI10.1137/1033004zbMath0734.90060OpenAlexW2029242918WikidataQ56067403 ScholiaQ56067403MaRDI QIDQ3362088
Manfred W. Padberg, Giovanni Rinaldi
Publication date: 1991
Published in: SIAM Review (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/966580e91b06f55605869b7155784c2fc0c444bb
Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Large-scale problems in mathematical programming (90C06) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
A branch-and-cut algorithm for vehicle routing problems, Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem, The two-echelon multi-depot inventory-routing problem, Layered graph approaches for combinatorial optimization problems, The \(p\)-arborescence star problem: formulations and exact solution approaches, Optimization of a 532-city symmetric traveling salesman problem by branch and cut, The clustered orienteering problem, Global optimization with spline constraints: a new branch-and-bound method based on B-splines, On the complexity of some basic problems in computational convexity. I. Containment problems, A purely proactive scheduling procedure for the resource-constrained project scheduling problem with stochastic activity durations, DASH: dynamic approach for switching heuristics, A survey for the quadratic assignment problem, Ordered spatial sampling by means of the traveling salesman problem, Optimal joint replenishment, delivery and inventory management policies for perishable products, Multi-period vehicle routing problem with due dates, The probabilistic orienteering problem, A variable MIP neighborhood descent algorithm for managing inventory and distribution of cash in automated Teller machines, Load-dependent and precedence-based models for pickup and delivery problems, History-dependent scheduling: models and algorithms for scheduling with general precedence and sequence dependence, A pure proactive scheduling algorithm for multiple Earth observation satellites under uncertainties of clouds, Some properties of cliques in 0-1 mixed integer programs, The pickup and delivery problem: Faces and branch-and-cut algorithm, A hybrid approach for biobjective optimization, A branch-and-cut algorithm for the equicut problem, On global integer extrema of real-valued box-constrained multivariate quadratic functions, A note on branch-and-cut-and-price, Optimally solving the joint order batching and picker routing problem, Extended formulations and branch-and-cut algorithms for the black-and-white traveling salesman problem, A Branch-and-Cut method for the Capacitated Location-Routing Problem, Heuristic and exact algorithms for a min-max selective vehicle routing problem, A semidefinite optimization approach to the target visitation problem, Customizing the solution process of COIN-OR's linear solvers with python, Global optimality conditions and optimization methods for quadratic assignment problems, Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups., Survivable network design with demand uncertainty, Solving survivable two-layer network design problems by metric inequalities, Information-theoretic approaches to branching in search, Alternative formulations and improved bounds for the multi-depot fleet size and mix vehicle routing problem, Seeking global edges for traveling salesman problem in multi-start search, Undirected postman problems with zigzagging option: a cutting-plane approach, Memetic algorithm based on improved inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem, An improved column generation algorithm for minimum sum-of-squares clustering, The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities, The precedence constrained knapsack problem: separating maximally violated inequalities, The min-degree constrained minimum spanning tree problem: formulations and branch-and-cut algorithm, An algorithmic framework for convex mixed integer nonlinear programs, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Local search inequalities, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, The traveling purchaser problem and its variants, A cutting plane algorithm for the windy postman problem, Inventory routing with pickups and deliveries, A modified Lin--Kernighan traveling-salesman heuristic, On symmetric subtour problems, Revival of the Gomory cuts in the 1990's, Computing compatible tours for the symmetric traveling salesman problem, Analysis of the maximum level policy in a production-distribution system, Branch-and-cut algorithms for the undirected \(m\)-Peripatetic Salesman Problem, A branch-and-cut algorithm for a traveling salesman problem with pickup and delivery, Active-constraint variable ordering for faster feasibility of mixed integer linear programs, On the domino-parity inequalities for the STSP, Design of planar articulated mechanisms using branch and bound, Multi-step methods for choosing the best set of variables in regression analysis, Exact solution approaches for the multi-period degree constrained minimum spanning tree problem, A minimum spanning tree based heuristic for the travelling salesman tour, Novel approaches for portfolio construction using second order stochastic dominance, Path optimization with limited sensing ability, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Certification of an optimal TSP tour through 85,900 cities, The graphical relaxation: A new framework for the symmetric traveling salesman polytope, Hamiltonian path and symmetric travelling salesman polytopes, Efficient reformulation for 0-1 programs -- methods and computational results, \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates, Distances between traveling salesman tours, Genetic algorithms and traveling salesman problems, The use of dynamic programming in genetic algorithms for permutation problems, Combinatorial optimization and small polytopes, On using clique overlapping for detecting knapsack constraint redundancy and infeasibility in 0-1 mixed integer programs, 0-1 reformulations of the multicommodity capacitated network design problem, A note on formulations for the \(A\)-partition problem on hypergraphs, A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, A branch-and-bound algorithm for the mini-max spanning forest problem, Frequency assignment in mobile radio systems using branch-and-cut techniques, A heuristic for the pickup and delivery traveling salesman problem, On matroid parity and matching polytopes, Minimum cost capacity installation for multicommodity network flows, The node capacitated graph partitioning problem: A computational study, A linearization method for mixed 0--1 polynomial programs, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Economic spare capacity planning for DCS mesh-restorable networks, The complexity of cover inequality separation, Survey of facial results for the traveling salesman polytope, Perturbation heuristics for the pickup and delivery traveling salesman problem, Compact formulations of the Steiner traveling salesman problem and related problems, Separating capacity constraints in the CVRP using tabu search, About Lagrangian methods in integer optimization, Airline crew scheduling: state-of-the-art, Non delayed relax-and-cut algorithms, Mixed-integer programming techniques for the minimum sum-of-squares clustering problem, On the generation of metric TSP instances with a large integrality gap by branch-and-cut, The inventory routing problem with split deliveries, Unnamed Item, A new heuristic algorithm for laser antimissile strategy optimization, The biobjective travelling purchaser problem, Multilevel asymptotic-preserving Monte Carlo for kinetic-diffusive particle simulations of the Boltzmann-BGK equation, Problems of discrete optimization: challenges and main approaches to solve them, The Boolean Quadric Polytope, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Classification, models and exact algorithms for multi-compartment delivery problems, Automatic synthesis of data-flow analyzers, Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics, Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder), The multiple Steiner TSP with order constraints: complexity and optimization algorithms, Routing problems: A bibliography, Comparison of formulations for the inventory routing problem, The simultaneous semi-random model for TSP, A mathematical model for supply chain management of blood banks in India, Solving real-world linear ordering problems using a primal-dual interior point cutting plane method, Packing Steiner trees: A cutting plane algorithm and computational results, Combining simulated annealing with local search heuristics, Genetic algorithms for the traveling salesman problem, Maximum planar subgraphs and nice embeddings: Practical layout tools, A Scalable Algorithm for Sparse Portfolio Selection, The two-echelon inventory-routing problem with fleet management, On learning and branching: a survey, An Integer-Programming-Based Approach to the Close-Enough Traveling Salesman Problem, Order batching using an approximation for the distance travelled by pickers, Ideal polytopes and face structures of some combinatorial optimization problems, Vehicle routing on road networks: how good is Euclidean approximation?, A partitioning column approach for solving LED sorter manipulator path planning problems, A branch-and-cut algorithm for the one-commodity pickup and delivery location routing problem, Could we use a million cores to solve an integer program?, Reluplex: a calculus for reasoning about deep neural networks, Outer-product-free sets for polynomial optimization and oracle-based cuts, A Matheuristic for the Multivehicle Inventory Routing Problem, The effect of different mathematical formulations on a matheuristic algorithm for the production routing problem, Network Reconstruction – A New Approach to the Traveling Salesman Problem and Complexity, A stabilized column generation scheme for the traveling salesman subtour problem, How traveling salespersons prove their identity, On facet-inducing inequalities for combinatorial polytopes, Unnamed Item, Deriving compact extended formulations via LP-based separation techniques, Facets from gadgets, A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation, Practical Minimum Cut Algorithms, A polyhedral approach to an integer multicommodity flow problem, The minimum area spanning tree problem: formulations, Benders decomposition and branch-and-cut algorithms, A general system for heuristic minimization of convex functions over non-convex sets, Classical cuts for mixed-integer programming and branch-and-cut, Combinação de abordagens GLSP e ATSP para o problema de dimensionamento e sequenciamento de lotes de produção de suplementos para nutrição animal, Formulations and exact algorithms for the vehicle routing problem with time windows, Symmetric ILP: Coloring and small integers, A Unified Approach to Mixed-Integer Optimization Problems With Logical Constraints, On the vehicle routing problem, A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem, Classification of orthogonal arrays by integer programming, Deriving compact extended formulations via LP-based separation techniques, The travelling salesman problem with neighbourhoods: MINLP solution, Branch and cut methods for network optimization, A strong cutting plane algorithm for the robotic assembly line balancing problem, Using Lagrangian dual information to generate degree constrained spanning trees, Perspective cuts for a class of convex 0-1 mixed integer programs, Improved WLP and GWP lower bounds based on exact integer programming, A constraint generation algorithm for large scale linear programs using multiple-points separation, Evaluating the impact of AND/OR search on 0-1 integer linear programming, The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization, Strong IP formulations need large coefficients, Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design, A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation, Preprocessing composite cutting procedure: an approach to the integer model, The two-echelon production-routing problem, Improved branch-and-cut for the inventory routing problem based on a two-commodity flow formulation, Robust multi-product newsvendor model with uncertain demand and substitution, Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs, Statistical mechanics methods and phase transitions in optimization problems, A branch-and-cut algorithm for the inventory routing problem with pickups and deliveries, A branch-and-cut algorithm for an assembly routing problem, A generalized exchange heuristic for the capacitated vehicle routing problem, Provably good solutions for the traveling salesman problem, Integer programming approach to the printed circuit board grouping problem, Core group placement: allocation and provisioning of heterogeneous resources, Learning discontinuous piecewise affine fitting functions using mixed integer programming over lattice, Continuous relaxations for the traveling salesman problem, Feasibility pump algorithm for sparse representation under Laplacian noise, Knapsack constraint reformulation: A new approach that significantly reduces the number of sub-problems in the branch and bound algorithm, A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem, Formulations for an inventory routing problem, Modelling and Solving the Joint Order Batching and Picker Routing Problem in Inventories, Computing in combinatorial optimization, Exact algorithms for a selective Vehicle Routing Problem where the longest route is minimized, Gomory cuts revisited, Improving TSP Tours Using Dynamic Programming over Tree Decompositions., Modeling and solving the angular constrained minimum spanning tree problem, Cost-oriented assembly line balancing: model formulations, solution difficulty, upper and lower bounds, A cutting plane algorithm for the unrelated parallel machine scheduling problem, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, Unbiasing in iterative reconstruction algorithms for discrete compressed sensing, Algorithms for finding generalized minimum aberration designs, Model Development and Optimization for Space Engineering: Concepts, Tools, Applications, and Perspectives, Optimisation of the interconnecting network of a UMTS radio mobile telephone system, Nonlinear chance-constrained problems with applications to hydro scheduling
