The traveling-salesman problem and minimum spanning trees: Part II
From MaRDI portal
Publication:5641007
DOI10.1007/BF01584070zbMath0232.90038WikidataQ96162761 ScholiaQ96162761MaRDI QIDQ5641007
Publication date: 1971
Published in: Mathematical Programming (Search for Journal in Brave)
Related Items
The 2-quasi-greedy algorithm for cardinality constrained matroid bases ⋮ The salesman and the tree: the importance of search in CP ⋮ Polyhedral proof methods in combinatorial optimization ⋮ The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm ⋮ Optimal capacitated ring trees ⋮ Edge exchanges in the degree-constrained minimum spanning tree problem ⋮ A cross-decomposition scheme with integrated primal-dual multi-cuts for two-stage stochastic programming investment planning problems ⋮ Optimization of a 532-city symmetric traveling salesman problem by branch and cut ⋮ Computing assortative mixing by degree with the \(s\)-metric in networks using linear programming ⋮ Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ On common edges in optimal solutions to traveling salesman and other optimization problems ⋮ A hybrid Lagrangean heuristic with GRASP and path-relinking for set \(k\)-covering ⋮ Scenario cluster decomposition of the Lagrangian dual in two-stage stochastic mixed 0-1 optimization ⋮ Cluster Lagrangean decomposition in multistage stochastic optimization ⋮ 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 ⋮ Application of Lagrangian relaxation to computer network control ⋮ Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem ⋮ 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 ⋮ Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem ⋮ The quadratic knapsack problem -- a survey ⋮ A lower bound for the breakpoint phylogeny problem ⋮ A decomposition heuristic for the maximal covering location problem ⋮ Solution of a tinned iron purchasing problem by Lagrangean relaxation ⋮ Minmax combinatorial optimization ⋮ New filtering for \textsc{AtMostNValue} and its weighted variant: a Lagrangian approach ⋮ The combinatorial bandwidth packing problem ⋮ Combining probabilistic algorithms, constraint programming and Lagrangian relaxation to solve the vehicle routing problem ⋮ Some aspects of integer programming duality ⋮ On the choice of step size in subgradient optimization ⋮ Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times ⋮ Heuristics and their design: A survey ⋮ Lower bounds for the symmetric travelling salesman problem from Lagrangean relaxations ⋮ 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 ⋮ Classification of travelling salesman problem formulations ⋮ An improvement in the Gavish-Shlifer algorithm for a class of transportation scheduling problems ⋮ A heuristic decomposition approach to optimal control in a water supply model ⋮ The symmetric traveling salesman problem and edge exchanges in minimal 1- trees ⋮ Certifying algorithms ⋮ Surrogate duality relaxation for job shop scheduling ⋮ Improved filtering for weighted circuit constraints ⋮ Weighted matching as a generic pruning technique applied to optimization constraints ⋮ An additive bounding procedure for the asymmetric travelling salesman problem ⋮ On single courier problem ⋮ A new warmstarting strategy for the primal-dual column generation method ⋮ How to find Steiner minimal trees in Euclidean \(d\)-space ⋮ Topological design of computer communication networks -- the overall design problem ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ A cross entropy-lagrangean hybrid algorithm for the multi-item capacitated lot-sizing problem with setup times ⋮ A system for priority routing and capacity assignment in packet switched networks ⋮ An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem ⋮ On the solving strategy in composite heuristics ⋮ Real-time vehicle rerouting problems with time windows ⋮ A modified Lin--Kernighan traveling-salesman heuristic ⋮ Survivable networks, linear programming relaxations and the parsimonious property ⋮ Ergodic, primal convergence in dual subgradient schemes for convex programming. II: The case of inconsistent primal problems ⋮ An exact algorithm for side-chain placement in protein design ⋮ 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 ⋮ Models, relaxations and exact approaches for the capacitated vehicle routing problem ⋮ Match twice and stitch: a new TSP tour construction heuristic. ⋮ Bounds for 3-matroid intersection problems ⋮ On efficient matheuristic algorithms for multi-period stochastic facility location-assignment problems ⋮ A branch and bound algorithm for the capacitated vehicle routing problem ⋮ Hub-and-spoke network design and fleet deployment for string planning of liner shipping ⋮ A language and a program for stating and solving combinatorial problems ⋮ Algorithms for updating minimal spanning trees ⋮ Certification of an optimal TSP tour through 85,900 cities ⋮ The seriation problem and the travelling salesman problem ⋮ On the integrality ratio for tree augmentation ⋮ A characterization of linear admissible transformations for the m- travelling salesmen problem: A result of Berenguer ⋮ Procedures for travelling salesman problems with additional constraints ⋮ A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality ⋮ A proximal cutting plane method using Chebychev center for nonsmooth convex optimization ⋮ Models and Lagrangian heuristics for a two-level lot-sizing problem with bounded inventory ⋮ A Lagrangian relaxation approach for the multiple sequence alignment problem ⋮ Optimizing tabu list size for the traveling salesman problem ⋮ Heuristically guided algorithm for k-parity matroid problems ⋮ The symmetric clustered traveling salesman problem ⋮ A Lagrangian-based algorithm for a multiple depot, multiple traveling salesmen problem ⋮ Relaxation heuristics for a generalized assignment problem ⋮ General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic ⋮ Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem ⋮ Transforming asymmetric into symmetric traveling salesman problems ⋮ An equivalent subproblem relaxation for improving the solution of a class of transportation scheduling problems ⋮ Solving capacitated clustering problems ⋮ Heuristics and reduction methods for multiple constraints 0-1 linear programming problems ⋮ Solution of large-scale symmetric travelling salesman problems ⋮ An algorithm for the traveling salesman problem with pickup and delivery customers ⋮ The multiple depot, multiple traveling salesmen facility-location problem: Vehicle range, service frequency, and heuristic implementations ⋮ An upper bound for the speedup of parallel best-bound branch-and-bound algorithms ⋮ Average-case analysis of best-first search in two representative directed acyclic graphs ⋮ About Lagrangian methods in integer optimization ⋮ Airline crew scheduling: state-of-the-art ⋮ Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games ⋮ Lagrangean relaxation. (With comments and rejoinder). ⋮ Subgradient optimization applied to a discrete nonlinear problem in engineering design ⋮ Further results on the probabilistic traveling salesman problem ⋮ On some difficult linear programs coming from set partitioning ⋮ DYNAMICAL ADJUSTMENT OF THE PROX-PARAMETER IN BUNDLE METHODS ⋮ Computational efficiency of the simplex embedding method in convex nondifferentiable optimization ⋮ A class of convergent primal-dual subgradient algorithms for decomposable convex programs ⋮ A Lagrangian relaxation algorithm for sparse quadratic assignment problems ⋮ Scenario cluster Lagrangean decomposition for risk averse in multistage stochastic optimization ⋮ The vehicle rescheduling problem with retiming ⋮ An exact algorithm for the capacitated shortest spanning arborescence ⋮ The \(p\)-Lagrangian relaxation for separable nonconvex MIQCQP problems ⋮ Solving the anti-covering location problem using Lagrangian relaxation ⋮ Improving the robustness of EPS to solve the TSP ⋮ A direct dual method for the mixed plant location problem with some side constraints ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ Optimizing production capacity and safety stocks in general acyclic supply chains ⋮ Simultaneously exploiting two formulations: an exact Benders decomposition approach ⋮ Designing and reporting on computational experiments with heuristic methods ⋮ New variants of bundle methods ⋮ Greedy initialization for distributed persistent monitoring in network systems ⋮ The Lagrangian relaxation for the combinatorial integral approximation problem ⋮ On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms ⋮ Some problems in discrete optimization ⋮ A bound for the symmetric travelling salesman problem through matroid formulation ⋮ An exact algorithm for general, orthogonal, two-dimensional knapsack problems ⋮ Joint chance constrained shortest path problem with Copula theory ⋮ A 4/3-approximation for TSP on cubic 3-edge-connected graphs ⋮ Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ Lagrangian decomposition for large-scale two-stage stochastic mixed 0-1 problems ⋮ The Minimum Spanning Tree Problem with Time Window Constraints ⋮ Incorporating Aggregate Diversity in Recommender Systems Using Scalable Optimization Approaches ⋮ Bounds for the symmetric 2-peripatetic salesman problem ⋮ Upper and lower bounds for the single source capacitated location problem. ⋮ Parallel machine scheduling with earliness--tardiness penalties and additional resource con\-straints. ⋮ A Lagrangian heuristic for a train-unit assignment problem ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem ⋮ A variable target value method for nondifferentiable optimization ⋮ The travelling salesman problem and a class of polyhedra of diameter two ⋮ Cut-and-solve: An iterative search strategy for combinatorial optimization problems ⋮ Collapsing Superstring Conjecture ⋮ Natalie 2.0: sparse global network alignment as a special case of quadratic assignment ⋮ Constrained 0-1 quadratic programming: basic approaches and extensions ⋮ Lagrangean relaxation with clusters for point-feature cartographic label placement problems ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ A heuristic algorithm for the set covering problem ⋮ A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem ⋮ Integer programming approaches to the travelling salesman problem ⋮ Edge-disjoint spanning trees and the number of maximum state circles of a graph ⋮ Comparison of bundle and classical column generation ⋮ Lineare Charakterisierungen von Travelling Salesman Problemen ⋮ APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME ⋮ Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem ⋮ A dual bounding scheme for a territory design problem ⋮ The selection and scheduling of telecommunication calls with time windows ⋮ A dual algorithm for the one-machine scheduling problem ⋮ A 3-flip neighborhood local search for the set covering problem ⋮ Upper bounds and exact algorithms for \(p\)-dispersion problems ⋮ On convergence rates of subgradient optimization methods ⋮ The omnipresence of Lagrange ⋮ The traveling salesman problem: A duality approach ⋮ The Held—Karp algorithm and degree-constrained minimum 1-trees ⋮ A continuous variable representation of the traveling salesman problem ⋮ Using cutting planes to solve the symmetric Travelling Salesman problem ⋮ Dynamic programming algorithms and Lagrangian lower bounds for a discrete lot streaming problem in a two-machine flow shop ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ AUGMENTED LAGRANGEAN RELAXATIONS IN GENERAL MIXED INTEGER PROGRAMMING ⋮ Continuous relaxations for the traveling salesman problem ⋮ Nonoblivious 2-Opt heuristics for the traveling salesman problem ⋮ Lagrangean/surrogate relaxation for generalized assignment problems ⋮ Coordination mechanisms with mathematical programming models for decentralized decision-making: a literature review ⋮ Lagrangian relaxation of the generic materials and operations planning model ⋮ An MDD-Based Lagrangian Approach to the Multicommodity Pickup-and-Delivery TSP ⋮ Lagrangean decompositions for the unconstrained binary quadratic programming problem ⋮ Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations ⋮ A restricted Lagrangean approach to the traveling salesman problem ⋮ Constrained spanning trees and the traveling salesman problem ⋮ An application-oriented guide for designing Lagrangean dual ascent algorithms ⋮ New lower bounds for the symmetric travelling salesman problem ⋮ Computing in combinatorial optimization ⋮ Plant location with minimum inventory ⋮ Estimating the Held-Karp lower bound for the geometric TSP ⋮ Minimum directed 1-subtree relaxation for score orienteering problem ⋮ The simple plant location problem: Survey and synthesis ⋮ Generalized spanning trees ⋮ A path relinking approach with ejection chains for the generalized assignment problem ⋮ An effective implementation of the Lin-Kernighan traveling salesman heuristic ⋮ Implementation analysis of efficient heuristic algorithms for 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 ⋮ Investigation of optimization methods and their applications ⋮ 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 ⋮ Validation of subgradient optimization ⋮ Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem ⋮ Relaxed tours and path ejections for the traveling salesman problem ⋮ Solving the shortest route cut and fill problem using simulated annealing ⋮ Optimal set partitioning, matchings and lagrangian duality ⋮ Lagrangian bounds for large‐scale multicommodity network design: a comparison between Volume and Bundle methods ⋮ An effective approach for optimization of a perishable inventory system with uncertainty in both demand and supply ⋮ Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ Fuzzy cleaner production in assembly flexible job-shop scheduling with machine breakdown and batch transportation: Lagrangian relaxation ⋮ A branch-and-bound approach for a vehicle routing problem with customer costs ⋮ Construction heuristics for the asymmetric TSP. ⋮ Iterative state-space reduction for flexible computation ⋮ Lagrangian heuristics for the quadratic knapsack problem
Cites Work
- A note on two problems in connexion with graphs
- On the shortest spanning subtree of a graph and the traveling salesman problem
- A Dynamic Programming Approach to Sequencing Problems
- Computer Solutions of the Traveling Salesman Problem
- Optimal assignments in an ordered set: An application of matroid theory
- The Traveling Salesman Problem: A Survey
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The Relaxation Method for Linear Inequalities
- The Relaxation Method for Linear Inequalities
