The traveling salesman problem on a graph and some related integer polyhedra

From MaRDI portal

Publication:3675933

Jump to:navigation, search

DOI10.1007/BF01582008zbMath0562.90095OpenAlexW2083210138WikidataQ96162135 ScholiaQ96162135MaRDI QIDQ3675933

Cornuéjols, Gérard, Denis Naddef, Jean Fonlupt

Publication date: 1985

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01582008

zbMATH Keywords

polynomial algorithm Steiner tree facet series-parallel graph efficient algorithm integer polyhedra comb inequalities graphical traveling Salesman minimum length cycle

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Combinatorial aspects of matroids and geometric lattices (05B35) Polytopes and polyhedra (52Bxx)

Related Items

Improving a constructive heuristic for the general routing problem, Arborescence polytopes for series-parallel graphs, Two-edge connected spanning subgraphs and polyhedra, The Steiner tree problem. I: Formulations, compositions and extensions and extension of facets, The Steiner tree problem. II: Properties and classes of facets, A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets, A polyhedral approach to the rural postman problem, ILP formulation of the degree-constrained minimum spanning hierarchy problem, Half integer extreme points in the linear relaxation of the 2-edge-connected subgraph polyhedron, The Steiner traveling salesman problem with online edge blockages, An algorithm for dynamic order-picking in warehouse operations, Good triangulations yield good tours, Pricing routines for vehicle routing with time windows on road networks, Empirical analysis for the VRPTW with a multigraph representation for the road network, The Steiner traveling salesman problem with online advanced edge blockages, A new class of cutting planes for the symmetric travelling salesman problem, The multiple Steiner TSP with order constraints: complexity and optimization algorithms, On perfectly two-edge connected graphs, Routing problems: A bibliography, A simple LP-based approximation algorithm for the matching augmentation problem, On the graphical relaxation of the symmetric traveling salesman polytope, Submodularity and the traveling salesman problem, Design and control of warehouse order picking: a literature review, On approximately fair cost allocation in Euclidean TSP games, Vehicle routing on road networks: how good is Euclidean approximation?, An efficient and general approach for the joint order batching and picker routing problem, A partitioning column approach for solving LED sorter manipulator path planning problems, Optimally solving the joint order batching and picker routing problem, Upgrading edges in the graphical TSP, A note on computational aspects of the Steiner traveling salesman problem, Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices, The Steiner bi-objective shortest path problem, Polyhedral techniques in combinatorial optimization: matchings and tours, Complexity of branch-and-bound and cutting planes in mixed-integer optimization, Box-total dual integrality and edge-connectivity, The \(k\) edge-disjoint 3-hop-constrained paths polytope, A discrete cross aisle design model for order-picking warehouses, On the cut polyhedron., The \(k\)-edge connected subgraph problem. I: Polytopes and critical extreme points., Multigraph modeling and adaptive large neighborhood search for the vehicle routing problem with time windows, Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs, The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities, The traveling salesman problem in graphs with some excluded minors, Formulating and solving the integrated batching, routing, and picker scheduling problem in a real-life spare parts warehouse, TSP on Cubic and Subcubic Graphs, On matrices with the Edmonds-Johnson property arising from bidirected graphs, On the general routing polytope, Circuit and bond polytopes on series-parallel graphs, On the convex hull of feasible solutions to certain combinatorial problems, The anti-join composition and polyhedra, Traveling salesman path problems, Polyhedral study of the capacitated vehicle routing problem, The Steiner traveling salesman problem and its extensions, \(\frac{13}{9}\)-approximation for graphic TSP, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Branch and cut methods for network optimization, GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY, On survivable network polyhedra, Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems, On the dominant of the Steiner 2-edge connected subgraph polytope, Steiner trees and polyhedra, A branch‐and‐cut algorithm for the nonpreemptive swapping problem, On the Steiner 2-edge connected subgraph polytope, Exact algorithms for the order picking problem, Minimum-weight two-connected spanning networks, Approximating the smallest k -edge connected spanning subgraph by LP-rounding, A branch-and-cut algorithm for the k-edge connected subgraph problem, Recent results on Arc Routing Problems: An annotated bibliography, On the distance-constrained close enough arc routing problem, Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs, The box-TDI system associated with 2-edge connected spanning subgraphs, A new integer programming formulation of the graphical traveling salesman problem, Routing Optimization Under Uncertainty, The graphical relaxation: A new framework for the symmetric traveling salesman polytope, Hamiltonian path and symmetric travelling salesman polytopes, Designing Networks with Good Equilibria under Uncertainty, A new integer programming formulation of the graphical traveling salesman problem, The general routing polyhedron: A unifying framework, Packing circuits in matroids, An Improved Analysis of the Mömke--Svensson Algorithm for Graph-TSP on Subquartic Graphs, Cut Dominants and Forbidden Minors, Weighted connected domination and Steiner trees in distance-hereditary graphs, An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem, The graphical traveling salesperson problem has no integer programming formulation in the original space, New inequalities for the general routing problem, Modelling and Solving the Joint Order Batching and Picker Routing Problem in Inventories, \(k\)-edge connected polyhedra on series-parallel graphs, Using a TSP heuristic for routing order pickers in warehouses, Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal, Partial monotonizations of Hamiltonian cycle polytopes: Dimensions and diameters, The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra, On the facets and diameter of thek-cycle polytope, On the facial structure of symmetric and graphical traveling salesman polyhedra, The 2-edge-connected subgraph polyhedron, Survey of facial results for the traveling salesman polytope, Critical extreme points of the 2-edge connected spanning subgraph polytope, Optimizing over the subtour polytope of the travelling salesman problem, The Steiner tree polytope and related polyhedra, Compact formulations of the Steiner traveling salesman problem and related problems, Light on the infinite group relaxation. I: Foundations and taxonomy

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:3675933&oldid=17144831"