SOLVING THE KNAPSACK PROBLEM VIA Z-TRANSFORM

JEAN B. LASSERRE AND EDUARDO S. ZERON

Abstract. Given vectors a, c ∈ ℤ^{n} and b ∈ ℤ, we consider the (unbounded) knapsack optimization problem ℙ : min{c′x | a′x = b; x ∈ ℕ^{n}}. We compute the minimum value p^{∗} using techniques from complex analysis, namely Cauchy ’s Residue Theorem to integrate a function in ℂ^{2}, and the ℤ-transform of an appropriate function related to ℙ. The computational complexity depends on s := ∑_{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.

1. Introduction

Given integer vectors a, c ∈ ℤ^{n} and an integer b ∈ ℤ, we consider the unbounded knapsack optimization problem

(1.1)  ℙ : p^{∗} := min{c′x | a′x = b; x ∈ ℕ^{n}},

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. [1] or Chung [5] and the many references therein, not to mention the powerful LLL-type lattice reduction techniques of Lenstra, Lenstra, and Lovász for 0-1 knapsack problems in cryptography (see e.g. Schnorr and Hörner [8]). 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 [10] to yield an algorithm for computing the volume of a convex polytope, and in Lasserre and Zeron [12] for solving a class of multivariate integration problems). We briefly recall that with a function f : ℕ→ℝ one may associate its (one-sided) ℤ-transform F : ℂ→ℂ, defined by

z ↦ F (z) := ∑_{n=0}^{∞} f(n)z^{−n},

assumed to be well-defined on a appropriate domain |z| > r for some r > 0. Assuming that f(n) = 0 for n < 0, one may retrieve the value f(n) from the complex integral

(1.2)  f(n) = \frac{1}{2πi} ∫_{|z|=γ} F (z)z^{n−1} dz,  n ∈ ℕ,

where γ > r is fixed, arbitrary (see e.g. Debnath [7, Chap. 10]). For many cases of interest, Cauchy ’s Residue Theorem is a powerful technique to compute the integral (1.2). The above also extends to the multi-dimensional case.

We reduce the original problem to a counting problem in a related lattice polytope as in [11]. We then use counting techniques based on generating functions as described in Brion and Vergnes [3, 4]. This technique uses the generating function of the function (b, p) ↦ f(b, p) which counts the integral points in the polytope {a′x = b; c′x ≤ p; x ∈ ℝ^{n}}. It can be interpreted as a dual technique of those described in Barvinok and Pommersheim [2] (see also Diaz and Robbins [9]) as we work in the space of dual variables associated with the (non trivial) constraints of the polytope instead of working with the generating function in the original space ℝ^{n}. The idea can be summarized as follows. Consider the convex polytope

(1.3)  Ω(b, p) := {x ∈ ℝ_{+}^{n} | a′x = b; c′x ≤ p},

and the function (b, p) ↦ f(b, p) that counts the number of integral points x ∈ ℕ^{n} in Ω(b, p). Therefore, since the function p ↦ f_{b}(p) := f(b, p) is nonnegative and nondecreasing, for any fixed b ∈ ℤ, we only need to detect the first value p = p^{∗} for which f_{b}(p) ≠ 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 ℤ-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 ℤ-transform G_{b} of f_{b}(p).

