we
Journal of	JET v°iume 8 (2015) p.p. 43-58
Issue 2, October 2015 Typology of article 1.01
Technology	www.fe.um.si/en/jet.html
INTEGER PROGRAMMING AND GROBNER BASES
CELOSTEVILSKO PROGRAMIRANJE IN GROBNERJEVE BAZE
Brigita Fercec1, Matej MencingerR
Keywords: Integer linear programming, polynomial rings, Grobner bases, nonlinear polynomial systems of equations
Abstract
An approach to solve the integer linear programming problem (IP) using the Grobner bases theory is presented. We consider the basics of commutative algebra on polynomial rings and their ideals and the multidivision algorithm. Grobner bases were introduced to solve nonlinear polynomial systems of equations; therefore, we first present the generalization of the Gauss elimination method. In order to solve a general IP a special ideal depending on the coefficients of the system and number of constraints in the IP has to be constructed. Finally, a Grobner basis of this ideal, which yields the solution to IP, must be sought.
Povzetek
V članku je podan pristop k reševanju celoštevilskega linearnega programiranja (IP) z uporabo teorije Grobnerjevih baz. Obravnavamo osnovne elemente komutativne algebre na polinomskih kolobarjih, njihove ideale in algoritem multi-deljenja. Grobnerjeve baze so bile vpeljane za reševanje nelinearnih polinomskih sistemov enačb, zato je v članku najprej predstavljen primer posplošitve Gaussove elimi-nacijske metode. Pri reševanju splošnega IP konstruiramo poseben ideal, ki je odvisen od koeficientov sistema in števila enačb v IP. Končno rešitev dobimo s pomočjo Grobnerjeve baze tega ideala.
R Corresponding author: Integer programming and Grobner bases, Matej Mencinger, Tel.: +386 2 229 4321, Mailing address: University of Maribor, Faculty of Civil Engineering, Transportation Engineering and Architecture, Smetanova ulica 17, 2000 Maribor, Slovenia, E-mail address: matej.mencinger@um.si
'Faculty of Energy Technology, Hočevarjev trg 1, 8270 Krško
JET 43
Brigita Fercec, Matej Mencinger
J ETVol. 8 (2015)
Issue 2
1 INTRODUCTION
Many modern computer programs, such as Mathematica, Matlab and others, enable solving the problem of integer (linear) programming (IP). There are several algorithms to solve the problem of IP; one of the most known and commonly used is the so called 'Branch and bound algorithm'. In this paper, we consider another aspect of solving this problem, which is based on the theory of Grobner bases, which is the basis of the ideal of a polynomial ring in a similar sense as the vector space (Rn, +), which has a basis consisting of n linearly independent vectors (1,0,0,...,0), (0,1,0,...,0), ..., (0,0,0,...,1). These n vectors are called a standard basis of (Rn, +) and in a similar sense theGrobner basis is called a standard basis of the given ideal.
Turning now to the IP, where there are more equations and variables, and a cost function to be optimized, and taking into account that the main objects of the polynomials of several variables are monomials, we can use the fact that the exponent of each monomial is actually a vector. As we will see later, this vector is naturally related to independent variables of IP that are (basically positive) integers.
There are many different ways of examining the theory of Grobner bases. In the context of classical algebra, the natural point of view is as follows.
We consider polynomials in variables X1, ... with coefficients a„ of a field fc. We call x" =x"1—x^™ a monomial, aa £fc a coefficient and a^x"1 •••x"™ a tenm, and a = a multi-index. The set of all polynomials in variables x^... ,x„ with coefficient in fc is denoted by fc[x1,.,x„]. With the usual operations of addition and multiplication, fc[x1,.,x„] is a commutative ring (i.e. the multiplication in the ring is symmetric). We call a = a1 + —ha„ the full degree of a monomial xa. The degree of a polynomial /, denoted by deg(/), is the maximum degree of a monomial of /. For any natural number n, the space
fcn = {(a-p..., an): a1,. ,an £fc)
is called n—dimensional affine space. The set of polynomials /1,... ,/ is naturally associated with a system of equations
A(X1,..,XJ = 0,
• (1.1) /S(X1,...,X„) = 0.
The set of all solutions to the above system can be defined as the affine variety, K, determined by polymomials /1,...,/:
K(A...../) = {K.....aj efc":/(a1.....aj = 0 /or 1 <7 < s}.
It is clear that there are many families of polynomials defining the same variety. For example, if /1 = x — y, /2 = y —1 and 51 = (y — x)3, =y2 — 2y +1, then V</1,/2> = K<51,52>-To understand the concept of an affine variety better we need the notion of an ideal.
44 JET
Integer programming and Grobner bases
An ideal in the polynomial ring	is a subset / of	satisfying
i.	if /,,gG/ then / + $ G / and
ii.	if / G/ and h Gfc[x1,_,xn], then h/ G /.
Let A,...,/ be polynomials of	We denote
</1...../) ={Z5=ih//yl hi.....hs Gfc[*i.....*„]}.
It is easily seen that </1,.,/S) is an ideal in fc[x1,.,xn]. Polynomials /1,.,/s are called generators of this ideal. Ideal / cfc[x1,.,xn] is finitely generated if there exist polynomials </1...../) Gfc[x1,.,xn] such that / = </1,.,/s), and the set {A,...,/} is called a Oasis of /.
From the definition of an affine variety, we see that to find an affine variety V(A,..-,/) is equivalently as to find the set of solutions of system (1.1). This is a problem that frequently arises in studies of various phenomena in physical, technical and other sciences. In particular, in order to study the qualitative behaviour of dynamics system
=/1	= 0, . ,xs = A (X1,X2,..., xn)
we first have to determine singular points of the system, which are the points where all polynomials A, — ,/ vanish. Thus, we again arrive at a problem of the form (1.1), [6,7,10].
The problem of finding solutions of system (1.1) is very difficult. It can happen that system (1.1) has infinitely many solutions, which means that it is impossible to find (all) solutions numerically. Even if system (1.1) has a finite number of solutions it is still very difficult and often impossible to find all of them numerically without applying methods of computational algebra.
In the next section, we describe the concept of Grobner bases, which is closely related to the multivariable division algorithm. We consider the main properties of Grobner bases and connect them to the solution of system (1.1). In the third section, we study the main topic of this paper, the integer programming problem (IP) via the theory of Grobner bases. We demonstrate the application of the theory of Grobner bases theory to IP on two examples. In the first example, we consider a case of IP without a cost function (i.e. just a problem to find integer solutions to Ax = fo), while in the second example we search for the solutions to a general IP (with a given cost function).
2 GROBNER BASIS AND NONLINEAR SYSTEMS OF EQUATIONS
Until the mid-1960s, when Bruno Buchberger, [2], invented the theory of Grobner bases, no method for solving a general (nonlinear polynomial) system (1.1) was known. What is nowadays called Buchberger's algorithm (and Grobner basis) is actually the cornerstone of modern computational algebra. In this section, we first briefly describe the notion of a Grobner basis, which will be used to obtain the variety of an ideal generated by polynomials A,--,/, i.e. to obtain the solution of system (1.1). Since a Grobner basis of / depends on a term ordering on monomials of fc[x1,.,xn], we define monomial (term) order.
JET 45
Brigita Fercec, Matej Mencinger
J ETVol. 8 (2015)
Issue 2
A monomial order < on	, xg] is a total order < on Ng with the following two properties:
(i)	any nonempty subset of monomials has a least element (under <),
(ii)	if xa <x^ then xaxy <x^xy for every monomial xy.
The most common monomial ordering is shown in the following example.
Let us consider x^xfxf0 , xjsx|x|,xjix|x3 6E[x1,x2,x3] and say, x is 'more important' than x2 (and x3) and x2 is 'more important' than x3. Then:
xfx2xf >xjix2x3 >X:LX2X3°.
This monomial order is called a lexicographic (monomial) order. More precisely, xa <x^ if and only if the first coordinates and ^ in a and p from left, which are different, satisfy a^ <Pj. There are many other standard monomial orders, like (graded) reverse lexicographic, (graded) reverse lexicographic, etc. [4]. To avoid the, we can emphasize the name of the monomial order. For example <iex stands for the lexicographic order.
As soon as the monomial order is chosen, we can speak of the so-called leading monomial (LM), leading term (LT) and leading coefficient (LC) of the polynomial. The leading term is defined with the largest (with respect to fixed order) monomial.
For example, if / = —x2xfxf° + 2xfx|xf + 3x^x1x1 and the order is lexicographic with xx > x2 >xf, the leading term of / is LT(/) = 2xfx|xf, whilst the leading coefficient is LC(/) = 2 and the leading monomial LM(/) = xf xl xi.
Finally, note that any vector c £ Rn defines an monomial order < in E[x1,.,xn] in the following way:
.»■¡j (?•£?<?•/?	or
x" < xp o
Ic • a = (?• // and a p,
where a stands for the standard dot product c • a = X c^. This monomial term order < defined by vector c is usually called weighted (monomial) order.
For example, if c = (1,5,10), we have xfx1xf < x1x°xf since c • a = (1,5,10) • (5,1,2) = 30 and c • P = (1,5,10) • (1,0,3) = 31 (and 30 < 31). Note, that for < the leading term of g = 2xfx!x| — 5x1x°xf is LT(g) = —5x1xf while for <iex the leading term of (the same) g is LT(g) = 2xfx!x|.
Now, we describe the procedure of multi-division of a polynomial by an ordered set of polynomials, that is to divide / £ fc[x1,.,x„] by an ordered set F = {/1,.,/sl, which means to express / in the form
/ = ?i/i + ?2/2 + - + ?s/s + r,	(1.2)
46 JET
Integer programming and Grobner bases
where the quotients ^i,..., and the reminder r are polynomials of fc^,...^,,], and either r = 0 or deg(r) < deg(/). In this case (1.2) means that / is reduced to r modulo F, and we write
F
The process of multi-division depends on the monomial order and the order of the polynomials in the set F = {A,..,/s,}. So, we have to fix the monomial order first to perform the multidivision. For the precise introduction to multivariable division algorithm see e.g. Adams & Luostaunau (1994), Cox et al. (2007), and Romanovski & Shafer (2009). We demonstrate the division process by the following example.
Let us divide / = x2y + xy2 +y2 by the ordered set of polynomials F = {/i,/2} = {xy — l,y2 — 1} using lexicographic order with x > y.
i/i - s + y
Qi : i __T_
fi xy-i y'x2y -f xy2 + y2
x2y — x
xy2 + x + y2 xy2 - y x + y2 + y
yr+ y	->	x y2- 1
1	—>	x + y
0	x + y+l
Figure 1: The scheme of multivariable division procedure
On the first step, the leading term LT(/i) = xy divides the leading term LT(/) =x2y. Thus, we divide x2y by xy, leaving x and then subtract x ■ /i from /. Next, we repeat the same process on x y2 + x + y2. We divide / by LT(/i) = xy again. Note that neither LT(/i) = xy nor LT(/2) = y2 divides LT(x +y2 +y) = x. However, x + y2 +y is not the remainder since LT(/2) divides y2. Thus, if we move x to the remainder column, we can continue with the process. If we can divide by LT(/i) or LT(/2), we proceed as usual, otherwise, we move the leading term of the intermediate dividend (the polynomial under the radical sign) to the remainder column. We continue dividing in such a way. Now the polynomial under the radical is y2 +y. It is not divisible by LT(/i) but we can divide it by LT(/2) yielding 1 and the subtract 1 ■ y2 from y2 +y. The obtained polynomial under the radical is y +1 and neither LT(/i) nor LT(/2) is divisible by LT(y + 1) = y. Therefore, we move y to the remainder column and obtain 1, which is also moved to the remainder column. Thus, the remainder is x + y + l and this concludes the example. Thus, we can write / in the form
JET 47
Brigita Fercec, Matej Mencinger
J ETVol. 8 (2015)
Issue 2
f = x2y + xy2 +y2 = (x + y) • (xy — 1) + 1 • (y2 — 1) + x + y +1.
In contrast, if we change the order of polynomials f and f2 in F, i.e. if we divide f by the ordered set F = {f2,f}, we obtain
f = x2y + xy2 + y2 = x^ (xy — 1) + (x + 1) • (y2 — 1) + 2x + 1.
Obviously, this multivariable division is very sensitive on the order of f1,f2. The order affects the multi-quotients q,1,ql2, as well as the remainder r. Dividing the polynomial f with the (ordered) set F = (f1,f2), one can simply write: f = {{q,1,ql2}, r} instead of f = ql1f1 + ql2f2 + r. Using this notation, in the first case, we have f = {{x + y, 1}, x + y +1} and in the second case we have f = {{x, x + 1},2x+ 1}. Figure 2 shows the last results obtained by the MATHEMATICA computer algebra system. The multi-quotients and the remainder are also changed if we use another monomial order.
lm[l]:= PolynomialReduoe [ x A 2 y + x y A2 + y A2, (ij-1, y A2 - 1} , {x, y] ] lr[2;:= PolynomialReduoe [x A2 y + x y A2 + y A2, {y A2 - 1, x y - 1} , {x, yj]
Figure 2: Results obtained by MATHEMATICA fon the case above
Now, we present the basic definitions and properties of Grobner bases. For any ideal, / we define <iT(/)> = <iT(/): / £ / \ {0}> = <iM(/): / £ / \ {0}>. A Grobner basis of an ideal /cfc[;e1,,_,xn] is a finite subset G = {fl^,...,^} of / such that
<LT(/)> = <LT(51).....LT(gt)>.
It is a special generating set for ideal <f1,^,f,> for which the multivariable division algorithm for a given f returns the remainder r = 0 if and only if f £ <51,...,5t>,[4]. Using a Grobner basis, we obtain the uniqueness of the remainder, which was not assured when we divided by an arbitrary set of polynomials, [2].
We now describe an algorithm for computing a Grobner basis of a polynomial ring. Let f,g be from fc[x1,.,x„] with LT(f) = axa and LT(g) = fox^. The least common multiple of xa and x^, denoted LCM(xa,x/?), is the monomial xr = x[* •••x,n such that = maxfo,^-), 1< 7 < n. The so-called 5—polynomial of f and g is
= x^	x^
= ZTcf) — ITcg) •g.
Buchcbengen's basic observation was the following criterion, [2]. Let / be a nonzero ideal in fc[x1,.,x„] and let < be a fixed monomial order on fc[x1,.,x„]. Then, G = {g1,g2,.,gt} is
a Grobner basis for / with respect to < if and only if for all i
,
48 JET
erteggr progrnmminGandGrdbner bases
This criterion is the essence of the famous Buchberger's algorithm, which produces a Grobner basis for the nonzero ideal / = (/1,...,/s). Buchberger's algorithm is shown below, [11].
Buchberger's Algorithm
Input: A set of polynomials {A,..,/} £fc[x1,..,xn]\{0}. Output: A Grobner basis G of the ideal (A,..,/). Procedure: G: = {A,-,/}.
Step 1. For each pair fl^fl, EG.iij, compute the 5—polynomial Sg^. and compute the remainder r^ of division Sg^. by the set G.
Step 2. Check if all r^- are equal to zero . If "yes", then G is a Grobner basis, otherwise add all nonzero r^ to G and return to step 1.
It is proved in [2] that the algorithm terminates and returns a Grobner basis of the ideal / =
</l,/2...../n).
Nowadays, all well-known computer algebra systems (MATHEMATICA, SINGULAR, MAPLE, REDUCE, and others) have routines to compute Grobner bases.
Even if a monomial order is fixed, an imprecision in the computation of a Grobner basis arises because the division algorithm can produce different remainders for different orderings of polynomials in the set of divisors. Thus the output of Buchberger's Algorithms is not unique; neither is it minimal (in the sense that it contains more polynomials then necessary). A Grobner basis G = {fl,1,.,fl,m} is called minimal if, for all i,_j £ {1,... ,m},	= 1 and
for j ^ ¿, LM(fli) does not divide LM(fl,). Every nonzero polynomial ideal has a minimal Grobner basis, [4]. If no term of fl is divisible by any LT(fl_,) for j ^t then the Grobner basis is called reduced and if we fix a monomial order then every nonzero ideal / cfc[x1,.,xn] has a unique reduced Grobner basis with respect to this order.
In Figures 3 and 4, the Grobner basis of the ideal (—x3 + y,x2y — y2) with respect to lexicographic monomial order with x >y is computed in systems MATHEMATICA and SINGULAR, [9], respectively. We see that in both cases the result is {y3 —y2,xy2 —y2,x2 y — y2,x3 — y}.
In[6]:= GroebnerBasis [ |-k3 + y, xzy-y2}, {x, y} ]
Figure 3: Output of Grabner basis in system MATHEMATICA
JET 49
Brigita Fercec, Matej Mencinger
J ETVol. 8 (2015)
Issue 2
SINGULAR
A Computer Algebra System for Polynomial Computations
by: U. Decker, G.-M. Greuel, G. Pfister, H. Schoenemann FB Mathematik der Uniuersitaet, D-67653 Kaiserslautern
>	ring r1=fl, (x,y),lp;
>	poly f1=-x3+y;
>	poly f2=x2*y-y2;
>	ideal I=f1 ,f2;
>	ideal G=groebner(I);
>	G;
G[1]=y3-y2 G[2]=xy2-y2 G[3]=x2y-y2 G[i|]=x3-y
>	I
Figure 4: Output of Gnöbncn basis in system SINGULAR
A reason to use more special systems than MATHEMATICA offers is to compute the Grobner basis with respect to some special monomial order. In Figure 5 we compute the Grobner basis of (—x3 + y,x2y — y2) using SINGULAR with respect to the weighted monomial order with weight vector c = (1,3). Note, that the result G< = (x3 — y,y2 — x2y) is not the same as the Grobner basis with respect to lexicohraphic monomial order G<)pr(v>r) = (—xs + x6, —x3 +y).
SINGULAR
A Computer Algebra System for Polynomial Computations
by: W. Decker, G.-M. Greuel, G. Pfister, H. Schoenemann PB Mathenatik der Uniuersitaet, D-67653 Kaiserslautern
>	ring r1=B, (x,y),Wp(1,3);
// ** redefining r1 **
>	poly f1=-x3+y;
>	poly f2=x2*y-y2;
>	ideal I=f1,f2 ;
>	ideal gI=groebner(I);
>	gi;
gl[1]=x3-y
gl[2]=y2-x2y
Figure 5: Grobner basis G<( ) of (x3 — y, —x2y + y2) computed in SINGULAR
Recall that to solve a system of linear equations, an effective method is to reduce it to the form in which an initial string of variables is missing from some of the equations, that is, the so-called "row-echelon" form. The next definition and theorem provide a way to eliminate a group of variables from a system of nonlinear polynomials. Moreover, it provides a way to find all solutions of a polynomial system in the case that the solution set is finite, or in other words, to find the variety of a polynomial ideal in the case that the variety is zero-dimensional.
For any ideal 1 = (fi, — ,fs) c fc[x1,x2,^,x„] the I— th elimination ideal /; is the ideal of fc[xi+1,xi+2,.., xn] defined by
/
/ uersion 3-1->
\ Jan 2012 \

