Turning Mathematics Problems into Games: Reinforcement Learning
and Gröbner bases together solve Integer Feasibility Problems

Reinforcement learning has seen tremendous success in recent years, especially in playing games at levels that achieve superhuman performances Mnih et al. (2015); Silver et al. (2017); Guo et al. (2016); Vinyals et al. (2019)). The philosophical principle we introduce in this paper is to try to reformulate non-trivial mathematical problems as games and then try to adapt reinforcement learning techniques to play those games. By winning the game we solve the original mathematical problem. Of course this first requires (at least for now) a human creating the right game for the given mathematical problem. As a proof of concept, in this paper we use the integer feasibility problem (IFP). In its simplest form, the IFP is the decision question of whether a polyhedral system $\{x:Ax=b,x\ge 0\}$ has an integer vector solution $x$ (note that any system of equations and inequalities can be reduced to this standard form). This famous NP-complete problem is very important in mathematical optimization, discrete mathematics, algebra, and other areas of mathematics. What we propose here is to turn it into a game on arrays.

As we explain below we transform every instance of the integer IFP into a positional game over arrays or tables with fixed margin sums belonging to the axial transportation we use an old polynomial-time algorithm from De Loera and Onn (2004a) that canonically rewrites an instance of the IFP as the face of a $l\times m\times n$ axial transportation polytope. Axial transportation polytopes are convex polytopes whose points are arrays or tables with fixed axial sums of entries Yemelichev et al. (1984). The second idea is that we know well the toric (polynomial ring) ideals of axial transportation polytopes have an explicit North-West Gröbner basis that connects all lattice points. The game starts with an initial state (an initial array), and by applying a legal move that leaves the margins unchanged, we aim to reach a winning state with zeros in specific positions. To win the game the player must find a path between the initial state and a final terminal winning state. Finding such a winning state is equivalent to solving the integer feasibility problem. As we see later the winning position, if one exists, is essentially a table with very specific zero entries. The Gröbner basis of the toric ideal for the underlying transportation polyhedron as a set generating all connecting moves that the agent can be trained to select the moves. Of course our games sometimes have no solution, then our method, at least for now, may have to exhaust all positions before concluding this. Reinforcement learning tools are then used to search the game space

Reinforcement learning on games has achieved great success and a key point of our paper is that the success can be extended to train artificial agents to play these games with a mathematical origin. We make a successful practical demonstration of these ideas with experiments in the simplest form of our games, the situation for 2D tables where we trained an agent to predict the moves. Our game can be viewed as a variant of the stochastic shortest path problem Bertsekas and Tsitsiklis (1991); Bertsekas and Yu (2013) where an agent takes a path to reach pre-defined goal states. However, unlike any of the games like Go, maze, etc, our table game has a very large and highly (algebraically) structured action space. In 2-way tables, the minimum Grobner basis contains moves of degree $4$ ($4$ non-zero entries). Although these most basic moves are sufficient for solving the game, the progress they make at each step is limited, which can cause extremely long episodes. We instead consider much more advanced moves that are integer combinations of the minimum moves. These complicated moves will be very effective for solving the table games faster. New techniques are required to compute these advanced moves because they are not only very large in number but also difficult to construct. We treat it as a regression problem and make the agent predict continuous moves which are then projected onto its closest lattice point in a constraint set specified by an integer program. We make the whole framework differentiable and thus can be trained end-to-end.

We conduct experiments on 2-way table and the results are promising, which sheds light on the potential of Gröbner basis approaches for integer feasibility problems.

We begin describing how testing integer feasibility is actually equivalent to playing a certain game on finite set of arrays inside a polytope. We begin with some notation: Let $l$,$m$ and $n$ be three positive integers. Let $x=(x_1,\dots ,x_l)$, $y=(y_1,\dots ,y_m)$, and $z=(z_1,\dots ,z_n)$ be three rational vectors of lengths $l$, $m$ and $n$, respectively, with non-negative entries. We consider the 3-way transportation polytope $T_{x,y,z}$ with entries $a_{i,j,k}$ defined by 1-marginals,

The margins are sums of the certain entries of an 3-way array of numbers. We begin with stating the first algorithmic step of this paper:

