Multi-row Approaches to Cutting Plane Generation
| Speaker: | Jintai Ding |
|---|---|
| Affiliation: | University of Cincinnati |
| Room: | Mathematics and Computer Building (MC) 5168 |
Abstract:
We
cover
two
topics
in
the
generation
of
multi-row
cutting
planes.
In
the
first
one,
we
present
a
separation
method
for
two-row
cuts.
Two-row
cuts
are
intersection
cuts
from
two
rows
of
a
simplex
tableau
describing
the
LP
relaxation
of
the
problem.
The
specificity
of
the
approach
adopted
here
is
that
it
does
not
rely
on
an
"infinite
relaxation"
point
of
view
and
generate
intersection
cuts
from
fixed
lattice-free
sets.
Instead,
given
a
fractional
point,
it
aims
at
always
finding
a
most
violated
facet-defining
inequality
for
the
two-row
model.
This
is
known
to
be
achievable
by
optimizing
over
the
polar
set
of
the
integer
hull
of
the
model.
We
develop
an
improvement
on
this
approach,
by
means
of
a
polyhedron
that
is
equivalent
to
the
polar
for
our
purpose,
but
has
a
more
compact
representation.
We
perform
row-generation
in
order
to
avoid
the
costly
computations
of
integer
hulls
of
two-dimensional
cones,
and
provide
a
simple
oracle
for
finding
violated
constraints.
An
implementation
of
the
resulting
algorithm
performs
separation
of
two-row
cuts
in
a
few
milliseconds
on
average,
on
the
standard
MIPLIB
3
and
2003
test
sets.
While
this
two-row
separator
is
quick,
the
measurements
of
the
computational
usefulness
of
the
cuts
do
not
yield
satisfactory
results.
Since
all
the
cuts
generated
are
facet-defining,
this
might
suggest
that
the
underlying
two-row
models
are
too
weak.
This
observation
prompted
an
attempt
to
evaluate
the
strength
of
various
multi-row
relaxations,
on
small
instances,
using
a
generic
separator.
To
that
end,
a
separator
is
developed,
which
is
able
to
compute
facet-defining
inequalities
from
arbitrary
(yet
reasonably
small)
mixed-integer
sets.
A
row-generation
approach
is
again
adopted,
but
this
time
the
slave
part
consists
in
the
resolution
of
a
mixed-integer
problem
instead
of
a
closed-form
oracle.
Some
interesting
computational
tricks
are
necessary
in
order
to
speed
up
the
inherently
hard
computations.