Frauke Liers

Title:
Local cuts for binary non-linear programs

Abstract:
joint work with Christoph Buchheim (University of Cologne) and Marcus
Oswald (University Heidelberg)

Local cuts have been successfully applied by Applegate, Bixby, Cook
and Chv\'atal for faster solution of large-scale traveling salesman
instances. These valid inequalities outside the template paradigm are
generated by optimizing over a polytope~$\Pbar$ obtained by projecting
the traveling salesman polytope~(TSP) to a small subset of variables.
Solving an appropriate linear program yields a violated face-inducing
inequality of~$\Pbar$ whenever one exists. In a second step, the face
is transformed into a facet of~$\Pbar$ by a sequence of tilting and
lifting phases.

In this talk, we present a variant of the cut generation procedure.
Using a different LP formulation of basically the same size, we always
obtain a facet of~$\Pbar$ and so avoid the time-consuming tilting
steps. We show experimental results for binary non-linear programs
showing the effectiveness of the method.