Solving the knapsack problem via Z-transform

Jean B. Lasserre (lasserrelaas.fr)
Eduardo S. Zeron (eszeronmath.cinvestav.mx)

Abstract: Given vectors $a,c\in Z^n$ and $b\in Z$, we consider the (unbounded) knapsack optimization problem $P:\,\min\{c'x\,\vert\, a'x=b;\,x\in N^n\}$. We compute the minimum value $p^*$ using techniques from complex analysis, namely Cauchy residue technique to integrate a function in $C^2$, the $Z$-transform of an appropriate function related to $P$. The computational complexity depends on $s:=\sum_{a_j} a_j$, not on the magnitude of $b$ as in dynamic programming based approaches. We also completely characterize the number of solutions with value less than $p$, as a function of $p$.

Keywords: knapsack problem; Z-transform; counting problems

Category 1: Integer Programming

Category 2: Combinatorial Optimization (Polyhedra )

Citation: Operations Research Letters 30 (2002), 394-400 http://www.elsevier.com/homepage/sae/orms/orl/menu.htm

Download:

Entry Submitted: 07/13/2002
Entry Accepted: 07/13/2002
Entry Last Modified: 03/02/2003

Modify/Update this entry