Integer programming, duality and superadditive functions

Jean B. Lasserre (lasserrelaas.fr)

Abstract: Given $A \in Z^{m\times n}$, $b \in Z^m, c \in R^n$, we consider the integer program $P_d: \max \{c'x\vert Ax=b;x\in Z^n_+\}$ which has a well-known abstract dual optimization problem stated in terms of superadditive functions. Using a linear program $Q$ equivalent to $P_d$ that we have introduced recently, we show that its dual $Q^*$ can be interpreted as a simplified and tractable form of the abstract superadditive 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 \in R^n\vert \:Ax=b;x\geq0\}$.

Keywords: Integer programming; duality; superadditive functions

Category 1: Integer Programming

Citation: Contemporary Mathematics 374 (2005), pp. 139--150 (Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference, Snowbird, July 2003)

Download:

Entry Submitted: 03/31/2004
Entry Accepted: 03/31/2004
Entry Last Modified: 09/23/2005

Modify/Update this entry