The Sequential Knapsack Polytope.
In this paper we describe the convex hull of all solutions of the integer bounded knapsack problem in the special case when the weights of the items are divisible. The corresponding inequalities are defined via an inductive scheme that can also be used in a more general setting.
Introduction
In this paper we deal with the integer bounded knapsack problem
a
and the numbers
a i are divisible, i.e., a i
a
n. In this case we say that the
knapsack problem has the divisibility property. It is also called the sequential
knapsack problem (see [1]). Whenever we are given a knapsack problem having
the divisibility property, we will assume without loss of generality that a
Our main result is the construction of the system of inequalities that describes
the convex hull of all solutions in this special case.
Since years the knapsack polytope is of particular interest for researchers in
polyhedral combinatorics. This is due to several reasons: one is the increasing
number of applications like in circuit design, telecommunication, vehicle routing
and scheduling that involve the knapsack problem as a subproblem. In order to
apply polyhedral methods to such complex problems, a good understanding of the
knapsack polytope is important. Secondly, the knapsack problem is the "easiest"
case of a number dependent problem. A slight change of the weights of the items
might change the inequalities that describe the polyhedron drastically. There-
fore, it is important to understand "general principles" according to which valid
inequalities are constructed. Examples in this direction are, for instance, Gomory
cutting planes [2], covers [12], (1; k)-configurations [8], the concept of lifting [7],
the weight reduction principle [10] or inequalities based on the Hilbert basis of
a cone of exchange vectors [11]. The knapsack polytope is one of the very interesting
and challenging polyhedra for which beautiful results can be discovered.
We present an inductive scheme to construct valid inequalities for the knapsack
polytope and show, in case that the weights of the items have the divisibility
property, that we obtain the complete description of the associated polyhedron.
The special case of the knapsack problem with the divisibility property has been
studied in the literature by several authors.
Hartmann and Olmstead [4] give an O(n log n) algorithm for optimizing a linear
objective function whose bottleneck operation is sorting the ratios fl i
a i
The case of the sequential knapsack problem when s
considered by Marcotte [6]. He shows that an optimum solution can be found
in linear time and applies his algorithm to the cutting stock problem. Pochet
and Wolsey [9] give an explicit description of the knapsack polyhedron with the
divisibility property when there are no bounds on the variables. They also refer
to applications in local area networking.
In Section 2 we present a transformation of any given sequential knapsack problem
to a special one such that in terms of feasible solutions and optimization both
formulations are equivalent. In Section 3 we outline a decomposition result for
all the optimal solutions of such a transformed sequential knapsack problem.
Our main result is contained in Section 4. Here we present an inductive scheme
to generate valid inequalities for the sequential knapsack problem. Given an
objective function, we construct an inequality via this scheme whose induced
face contains the set of all optimal solutions. This sufficies to show that our
inductive class of inequalities describes the sequential knapsack polyhedron. How
inequalities defined via our inductive scheme can be interpreted combinatorially
is the issue of Section 5. The discussions end in Section 6 with some extensions.
Throughout the paper we use the following notation.
For
vg.
The constraint
is called the knapsack inequality. The number
a is termed the weight of item i and a 0 2 IN is called the knapsack capacity.
We set N := ng and we always assume that 0 ! a 1 - a n - a 0 .
An integer vector that satisfies the knapsack constraint and the lower and upper
bound constraints is called feasible.
We say, F c is a face of some polytope P induced by the valid inequality c T x - fl,
flg. Every x 2 F c is also called a root of c T x - fl. The
inequalities x are called trivial. For real numbers
ng we use
the notation - (I) := P
In this section we present a transformation of the given sequential knapsack problem
to a special sequential knapsack problem that satisfies certain requirements.
We show that in terms of polyhedra and in terms of optimization both formulations
are equivalent. We start by introducing the notion of blocks.
l be a subset of items. B is
called a block if, for every
holds.
Let B be a block. The above definition implies that for every number - 2
there exists a subset W ' B such that
. The number uB :=
a
is called the
multiplicity of block B. We replace block B by a single item B with weight a i 1 and
multiplicity (upper bound)
a
. The objective function coefficient
of B is the number
Bm be a partition of N into blocks and denote by fw , c w , uw the
weight, objective function coefficient, multiplicity of block Bw , respectively,
m. Now consider the knapsack problem where every block is replaced by
a single item:
z
From the construction of the blocks it is clear that (MSKP) is a sequential knapsack
problem (MSKP stands for modified sequential knapsack problem). We now
show that there is a many to one correspondence between the feasible solutions
of the original problem (SKP) and the feasible solutions of its modified version
(MSKP). For ease of notation we assume that f 1 - f 2 - fm , and in case
holds. By P SKP and PMSKP we denote the convex
hull of all feasible vectors of the problem (SKP) and (MSKP), respectively.
Let z 2 IR m be a feasible solution of (MSKP), i.e., 0 - z w - uw , z w integer for
all m. By Definition 2.1, for every w there exist integers
Bw such that P
In fact, for all subsets I w of
items in Bw with
IN, the vector x 2 IR n
defined via x otherwise, is
feasible for problem (SKP).
Conversely, with every vector x 2 IR n that is feasible for problem (SKP) we
associate a vector z 2 IR m by setting z w :=
j2Bw a j x j
It follows that an integer vector z with z w
feasible for (MSKP) if and only if there exist feasible vectors of (SKP) with the
same total weight as z.
Now suppose that
is a valid inequality for the polytope PMSKP .
By setting fi i := b w a i
fw if item i belongs to block Bw , the inequality
is valid for P SKP . This statement follows from the fact that if x is feasible
for (SKP) then defined via z
j2Bw a j x j
is feasible for (MSKP) and satisfies
This shows that valid
inequalities for PMSKP can be transformed into valid inequalities for P SKP .
In the following we focus on a special partition of the set N into blocks
For an item i of (SKP), its gain per unit is defined as fl i
a i
. Let
the different values of gains per unit for all items of (SKP) (clearly, v - n).
We partition each set V g := fi
a i
into blocks
ng such that B g
j is not a block anymore, for
denote the final blocks constructed this way. Each block B i ,
is called a maximal block and, by definition, all items belonging to
the block B i have the same gain per unit.
Example 2.2. Consider the instance of the sequential knapsack problem
with upper bounds s i on the variables x i as follows: s
1. The set of items is partitioned into the
f7g. After transformation we obtain the instance
of the sequential knapsack problem:
with upper bounds on the variables
For a given sequential knapsack problem, the aggregation of items into maximal
blocks is unique. If V l is the set of
all items in N with gain per unit equal to g, then the unique maximal block
containing
g and a i l+1
is defined as
item in this subset fi can belong to some maximal block containing
an item t, because a i j
- a i t+1
. By removing
1 from V g and iteratively using the same argument, the unique partition of V g
into maximal blocks B g
ng , with B g
can be constructed
easily. This argument applies to all numbers g 2 fg g.
From the above discussions follows that, if we define (MSKP) using the unique
partition into maximal blocks, a vector z is feasible for (MSKP) if and only if
the associated vectors x are feasible for (SKP). As each maximal block contains
items in N with the same gain per unit we obtain in addition: a vector x 2 IR n
is optimal with respect to (SKP) if and only if the associated vector z 2 IR m is
optimal with respect to (MSKP) and vice versa, a vector z 2 IR m is optimal with
respect to (MSKP) if and only if all of its associated vectors x 2 IR n are optimal
solutions to (SKP).
To simplify notation, we always assume, when transforming (SKP) to (MSKP)
using maximal blocks, that f 1 - f 2 - fm , and in case
. Moreover, the above arguments for the construction of the unique
partition into maximal blocks show that for the transformed problem (MSKP)
the following property always holds:
fw
This property will be used in the next section to derive a decomposition scheme
of all optimal solutions of (MSKP).
3 Decomposition of optimum solutions
In this section, we characterize the optimal solutions of a problem (MSKP) obtained
by the maximal block transformation of an initial (SKP) problem presented
in the previous section.
Let positive rational numbers c positive integers
fm be given such that
We also assume that for every
For every F 2 IN and we denote by P F (j) the convex hull
of all solutions of the following (MSKP) problem with knapsack capacity F and
restricted to the variables 1 to j.
The optimization problem OP F (j) is the program
Note that in this section we only consider optimization problems OP F (j) with
positive objective coefficients. Using this notation we have that
and (m). By O F (j) we denote the set of all optimal solutions to
OP F (j). Finally, for an item
oe
i.e., \Delta i is the set of all items before i whose gain per unit is strictly better than
the one of i. Let f
be the total weight of items in \Delta i .
For every F and j, we now construct a decomposition tree whose paths from the
root node to the leaves contain all the optimal solutions of OP F (j). The key for
this result is the next lemma showing that for every optimum solution z 2 O F (j)
the component z j can attain at most two different values.
Lemma 3.1. For the optimization problem OP F (j) with positive cost coefficients
the following statement is true:
z 2 O F (j) implies that z j - min
ae
and z j - min
ae
l
Proof. We prove this result by contradiction using standard exchange arguments.
Several cases are distinguished.
the lemma states that z (j). By contra-
diction, suppose that there exists z 2 O F (j) with z j ? 0. As
f l z l
the divisibility of the weights, there exist integers - l 2
all l 2 \Delta j such that P
. We now define a solution z 0 with
z 0
i and the solution z 0 has
strictly better objective value than z by definition of \Delta j . This contradicts
the optimality of z.
because u j is in-
tegral. In this case the lemma states that z (j). By
contradiction, suppose that there exists z 2 O F (j) with z
the new solution z 0 with z 0
z 0
belongs to P F (j) and has strictly better
objective value than z, because c j
for all
contradiction.
Hence, we can assume that By the divisibility of the
weights, there exist integers - l 2
with
The new solution z 0 with z 0
for l 2
belongs to P F (j).
0g. As
(where the last inequality holds by as-
sumption), there exists i 2 W with c i
. Then the solution z 0 has
strictly better objective value than z, again a contradiction.
In the remaining cases we have that and the lemma states
and z j -
l F \Gammaf
suppose, by contradiction, that there exists
z 2 O F (j) with z
similar argument as in case (ii) shows that there exists
a solution z
and with a strictly better
objective value than z, a contradiction.
suppose, by contradiction, that there exists
z 2 O F (j) with z
l F \Gammaf
As
f l z l +f j z j -
l F \Gammaf
similar argument as in case (i) shows that
there exists a solution z
z 0
l F \Gammaf
and with a strictly
better objective value than z, a contradiction.
Lemma 3.1 can be applied inductively to build a binary decomposition tree containing
all potential optimal solutions in O F (j). We illustrate this on an example.
Example 2.2 Continued. The modified sequential knapsack problem P 396 (5)
using the maximal block transformation was defined as
with upper bounds on the variables
We have c 1
0:56, and hence
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
(2) (2) (2) (2)
(1) (1) (1) (1) (1) (1) (1)

