NDLI: New results on the Windy Postman Problem

Content Provider	Springer Nature Link
Author	Oswald, Marcus Sanchis, José M. Plana, Isaac Corberán, Angel Reinelt, Gerhard
Copyright Year	2010
Abstract	In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd zigzag inequalities, are Chvátal–Gomory inequalities of rank at most 2. Moreover, a branch-and-cut algorithm that incorporates two new separation algorithms for all the previously mentioned inequalities and a new heuristic procedure to obtain upper bounds are presented. Finally, the performance of a branch-and-cut algorithm over several sets of large WPP and MCPP instances, with up to 3,000 nodes and 9,000 edges (and arcs in the MCPP case), shows that, to our knowledge, this is the best algorithm to date for the exact resolution of the WPP and the MCPP.
Ending Page	332
Page Count	24
Starting Page	309
File Format	PDF
ISSN	00255610
e-ISSN	14364646
Journal	Mathematical Programming
Issue Number	1-2
Volume Number	132
Language	English
Publisher	Springer-Verlag
Publisher Date	2010-08-10
Publisher Place	Berlin, Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Polyhedral combinatorics Arc routing Mathematical Methods in Physics Facets Mixed Chinese Postman Problem Mathematics of Computing Calculus of Variations and Optimal Control; Optimization Numerical Analysis Theoretical, Mathematical and Computational Physics Windy Postman Problem Combinatorics Polyhedral combinatorics, branch-and-bound, branch-and-cut
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Zigzag inequalities: a new class of facet-inducing inequalities for Arc Routing Problems

A branch-and-cut algorithm for the maximum benefit Chinese postman problem

A note on the Undirected Rural Postman Problem polytope

The Windy General Routing Polyhedron: A Global View of Many Known Arc Routing Polyhedra

Polyhedral results and a Branch-and-cut algorithm for the $$k$$ -cardinality tree problem

A polyhedral approach to the single row facility layout problem

The convex recoloring problem: polyhedra, facets and computational experiments

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

Improved lower bounds and exact algorithm for the capacitated arc routing problem

New results on the Windy Postman Problem

Similar Documents

Zigzag inequalities: a new class of facet-inducing inequalities for Arc Routing Problems

A branch-and-cut algorithm for the maximum benefit Chinese postman problem

A note on the Undirected Rural Postman Problem polytope

The Windy General Routing Polyhedron: A Global View of Many Known Arc Routing Polyhedra

Polyhedral results and a Branch-and-cut algorithm for the $$k$$ -cardinality tree problem

A polyhedral approach to the single row facility layout problem

The convex recoloring problem: polyhedra, facets and computational experiments

Two-edge connected subgraphs with bounded rings: Polyhedral results and Branch-and-Cut

Improved lower bounds and exact algorithm for the capacitated arc routing problem

New results on the Windy Postman Problem