- 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/2004Entry Accepted: 03/31/2004Entry Last Modified: 09/23/2005Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.