This theorem is a particular case of a much more general theory further developed in De Loera and Onn (2004a, b). Given a convex polytope $P=\{x:Ax=b,x\ge 0\}$ (for which we wonder whether there is a lattice point), the very first step is to use Theorem 1 to transfer the points of $P$ as 3-way tables. We construct $1$-marginals for a $3$-way transportation polytope $Q$, and a set $S$ of triples $(i,j,k)$, such that $P$ is the face of $Q$ of those points with $a_{ijk}=0$ for all $i,j,k$ in $S$.

Unlike general polytopes, for axial transportation polytopes with given 1-marginals it is trivial to decide integer feasibility and to find an integer vertex of $Q$. This can be done via the famous greedy north-west-up corner rule Hoffman (1963); Yemelichev et al. (1984). In fact, integral points of $Q$ will exists as long as the polytope is non-empty and the 1-marginals are integral. To check if $Q$ is nonempty over the reals (i.e., LP feasibility), all we have to do is check whether the sum of the entries in the three margins $x,y,z$ are equal.

The tables inside $Q$ will be the state space for the game. Next, in order to detect whether we have an integral solution of $P$, we can use another property of axial transportation polytopes, namely we prove that there exists an explicit Gröbner basis for the toric ideal of axial transportation polytopes which will give an integer point in $P$ if one exists. As explained in Sturmfels (1996) one can rely on the Gröbner basis elements as moves, which move us from one feasible integer point, a table, in $Q$ to another. We stress that although Gröbner bases have been criticized as having too many elements and potentially many elements of large entries (hence being hard to compute), in our situation we have nicer structure that aids to practical performance. Unlike prior situations our Gröbner bases can be generated on the fly and their elements have entries only $0,1,-1$ due to the special structure of axial transportation polytopes. We move from table to table that satisfy same margins. In other words, we get around the nasty structure of an arbitrary polyhedron $P$ via the canonical embedding $P$ as a face of an axial transportation polyhedron (which is a larger polyhedron, but it is simpler). By our results in Section Integer Feasibility Testing is a Game on Tables the pivots will find a feasible point in $P$ if and only if one exists.

Let us explain next more about Gröbner bases and the way to always find an initial table. While general transportation polytopes can be as nasty as arbitrary polytopes, axial transportation polytopes have several noteworthy computational advantages. First, checking real feasibility is trivial, the polytope is feasible if and only if the sum of the entries in each of the 1-margins equal the same value. More strongly, there will be an integer solution if the margins are integer.

A special case of axial transportation polytopes that is familiar to most readers, consists of 2-way transportation polytopes. They appear in most college-level optimization courses as bipartite network-flow problems. The $n\times m$ Hitchcock transportation problem: ${min}_{x}c[i,j]x_{ij}$, s.t. ${\sum }_{i=1}^n{x}_{ij}=a_j^1{\sum }_{j=1}^n{x}_{ij}=a_i^2$. An initial feasible solution can be obtained from a greedy procedure for certain sequences of the variables, the northwest-corner rule. This algorithm proceeds along a sequence of entries $S$ and maximizes each variable in turn with respect to the margins that bound it. Its running time is $O\left(nm\right)$. In general the algorithm constructs only a feasible, not an optimal solution. Fortunately, Hoffman (1963) gave a sufficient and necessary condition on $S$ such that the algorithm always constructs an optimal solution for arbitrary demand and supply vectors $a^1$ and $a^2$ and cost vector $c$. But for some cost vectors and special sequences the solution will be optimal. Sequences and cost matrices which fulfill the property above are called Monge sequences.

For this paper, we need to find an initial integer table efficiently for $3$-way axial transportation polytopes. The good news is that, once again, a very similar greedy algorithm for the classical $2$-way problem explained above can be applied to obtain a feasible solution for this more general case. In pseudocode this algorithm will read as follows in the case of a 3-way $l\times m\times n$ axial transportation polytope: Take an arbitrary order of the variables, say the sequence $S:=\left(\right[i_1,j_1,k_1],[i_2,j_2,k_2],\dots ,[i_{lmn},j_{lmn},k_{lmn}\left]\right)$, and perform the subsequent greedy algorithm:

Again, given a sequence $S$ of triples of indices, this greedy algorithm maximizes each variable of $S$ in turn. When the algorithm ends it will give always a feasible solution, in fact an integer solution when the margins are integer. In Rudolf (1998) we have a necessary and sufficient condition on $S$ and the cost matrix $c$ which guarantees that the solution is in fact an optimal LP solution for costs $c_{i,j,k}$ associated to each entry:

In the rest of this section, we will briefly introduce the notion of Gröbner bases relevant for our project problems. Recall a polynomial ideal $I$ is a set of polynomials in $R=Q[x_1,\dots ,x_n]$ that satisfies two properties: (1) If $f,g$ are in $I$ then $f+g\in I$ (2) If $f\in I$ and $h\in R$ then $fh$ is in $I$. a Gröbner basis of an ideal $I$ is a special finite generating set for $I$ with special computational properties. Their computational powers include the ability to answer membership questions for the ideal, computing intersections of ideals, computing projections of ideals, etc. Gröbner bases in general can be computed with the well-known Buchberger algorithm. We are only interested in special kinds of ideals, called toric ideals whose Gröbner bases are better behaved: Given a matrix $A$ with integer entries, the toric ideal $I_A$ is the ideal generated by the binomials of the form $x^u-x^v$ such that $A(u-v)=0$. Gröbner bases of toric ideals have been explored in the literature (see Sturmfels (1996); De Loera et al. (2013); Cox et al. (2005) and references therein). If we find a Gröbner basis $G_A=\{x^{u_1}-x^{v_1},x^{u_2}-x^{v_2},\dots ,x^{u_k}-x^{v_k}\}$ for $I_A$, it is well known that the vectors $\Gamma =\{u_1-v_1,u_2-v_2,\dots ,u_k-v_k\}$ will have the following properties. Let $P=\{x:Ax=b,x\ge 0\}$ be any polytope that could be defined by the matrix $A$ and by a choice of an integral right-hand-side vector $b$. If we form a graph whose vertices are the lattice points of $P$ and we connect any pair $x_1,x_2$ of them by an edge if there is a vector $u-v$ in $\Gamma$ such that $x_1-u+v=x_2$ with $x_1-u\ge 0$, then the resulting graph is connected (Sturmfels, 1996, Chapter 4). Moreover if we orient the edges of this graph according to a term order we used to compute the Gröbner basis above (where the tail of an edge is bigger than its head) this directed graph will have a unique sink. Thus from any lattice point of $P$ there is an“augmenting” path to this sink. We will call the process of traversing such an augmenting path a reduction. Moreover, we will refer to the elements in $\Gamma$ as moves. It has been shown in Hoşten and Sullivant (2002) that while toric ideals of general transportation polytopes are as nasty as those for general polytopes, axial transportation polytopes enjoy a rich decomposable structure that essentially allow us to build Gröbner bases from the Gröbner bases of their slices. For instance, for 2-way tables we know everything about the Gröbner bases of their toric ideals

For axial transportation polytope of size $m\times n\times k$, can we find a similarly nice Gröbner basis for some term order. We explain several ways next.

We have seen that from Theorem 1 the (integer) tables with specified margins in the construction represent all the lattice solutions of the original IFP. Those will be the states of the game. In order to check the integer feasibility of $P$ we need to have a Gröbner basis (test set) of the axial transportation polyhedron $Q$ such that the normal form of the North-West-corner rule integer initial solution $v$ is a feasible solution of $P$ (if such a solution exists). Of course, such a Gröbner basis exists right away: a Gröbner basis of the axial transportation arrays with respect to an elimination term order where all variables corresponding to the ”forbidden” entries of the arrays are bigger than the ”enabled” entries will do the job. In principle, we are done. However in the rest of the section we explain how to find a more efficient solution avoiding to use Buchberger algorithm.

We construct such a Gröbner basis building from the Gröbner bases of $2$-way transportation problems slices of $3$-way tables (see Theorem 2 and discussion there). Moreover, we will prove that we do not need to explicitly compute and store this Gröbner basis in advance (which is a very large set of vectors). It is enough to compute an element of the Gröbner basis ”on the fly” that will improve the current feasible solution. For our construction we will follow the ideas presented in Hoşten and Sullivant (2002). There a similar construction was given for any decomposable statistical problem. Fortunately, the $3$-way axial problems are decomposable, so we can use those techniques. But we will do this in a slightly more general way. The first set of moves that will make up a Gröbner basis is obtained as follows. Let $T$ be, for a fixed index value $k$, the 2-way transportation problem defined as $\{a_{i,j,k}\ge 0,\forall i,j,k,{\sum }_j{a}_{i,j,k}=u_{i,k},\forall (i,k),{\sum }_i{a}_{i,j,k}=v_{j,k},\forall (j,k).\}$