- (c) the ℤ-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 := ∑_{j=1}^{n} a_{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 finitely many values and a polynomial P (p) of degree m, with periodic coefficients. The period γ is the least common multiple of the absolute value of some 2 × 2 sub-determinants of the matrix [a|b]. Therefore, the number of solutions with value less than p = tγ is of the order t^{m}.

2. Main result

Let ℤ and ℕ 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 ∈ ℝ^{n}.

Consider the function f : ℤ^{2}→ℕ defined by

(2.1)  (b, p) ↦ f(b, p) := | ℕ^{n} ∩ {x | a′x = b; c′x ≤ p} |

(where |A| denotes the cardinality of A). That is, f counts the integral points in the convex rational polytope (1.3).

Next, for fixed b ∈ ℤ, let f_{b} : ℤ→ℕ be the function

(2.2)  p ↦ f_{b}(p) := f(b, p).

Since f_{b} is obviously non-negative and non-decreasing, with p^{∗} as in (1.1), we have

(2.3)  p^{∗} = c′x^{∗} ⇔ f_{b}(p^{∗}) ≥ 1 and f_{b}(p) = 0 ∀ p < p^{∗}.

Moreover, let F : ℂ × ℂ → ℂ be the two-sided ℤ-transform of f, that is,

(2.4)  z ↦ F (z_{1}, z_{2}) := ∑_{j,k∈ℤ} f(j, k)z_{1}^{−j}z_{2}^{−k},

for (z_{1}, z_{2}) ∈ Γ ⊂ ℂ^{2}. Theorem 2.1. Let (a, c) ∈ ℤ^{n} × ℤ^{n} and assume that p^{∗} > −∞.

(a) For every z ∈ ℂ^{2} such that

(2.5)  |z_{2}| > 1 and |z_{1}^{a_{j}}z_{2}^{c_{j}}| > 1 ∀ j = 1, …, n,

we have

(2.6)  F (z_{1}, z_{2}) = \frac{z_{2}}{z_{2} − 1} ∏_{j=1}^{n} (1 − z_{1}^{−a_{j}}z_{2}^{−c_{j}})^{−1} .

(b) Fix α_{1}, α_{2} ∈ ℝ such that α_{2} > 1 and α_{1}^{a_{j}}α_{2}^{c_{j}} > 1 for j = 1, …, n. Then

(2.7)  f(b, p) = \frac{1}{(2πi)^{2}} ∫_{|z_{1}|=α_{1}} ∫_{|z_{2}|=α_{2}} z_{1}^{b−1}z_{2}^{p−1}F (z_{1}, z_{2}) dz_{1} dz_{2}.

Proof. Let (z_{1}, z_{2}) ∈ ℂ^{2}

F (z_{1}, z_{2}) = ∑_{j,k∈ℤ;} ∑_{a′x=j, c′x≤k} z_{1}^{−j}z_{2}^{−k} = ∑_{x∈ℕ^{n}} z_{1}^{−a′x} ∑_{k=c′x}^{∞} z_{2}^{−k}
= \frac{z_{2}}{z_{2} − 1} ∑_{x∈ℕ^{n}} z_{1}^{−a′x}z_{2}^{−c′x} if |z_{2}| > 1

= \frac{z_{2}}{z_{2} − 1} ∏_{j=1}^{n} (1 − z_{1}^{−a_{j}}z_{2}^{−c_{j}})^{−1} [if (2.5) holds.]

Point (b) follows from Cauchy ’s Residue Theorem (see e.g. Conway [6]). It remains to prove that the domain (2.5) is not empty. Since p^{∗} > −∞, the recession cone of the polytope Ω(b, p) in (1.3), i.e.,

{x ∈ ℝ^{n} | x ≥ 0, a′x = 0, c′x ≤ 0},

reduces to the singleton {0}; equivalently Ω(b, p) is compact. Therefore, it immediately follows from an adapted version of Farkas Lemma due to Carver, that the cone

Ω^{∗} := {λ_{1}, λ_{2} ∈ ℝ | λ_{2} > 0; a_{j}λ_{1} + c_{j}λ_{2} > 0 ∀j = 1, …, n}

is not empty (e.g. see Schrijver [13, (33), p. 95]). We may then take (α_{1}, α_{2}) := (e^{λ_{1}}, e^{λ_{2}}) for some arbitrary (λ_{1}, λ_{2}) ∈ Ω^{∗}. □

2.1. Computing f(b, p). From equation (2.7), we can directly calculate the value of f(b, p) at each point (b, p) by computing a double integral.

However, we need not compute the double integral defined in (2.7) in order to determine the minimal value p^{∗} in (1.1). We can instead use implicit properties of the ℤ-transform and proceed as follows.

Fix α_{1}, α_{2} ∈ ℝ such that α_{2} > 1 and α_{1}^{a_{j}}α_{2}^{c_{j}} > 1 for j = 1, …, n; next, calculate the following integral, where b ∈ ℤ is fixed;

(2.8)  G_{b}(z_{2}) := \frac{1}{2πi} ∫_{|z_{1}|=α_{1}} z_{1}^{b−1}F (z_{1}, z_{2}) dz_{1}.

Obviously, G_{b}(z_{2}) is well defined for α_{2} − ϵ < |z_{2}| < α_{2} + ϵ and ϵ > 0 small enough. Moreover, we can express (2.8) as an infinite sum by using definition (2.4) for F (z_{1}, z_{2}), which yields

(2.9)  G_{b}(z_{2}) = ∑_{j,k∈ℤ} f(j, k)z_{2}^{−k} \frac{1}{2πi} ∫_{|z_{1}|=α_{1}} z_{1}^{b−j−1}dz_{1}
= ∑_{k∈ℤ} f(b, k)z_{2}^{−k} = ∑_{k∈ℤ} f_{b}(k)z_{2}^{−k}.

Notice that from (2.9), G_{b}(z_{2}) is the ℤ-transform of p ↦ f_{b}(p) for every fixed b ∈ ℤ. On the other hand, after calculating (2.8), it immediately follows that G_{b}(z_{2}) is a rational function, say

(2.10)  G_{b}(z_{2}) := \frac{P (z_{2})}{Q(z_{2})},

for some real polynomials P and Q. If P ≡ 0 then f_{b}(p) = 0 for all p ∈ ℤ, and so p^{∗} = +∞; that is, the equation a′x = b has no integer solution x ∈ ℕ^{n}.

Now define the number:

(2.11)  p_{o} := degree(Q) − degree(P),

where P and Q are given on (2.10). It is easy to see that

lim_{|z_{2}|→∞} z_{2}^{p_{o}} G_{b}(z_{2}) ≠ 0 and
lim_{|z_{2}|→∞} z_{2}^{p} G_{b}(z_{2}) = 0 whenever p < p_{o}.

Hence, recalling the expression (2.9) of G_{b}(z_{2}), we can conclude that

f(b, p_{o}) ≠ 0 and f(b, p) = 0 whenever p < p_{o}.

The preceding constitutes a proof of the following result. Theorem 2.2. Let p^{∗} > −∞ be the minimum value of ℙ in (1.1) and let P and Q be as in (2.10). Then

(a) p^{∗} = +∞ if P ≡ 0 (the equation a′x = b has no integral solution x ∈ ℕ^{n}).

(b) if P ≢ 0 one has

(2.12)  p^{∗} := degree(Q) − degree(P).

2.2. Practical computation. We can calculate polynomials P and Q in (2.10) by directly integrating (2.8) using Cauchy ’s Residue Theorem (see e.g. Conway [6]); 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 ξ_{jk} = e^{2πik/a_{j}}z_{2}^{−c_{j}/a_{j}}, for k = 1, …, |a_{j}| and j = 1, …, n. Besides, recall that we are setting |z_{1}| = α_{1} > 0 and |z_{2}| = α_{2} > 1 with α_{1}^{a_{j}}α_{2}^{c_{j}} > 1. Hence, only the poles ξ_{jk} with k = 1, …, a_{j} and a_{j} strictly positive are located inside the integration path |z_{1}| = α_{1}, because |ξ_{jk}| = α_{2}^{−c_{j}/a_{j}} < α_{1} only if a_{j} > 0.

Thus, we only need to consider the poles ξ_{jk} = e^{2πik/a_{j}}z_{2}^{−c_{j}/a_{j}} with a_{j} > 0 in order to integrate (2.8). 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, …, N and a_{j} ≤ 0 if j = N + 1, …, n.

Moreover, with no loss of generality, we may assume that b ≥ 0 (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 |z_{1}| = α_{1}. This happens whenever none of the 2 × 2 determinants

(2.13)  Δ_{ij} := | \begin{matrix}a_{i} & c_{i} \\ a_{j} & c_{j} \end{matrix} |

vanishes for i, j = 1, …, N.

Indeed, computation gets simplified for we then have the following decomposition into simple fractions; setting s := ∑_{j=1}^{N} a_{j} we have that s > 0 and :

\frac{F (z_{1}, z_{2})}{z_{1}} = \frac{z_{1}^{s−1} z_{2}}{z_{2} − 1} ∏_{j=1}^{n} (z_{1}^{a_{j}} − z_{2}^{−c_{j}})^{−1}

= ∑_{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})}{∏_{j>N}(1 − z_{1}^{|a_{j}|}z_{2}^{−c_{j}})},

