Chapter 7 Algebraic geometry and integer optimization 7.1. 7.2. 7.3. 7.4. 7.5. 7.6. 7.7. 7.8. Contents Background from algebraic geometry Applications to binary optimization Grobner bases for integer optimization Applications of real algebraic geometry Generating functions for integer points in polyhedra Summary Exercises Notes and sources 4 Chap. 7 Algebraic geometry and integer optimization In this chapter, we introduce several approaches to integer optimization that have their roots in algebraic geometry. While the methods we discuss in this chapter have not yet resulted in practical algorithms, they are based on deep and elegant ideas from a very active eld of mathematics that could potentially lead to ecient algorithms in the future. To make the chapter self-contained we discuss the fundamental concepts from algebraic geometry we will use throughout the chapter. Applying some classical ideas from algebraic geometry we derive a Farkas lemma for integer optimization, and algorithms for both binary and integer optimization. We further introduce some ideas from real algebraic geometry and the problem of moments and derive a convergent (and, in the case of binary optimization, nite) sequence of semidenite relaxations for integer nonlinear optimization. Finally, we introduce a powerful idea of decomposition of cones that leads to a polynomial time algorithm for counting the number of integer points in a polyhedron in a xed dimension. 7.1 Background from algebraic geometry The basic algebraic objects in this chapter are polynomials over complex or real numbers. Denition 7.1 (Polynomials) (a) A monomial in variables x = (x1 : : : xn) is a product of the form x� = x1 1 xnn where � = (1 : : : n) Z+n . (b) A polynomial is an expression of the form 0 0 2 f (x) = X � S f� x� 2 with S Z+n , S nite, and f� k (k = R or k = C ) for all � S. The set of all polynomials in x1 : : : xn with coecients in k = R or k = C is denoted by kx1 : : : xn]. 2 2 Throughout the chapter we will use k to mean either R or C . We will indicate explicitly when specic results only hold for k = C . While in one dimension the monomials are naturally ordered by their degree, i.e., xm > xm 1 > > x > 1, in many dimensions one can dene ; Sec. 7.1 5 Background from algebraic geometry several orders. Denition 7.2 A monomial order on kx1 : : : xn] is any relation > on Zn+, or equivalently, any relation on the set of monomials x� , � Zn+, 2 satisfying: (a) > is a total order on Zn+. (b) If � > � and � Zn+, then � + � > � + � . (c) Any nonempty subset of Zn+ has a smallest element under >. 2 Important examples of monomial orders include: (a) The lexicographic order. For every � � Zn+, we say � >lex � (or x� >lex x� ) if, in the vector dierence � � Zn, the leftmost nonzero entry is positive. For example � = (1 2 0) >lex (1 1 3) = � , since � � = (0 1 3) . (b) The graded lex order. For every � � Zn+, we say � >grlex � (or x� >grlex x� ) if, 2 ; 2 0 0 ; ; 0 2 �= j j n X i=1 i > n X i=1 i = � or � = � and � >lex � : j j j j j j In other words, grlex orders by total degree rst and breaks ties using the lex order. For example, � = (1 2 3) >grlex (3 2 0) = � since � =6>5= �: 0 j j j 0 j (c) The graded reverse lex order. For every � � Zn+, we say � >grevlex � (or x� >grevlex x� ) if, 2 �= j j n X i=1 i > n X i=1 i = � or � = � and j j j j j j in � � Zn the right-most nonzero entry is negative. For example, � = (1 5 2) >grevlex (2 3 3) = � , since � = � = 8 and � � = ( 1 2 1) : ; 2 0 ; ; 0 j j j j ; 0 (d) The vector induced order. We consider a vector c Zn+, and for every � � Zn+, we say � >c � (or x� >c x� ) if, c � > c � or c � = c � and � >lex �: Note that the requirement c 0 is important, since otherwise, Part 2 0 0 2 0 0 (c) in Denition 7.2 is violated. Example 7.12 Under di 2 3 2 erent monomial orders the polynomial f = 6x1 x22 x3 + 7x3 ; 5x1 + 4x1 x3 is written as follows: 6 Chap. 7 Algebraic geometry and integer optimization (a) Under the lex order f = ;5x31 + 4x21 x23 + 6x1 x22 x3 + 7x23 : (b) Under the grlex order f = 4x21 x23 + 6x1 x22 x3 ; 5x31 + 7x23 : (c) Under the grevlex order f = 6x1 x22 x3 + 4x21 x23 ; 5x31 + 7x23 : (d) Under the vector induced order with c = (3 2 2) 0 f = 4x21 x23 ; 5x31 + 6x1 x22 x3 + 7x23 : Note that the eld of complex numbers k = C is algebraically closed, since every nonconstant polynomial has a root in C . The eld k = R, however, is not algebraically closed, since there do not exist any real roots of the equation x2 + 1 = 0. We next introduce the concept of ideals and ane varieties that play a central role in algebraic geometry. Denition 7.3 (Ideals and A ne Varieties) (a) An ideal is a subset I kx1 : : : xn] satisfying: (i) 0 I. (ii) If f g I, then f + g I. (iii) If f I and h kx1 : : : xn], then hf I. (b) Given an ideal I, we dene an a ne variety V (I) 2 2 2 2 2 2 V (I) = x kn f (x) = 0 for all f I : f 2 j 2 g A key property related to ideals is that every ideal is nitely generated. Theorem 7.1 (The Hilbert Basis Theorem) Every ideal I kx1 : : ::xn] is nitely generated, i.e., there exist g1 : : : gt I such that 2 (X t ) I= hi gi h1 : : : ht kx1 : : : xn] : i=1 2 We write I = g1 : : : gt . h i Sec. 7.1 7 Background from algebraic geometry Theorem 7.1 implies that if I = g1 : : : gt , then V (I) = x kn gi (x) = 0 for all i = 1 : : : t : For polynomials in one variable, it turns out that any ideal in kx] can be generated by a single polynomial, i.e., I = f for some polynomial f kx]. Then V (I) is the set of roots of f . Since every nonconstant polynomial in C x] has a root, the only way that V (I) = would be for f to be a nonzero constant. In this case, 1=f C , and thus 1 = (1=f ) f I, which implies that g 1 = g I for all g C x]. This shows that I = C x] is the only ideal of C x] that represents the empty variety. It turns out that the same property holds in multiple variables, that is, in any polynomial ring, algebraic closure of k is enough to guarantee that the only ideal which represents the empty variety is the entire polynomial ring itself. This is the Weak Nullstellensatz, which is the basis of one of the most important mathematical results of the late nineteenth century, Hilbert's Nullstellensatz. h f 2 i j g h i 2 2 2 2 2 Theorem 7.2 (The Weak Nullstellensatz) Let I C x1 : : : xn] be an ideal satisfying V (I) = . Then I = C x1 : : : xn]. We use I(V ) to denote the ideal that contains all polynomials that vanish on a given variety V . In Exercise 7.2 we show that for a variety V , it holds that if f m I(V ), for some integer m 1, then f I(V ). Thus, an ideal consisting of all polynomials which vanish on a variety V has the property that if some power of a polynomial belongs to the ideal, then the polynomial itself must belong to the ideal. This leads to the denition. 2 2 Denition 7.4 An ideal I is radical if f m I for some integer m 1 2 implies that f I. 2 The previous discussion implies that I(V ) is a radical ideal. Another powerful theorem is as follows. Theorem 7.3 (Hilbert's Nullstellensatz) The polynomials f f1 : : : fs C x1 : : : xn] satisfy f I(V (f1 : : : fs)) if and only if there exists an integer m 1 such that f m f1 : : : fs . 2 2 2 h i Theorem 7.3 says that the only way that an arbitrary ideal I can fail to be the ideal of all polynomials vanishing on V (I) is for I to contain powers 8 Chap. 7 Algebraic geometry and integer optimization f m of polynomials which are not in I. This leads to the denition. Denition 7.5 Let I p denoted by I , is the set kx1 : : : xn] be an ideal. The radical of I, f f m I for some integer m 1 : f j 2 g p It is a simple observation that an ideal is radical if and only if I = I . It turns out (Exercise 7.3) that if I is an ideal in kx1 : : : xn], then I is an ideal in kx1 : : : xn] containing I. Furthermore, I is a radical ideal. Theorem 7.2 leads to a Farkas type lemma for a system of polynomial equations over C x1 : : : xn]: p p Theorem 7.4 Let g1 : : : gt C x1 : : : xn] be polynomials. Then, the system gi (x) = 0 i = 1 ::: t (7.1) 2 has no solution in C n if and only if there exist polynomials h1 : : : ht : : : xn] such that t X hi gi = 1: (7.2) 2 C x1 i=1 Proof. We let I = g1 : : : gt and V (I) = x C n gi (x) = 0 for all i = 1 : : : t : If Eq. (7.1) does not have a solution, then V (I) = . Theorem 7.2 implies that I = C x1 : : : xn]. Since the number 1 is a member of kx1 : : : xn] and since I is generatedPbyt g1 : : : gt, there exist polynomials h1 : : : ht C x1 : : : xn] such that i=1 hi gi = 1 i.e., Eq. (7.2) has a solution. Conversely, suppose that Eq. (7.2) has a solution. We assume, for the purposePoft deriving a contradiction, that Eq. (7.1) has a solution x0 . Then, 1 = i=1 hi (x0 )gi (x0) = 0 a contradiction. h i f 2 j g 2 Theorem 7.4 asserts that a certicate of the infeasibility of the system of polynomial equations (7.1) is the set of polynomials h1 : : : ht. In this sense, Theorem 7.4 can be considered an extension of the Farkas lemma to a system of polynomial equations. In order to compute the polynomials h1 : : : ht, we need to be able to address the question of deciding whether a given polynomial f belongs to the ideal I = g1 : : : gt . Specically, Theorem 7.4 asks whether the polynomial 1 is in I. In order to develop h i Sec. 7.1 9 Background from algebraic geometry methods to address this question we need some additional denitions. Denition Given a monomial order > and a polynomial f (x) = P f� x� 7.6 we dene � S (a) The multidegree of f is multideg(f ) = max � � S 2 2 where the maximum is taken over the given order > : (b) The leading coecient of f is LC(f ) = fmultideg(f ) : (c) The leading monomial of f LM(f ) = xmultideg(f ) : (d) The leading term of f LT(f ) = LC(f ) LM(f ): To illustrate for f = 5x31 + 4x21x23 + 6x1x22 x3 + 7x32 and the lex order, ; multideg(f ) = (3 0 0) LC(f ) = 5 LM(f ) = x31 LT(f ) = 5x31: 0 ; ; Given a monomial order, we can dene the division of a polynomial f (x) by a polynomial g(x) as illustrated in Example 7.2. A natural idea to decide if f I = g1 : : : gt is then to start dividing f by g1 : : : gt to obtain f = h1 g1 + + htgt + r and to say that f I if the remainder r = 0: Note that in multivariate polynomials the remainder r depends on the order in which we perform the division. While r = 0 implies that f I, r = 0 does not necessarily imply that f = I as the next example illustrates. 2 h i 2 2 6 2 Example 7.2 Let g1 = xy + 1, g2 = y2 ; 1 and consider the lex order. We want to determine whether f = xy2 ; x 2 hg1 g2 i. If we divide f by g1 rst and then by g2 we obtain xy2 ; x = y(xy + 1) + 0(y2 ; 1) + (;x ; y): If, however, we divide f by g2 rst and then by g1 we obtain xy2 ; x = x(y2 ; 1) + 0(xy + 1) + 0 which leads to the conclusion that f 2 hg1 g2 i. 10 Chap. 7 Algebraic geometry and integer optimization This observation motivates the following denition. Denition 7.7 Let G = g1 : : : gt be a set of polynomials and I = g1 : : : gt . G is called a Grobner basis for the ideal I if f I if and f h g i 2 only if the remainder of the division of f by the polynomials in G is always zero, independent of the order in which we perform the division. Given an ordered collection G of polynomials and a polynomial f, we can dene the remainder R(f G) of the division of f by the polynomials in G in the order specied. If G, however, is a Grobner basis the remainder R(f G) is independent of the order we perform the divisions. Thus, given a Grobner basis G of an ideal I we can decide whether f I by successive divisions. It is not a priori clear that a Grobner basis exists for an arbitrary ideal. The following algorithm, however, constructs such a basis. 2 Algorithm 7.1 The Buchberger algorithm Input: A set F = f1 : : : fs of polynomials in kx1 : : : xn] and a f g monomial order. Output: A Grobner basis G = g1 : : : gt for I = f1 : : : fs . Algorithm: 1. (Initialization) Let G := (f1 : : : fs ) be the ordered tuple obtained from F. 2. For each p q G (a) Let � = multideg(p), � = multideg(q), i = max(i i), and � = (1 : : : n ) . (b) Compute the polynomial f g h i 2 0 x p x q: S(p q) = LT(p) LT(q) � ; � (c) Compute the remainder r of the division of S(p q) with the ordered set G, denoted as R(S(p q) G) using the given monomial order. (d) If r = 0, then G := (G r) goto Step 2 If r = 0 for all p q G, then goto Step 3. 3. Output G. 6 2 We remark that dierent monomial orders lead to dierent Grobner bases, since the monomial order aects the outcome of the division of polynomials. Sec. 7.1 11 Background from algebraic geometry Example 7.3 3 We would like to nd the Grobner basis for I = hf1 f2 i with f1 = x ; 2xy and f2 = x2 y ; 2y2 + x and the grlex order. We compute S (f1 f2 ) as follows: multideg(f1 ) = (3 0) multideg(f2 ) = (2 1) , and thus � = (3 1) . 0 0 0 Thus, 3 3 S (f1 f2 ) = xx3y (x3 ; 2xy) ; xx2 yy (x2 y ; 2y2 + x) = ;x2 : Moreover, R(S (f1 f2 ) ff1 f2 g) = f3 = ;x2 , and G = (f1 f2 f3 ). We continue and obtain S (f1 f3 ) = (x3 ; 2xy) ; (;x)(;x2) = ;2xy R(S (f1 f3 ) ff1 f2 f3g) = f4 = ;2xy: We add f4 to G which now becomes G = (f1 f2 f3 f4 ). We continue and nd S (f1 f4 ) = y(x3 ; 2xy) ; (;1=2)x2 (;2xy) = ;2xy2 = yf4 R(S (f1 f4 ) G) = 0: Moreover, S (f2 f3 ) = (x2 y ; 2y2 + x) ; (;y)(;x2 ) = ;2y2 + x R(S (f2 f3 ) G) = f5 = ;2y2 + x: We add f5 to G, and obtain G = (f1 : : : f5 ), and we check that R(S (fi fj ) G) = 0 for all i j = 1 : : : 5: Thus, a Grobner basis is fx3 ; 2xy x2 y ; 2y2 + x ;x2 ;2xy ;2y2 + xg: The following theorem shows that Grobner bases are correctly computed by Algorithm 7.1. Theorem 7.5 Algorithm 7.1 terminates in nite time. It computes a Grobner basis for the ideal I = f1 : : : fs with respect to the given monomial order. h i It turns out that Grobner bases computed by Algorithm 7.1 are often bigger than necessary. We can eliminate some of its elements by using the observation that if p G such that LT(p) LT(G p ) , then G p is also a Grobner basis. 2 Example 7.4 2 h nf g i Continuing Example 7.3, we observe that LT(f1 ) = x3 = ;x LT(f3 ) and thus we can delete f1 from the Grobner basis. Also, LT(f2 ) = x2 y = ;(1=2)x LT(f4 ) and we can eliminate f2 . nf g 12 Chap. 7 Algebraic geometry and integer optimization We next dene the notion of a minimal Grobner basis. Denition 7.8 A minimal Grobner basis for a polynomial ideal I is a Grobner basis G for I such that (a) LC(p) = 1 for all p G. (b) For all p G, LT(p) = LT(G p ) : 2 2 2 h nf g i Example 7.5 Continuing Example 7.4, we conclude that fx2 xy y2 ; (1=2)xg is a minimal Grobner basis. A given ideal, however, might have many minimal Grobner bases. In the example, it is easy to check that G = fx2 + xy xy y2 ; (1=2)xg for 2 R being any constant is also a minimal Grobner basis. This leads to the denition. Denition 7.9 A reduced Grobner basis for a polynomial ideal I is a Grobner basis G for I such that (a) LC(p) = 1 for all p G. (b) For all p G, no monomial of p lies in LT(G 2 2 h p ): nf g i In Example 7.5, the only reduced Grobner basis is G0 corresponding to = 0. In fact, we have the following theorem. Theorem 7.6 For a given monomial order, a polynomial ideal has a unique reduced Grobner basis. Many computer algebra systems have implemented Algorithm 7.1 to compute the reduced Grobner basis for a given monomial order. However, Algorithm 7.1 has two diculties: First, it nds a lot of elements in the basis that might be deleted later as they do not belong to the reduced Grobner basis. Furthermore, because of the divisions with potentially large numbers, its numerical stability is problematic. Nevertheless, Algorithm 7.1 leads to a constructive proof of Theorem 7.1 and forms the algorithmic foundation for several applications of algebraic geometry including those in integer optimization we outline in Sections 7.2 and 7.3. We will also utilize the notion of an elimination ideal. Denition 7.10 Given I = f1 : : : fs kx1 : : : xn], the lth elimination ideal Il is dened as Il = I kxl+1 : : : xn]. h i \ Sec. 7.2 13 Applications to binary optimization A connection of elimination ideals and Grobner bases with the lex order is given by: Theorem 7.7 Let I kx1 : : : xn] be an ideal and let G be a Grobner basis of I with respect to lex order where x1 > x2 > for every 0 l n 1, the set > xn. Then, ; Gl = G kxl+1 : : : xn] \ is a Grobner basis of the lth elimination ideal Il . We also have: Theorem 7.8 Let I = q1 : : : qs h i rst elimination ideal of I. For each 1 form C x1 i : : : xn] and let I1 be the s, we can write qi in the qi = hi (x2 : : : xn)xN1 i + terms in which x1 has degree smaller than Ni where Ni 0 and hi C x2 : : : xn] is nonzero. Suppose we have a partial solution (a2 : : : an) V (I1 ). If (a2 : : : an) = V (h1 : : : hs), then there exists a1 C such that (a1 : : : an) V (I). 2 2 2 2 2 7.2 Applications to binary optimization In this section, we develop a Farkas type lemma and propose an algorithm for binary optimization problems using the results of Section 7.1. Let A Zm n and b Zm and consider the system 2 2 Ax = b x 0 1 n: 2 f (7.3) g We write xi 0 1 as x2i xi = 0 and dene k = C , which is algebraically closed. We let fi = ai x bi , i = 1 : : : m, gj = x2j xj and N = 1 : : : n : We let 2 f g ; 0 f ; ; g J = f1 : : : fm g1 : : : gn V (J ) = x C n Ax = b xi2 xi = 0 i N i h f 2 j ; 2 g 14 Chap. 7 Algebraic geometry and integer optimization and apply Theorem 7.4. Theorem 7.9 System (7.3) is infeasible if and only if there exist vectors uS Qm, S N such that u b0= 1 1 2 0 ; uS @ 0 X j 2S A j bA + ; X j 2S uS 0 j nf g Aj = 0 8 S N S = : 6 (7.4) Proof. Applying Theorem 7.2 to the ideal J we obtain that problem (7.3) is infeasible if and only if there exist polynomials h1 : : : hm and r1 : : : rn such that m X i=1 hi(x)(ai x bi ) + 0 ; Since we are interested in x h1 : : : hm of the form n X i=1 ri (x)(x2i xi) = 1: ; 0 1 n it is enough to consider polynomials 2 f g hi (x) = X S N uSi Y j 2S xj with uSi C . Since the matrix A and the vector b are real, it is enough to consider uSi Q by considering the real part of uSi . We thus obtain that for all x 0 1 n 2 2 2 f 1= g m X X i=1 S N m X X uSi (ai x bi ) 0 ; Y j 2S xj 0 1 X X Y = uSi @ aij xj bi + aij xj A xj i=1 S N j S 1 j =S 0j S m Y X X @X = uSi aij bi A xj (x2i = xi i S) i=1 S N j S j S m XX X Y ; 2 2 2 2 2 ; + = i=1 S N 0m X X S N uSi j 2= S 2 aij r2S fj g xr 0 1 m X @ uSi @ aij biA + XX uS i=1 j 2S ; j 2S i=1 1 Y xj : j iaij A nf g j 2S Sec. 7.2 15 Applications to binary optimization Q Equating the coecients of the monomials j S xj , we obtain m X ui ( bi ) = 1 i=1 0 m X i=1 ; 0 1 X @uSi @ aij biA + X uS j 2S ; j 2S 2 1 j iaij A = 0 S N S = : 8 nf g 6 which leads to Eq. (7.4). We next proceed to use Algorithm 7.1 to nd a solution to system (7.3) or to detect that no feasible solution exists. Algorithm 7.2 Input: A Zm n b Zm. Output: A feasible solution (a1 : : : an) to system (7.3) or a certicate 2 2 that system (7.3) is infeasible. Algorithm: 1. Find a Grobner basis G of the ideal J using lex order x1 > x2 > > xn. If G = 1 , then problem (7.3) has no feasible solutions. 2. If G = 1 : Consider for 1 l n 1, the sets Gl = G C xl+1 : : : xn]. Starting from index n 1, and working sequentially: (a) Find an in V (Gn 1). (b) Extend an to (an 1 an) such that (an 1 an) V (Gn 2). Continuing in this fashion, nd a2 such that (a2 : : : an) V (G1 ) and a1 such that (a1 : : : an) V (G). (c) Output (a1 : : : an). f g 6 f g ; \ ; ; ; 2 ; ; 2 2 We next show that Algorithm 7.2 correctly solves system (7.3). Theorem 7.10 Algorithm 7.2 either nds a feasible solution for system (7.3), or provides a certicate of infeasibility whenever the Grobner basis G= 1 . f g Proof. Consider the elimination ideals J1 : : : Jn 1 where Jk = J C xk+1 : : : xn]. If we nd the Grobner basis G of the ideal J using Algorithm 7.1 with the lex order, then Theorem 7.7 implies that Gk := G C xk+1 : : :xn ] is a \ ; \ 16 Chap. 7 Algebraic geometry and integer optimization Grobner basis of Jk , further implying that V (Gk ) = V (Jk ). Observe that one of the following two cases holds: (a) The Grobner basis G = 1 . Then, the ideal J = C x1 : : : xn] indicating that V (J ) is empty, since we are working in an algebraically closed eld. Therefore, system (7.3) is infeasible. (b) The Grobner basis G = 1 . In this case, we notice that Gn 1 has elements xn 1 or xn or x2n xn belonging to it. This follows from the observation that Jn 1 is a polynomial ideal in one variable, namely a subset in C xn ], and therefore needs only one generator. Moreover, we know that x2n xn is in the ideal, and thus, given that the only possible solutions in the corresponding variety are xn = 0 or xn = 1, it follows that the only possible elements of Gn 1 are xn 1 or xn or x2n xn. We interpret this to mean that points 1 or 0 or both 1 and 0 are partial solutions, respectively. Thus, we nd an V (Jn 1). Subsequently, we obtain an 1 by extending the partial solution an to (an 1 an) V (Jn 2). That is, we take a partial solution in V (Jk ) and extend it to a partial solution in V (Jk 1) and so on. By Theorem 7.8 this is always possible as the appropriate leading coecients (starting from fi and gj ) in our setting are constants. Continuing in this way and applying Theorem 7.8 we can obtain a solution (a1 : : : an) in V (J ). It is important to observe that using dierent an from V (Jn 1 ), we can nd all solutions to system (7.3). Moreover, it is important to use the lex monomial order. The results do not hold for other orders. f g 6 f g ; ; ; ; ; ; ; 2 ; ; ; 2 ; ; ; ; Example 7.6 Consider the problem x1 + 2x2 + 3x3 + 4x4 + 5x5 + 15x6 = 15 xj 2 f0 1g 8j: The ideal we consider is J = hx1 + 2x2 + 3x3 + 4x4 + 5x5 + 15x6 ; 15 x21 ; x1 x22 ; x2 : : : x26 ; x6 i: The reduced Grobner basis of J with lex order is G = fx26 ; x6 x5 + x6 ; 1 x4 + x6 ; 1 x3 + x6 ; 1 x2 + x6 ; 1 x1 + x6 ; 1g: Therefore, we have G5 = fx26 ; x6 g, indicating that a6 = 1 and a6 = 0 are both partial solutions. Starting from a6 = 1, we get a1 = a2 = : : : = a5 = 0. Starting from a6 = 0, we get a1 = : : : = a5 = 1. Therefore, the only two feasible solutions are (0 0 0 0 0 1) and (1 1 1 1 1 0) . 0 0 We next outline some structural properties of the reduced Grobner basis obtained from Algorithm 7.2 using the lex order x1 > x2 > > xn. If the solution to system (7.3) is unique, then all the reduced Grobner basis elements are of the form xi ai with ai 0 1 . ; Example 7.7 2 f g Consider the system x1 + x2 + x3 = 2 x1 + x2 = 2 x2 + x3 = 1 Sec. 7.2 17 Applications to binary optimization x1 x2 x3 2 f0 1g having a unique solution x1 = x2 = 1, x3 = 0. Algorithm 7.2 yields this solution through the reduced Grobner basis G = fx3 x2 ; 1 x1 ; 1g. As we have seen in the proof of Theorem 7.10, if the reduced Grobner basis G = 1 , then the polynomials in G can be partitioned in n sets Sn : : : S1 as follows: (a) Set Sn contains only one polynomial, which is either xn , xn 1 or x2n xn . (b) Set Sn 1 contains polynomials in xn and xn 1. (c) Set Si, i = n 2 : : : 1 contains polynomials in xn xn 1 : : : xi. This property follows from the fact that the underlying term order is an elimination order. This \diagonalized structure" of the reduced Grobner basis { a generalization of Gaussian elimination for the n n linear system of equations { is useful in enumerating the feasible binary solutions. Starting with Sn , we assign values for xn = 0 (if xn Sn ), or xn = 1 (if xn 1 Sn ), or xn = 0 1 (if x2n xn Sn ). Having chosen xn, we backsolve for xn 1 using the polynomials in Sn 1, and proceed to assign values to the other variables recursively. 6 f g ; ; ; ; ; ; 2 ; ; 2 2 ; ; Example 7.8 Consider the system x1 + 2x2 + 3x3 + 4x4 + 6x5 = 6 x1 : : : x6 2 f0 1g: The reduced Grobner basis for the lex order is G = fx25 ; x5 x4 x5 x24 ; x4 x3 + x4 + x5 ; 1 x2 + x5 ; 1 x1 + x4 + x5 ; 1g: The sets are as follows: S5 = fx25 ; x5 g S4 = fx4 x5 x24 ; x4 g, S3 = fx3 + x4 + x5 ; 1g S2 = fx2 + x5 ; 1g, S1 = fx1 + x4 + x5 ; 1g: Algorithm 7.2 enumerates all binary solutions: (0 0 0 0 1) (0 1 0 1 0) (1 1 1 0 0) : 0 0 0 We next use Grobner bases to solve the optimization problem minimize c x subject to Ax = b (7.5) x2j = xj j = 1 : : : n: 0 P n cx f = ax We work in C x1 : : : xn y] and we let h = y i j =1 j j i bi , i = 1 : : : m and gj = x2j xj , j = 1 : : : n. We consider V = V (f1 : : : fm g1 : : : gn h). Following the same approach as that used for the feasibility problem, with lex order x1 > x2 > : : : > xn > y, we notice that the Grobner basis G of J = f1 : : : fm g1 : : : gn h is either 1 (indicating infeasibility) or we will have G intersected with ky] which ; 0 ; h f g i ; 18 Chap. 7 Algebraic geometry and integer optimization leads to a polynomial in y. This polynomial in y has the interpretation that every root of the polynomial is an achievable cost, i.e., there exists a feasible solution x that has cost equal to the root. Therefore, we can nd the minimum root, and work backwards to get the associated xj values. Example 7.9 Consider the problem minimize x1 + 2x2 + 3x3 + 3x4 subject to x1 + x2 + 2x3 + x4 = 3 x2j = xj j = 1 : : : 4: The reduced Grobner basis with lex order of J = hx1 + 2x2 + 3x3 + 3x4 ; y 2x1 + 2x2 + 4x3 + 2x4 ; 6 x21 ; x1 x22 ; x2 x23 ; x3 x24 ; x4 i is G = f120 ; 74y + 15y2 ; y3 ; 20 + 2x4 + 9y ; y2 ; 6 + 6x3 + y ; x3 y x3 ; x23 ; 23 ; x2 ; x3 ; x4 + 10y ; y2 32 ; 2x1 ; 2x3 ; 11y + y2 g which suggests that all feasible y's are y = 4 5 6, i.e., the roots of the rst polynomial of the Grobner basis. If, however, we have additional information that 4 y 5, we can add the polynomial (y ; 4)(y ; 5) to J and rerun algorithm 7.2. The reduced Grobner basis with lex order is then: G = f20 ; 9y + y2 ; 1 + x3 ; 4 ; x2 + y 5 ; x1 ; yg: 7.3 Grobner bases for integer optimization We consider the integer optimization problem in standard form minimize c x subject to Ax = b 0 (7.6) x 2 Zn+ where c Zn+, b Zm+ and A Zm+ n. Note that for ease of exposition we consider rst the case that all data in the problem are nonnegative integers. We introduce an indeterminate zi , i = 1 : : : m for the ith constraint aix = bi, and exponentiate to obtain z ai1 x1 + : : : + ainxn = z bi i = 1 : : :m: 2 2 2 0 i i Multiplying these equalities we obtain n m n m m Y n ; Y aij xj Y Y ; aij xj Y Y i=1 j =1 zi = j =1 i=1 zi = j =1 i=1 ziaij !xj Y m = i=1 zibi : (7.7) Sec. 7.3 19 Grobner bases for integer optimization We further introduce the indeterminates wj , j = 1 : : : n, and the mapping : C w1 : : : wn] C z1 : : : zm ] dened as: ! (wj ) = and for a polynomial g 2 C w1 m Y i=1 ziaij : : : wn], (g(w1 : : : wn)) = g((w1) : : : (wn)): The following proposition is a direct manipulation of the denitions and is left as an exercise. Proposition 7.1 A vector x 2 Zn + is feasible in problem (7.6) if and wnxn to the monomial zb = only if maps the monomial wx = w1x1 Qm zbi : i=1 i Example 7.10 We consider the integer feasibility problem 4x1 + 5x2 + x3 = 37 2x1 + 3x2 + x4 = 20 x1 x2 x3 x4 2 Z+ The mapping : C w1 w2 w3 w4 ] ! C z1 z2 ] is given by (w1 ) = z14 z22 (w2 ) = z15 z23 (w3 ) = z1 (w4 ) = z2 : The set of feasible solutions are all the integer points (x1 x2 x3 x4 ) such that 0 (w1x1 w2x2 w3x3 w4x4 ) = z137 z220 : Q Let fj = (wj ) = im=1 ziaij and consider the ideal I = f1 w1 : : : fn wn h ; ; i C z1 : : : zm w1 : : : wn]: We further consider monomial orders in C z1 : : : zm w1 : : : wn] with the property that any monomial containing one of the zi 's is greater than any monomial containing only wj 's. For example, the monomial order z1 > : : : > zm > wn > : : : > w1 is one such order. We consider a Grobner basis G for the ideal I and the monomial order above. Let f C z1 : : : zm ] and let g = R(f G) be the remainder of the division of f by the polynomials in 2 20 Chap. 7 Algebraic geometry and integer optimization G. We next characterize R(f G) and the structure of G. Proposition 7.2 Let I = f1 w1 : : : fn wn . Let G be a Grobner h ; ; i basis G for the ideal I and the monomial order z1 > : : : > zm > wn > : : : > w1. (a) All elements of G are dierences of two monomials. (b) If f is a monomial in C z1 : : : zm ], then R(f G) is also a monomial. Proof. (a) We initialize Algorithm 7.1 with polynomials fi wi , i = 1 : : : n that ; are all dierences of two monomials. In the computation of an S-polynomial in Algorithm 7.1 to compute G, we are subtracting two polynomials each of which is a dierence of two monomials. Since the leading terms cancel, the resulting S-polynomial is again a dierence of two monomials. Arguing inductively, the result follows. (b) In the remainder calculation, we rst subtract from f a multiple of an element of G, which from part (a) is the dierence of two monomials in a way that the leading terms cancel. Given that f is a monomial, then the remainder will be a monomial. Continuing with the divisions, we conclude that R(f G) is a monomial. Example 7.11 The ideal I in Example 7.10 is I = hz14 z22 ; w1 z15 z23 ; w2 z1 ; w3 z2 ; w2i: For the monomial order z1 > z2 > w4 > w3 > w2 > w1 the Grobner basis is G = fz1 ; w3 z2 ; w3 w42 w34 ; w1 w4w33 w2 ; w12 w4 w3 w1 ; w2 w4 w14 ; w3 w23 w32 w22 ; w13 g i.e., all the elements are di erences of two monomials. The remainder is R(z137 z220 G) = w14w24 w3 : This monomial corresponds to the feasible solution x1 = 4 x2 = 4 x3 = 1 x4 = 0. The previous example demonstrates how we nd a feasible solution to problem (7.6). In order to obtain an optimal solution we need to use a monomial order that incorporates information about the cost vector c. Specically, for c Zn+, we consider a monomial order in which as before any monomial containing one of the zi 's is greater than any monomial containing only wj 's and in addition the monomials wx , wy are ordered according to the vector c induced order, so that if c x > c y, then wx > wy . If c x = c y, 2 0 0 0 0 Sec. 7.3 21 Grobner bases for integer optimization we break ties arbitrarily. We consider the following algorithm. Algorithm 7.3 Input: A Zm+ n b Zm+ c Z+n . Output: An optimal solution to problem (7.6). Algorithm: Q 1. Let fj = mi=1 ziaij and I = f1 w1 : : : fn wn : 2. Compute a Grobner basis of I using the c induced order. 3. Compute the remainder g = R Qim=1 zibi G . � � 4. If g C w1 : : : wn], i.e., g = wx� = w1x1 wnxn , then (x1 : : : xn) 2 2 2 h ; ; 2 is an optimal solution to problem (7.6) If g lem (7.6) is infeasible. 2 6 i C w1 0 : : : wn] prob- We next show that Algorithm 7.3 is correct. Theorem 7.11 Algorithm 7.3 correctly solves problem (7.6). Proof. Suppose that wx� = R(zb G), i.e., (wx� ) = zb . We assume for the purpose of deriving a contradiction that there exists a vector y such that (wy ) = zb and c y < c x . Let h = wx� wy . We have that (h) = zb zb = 0, which implies (see Exercise 7.9) that h I. Hence R(h G) = 0. However, since we use the c induced monomial order, the leading term of h must be wx� . Since wx� = R(zb G), the remainder R(h G) cannot be zero, leading to a contradiction. Note that if g C w1 : : : wn], g = R(zb G) is a polynomial in both z w. Since the variables w are lower in the order than z, if there were a feasible solution, the variables z would have been eliminated. Therefore, if g C w1 : : : wn], then there is no feasible solution. 0 0 ; ; 2 2 6 62 Example 7.12 In Example 7.10 we consider the objective function minimize 3x3 + x4 : Applying Algorithm 7.3 we nd the monomial w18 w2 w4 , leading to the optimal solution x1 = 8 x2 = 1 x3 = 0 x4 = 1: � � � � We nally discuss how to modify Algorithm 7.3 to allow for A b c having negative entries. Note that since we can write problem (7.6) as minimize y subject to c x y = 0 Ax = b 0 x ; 2 Zn + 22 Chap. 7 Algebraic geometry and integer optimization we can assume without loss of generality that c Zn+. We next consider the case that A b contain negative entries. We introduce a new variable t such that tz1 zm 1 = 0 (note t = 1=(z1 zm )). Then each of the terms 2 ; m Y i=1 can be rewritten as tkj m Y ziaij m Y i=1 ziaij i=1 tk zibi m Y i=1 zibi with kj = min 0 a1j : : : amj 0 aij = aij +kj 0, k = min 0 b1 : : : bm 0 bi = bi + k 0: Thus, Eq. (7.7) becomes ; f g n Y m Y kj j =1 t i=1 ziaij !xj = tk m Y i=1 ; f zibi modulo the relation tz1 zm 1 = 0. Thus, we consider the mapping that maps wj to the remainder ; (wj ) = tkj m Y i=1 ziaij mod tz1 h zm 1 ; and extend this mapping to a general polynomial g before. Then, the analog of Proposition 7.1 is: i 2 C w1 : : : wn] as Proposition 7.3 A vector x Zn+ is feasible in problem (7.6) having A b with general entries if and only if (wx) tk zb is divisible by 2 tz1 ; zm 1. ; Q Let fj = tkj mi=1 ziaij and consider the ideal J = tz1 h zm 1 f1 w1 : : : fn wn ; ; ; i C z1 : : : zm t w1 : : : wn]: We further consider monomial orders in C z1 : : : zm t w1 : : : wn] with the property that any monomial containing one of the zi 's or t is greater than any monomial containing only wj 's. We consider a Grobner basis G for the ideal J for the lex order above. Let f C z1 : : : zm t] and let g = R(f G) the remainder of f on G. From Proposition 7.2(b), we obtain that if f is a monomial in C z1 : : : zm t], then R(f G) is also a monomial. This 2 g Sec. 7.3 23 Grobner bases for integer optimization property together with Proposition 7.3 leads to the following algorithm. Algorithm 7.4 Input: A Zm n b Zm c Zn+. Output: An optimal solution to problem (7.6). Algorithm: 1. Let fj = tkj Qmi=1 ziaij and 2 2 J = tz1 h 2 zm 1 f1 w1 : : : fn wn : ; ; ; i 2. Compute a Grobner basis of J using the c induced order. 3. Compute the remainder g = R tk Qmi=1 zibi G . 4. If g C w1 : : : wn], i.e., g = wx� , then (x1 : : : xn) is an optimal 2 solution to problem (7.6) if g infeasible. 2 6 C w1 0 : : : wn], problem (7.6) is We illustrate Algorithm 7.4 on the following example. Example 7.13 We consider the problem minimize x1 ; x2 subject to 3x1 ; 2x2 = 1 2x1 + x2 = 7 x1 x2 2 Z+: which we rewrite to have nonnegative cost vector as: minimize subject to y x1 ; x2 ; y = 0 =1 3x1 ; 2x2 2x1 + x2 =7 x1 x2 2 Z+: The ideal J in this case is J = htz1 z2 z3 ; 1 z1 z23 z32 ; w1 t2 z1 z33 ; w2 t ; w3 i: Let G be a Grobner basis for the term order induced by (0 0 1) . We compute R(z2 z37 G) = w13 w2w32 , which leads to the optimal solution x1 = 3 x2 = 1 y = 2. 0 � � � 24 Chap. 7 Algebraic geometry and integer optimization 7.4 Applications of real algebraic geometry In this section, we use results from algebraic geometry over the reals to provide a convergent (and in the case of binary optimization, nite) sequence of semidenite relaxations for the general polynomial optimization problem Z = minimize f(x) subject to gi (x) 0 x where f gi 2 Rx] are i = 1 ::: m 2 Rn (7.8) polynomials dened as: f(x) = X � Z+n X f� x� 2 gi(x) = �2Z+n gi�x� where there are only nitely many nonzero f� and gi� . Let K= x f 2 Rn j gi(x) 0 i = 1 ::: m : g Note that problem (7.8) can model binary optimization, by taking f(x) = c x and taking as the polynomials gi(x), aix bi, xj2 xj and x2j + xj 0 0 x2 ; ; ; (to model j xj = 0). Problem (7.8) can also model bounded integer optimization, as well as bounded mixed integer nonlinear optimization. Problem (7.8) can be written as: ; maximize subject to f(x) 0 ; 8 x K: 2 (7.9) This leads us to consider conditions for polynomials to be nonnegative. We rst consider nonnegative polynomials in one dimension. Theorem 7.12 A polynomial f Rx] of degree 2d is nonnegative if and only if itPcan be written as a sum of squares of other polynomials, i.e., f(x) = ki=1hi (x)]2, with hi Rx], i = 1 : : : k. 2 2 Proof. P Clearly, if f(x) = ki=1 hi(x)]2, then f(x) 0. P d f xi of degree 2d Conversely, suppose that the polynomial f(x) = 2i=0 i is nonnegative for all x. Then, the real roots of f(x) should have even multiplicity, otherwise f(x) would alter its sign in a neighborhood of a root. Let i , i = 1 : : : r be its real roots with corresponding multiplicity Sec. 7.4 25 Applications of real algebraic geometry 2mi . Its complex roots can be arranged in conjugate pairs, aj +ibj , aj ibj , j = 1 : : : h. Then, ; f (x) = f2d Yr i=1 (x ; i )2mi h ; Y j =1 (x aj )2 + b2j : ; Note that the leading coecient f2d needs to be positive. By expanding the terms in the products, we see that f (x) can be written as a sum of squares of 2h polynomials. Clearly, in multiple dimensions if a polynomial can be written as a sum of squares of other polynomials, then it is nonnegative. However, it is possible for a polynomial in higher dimensions to be nonnegative without being a sum of squares. In Exercise 7.10 we show that the polynomial f (x y z) = x4 y2 + x2y4 + z 6 3x2y2 z 2 is nonnegative without being a sum of squares of polynomials. The next theorem generalizes Theorem 7.12 in multiple dimensions and accomodates constraints. Let M = 1 : : : m . We dene the set ; 8 < P (g1 : : : gm ) = :g 9 = X Y Rx] g(x) = qJ (x) gi (x) J M i J f 2 g 2 with qJ (x) are polynomials that have a sum of squares representation. Theorem 7.13 (Positivstellensatz) Let K = x Rn gi (x) 0 i = 1 : : : m and g Rx]. (a) g 0 on K if and only if there exist q h P (g1 : : : gm ) and f 2 j g 2 2 k Z+ such that gq = g2k + h: (b) g > 0 on K if and only if there exist q h P (g1 : : : gm ) such that gq = 1 + h: (c) g = 0 on K if and only if there exist h P (g1 : : : gm) and k Z+ such that g2k + h = 0: 2 2 2 2 If the set K is compact we can obtain a more precise certicate of positivity on K. Theorem 7.14 If K is compact, then the polynomial g > 0 on K if and only if g P (g1 : : : gm ), that is 2 g(x) = X J M qJ (x) Y i2J gi (x) (7.10) with qJ (x) are polynomials that have a sum of squares representation. 26 Chap. 7 Algebraic geometry and integer optimization Note that the number of terms in Eq. (7.10) is exponential. The next theorem establishes a certicate of positivity on K, under a mild assumption on K. Theorem 7.15 Suppose that the set K is compact and there exists a polynomial h(x) of the form h(x) = h0(x) + m X i=1 hi (x)gi (x) such that x Rn h(x) 0 is compact and hi (x), i = 0 1 : : : m are polynomials that have a sum of squares representation. Then, the polynomial g > 0 on K if and only if there exist pi Rx], i = 0 1 : : : m that are sums of squares such that f 2 j g 2 g(x) = p0(x) + m X i=1 pi (x)gi (x): (7.11) In contrast to Eq. (7.10), the number of terms in Eq. (7.11) is linear. While the assumption of Theorem 7.15 may seem restrictive, it is satised in several cases: (a) For binary optimization problems, that is, when K includes the inequalities x2j xj and xj xj2 for all j = 1 : : : n. (b) If all the gj 's are linear, i.e., K is a polyhedron. (c) If there is one polynomial gk such that the level set x Rn gk (x) 0 is compact. More generally, one way to ensure that the assumption of Theorem 7.15 holds is to add to K the extra quadratic constraint gm+1 (x) = a2 x 2 0 for some a suciently large. It is also important to emphasize that we do not assume that K is convex (it may even be disconnected). From Theorem 7.15 it is natural to investigate when a polynomial is a sum of squares. We consider the vector vd (x) = (x�) � d = (1 x1 : : : xn x21 x1x2 : : : xn 1xn x2n : : : xd1 : : : xnd ) of all the P monomials ; x; � of degree less than or equal to d, which has dimension s = di=0 ni = n+d d : f 2 j g ; k k j j ; 0 Proposition 7.4 The polynomial g(x) of degree 2d has a sum of squares decomposition if and only if there exists a positive semidenite matrix Q for which g(x) = vd (x) Qvd(x). 0 Sec. 7.4 27 Applications of real algebraic geometry Proof. Suppose there exists an s s matrix Q 0 for which g(x) = vd (x) Qvd (x). Then Q = HH for some matrix s k H, and thus, 0 0 g(x) = vd (x) HH vd (x) = 0 0 k X i=1 (H vd (x))2i : 0 Since (H vd (x))i is a polynomial, then g(x) is expressed as a sum of squares of the polynomials (H vd (x))i . Conversely, suppose that g(x) has a sum of squares decomposition P g(x) = `i=1 hi (x)2 : Let hi be the vector of coecients of the polynomial hi (x), i.e., hi (x) = hivd (x): Thus, 0 0 0 g(x) = P ` X i=1 vd (x) hi hivd (x) = vd (x) Qvd (x) 0 0 0 with Q = `i=1 hihi 0, and the proposition follows. Theorem 7.15 and Proposition 7.4 jointly imply that one can use semidenite optimization to provide a sequence of semidenite relaxations for problem (7.9). Assuming that the set K satises the assumption of Theorem 7.15, then f (x) 0, for all x K if and only if 0 ; 2 f (x) = p0(x) + ; m X i=1 pi (x)gi (x) (7.12) where pi (x), i = 0 1 : : : m have a sum of squares representation. Theorem 7.15 does not specify the degree of the polynomials pi (x). Thus, we select a bound 2d on the degree of the polynomials pi (x), and we apply Proposition 7.4 to each of the polynomials pi (x), that is, pi (x) is a sum of squares if and only if pi (x) = vd (x) Qi vd (x) with Qi 0, i = 0 1 : : : m. Substituting to Eq. (7.12), we obtain that Qi , i = 0 1 : : : m satisfy linear equations that we denote as L( Q0 Q1 : : : Qm ) = 0: Thus, we can nd a lower bound to problem (7.8) by solving the semidenite optimization problem Zd = max s:t: L( Q0 Q1 : : : Qm ) = 0 (7.13) Qi 0 i = 0 1 : : : m: Problem (7.13) involves semidenite optimization over m +1 s s matrices. From the construction Zd Z . It turns out that as d increases, Zd converges to Z . Moreover, for binary optimization, there exists a nite d for which Zd = Z . Problem (7.13) provides a systematic way to nd convergent semidefinite relaxations to problem (7.8). While the approach is both general 0 28 Chap. 7 Algebraic geometry and integer optimization (it applies to very general nonconvex problems including nonlinear mixed integer optimization problems) and insightful from a theoretical point of view, it is only practical for values of d = 1 2, as large scale semidenite optimization problems cannot be solved in practice. In many situations, however, Z1 or Z2 provide strong bounds. Let us consider an example. Example 7.14 Consider the problem minimize f (x1 x2 ) = 2x41 + 2x31 x2 ; x21 x22 + 5x42 : We attempt to write f (x1 x2 ) = 2x41 + 2x31 x2 ; x21 x22 + 5x42 0 x21 1 0 q11 q12 q13 10 x21 1 =B A@ x22 CA @ x22 CA B@ q12 q22 q23 CB q13 q23 q33 x1 x2 x1 x2 4 4 2 2 = q11 x1 + q22 x2 + (q13 + 2q12 )x1 x2 + 2q13 x31 x2 + 2q23 x1 x32 : 0 In order to have an identity, we obtain q11 = 2 q22 = 5 q33 + 2q12 = ;1 2q13 = 2 q23 = 0: Using semidenite optimization, we nd a particular solution such that Q 0 is given by 0 2 ;3 Q=B @ ;3 5 1 1 0 0 5 1 CA = HH 0 0 2 B ;3 H = p12 @ 0 1 1 3 1 AC : It follows that f (x1 x2 ) = 12 (2x21 ; 3x22 + x1 x2 )2 + 21 (x22 + 3x1 x2 )2 and thus the optimal solution value is = 0 and the optimal solution is x1 = x2 = 0. � � � 7.5 Generating functions for integer points in polyhedra In this section, we introduce generating functions for integer points in polyhedra for the purpose of counting the number of integer points in a bounded rational polyhedron P Rn. The problem naturally arises in several branches of mathematics, specically combinatorics, representation theory and number theory, while it plays a central role in statistics, specically in the computation of the exact conditional distribution for contingency tables. Sec. 7.5 29 Generating functions for integer points in polyhedra Given a rational polyhedron P introduce the generating function: f(P x) = Rn (not necessarily bounded) we X Zx : � P n 2 � \ Note that if P is bounded f(P e) is exactly the number of integer points in P . Let v be a vertex of P . The supporting cone of P at v is: : K(P v) = v+ u Rn there exists > 0 : v+ u P for all 0 Our point of departure is the following theorem: f j 2 2 g Theorem 7.16 Let P be a rational polyhedron and let V be the set of its vertices. Then, f(P x) = X v V f(K(P v) x): (7.14) 2 Proof outline Let P (y) = y A Zm n and y f 2 2 Rn + j Ax = yg be a polyhedron in standard m. We introduce the generating function 2 Z X form with Z X = x zy y ZA y Z X = Zx z A : (z x) = yX 2 2 f(P(y) x)z y ; m m �= �2 n+ � � n+ � ; � ; 2 Since Y; x� z A� = xkz1 a1k z2 a2k zmamk n ; ; ; ; k k=1 we obtain that (z x) = = n X; Y 1 k=1 k =0 n Y xk z1 a1k z2 a2k ; zmamk ; ; 1 a1k z a2k 1 x z k 1 2 k=1 ; ; k zmamk ; ; under the condition that z1a1k z2a2k zmamk > xk : Given that we know the generating function (z x) in closed form, we can use Cauchy's residue theorem to nd the coecients f(P(y) x) of the generating function (z x). j j j j 30 Chap. 7 Algebraic geometry and integer optimization The application of complex variables theory leads to Eq. (7.14). The derivation uses complex analysis heavily and it is ommited as it is outside the scope of the book. Example 7.15 Let P = 0 1]. Clearly, f (Px) = 1 + x: Moreover, for each of its two vertices, K0 = K (P 0) = 0 1) and K1 = K (P 1) = (;1 1]. Then, for jxj < 1, X f (K0 x) = xk = 1 ;1 x 1 k�0 and for jxj > 1, f (K1 x) = 1 X k� ;1 We observe that 1 : xk = x + 1 ; (1 =x) 1 f (K0 x) + f (K1 x) = 1 ;1 x + x + 1 ; (1 =x) = 1 + x verifying Theorem 7.16. Note that there is no common value of x such that the two innite sums converge. Thus, the generating functions in Theorem 7.16 need to be understood symbolically as formal power series. Therefore, the need arises to compute f(K x) for rational cones K. We rst examine the case that cone K is described by linearly independent integral vectors. Proposition 7.5 Let K = cone(u1 : : : uk),nP where u1 : : : uk are lino n early independent vectors in Z . Let S = ki=1 i ui 0 i < 1 : Then, f(K x) = X 2 Proof. Let � K 2 \ Zn, \ !Y k 1 i=1 1 ; x ui : (7.15) i.e., �= Let Z � S n x� �1 = k X i=1 ( i k X i=1 ; b i ui i c)ui i 0: and �2 = k X i=1 b i cui : Therefore, � = �1 + �2, �1 S Zn and �2 is a nonnegative integer combination of u1 : : : uk . In fact, this representation is unique. It is 2 \ Sec. 7.5 31 Generating functions for integer points in polyhedra also clear that the sum of an integer point in S and a nonnegative integer combination of u1 : : : uk is an integer point in K. Therefore, f(K x) = X � K 2 Z \ n x� = X �1 S 2 !0 x� @ Z \ n X 1 1 xm u +:::+mk uk A : Z (m1 :::mk )2 k + 1 1 The second term is a multiple geometric series which sums up to Yk 1 i=1 1 ; x ui and Eq. (7.15) follows. We next show that for certain types of cones K the computation of f(K x) is signicantly simpler. Denition 7.11 Let u1 : : : uk Zn be linearly independent vectors, K = cone(u1 : : : uk) and Lk = span(u1 : : : uk ): We say that K is a unimodular cone if u1 : : : uk is a basis of the lattice Lk Zn. 2 \ It follows that if the supporting cone K n= v + cone( u1 : : : uk)ois P unimodular, then (v+S) Zn = v , where S = ki=1 i ui 0 i < 1 : Clearly, is v Zn, then v = v. Thus, from Proposition 7.5 we obtain \ f g 2 v f(K v) = (1 xu1 ) x (1 xuk ) : ; (7.16) ; We next show how to decompose a given cone into unimodular cones. For simplicity of exposition and without loss of generality we assume that the cone is fully dimensional, i.e., K = cone(u1 : : : un). Let A be the matrix with columns u1 : : : un. We dene index(K) = det(A) . Note that nPk det(A) is equal to othe number of integer points in the parallelepiped i < 1 . In particular, K is a unimodular cone if and i=1 i ui 0 only if det(A) = 1. j j j j j j 32 Chap. 7 Algebraic geometry and integer optimization Algorithm 7.5 Input: K = cone(u1 : : : un) with u1 : : : un dent. 2 Zn linearly indepen- Output : A collection Ki , i I of unimodular cones such that K = P i2I i Ki , where i 2 f;1 2 1. g Algorithm: 1. If K is unimodular, set U1 = K U2 = otherwise U1 = , f g U2 = K . 2. While U2 = 2a. Select a cone C = cone(u1 : : : un) U2 and set A = u1 : : : un]. 2b. Apply the basis reduction algorithm ?? to nd a reduced basis A for the lattice (A 1). Compute by enumeration the shortest nonzero vector w with respect to in the lattice (A 1) as follows: f g 6 2 L ; k L k1 ; min Ax s:t: xj k j k1 p j x 2 Zn: n2n(n 1)=4 j = 1 : : : n ; Let z = Aw. 2c. Set Ki = cone(u1 : : : ui 1 z ui+1 : : : un) and Ai = u1 : : : ui 1 z ui+1 : : : un] for i = 1 : : : n. 2d. For i = 1 : : : n, set Ki = K if det(A) and det(Ai ) have the same sign, Ki = K , otherwise. If Ki is unimodular, then U1 := U1 Ki , otherwise U2 := U2 Ki . 3. Output the elements of the set U1. ; ; ; f Example 7.16 g f g Let K = cone((2 7) (1 0) ) and 0 0 A = 27 10 A 1 = 01 ;12==77 with det(A) = ;7. The reduced basis A of the lattice L(A 1 ) is 1=7 3=7 A = ;2=7 1=7 : ; ; The vector w = (1=7 ;2=7) is the shortest vector in L(A 1 ) with respect to the norm k k , and thus z = Aw = (0 1) . Then, performing Step 2c of Algorithm 0 1 ; 0 Sec. 7.5 33 Generating functions for integer points in polyhedra 7.5 we obtain the cones K1 = cone((2 7) (0 1) ) and K2 = cone((0 1) (1 0) ) with A1 = 27 01 A2 = 01 10 : 0 0 0 0 The cone K2 is unimodular with det(A2 ) = ;1 of the same sign as det(A). Then, U1 = fK2 g and K2 = 1: The cone K1 has determinant 2, and thus U2 = fK1 g and K1 = ;1. We continue Algorithm 7.5 with cone K1 and matrix A1 . We obtain that a reduced basis for L(A1 1 ) is A1 = ;11==22 11==22 : Thus, w = (1=2 ;1=2) and z = A1 w = (1 3) . Step 2c generates the two cones K3 = cone((2 7) (1 3) ) and K4 = cone((1 3) (0 1) ). Both cones are unimodular with K3 = 1 and K4 = ;1. We thus obtain the decomposition K = K2 + K3 ; K4 : ; 0 0 0 0 0 0 We next show that Algorithm 7.5 is polynomial when the dimension is xed. Proposition 7.6 Algorithm 7.5 is correct and runs in polynomial time when the dimension n is xed. Proof. We will show rst that the indices of the cones Ki decrease. Let ( X n B = z Rn z = ui xi = Ax xi i=1 2 j ) j j det(A) 1=n : j; The set B is symmetric around the origin (if z B, then z B), is convex and has volume vol(B) = 2n det(A) = det(A) = 2n : By Theorem ?? there exists a nonzero integral point z B. Thus, there exists some x = det(A) 1=n: Since in Step 2b, Algorithm A 1z (A 1) with x 1 7.5 nds a nonzero w (A ) with thePsmallest w , we have w x det(A) 1=n: Since z = Aw = ni=1 wi ui, we obtain index(Ki ) = detu1 : : : ui 1 z ui+1 : : : un] = wi detu1 : : : ui 1 ui ui+1 : : : un] w det(A) det(A) (n 1)=n = index(K)(n 1)=n: For all Ki U2 , index(Ki ) decreases after each iteration. Thus, index(Ki ) will become one, i.e., all the resulting cones in U2 will be unimodular, and thus the decomposition given by Algorithm 7.5 is correct. 2 j j j ; 2 j 2 ; ; 2 L k 2 L k k1 j j j; k1 j ; k j j k j k j ; jj ; k1 j j j ; ; 2 k1 ; j k1 34 Chap. 7 Algebraic geometry and integer optimization We next show that Algorithm 7.5 runs in polynomial time when the dimension n is xed. The key step in Algorithm 7.5 is Step 2b. The basis reduction algorithm ?? runs in polynomial time. We show next that the shortest nonzero vector w with respect to in the lattice (A 1) satises w = Ax, where A is a reduced basis and k xj j n2n(n 1)=4 p j We rst note that for all y w k Since w we have 2 ; (7.17) ; nw k ny p k1 k n y 2: (7.18) p k1 L k 2 k Zn. By Cramer's rule, xj = det(A1 : : : Aj 1 w Aj +1 : : : An ]) : det(A) By Hadamard's inequality (Exercise ??) (7.19) ; det(A1 : : : Aj j From Eq. (7.18), w k w Aj +1 : : : An] 1 2 n Aj p det(A1 : : : Aj j w j k ; k ; (A 1), we have 2 L (A 1) = (A), then w = Ax and x 2 L L j = 1 : : : n: ; p k k1 1 ; k 2 k since Aj k 2 Y i= 6 j Ai 2: k k (A 1 ). Thus, ; 2 L w Aj +1 : : : An] n p j n Y i=1 Ai 2 : k k From Eq. (7.19) we obtain xj j Q n p j n Y i=1 Ai 2 =det(A): k k From Theorem ??(d), ni=1 Ai 2 2n(n 1)=4det(A) and hence Eq. (7.17) follows, which implies that the calculation of w can be done by enumeration in polynomial time for xed dimension. Given that if the index of any cone drops below 2, the cone is unimodular and index(Ki ) index(K)(n 1)=n , after r = n log2 log2 (index(K)) iterations, we decompose K into a linear combination of unimodular cones. Since at each step at most n new cones are generated, the total number of cones we generate is at most k k ; ; nr = (log2 (index(K)))n log2 n i.e., a polynomial number for xed n. Therefore, Algorithm 7.5 runs in polynomial time when the dimension n is xed. Sec. 7.5 Generating functions for integer points in polyhedra 35 We are thus ready to prove the main theorem of the section. Theorem 7.17 Given a polyhedron P in xed dimension n, there exists a polynomial time algorithm that computes f(P x) for any given value of x. Proof. In xed dimension n there are polynomially many vertices of P . Thus, there are polynomially many terms in the decomposition in Eq. (7.14). We apply Algorithm 7.5 to decompose each term f(K(P v) x) in Eq. (7.14) in a polynomial number of unimodular cones as shown in Proposition 7.6. Since for unimodular cones K = v + cone(u1 : : : un), f(K x) is explicitly computed in Eq. (7.16) as f(K x) = (1 xu1 ) x (1 xun ) v ; ; we can compute f(P x) in polynomial time for xed n. The generating function f(P x) for a polyhedron P that results from the previous analysis has the form f(P x) = L X xai i Qn (1 ; xbij ) j =1 i=1 (7.20) where L is the number of unimodular cones, and i 1 1 . In order to compute the number of integral points within a bounded polyhedron P , we would set x = e in Eq. (7.20). Unfortunately, the value e is a singularity in the expression for f(P x). Instead we proceed as follows. With the intention of creating a univariate rational function we let xi = (1 + t)i , and i must be selected so that there is no zero denominator in any term in Eq. (7.20). It turns out that this can be done in polynomial time as well for xed dimension, but for practical purposes a random vector � with small integer coecients is sucient as we are essentially trying to avoid a set of measure zero. Then, under this transformation f(P x) becomes: 2 f; f(P t) = = = g L X (1 + t)ci i Qn (1 ; (1 + t)dij ) j =1 i=1 L X (1 + t)ci i (;1)n t;n (Qn ((1 + t)dij j =1 i=1 L X Pi (t) i (;1)n t;n Q (t) i i=1 ; 1)=t) 36 Chap. 7 Algebraic geometry and integer optimization Q where Pi (t) = (1 + t)ci , Qi(t) = jn=1 (((1 + t)dij 1)=t): We write Pi(t) = 0 + 1 t + 2 t2 + : : : and Qi (t) = 0 + 1 t + 2 t2 + : : : and let Pi (t)=Qi(t) = 0 + 1 t + 2 t2 + : : : using the recurence relation k = 1 (k 1 k 1 2 k 2 : : : k 0 ) k = 1 2 : : :: 0 = 0 0 0 We want to set t = 0 in order to compute the number of integral points in P . Thus, we are interested in computing the coecient n in this expression, and thus the number of integral points in P is ; ; L X i=1 ; ; ; ; ; i (;1)nin where in is the corresponding coecient for every unimodular cone in the decomposition. Example 7.17 We consider a triangle in two dimensions with vertices v1 = (0 1) v2 = (1 0) and v3 = (0 0) : Let Ki be the supporting cone at vi , 0 0 0 i = 1 2 3. Since each of the three cones is unimodular, we apply Eq. (7.16) and obtain x2 f (K1 x1 x2 ) = (1 ; x 1 )(1 ; x1 x2 1 ) 2 x 1 f (K2 x1 x2 ) = (1 ; x 1 )(1 ; x 1 x ) ; ; 1 ; ; 1 2 1 f (K3 x1 x2 ) = (1 ; x )(1 ; x2 ) : 1 We select � = (1 ;1) , i.e., x1 = 1 + t and x2 = (1 + t) 1 : After algebraic manipulations we obtain f (K1 t) = t2 (21+ t) 2 3 4 5 f (K2 t) = 1 + 5t + 10tt2 (2+ +10tt) + 5t + t 2 f (K t) = ;(1 + 2t + t ) : 0 3 ; t2 Using the recurrence relations the coecients 2 of the constant terms are 1=8 for K1 , 31=8 for K2 and ;1 for K3 . Summing these numbers, we obtain that the number of integer points in the triangle is 3. 7.6 Summary In this chapter, we outlined two general approaches to integer optimization and a general approach to counting integer points. The rst approach to optimization, rooted in classical algebraic geometry, has its basis in the Buchberger Algorithm 7.1. The second approach to optimization, rooted Sec. 7.7 Exercises 37 in real algebraic geometry, has its basis in algorithms to solve semidenite optimization problems. The approach to counting, rooted in complex analysis, has its basis in lattice reduction. Algorithms in algebraic geometry go hand in hand with software packages that implement them. Together they have established the modern eld of computational algebraic geometry which has come to play a major role in both theoretical advances and applications. Over the past fteen years, several excellent general purpose packages for computations in algebraic geometry have been developed, such as CoCoA, Singular, Macaulay 2 and 4ti2. Particularly Algorithm 7.1 is central to all the packages. Similarly, there is software that implements the methods of Section 7.4, specically Gloptypoly and SOS tools are general purpose packages to solve optimization problems over polynomials and are based on Sedumi, a package that implements interior point methods for semidenite optimization. Finally, the software LattE implements the counting method outlined in Section 7.5. 7.7 Exercises Exercise 7.1 Show that an order relation > on Zn+ satises Denition 7.2 if n and only if every strictly decreasing sequence �1 > �2 > in Z+ terminates. Exercise 7.2 Let V be an ane variety. If f m 2 I (V ) for some integer m, then f 2 I (V ). Exercise p 7.3 Let I be an ideal in kx1 : : : xn ]. Show that (a) I is an ideal in kx1 : : : xn ] containing I . (b) pI is a radical ideal. Exercise 7.4 Let I = hAx ; b x2i ; xi i = 1 : : : ni and let G be a reduced Grobner basis with lex order. Show that polynomials in G can be partitioned as follows: (a) Binomials of the type x2j ; xj , j 2 S = fk k + 1 : : : ng, for some k, i.e., the binomials correspond to variables that are lower in the term order. We call this group A. (b) Square free polynomials that form Group B. This group can be further partitioned in two subgroups: (b1) Polynomials that have a leading term xi , i 2= S . (b2) Polynomials that are square free with a leading monomial term: xi1 xi2 : : : xir , il 2 S . Illustrate the above property for the problem: x1 + x2 + x3 + x5 + 2x6 = 2 x2 + x4 + x7 = 1 x3 + x4 + x8 = 1 xi 2 f0 1g i = 1 : : : 8: 38 Chap. 7 Algebraic geometry and integer optimization Exercise 7.5 Given a set of points S in f0 1gn , provide a collection of linear inequalities with binary variables such that S is the set of feasible solutions and construct a Grobner basis of an ideal I such that V (I ) = S . Exercise 7.6 (a) Show how to modify Algorithm 7.2 to nd the optimal objective function value of problem (7.5) as a function of one of the right hand side coecients. (b) Appling the method from part (a) to the problem Z (b) = min x1 + 2x2 + 3x3 s:t: 2x1 + 2x2 + 4x3 = b x2j = xj j = 1 : : : 3 nd Z (b) as a function of b, when 4 b 6. Exercise 7.7 Let n be an even number. Find the output of Algorithm 7.2 applied to the problem: xi + xi+1 = 1 i = 1 : : : n ; 1 x2j = xj j = 1 : : : n: Exercise 7.8 Prove Proposition 7.1. Exercise 7.9 Using the notation of Section 7.3, show that if h 2 C w1 : : : wn ] satises (h) = 0, then h 2 I . Exercise 7.10 Show that the polynomial f (x y z ) = x4 y2 + x2 y4 + z 6 ; 3x2 y2 z 2 is nonnegative without being a sum of squares of polynomials. Exercise 7.11 Let 1 6 4 2 4 f (x y) = 4x2 ; 21 10 x + 3 x + xy ; 4y + 4y : Using semidenite optimization show that the largest for which f (x y) ; is a sum of squares is ;1:03162845: � Exercise 7.12 Let a b be positive integers with gcd(a b) = 1. Let S = f 1 a + 2 b j 1 2 2 Z+ g. Prove that for jxj < 1 X m S 2 ab x xm = (1 ; 1x; a)(1 ; xb ) : Exercise 7.13 Using the approach of Section 7.5, compute the number of in X ( ) n n x 2 R+ xi 2 : i�1 teger points in Sec. 7.8 Notes and sources 39 7.8 Notes and sources 7.1. Algebraic geometry has a long and distinguished presence in the his- 7.2. 7.3. 7.4. 7.5. tory of mathematics that has produced both powerful and elegant theorems. In recent years new algorithms have been developed and several old and new methods from algebraic geometry have led to signicant and unexpected advances in the area of discrete optimization. For a very accessible introduction to the theory of algebraic geometry we refer to the book by ?). The book by ?) develops applications of algebraic geometry to several elds. From an algorithmic perspective, a signicant development is Algorithm 7.1 which is due to ?), who coined the term Grobner basis to honor his advisor. The derivation of the Farkas lemma is new, while Algorithm 7.2 is from ?). ?) introduced Algorithm 7.3. A rst geometric translation of Algorithm 7.3 was given in ?). Further developments are described in ?) and ?). David Hilbert proposed a list of twenty-three unsolved problems at the international congress of mathematicians at Paris in 1900. The 17th problem asked whether a polynomial is nonnegative if and only if it is a sum of squares of rational functions. For a nice discussion on historical aspects of Hilbert's 17th problem see ?). Theorem 7.13 is credited to ?), but was proved earlier by ?). Theorem 7.14 is due to ?). Theorem 7.15 is due to ?) and ?). The idea of using semidenite optimization for solving optimization problems over polynomials is due to ?) and further expanded in ?) and ?). The application of the method to nonlinear binary optimization is described in ?). ?) shows that the semidenite relaxations obtained by the methods of this section are stronger than the ones obtained by ?) and ?). Theorem 7.16 is due to ?) and the polynomial time algorithm for enumerating integral points in the polyhedron is due to ?), see also ?). The use of the basis reduction algorithm in Algorithm 7.5 is due to ?). The implementation aspects of the algorithm are discussed in De?).