Let $G_{{\succ }_1},\dots ,G_{{\succ }_n}$ be $n$ different Gröbner bases of $2$-way $l\times m$ transportation problems. Note that if the $l\times m$ table $X$ with entries $X[i,j]$ is a Gröbner basis element, then for each fixed $k$ the $3$-way table $Y$ with entries $Y[i,j,k]=X[i,j]$ and $Y[i,j,t]=0$ for $t\ne k$ is a valid move for the transportation problem $T$. Now let $F(G_{{\succ }_1},\dots ,G_{{\succ }_n})$ be the set of moves obtained this way from all elements in $G_{{\succ }_k}$ for all values of $k$. The following theorem is a modification of Theorem 4.13 in Hoşten and Sullivant (2002), we omit its proof here:

There is a second set of moves for the original transportation problem $Q$ obtained from 2-way transportation problems. Now we will describe these moves. This time let $T_{x,z}$ be the $2$-way planar transportation problem. Let $G_{x,z}$ be a Gröbner basis for this problem. Suppose $X_1-X_2$ is an element in $G_{x,z}$ where $X_1$ and $X_2$ are nonnegative tables with entries $X_1[i,k]$ and $X_2[i,k]$. We can “lift” such an element to a move for the original problem $Q$ as follows. First note that $X_1-X_2$ is homogeneous, i.e., ${\sum }_{i,k}{X}_1[i,k]={\sum }_{i,k}{X}_2[i,k]=t$. Second because we are in the setting of a $2$-way transportation problem, for each $k$ we have ${\sum }_i{X}_1[i,k]={\sum }_i{X}_2[i,k]$. Hence we can represent $X_1-X_2$ as

Here we allow that some indices $[i_s,k_s]$ repeated if the corresponding entry $X_1[\cdot ,\cdot ]$ (or $X_2[\cdot ,\cdot ]$) in the table is bigger than one. Now given a sequence of indices (again repetitions are allowed) $j_1,\dots ,j_t$ we get a move $Y_1-Y_2$ for the transportation problem $Q$: $\left(\right[i_1,j_1,k_1],[i_2,j_2,k_2],\dots ,[i_t,j_t,k_t\left]\right)-\left(\right[i_1^{\prime },j_1,k_1],[i_2^{\prime },j_2,k_2],\dots ,[i_t^{\prime },j_t,k_t\left]\right).$

We let $L\left(G_{x,z}\right)$ to be the set of all moves obtained from all Gröbner basis elements in $G_{x,z}$ using all possible liftings. Similarly we can define $L\left(G_{y,z}\right)$. Now we claim we can put together $F(G_{{\succ }_1},\dots ,G_{{\succ }_n})$, $L\left(G_{x,z}\right)$, and $L\left(G_{y,z}\right)$ to get a Gröbner basis for the toric ideal of $l\times m\times n$ $3$-way axial transportation problem. However, we first need to describe the appropriate term order.

Given a $3$-way table $X$ we can compute “projection” tables (marginals) in any axial direction. For instance $Pro{j}_{x,z}\left(X\right)$ would be the $2$-way table whose $(i,k)$ entry is ${\sum }_{j}X[i,j,k]$.

The proof of Lemma 2 is in the Appendix.

