scientific article

Martin Grötschel, Manfred W. Padberg

Publication date: 1985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

survey polytopes traveling salesman valid inequalities facets polyhedral theory clique inequalities sequential lifting

Integer programming (90C10) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Polytopes and polyhedra (52Bxx)

Related Items (77)

The Steiner cycle polytope ⋮ On the orthogonal Latin squares polytope ⋮ Polyhedral proof methods in combinatorial optimization ⋮ A lifting procedure for asymmetric traveling salesman polytope and a large new class of facets ⋮ Further results on the probabilistic traveling salesman problem ⋮ Optimization of a 532-city symmetric traveling salesman problem by branch and cut ⋮ Clique tree inequalities define facets of the asymmetric traveling salesman polytope ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Improved integer linear programming formulations for the job sequencing and tool switching problem ⋮ A branch-and-cut framework for the consistent traveling salesman problem ⋮ Complete linear descriptions of small asymmetric traveling salesman polytopes ⋮ On the Skeleton of the Polytope of Pyramidal Tours ⋮ Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: an application to fish aggregating devices ⋮ Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm ⋮ An exact algorithm for a vehicle-and-driver scheduling problem ⋮ A polynomial-time solution to Papadimitriou and Steiglitz's ``traps ⋮ The pickup and delivery problem: Faces and branch-and-cut algorithm ⋮ Faces of diameter two on the Hamiltonian cycle polytope ⋮ Incorporating facet-inducing inequalities into graphical-construct-based Lagrangian relaxation methodologies ⋮ On cutting-plane proofs in combinatorial optimization ⋮ Interchange graphs and the Hamiltonian cycle polytope ⋮ Some thoughts on combinatorial optimisation ⋮ On the polyhedral structure of uniform cut polytopes ⋮ The multi‐depot family traveling salesman problem and clustered variants: Mathematical formulations and branch‐&‐cut based methods ⋮ Some properties of the skeleton of the pyramidal tours polytope ⋮ Complexity of branch-and-bound and cutting planes in mixed-integer optimization ⋮ Computational experience with a branch-and-cut algorithm for flowshop scheduling with setups. ⋮ Facet Generating Techniques ⋮ Multiperiod location-routing with decoupled time scales ⋮ Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints ⋮ A lexicographic semiorder polytope and probabilistic representations of choice ⋮ Analyzing the Held-Karp TSP bound: A monotonicity property with application ⋮ Facet identification for the symmetric traveling salesman polytope ⋮ Polyhedral results for a vehicle routing problem ⋮ The wheels of the OLS polytope: Facets and separation ⋮ A spectral method for concordant polyhedral faces ⋮ An analytical comparison of different formulations of the travelling salesman problem ⋮ Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search ⋮ Facets of two Steiner arborescence polyhedra ⋮ Formulations and exact algorithms for the vehicle routing problem with time windows ⋮ Combined route capacity and route length models for unit demand vehicle routing problems ⋮ Recent Models and Algorithms for One-to-One Pickup and Delivery Problems ⋮ The traveling salesman problem: An overview of exact and approximate algorithms ⋮ A comparative analysis of several asymmetric traveling salesman problem formulations ⋮ Energy-efficient rail guided vehicle routing for two-sided loading/unloading automated freight handling system ⋮ The traveling purchaser problem and its variants ⋮ Faces with large diameter on the symmetric traveling salesman polytope ⋮ The complexity of lifted inequalities for the knapsack problem ⋮ On the completability of incomplete Latin squares ⋮ Solving school bus routing using the multiple vehicle traveling purchaser problem: a branch-and-cut approach ⋮ Facets of the \((s,t)-p\)-path polytope ⋮ Branch and cut methods for network optimization ⋮ Branch-and-cut algorithms for the undirected \(m\)-Peripatetic Salesman Problem ⋮ New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints ⋮ A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ Facets of the polytope of the asymmetric travelling salesman problem with replenishment arcs ⋮ The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints ⋮ Facets of the \(p\)-cycle polytope ⋮ Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? ⋮ The skeleton of the symmetric Traveling Salesman Polytope ⋮ The graphical relaxation: A new framework for the symmetric traveling salesman polytope ⋮ A spectral approach to polyhedral dimension ⋮ Combinatorial optimization and small polytopes ⋮ Stability aspects of the traveling salesman problem based on \(k\)-best solutions ⋮ Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm ⋮ Branch-and-cut for the pickup and delivery traveling salesman problem with FIFO loading ⋮ Partial monotonizations of Hamiltonian cycle polytopes: Dimensions and diameters ⋮ A polyhedral approach to sequence alignment problems ⋮ On the facial structure of symmetric and graphical traveling salesman polyhedra ⋮ Survey of facial results for the traveling salesman polytope ⋮ Optimizing over the subtour polytope of the travelling salesman problem ⋮ A location-or-routing problem with partial and decaying coverage ⋮ Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph ⋮ Solution of large-scale symmetric travelling salesman problems ⋮ A facet generation and relaxation technique applied to an assignment problem with side constraints ⋮ Canonical equation sets for classes of concordant polytopes ⋮ Light on the infinite group relaxation. I: Foundations and taxonomy

This page was built for publication: