The Traveling-Salesman Problem and Minimum Spanning Trees
From MaRDI portal
Publication:5633847
DOI10.1287/opre.18.6.1138zbMath0226.90047OpenAlexW2009803313WikidataQ55899753 ScholiaQ55899753MaRDI QIDQ5633847
Publication date: 1970
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.18.6.1138
Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)
Related Items
Improving Christofides' lower bound for the traveling salesman problem, Approximation Limits of Linear Programs (Beyond Hierarchies), Global strategies for augmenting the efficiency of TSP heuristics, Random Instances of Problems in NP – Algorithms and Statistical Physics, A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, A direct dual method for the mixed plant location problem with some side constraints, Integer Programming Formulations for Minimum Spanning Tree Interdiction, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, The traveling-salesman problem and minimum spanning trees: Part II, An effective approach for optimization of a perishable inventory system with uncertainty in both demand and supply, A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP, A deterministic better-than-3/2 approximation algorithm for metric TSP, Configuration‐based approach for topological problems in the design of wireless sensor networks, Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem, Hamiltonian circuits with generalised cost, A reinforced hybrid genetic algorithm for the traveling salesman problem, Polyhedral techniques in combinatorial optimization: matchings and tours, Refinement of Lagrangian bounds in optimization problems, The Minimum Spanning Tree Problem with Time Window Constraints, Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches, An efficient mixed integer linear programming model for the minimum spanning tree problem, Quantum complexity for vector domination problem, A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM, Unnamed Item, Hidden Hamiltonian Cycle Recovery via Linear Programming, Graphical-structure-based models for routing problems, A Simple LP Relaxation for the Asymmetric Traveling Salesman Problem, The travelling salesman problem and a class of polyhedra of diameter two, New Approximation Algorithms for (1,2)-TSP, Separating maximally violated comb inequalities in planar graphs, A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem, A New Formulation for the Travelling Salesman Problem, A modified subgradient algorithm for Lagrangean relaxation, Construction heuristics for the asymmetric TSP., Lineare Charakterisierungen von Travelling Salesman Problemen, A general scheme for automatic generation of search heuristics from specification \(dependencies^{*}\), Some relationships between lagrangian and surrogate duality in integer programming, Quantity discount decisions under conditions of multiple items, multiple suppliers and resource limitations, The traveling salesman problem: A duality approach, The Held—Karp algorithm and degree-constrained minimum 1-trees, Affinity propagation and uncapacitated facility location problems, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, On the existence of duality gaps for mixed integer programming, An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs, Modeling and Managing Uncertainty in Process Planning and Scheduling, Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, A restricted Lagrangean approach to the traveling salesman problem, Lagrangean Relaxation-Based Techniques for Solving Facility Location Problems, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, Unnamed Item, On the refinement of bounds of heuristic algorithms for the traveling salesman problem, Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Solving the Watchman Route Problem with Heuristic Search, Validation of subgradient optimization, On recursive computation of minimum spanning trees for special partial graphs, Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem, Steps toward accurate reconstructions of phylogenies from gene-order data., A new heuristic algorithm for laser antimissile strategy optimization, A Lagrangean decomposition for the maximum independent set problem applied to map labeling, Lagrangean relaxation. (With comments and rejoinder)., A fast optimization method based on a hierarchical strategy for the travelling salesman problem, Further results on the probabilistic traveling salesman problem, On spanning tree problems with multiple objectives, A quadratic integer programming method for minimizing the mean squared deviation of completion times, Distribution network design for fixed lifetime perishable products: a model and solution approach, On some difficult linear programs coming from set partitioning, 2-change for k-connected networks, Hybrid approaches for the two-scenario max-min knapsack problem, Better s-t-Tours by Gao Trees, Improved Approximations for Cubic Bipartite and Cubic TSP, Weighted amplifiers and inapproximability results for travelling salesman problem, Approximation algorithms for the directed \(k\)-Tour and \(k\)-Stroll problems, A Lagrangian relaxation algorithm for optimizing a bi-objective agro-supply chain model considering CO\(_2\) emissions, An exact algorithm for the capacitated shortest spanning arborescence, The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching, Efficient optimization of the Held-Karp lower bound, The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems, Solving the anti-covering location problem using Lagrangian relaxation, Solving large-scale TSP using a fast wedging insertion partitioning approach, Improving the robustness of EPS to solve the TSP, Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies, Genetic algorithms for the traveling salesman problem, Multi-period stochastic programming models for two-tiered emergency medical service system, An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem, Designing and reporting on computational experiments with heuristic methods, The Lagrangian relaxation for the combinatorial integral approximation problem, On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms, Subtour elimination constraints imply a matrix-tree theorem SDP constraint for the TSP, Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems, Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length, On the computational efficiency of subgradient methods: a case study with Lagrangian bounds, Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm, Upper and lower bounds for the single source capacitated location problem., A stabilized column generation scheme for the traveling salesman subtour problem, Parallel machine scheduling with earliness--tardiness penalties and additional resource con\-straints., The symmetric travelling salesman problem. II: New low bounds, A discrete cross aisle design model for order-picking warehouses, The multidimensional 0-1 knapsack problem: an overview., Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem, Cut-and-solve: An iterative search strategy for combinatorial optimization problems, FINITE SIZE SCALING AND CRITICAL TRANSITION IN CONSTRAINED TRAVELING SALESMAN PROBLEM, A new bilevel formulation for the vehicle routing problem and a solution method using a genetic algorithm, Formulations and exact algorithms for the vehicle routing problem with time windows, Hybrid optimization methods for time-dependent sequencing problems, Dynamic convexification within nested Benders decomposition using Lagrangian relaxation: an application to the strategic bidding problem, Inventory rebalancing and vehicle routing in bike sharing systems, Improved integrality gap upper bounds for traveling salesperson problems with distances one and two, Comparison of bundle and classical column generation, \(\frac{13}{9}\)-approximation for graphic TSP, Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem, A dual bounding scheme for a territory design problem, An application of a Lagrangian-type relaxation for the uncapacitated facility location problem, The selection and scheduling of telecommunication calls with time windows, A note on relatives to the Held and Karp 1-tree problem, Studying properties of Lagrangian bounds for many-to-many assignment problems, A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem, On the core of traveling salesman games, SDP Relaxations for Some Combinatorial Optimization Problems, The seriation problem and the travelling salesman problem, Reassembling Trees for the Traveling Salesman, Better \(s-t\)-tours by Gao trees, Improved approximations for cubic bipartite and cubic TSP, An improved lower bound for the traveling salesman constant, Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop, A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality, Continuous relaxations for the traveling salesman problem, Nonoblivious 2-Opt heuristics for the traveling salesman problem, Multiple bottleneck assignment problem, Coordination mechanisms with mathematical programming models for decentralized decision-making: a literature review, Lagrangian relaxation of the generic materials and operations planning model, Optimizing tabu list size for the traveling salesman problem, Constrained spanning trees and the traveling salesman problem, A feasibility-ensured Lagrangian heuristic for general decomposable problems, Multi-constrained matroidal knapsack problems, Fictitious upper bounds in an algorithm for the symmetric traveling salesman problem, New lower bounds for the symmetric travelling salesman problem, Stronger \(K\)-tree relaxations for the vehicle routing problem, Plant location with minimum inventory, Estimating the Held-Karp lower bound for the geometric TSP, Minimum directed 1-subtree relaxation for score orienteering problem, An effective implementation of the Lin-Kernighan traveling salesman heuristic, Implementation analysis of efficient heuristic algorithms for the traveling salesman problem, Algorithms for a multi-level network optimization problem, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, A hybrid genetic-GRASP algorithm using Lagrangean relaxation for the traveling salesman problem, A new variant of a vehicle routing problem: Lower and upper bounds, Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems, A technique for speeding up the solution of the Lagrangean dual, Analyzing tradeoffs between zonal constraints and accessibility in facility location, An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers, An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality, Relaxed tours and path ejections for the traveling salesman problem, Solving the shortest route cut and fill problem using simulated annealing, The cardinality constrained covering traveling salesman problem, LP-based algorithms for multistage minimization problems, A heuristic for cumulative vehicle routing using column generation, The 2-quasi-greedy algorithm for cardinality constrained matroid bases, Polyhedral proof methods in combinatorial optimization, The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm, Efficient algorithms for the capacitated concentrator location problem, A computational evaluation of two subgradient search methods, On a mixture of the fix-and-relax coordination and Lagrangian substitution schemes for multistage stochastic mixed integer programming, Duality for mixed-integer convex minimization, Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming, A linear-time algorithm for finding a minimum spanning pseudoforest, Evolutionary algorithms and matroid optimization problems, Lower bounding procedure for the asymmetric quadratic traveling salesman problem, A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem, A hybrid Lagrangean heuristic with GRASP and path-relinking for set \(k\)-covering, Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation, Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs, A matroid algorithm and its application to the efficient solution of two optimization problems on graphs, Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation, A hybrid approach of bundle and Benders applied large mixed linear integer problem, A Lagrangean approach to the degree-constrained minimum spanning tree problem, Lagrangian dual ascent by generalized linear programming, A lower bound for the breakpoint phylogeny problem, A simple LP relaxation for the asymmetric traveling salesman problem, Lagrangian heuristic for a class of the generalized assignment problems, The combinatorial bandwidth packing problem, Some aspects of integer programming duality, On the choice of step size in subgradient optimization, Lower and upper bounds for the \(m\)-peripatetic vehicle routing problem, Heuristics and their design: A survey, Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry, An exact algorithm for the Boolean connectivity problem for \(k\)-CNF, An exact algorithm to minimize the makespan in project scheduling with scarce resources and generalized precedence relations, A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem, A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation, Exact hybrid algorithms for solving a bi-objective vehicle routing problem, Analyzing the Held-Karp TSP bound: A monotonicity property with application, A comparison of lower bounds for the symmetric circulant traveling salesman problem, Serial and parallel simulated annealing and tabu search algorithms for the traveling salesman problem, The capacitated maximal covering location problem with backup service, Minimal spanning trees and partial sorting, A heuristic decomposition approach to optimal control in a water supply model, Nonlinear resolving functions for the travelling salesman problem, Spanning closed walks and TSP in 3-connected planar graphs, The symmetric traveling salesman problem and edge exchanges in minimal 1- trees, Certifying algorithms, Small spectral gap in the combinatorial Laplacian implies Hamiltonian, Improved parameterized algorithms for minimum link-length rectilinear spanning path problem, A decomposition-based pricing method for solving a large-scale MILP model for an integrated fishery, The hierarchical network design problem with transshipment facilities, Intersection representations of matrices by subtrees and unicycles on graphs, Improved filtering for weighted circuit constraints, Weighted matching as a generic pruning technique applied to optimization constraints, Travelling salesman problem tools for microcomputers, A new warmstarting strategy for the primal-dual column generation method, How to find Steiner minimal trees in Euclidean \(d\)-space, Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm, Optimal partitioning of a data set based on the \(p\)-median model, The \(k\)-path tree matroid and its applications to survivable network design, The traveling salesman problem: An overview of exact and approximate algorithms, Configuration of fully replicated distributed database system over wide area networks, Locating concentrators in centralized computer networks, An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem, Paroids: A canonical format for combinatorial optimization, A note on the prize collecting traveling salesman problem, Analysis of the Held-Karp lower bound for the asymmetric TSP, On the solving strategy in composite heuristics, Survivable networks, linear programming relaxations and the parsimonious property, Capacitated emergency facility siting with multiple levels of backup, Ergodic, primal convergence in dual subgradient schemes for convex programming. II: The case of inconsistent primal problems, Experiments with LAGRASP heuristic for set \(k\)-covering, The multicovering problem, A decomposition technique for mixed integer programming problems, Symmetric weight constrained traveling salesman problem: Local search, An homage to Joseph-Louis Lagrange and Pierre Huard, The directed orienteering problem, Match twice and stitch: a new TSP tour construction heuristic., A Lagrangian bound for many-to-many assignment problems, Solving the combinatorial double auction problem, Stochastic set packing problem, An efficient procedure for obtaining feasible solutions to the n-city traveling salesman problem, Symmetric traveling salesman problems, A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem, The indefinite period traveling salesman problem, A language and a program for stating and solving combinatorial problems, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, The complexity ecology of parameters: An illustration using bounded max leaf number, On the integrality ratio for tree augmentation, Uncapacitated flow-based extended formulations, The symmetric clustered traveling salesman problem, A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem, Minimizing the completion time of a project under resource constraints and feeding precedence relations: a Lagrangian relaxation based lower bound, General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic, Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem, A non-delayed relax-and-cut algorithm for scheduling problems with parallel machines, due dates and sequence-dependent setup times, Efficient spanning trees, Zero-one integer programs with few contraints - lower bounding theory, Optimizing over the subtour polytope of the travelling salesman problem, Solution of large-scale symmetric travelling salesman problems, An algorithm for the traveling salesman problem with pickup and delivery customers, A decomposition method for large scale MILPs, with performance guarantees and a power system application, Airline crew scheduling: state-of-the-art
