Integer programming, duality and superadditive functions

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\}$.


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