Topic for Winter 2016: Topics in Integer Programming
Instructor: Ricardo Fukasawa
Class time: 10:30am -11:50am Tuesday/Thursday, Mathematics and Computer Building (MC) 6486
Course
outline:
Integer
Programming
consists
in
nding
an
optimal
solution
to
a
system
of
linear
inequalities
such
that
some
(or
all)
of
the
variables
satisfy
a
given
integrality
requirement.
It
is
a
widely
applicable
area
of
research
and
is
intimately
linked
to
the
solution
of
many
different
optimization
problems.
The
purpose
of
this
course
is
to
complement
the
regular
integer
programming
course
(CO652)
and
study
integer
programming
methods
and
theory
not
covered
in
that
course.
We
will
survey
several
different
approaches
to
integer
programming.
Even
though
this
course
will
be
related
to
CO652,
I
will
not
require
the
CO652
material
as
background.
Whatever
results
that
are
usually
seen
in
CO652
that
I
require
I
will
either
state
completely
without
proof
or
informally
give
the
basic
idea
so
that
you
can
follow
the
material
along.
Topics
to
be
covered
will
include
a
signi
cant
subset
of
the
following:
1. Cutting planes
(a) Some basic polyhedral theory, and usual results seen in CO652.
(b) Introduction (review): Gomory cuts, MIR cuts, split cuts, disjunctive cuts, inter-section cuts
(c) Equivalence between Gomory/MIR/split cuts
(d) Rank and Closures: Polyhedrality and relationship
(e) Cutting planes from simple structures: mixing, mingling, two-step MIR.
(f) Gomory's Group and Corner Polyhedra (finite and infinite)
(g) Multi-row Gomory cuts
2. Reformulation
(a) Basis reduction and LLL
(b) Solving IP in fixed dimension
(c) Extended formulations
3. Primal methods
(a) Test sets and
(b) Primal cutting plane method
(c) Integral Basis Method
4. Duality
(a) Duality in binary optimization
(b) Superadditive duality
(c) Lagrangian relaxation / duality / decomposition
5. Other topics
(a) Decomposition: DW, Benders
(b) Symmetry
(c) Enumeration: Resolution search
(d) Heuristics: RINS, Local Branching, Feasibility Pump
(e) MINLP
(f) MIP approaches to stochastic programming