Hard Equality Constrained Integer Knapsacks.
We consider the following integer feasibility problem: Given positive integer numbersa0,a1, ... , a n , with gcd( a1,..., a n does there exist a vectorx?Z n =0satisfyinga x= a0? We prove that if the coefficientsa1,..., a nhave a certain decomposable structure, then the Frobenius number associated witha1,..., a n , i.e., the largest value ofa0 for whicha x= a0 does not have a nonnegative integer solution, is close to a known upper bound. In the instances we consider, we takea0 to be the Frobenius number. Furthermore, we show that the decomposable structure ofa1,..., a nmakes the solution of a lattice reformulation of our problem almost trivial, since the number of lattice hyperplanes that intersect the polytope resulting from the reformulation in the direction of the last coordinate is going to be very small. For branch-and-bound such instances are difficult to solve, since they are infeasible and have large values ofa0/ a i , 1= i= n. We illustrate our results by some computational examples.
Introduction
1.1 Problem Statement and Summary of Results
In the past decade there has been substantial progress in computational integer
programming. Many large and complex instances can now be solved.
There are, however, still many small instances that seem extremely hard
to tackle by standard methods such as branch-and-bound or branch-and-
cut, and it is still quite unclear what makes these instances so hard. Examples
are the so-called market share problems, Cornu'ejols and Dawande
(1999), and Aardal et al. (2000a), some feasibility problems reported on by
Aardal et al. (2000b), and certain portfolio planning problems, Louveaux
and Wolsey (2000). All of these are related to the following simple problem.
Let a 0 ; a a n be positive integer numbers with a
The problem is:
Does P contain an integer vector? (2)
If the components of x may take any integer value, then the problem is
easy. There exists a vector x 2 Z n satisfying only if a 0
is an integer multiple of gcd(a The non-negativity requirement
on x makes the problem NP-complete. In this study we focus on infeasible
instances to rule out that a search algorithm terminates fast because it found
a feasible solution by luck. The largest value of a 0 such that the instance of
(2) given by the input a is infeasible is called the Frobenius number
of a denoted by F (a
Infeasible instances with large ratios a 0 =a
hard for branch-and-bound. In this context we address two topics.
The first one is to provide a sufficient explanation why certain coefficients
will yield large Frobenius numbers than others of comparable
sizes. In Theorem 1 we demonstrate that the Frobenius number is relatively
large if it is possible to decompose the a-coefficients as a
large compared to p i and jr i j.
This leads to the second topic: we give a sufficient condition under which
the lattice reformulation using the projection suggested by Aardal, Hurkens,
and Lenstra (2000b) will work significantly better than branch-and-bound
on instances of type (2). We show that with a 0 ; a above, the re-formulation
by Aardal, Hurkens, and Lenstra is computationally very easy
to solve in a way similar to Lenstra's algorithm (H.W. Lenstra, Jr. (1983)),
since the projected polytope will be thin in the direction of the last coor-
dinate. This is demonstrated in Section 3.2. So, these instances that are
very difficult for branch-and-bound are easy if first reformulated according
to Aardal, Hurkens and Lenstra. Their reformulation, based on lattice basis
reduction, is briefly described in Section 2. We also see that instances with
a-coefficients that decompose in the more general way: a
with M and N large compared to p i and jr i j,
will be easy to solve after applying the reformulation. For this decompo-
sition, however, we have not yet been able to prove that it leads to large
Frobenius numbers.
To illustrate our observations we report on a modest computational study
on infeasible instances from the literature, and infeasible instances that we
generated ourselves. About half of the instances have a-coefficients that decompose
as discussed above and in Section 3, and the others have random
coefficients of comparable sizes. All instances have 5 - n - 10. The computational
results, presented in Section 4, clearly confirm our theoretical
observations.
Before presenting our results we will, in the following subsection, give a
short description of some known results on integer programming.
1.2 Integer Programming and Branching on Hyperplanes
The polytope P ' R n as defined by (1) has dimension it is not
full-dimensional. In the full-dimensional case the following is known. Let S
be a full-dimensional polytope in R n given by integer input. The width of
S along the nonzero vector d is defined as W (S; d)
Sg. Notice that this is different from the definition of
the geometric width of a polytope. Consider the problem: "Does the polytope
S contain a vector x in the integer lattice Z n ?" Khinchine (1948) proved
that if S does not contain a lattice point, then there exists a nonzero integer
vector d such that W (S; d) is bounded from above by a constant depending
only on the dimension. H. W. Lenstra, Jr., (1983) developed an algorithm,
exploiting this fact, for determining whether a given polytope S contains
an integer vector or not. The algorithm either finds an integer vector in
S, or a lattice hyperplane H such that at most c(n) lattice hyperplanes
parallel to H intersect S, where c(n) is a constant depending only on the
dimension n. The intersection of each lattice hyperplane with S gives rise to
a problem of dimension at most n \Gamma 1, and each of these lower-dimensional
problems is solved recursively to determine whether or not S contains an
integer vector. One can illustrate the algorithm by a search tree having at
most n levels. The number of nodes created at each level is bounded from
above by a constant depending only on the dimension at that level. Hence,
the algorithm is polynomial for fixed dimension. A search node is pruned
if, in the given direction, no lattice hyperplane is intersecting the polytope
defined by the search node.
We are not aware of any implementation of Lenstra's algorithm. Cook et
al. (1993) implemented the integer programming algorithm by Lov'asz and
Scarf (1992), which is similar in structure to Lenstra's algorithm, and they
observed that, for their instances, the number of search nodes created by
the Lov'asz-Scarf algorithm was much less than the number of nodes of a
branch-and-bound tree. To compute a good search direction in each node
was, however, more time consuming than computing an LP-relaxation. This
raises the question of understanding if there are situations in which good
search directions can be determined fast. This is related to one of the results
presented in this paper, as we demonstrate that for a class of very difficult
infeasible instances, i.e., the instances that have decomposable a-coefficients
as outlined above, the projection proposed by Aardal, Hurkens, and Lenstra
by itself yields an integer direction in which the projected polytope is provably
thin. In our case this direction is the last coordinate direction. So, if we
apply a tree search algorithm, such as Lenstra's, to the projected polytope,
but branch only in coordinate directions in the order of decreasing variable
indices, then the instances become very easy.
1.3 Notation
We conclude this section by introducing some definitions and notation. The
Euclidean length of a vector x 2 R n is denoted by jxj, the n \Theta n identity
matrix by I (n) , the zero p \Theta q matrix by 0 (p\Thetaq) , where the dimensions are
omitted if they are clear from the context.
The m \Theta n matrix A is said to be in Hermite normal form if it has
the form (C m\Thetam ; 0 m\Theta(n\Gammam) ), where C is a lower triangular, non-negative
matrix in which each diagonal element is the unique maximum row entry.
The Hermite normal form of the matrix A is denoted by HNF (A), and it is
unique if A has full row rank.
A set of the form
are linear independent vectors in R n , l - n, is called a
lattice. The set of vectors fb l g is called a lattice basis. A lattice has
two different bases if l = 1, and infinitely many if l ? 1.
The determinant d(L) of the lattice L is defined as
det (B T B),
where B is a basis for L, and where B T denotes the transpose of matrix B.
If the lattice L is full-dimensional we have Bj. The rank rk L of
the lattice L is the dimension of the Euclidean vector space spanned by L.
If rk then d(L) is defined to be equal to one.
The integer width of a polytope S ae R n in the non-zero integer direction
defined as:
I
The number of lattice hyperplanes in the direction d that intersect S is equal
to W I (S; d) does not contain an integer
vector.
2 The Reformulation and the Search Algorithm
The starting point of the reformulation of (2) suggested by Aardal, Hurkens,
and Lenstra (2000b) is the sign relaxation of
g. The relaxation X I can be rewritten as X I =
is an integer vector satisfying
is a basis for the lattice L 0g.
That is, there is an integer vector x f such that any vector x 2 X I can be
written as the sum of x f and a vector x
and a 0 is integer, we know that a vector x f exists. In the paper by Aardal et
al. it is shown that x f and B 0 can conveniently be determined in polynomial
time using lattice basis reduction.
Let
fy
Problem (2) can now be restated as:
Does Q contain an integer vector?
The polytope Q is a full-dimensional formulation, i.e., the dimension of
as mentioned in the previous section we can apply Lenstra's
(Lenstra (1983)) algorithm, or any other integer programming algorithm,
to Q. Here we will consider a tree search algorithm inspired by Lenstra's
algorithm, but using only unit directions in the search.
be the ith unit vector, let
(assume recursively define a feasibility search process Search(S)
on a set S ' J as follows:
if S is empty, output the point fk j g j2J , print 'feasible' and quit
otherwise:
pick an i 2 S
compute l
compute
for all integers k i in the interval [l do Search(S n fig)
print 'infeasible' and quit
The feasibility search is then defined as Search(J). For an example of a
search tree, see Figure 1. Notice that the search tree created in this way is
similar to the search tree of Lenstra's algorithm in that the number of levels
of the tree is no more than the number of variables in the problem instance,
and that the number of nodes created at a certain level corresponds to the
integer width of the polytope in the chosen search direction.
l ? u
l ?
l ? u
Figure

1: The search tree for instance prob2 (cf. Section
Here we will investigate a class of instances that are exceptionally hard
to solve by branch-and-bound when using the original formulation in x-
variables, but that become easy to solve when applying the branching scheme
described above to the reformulated problem in y-variables (3). In our implementation
of the algorithm Search(S), we always choose the index i as
the highest index in the set S when we are at the step "pick an index i 2 S",
i.e., we branch in the order 1. This is done because the width in the
unit direction e n\Gamma1 is small for our class of instances as will be demonstrated
in following section. Below we give an example of such an instance.
Example 1 Let
A vector x f and a basis B 0 for this instance is:
\Gamma3 \Gamma1222
The polytope Q is:
fy
Moreover, we have W I (Q; e 1 so if we consider
the search direction e 2 first, we can immediately conclude that
If we solve the formulation in x-variables by branch-and-bound with objective
function 0 using the default settings of CPLEX 6.5, it takes 1,262,532
search nodes to verify infeasibility. 2
An instance such as the one given in Example 1 may seem quite artificial.
However, some of the instances reported on by Cornu'ejols and Dawande
(1999), Aardal et al. (2000a,b), and by Louveaux and Wolsey (2000) stem
from applications and show a similar behavior. From a practical point of
view it is therefore relevant to try to explain this behavior.
3 The Class of Instances
3.1 The Coefficient a 0
The polytope P as given in (1) is an n-simplex. An instance of problem (2)
is particularly hard to solve by branch-and-bound if it is infeasible and if
the intersection points of the n-simplex with the coordinate axes have large
values. Branch-and-bound will then be forced to enumerate many of the
possible combinations of x Since the instance
is infeasible we cannot "get lucky" in our search, which may happen if the
instance is feasible, and if we by chance have chosen an objective function
that takes us to a feasible solution quickly. Example 1 of the previous section
illustrates such a hard infeasible instance. Similar, but larger, instances
are virtually impossible to solve using a state-of-the-art branch-and-bound
algorithm such as implemented in CPLEX.
To create infeasible instances with maximum values of a 0 =a i we choose a 0
as the Frobenius number F (a Computing the Frobenius number
for given natural numbers a
In

Appendix

1 we discuss the algorithm that we used in our computational
study. For it is known that F (a 1 ; a 2
matics from the Educational Times, with Additional Papers and Solutions",
Sylvester published the problem of proving that if a 1 and a 2 are relatively
prime integers, then there are exactly 1=2(a non-negative integers
ff less than a 1 a does not have a
non-negative integer solution. The solution to this problem was provided by
Curran Sharp in volume 41 (1884) of the journal. The precise reference is
Sylvester (1884). See also Schrijver (1986) p. 376.) For the Frobenius
number can be computed in polynomial time, see Selmer and Beyer (1978),
R-odseth (1978), and Greenberg (1988). Kannan (1992) developed a polynomial
time algorithm for computing the Frobenius number for every fixed n.
His algorithm is based on the relation between the Frobenius number and
the covering radius of a certain polytope. Some upper bounds on the Frobenius
number are also known. If a 1 ! a showed
that F (a . Other upper bounds were provided by
Erd-os and Graham (1972) and Selmer (1977).
Below we determine a lower bound on F (a
a i as a We express the lower bound as a function
of p; r and M . The highest order term in M is quadratic in M , so for
large values of M , and relatively small values of p i and jr i j, this term will
be dominant.
Theorem 1 Let a
and let (r k =p k g. Assume that:
1. a 1 ! a
2.
3.
5.
Then, we obtain f(p;
and
Proof: The upper bound g(p; r; M) is derived from the result by Brauer
(1942) that F (a
In our proof of the lower bound we introduce the following notation:
The lattice L 0 is defined as B " Z n as in Section 2.
The lattice L 0 is contained in parallel hyperplanes generated by C

Figure

2: B, C, and L 0
The idea behind the proof is as follows. We define a homomorphism from
\Delta t to R=Zsuch that x 2 Z maps to 0, if such a vector x exists. An
integer number t for which 0 is not contained in the image of \Delta t under
this map then provides a lower bound on the Frobenius number. We define
such a homomorphism by first defining a projection - z , along the vector z,
of z is in the same plane as \Delta 1 . Then we consider a
R=Z. We show that the kernel of f is L 0 +C. Due
to the First Isomorphism Theorem (see e.g. Hungerford (1996), p. 44) we
know that B divided out by (ker f ), i.e., B=(L 0 +C), is isomorphic to R=Z.
The image of - z under the isomorphism B=(L R=Zturns out
to be an interval [l; u] in R=Z. Finally we determine an integer number t
such that [tl; tu] does not contain an integer point. The integer t then yields
a lower bound on the Frobenius number under the conditions given in the
theorem.
We first define a linear mapping -
where z satisfies
then - z Notice that \Gammaz 62 C as
Next we define the homomorphism R=Zgiven by x 7! (px
mod 1).
Claim: The kernel of f is
First we show that (L 0
which implies px 2 Z, and hence (px mod
then
Next, show that (ker f) ' (L 0 +C). Notice that each element
in B can be written as c
such that the absolute value of each element of y 2 is in the
interval (\Gamma1=2; 1=2). Since f(c+y 1 +y 2
0 and since
contradicts y 2 62 C. So,
ay ry 2 , and since py 2 is integral we have that
ry 2 is an integer multiple of M . Now, observe that since the
absolute value of each element of y 2 is less than 1=2, then, due
to Assumption 3 of the theorem, ry
therefore is the only possible solution. This concludes the
proof of our claim.
Due to the First Isomorphism Theorem, the homomorphism f induces an
R=Z. Below we determine the image of \Delta 1
under the composition of the mappings -
R=Z. This composition of mappings is a homomorphism.
We use v i to denote vertex i of \Delta 1 . Vertex v i , is the vector
is the ith component of v i . Applying
the linear mapping - to v i yields - z (v i Next, by the isomorphism
and (r k =p k g. Then, since \Delta 1 is the convex hull of the
vertices is a homomorphism, the image of - z
is an interval [d j ; d k ] of length
Now we will demonstrate that there exists an integer t - b 1\Gamma2d j
L c such
that the interval [td does not contain an integer point. This implies that
L c is a lower bound on the Frobenius number. Notice that
due to Assumption 4.
c. The interval [I has length less than
or equal to 1 \Gamma 2d j . Let
The number k 0 - k yields an interval [I 0
such that I 0is integral. The interval [I 0
does not contain an integer since the
length of [I 0
2 ] is less than or equal to the length of the interval [I
and since I 0
1 is integral. Now define k  We claim that the interval
[I
does not contain an integer point. To prove the claim,
first assume that k 0 is integer. Then k   d
due to
Assumption 5 that implies that d k ! 2d j . Next, assume that k 0 is fractional.
In this case we obtain I 0
and, due to the same reasoning as
This finishes the proof of our claim.
We finally notice that k   - b 1\Gamma2d j
so we can conclude that b 1\Gamma2d j
a lower bound on the Frobenius number. We obtain
The a-coefficients in Example 1 decompose as follows. Let
12223.
a
Theorem 1 yields a lower bound on the Frobenius number equal to 149; 381; 362
and an upper bound equal to 448,192,961. The Frobenius number for this
instance is 149; 389; 505, which is very close to the lower bound. 2
For all our instances that decompose with vectors p and r that are short
compared to M , the Frobenius number is large, see the computational study
in Section 4. We have computed the lower bound on the Frobenius number
for these instances and in all cases it was close to the actual value. It would
be interesting to investigate whether it is possible to use similar techniques
to tighten the upper bound on the Frobenius number for instances of this
sort.
In the following subsection we demonstrate that instances with a-coeffi-
cients that decompose with large M and relatively short p and r are trivial to
solve using the reformulation outlined in Section 2. These are the instances
that are extremely hard to solve by branch-and-bound due to the large
Frobenius numbers.
3.2 The Coefficients a
For the further analysis of our class of instances we wish to express the
determinant of the lattices L 0 and a sublattice of L 0 in terms of the input.
Before presenting our results, we introduce more notation, two definitions,
and present some known results. For more details, see for instance Cassels
(1997).
be a lattice in a Euclidean vector space E, and let K
be subgroup of L. If there exists a subspace D of E such that
then K is called a pure sublattice.
be a lattice in R n . Its dual lattice L y is defined as
follows:
Suppose that K is a pure sublattice of the lattice L. Then the following
holds:
For a lattice L and its dual L y we have
Let L be a lattice with dual L y , and let K be a pure sublattice of L. Then
and we can write
Theorem
Proof: Take L to be the lattice Z n , and K to be the lattice L 0 . By
equation (4) we have equivalently, by
equation (5):
From (6) we obtain (Z n =L 0
, and since the dual lattice of Z n is
again Z n we have L ?
g. Since
is exactly the lattice L(a T ) with basis a T . So,
We have obtained
result is also mentioned in Section 3.2 of the survey by Nguyen and
Stern (2000).
Remark 1 Notice that d(L 0 ) can also be computed as
is a basis for L 0 .
Write a denote the
orthogonal complement of the hyperplane spanned by p and r, as in the
proof of Theorem 1. We denote the lattice C " Z n by LC .
Proposition 3 The lattice L 0 contains the lattice LC . The rank of the lattice
LC is equal to n \Gamma 2.
Proof: Assume that x 2 Z n satisfies
which shows that L 0 ' LC .
To prove that rk to create a contradiction, that p
and r are linearly dependent, that is, we can write
Write - as
has to be
an integer multiple of g, i.e., Z. We can now express a i as
a
gM+g- I +f being integer. This contradicts that gcd(a Hence
and r are linearly independent, which implies that the rank of LC is equal
to 2. 2
Let
Theorem 4
Proof: This proof follows the same lines as the proof of Theorem 2. Here
we choose the lattice L from Definitions 1 and 2 to be the lattice Z n , and
the sublattice K to be the lattice LC . We have
and since (Z n
g.
be a basis for L ?
C . The vectors p and r are linearly independent (see
proof of Proposition and belong to the lattice L ?
C generated by B C . This
implies that d(L(P T
To summarize, we have
The determinant of the lattice L(P T ) is equal to
0 be a basis for L 0 , and assume without loss of generality
that these basis vectors are ordered such that b 1
0 form a basis
for the lattice LC . Hence, b
0 does not belong to LC . Let
h be the distance of b
0 to H . Notice that h - jb
j.
Corollary 5
Proof: The following holds:
Suppose p and r are short relative to M . Then, Lov'asz' basis reduction
algorithm (Lenstra et al. (1982)) yields a basis in which the basis vectors are
ordered according to increasing length, up to a certain factor. In a basis B 0
for L 0 , such as we generate it, the first vectors form a basis for the lattice
LC . These vectors are short, since the basis is reduced and since the determinant
of the lattice LC is bounded from above by
The length of the last vector of B 0 will be bounded from below according
to Corollary 5.
Example 3 Recall the decomposition of the a-coefficients from Examples
1 and 2. Let
a
so . The first column of B 0 , (0; \Gamma3; 1) T , is
short. This vector is orthogonal to a; p, and r. The second, and last, column
of B 0 , (12224; \Gamma1222; \Gamma3667) T , is long. 2
To summarize, if the determinant of the lattice L 0 is large due to a large
value of M , then this large value basically has to be contributed by the last
vector b
. The long vector b
0 implies a small value of the integral
width of Q in the unit direction e n\Gamma1 , so only a few, in fact often zero or one,
lattice hyperplanes intersect Q in this direction for the instances we consider.
In Example 1 we observed that W I (Q; e 2 immediately gave
us a certificate for infeasibility.
The argument regarding the length of the columns of B 0 presented above
also holds in the more general case that the a-coefficients decompose as
follows:
a
and N are assumed to be large
compared to p i and jr i j.
Computational Results
To illustrate our results we have solved various instances of type (2). The
instances are given in Table 1. In the first column the instance name is given.
The
instances
Instance
a
Frobenius number
cuww1122246111989643481
cuww2366794890873365cuww3242693640760683cuww4132125284479268104723595

Table

2: A value of M for instances cuww1-5 yielding short p and r
cuww1 cuww2 cuww3 cuww4 cuww5
Next, in column "a", the a i -coefficients are given, and in the last column
the Frobenius number can be found. For all the instances we computed the
Frobenius number using the algorithm described in Appendix 1. The instances
can be divided into two groups. The first group contains instances
cuww1-cuww5 and prob1-prob10, and the second group consists of instances
prob11-prob20. Instances cuww1-cuww5 were generated by Cornu'ejols, Ur-
baniak, Weismantel, and Wolsey (1997), and the remaining instances were
generated for this study. For each of the instances cuww1-cuww5 there is a
decomposition a vectors p and r. In Table 2 we give
values of M that yield short vectors p and r for these instances. Instances
were generated such that the a-coefficients have a decomposition
a and r. We randomly generate M from
the uniform distribution U[10000; 20000], N from U[1000; 2000], p i from
U[1; 10], and r i from U [\Gamma10; 10].
In contrast, the second group of instances prob11-prob20 were randomly
generated such that the a-coefficients are of the same size as in
prob1-prob10, but they do not necessarily decompose with short vectors
p and r. We chose the same size of the a-coefficients since this yields values
of d(L 0 ) of approximately the same size as for the instances prob1-prob10.
For instances prob11-prob20 coefficient a i is randomly generated from
The computational results of verifying infeasibility for the instances is
reported on in Table 3. For each instance a we used the Frobenius number
as the right-hand side coefficient a 0 . For each of the instances
we computed d(L 0 ), the length of each of the basis vectors of the basis
, and the number of lattice hyperplanes intersecting Q in the coordinate
directions e 1 and e n\Gamma1 . We then applied the integer branching algorithm described
in Section 2 to Q. The number of nodes that were generated, and the
computing time in seconds are given in the columns "# Search tree nodes"
and "Time". Finally, we attempted to solve the instances, using the original
formulation P , by standard linear programming based branch-and-bound
using CPLEX version 6.5.3 . The number of nodes needed by branch-and-
bound, and the computing time in seconds are reported on in the columns
"# B&B nodes" and "B&B time". For the branch-and-bound algorithm we
set the node limit to 50 million nodes. If an instance was not solved within
this node limit, this is indicated by "? 50 \Theta 10 6 " in the column "# B&B
nodes". The time t needed to evaluate the 50 million nodes is then indicated
as "? t" in the column "B&B time". All the computations were carried out
on a Sun Ultra 60 Model 2360 workstation with two UltraSPARC-II 359
MHz processors (our implementation is sequential) and 512 MB of memory.
We make the following observations. First, the Frobenius number of the
instances cuww1-cuww5 and prob1-prob10 is about two orders of magnitude
larger than the Frobenius number of instances prob11-prob20 (see Table 1).
Infeasible instances are typically harder to solve than feasible ones, and the
larger the intersection points a 0 =a i between the n-simplex P and the coordinate
axes, the harder the instance becomes for branch-and-bound. So, as a
class, the first group of instances is harder for branch-and-bound. In Table 3
we can see that instances cuww1-cuww5 and prob1-prob10 are considerably
harder to solve by branch-and-bound than instances prob11-prob20. The
presolver of CPLEX was able to verify infeasibility for instances cuww2 and
prob10, but none of the other instances in the first group was solved within
the node limit of 50 million nodes. All of the instances prob11-prob20 were
solved by branch-and-bound within half a million search nodes and one
minute of computing time.
We also observe that the shape of the polytope Q is very much influenced
by the decomposition of the a-coefficients. If the coefficients decompose with
short vectors p and r relative to M , then the width of the corresponding
polytope Q in the unit direction e n\Gamma1 is very small. This made the instances
trivial for our tree search algorithm applied to Q. All instances were solved
using less than twenty search nodes and a fraction of a second computing
time. For instances prob11-prob20 where the a-coefficients are generated
randomly from a certain interval we observe that the width of Q is of the
same size in all unit directions, and in general greater than two. Our tree
search algorithm applied to Q therefore needed more nodes and longer computing
times than for the first group of instances. Still, none of the instances
needed more than 126 nodes and about a tenth of a second
computing time.

Table

3:
Verification
of
infeasibility
Instance
WI
)+WI
Search
Time
tree
nodes
nodes
time
8139:3
7797:5
7912:6
5411:5
prob102.02.22.22.41165.22:002prob113.64.54.64.76.15.0059.3
prob144.44.04.75.15.67.01243.4
prob153.64.13.94.86.03.08049.4
prob164.03.74.24.69.72.08061.4
prob174.64.24.64.05.74.15024.1
Presolve
determines
problem
is
or
unbounded.

Acknowledgments

We want to thank Hendrik Lenstra for his valuable suggestions and in particular
for the outline of the proof of Theorem 1. We also wish to thank Bram
Verweij for providing a framework code, based on his general enumeration
library, for our integer branching algorithm.
The research of the first author was partially financed by the project
TMR-DONET nr. ERB FMRX-CT98-0202 of the European Community.



--R


Towards a solution of the Cornu'ejols- Dawande instances
Solving a system of diophantine equations with lower and upper bounds on the variables.
On a problem of partitions.
On a problem of Frobenius.
An Introduction to the Geometry of Numbers.
An implementation of the generalized
ORSA Journal on Computing 5
A class of hard small 0-1 programs
Decomposition of integer programs and of generating sets.


Solution to a linear Diophantine equation for nonnegative integers.

Lattice translates of a polytope and the Frobenius Problem.
A quantitative formulation of Kronecker's theory of approximation (In Russian).


The generalized
Mathematics of Operations Research 17
Combining problem structure with
Lattice reduction in cryptology.
Theory of Linear and Integer Programming
On the linear diophantine problem of Frobenius.


--TR

--CTR
K. Fukuda , A. N. Jensen , N. Lauritzen , R. Thomas, The generic Grbner walk, Journal of Symbolic Computation, v.42 n.3, p.298-312, March, 2007
lattice basis reduction;frobenius number;branching on hyperplanes