Optimization Online


Integer programming, duality and superadditive functions

Jean B. Lasserre (lasserre***at***laas.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)


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society