Figure

1: Decomposition of Optimal Solutions for Example 2.2

Figure

1 illustrates the decomposition tree that we obtain from applying Lemma
3.1 iteratively. The node labels identify the problems P F (j) to be solved and
the value of z j is fixed on the corresponding branches. For example, Lemma 3.1
applied to P 396 (5) yields z are left with problem
are left with problem P 36 (4). Potential optimal solutions
of problems P 396 (4) and P 36 (4) are further decomposed using Lemma 3.1.
The set S 396 (5) of potential optimal solutions to P 396 (5) is defined by all the paths
from the leaves to the root node in the decomposition tree, that is
and, by Lemma 3.1, O 396 (5) ' S 396 (5).
For a given problem P F (j) and its associated decomposition tree, we define in
the next section valid inequalities that are satisfied at equality by all solutions in
this decomposition tree, and thus by all optimal solutions in O F (j).
4 The convex hull of all solutions to the sequential
knapsack problem
Let (SKP) be a sequential knapsack problem and suppose that C is a class of valid
inequalities for P SKP . The technique that we use in order to show that C describes
P SKP is due to Lovasz [5]: for every objective function fl we prove that the set of
optimal solutions to (SKP) belongs to the face induced by some inequality in C.
This suffices to show that C describes P SKP , because when an objective function
is parallel to a facet defining inequality, then the only inequality satisfied at
equality by all optimal points in (SKP) is this facet defining inequality. Hence,
C contains all the facet defining inequalities.
We first consider the case that all objective function coefficients are positive.
As outlined in Section 2, we partition N into maximal blocks
construct the modified sequential knapsack problem (MSKP). Associated with
the transformed problem (MSKP), we use the notations P F (j), OP F (j), O F (j),
introduced in Section 3.
For every knapsack capacity F 2 IN and for every mg, we now
define an inequality I F (j) satisfying the conditions (i), (ii), (iii) listed below:
(i) The left hand sides of inequalities I F (j) and I F 0 (j) are equal if F modulo f j
holds.
(ii) I F (j) is a valid inequality for P F (j).
(iii) The set of optimal solutions O F (j) is contained in the face induced by the
inequality I F (j).
The inequalities I F (j) are defined inductively on j.
We define the inequality I F (1) as z 1 - minfF; u 1 g. This inequality clearly
satisfies all the properties (i) - (iii).
number r between 0 and f given and assume that for
every number F 2 IN with F modulo f there exists an inequality I F (j \Gamma 1)
that satisfies the properties (i) - (iii).
In particular, property (i) guarantees that this family of inequalities is of the
are the coefficients of the
inequalities I F (j \Gamma 1) for all F with F modulo f r. With the parameter r we
associate a number F r . We set F r := r if f
r is the largest number of residuum class r with respect
to f j not exceeding the sum of weights in that have a better gain
per unit than j.
For every F 2 IN with F modulo f r the left hand side of the inequality I F (j)
is of the form
defined as in I F (j \Gamma 1) and d j defined
by
In order to define the corresponding right hand side - that we denote by g F;j -
we need to distinguish several cases.
First,
is an integer.
We set
Under these assumptions the inequality I F (j) defined via
the three properties (i), (ii) and (iii). These statements are shown below. We
first illustrate this (inductive) construction on the initial example. Then three
technical lemmas are proved and afterwards applied to show that I F (j) satisfies
(i)-(iii).
Example 2.2 continued.
with upper bounds on the variables
The construction of the inequalities is defined for any value of F . If we are only
interested in the inequality I 396 (5), then we need not find I F (j) for all values of
F . The node labels in Figure 1 represent the subproblems we have to solve in
order to obtain an optimum solution for the original problem OP 396 (5). They
also give the F and r values we must consider in order to construct I 396 (5).
I
I F (2) with
I
I 6 (2)
I 1+5s (2)
I 1+5s (2)
I F (3) with
I
I
I
I F (4) with
I
I
I F (5) with
I
I
The inequality I 396 (5) is satisfied at equality by all solutions in S 396 (5) containing
all optimal solutions in O 396 (5).
Lemma 4.1. Let F and G be natural numbers such that F - G and F modulo
holds.
Proof. For the statement is certainly true. So assume, it holds for all
numbers that are less or equal than j \Gamma 1. We show that it is true for j as well.
We G, we know that s - t. We
define
G; if t ! 0;
Checking all cases we notice that F 0 - G 0 , F 0 modulo f
As F 0 modulo by assumption of the induction
and the claim follows.
Lemma 4.2. Let F and G be natural numbers such that F - G and F modulo
holds for every
Proof. g G+oef j Applying Lemma 4.1
yields [g G+oef
Iterating this argument proves Lemma 4.2.
Accordingly, we obtain Lemma 4.3.
Lemma 4.3. Let F and G be natural numbers such that F - G and F modulo
holds for every
Proof. 4.1, we conclude that [g F;j \Gamma
Iterating
this argument proves Lemma 4.3.
Using Lemmas 4.1 - 4.3 we are now able to prove the following theorem.
Theorem 4.4. Given a modified sequential knapsack problem with positive
objective function obtained from the maximal block transformation. If the inequalities
I F (j \Gamma 1) satisfy the three conditions (i), (ii), (iii) with
so do the inequalities I F (j) with
(i) The left hand sides of two inequalities I F (k) and I F 0 (k) are identical whenever
(ii) I F (k) is valid for P F (k);
(iii) Every optimum solution to problem OP F (k) is contained in the face induced
by the inequality I F (k);
Proof. We write I F (j) as
(i) Let F and F 0 be two natural numbers satisfying F modulo f
As \Delta j and F r are uniquely defined by the residuum class r and the
objective function we obtain - per definition - that the left hand sides of the two
inequalities I F (j) and I F 0 (j) are the same.
(ii) The inequality I F (j) is valid for the polyhedron P F (j). Let z 2 P F (j) be
a feasible point, then
G;j \Gamma1 is a valid inequality for all values of G with G modulo f j
Again, we write
cases.
(ii) (a) F - F r . Then s - 0. If z it follows from the definition of g
F;j \Gamma1 that the inequality is valid. Suppose that z j ? 0. Then
, where the
last inequality follows from Lemma 4.3, and the statement follows.
it follows from the definition of
that the inequality is valid. Suppose that z j ! u j . By
applying Lemma 4.2, we obtain:
(ii) (c) What remains is the case where F r
holds and we obtain
If z the inequality is valid by construction. Otherwise,
if z j ? s, then Lemma 4.3 implies that g Fr \Gamma(z j \Gammas)f
together with (?) we have that I F (j) is valid. Finally, if z
implies that g Fr \Gamma(z j \Gammas)f
which again shows that the inequality I F (j) is valid.
(iii) It remains to be shown that the set of optimal solution O F (j) is contained
in the face induced by the inequality I F (j).
By definition of F r , we can always write (j), then by
Lemma 3.1 and by definition of F r we have F \Gammaf
. If r - f
then F r is the unique number such that F r - f
r. In this case Lemma 3.1 implies that
or z
In this case, z
Hence, r ? f implies that z sg.
Summarizing all cases yields z or z
In case s - 0, i.e., F - F r , we have z in every optimum solution. Therefore
by assumption of the induction, every optimum solution to problem OP F (j) is
contained in the face
this case, the claim
follows.
In case s - every element in the set O F (j) satisfies
By assumption of the induction, every optimum solution z to problem
F;j . This proves the claim in this case.
Finally, we have 1 - s - u j . Then every optimum solution z of OP F (j) satisfies
either z By assumption of the induction we obtain that (a)
This yields in case (a):
In case (b) we obtain:
This shows that in both cases the
inequality I F (j) is satisfied at equality by all optimal points.
Let us now present the final theorem describing P SKP as a system of inequalities.
Let W ' N be a subset of items in N , let be a partition of W
into blocks and let - be a permutation of
l g be
the weight of block
a l s l
be the multiplicity of block B i and assume
that f 0
m . We set f
Denote by P b a 0
f 0c (m) the modified knapsack polytope defined with the block partition
B of W , weights f multiplicities um and knapsack capacity
b a 0
f 0c. That is
z
f 0c
If the inequality I b a 0
f 0c (m), written as
f 0c;m , denotes the valid inequality
developed in this section for P b a 0
f 0c (m) using the sets \Delta j induced by the
permutation -, then the inequality K(W;B;-) is defined as
a i
Theorem 4.5. Given an instance of (SKP), the following system of inequalities
describes the polyhedron
K(W;B;-); for all W ' N; all partitions
W into blocks, and all permutations - of
Proof. We first show validity of the inequalities K(W;B;-). Given W ,
and -. It is easy to check that there exists an objective function
is the partition of W into maximal blocks and there exists
- such that
g:
Then, the inequality I b a 0
f 0c (m) is valid for the polyhedron P b a 0
f 0c (m) by Theorem
4.4 (i) and (ii). By the arguments on the transformation of valid inequalities for
PMSKP to valid inequalities for P SKP (see Section 2), the inequality K(W;B;-)
is valid for the polyhedron
a i
This polyhedron is a relaxation of P SKP , because f 0
1 is the smallest weight among
all items in W . As K(W;B;-) is valid for this relaxation of P SKP , it is certainly
valid for P SKP .
Now given any objective function construct an inequality
satisfied at equality by all optimal solutions of (SKP). If
then and we set W := fi 2
Bmg be the partition of W into maximal blocks and let (MSKP)
denote the modified sequential knapsack problem of Section 2. From Theorem
4.4 (iii) we know that I b a 0
f 0c (m) is satisfied at equality by all optimal solutions
of (MSKP). By the arguments on the equivalence of optimal solutions beween
problems (SKP) and (MSKP) (see Section 2), K(W;B;-) is satisfied at equality
by all optimal solutions of
a i
Now if x is an optimal solution of the original problem with K(W;B;-) not
satisfied at equality (because some i 2 N n W has value x i ? 0), then a solution
with strictly better objective function value can be found by setting x
This completes the proof.
5 Explicit Inequalities
In the previous section we have inductively defined a class of inequalities that
depends on the choice and ordering of the blocks. Can we find a more explicit
or combinatorial formulation for those inequalities? This question is addressed
now.
Given a sequential knapsack problem of the form
where u is the vector of upper bounds on the variables and 1
A large class of inequalities for the associated polyhedron P SKP can be described
as follows:
Let r i denote the residuum of the capacity F modulo f i . We choose sets S i ' N i ,
with the following properties:
Setting
the inequality
is valid for P SKP . This statement can be verified by applying our inductive
scheme: we define a modified sequential knapsack problem and, for every item i
in this modified problem, we choose a set \Delta i such that the inequality constructed
via our inductive scheme coincides with (?).
We first consider the case where
2. Here we define the transformation to (MSKP) by
considering k. Thus, the
modified sequential knapsack is of the form
The ordering of blocks is defined by \Delta
F;k denote the
inequality I F (k) for this modified problem (MSKP) with sets
now show that (?) coincides with the inequality
F;k that is
obtained by transforming I F (k) to a valid inequality for (SKP) (see Section 2).
As
we have that, for any j - 2, r
thus
To derive I F (k) using our inductive scheme, we have to compute the numbers
g. As f
Starting from d going through the
inductive scheme (see Section 4) we obtain for each
finally
which shows that the inequality (?) is obtained via our inductive
scheme and thus is valid for P SKP when
When
then we consider
as a single block. Performing this for all j with
generating the corresponding modified knapsack problem, constructing the valid
inequality using our inductive scheme and transforming it to a valid inequality
for (SKP) yields the inequality (?).
The inequalities of the form (?) are already a strong generalization of other known
inequalities:
In case that if u is the vector of all ones (the 0=1 case), then the
inequality (?) is of the form
cl
. The latter class of inequalities plus the trivial inequalities
plus the cover inequality
c describe the polyhedron
g. This result was
shown in [11] and, independently in [3].
As a special case we obtain Padberg's result on (1; k)-configurations [8]: Suppose,
we are given a knapsack problem such that the set of feasible solutions is equal
to
The corresponding polyhedron is described by the lower and upper bound constraints
plus the inequalities
for all subsets
Summarizing our discussions, the inequalities (?) are only a subclass of the inequalities
needed to describe a sequential knapsack polyhedron. Nevertheless, this
subclass is quite large and extends all the explicitly known inequalities for special
cases of the knapsack problem having the divisibility property.
6 Extensions
The previous sections deal exclusively with the sequential knapsack polytope
which is still a restrictive assumption when considering integer programs in gene-
ral. Can we use parts of this polyhedral knowledge presented so far and apply it
within a more general framework? The answer is "yes" and we outline now some
directions.
A first question in using our inductively defined inequalities computationally is
whether we have a combinatorial algorithm for solving the separation problem,
i.e., given a fractional solution y: does there exists an inequality that is violated
by y and if so, then what is the inequality? We did not succeed in solving this
separation problem. "Only" for the subclass of inequalities
cl where ;
Hartmann [3] gives a linear time algorithm for solving the separation problem .
The general problem is still open. However, we can use our inductive scheme as
a separation heuristic. For instance, defining every item i 2 N as a single block,
setting generating an inequality
according to this ordering seems to be a promissing approach to end up with a
violated inequality, if one exists. Other reasonable definitions of \Delta i might be to
set
Whether those ideas work is
certainly not clear, but similar "greedy type" of procedures work pretty well for
the separation of cover- and (1; k)-configuration inequalities.
Given an integer programming problem Ax - b; 0 - x - u; x integer with
. If there exists some row P
such that a subset S of items in fj 2 ng 0g has the divisibility
property, then we can investigate the polyhedron: convfx 2
and generate inequalities for this polyhedron. By
computing lifting coefficients for the items in N n S, we obtain a valid inequality
for the overall polyhedron convfx 2 g. This
approach can always be used to apply knowledge about special integer programs
to more general cases.
Another idea is to try to relax a given integer program as a sequential knapsack
problem. Given a row
of an integer program, the easiest way to
obtain a relaxation as a sequential knapsack problem is to choose, a priori, a set
of divisible numbers f say. The sequential knapsack problem defined via
the constraint X
is certainly a relaxation of the given integer program.
A more specific relaxation is obtained by generalizing the concept of (1; k)-
configurations. Consider the 0=1 knapsack problem defined by the constraint
with N :=
assume that f(S) - F , f(S)
define a partition S 1 of the set N
of items as
Based on this partition, we define an inequality with the divisibility property that
is valid for the given 0=1 knapsack problem. We set b 1 := 1 and, for
we define
Note that t j - We define finally
If such a t -+1 exists (i.e. if f s ! f then the inequality
is valid for the 0=1 knapsack problem. Before verifying this statement, let us
illustrate the above construction on an example.
Example 5.1. Consider the knapsack problem in 0=1 variables defined via the
constraint
3. We choose
This meets the requirements that the indices
must satisfy, because f 4 - f 3 +f 2 and f 8 - f 7 +f 6 . In this example, the inequality
(?) is of the form
and it is valid for the given knapsack polytope.
Let us now show that the inequality (?) is always valid under the above assump-
tions. It is valid if and only if every subset T ' S with f(T
equivalently if and only if the problem
s
has an optimal value f
Setting Y j :=
first show that there always exists an
optimal solution to this problem with Y First, observe
that Y - t -+1 is infeasible for this problem because b
as by construction
solution obtained by decreasing Y - \Gamma1 by t - and increasing Y - by 1 is at least as
good as the initial solution in terms of objective value
equivalently in
terms of the knapsack constraint
optimal solution
with can be transformed into an optimal solution with
Proceeding in this way for all , we can produce an optimal solution
with
The objective value of such a solution satisfies
because implies that there exists z 2 S j with y
such that f
Summing these inequalities for
Hence r and the inequality is valid.
By construction, b j is a multiple of b j \Gamma1 for all j - 2. It follows that (?) has the
divisibility property and we can apply all of our information for the sequential
knapsack polytope induced by inequality (?). In case that if we impose
a "regularity condition" such as "every subset T in S with b(T
then the corresponding inequality defines a facet of
the 0=1 knapsack polytope [8].
For - 2 one can also derive sufficient conditions under which inequality (?)
defines a facet of the corresponding polytope. Yet, such conditions are quite
technical and we refrain within this paper from explaining further details.
If one finds such generalized (1; k)-configurations or some subset of the items having
the divisibility property with respect to some row of a given integer program
all the knowledge about the sequential knapsack polytope can be
used. Together with lifting this yields a powerful tool that might help solving
integer programs.

Acknowledgement

. This research was partially supported by Science Program
SC1-CT91-620 of the EEC and contract ERB CHBGCT 920167 of the EEC
Human Capital and Mobility Program.



--R

"The sequential knapsack pro- blem"
"Some polyhedra related to combinatorial problems"
"Cutting planes and the sequential knapsack problem"
"Solving sequential knapsack problems "
"Graph theory and integer programming "
"The cutting stock problem and integer rounding"
"A Note on 0-1 Programming"
"(1,k)-Configurations and Facets for Packing Pro- blems"
"Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation"
"On the 0/1 knapsack polytope"
"Hilbert bases and the facets of special knapsack pro- blems"
"Faces of Linear Inequalities in 0-1 Variables"
--TR
integer programming;linear programming formulation;knapsack problem;knapsack polytope;separation