:=

U

y~~

we know from Gordan's Lemma that there exists a unique finite set of points {bl,..-,/9,} in P such that for every y ~ Zn\{0} we have that b(y) _ bj for at least one indexj e { 1 , . . . , t}. We remark that for x,y ~ 7In \{0}, x ~ y, we have that Sx - Sy if and only if b(x) < b(y). For i ~ { 1 , . . . , t} let y[i, 1],..., y[i, ni] be all the points in z n \ { 0 } for which b(y[i,j])=bi,j= 1 , . . . , h i . Note that because Q(b, co) is bounded for all b ~ Z m, co E F,, these sets of y-points exist and are finite. It foilows that the set o f integral points t

W := U{y[i, 1],... ,y[i, ni]} i=1

16

R. Weismantel

so that [~(y[i,j]) = [~i for all i = 1 , . . . , t a n d j -- 1,... ,ni contains the set of all minimal points with respect to the partial order < P. A subset of W that contains the minimal points with respect to < P is a neighborhood system of the origin. 9 Let x be a feasible point of the integer program min{cl"x : A x < b, x e 7ZY) and assume that every integral y such that A y < b satisfies c r x ~ cry. By checking the elements of N ( x ) we can decide whether x is optimal.

Theorem 4.3: Let A ~ 7Zrnxn, b E 7Z.m and let c ~ R n be a non-degenerate objective function, i.e.,for every pair o f integral points x, y with A x < b a n d A y < b we have that cT"x # cry. A feasible point x is optimal f o r the integer program min{crx : A x < b , x ~ Z n } if and only iffor every z e N ( x ) we have that c r z > 0 or x + z is not feasible.

Proof" It is clear that if x optimal, there does not exist any z ~ N ( x ) such that x + z is feasible and c r z < 0. Let x be a non-optimal point of the program min{cT"x : A x < b, x e 7Z.n } and lety denote the optimal solution of this program. It follows that the convex body Sy-x = {z ~ IRn : A f z < max(0, A T ( y -- x)u M , cZz < max(0, cZ(y - x) > 0} is not empty. I f y - x is a neighbor of 0, then y is a neighbor of x and the claim follows. Otherwise, y - x is not a neighbor of the origin, i.e., there exists v e Z n such that So ~ Sy-x, see the proof of Theorem 4.2. Therefore, for every i e M, we have that ~ j ~ N Aovj < 0 if Aij(yy - xj) <_ 0 and Aovj <- Y']jeN Aij(yj - xj) if ~ j e N A~i(YJ - xj) > O. This means that x + v is feasible. On account of the conditions cT(y -- x) < O, So --- Sy-x and c r y r 0 because c is non-degenerate, we conclude that cTv < 0. Hence, x can be improved by v. 9 For families of integer programs of the form

EjeN

EjeN

m i n cTx : A x = b, 0 < x < u, x e 7Zn with fixed A ~ 2~mxn and varying c e 2~n,b E 7/.m, we have introduced in the previous sections two test sets: the universal GrSbner basis and the Graver test set. The elements of the Graver test set in this special situation may also be interpreted as neighbors of the origin: First note we can rewrite A x = b, 0 <_ x <_ u as A x = b, Ix <__u, - I x < O. Since we investigate here families of lattice points that satisfy A x = b, 0 <_ x < u, x e Z" we require that a neighbor y of the origin must satisfy A y = 0. Let y E 7Z"\ { 0 ) such that A y = 0. With y we can - like in the proof of Theorem 4.2 - associate a convex body Sy -- {x E ~ n : min{O,yi} < x < max{O, yi}Vi e N , CTx < max{O, c r y } } .

Test Sets of Integer Programs

17

Sy is the smallest body containing 0 and y that one obtains from a parallel trans-lation of the inequalities associated with the rows of I and - I and the hyperplane with normal vector c. Let Oj be the orthant that corresponds to y. if y is not the sum of two other integral vectors x and z from the same orthant Oj that satisfy A x = A z = O, then the convex body Sy is free of relative interior lattice points. Therefore, every element of the Graver test set defines a neighbor of the origin. Conversely, if for y ~ Z n, A y = 0, the body Sy does not contain a point x ~ Z n such that A x = 0 in its interior, then y is either contained in the Graver test set, or y can be written as the sum of two integral points x and z, A x = A z = 0 that lie on the boundary of the body Sy. Neighbors of the origin [32] define maximal lattice free convex bodies that are a central topic in the geometry of numbers. In fact, in the last 20 years there appeared many beautiful papers that derive deep results for integer programming by using methods from the geometry of numbers that we cannot here quote them all. However some important and recent references on the study of maximal lattice free bodies and their relation to integer programming are Kannan [23], Kannan & Lovasz [24], Kannan, Lov~sz & Scarf [25], Lov~isz [28], B~ir~iny, Howe & Scarf [2], Lagarias [26], Gritzmann & Wills [18]. We also refer to the references given there.

5 Basic Examples Throughout this section we present elementary examples of test sets. The combinatorial optimization problems that we consider are a special case of the knapsack problem, the matroid optimization problem and the minimum cost flow problem. Primitive Partition Identities

Consider the following family of knapsack problems with varying c ~ Z n and beN: max c l x t + 99 9 + cnxn : Xl + 2x2 + 999 + nXn = b , x ~ b l n .

Definition 5.1: A partition identity is an identity o f the f o r m

al + a 2 + . . . + a ~ = bl +b2 + . - - + b t such that 0 < ai, bj <_ n are integral f o r all i = 1 , . . . , k a n d j = 1 , . . . , l. A partition identity is called primitive i f there are no proper subsets o f { a l , . . . , ak} and { b l , . . . bt} that f o r m a partition identity.

18

R. Weismantel

Example 5.2: 1+1=2; 2+2=1+3, 2+2+2=3+3, 1 + 1 + 1 = 3 are all the primitive partition identities f o r n = 3.

1+2=3,

Next we want to mention that the number of elements k + l involved in a primitive partition identity does not exceed the value 2 n - 1. This bound is sharp since n x (n - 1) = (n - 1) x n. For a proof of Theorem 5.3 we refer to Diaconis, G r a h a m and Sturmfels [10], see also Sturmfels [37].

Theorem 5.3: Every primitive partition identity with largest number n satisfies k+l<_2n-1.

There is a relation between the set of all primitive partition identities, the Graver test set H and the union of all reduced G r t b n e r bases G for the above family of knapsack problems.

L e m m a 5.4: L e t P denote the union o f all vectors o f the f o r m e a~ + e a2 + . 99 + e ak - e b t - e b2 . . . . . e b~, where al + az + . . . + ak = bl + b2 + . - . b[ defines a primitive partition identity. Then P = H. However, G ~_ P and, in 9eneral, G v~ P.

Proof" For the family of knapsack problems with varying c 9 Z n and b 9 N,

max ClXl +

9

" "

+ CnXn : Xl + 2X2 + "'" + nXn = b , x 9 N n ,

let Cj := {x 9 Oy : Ein=l ixi = 0} denote the pointed cone associated with orthant Oj and/-/j its Hilbert basis. By H = Uj Hy we denote the Graver test set, see Definition 2.11. The set G is the union of all reduced G r t b n e r bases associated with the above family of knapsack problems, see Definition 3.6. We already know the inclusion that G ~_ H , see Corollary 3.7. It is easy to see that P = H , because x 9 P if and only if x is integral and ~ i n l ixi = 0 and there does not exist any integral y such that Ei=I iyi = O,Y + ~ x + , Y - ~-~ X - . This implies that x 9 P if and only i f x 9 Cj n Z n for s o m e j and x is not the sum of integral vectors in Cj, i.e., x is an element of the Hilbert basis/-/j of Cj. To show that G r P, consider the following example. 4 + 2 + 2 = 8 is a primitive partition identity. By Theorem 3.9 we know that if e 4 + e 2 + e 2 - e 8 9 G, then v := e4 + e2 + e 2 is a vertex of conv{x 9 N s : ~i8__1j x j = 8}. Because v = 1 (2e 4) + 1 (4e2), we see that v is a convex combination of two other integral points in conv{x 9 N s : ~}81 j x j = 8}, and hence, v is not a vertex. 9 We have indicated here that primitive partition identities define test sets for knapsack problems. Besides this application, there is a motivation for the study

Test Sets of IntegerPrograms

19

of primitive partition identities coming from applied statistics. The application is the binary logistics regression that is discussed in [10]. The Matroid Test Set One of the fundamental structures in combinatorial optimization are matroids. Detailed discussions on matroids and independence systems can be found in [12] and [44]. We also want to mention the references given there. A matroid is a tuple (E, ~/) where E is a finite set and J/g is a collection of subsets of E with the following three properties:

(i) O e J / ; (ii) F _ G e J / i m p l i e s that F e Jr (iii) If F, G e ~ [ with IGI > IFI, then there exists f e G \ F Fw{f}eJg.

such that

The elements of J / a r e called independent sets. For S ~ E, the bases of S are the independent sets of S that are maximal with respect to inclusion. All bases of S have the same cardinality. This statement follows immediately from (iii), One special property of matroids is that, given a profit ci e ~ to every element i in the ground set E, one can find the independent set of maximal weight (profit) by using the Greedy algorithm. Algorithm 5.5 "Greedy Algorithm"

(1) Set F = 0. (2) As long as there exists i e E \ F with ci > 0 and F u {i} e ~/, choose i* e E \ F such that el, > 0, F u {i*} e J / / a n d el, = max{ei : i e E \ F , F u {i} e J / } . Add i* to F. The fact that one is able to optimize a linear function over the independent sets of a matroid in polynomial time via a fairly simple algorithm indicates that there should be a nice description of the test set in this case. Indeed, this is true as we now show. To simplify the exposition, we assume that (E, ~r is a matroid defined on the ground set E = { 1 , . . . , n } with {i} e J r for all i = 1 , . . . , n and set e i : = Z {i}. The symbol >-c denotes the order on the elements of E that we associate with the objective function c. Under these assumptions the following can be shown.

Theorem 5.6." For a matroid (E,.//r and an objective function e : E --* ff~, the set

T := {ei: i >-c O} u { - e l : i "'cj >'c O}

20

R. Weismantel

defines a test set f o r the matroid optimization problem

m a x { c r x M : M e d4} .

(2)

Proof" Let x be the incidence vector of the independent set M e J / / a n d assume that x is not an optimal solution of the problem (2). If there exists i ~ M such that i ~(c 0, then x - e i is the incidence vector of an independent set in ~ satisfying x - e i ~'c x. Therefore, x can be improved by an element in T in this case. For the following we can assume that i >-c 0 for all i e M. We denote by P the subset of E such that i ~ c 0 for all i e P. I f M is not a basis o f E, then there exists i e E \ M such that M w {i} belongs to ~/. This means that x + e i is feasible for the program (2) and X uU{i} ~-cx. Hence, x can be improved by some element in T. Otherwise, M is a basis of E. Let M* denote the basis of P such that x* = Zu* is an optimal solution of (2). It follows that [M 1 = [M* I. Set S := M* c~ M , R := M \ S and R* := M * \ S . Let i* e R* be the element with maximal profit, i.e., ci. = m a x { c i : i e R*}. As M* is obtained by applying the Greedy algorithm, ci, > c; for all i e R. Moreover, M is a basis associated with the ground set M u {i*}. S u {i*} is an independent set associated with the ground set M u {i*}. By iteratively applying Axiom (iii) we find R'~_ R, IR'I = IRI - 1 s u c h that S w {i*} w R' is a basis o f M w {i*}. Yet, S w {i*} w R' is also a basis of E as I S w {i*} w R ' I = IMt = [M*I. Setting {j} := R \ R ' , it follows that x - eJ + e e is the incidence vector of a basis of E and hence, feasible for (2). As ci, > c] and - e J + e i* ~ T, the proof is complete. 9 The M i n i m u m Cost Flow Test Set The shortest path problem, the m a x i m u m flow and the minimum cost flow problem are classical combinatorial optimization problems that one can attack with primal type algorithms. We refer to the book of Ahuja, Magnanti & Odin [1] for a comprehensive survey on this subject. We consider the following situation: Let G = (V, A) be a directed (di)graph with n = I vl nodes and m = n(n - 1) = IAI arcs. Let s and t ~ s be specified nodes in V : s e V is interpreted as the source node and t e V \ { s } is interpreted as sink node.

Definition 5. 7: For f e N , edge capacities u(i,j) E Z and cost C(i,j) ~ IN for all (i,j) E A such that u(t,s) = f and c(t,s) = O, the minimum cost flow problem defined f o r the digraph G consists in finding an optimal solution o f the integer

Test Sets of Integer Programs

21

programming problem

mill E ( i j ) ~ A

s,t.

C(i,j)xij

-

=

o

f o r all v ~ V ,

X(t,s) = f , x(i,j) e N ,

0 ~_~X(i,j ) ~_~U(i,j ) . Every feasible solution o f this program is called a circulation. In the following we characterize the Graver test set and the universal Gr6bner basis for the family of minimum cost flow problems when c , f and u vary. For this characterization we need to prove the so-called circulation decomposition theorem that we state as Theorem 5.10. Let x and y be feasible solutions for the minimum cost flow problem. Setting z := x - y, we see that for every v s V the following equation is satisfied:

z(f+(v)) - z ( 6 - ( v ) ) = x(6+(v)) - y(f+(v)) - (x(fi-(v)) - y ( f - ( v ) ) ) = O . On account of these equations we claim that z is the non-negative sum of at most m so-called signed incidence vectors of directed cycles in G. This notation is given below.

Definition 5.8: Let C ~_ A be a subset o f the set o f arcs. B y V( C) we denote the set o f all nodes that are incident to at least one arc in C. For C c_ A and i e V, the symbol 6c(i) denotes the degree o f i in Gc = ( V ( C ) , C), i.e., the number o f all arcs in C that are incident to i. 6+( i)(~c( i) ) denotes the out-degree (in-degree) o f i in Gc = ( V ( C ) , C), i.e., the number o f all arcs in C that leave (enter) node i. We call a set o f arcs C a cycle, if the subgraph Gc is connected and if f c ( i ) = 2 f o r all i E V(C). The cycle C is called directed if ~c(i) + = 6 c ( i ) - = 1 f o r all i ~ V(C). B y C we denote the set o f all incidence vectors o f directed cycles in G.

Definition 5.9: A signed incidence vector o f a directed cycle C in G is a vector z ~ { - 1 , 0 , + 1 } m such that 9 z(i,j) va - zq,i) f o r all (i,j) ~ C and 9 ~ff, j) = --z(Lo, i f z(i,i) < 0 and yf(cj) = z(i,j)" otherwise. We denote by cg~ the set o f all signed incidence vectors o f directed cycles in G.

22

R. Weismantel

I f z is a signed incidence vector of a directed cycle C in G, then the vector of absolute values of the components of z is the incidence vector of an undirected cycle in G. I f a component of z is +1, then this m a y be interpreted as having a "forward arc" in the cycle. I f a component of z is - 1 , then this m a y be interpreted as having a "backward arc" in the cycle. Signed incidence vectors allow to decompose difference vectors of feasible circulations.

Theorem 5.10: Let x ~ y be feasible solutions o f the minimum cost flow problem. The vector x - y is the non-negative sum o f at most m signed incidence vectors o f directed cycles in cg~. Theorem 5.10 tells us that if we are given a feasible circulation x that is not optimal with respect to some objective function c, then there must exist a vector in cg~ that one can use in order to improve x. Therefore, the collection of all signed incidence vectors of directed cycles in cg~ defines a test set for the minim u m cost flow problem.

Theorem 5.11: The set ~ is a test set for the family o f minimum cost flow problems as defined in Definition 5. 7 with f ~ N , c ~ Z m, and u ~ N m. In fact, it is not too difficult to show that for the complete directed graph G and for the family of minimum cost flow problems as defined in Definition 5.7 with varying f e N, e e 7/.m, and u e N 'n the Graver test set and the universal Gr6bner basis coincide with the set cg~.

6

Augmentation Problems and Graver Test Sets

In this section we summarize elementary links between the study of Hilbert bases and the Augmentation problem. We continue with the notation introduced in Section 2. Let Oj denote the j-th orthant in R n. Then Cj := Oj c~ {x ~ IRn : A x = 0} is a pointed polyhedral cone in F..". C} possesses a unique Hilbert basis Hj and H := U j ~ is a test set for the family of integer programs of the form IP(b, c) with l = 0, u = ~ n and varying c ~ Z" and b eTZ.m.

Definition 6.1." Let A e Z m• We say that a vector v e Z n \ { 0 } w e z n \ { 0 } i f v ~ w and i f the following properties hold"

reduces

23

Test Sets of Integer Programs

V+ ~ W + ,

V- ___W- ,

(Av) + _ ( A w ) + ,

( A v ) - ___ ( A w ) - .

(3)

w is called reducible in this case. ffthere does not exist v e Z n reducing w, we say that w is irreducible. I f v reduces w, then also w - v reduces w and we have that v + + (w - v) + = w + ,

v - + (w - v ) - = w - ,

(Av) + + ( A ( w - v)) + = ( A w ) + ,

(Av)- + (A(w - v))- = (Aw)-.

(4)

These conditions ensure that for a cone Cj o f the f o r m {x r Oj : A x = 0} the set o f all irreducible integral points w + and w- that lie in Cj define a Hilbert basis o f this cone. This yields

Remark 6.1.1: The set o f all irreducible vectors z with A z = 0 is the Graver test set for the families o f integer programs IP(b, c) with varying b e 2gm, c ~ Z n.

Proof" Let H be the G r a v e r test set for the family o f integer programs IP(b, c). F o r j e {+, _}n, l e t / / / d e n o t e the unique Hilbert basis/-/s for the pointed cone Cj = {x e O/: A x = 0}. I f v ~ Z n is irreducible, then v is an integral point in some cone Cj. Because it is irreducible, v cannot be written as the sum o f other integral vectors in C}. Therefore it is contained in //j. Conversely, if h ~ Hj for some index j, then h cannot be written as the sum o f two integral vectors f r o m Cj. However, if h were reducible by w e Z n, we would have that h = w + (h - w) where both h and (h - w) are integral elements in Cj. 9 The notion o f irreducibility can be used to formulate a stronger problem than that o f finding an augmentation vector. F o r this let ~- denote the set o f feasible points o f an integer program.

The Irreducible Augmentation Problem ( I R R - A UG) Given a vector c e 7Zn and a point X ~ e ~ - , find a point x new e ~ such that x aew - x ~ is irreducible and c r x new < cT~x~ or assert that no such x ~ew exists. F r o m R e m a r k 6.1.1 we k n o w that in order to solve the irreducible augmentation vector we must be able to c o m p u t e elements of the Hilbert basis o f some

24

R. Weismantel

cones. This is a difficult task. In fact it is already Jff~-complete to decide whether a vector is reducible.

Theorem 6.2 The Decomposition Problem ( D P ) : For a pointed cone C c Rn, and a vector g ~ C n 71~ it is sift-complete to decide whether g is not containd in the Hilbert basis H o f C.

Theorem 6.2 asserts the difficulty of deciding whether an augmentation vector is reducible. On the other hand, every augmentation vector can be decomposed into irreducible ones. In fact we can write every integral vector in a pointed cone as the non-negative integer combination of at most 2n - 2 irreducible vectors. This is mentioned below and usually refered to as an Integer Version o f Caratheodory's Theorem.

Theorem 6.3 Let C be a pointed cone in ~xn and H = { h i , . . . , hm} its Hilbert basis. Every integral point in C can be written as the non-negative integral combination o f at most 2n - 2 elements from H.

Theorem 6.2 and Theorem 6.3 have been shown by Seb6 [36]. Theorem 6.3 shows that every integral vector in a pointed cone is the non-negative integer combination of at most 2n - 2 vectors from the Hilbert basis. This is currently the best bound; it improves the bound given by Cook, Fonlupt & Schrijver [6] by 1, yet is still quite far from what many researchers conjecture to be true, namely: every integral vector in a pointed cone is the non-negative integer combination of at most n vectors of the Hilbert basis. For further results about Hilbert bases we cite Liu's dissertation [27], Schrijver [34] and Henk & Weismantel [22].

7

Augmentation Oracles for 0/1-Programs

In this section we show that from the computational complexity point of view the problems (OPT), (AUG) and (IRR-AUG) are equivalent in the special situation when ~ can be described as

=

{o,

b}.

Our presentation follows Schulz, Weismantel & Ziegler [35]. An indepependent proof of Theorem 7.2 can be found in Gr6tschel and Lov~isz [19]. For a

Test Sets of Integer Programs

25

thorough introduction to oracles and oracle-polynomial time algorithms we refer to Gr6tschel, Lov~sz, and Schrijver [20]. We use the method of bit-scaling (see [11]) in order to show that for a class of 0/1-integer programming problems the optimization problem can be solved by a polynomial number of calls of the augmentation oracle. To formulate the method of bit-scaling we have to represent data by binary numbers.

Definition 7.1 For ~ ~ IN and a given number K that is at least as big as the number of bits needed to encode ~, i. e., K > (~), we represent ~ as a K-bit binary number, adding leading zeroes if necessary. We denote by a(k) the number obtained by considering the k leading bits only. With k~ we refer to the k-th bit of a. Thus, ~(k) -~ (la,2 ~ , . . . k a) ~- ~-~k=l i O~2k-i, and ~(K) = ~.

Theorem 7.2 There exists an algorithm that solves (OPT) by (9(nlog C) calls of an oracle that solves (AUG), for C = max{lql :j = 1,..., n} + 1.

Proof." (a) We first show that we can assume that c > 0. With c e 2~n, we associate the vector ~ ~ INn with coefficients

cJ =

cj,

if cj_> O,

-q,

otherwise.

Then for x ~ ~ , the vector with coefficients

5cj =

xj,

if cj > 0 ,

1 - xj ,

otherwise,

belongs to ~- := {~ : x ~ ~-}. It follows that x ~ ~- is a minimal solution with respect to c if and only if ~ ~ ~ minimizes ~. Moreover, if t ~ ~n is an augmenting vector for x ~ J~, then the vector } with coefficients

~j_=_(tj, 1 -

if cj >_0,

tj,

otherwise.

is an augmenting vector for ~ ~ ~ .

26

R. Weismantel

(b) We assume that c > 0. For k = 1 , . . . , K we define a sequence of problems (Pk) as follows:

min

c(k)Tx

s.t.

xe~

Here, c(k) e N n denotes the vector obtained from c by restricting each component to the k leading bits, c(k) = ( c l ( k ) , . . . , cn(k)).

Algorithm 7.3 (Bit-scaling algorithm for solving ( O P T ) ) 1. 2. 3. 4. 5. 6. 7.

let x ~ be a feasible solution; k:=l; while k < K do solve (Pk) by iterated use of (AUG), with initial solution xk-1; let x k be the optimal solution of (Pk); k:=k+l; end.

Since (PK) coincides with the original optimization problem Algorithm 7.3 is correct. It remains to be shown that the number of calls of (AUG) in Step 4 to determine x k starting from x k-1 is polynomially bounded in the input size. The following calculation shows that in Step 4 for each problem (Pk) the oracle for (AUG) is called at most n times, because the objective function values of x k and x ~-1 with respect to c(k) distinguish by no more than n:

0 > c ( k ) r ( x k - x k-l) = 2c(k - 1)T(x k -- x t - l ) +k cT(x ~ -

x k-l)

~

-

l'l.

The inequality follows from the optimality o f x k-1 for (Pk-1), from kc e {0, 1}n, and from xk, x k-1 ~{0,1} n. (We define c(0) to be zero.) Note that 2c(k - 1 ) T ( x k -- X k - l ) >_ O, because x k-1 minimizes c(k - 1). 9 Next we show that, given x TM e ~- and c e Z n, one can find one irreducible augmentation vector via a polynomial number of calls of the optimization oracle. We proceed as follows: We first call (OPT) with the linear functional c. In case that x TM is optimal, there does not exist an irreducible augmentation vector. Otherwise, we determine a so-called maximum mean augmentation vector, see Definition 7.4. We show that among all maximum mean augmentation vectors there is one that is irreducible. Such a vector can be found by perturbation techniques.

Test Sets of Integer Programs

27

Definition 7.4." L e t c e 7Z.n and let x ~ e o~ be non-optimal. A vector t e Zn\{0} is called a maximum mean augmentation vector if cr t < 0 and t maximizes the ratio

:= IcTtl

It[1 The value I~* is called maximum mean augmentation value.

E x a m p l e 7.5." Consider the integer programming problem min2xl § x2 e {0, 1}. For the point x ~ = (1, 1) T, the m a x i m u m mean augmentation value is 2 = {. The vector ( - 1 , 0 ) r is the m a x i m u m mean augmentation vector. The vector ( - 1 , 1) T is the maximally augmenting vector.

The reason why we are interested in maximum mean augmentation vectors is the fact that among all maxmimum mean augmentation vectors there is always one that is irreducible. This follows from

x-cr x~h l = 11" > O. I f z := x - X~ such that [crix_xO~

Proposition 7.6." L e t x ~ ~176

is reducible by v, then cr--z= cr(z-O -- - - t f .

Ivh

Iz-vh --

A combination of binary-search and perturbation techniques shows that a maximum mean augmentation vector can be computed by a polynomial number of calls of the Optimization oracle.

Theorem 7. 7: There exists an algorithm that finds a m a x i m u m mean augmentation vector by (O(n + log(nC)) calls o f an oracle that solves (OPT).

We use Proposition 7.6 to compute an irreducible maximum mean augmentation vector: if z is reducible by v and w := z - v, the support of both v and w is properly contained in the support of z. We exploit this by appropriate perturbation of the objective function.

Theorem

7.8." There

exists

an

algorithm

that

solves

(IRR-AUG)

by

(P(n + log(nC)) calls o f an oracle that solves (OPT). Many of the techniques that one uses to show that the irreducible augmentation problem, the augmentation problem and the optimization for 0/1programs are equivalent in terms of computational complexity have been

28

R. Weismantel

invented for the minimum cost flow problem, see Ahuja, Magnanti & Odin [1]. The bit scaling algorithm 7.3 of Edmonds and Karp [11] has also been used by R6ck [31] and Gabow [14] for solving minimum cost flow and shortest path problems, respectively. Also, the technique that we use in order to determine the maximum mean augmentation value and a vector that attains it (Theorem 7.7) is quite similar to the one used for the minimum cost-to-time ratio cycle problem (see [1, pp. 150-152]). Using the "preprocessing algorithm" of Frank and Tardos [13] one can prove that the irreducible augmentation problem, the augmentation problem and the optimization problem for 0/1-programs are strongly polynomial time equivalent, see [35], [19].

8

Computing the Graver Test Set

In the previous section we have seen that from the point of computational complexity it is reasonable to study the irreducible augmentation problem, because - at least for 0/1 programs - it is not harder than the optimization problem and, given an irreducible augmentation oracle, we can optimize by calling it a polynomial number of times. In this section we present an algorithm for computing the set of all irreducible augmentation vectors for the family of integer programs IP(b, c) with varying b ~ ~,m and c ~ Z n. By Remark 6.1.1 this amounts to computing the Graver test set. Our presentation follows the paper Cornfiejols, Urbaniak, Weismantel & Wolsey [7]. The algorithm for computing the Graver test set for the family of integer programs 1P(b, c) works successively through the rows of A: for i = 0 until m - 1 we take, as input, the Graver test set G i for the family of integer programs rain cTx : A i x ~- b i, x ~ INn with vaying c e 7Z~ n and varying b i ~ Z i if i > 1 (b~ := 0). The symbol A i denotes the matrix that consists of the first i rows of A if i > 1. We use the convention that A ~ is the matrix consisting of one row with coefficients 0. The Graver test set Go is the set { _+e i : i = 1 , . . . , n}. Starting with input G : = G i we take repeatedly all the sums of two vectors in G, reduce each of these vectors as long as possible by the elements of G (with respect to the matrix Ai+l), and add all the reduced vectors that are different from the origin to the set G. When we terminate with this step, the set G will contain the Graver test set G i+1 . The following simple lemma is crucial to show that this approach works.

L e m m a 8.1." Let G i ~- ( t l , . . . , tk}. For every t ~ G i+l, there exist 21,... ,2k ~ IN such that t = ~ff=l 2JtJ, t+ -- ~ f = l 2J(tJ) + and t- = ~ = 1 2J(tJ) -.

Test Sets of Integer Programs

29

Proof." Let t e G i+l . There exists an index j such that t e Oj. Moreover, A~+lt = 0 implies that Air = 0. Hence t is an integral vector contained in the pointed cone Cj = {x e Oj : Aix = 0}. Because the Hilbert basis of C] is contained in G i, the claim follows. 9 By L e m m a 8.1, every element in G ~+1 is a nonnegative integer combination of elements in G i. This property can be used to compute G ;+1 starting with the set G;. In pseudo-programming language the algorithm for performing this task m a y look as follows:

Algorithm 8.2: Set Gold := 0 and G := G i. Let a denote the row of A of index i + 1. While Gotd r G repeat the following steps: Set Gold := G. F o r all pairs of vectors v, w e Gotd, let z := v + w: As long as there exists y e G such that y + < z + , y - < z - , (ary) + <_(aTz) +, (aTy) - <_ (arz) -, update z :-- z - y. I f z ~ 0, update G : = G u {z}.

Theorem 8.3: Algorithm 8.2 is finite. The set G that is returned by the algorithm contains G i+l. Theorem 8.3 shows that one can produce from the Graver test set G i a set of vectors G that contains the generating set G i+1. It should be clear that G i+1 is the subset of all elements g e G for which Ai+lg = 0. This subset can be obtained by processing through the elements of G one more time. We illustrate the performance of Algorithm 8.2 on a small example.

Example 8.4: Consider the family of integer programs in 3 variables min{cTx : ar x = b, x e IN3},

with fixed row vector a T = (1,2, 3) and varying b e 7/, c e 7/3. Algorithm 8.2 starts with the Graver test set Go that consists of all the unit vectors +__e1, +_e2, +_e3. Setting G : : GO, taking all sums of vectors of G gives rise after reduction to a new set G={+el,+__e 2, ___e3, + ( e 1 - e 2 ) , _+(e I - e 3 ) , + ( e 2 - e 3 ) } .

30

R. Weismantel

Note that for i = 1, 2, 3 the vectors + 2e i reduce to O. Accordingly _ (e 1 + e 2) can be reduced by +e 1, because ( a r ( e 1 + e 2 ) ) + = 3 > l = ( a r e l ) + and a r ( e 1 + e 2 ) ) - = 0 = ( a r e l ) -. Similar calculations show that, for i = 1,2, +_(ei + e 3) is reducible by +_ei and by -Fe3. Let Gold = G. With the set Gold we again perform the operations of taking all the sums of vectors of Gola and checking for reducibility. This yields after reduction an updated set G= Go~w{+(2e 1 -e2),+(2e

1 -e3), +(2e2-e3),

+(e 1 +e2-e3)}.

Denoting this set G by Gold, taking the sums of vectors • ( e l + [2e 1 - e3]), _ (e 1 + [ - 2 e 1 + e3]) and + ([e 2 - e 3] + [2e 2 - e3]) yields three additional vectors that are irreducible and added to G. All other sums of vectors of G can be reduced by G to O. Algorithm 8.2 terminates with the following set G = {-t-e 1, e 2, + e 3, _+ (e 1 - e2), -F (e 1 - e3), ___(e 2 - e3),

(5) ___(2e 1 - e2), _ (2e 1 - e3), __ (2e 2 -- e3), __ (e 1 q- e 2 _ e3), + (3e 1 -- e3), q- (3e 2 -- 2e3), + (e 1 d- e 3 -- 2e2)}.

The Graver test set for the family of knapsack problems investigated here reads {__+ (2e I - e2), __+(3e I - e3), __+(e 1 + e 3 _ 2e2), ___(3e 2 - 2e3), _+ (e 1 + e 2 _ e3)} .

Besides A l g o r i t h m 8.2 o f [7], there are o t h e r a l g o r i t h m s for c o m p u t i n g the G r a v e r test set o f a family o f integer p r o g r a m s , see, for instance, S c a r f [32], T h o m a s [40], Sturmfels & T h o m a s [38] C o n t i & T r a v e r s o [5], T h o m a s [40], U r b a n i a k , W e i s m a n t e l & Ziegler [43], T h o m a s & W e i s m a n t e l [42], M o u l i n e t & Pottier [29], H o s ~ t e n & Sturmfels [21] or Pottier [30].

9

Knapsack Problems with Few Coefficients

W e h a v e seen in the p r e v i o u s section t h a t one c a n - in principle - c o m p u t e the G r a v e r test set for a f a m i l y o f integer p r o g r a m s o f the f o r m IP(b, c) w h e r e b a n d c vary, T h e G r a v e r test set contains, for each o r t h a n t in Rn, a H i l b e r t basis

Test Sets of Integer Programs

31

of the cone Cj, see Section 2. It is however clear that Algorithm 8.2 is far from being able to compute test sets for arbitrary families of integer programs, even in low dimension. In this section we study the family of knapsack problems in 3 coefficients. For this family one can compute, as we will see, a subset of the Graver test set that is polynomial in the encoding length of the coefficients of the knapsack problem. This subset of vectors serves as the basis to solve the augmentation problem for the associated family of programs in polynomial time. The family of knapsack problems that we consider here is of the following form m a x c~xx + c2x2 + c3x3 : / t X l -.l- ]l,x2 -.[- o-x3 = b, X l , X 2 , X 3 ~ I N .

(6)

The numbers b, cl, c2, c3 e N vary. /t,2 and a are natural numbers such that gcd(/t, 2) = gcd(/t, ,~) = gcd(~, 2) = 1. when investigating the Graver test set for this family of knapsack problems, we may restrict, without loss of generality, our attention to the Hilbert basis of the cone C1 := {xl, x2, x3 > 0 :/txl + 2x2 = ax3}.

Definition 9.1: We define functions f : N ~ N and g : N ---, N as follows: for x2 ~ N , f ( x 2 ) is the minimum natural number Xl such that there exists a number x3 ~ N \ { 0 } with /tXl + 2X2 = aX3. for X 2 ~ N,g(X2) is the minimum natural number x3 such that there exists a number xl e N \ { 0 } with IZXl + 2x2 = crx3.

Example 9.2: Let Cl := {Xl,X2,X3 >~O : 5Xl q- 7x2 : 9x3}. f ( 0 ) = 9 , since 9 x 5 + 7 x 0 = 9 • 5. Accordinoly 9(0) = 5. I f x2 = 1, then in order to determine f ( 1 ) we need to find the smallest natural number xl such that the system has a solution in natural numbers. We obtain that f ( 1 ) = 4. (Note that 4x5+1•215 Accordingly, 9 ( 1 ) = 3 . In fact, for a given natural number x2 e N , the set o f all integral values o f Xl and x3 for which the equation 5xl + 7x2 = 9x3 is solvable is given by the set o f all vectors o f the f o r m {xl,x3 ~ 71 : there exists v ~ Z : xl = f ( x 2 ) -F va, x3 = g(x2) -F v/t}. In this example the set o f all integral values o f xl and x3 for which the equation 5xt + 0 x 7 = 9x3 is solvable is described by the set

{Xl = v • 9,x3 = v x 5, v e Z} . The black points in Figure 9 correspond to the function values that f attains between 0 and a = 9.

32

R. Weismantel Formalizing this example shows Proposition 9.3.

Proposition 9.3: (i)f(0) = o',f(o') = 0; (ii) IfO < f ( x ) + f ( y ) < ~, then f ( x + y) = f ( x ) + f ( y ) ; (iii) The set of all integral values of xl and x3 for which the equation IlXl + 2x2 = o-x3 is solvable for a fixed number x2 ~ N is the set {xl, x3 ~ Z : there exists v e Z : Xl = f ( x 2 ) + va, x3 = g(x2) + vl~}. The object of our investigations here is an effective algorithm for computing the Hilbert basis of the cone C1. It turns out that the key for this algorithm is a decomposition property of the function f that we study now. More precisely, we want to demonstrate that there exists a number r < log2(a) and 3z natural numbers d l , . . . , d ~ , g l , . . . ,g~ and p l , . . . ,p~ such that we can decompose, for every x ~ N withpi < x < pi+l, the function v a l u e f ( x ) in the following form:

Property 9.4: For every x ~ IN with Pi <- x < Pi+l let l = m a x t ~ { t g i < x - p i } and v = maxt~N{tpi <_x - lgi}. Setting y := x - vpi - lgi, we have that f ( x ) = f ( y ) + vf(pi) + ldi if y r 0 and f ( x ) = vf(pi) + ldi, otherwise.

Example 9.5: We continue with Example 9.2. Figure 9 illustrates that a Hilbert basis H1 of the cone C1 is composed of the following set of vectors Ha = { ( f ( x ) , x , - 9 ( x ) ) : x ~ {0, 1 , 3 , 5 , 7 , 9 } } .

This example already demonstrates that the Hilbert basis may be of the order a/2. This number is not polynomial in the encoding length of the original knapsack problem. On the other hand the piecewise linear function that connects two consecutive points in the Hilbert basis (see Figure 2) shows that the number of bending points on the piecewise linear function is equal to 3. The piecewise linear function is composed of 2 linear functions with slope vectors (gl,dl) and (g2, d2). The idea to find a decomposition of the function f according to (9.4) is to construct just the bending points ( P l , f (Pl ) ), . . . , (P~,f (P~)) of the piecewise linear function that connects the points of the Hilbert basis H1 (without inspecting all the elements of Hi). I f we store additionally the slope vectors (gl,dl) and (91, d2), then this information allows us to reconstruct the entire Hilbert basis 111. It also enables us to solve the augmenation problem for the family of knapsack problems 6. To see how one can decompose the function values o f f according to (9.4) consider, for instance, x = 3. Then x = 2 + 1 = p 2 q-g2- As f ( 3 ) = 3 = 4 - 1 = f ( p 2 ) + d2, the decomposition formula applies for x = 3. I f x = 8, we obtain

Test Sets of Integer Programs

33

9~

i-

8 7. 6 5 4

\ . ~ ~ = . ,

~

3 2 I 0 0=Pl

I=p2

2

3

4

5

6

7

8

9=p3

Fig. 2.

l = m a x t ~ N { t g 2 _< x - P 2 = 7} = 3 and v = maxtEN{tp2 g x -- ld2 = 2} = 2. Setting y := x - vp2 - 1 9 2 = 8 - 1 6 = O, we have that 5 = f ( x ) = 8 - 3 =

vf(p2) + ld2. The natural numbers d l , . . . , dr, g l , . . . , gr and P l , . . . ,P~ are linked through the following recursive algorithm. Algorithm 9.6 Recursion f o r m u l a s

Pl :-- 0. g l : = 1. d I :=f(1)-f(0). Vl : = O.

For i >_ 2 and pi <_ a define:

li : = m J n l e N { f ( P i - l ) + ldi-1 < 0}. Pi : = P i - 1 + (li -- 1)gi-1vi := maxo~N{(v + 1 ) f ( p i ) + di-1 < 0}. gi : = (Vi + 1)pi + gi-1. di :---- (vi + 1 ) f ( p i ) + di-1. An analysis of the Recursion formula 9.6 shows in particular that with each incrementation of the index i we have that Pi >- 2pi-1- This yields that z < log2(a). We show first that the f u n c t i o n f can be decomposed as illustrated in Example 9.5.

34

R. Weismantel

L e m m a 9.7: di < 0 a n d lzdi + 2gi = 0 m o d crf o r all i = 1 , . . . ,z.

L e m m a 9.8: For all i = 2 , . . . , z the following relations hold. (a) f ( p i ) = f ( p i - 1 ) + (li - 1)di_l. (b) pi >- 2pi-1. (c) L e t xeN,pi<_x
C1 : = { X l , X 2 , X 3 ~ 0 : flXl -[-2x2 - fix3 ~-- 0}

is c o m p o s e d o f the following set o f vectors

Ha = { ( f ( x ) , x , - g ( x ) )

: x=pi+

ldi : i = 1 , . . . , z , l = 0 , . . . , l i -

1}.

T h e o r e m 9 . 9 : H 1 is a Hilbert basis o f C 1

Proof" By the definition o f f and g, every integral point z in Ca that is not the sum o f two other integral vectors in C1 is o f the f o r m z = ( f ( x ) , x , - g ( x ) ) where x s N. I f x > a = p,, then z = (0, a, - 2 ) + ( f ( x - cr), x - a, - g ( x - a)) where both ( 0 , a , - 2 ) and ( f ( x - a ) , x - a , - g ( x - a ) ) are integral points in C1. Otherwise, there exists an index i N ~: -- 1 such that Pi N x < Pi+a. Let l = maxt~N{tOi < x - P i } and v = maxt~r~{tpi < x - loi}. Setting y : = x - vpi - lgi, we k n o w f r o m L e m m a 9.8 that f ( x ) = f ( y ) + v f ( p i ) + ldi, if y r 0. Otherwise, f (x) = v f ( p i ) +ldi. Moreover, l <_ li - 1 a n d v ___v - i + 1. I f y = 0, then z = ((v - 1 ) f ( p i ) , (v - 1 ) p i , - O ( ( v - 1)p/)) + ( f ( P i ) + ldi,pi + 1 9 i , - g ( P i + lgi)) where (v - 1 ) f ( p i ) , (v - 1 ) p i , - g ( ( v - 1)pi)) and ( f ( P i ) + ldi,pi + loi, - g ( P i + Igi)) are both integral points in Ca by L e m m a 9.7 and L e m m a 9.8. This is a contradiction that z is not the sum o f integral vectors in C1.

Test Sets of Integer Programs

35

I f y ~ 0, we obtain that

z = ((v - 1)f(pi), (v - 1)pi,-9((v - 1)pi))+ (f(Pi) + ldi,pi + loi,-9(Pi + lgi)) + ( f ( y ) , Y , - 9 ( Y ) ) . By Lemmas 9.7 and L e m m a 9.8 ( v - 1 ) f ( p i ) , ( v - 1 ) p i , - O ( ( v - 1 ) p i ) ) , (f(pi) + ldi,pi + 19i, -9(Pi + 19i)) and ( f ( y ) , y , - 9 ( Y ) ) are integral points in C1. This yields also a contradiction that z is not the sum of integral vectors in C1. 9 One can apply Theorem 9.9 and Lemmas 9.7 and 9.8 to solve the augmentation problem for the family of knapsack problems in 3 coefficients in polynomial time. F o r a knapsack problem of the form (6), let z ~ N 3 be a feasible point. In order to check whether z is optimal we need to decide whether, in any of the 8 orthants, there exists an element in the Hilbert basis of the cone Cj, see Theorem 2. W.l.o.g. we m a y restrict our attention to the Hilbert basis elements of the cone C1 := {xl,x2,x3 > 0 : ]/Xl q-/~X2 z O'X3}. First we run an algorithm to compute the arrays p, d, l, v of Recursion 9.6. As the length of each of these arrays is lo02(~), this can be implemented in polynomial time. Next we initialize h = ( f ( p l ) , p l , - 9 ( P l ) ) and procced for i = 1 up to z as follows: (a) Check whether h is an augmenting vector such that z + h is feasible for the particular knapsack problem. I f this is the case, then STOP. (b) Check whether crdi > 0. If not, Goto Step (c). (c) Use binary search to assert whether there exists an augmenting vector of the form h + ldi with l E { 1 , . . . , li - 1 } that is applicable at z. I f we have found such a vector, then STOP. (d) Set i := i + 1 and h := (f(pi),pi, -9(Pi)). Goto Step (a). Elementary considerations show that this algorithm works correct and yield

Theorem 9.10: The augmentation problem for the family of knapsack problems with 3 coefficients can be solved in time O(log2(tr) ). For the family of knapsack problems that we investigated here we have shown that there is an efficient way of storing a subset of the Graver test set. The cardinality of this subset is polynomial in the encoding length of the coefficients of the knapsack problem. Moreover, one can easily reconstruct the entire Graver test set from this small subset. An extension of this sort to higher

36

R. Weismantel

dimensions would be desirable to support the relevance of the study of test sets in integer programming.

Acknowledoement: I am very grateful to Alexander Martin and, in particular, Christoph Helmberg for the careful proof reading and the corrections of earlier versions of this paper. I needed their suggestions to come up with the current version.

References

[1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network flows: Theory, algorithms, and applications. Prentice Hall, Englewood Cliffs NJ [2] B~ir~inyI, Howe R, Scarf H (1993) The complex of maximal lattice free simpfices, Proc. of the IPCO conference, Erice, Italy, pp. 1-10 [3] Becket T, Weispfenning V (1993) Gr6bner bases: A computational approach to commutative algebra. Springer Verlag, New York [4] Buchberger B (1985) Grrbner bases: An algorithmic method in polynomial ideal theory. In: Bose NK (ed.) Multidimensional systems theory, D. Reidel Publications, pp. 184-232 [5] Conti P, Traverso C (1991) Buchberger algorithm and integer programming. Proceedings AAECC-9 (New Orleans), Springer LNCS 539, pp. 130-139 [6] Cook W, Fonlupt J, Schrijver A (1986) An integer analogue of Caratheodory's theorem. J. Comb. Theory (B) 40: 63-70 [7] Cornuejols G, Urbaniak R, Weismantel R, Wolsey L (1997) Decomposition of integer programs and of generating sets. LNCS 1284, Burkard R, Woeginger G (eds.), Springer, pp. 92103 [8] van der Corput JG (1931) Ober Systeme von linear-homogenen Gleichungen und Ungleichungen. Proceedings Koninklijke Akademie van Weteuschappen te Amsterdam 34:368-371 [9] Cox DA, Little JB, O'Shea D (1992) Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra. Springer-Verlag, New York [10] Diaconis P, Graham RL, Sturrnfels B (1995) Primitive partition identities. Working Paper [11] Edmonds J, Karp RM (1972) Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the Association for Computing Machinery 19:248-264 [12] Faig~e U (1987) Matroids in combinatorial optimization. In: White N Combinatorial geometries, Cambridge University Press, Cambridge [13] Frank A, Tardos E (1987) An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica 7:49-65 [14] Gabow HN (1985) Scaling algorithms for network problems. Journal of Computer and System Sciences 31:148-!68 [15] Giles FR, Pulleyblank WR (1979) Total dual integrality and integer polyhedra. Lineare Algebra Appl. 25:191-196 [16] Gordan P (1873) l)ber die Aufl6sung linearer Gleichungen mit reellen Coefficienten. Math. Ann. 6: 23-28 [17] Graver JE (1975) On the foundations of linear and integer programming I. Mathematical Programming 8 : 207-226 [18] Gritzmann P, Wills JM (1993) Lattice points. In: Gruber PM, Wills JM (eds.) Handbook of convex geometry, Volume B, North-Holland, Amsterdam, pp. 765-798 [19] Gr6tschel M, Lov~isz L (1995) Combinatorial optimization. In: Graham R, Gr6tschel M, Lov~isz L (eds.) Handbook of combinatorics, North-Holland, Amsterdam

Test Sets of Integer Programs

37

[20] Gr6tsehel M, Lov~sz L, Schrijver A (1988) Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin [21] Hosten S, Sturmfels B (1995) GRIN: An implementation of Gr6bner bases for integer programming. In: Balas E, Clausen J (eds.) Integer programming and combinatorial optimization, Lecture notes in Computer Science 920, Springer-Verlag, Berlin, pp. 267-276 [22] Henk M, Weismantel R (1996) On Hilbert bases of polyhedral cones. Konrad-Zuse-Zentrum fiir Informationstechnik Berlin, Preprint SC 96-12 [23] Kannan R (1987) Minkowski's convex body theorem and integer programming. Math. Oper. Res. 12:415-440 [24] Kannan R, Lowisz L (1988) Covering minima and lattice point free convx bodies. Ann. Math. 128 : 577-602 [25] Kannan R, Lovhsz L, Scarf H (1990) The shapes of polyhedra. Math. Oper. Res. 15:364-380 [26] Lagarias JC (1995) Point lattices. In: Graham R, Gr6tschel M, Lov~sz L (eds.) Handbook of combinatorics, North-Holland, Amsterdam [27] Liu J (1991) Hilbert bases with the carath~odory property. PhD. Dissertation, Comell University [28] Lov~tsz L (1989) Geometry of numbers and integer programming. In: Iri M, Tanabe K (eds.) Proc. of the 13th International Symposium on Mathematical Programming, Mathematical Programming: 177-201 [29] Moulinet C, Pottier L Gr6bner bases of toric ideals: Properties, algorithms and applications. Preprint INRIA Sophia Antipolis [30] Pottier L (1991) Minimal solutions of linear diophantine systems: bounds and algorithms. Proceedings RTA (Como), Springer Verlag, LNCS 488 [31] R6ck H (1980) Scaling techniques for minimal cost network flows. Discrete Structures and Algorithms, Carl Hanser, Miinchen, pp. 181-191 [32] Scarf HE (1981) Production sets with indivisibilities, Part I: Generalities. Econometrica 49:132 [33] Scarf HE (1986) Neighborhood systems for production sets with indivisibilities. Econometrica 54: 507-532 [34] Schrijver A (1986) Theory of linear and integer programming. Wiley Chichester [35] Schulz A, Weismantel R, Ziegler G (1995) 0/1 integer programming: Optimization and augmentation are equivalent. In: Spirakis P (ed.) Proceedings of the European Symposium on Algorithms, Lecture Notes in Computer Science, Springer-Verlag [36] Seb6 A (1990) Hilbert bases, Caratheodory's Theorem and combinatorial optimization. In: Proc. of the IPCO conference, Waterloo, Canada, pp. 431-455 [37] Sturmfels B (1996) Gr6bner bases and convex polytopes. American Mathematical Society, Providence [38] Sturmfels B, Thomas R (1994) Variation of cost functions in integer programming. Manuscript (1994), Mathematical Programming, to appear [39] Sturmfels B, Weismantel R, Ziegler G (1995) Gr6bner bases of lattices, comer polyhedra and integer programming. Beitr" age zur Geometric und Algebra 36:281-298 [40] Thomas R (1995) A geometric Buchberger algorithm for integer programming. Math. Oper. Res. 20, 4: 864-884 [41] Thomas R (1994) Gr6bner basis methods for integer programming. Phi). Dissertation, Comell University [42] Thomas R, Weismantel R (1995) Truncated Gr6bner bases for integer programming. Applicable Algebra in Engineering, Communication and Computing 8, 4:241-257 [43] Urbaniak R, Weismantel R, Ziegler G (1994) A variant of Buchberger's algorighm for integer programming. SIAM Journal on Discrete Mathematics 1, 10:96-108 [44] Welsh DJA (1976) Matroid theory. Academic Press London

Received: February 1997