Now we are ready to construct a Gröbner basis for $3$-way axial transportation problems with which we will solve the integer feasibility problem for any polytope $P$ after it has been encoded as a $3$-way axial transportation polytope $Q$. In order to do this we will describe term orders ${\succ }^1$, ${\succ }^2$ and ${\succ }_1,\dots ,{\succ }_n$ and then use Theorem 4. Recall that by the construction of $Q$, the tables corresponding to the feasible solutions of $P$ will be a face $F$ given by forbidden entries which need to be set to zero. If $X$ is such a table where all the enabled entries are positive, then we get forbidden entries for tables $Pro{j}_{x,z}\left(X\right)$, $Pro{j}_{y,z}\left(X\right)$ which are forced to be equal to zero. Also each horizontal slice $X_1,\dots ,X_n$ will have its own forbidden entries. Let $F_{x,z}$, $F_{y,z}$ and $F_1,\dots ,F_n$ be these forbidden entries, and let $E_{x,z}$, $E_{y,z}$, and $E_1,\dots ,E_n$ be their complements, namely the enabled entries. We let $w_{x,z}$ be the weight vector where $w_{x,z}(i,k)=1$ if $(i,k)\in F_{x,z}$ and $w_{x,z}(i,k)=0$ if $(i,k)\in E_{x,z}$. We define $w_{y,z}$ and $w_1,\dots ,w_n$ in a similar way. We define the term order ${\succ }^1$ to be any elimination term order where $F_{x,z}{\succ }^1{E}_{x,z}$ (and the entries $F_{x,z}$ and $E_{x,z}$ within themselves are ordered in an arbitrary but fixed way) which refines the ordering giving by $w_{x,z}$. In other words, given two $l\times m\times n$ tables $X$ and $Y$, if the weight of $Pro{j}_{x,z}\left(X\right)$ is bigger than the weight of $Pro{j}_{x,z}\left(Y\right)$ then we declare $Pro{j}_{x,z}\left(X\right){\succ }^{1}Pro{j}_{x,z}\left(Y\right)$. In the case of equality, we resort to the elimination term order that breaks the tie. Note that if the support of $Pro{j}_{x,z}\left(Y\right)$ is contained in $E_{x,z}$ and that of $P_{x,z}\left(X\right)$ is not, then we immediately declare $Pro{j}_{x,z}\left(X\right){\succ }^{1}Pro{j}_{x,z}\left(Y\right)$. We define ${\succ }^2$ and ${\succ }_1,\dots ,{\succ }_n$ similarly in which the forbidden entries are eliminated.

As a proof of concept, we now describe our method of playing table games using reinforcement learning on the polyhedral Gröbner bases systems we presented. Here we only consider the simpler special case of 2-way tables because we have an explicit list of all Gröbner basis moves already (See Theorem 2). Similar ideas can be extended to 3-way axial transportation polytopes. In this family, the state space $S$ consists of $m\times n$ tables of a 2-way transportation polytope with fixed 1-margins,

The action space is the Gröbner basis generators that connect any two $m\times n$ tables in $S$. They are computed using Theorem 2. It is noteworthy that the action space can be defined with more flexibility because one can consider the minimum set of actions that connects all tables, or with more complicated moves that are linear combinations of the minimum moves. There is a trade-off between the action space and the efficiency of solving the game. We refine our action space $A$ as follows.

Note that any element of the action space $A$ is generated as integer combination of the Gröbner basis of Theorem 2, which suggests that for any two states $s_1,s_2\in S$, there exists a path connecting $s_1,s_2$ using moves from $A$. In the most general form, our table games can be formulated as follows.

where $\Omega \left(s\right)$ is the set of valid moves for (table) $s$: $\Omega \left(s\right)=\{a|a\in A,s+a\ge 0\}.$

We pre-defined the terminating state of the game by specifying a set of entries $G$ such that $s_{(i,j)}=0,\forall (i,j)\in G$ as the terminating condition which mimics the forbidden entries of the axial transportation polytope computed in Theorem 5. The reward function penalizes every step when the goal state is not reached:

The reward function encourages a policy $\pi$ that can reach a terminating state with the minimum number of steps.

We proposed an algorithm that converts the integer feasibility problem into a game on tables. We formulated the table game as a reinforcement learning problem and developed novel techniques to tackle the algebraic structure of the action space. The experimental results on 2-way tables show the potential of solving integer feasibility problems using the Gröbner bases approach. Training on 3-way tables is the next stage of our work. Since IFP is an NP-complete problem, in some cases our game algorithm may have to visit all (exponentially many) tables before concluding there is no solution. It is an open problem to explore ways to cut the search as our games have no solution sometimes.

In this appendix we include technical proofs of some of the main theorems. Including an explanation of how any rational polyhedron can be rewritten as a face of a 3-way axial transportation polytopes with fixed 1-marginals.