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: | Maculan Nelson, Souza Cid C. de, Macambira Elder M. |
Keywords: | programming: travelling salesman |
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.