  


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 wellknown 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. 139150 (Proceedings of the AMSIMSSIAM Joint Summer Research Conference, Snowbird, July 2003) Download: Entry Submitted: 03/31/2004 Modify/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  