A note on characterizing canonical cuts using geometry

A note on characterizing canonical cuts using geometry

0.00 Avg rating0 Votes
Article ID: iaor20072069
Country: United Kingdom
Volume: 12
Issue: 6
Start Page Number: 581
End Page Number: 594
Publication Date: Nov 2005
Journal: International Transactions in Operational Research
Authors: , ,
Keywords: programming: travelling salesman
Abstract:

In this technical note we introduce a set of cuts for 0–1 integer programming with a strong geometrical flavor. These are the spherical and cylindrical inequalities. We show that the geometrical cuts are in one-to-one correspondence with the canonical cuts introduced by Balas and Jeroslow. Moreover, we show how the well-known subtour elimination constraints for the Traveling Salesman Problem can be obtained via geometrical cuts. By presenting the subtour elimination constraints in this way, we give another easy and intuitive way to explain the validity of such inequalities. We show that the arguments used to derive the subtour elimination constraint as geometrical cut can be repeated to derive strong valid inequalities that are known for other combinatorial optimization problems.

Reviews

Required fields are marked *. Your email address will not be published.