Premium
A note on characterizing canonical cuts using geometry
Author(s) -
Macambira Elder M.,
Maculan Nelson,
Souza Cid C.
Publication year - 2005
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2005.00527.x
Subject(s) - constraint (computer aided design) , travelling salesman problem , set (abstract data type) , mathematics , integer programming , integer (computer science) , mathematical optimization , computer science , combinatorics , geometry , programming language
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.