%version revisee envoyee a ORL le 2 Mai 2002.
\documentclass{amsart}

\usepackage{amsmath,amsthm}
\numberwithin{equation}{section}

%       Theorem environments

\newtheorem{theorem}{Theorem}[section]
\newtheorem{coro}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{axiom}{Axiom}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark} 
\newtheorem*{notation}{Notation}

\def\theequation{\thesection.\arabic{equation}}

\def\R{\mathbb{R}}
\def\P{\mathbb{P}}
\def\C{\mathbb{C}}
\def\Q{\mathbb{Q}}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\e{{\rm e}}

\newtheorem{example}[theorem]{Example}
\def\to{{\rightarrow}}

\begin{document}

\title{Solving the knapsack problem via Z-transform}
\author{Jean B. Lasserre}
\address{LAAS-CNRS, 7 avenue du Colonel Roche, 31 077 Toulouse c\'edex 4, 
France}
\email{lasserre@laas.fr}
\author{Eduardo S. Zeron}
\address{Depto. Matem\'aticas, CINVESTAV-IPN, Apdo. Postal 14-740,
Mexico D.F. 07000, M\'exico}
\email{eszeron@math.cinvestav.mx}

\date{}
\maketitle

\begin{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 's Residue Theorem to integrate a function in $\C^2$, and the 
$\Z$-transform of an appropriate function related to $\P$. 
The computational complexity depends on $s:=\sum_{j=1}^n 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$.
\end{abstract}


\section{Introduction}
Given integer vectors $a,c\in\Z^n$ and an integer $b\in\Z$,
we consider the {\it unbounded knapsack} optimization problem
\begin{equation}
\label{k1} \P: \quad p^*\,:=\,\min\{c'x \,\vert\,a'x=b;\, x\in\N^n\},
\end{equation}
which is known to be NP-hard.

In this paper we propose an exact method to compute $p^*$ which differs 
from previous known approaches.
The primary goal here is not to compete with the efficient 
heuristics already available for hard knapsack problems
as developed in e.g. Babaev et al. \cite{baba} or
Chung \cite{chung} and the many references therein, not to mention
the powerful LLL-type lattice reduction 
techniques of Lenstra, Lenstra, and Lov\'asz
for 0-1 knapsack problems in cryptography
(see e.g. Schnorr and H\"orner \cite{schnorr}). 
The proposed method brings some new insight into the problem
and shows how simple techniques from complex analysis 
(widely used in number theory but not in optimization) can help 
understand and solve some discrete optimization  problems
(a similar technique was used in Lasserre and Zeron \cite{laszeron1}
to yield an algorithm for computing the volume of a convex polytope,
and in Lasserre and Zeron \cite{laszeron3} for solving a class of multivariate
integration problems).
We briefly recall that with a function $f:\N\to\R$ one may associate
its (one-sided) $\Z$-transform $F:\C\to\C$, defined by
\[z\,\mapsto\,F(z)\,:=\,\sum_{n=0}^\infty f(n)z^{-n},\]
assumed to be well-defined on a appropriate domain $\vert z\vert >r$ for some $r>0$.
Assuming that $f(n)=0$ for $n<0$,
one may retrieve the value $f(n)$ from the complex integral
\begin{equation}
\label{aoo}
f(n)\,=\,\frac{1}{2\pi i}\int_{\vert z\vert =\gamma}F(z)z^{n-1}\,dz,\quad\quad
n\in\N,
\end{equation}
where $\gamma >r$ is fixed, arbitrary (see e.g. Debnath \cite[Chap. 10]{debnath}).
For many cases of interest, Cauchy 's Residue Theorem is a powerful
technique to compute the integral (\ref{aoo}).
The above also extends to the multi-dimensional case.

We reduce the original problem to a {\it counting problem} in a 
related lattice polytope as in \cite{laszeron2}.
We then use counting techniques based on generating functions
as described in Brion and Vergnes \cite{brion,brion2}.
This technique uses the generating function of the function
$(b,p)\mapsto f(b,p)$ which counts the {\it integral} points in
the polytope $\{a'x =b; c'x \leq p;x\in\R^n\}$.
It can be interpreted as a {\it dual} technique of those described in 
Barvinok and Pommersheim
\cite{barvinok2} (see also Diaz and Robbins \cite{sinai})
as we work in the  space of {\it dual} variables associated with the 
(non trivial) constraints of the polytope instead of 
working with the generating function in the original space $\R^n$.
The idea can be summarized as follows. Consider the convex 
polytope
\begin{equation}
\label{poly}
\Omega(b,p)\,:=\,\{x\in\R^n_+\,|\,a'x\,=\,b;\quad c'x\,\leq\,p\},
\end{equation}
and the function $(b,p)\mapsto f(b,p)$ that counts the number of 
integral points $x\in\N^n$
in $\Omega(b,p)$.  
Therefore, since the function $p\mapsto f_b(p):=f(b,p)$ is nonnegative 
and nondecreasing, for any fixed $b\in\Z$, we only need to detect the 
first value $p=p^*$ for which $f_b(p)\neq 0$; which, as we show below,
can be done without knowledge of the function itself. To do this 

- (a) we first provide a very simple closed-form expression 
of the two-dimensional $\Z$-transform $F(z_1,z_2)$ of $f(b,p)$. 

- (b) we the show that the partial integration of $F$ w.r.t. the 
variable $z_1$ associated with the constraint $a'x=b$, yields the
$\Z$-transform $G_b$ of $f_b(p)$. 

- (c) the $\Z$-transform $G_b$ is a rational fraction $P(z_2)/Q(z_2)$ of 
the remaining variable $z_2$; and thus, with simple arguments, it follows
that $p^*$ is just the difference of the degrees of $P$ and $Q$.
We also analyze the practical computation of $P$ and $Q$.

From a computational point of view, the relevant quantities are
the number $N$ of positive entries $a_j$'s in the knapsack constraint 
and the sum $s:=\sum_{j=1}^na_j$. The magnitude of $b$ is irrelevant.
Hence, one can solve several problems with different $b$'s without
redoing most computations.

Finally, we also show that the function $f_b(p)$ has the following 
characterization. It can be written as the sum of a function $w(p)$ which
takes {\it finitely many} values and a polynomial $P(p)$ of degree $m$, with 
{\it periodic} coefficients. The period $\gamma$ is the least common multiple 
of the absolute value of some $2\times 2$ sub-determinants of the matrix 
$\left[a\vert b\right]$. Therefore, the number of solutions with value less 
than $p=t\gamma$ is of the order $t^m$.

\section{Main result}
\label{sec}

Let $\Z$ and $\N$ denote the sets of integers and natural numbers respectively 
(we consider $0$ to be a natural number), and let $x'$ denote the transpose of
any vector $x\in\R^n$.

Consider the function $f:\Z^2\to\N$ defined by
\begin{equation}
\label{f}
(b,p)\,\mapsto\,f(b,p)\,:=\,\vert\,\N^n\cap \{x\,|\,a'x=b;\, c'x\leq p\}\,\vert
\end{equation}
(where $\vert A\vert$ denotes the cardinality of $A$). That is, $f$ {\it counts} 
the integral points in the convex rational polytope (\ref{poly}).

Next, for fixed $b\in\Z$, let $f_b:\Z\to \N$ be the function
\begin{equation}
p\,\mapsto\,f_b(p)\,:=\,f(b,p).
\end{equation}
Since $f_b$ is obviously non-negative and non-decreasing, 
with $p^*$ as in (\ref{k1}), we have 
\begin{equation}
\label{kk1}
p^*\,=\,c'x^*\quad\Leftrightarrow\quad f_b(p^*)\geq1
\quad\hbox{and}\quad f_b(p)=0\quad\forall\,p\,<\,p^*.
\end{equation}

Moreover, let $F:\C\times \C\,\to\,\C$ be the two-sided 
$\Z$-transform of $f$, that is,
\begin{equation}
\label{eq3}
z\,\mapsto\,F(z_1,z_2)\,:=\,\sum_{j,k\in\Z}\,f(j,k)z_1^{-j}z_2^{-k},
\end{equation}
for $(z_1,z_2)\in\Gamma\subset \C^2$.
\begin{theorem}
\label{th1}
Let $(a,c)\in\Z^n\times \Z^n$ and assume that $p^*>-\infty$.

{\rm (a)} For every $z\in\C^2$ such that
\begin{equation}
\label{dom}
\vert z_2\vert>1\quad\mbox{and}\quad\vert 
z_1^{a_j}z_2^{c_j}\vert\,>\,1\quad\forall\,j=1,\ldots, n, 
\end{equation}
we have
\begin{equation}
\label{a1}
F(z_1,z_2)\,=\,\frac{z_2}{z_2-1}\prod_{j=1}^n
\left(1-z_1^{-a_j}z_2^{-c_j}\right)^{-1}.
\end{equation}

{\rm (b)} Fix $\alpha_1,\alpha_2\in\R$ such that $\alpha_2>1$ 
and $\alpha_1^{a_j}\alpha_2^{c_j}>1$ for $j=1,\ldots, n$. Then 
\begin{equation}
\label{a2}
f(b,p)\,=\,\frac{1}{(2\pi i)^2}\,\int_{\vert z_1\vert=\alpha_1}
\int_{\vert z_2\vert=\alpha_2}z_1^{b-1}z_2^{p-1}F(z_1,z_2)\,dz_1\,dz_2.
\end{equation}
\end{theorem}

\begin{proof} Let $(z_1,z_2)\in\C^2$ 
\begin{eqnarray*}
F(z_1,z_2)&=&\sum_{j,k\in\Z;}\,\sum_{a'x=j,\,c'x\leq k}z_1^{-j}z_2^{-k}
\,=\,\sum_{x\in\N^n} z_1^{-a'x}\sum_{k=c'x}^\infty z_2^{-k}\\
&=&\frac{z_2}{z_2-1}\,\sum_{x\in\N^n} 
z_1^{-a'x}z_2^{-c'x}\quad\mbox{if}\quad \vert z_2\vert >1\\
&=&\frac{z_2}{z_2-1}\prod_{j=1}^n
\left(1-z_1^{-a_j}z_2^{-c_j}\right)^{-1}\quad\mbox{[if (\ref{dom}) holds.]}
\end{eqnarray*}

Point (b) follows from Cauchy 's Residue Theorem (see e.g. Conway \cite{conway}). 
It remains to prove that the domain (\ref{dom}) is not empty. Since 
$p^*>-\infty$, the recession cone of the polytope $\Omega(b,p)$ in
(\ref{poly}), i.e.,
\[\{x\in\R^n\,|\,x\geq0,\quad a'x\,=\,0,\quad c'x\,\leq\,0\},\]
reduces to the singleton $\{0\}$; equivalently
$\Omega(b,p)$ is compact. Therefore, it 
immediately follows from an adapted version of Farkas Lemma due to Carver,
that the cone 
\[\Omega^*\,:=\,\{\lambda_1,\lambda_2\in\R\,|\,\lambda_2\,>\,0;\quad 
a_j\lambda_1+c_j\lambda_2 \,>\,0\quad\forall j=1,\ldots, n\}\]
is not empty (e.g. see Schrijver \cite[(33), p. 95]{schrijver}). We may 
then take $(\alpha_1,\alpha_2):=(\e^{\lambda_1},\e^{\lambda_2})$ for some 
arbitrary $(\lambda_1,\lambda_2)\in\Omega^*$.
\end{proof}

\subsection{Computing $f(b,p)$}
\label{rem0}

From equation (\ref{a2}), we can directly calculate the value of $f(b,p)$ 
at each point $(b,p)$ by computing a double integral.

However, we need {\it not} compute the double integral defined in (\ref{a2}) 
in order to determine the minimal value $p^*$ in (\ref{k1}). We can instead
use implicit properties of the $\Z$-transform and proceed as follows.

Fix $\alpha_1,\alpha_2\in\R$ such that $\alpha_2>1$ and 
$\alpha_1^{a_j}\alpha_2^{c_j}>1$ for $j=1,\ldots, n$; next,
calculate the following integral, where $b\in\Z$ is fixed;
\begin{equation}
\label{eq0}
G_b(z_2)\,:=\,\frac{1}{2\pi i}\,
\int_{\vert z_1\vert=\alpha_1}z_1^{b-1}F(z_1,z_2)\,dz_1.
\end{equation}

Obviously, $G_b(z_2)$ is well defined for 
$\alpha_2-\epsilon<\vert z_2\vert<\alpha_2+\epsilon$ and $\epsilon>0$ 
{\it small enough}. Moreover, we can express (\ref{eq0}) as an infinite 
sum by using definition (\ref{eq3}) for $F(z_1,z_2)$, which yields
\begin{eqnarray}
\label{eq1}
G_b(z_2)&=&\sum_{j,k\in\Z}f(j,k)z_2^{-k}\frac{1}{2\pi i}
\int_{\vert z_1\vert=\alpha_1}z_1^{b-j-1}dz_1\\
\nonumber
&=&\sum_{k\in\Z}f(b,k)z_2^{-k}\,=\,\sum_{k\in\Z}f_b(k)z_2^{-k}.
\end{eqnarray}
Notice that from (\ref{eq1}), $G_b(z_2)$ is the 
$\Z$-transform of $p\mapsto f_b(p)$ for 
every fixed $b\in\Z$. On the other hand, after calculating (\ref{eq0}), 
it immediately follows that $G_b(z_2)$ is a rational function, say 
\begin{equation}
\label{eq2}
G_b(z_2)\,:=\,\frac{P(z_2)}{Q(z_2)},
\end{equation}
for some real polynomials $P$ and $Q$. If $P\equiv 0$ then $f_b(p)=0$ for 
all $p\in\Z$, and so $p^*=+\infty$; that is, the equation $a'x=b$ has no 
integer solution $x\in\N^n$.

Now define the number:
\begin{equation}
p_o\,:=\,\hbox{degree}(Q)\,-\,\hbox{degree}(P),
\end{equation}
where $P$ and $Q$ are given on (\ref{eq2}). It is easy to see that
\begin{eqnarray*}
\lim_{\vert z_2\vert\rightarrow\infty}\,z_2^{p_o}\,G_b(z_2)
&\neq&0\quad\hbox{and}\\
\lim_{\vert z_2\vert\rightarrow\infty}\,z_2^p\,G_b(z_2)
&=&0\quad\hbox{whenever}\quad p<p_o.
\end{eqnarray*}

Hence, recalling the expression (\ref{eq1}) 
of $G_b(z_2)$, we can conclude that
$$f(b,p_o)\neq0\quad\hbox{and}\quad f(b,p)=0\quad\hbox{whenever}\quad p<p_o.$$

The preceding constitutes a proof of the following result.

\begin{theorem}
\label{th2}
Let $p^*>-\infty$ be the minimum value of $\P$ in (\ref{k1}) 
and let $P$ and $Q$ be as in (\ref{eq2}). Then 

\noindent
{\rm (a)} $p^*=+\infty$ if $P\equiv 0$ (the equation $a 'x=b$ has no integral
solution $x\in\N^n$).

\noindent
{\rm (b)} if $P\not\equiv 0$  one has
\begin{equation}
\label{min}
p^*\,:=\,\hbox{\rm degree}(Q)\,-\,\hbox{\rm degree}(P).
\end{equation}
\end{theorem}

\subsection{Practical computation}

We can calculate polynomials $P$ and $Q$ in (\ref{eq2}) by directly 
integrating (\ref{eq0}) using Cauchy 's  Residue Theorem (see e.g. Conway 
\cite{conway}); however, we next introduce some observations 
that make calculations easier.

First we need to locate the poles of $F(z_1,z_2)$ with respect to 
$z_1$. These poles are given by $\xi_{jk}=e^{2\pi ik/a_j}z_2^{-c_j/a_j}$, 
for $k=1,\ldots,\vert a_j\vert$ and $j=1,\ldots, n$. Besides, recall that we 
are setting $\vert z_1\vert=\alpha_1>0$ and $\vert z_2\vert=\alpha_2>1$ 
with $\alpha_1^{a_j}\alpha_2^{c_j}>1$. Hence, only the poles $\xi_{jk}$ 
with $k=1,\ldots,a_j$ and $a_j$ strictly positive are located {\it inside} 
the integration path $\vert z_1\vert=\alpha_1$, because 
$\vert\xi_{jk}\vert=\alpha_2^{-c_j/a_j}<\alpha_1$ only if $a_j>0$. 

Thus, we only need to consider the poles 
$\xi_{jk}=e^{2\pi ik/a_j}z_2^{-c_j/a_j}$ with $a_j>0$ in order to integrate 
(\ref{eq0}). We will suppose from now on that at least one entry of 
$a$ is strictly positive, and we order the components of $a$
such that $a_j>0$ if $j=1,\ldots, N$ and $a_j\leq0$ 
if $j=N+1,\ldots, n$.

Moreover, with no loss of generality, we may assume that $b\geq0$ (otherwise
consider the equality $-a 'x=-b$), and that 
$F(z_1,z_2)$ has only simple poles (with respect to $z_1$) located inside 
the integration path $\vert z_1\vert=\alpha_1$. This happens whenever none 
of the $2\times 2$ determinants 
\begin{equation}
\label{deter}
\Delta_{ij}\,:=\,\left|\begin{array}{cc}a_i&c_i\\a_j&c_j\end{array}\right|
\end{equation}
vanishes for $i,j=1,\ldots, N$.

Indeed, computation gets simplified for we then have the following 
decomposition into simple fractions; setting $s:=\sum_{j=1}^Na_j$ 
we have that $s>0$ and :
\begin{eqnarray*}
\frac{F(z_1,z_2)}{z_1}&=&\frac{z_1^{s-1}\,z_2}{z_2-1}\,\prod_{j=1}^n
\left(z_1^{a_j}-z_2^{-c_j}\right)^{-1}\\
&=&\sum_{j=1}^N\frac{A_{j}(z_1,z_2)}{z_1^{a_j}-z_2^{-c_j}}\,+\,
\frac{A_0(z_1,z_2)}{\prod_{j>N}(1-z_1^{\vert a_j\vert}z_2^{-c_j})},
\end{eqnarray*}
where, for all $j=0,1,\ldots, N$,

- $A_j(.,z_2)$ is a polynomial with respect to $z_1$, and 

- $A_j(z_1,.)$ is a rational function with respect to $z_2$. 

The coefficients of $A_j$ can be calculated either symbolically or
numerically by solving a linear system of $s$ variables. The latter because
one knows in advance that the the denominator of $A_j(z_1,.)$
is of the form $z_2^{\beta_k}(z_2-1)\prod_{i\neq j}(z^{\Delta_{ij}}-1)$ with
$\Delta_{ij}$ as in (\ref{deter}).
Moreover, 
the degree of $A_j(.,z_2)$ with respect to $z_1$ is less than $a_j$ for 
$j=1,\ldots, N$, and so,
$$A_j(z_1,z_2)\,=\,\sum_{k=0}^{a_j-1}\,A_{jk}(z_2)\,z_1^k
\quad\hbox{for all}\quad j=1,\ldots, N,$$
where each coefficient $A_{jk}(z_2)$ is a rational function of $z_2$ 
with real coefficients. On the other hand, the integral (\ref{eq0}) 
depends only on the poles located inside the integration path. Therefore,
\begin{equation}
\label{eq4}
G_b(z_2)\,=\,\sum_{j=1}^N\sum_{k=0}^{a_j-1}
\frac{A_{jk}(z_2)}{2\pi i}\int_{\vert z_1\vert=\alpha_1}
\frac{z_1^{k+b}}{z_1^{a_j}-z_2^{-c_j}}\,dz_1.
\end{equation}

Notice that the term $z_1^{b}$ does not introduce any new pole at zero 
because we are supposing $b$ to be greater than or equal to zero. Finally, 
each one of previous integrals can be easily calculated to get (recall 
that $\vert z_1^{a_j}z_2^{b_j}\vert=\alpha_1^{a_j}\alpha_2^{c_j}>1$),
\begin{eqnarray*}
\frac{1}{2\pi i}\int_{\vert z_1\vert=\alpha_1}\frac{z_1^{k+b}}
{z_1^{a_j}-z_2^{-c_j}}\,dz_1&=&\frac{1}{2\pi i}\int_{\vert z_1\vert=\alpha_1}
\frac{z_1^{k+b-a_j}}{1-z_1^{-a_j}z_2^{-c_j}}\,dz_1\\
&=&\sum_{x\geq0}\frac{z_2^{-c_jx}}{2\pi i}\int_{\vert z_1\vert=\alpha_1}
z_1^{k+b-(x+1)a_j}\,dz_1\\
&=&\left\{\begin{array}{cl}z_2^{-c_jx}&\hbox{if }
x=\frac{k+b+1}{a_j}-1\in\N,\\0&\hbox{otherwise.}\end{array}\right.
\end{eqnarray*}

Thus, (\ref{eq4}) can be rewritten, for $b\geq0$, as follows 
\begin{equation}
\label{finalexp}
G_b(z_2)\,=\,\sum_{j=1}^N\sum_{k=0}^{a_j-1}\left\{\begin{array}{cl}
A_{jk}(z_2)z_2^{-c_jx}&\hbox{if }x=\frac{k+b+1}{a_j}-1\in\N,\\
0&\hbox{otherwise.}\end{array}\right.
\end{equation}

\begin{example}
\label{ex1}
Consider Problem  (\ref{k1}) in $\R^3$ with 
vectors $a=(2,3,-5)$ and $c=(1,-1,2)$.
Thus, $F$ in Theorem \ref{th1}  is given by
$$\frac{F(z_1,z_2)}{z_1}\,=\,\frac{z_1^4\,z_2}
{(z_2-1)(z_1^2-z_2^{-1})(z_1^3-z_2)(1-z_1^5z_2^{-2})},$$
and $\vert z_1\vert=\alpha_1>0$, $\vert z_2\vert=\alpha_2>1$, with
$\alpha_1^2\alpha_2>1$, $\alpha_1^3\alpha_2^{-1}>1$ and
$\alpha_1^{-5}\alpha_2^2>1$. Hence, we can set $\alpha_1=2$ and 
$\alpha_2=6$. Moreover, since the determinant
$$\left|\begin{array}{rr}2&3\\1&-1\end{array}\right|\,\neq\,0,$$
we have the expansion
\begin{eqnarray*}
\frac{F(z_1,z_2)}{z_1}&=&\frac{z_2^4+z_2^6+z_2^7+(z_2^4+z_2^5+z_2^7)z_1
+(z_2^3+z_2^5+z_2^7)z_1^2}{(z_2-1)^2(z_2^5-1)(z_1^3-z_2)}\\
&&-\,\frac{z_2^5+z_2^{12}+(z_2^8+z_2^{10})z_1}
{(z_2-1)(z_2^5-1)(z_2^9-1)(z_1^2-z_2^{-1})}\\
&&+\,\frac{A_0(z_1,z_2)}{(z_2-1)^2(z_2^9-1)(1-z_1^5z_2^{-2})}.
\end{eqnarray*}
Thus, $N=2$, $a_1=2$, $a_2=3$, and:
\[A_{10}(z_2)\,=\,-\,\frac{z_2^5+z_2^{12}}{(z_2-1)(z_2^5-1)(z_2^9-1)},\]
\[A_{11}(z_2)\,=\,\frac{-z_2^8-z_2^{10}}{(z_2-1)(z_2^5-1)(z_2^9-1)};\quad
A_{20}(z_2)\,=\,\frac{z_2^4+z_2^6+z_2^7}{(z_2-1)^2(z_2^5-1)},\]
\[A_{21}(z_2)\,=\,\frac{z_2^4+z_2^5+z_2^7}{(z_2-1)^2(z_2^5-1)};\quad
A_{22}(z_2)\,=\,\frac{z_2^3+z_2^5+z_2^7}{(z_2-1)^2(z_2^5-1)}.\]
Finally, if for instance $b:=10$, we get
\begin{eqnarray}
\nonumber
G_{10}(z_2)&=&A_{11}(z_2)z_2^{-5}\,+\,A_{21}(z_2)z_2^3\\
\label{example1}
&=&\frac{-z_2^3+z_2^4-z_2^5+z_2^6+z_2^7+z^9+z_2^{11}+z_2^{12}+z_2^{14}}
{(z_2-1)^2(z_2^9-1)}.
\end{eqnarray}
Thus, the minimum value $p^*=-3$, which can be checked to be exact.
\end{example}
\begin{remark}
It is important to emphasize that 
in contrast to dynamic programming based approaches,
the computational complexity does
{\it not} depend on the magnitude of $b$. Indeed, $b$ is only involved
in (\ref{finalexp}) to get the final expression of $G_b(z_2)$.
The relevant parameters are

- the number $N$ of positive entries $a_j$

- the sum $s:=\sum_{j=1}^na_j$.
\end{remark}

\subsection{Further characterization}

We have already seen that $G_b(z_2)$ is the $\Z$-transform of $f_b(p)$,
cf. (\ref{eq1}), where $f_b(p)$ counts the integral points in
the convex polytope $\Omega(b,p)$ for $b$ {\it fixed}. Moreover, the 
function $G_b(z_2)=P(z_2)/Q(z_2)$ is rational, cf. (\ref{eq2}), and we 
can determine where its poles are located.

The poles $\{\xi_{jk}\}$ of $F(z_1,z_2)$ w.r.t. to $z_1$ are given by
$\xi_{jk}=e^{2\pi ik/a_j}z_2^{-c_j/a_j}$, for $k=1,\ldots,\vert a_j\vert$ 
and $j=1,\ldots, n$. Notice that we could be counting the same pole several 
times, so let $\Xi$ be the set of all different poles $\xi_{jk}$ whose 
absolute value is less than $\alpha_1$. We can calculate integral
(\ref{eq0}) by using Cauchy 's Residue Theorem, i.e.,
\begin{equation}
\label{eq9}
G_b(z_2)\,=\,\sum_{\xi_{jk}\in\Xi}\hbox{Res}(z_1^{b-1}F,\,\xi_{jk})
\,+\,\hbox{Res}(z_1^{b-1}F,\,0).
\end{equation}
Recalling that $\hbox{Res}(z_1^{b-1}F,\,0)=0$ whenever $b\geq 1$, 
(e.g. see Conway \cite{conway}); and if $m$ is the multiplicity of 
the pole $z_1=\xi_{jk}$, 
$$\hbox{Res}(z_1^{b-1}F,\xi_{jk})\,=\,\frac{1}{(m-1)!}\,\frac{d^{m-1}}
{dz_1^{m-1}}\left[(z_1-\xi_{jk})^mz_1^{b-1}F(z_1,z_2)\right]_{z_1=\xi_{jk}}.$$

Now it is easy to see that the denominator of each residue 
$\hbox{Res}(z_1^{b-1}F,\cdot)$ has factors only of the form $z_2^\beta$, 
$(z_2-1)$ or $(\xi_{jk}^{a_l}-z_2^{-c_l})$ with $j\neq l$, we only need
to recall the definition (\ref{a1}) of $F$. Thus, by adding terms in 
(\ref{eq9}) and recalling that $G_b=P/Q$, we can deduce that $Q(z_2)$ 
has a factorization into terms which are only of the form $z_2^\beta$, 
$(z_2-1)$ or $(z_2^{\vert c_ja_l-c_la_j\vert}-1)$.

For instance, back to Example \ref{ex1}, we may indeed check that
$G_{10}(z_2)$ in (\ref{example1}) factorizes into terms of the form
$(z_2^s-1)$, where $s$ is the absolute value of some $2\times 2$ 
determinant of the matrix
$$\left[\begin{array}{rr}2&1\\3&-1\\-5&2\end{array}\right].$$

Therefore, from the integration of $G_b(z_2)$, the function $p\mapsto
f_b(p)$ can be characterized as follows: It is the sum of 

- a function $p\mapsto w(p)$ which is equal to zero outside a finite 
interval $[s_1,s_2]\in\Z$. That is, $w(p)=0$ if $p<s_1$ or $p>s_2$.

- a {\it polynomial} $p\mapsto P^\ast(p)$ whose degree $m$ is the multiplicity 
of the pole $z_2=1$ in $G_b(z_2)$, minus $1$, and whose coefficients are 
{\it periodic}. 

If all the entries $\{a_j\}$ are positive then
the polynomial $P^*$ is a constant for the knapsack polytope
$\{x\in\R^n\,|\,a'x=b\}$ has a finite number of integral points ($b$ is fixed).

For instance, consider again Example \ref{ex1}. We can decompose 
$G_b$ into simple fractions :
\begin{eqnarray*}
G_b(z_2)&=&z_2^3\,+\,2z_2^2\,+\,4z_2\,+\,
\frac{181\,z_2}{27\,(z_2-1)}\,+\,\frac{10\,z_2}{3\,(z_2-1)^2}\,+\\
&&\frac{5\,z_2}{9\,(z_2-1)^3}\,-\,\frac{z_2^2+2z_2}{27\,(z_2^2+z_2+1)}
\,+\,\frac{z_2^6-z_2^2}{3\,(z_2^6+z_2^3+1)}
\end{eqnarray*}

Thus, $f_{10}(p)=w(p)+P^\ast(p)$, with
\begin{eqnarray*}
w(p)&=&\left\{\begin{array}{rl}1&\hbox{if }p=-3,\\2&\hbox{if }p=-2,\\
4&\hbox{if }p=-1,\\0&\hbox{otherwise,}\end{array}\right.\\
P^\ast(p)&=&\left\{\begin{array}{rl}\frac{5p(p-1)}{18}+\frac{10p}{3}
+e_0(p)&\hbox{if }p\geq0,\\0&\hbox{otherwise,}\end{array}\right.
\end{eqnarray*}
where $e_0(p)$ is the only periodic coefficient of $P^\ast$, 
with period $\gamma =9$. Notice that the leading term of polynomial 
$P^\ast$ has degree $2$ because the pole $z_2=1$ has multiplicity $3$.

Thus, when $p>s_2$ is a multiple $t\gamma$ of the period $\gamma$, 
the function $f_b(t\gamma)$ is the polynomial $t\mapsto P^\ast(t\gamma)$
that we call the {\it Ehrhart polynomial}  of the polytope
$\Omega_b(t\gamma)$. However, observe that $\Omega_b(t\gamma)$ is {\it
not} the dilated polytope $\{tx;\:x\in\Omega_b(\gamma)\}$ and
$\Omega_b(\gamma)$ is not an integer polytope in general
(as in the usual definition of the Ehrhart polynomial of a dilated polytope). 
But still,
$f_b(t\gamma)$ is a polynomial.  It also follows that the number of
admissible solutions with value less than $t\gamma$, $t\in\N$, 
is of the order $t^m$.

\section{Conclusion}
We have provided a new approach for solving the knapsack problem.
Using the $\Z$-transform of a related function of two variables, 
the problem is solved by computing the (partial) $\Z$-inverse transform 
w.r.t. one of the variables via Cauchy's Residue Theorem. From a 
computational point of view, the relevant quantity is the number $N$ 
of positive entries $a_j$ in the knapsack constraint and the sum 
$s:=\sum_{j=1}^na_j$. In contrast to dynamic programming 
based methods, the magnitude of $b$ is irrelevant. 
In addition, this approach permits to characterize 
the function that counts the number of integral points in the polytope 
$\{a 'x=b;\,c'x \leq p;\,x\geq 0\}$, as a function of the threshold value 
$p$.


\begin{thebibliography}{lasserre}

\bibitem{baba}
D. Babaev, F. Glover and J. Ryan. A new knapsack solution approach by
integer equivalent aggregation and consistency determination,
{\it INFORM J. Comp.} {\bf 9} (1997), 43--50.
\bibitem{barvinok2}
A.I. Barvinok, J.E. Pommersheim. An algorithmic theory of lattice
points in polyhedra,  in {\it New Perspectives in Algebraic
Combinatorics},  MSRI Publications {\bf 38} (1999), 91--147. 
\bibitem{brion}
M. Brion, M.Vergne. Lattice points in simple polytopes, {\it
J. Amer. Math. Soc.} {\bf 10} (1997), 371--392.
\bibitem{brion2}
M. Brion, M.Vergne. Residue formulae, 
vector partition functions and lattice points in 
rational polytopes. {\it J. Am. Math. Soc.} {\bf 10}, No.4, 
797--833. 
\bibitem{chung}
C-S. Chung, M.S. Hung and W.O. Rom. A hard knapsack problem,
{\it Naval Res. Log.} {\bf 35} (1988), 85--98.
\bibitem{conway}
J.B. Conway. {\it Functions of a complex variable I}, 2nd ed., Springer, New
York, (1978).
\bibitem{debnath}
L. Debnath. {\it Integral Transforms and Their Applications},
CRC Press, Boca Raton, 1995.
\bibitem{schnorr}
C-P. Schnorr, H. H\"orner.
Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction,
in: {\it Theory and Application of Cryptographic Techniques},
Lectures Notes in Computer Sciences {\bf 921}, Springer, 1995,  pp. 1--12.
\bibitem{sinai}
R. Diaz and Sinai Robins. The Ehrhart polynomial of a lattice $n$-simplex,
{\it ERA Amer. Math. Soc.} {\bf 2}, No 1, August 1996.
\bibitem{laszeron1}
J.B. Lasserre, E.S. Zeron. A Laplace transform algorithm for the volume of a convex
polytope. {\it J. of the ACM}, to appear.
\bibitem{laszeron2}
J.B. Lasserre, E.S. Zeron. On counting integral points in a convex
polytope. Technical report \# 01353 (2001), LAAS-CNRS, Toulouse, France.
\bibitem{laszeron3}
J.B. Lasserre, E.S. Zeron. Solving a class of multivariate integration
problems via Laplace techniques. {\it Appl. Math. (Warsaw)} {\bf 28}
(2001), 391--405.
\bibitem{schrijver}
A. Schrijver. {\it Theory of Linear and Integer Programming},
John Wiley \& Sons, Chichester, 1986.
\end{thebibliography}
\end{document}