where, for all j = 0, 1, …, 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}^{β_{k}}(z_{2} − 1) ∏_{i≠j}(z^{Δ_{ij}} − 1) with Δ_{ij} as in (2.13). Moreover, the degree of A_{j}(., z_{2}) with respect to z_{1} is less than a_{j} for j = 1, …, N, and so,

A_{j}(z_{1}, z_{2}) = ∑_{k=0}^{a_{j}−1} A_{jk}(z_{2}) z_{1}^{k} for all j = 1, …, N,

where each coefficient A_{jk}(z_{2}) is a rational function of z_{2} with real coefficients. On the other hand, the integral (2.8) depends only on the poles located inside the integration path. Therefore,

(2.14)  G_{b}(z_{2}) = ∑_{j=1}^{N} ∑_{k=0}^{a_{j}−1} \frac{A_{jk}(z_{2})}{2πi} ∫_{|z_{1}|=α_{1}} \frac{z_{1}^{k+b}}{z_{1}^{a_{j}} − z_{2}^{−c_{j}}} dz_{1}.

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 |z_{1}^{a_{j}}z_{2}^{b_{j}}| = α_{1}^{a_{j}}α_{2}^{c_{j}} > 1),

\frac{1}{2πi} ∫_{|z_{1}|=α_{1}} \frac{z_{1}^{k+b}}{z_{1}^{a_{j}} − z_{2}^{−c_{j}}} dz_{1} = \frac{1}{2πi} ∫_{|z_{1}|=α_{1}} \frac{z_{1}^{k+b−a_{j}}}{1 − z_{1}^{−a_{j}}z_{2}^{−c_{j}}} dz_{1}

