A cutting plane algorithm for the windy postman problem

DOI10.1007/BF01581206zbMath0761.90082OpenAlexW2070970155MaRDI QIDQ1198736

Martin Grötschel, Zaw Win

Publication date: 16 January 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

simplex methodwindy postman problemcutting plane algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05) Combinatorial optimization (90C27) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Lower bounds and heuristics for the windy rural postman problem, New heuristic algorithms for the windy rural postman problem, Routing problems: A bibliography, Plowing with precedence in polynomial time, New results on the windy postman problem, A branch-and-price algorithm for the windy rural postman problem, A cutting plane algorithm for the windy postman problem, Series-parallel graphs are windy postman perfect, Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems, A comparison of two different formulations for arc routing problems on mixed graphs, Recent results on Arc Routing Problems: An annotated bibliography, OAR lib: an open source arc routing library, A GRASP heuristic for the mixed Chinese postman problem, An integer programming approach for the Chinese postman problem with time-dependent travel time, The time-dependent rural postman problem: polyhedral results

Uses Software

• XMP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the windy postman problem
• Solution of large-scale symmetric travelling salesman problems
• On the windy postman problem on Eulerian graphs
• A cutting plane algorithm for a clustering problem
• Assignment and matching problems: solution methods with FORTRAN-programs. In cooperation with T. Bönniger and G. Katzakidis
• The ellipsoid method and its consequences in combinatorial optimization
• A cutting plane algorithm for the windy postman problem
• A Cutting Plane Algorithm for the Linear Ordering Problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Solving matching problems with linear programming
• Odd Minimum Cut-Sets and b-Matchings
• On the complexity of edge traversing
• Matching, Euler tours and the Chinese postman
• On the surface duality of linear graphs