/
/ uersion 3-1-4
B<
\ Jan 2012 \
50 JET
Integer programming and Grobner bases
In the case of solving a system of nonlinear equations (1.1), this means that / — (/1,...,/), but the elements of /; are the equations (polynomials) that follow from / — 0, ...,/ — 0 and eliminate the variables	Concerning the Grobner bases and elimination ideals, we
have the following
Theorem, ([4]). IfG — {fll,...,St} is a Grobner basis for / — (A,...,/) c fc[x1,.,xn] with respect to lexicographic order with >-->xn, then for each 0<Z < n the set
G; — G O fc[X^ + l,X^+2,..., xn] is a Grobner basis for the Z—th elimination ideal.
Grobner basis theory allows one to find all solutions of a system (1.1) if the system has only a finite number of solutions. In such case a Grobner basis with respect to the lexicographic order is always in a "row-echelon" form, as can be seen using the following example, [5]. Consider the polynomials
/1 = x2 + yz + x /2 = z2 + xy + z /3 =y2 + xz + y.
With respect to the lexicographic order with x >y >z, the Grobner basis of ideal (A,/2,/3) is G = {fl'i.fl,2.fl,3.fl,4.fl,5.fl,6}, where
= x + x2 + yz
,2 = xy + z + z2
,3 = z + xz + yz + z2 + 2yz2
,4 = y + y2 z yz z2 2yz2
,5 =z2 + 2yz2 +z3 + 2yz3
,6 = z2 + 3z3 + 2z4.
Thus, the system /1 =/2 =/3 = 0 is equivalent to the system
,1 =,2 =,3 =,4 =,5 =,6 =
For a generic system (1.1), a Grobner basis may have significantly more complex structure than obtained in this example. However, if the system has only a finite number of solutions (i.e. the ideal is zero-dimensional), then any reduced Grobner basis {gf1(... ,,„} must contain a polynomial in one variable, let say, ,1(x1). Then, there is a subset of the Grobner basis depending on this variable and one more variable, say, ,2(x1,x2),.,,t(x1,x2), etc. Thus, we first solve (perhaps only numerically) the equation ,1(x1) = 0. Then, for each solution x^ of ,1(x1) = 0, we find the solutions of ,2(x1,x2) = ••• = ,t(x1,x2) = 0, which is a system of
JET 51
Brigita Fercec, Matej Mencinger
J ETVol. 8 (2015)
Issue 2
polynomials in a single variable x2. Continuing the process, we obtain in this way all solutions to (1.1). Thus, in the case of the finite number of solutions, Grobner basis computations theoretically provide the complete solution to the problem (see e.g. Section 2.2. of [1] for more details).
3 GROBNER BASIS AND INTEGER LINEAR PROGRAMMING
In previous sections, we considered the process of multi-division and the Grobner bases theory. Before the formal definition of the integer linear programming problem, note that the essence of the problem concerns the integer solutions of a linear system Ax = b (constraints), which optimizes the so-called cost function. Therefore, it would be quite convenient if the rows of the matrix equation Ax = b (i.e. the equations) could be presented (in the first approximation) as exponents of some new variables. In order to make things more straightforward, let us consider Ax = b (where: [A]tj = atj and b = (bl,.,bm)) with the following restrictions: atj £Z, btE2 and Cj E R with i = 1,2,... ,n and j = 1,2,... ,m. We want to find a solution x = (xl,x2,.,xn)E'n to
allxl + ai2x2 + + alnxn = bl
•	(3.1)
amlxl + am2x2 + '" + amnxn = bm,
which minimizes the cost function c(xl,x2,...,xn) = Y^n=l Cjxj. We call (3.1) an integer (linear) program (IP). In the matrix form, we have
minimize c ■ x", subject to Ax = b,
whene A EZmxn cnd b = (b^... ,bm)Elm. Note that all coefficients (including the solution vector) are generally allowed to be from the set ', but for now let the coefficients be limited to be natural numbers: N.
The main mathematical idea which makes use of Grobner bases when solving IP (3.1) is to associate new variables Xk for k = 1,2,... ,m (one variable to each equation) to (3.1) to represent the k— th equation in (3.1):
X<iklx1+ak2x2+-+aknxn =xk^k ^ Xk represents the k — th equaition
The use of new variables makes the formulation of system (3.1) much simpler:
ya11X1+a12X2H \-alnXn yamlX1 + am2X2H hamnXn _ yb1 ybm
Xl	m	l	m ,
which is equivalent to
(X*11 -X^m1)Xl.....(X*1n -Xammn)Xn =X$.	(3.1a)
52 JET
Integer programming and Grobner bases
Note that in (3.1a) the original (integer) variables Xk (fc = 1,... ,n) adopt the meaning of the (integer) exponent of X"1* •••X,™. Therefore, to each column of (3.1) or equivalently to each term in the brackets (...) in (3.1a), we associate a new variable yk = X1'1fc •••X,mfc for each fc = 1,2,., n.
The first step in solving our IP problem is to determine whether a solution exists or not. The theory of Grobner bases helps to characterize the existence and finally to prove the optimality of the solutions to IP (3.1).
The crucial idea in solving (3.1) in terms of Grobner bases plays the following ring homomorphism
O:fc[y.....^fctfi.....X,],
which associates to any polynomial from the ring fc[y1,...,y„] a polynomial from the ring fc[X1,.,Xm], which is defined by:
Oft) =<lfc "Xmfc.	(3.2)
We immediately see that homomorphism (3.2) is in a one-to-one relation with a system of the form (3.1) (more precisely, the image of every yk is bijective related with the fc-th column on the left side of (3.1)); furthermore, according to (3.1a), we have
o^*1.....y„n) = Xs.
Concerning the map O defined by (3.2) we can assert the following. If we assume that all coefficient a^- and ^ from (3.1) are non-negative, then a solution x = x EN„ of (3.1) exists if and only if the monomial Xf1 •••X,'™ is in the image under homomorphism O. This means that a monomial Y* £fc[y1,.,y„] exists for which O(y*) = Xf1 •••X,™, and x EM„ is a solution to (3.1).
Both implications of the above assertion can be proved at once. Let x = (x1,^2,.,;^„)ENj} be a solution of (3.1). This means that (3.1a) holds for b = x. According to definition of O this is equivalent to
(Oft))*1 - (O(y„))*" =X1fl •••X,™ Now, since O is a homomorphism we have
Oft1 -yf^X^-X,™
JET 53
Brigita Fercec, Matej Mencinger
J ETVol. 8 (2015)
Issue 2
and X^-X^" is in the image under O and the corresponding original is 5 1 ■■■yrnn £ yn], and we have shown that this is equivalent to x = (x^X^...^«^^ being solution to (3.1).
This means that x for which Yx is in the image under O is an integer solution to system (3.1), but still we have to handle the problem of the minimality condition of the cost function c(x1,x2,...,xn) = S{?=1c/x/-. In order to solve this, we need some additional results. First, if x1,x2,.,xn and y1,y2,.,yn are elements of a commutative ring fc, then for any non-negative integers a1,a2,.,an the polynomial x^x"2 x"n — yC^y"2 y"" is in the ideal (x1—y1,...,xn—yn). The proof can be done by mathematical induction on the number of elements xn and yn. Let us simply mention that for n = 1 (the basis for induction) the assertion is a well-known result
x" —y" = (x — y)(x"_1 + x"_2y H-----bxy""2 + y"_1).
For the rest of the proof, see [12].
Now let K = <lWi.....5n—/n)E ..........X„] and /n £fc[X1.....X„]. If g £
.....yn], then g(51.....5J = 2{l=1(5i —/„)h£, where hi efc[11.....M.....X„]. Let
O map 5	Then g(/1,.,/n)=0, thus O(g) = 0. In contrast, let O(g) = 0 and let g =
X« C" 51"152"2 ••• (where finitely many C" ^0). Since g(/1,.,/n)=0, we have
g = g — 0 = g— g(A,..,/,)
\ c /"l /"2 /"n
/ i La >1 >2 ••• /n
"
r-ai c"2 ran\ J1 >2 •••>{ J
which is in the ideal K = <y1—/1,..., 5,—/,), according to the previous result. Thus, Ker(O) = Knfc[51,., 5n], and the elements of Ker(O) can (by the elimination theorem) be found in the following way: first find the Grobner basis of the ideal K = <51—/^...,5n—/,) in fc[51,., 5n,X1,.,X?n] with respect to a lex ordering X1 > — >^,„>51 >•••> 5n. Then a Grobner basis for Knfcft,.., 5n] will be precisely the polynomials of the Grobner basis of K that do not have any X variables. Obviously, for a given homomorphism O, any monomial / £ fc[51,., 5n] is not in the image of O. Let us denote the Grobner basis of K = <51 —/1,., 5n—/n) obtained by the elimination theorem by G. According to the above results, we have
/ £ Ker(O) o 3h £ fc[55L,.,5n] s.t. / - h,
which is then the key to the solution of IP (3.1) constrained by the cost function c(x1,x2,...,xn)= Hn^ CjXj. Finally note that, if take care that the monomial order which is used to compute the Grobner basis, G<c, of the ideal K = <51—/1,.,5n—/,) is compatibile with the cost function c(x1,x2,...,xn)= H"=1 c,-x/ and with the corresponding
g = 7 C" if^"2 ••• 5„"n —
g =
"
"1 "2
n
54 JET
Integer programming and Grobner bases
^iY*1 ■■■ Y*n) = ^iy*1 ■■■ Y*n)
and
c(x1,x2, — ,xn)<c(x1,x2, — ,xn)
YX1 ... y*n ^ yJ
11 1n ^-c 11
Xi
then from X^1 —X^ Y*1 ■■■ Y*n one can deduce that x = (x1,x2,—, xn)ENn is a solution to IP (3.1) for which the cost function c(x) = c ■ x is minimal. The minimality of the solution is proven by contradiction. If any other solution x = (x1,x2, — ,xn) is minimal then, since c(x) = c(x) and since the term ordering <c is compatibile with the cost function and with the corresponding system we have ((Y* ■■■ Y*n) = ((Y*1 ■■■ YnXn); implying ((Y* ■■■ Y*n —
Y*1 ■■■Yn^n) = 0, which means Y* ■■Yn*n — Y*1 ■■■ Y^7 0, which contradicts the assumption that Y*1 ■■■ Yn*n is already reduced with respect to G<c.
The above results are the basis for Conti & Traverso's well-known algorithm, which is described below (see ([3]) for more details). However, first we have to consider how to transform (3.1) which can contain some negative integers; recall that generally a;j El and b; El. This can be generally transformed to an IP with strictly nonnegative (integer) coefficients aij,bi by adding an extra indeterminate W defined by
Xi^X2.....Xm^W = 1,	(3.3)
which transforms
XAj-. = X*1j.....X:aii.....
to
Xl1i+aii.....x;0.....XmmJ+aiJ ■Wan = XAjwj,
where Wj = Waii. In a similar way, if there are some negative entries in b, we transform Xb
to X^Wj;.
The optimal solution of IP (3.1) with some negative integers is, therefore, obtained in the following way:
•	Define W by (3.3), if there are some negative entries in A,b
•	define an ideal 1 = {Y1 —XA1,—,Yn —XAn} on the polynomial ring k[X1,...,Xm,Y1,—,Yn], if there are no negative entries in A,b
JET 55
Brigita Ferčec, Matej Mencinger
JET Vol. 8 (2015)
Issue 2
•	define an ideal / = {Y1—XAiW1, ...,Yn — XA"Wn,X1 -X2.....Xm-W -1} on
the polynomial ring k[X1,. ,Xm,W, Y1,.,Yn], if there are some negative entries in A,b
•	let G be a reduced Grobner basisof /with respect to a monomial order <g, where c is defined by the cost function c ■ x
•	dividing XbWg (i.e. the generalization of Xb) by G always yields a remainder RE k[Y1,.,Yn], which because of its minimality (ensured by the multivariate division algorithm) ensures the optimality of the solution; thus the solution x = (fi1,.,Pn) to IP (3.1) is obtained by reducing XbW^ by G which yields a remainder R =
Y1Pl — YnPn and thereby the solution x = (fi1,.,Pn).
The next example will show the method for determining whether system of the form (3.1) has a non-negative integer solution, and for finding a solution. The method consists of the following three steps, [12]:
•	Compute a Grobner basis G for the ideal K = {Yj —X^1' •••X^'-1 <j <n)
with respect to an elimination order with the X variables greater than Y variables.
b b
•	Find the remainder r of the division of the monomial X11 •••Xmm by G.
•	If r £ k[Y1,.,Yn], then system (3.1) does not have non-negative integer solutions. If r = Y1JC1 ••■Yn , then (x1,... ,xn) is a solution of system (3.1), [1].
Now, we show how the proposed method works.
Example 1: Let us check if there exist non-integer solutions of system
2x1 +x2 = 3
X1 "hx^ "h 3x3 — 5.
On the first step, we compute a Grobner basis G of an ideal K = {Y1 — X1X2,Y2 — X1Xz,Y3 — X2) with respect to lexicographic order with X1 >X2 >Y1 >Y2 >Y3. We obtain
r — f V 6 _1_ V 3v Y V 4 V 2v v V V 2 v 2v 2 y y 3 w Y 2v G — t_ y2 + X1 y3,X2 y2	1 Y3,X2 ~ X2 ,X2 Y2 ~ X1r3,X2 ~ X3, ~X2 Y2
+ X1Y3,—Y1+X1Y2,X1X2 — Y2}. Then, we divide monomial XlX2 by G and obtain Y11Y21Y31. Therefore, the non-negative integer solution is (x1,x2,x3) = (1,1,1).
Example 2 ([8]): We show how to optimize the cost function with respect to some constraints Ax = b, and the coefficients are now allowed to be also negative integers. Following (3.1), we have to minimize the cost function
c ■ x = 1000x1 +x2 +x3 + 100x4 subject to
3x^1 2x2 hx3 X4 — 1
4x1 +x2—x3 =5.
56 JET
Integer programming and Grobner bases
The solution to the above example obtained with system SINGULAR is shown in Figure 6. Note that the weighted term order is used with C = (1000002,1000001,1000000,1000,1,1,100) to ensure that X1 > X2 > W > 71 > 72 > 73 > 74 and to ensure the weight order (1000,1,1,100), corresponding to c = (1000,1,1,100). Note that, for example, the monomials XSWg and XA2W2 are:
X%g =X1"1Xf =X1"1X2"1 -X^f = W1X26, X^ W2 =Xj"2X2 =XJ-2X2-2 -X22X2 = W2X|.
The optimal solution x = (1,3,2,0) is obtained from the result of the multivariable division:
W1 X26 - 71172373274°.
SINGULAR	/
A Computer Algebra System for Polynomial Computations	/
0<
by: W. Decker, G.-M. Greuel, G. PFister, H. Schoenemann \ FB Mathenatik der Uniuersitaet, D-67653 Kaiserslautern	\
>	ring r1=0,(X1,X2,U,V1,V2,V3.V4) ,Up(1000002,1 000001 ,1000000,1000,1 ,1 ,100);
>	poly F1=V1-N13*N2ii;
>	poly f1=Y1-X1~3*X2"it;
>	poly f2=V2-X2~3*LT2;
>	poly F3=Y3-X1~2*U;
>	poly fii=Y4-J{2*W;
>	poly FB=N1*N2*W-1;
>	ideal I=F1,f2,f3,F4,F5;
>	ideal gI=groebner(I);
>	reduce(W*X2~6,gI); V1*V2~3*V3"2
>	I
Figure 6: Computing the optimal solution in system SINGULAR
uersion 3-Jan 2B12
JET 57
Brigita Ferčec, Matej Mencinger
JET Vol. 8 (2015)
Issue 2
References
[1]	W.W. Adams, P. Loustaunau: An introduction to Gröbner bases: Graduate Studies in Mathematics. Vol. 3, Providence, RI: American Mathematical Society, 1994
[2]	B. Buchberger: Ein Algorithmus zum Auffinden der Basiselemente des Restlasseringes nach einem nulldimensionalen Polynomideal. PhD Thesis, Mathematical Institute, University of Innsbruck, Austria, 1965
[3]	P. Conti, C. Traverso: Buchberger algorithm and integer programming, Applied algebra, falgebraic algorithms and error-correcting codes (New Orleans, LA, 1991), Lecture Notes in Comput. Sci. vol. 539, p. 130-139, 1991
[4]	D. Cox, J. Little, D. O'Shea: Ideals, Varieties and Algorithms: An Introduction to Computational Algebraic Geomety and Commutative Algebra. New York: Springer, 2007
[5]	S.R. Czapor: Gröbner basis methods for solving algebraic equations. Ph.D Thesis. University of Waterloo, Canada, 1988
[6]	V.F. Edneral, A. Mahdi, V.G. Romanovski, D.S. Shafer: The center problem on a center manifold in R3, Nonlinear Anal., vol. 75, p. 2614-2622, 2012
[7]	B. Fercec, M. Mencinger: Isochronicity of centers at a center manifold, AIP conference proceedings, 1468. Melville, N.Y.: American Institute of Physics, p. 148-157, 2012
[8]	S. Flory, E. Michel: Integer Programming with Gröbner basis. (http://www.iwr.uni-heidel-berg.de/groups/amj/People/Eberhard.Michel/Documents/Else/DiscreteOptimization.pdf)
[9]	G.M. Greuel, G. Pfister, H. Schönemann: Singular 3.0. A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserslautern, 2005; http://www.singular.uni-kl.de.
[10]	V.G. Romanovski, M. Mencinger, B. Fercec: Investigation of center manifolds of 3-dim systems using computer algebra. Program. comput. softw., vol. 39, no. 2, p. 67-73, 2013
[11]	V.G. Romanovski, D.S. Shafer: The center and cyclicity problems: A computational algebra approach. Boston: Birkhauser Verlag, 2009
[12]	C. Wendler: Groebner Bases with an Application to Integer Programming; (http://docu-ments.kenyon.edu/math/CWendler.pdf), 2004
58 JET