Campuses:

Integerprogramming, duality and superadditive functions

Friday, July 29, 2005 - 10:45am - 11:30am
EE/CS 3-180
Jean Lasserre (Centre National de la Recherche Scientifique (CNRS))
We consider the general integer program P: max {c'x : Ax=b; x
nonnegative integer}
which has a well-known abstract dual optimization problem stated in
terms of superadditive
functions. Using a linear program equivalent to P, introduced recently,
we show that its dual
can be interpreted as a simplified and more tractable form of the
abstract dual, and identifies
a subclass of superadditive functions, sufficient to consider in the
abstract dual. This class
of superadditive functions is also used to characterize the integer
hull of the convex polytope
{x : Ax=b; x nonnegative}.