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

• 成果类型: Article
• 署名作者: Corberan, Angel; Plana, Isaac; Sanchis, Jose M.
• 署名单位: University of Valencia; Universitat Politecnica de Valencia
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0643-y
• 发表日期: 2006
• 页码: 79-96
• 关键词: chinese postman problem; polyhedron; algorithm

摘要

In this paper we introduce a new class of facet-inducing inequalities for the Windy Rural Postman Problem and the Windy General Routing Problem. These inequalities are called Zigzag inequalities because they cut off fractional solutions containing a zigzag associated with variables with 0.5 value. Two different types of inequalities, the Odd Zigzag and the Even Zigzag inequalities, are presented. Finally, their application to other known Arc Routing Problems is discussed.