@techreport{TR-IC-02-06,
number = {IC-02-06},
author = {Nelson Maculan and Elder M. Macambira and Cid C. de Souza},
title = {Geometrical Cuts for 0--1 Integer Programming},
month = {July},
year = {2002},
institution = {Institute of Computing, University of Campinas},
note = {In English, 13 pages.
\par\selectlanguage{english}\textbf{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.
}
}