= ∑_{x≥0} \frac{z_{2}^{−c_{j}x}}{2πi} ∫_{|z_{1}|=α_{1}} z_{1}^{k+b−(x+1)a_{j}} dz_{1}

= \{ \begin{matrix}z_{2}^{−c_{j}x} & if x = \frac{k+b+1}{a_{j}} − 1 ∈ ℕ, \\ 0 & otherwise. \end{matrix}

Thus, (2.14) can be rewritten, for b ≥ 0, as follows

(2.15)  G_{b}(z_{2}) = ∑_{j=1}^{N} ∑_{k=0}^{a_{j}−1} \{ \begin{matrix}A_{jk}(z_{2})z_{2}^{−c_{j}x} & if x = \frac{k+b+1}{a_{j}} − 1 ∈ ℕ, \\ 0 & otherwise. \end{matrix}

Example 2.3. Consider Problem (1.1) in ℝ^{3} with vectors a = (2, 3, −5) and c = (1, −1, 2). Thus, F in Theorem 2.1 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}^{5}z_{2}^{−2})},

and |z_{1}| = α_{1} > 0, |z_{2}| = α_{2} > 1, with α_{1}^{2}α_{2} > 1, α_{1}^{3}α_{2}^{−1} > 1 and α_{1}^{−5}α_{2}^{2} > 1. Hence, we can set α_{1} = 2 and α_{2} = 6. Moreover, since the determinant

| \begin{matrix}2 & 3 \\ 1 & −1 \end{matrix} | ≠ 0,

we have the expansion

\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}^{5}z_{2}^{−2})}.

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)}; 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)}; 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

G_{10}(z_{2}) = A_{11}(z_{2})z_{2}^{−5} + A_{21}(z_{2})z_{2}^{3}
(2.16)  = \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)} .

Thus, the minimum value p^{∗} = −3, which can be checked to be exact. Remark 2.4. It is important to emphasize that in contrast to dynamic programming based approaches, the computational complexity does not depend on the magnitude of b. Indeed, b is only involved in (2.15) 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 := ∑_{j=1}^{n} a_{j}.

2.3. Further characterization. We have already seen that G_{b}(z_{2}) is the ℤ-transform of f_{b}(p), cf. (2.9), where f_{b}(p) counts the integral points in the convex polytope Ω(b, p) for b fixed. Moreover, the function G_{b}(z_{2}) = P (z_{2})/Q(z_{2}) is rational, cf. (2.10), and we can determine where its poles are located.

The poles {ξ_{jk}} of F (z_{1}, z_{2}) w.r.t. to z_{1} are given by ξ_{jk} = e^{2πik/a_{j}}z_{2}^{−c_{j}/a_{j}}, for k = 1, …, |a_{j}| and j = 1, …, n. Notice that we could be counting the same pole several times, so let Ξ be the set of all different poles ξ_{jk} whose absolute value is less than α_{1}. We can calculate integral (2.8) by using Cauchy ’s Residue Theorem, i.e.,

(2.17)  G_{b}(z_{2}) = ∑_{ξ_{jk}∈Ξ} Res(z_{1}^{b−1}F, ξ_{jk}) + Res(z_{1}^{b−1}F, 0).

Recalling that Res(z_{1}^{b−1}F, 0) = 0 whenever b ≥ 1, (e.g. see Conway [6]); and if m is the multiplicity of the pole z_{1} = ξ_{jk},

Res(z_{1}^{b−1}F, ξ_{jk}) = \frac{1}{(m − 1)!} \frac{d^{m−1}}{dz_{1}^{m−1}} [(z_{1} − ξ_{jk})^{m}z_{1}^{b−1}F (z_{1}, z_{2})]_{z_{1}=ξ_{jk}} .

Now it is easy to see that the denominator of each residue Res(z_{1}^{b−1}F, ·) has factors only of the form z_{2}^{β}, (z_{2} − 1) or (ξ_{jk}^{a_{l}} − z_{2}^{−c_{l}}) with j ≠ l, we only need to recall the definition (2.6) of F. Thus, by adding terms in (2.17) 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}^{β}, (z_{2} − 1) or (z_{2}^{|c_{j}a_{l}−c_{l}a_{j}|} − 1).

For instance, back to Example 2.3, we may indeed check that G_{10}(z_{2}) in (2.16) factorizes into terms of the form (z_{2}^{s} − 1), where s is the absolute value of some 2 × 2 determinant of the matrix

[ \begin{matrix}2 & 1 \\ 3 & −1 \\ −5 & 2 \end{matrix} ] .

Therefore, from the integration of G_{b}(z_{2}), the function p ↦ f_{b}(p) can be characterized as follows: It is the sum of

- a function p ↦ w(p) which is equal to zero outside a finite interval [s_{1}, s_{2}] ∈ ℤ. That is, w(p) = 0 if p < s_{1} or p > s_{2}.

- a polynomial p ↦ P^{∗}(p) whose degree m is the multiplicity of the pole z_{2} = 1 in G_{b}(z_{2}), minus 1, and whose coefficients are periodic.

If all the entries {a_{j}} are positive then the polynomial P^{∗} is a constant for the knapsack polytope {x ∈ ℝ^{n} | a′x = b} has a finite number of integral points (b is fixed).

For instance, consider again Example 2.3. We can decompose G_{b} into simple fractions :

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)}

Thus, f_{10}(p) = w(p) + P^{∗}(p), with

w(p) = \{ \begin{matrix}1 & if p = −3, \\ 2 & if p = −2, \\ 4 & if p = −1, \\ 0 & otherwise, \end{matrix}

P^{∗}(p) = \{ \begin{matrix}\frac{5p(p−1)}{18} + \frac{10p}{3} + e_{0}(p) & if p ≥ 0, \\ 0 & otherwise, \end{matrix}

where e_{0}(p) is the only periodic coefficient of P^{∗}, with period γ = 9. Notice that the leading term of polynomial P^{∗} has degree 2 because the pole z_{2} = 1 has multiplicity

Thus, when p > s_{2} is a multiple tγ of the period γ, the function f_{b}(tγ) is the polynomial t ↦ P^{∗}(tγ) that we call the Ehrhart polynomial of the polytope Ω_{b}(tγ). However, observe that Ω_{b}(tγ) is not the dilated polytope {tx; x ∈ Ω_{b}(γ)} and Ω_{b}(γ) 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γ) is a polynomial. It also follows that the number of admissible solutions with value less than tγ, t ∈ ℕ, is of the order t^{m}.

3. Conclusion

We have provided a new approach for solving the knapsack problem. Using the ℤtransform of a related function of two variables, the problem is solved by computing the (partial) ℤ-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 := ∑_{j=1}^{n} a_{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 ≤ p; x ≥ 0}, as a function of the threshold value p.

References

[1] D. Babaev, F. Glover and J. Ryan. A new knapsack solution approach by integer equivalent aggregation and consistency determination, INFORM J. Comp. 9 (1997), 43–50.

[2] A.I. Barvinok, J.E. Pommersheim. An algorithmic theory of lattice points in polyhedra, in New Perspectives in Algebraic Combinatorics, MSRI Publications 38 (1999), 91–147.

[3] M. Brion, M.Vergne. Lattice points in simple polytopes, J. Amer. Math. Soc. 10 (1997), 371–392.

[4] M. Brion, M.Vergne. Residue formulae, vector partition functions and lattice points in rational polytopes. J. Am. Math. Soc. 10, No.4, 797–833.

[5] C-S. Chung, M.S. Hung and W.O. Rom. A hard knapsack problem, Naval Res. Log. 35 (1988), 85–98.

[6] J.B. Conway. Functions of a complex variable I, 2nd ed., Springer, New York, (1978).

[7] L. Debnath. Integral Transforms and Their Applications, CRC Press, Boca Raton, 1995.

[8] C-P. Schnorr, H. Hörner. Attacking the Chor-Rivest Cryptosystem by Improved Lattice Reduction, in: Theory and Application of Cryptographic Techniques, Lectures Notes in Computer Sciences 921, Springer, 1995, pp. 1–12.

[9] R. Diaz and Sinai Robins. The Ehrhart polynomial of a lattice n-simplex, ERA Amer. Math. Soc. 2, No 1, August 1996.

[10] J.B. Lasserre, E.S. Zeron. A Laplace transform algorithm for the volume of a convex polytope. J. of the ACM, to appear.

[11] J.B. Lasserre, E.S. Zeron. On counting integral points in a convex polytope. Technical report # 01353 (2001), LAAS-CNRS, Toulouse, France.

[12] J.B. Lasserre, E.S. Zeron. Solving a class of multivariate integration problems via Laplace techniques. Appl. Math. (Warsaw) 28 (2001), 391–405.

[13] A. Schrijver. Theory of Linear and Integer Programming, John Wiley & Sons, Chichester, 1986.

LAAS-CNRS, 7 avenue du Colonel Roche, 31 077 Toulouse cédex 4, France

E-mail address: lasserre@laas.fr

Depto. Matemáticas, CINVESTAV-IPN, Apdo. Postal 14-740, Mexico D.F. 07000, México

E-mail address: eszeron@math.cinvestav.mx