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

Yue Wu, Jesús A. De Loera∗ Equal contribution

###### Abstract

Can agents be trained to answer difficult mathematical questions by playing a
game? We consider the _integer feasibility problem_ , a challenge of deciding
whether a system of linear equations and inequalities has a solution with
integer values. This is a famous NP-complete problem with applications in many
areas of Mathematics and Computer Science. Our paper describes a novel
algebraic reinforcement learning framework that allows an agent to play a game
equivalent to the integer feasibility problem. We explain how to transform the
integer feasibility problem into a game over a set of arrays with fixed margin
sums. The game starts with an initial state (an array), and by applying a
legal move that leaves the margins unchanged, we aim to eventually 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,
if one exists. Finding such a winning state is equivalent to solving the
integer feasibility problem. The key algebraic ingredient is a Gröbner basis
of the toric ideal for the underlying axial transportation polyhedron. The
Gröbner basis can be seen as a set of connecting moves (actions) of the game.
We then propose a novel RL approach that trains an agent to predict moves in
continuous space to cope with the large size of action space. The continuous
move is then projected onto the set of legal moves so that the path always
leads to valid states. As a proof of concept we demonstrate in experiments
that our agent can play well the simplest version of our game for 2-way
tables. Our work highlights the potential to train agents to solve non-trivial
mathematical queries through contemporary machine learning methods used to
train agents to play games.

## Introduction

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\geq 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, Kovalëv, and Kravtsov 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.

## Basic notions: polyhedra and Gröbner bases

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,

$\displaystyle a_{i,j,k}\geq 0,\,\forall
i,j,k,\quad\sum_{j,k}a_{i,j,k}=x_{i},\,\forall i$
$\displaystyle\sum_{i,k}a_{i,j,k}=y_{j},\,\forall
j,\quad\sum_{i,j}a_{i,j,k}=z_{k},\,\forall k.$

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:

######  Theorem 1.

Any rational convex polyhedron can be written as a face $F$ of some $3$-way
transportation polytope $Q$ with $1$-marginals $x,y,z$ supported by a
hyperplane of the form $\sum_{(i,j,k)\in S}a_{i,j,k}=0$, where $S$ is a finite
subset of indices. The sizes $l,m,n$, the set $S$, and marginals $x,y,z$ can
be computed explicitly in polynomial time on the size of the input.
Specifically, the face $F$ is given by certain entries forced to be zero.

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\geq 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, Kovalëv, and Kravtsov 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^{1}_{j}\ \sum_{j=1}^{n}x_{ij}=a^{2}_{i}$. 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(nm)$. 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:=([i_{1},j_{1},k_{1}],[i_{2},j_{2},k_{2}],\dots,[i_{lmn},j_{lmn},k_{lmn}])$,
and perform the subsequent greedy algorithm:

For $s:=1$ to $lmn$ do

  1. 1.

Set $x_{i_{s},j_{s},k_{s}}:=\min\\{a^{1}_{s},a^{2}_{s},a^{3}_{s}\\}$

  2. 2.

$a^{1}_{s}:=a^{1}_{s}-x_{i_{s},j_{s},k_{s}},\,a^{2}_{s}:=a^{2}_{s}-x_{i_{s},j_{s},k_{s}},\,a^{3}_{s}:=a^{3}_{s}-x_{i_{s},j_{s},k_{s}}$

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:

######  Lemma 1.

The generalized north-west rule algorithm finds a feasible solution for the
three-dimensional axial transportation problem for all right-hand-side vectors
$a_{1}$, $a_{2}$, and $a_{3}$ whose sum of entries are equal. The solution is
integer if the vectors $a_{1},a_{2},a_{3}$ are integer. Moreover if there is a
cost matrix cost matrix $c_{i,j,k}$, which is a three-dimensional Monge
sequence in the sense of (Rudolf 1998), then the solution found is an optimal
linear programming solution for the minimization problem.

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={\mathbb{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, Hemmecke, and Köppe 2013; Cox, Little, and O’Shea 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\geq 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\geq 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

######  Theorem 2.

Let $A$ be the $0/1$-matrix which is the matrix of the linear transformation
that computes the row and column sums of a given $2$-way table. Then $A$ is
(totally) unimodular and hence its minimal universal Gröbner basis consists of
its circuits. These circuits are $2$-way tables whose row and column sums are
zero and with entries in $\\{0,+1,-1\\}$ of minimal support.

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.

## Integer Feasibility Testing is a Game on Tables

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}\geq 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}},\ldots,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\neq k$ is a valid move for the transportation problem $T$.
Now let $\mathcal{F}(G_{\succ_{1}},\ldots,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:

######  Theorem 3.

Let $G_{\succ_{1}},\ldots,G_{\succ_{n}}$ be $n$ Gröbner bases of the $2$-way
$l\times m$ transportation problem. Let $\succ^{\prime}$ be the term order on
the entries of the $l\times m\times n$ axial transportation problem where
$\\{Y[i,j,1]\\}\succ^{\prime}\\{Y[i,j,2]\\}\succ^{\prime}\cdots\succ^{\prime}\\{Y[i,j,n]\\}$
and the entries in the $k$th horizontal slice $\\{Y[i,j,k]\\}$ are ordered
with respect to the term order $\succ_{k}$. Then
$\mathcal{F}(G_{\succ_{1}},\ldots,G_{\succ_{n}})$ is a Gröbner basis with
respect to $\succ^{\prime}$.

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

$([i_{1},k_{1}],[i_{2},k_{2}],\ldots,[i_{t},k_{t}])-([i_{1}^{\prime},k_{1}],[i_{2}^{\prime},k_{2}],\ldots,[i_{t}^{\prime},k_{t}]).$

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},\ldots,j_{t}$ we get a move $Y_{1}-Y_{2}$ for the transportation
problem $Q$:
$([i_{1},j_{1},k_{1}],[i_{2},j_{2},k_{2}],\ldots,[i_{t},j_{t},k_{t}])-([i_{1}^{\prime},j_{1},k_{1}],[i_{2}^{\prime},j_{2},k_{2}],\ldots,[i_{t}^{\prime},j_{t},k_{t}]).$

We let $\mathcal{L}(G_{x,z})$ 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 $\mathcal{L}(G_{y,z})$. Now we claim we can put together
$\mathcal{F}(G_{\succ_{1}},\ldots,G_{\succ_{n}})$, $\mathcal{L}(G_{x,z})$, and
$\mathcal{L}(G_{y,z})$ 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 $Proj_{x,z}(X)$ would be the $2$-way table
whose $(i,k)$ entry is $\sum_{j}X[i,j,k]$.

######  Lemma 2.

Let $\succ^{1}$ and $\succ^{2}$ be term orders for $l\times n$ and $m\times n$
planar tables and let $\succ_{1},\ldots,\succ_{n}$ be $n$ term orders forthe
$l\times m$ planar tables. If $\succ^{\prime}$ is the term order for $l\times
m\times n$ $3$-way tables described in Theorem 3, then the relation
$\succ_{*}$ on such $3$-way tables given by X $\succ_{*}$ X’ if

$\displaystyle Proj_{x,z}(X)$
$\displaystyle\succ^{1}Proj_{x,z}(X^{\prime})\,\mbox{or}$ $\displaystyle
Proj_{x,z}(X)=Proj_{x,z}(X^{\prime})$ $\displaystyle\mbox{ and
}Proj_{y,z}(X)\succ^{2}Proj_{y,z}(X^{\prime})\,\mbox{or}$ $\displaystyle
Proj_{x,z}(X)=Proj_{x,z}(X^{\prime})$ $\displaystyle\mbox{ and
}Proj_{y,z}(X)=Proj_{y,z}(X^{\prime})\mbox{ and }$ $\displaystyle
X\succ^{\prime}X^{\prime}$

is a term order.

The proof of Lemma 2 is in the Appendix.

######  Theorem 4.

Let $G_{x,z}$ and $G_{y,z}$ be Gröbner bases for the $l\times n$ and $m\times
n$ planar transportation problems with respect to the term orders $\succ^{1}$
and $\succ^{2}$, respectively. Also let $G_{\succ_{1}},\ldots,G_{\succ_{n}}$
be $n$ Gröbner bases for $l\times m$ planar transportation problems with
respect to the term orders $\succ_{1},\ldots,\succ_{n}$. Let $\succ^{\prime}$
be the term order for the $l\times m\times n$ tables given in Theorem 3. Then
the set

$G\quad=\quad\mathcal{L}(G_{x,z})\cup\mathcal{L}(G_{y,z})\cup\mathcal{F}(G_{\succ_{1}},\ldots,G_{\succ_{n}})$

is a Gröbner basis for the $3$-way axial transportation problems with respect
to the term order $\succ_{*}$ of Lemma 2.

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},\ldots,\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 $Proj_{x,z}(X)$,
$Proj_{y,z}(X)$ which are forced to be equal to zero. Also each horizontal
slice $X_{1},\ldots,X_{n}$ will have its own forbidden entries. Let $F_{x,z}$,
$F_{y,z}$ and $F_{1},\ldots,F_{n}$ be these forbidden entries, and let
$E_{x,z}$, $E_{y,z}$, and $E_{1},\ldots,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},\ldots,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 $Proj_{x,z}(X)$ is bigger than the weight
of $Proj_{x,z}(Y)$ then we declare $Proj_{x,z}(X)\succ^{1}Proj_{x,z}(Y)$. In
the case of equality, we resort to the elimination term order that breaks the
tie. Note that if the support of $Proj_{x,z}(Y)$ is contained in $E_{x,z}$ and
that of $P_{x,z}(X)$ is not, then we immediately declare
$Proj_{x,z}(X)\succ^{1}Proj_{x,z}(Y)$. We define $\succ^{2}$ and
$\succ_{1},\ldots,\succ_{n}$ similarly in which the forbidden entries are
eliminated.

Algorithm 1 Integer Feasibility Testing Game

Input: A rational polytope $P\subset\mathbb{R}^{d}$ presented in its
representation $P=\\{x:Ax=b,\ x\geq 0\\}$.

Output: YES or NO depending on whether $P$ contains an integer lattice point.

  1. 1.

Compute the encoding of $P$ as a face of a $3$-way axial transportation
polytope $Q$.

  2. 2.

Use the North-West-corner rule to find an initial table $V$ that is a feasible
integer solution in $Q$.

  3. 3.

Use Gröbner basis elements with respect to $\succ_{*}$ constructed above to
get the unique sink $W$. If the weight of $Proj_{x,z}(W)$ or of
$Proj_{y,z}(W)$ is not zero, output NO.

  4. 4.

Otherwise, using the Gröbner basis elements in $G_{x,z}$ and $G_{y,z}$ of
weight zero (and their liftings) generate a set $\mathcal{S}$ of tables such
that $\\{Proj_{x,z}(T)\,:\,T\in\mathcal{S}\\}$ and
$\\{Proj_{y,z}(T)\,:\,T\in\mathcal{S}\\}$ are the set of $2$-way $l\times n$
and $m\times n$ tables with the same row and column sums as $Proj_{x,z}(W)$
and $Proj_{y,z}(W)$, and with their support in $E_{x,z}$ and $E_{y,z}$
respectively.

  5. 5.

For each $T\in\mathcal{S}$ reduce $T$ just using the Gröbner basis elements in
$\mathcal{F}(G_{\succ_{1}},\ldots,G_{\succ_{n}})$ to obtain $X$. If the weight
of $X$ with respect to $w_{k}$ is zero for all $k=1,\ldots,n$, output YES. If
no $T$ in $\mathcal{S}$ gives rise to such an $X$, output NO.

######  Theorem 5.

Algorithm 1 solves the integer feasibility of any rational polytope $P$ by
first transforming it into an 3-way axial transportation polytope $Q$ with
specific 1-margins and finding a sequence of Gröbner basis moves from an
initial 3-way array in $Q$ to another 3-way array in $Q$ with zeros in
specified entries if one exists (equivalent to finding an integer solution for
$P$).

## Learning to Play Games on 2-way Tables

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 $\mathcal{S}$ consists of $m\times n$ tables of a 2-way
transportation polytope with fixed 1-margins,

$\mathcal{S}=\\{\mathbf{s}\in\mathbb{Z}^{m\times
n}\,|\,\sum_{i}\mathbf{s}_{i,j}=x_{i},\,\sum_{j}\mathbf{s}_{i,j}=y_{j},\,\mathbf{s}\geq
0\\}.$

The action space is the Gröbner basis generators that connect any two $m\times
n$ tables in $\mathcal{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 $\mathcal{A}$ as follows.

$\mathcal{A}=\\{\mathbf{a}\in\\{-1,0,1\\}^{m\times
n}\,|\,\sum_{i}\mathbf{a}_{i,j}=0,\sum_{j}\mathbf{a}_{i,j}=0\\}.$

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

$\displaystyle\max_{\pi}\quad$
$\displaystyle\sum_{t}\mathbf{r}_{t}(\mathbf{s}_{t},\mathbf{a}_{t})|_{\pi(\mathbf{s}_{t})=\mathbf{a}_{t}}$
$\displaystyle\text{s.t.}\quad\mathbf{a}_{t}\in\Omega(\mathbf{s}_{t})$
$\displaystyle\quad\quad\mathbf{s}_{t+1}=\mathbf{s}_{t}+\mathbf{a}_{t}.$

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

We pre-defined the terminating state of the game by specifying a set of
entries $\mathcal{G}$ such that
$\mathbf{s}_{(i,j)}=0,\,\forall(i,j)\in\mathcal{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:

$\displaystyle\mathbf{r}_{t}=\begin{cases}\frac{1}{\left\lVert|s|\right\rVert_{\infty}},&\text{if}\quad\exists\,(i,j)\in\mathcal{G},\,\mathbf{s}_{(i,j)}\neq
0,\\\ 0,&\text{otherwise.}\end{cases}$ (1)

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

### Reinforcement Learning Framework

Our RL framework is based on Twin Delayed DDPG (TD3 (Fujimoto, van Hoof, and
Meger 2018; Lillicrap et al. 2016)). TD3 is an off-policy method which
requires a replay buffer $\mathcal{B}$ to collect a set of transitions
$(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime},\mathbf{r})$. There are two critic
networks $Q_{\theta_{1}}$ and $Q_{\theta_{2}}$ and an actor network
$\pi_{\phi}$. Both critic networks are trained by minimizing the mean squared
Bellman error:

$L_{Q}(\theta_{i})=\mathbb{E}_{(\mathbf{s},\mathbf{a},\mathbf{s}^{\prime},\mathbf{r})\sim\mathcal{B}}\left\lVert
y(\mathbf{s}^{\prime},\mathbf{r})-Q_{\theta_{i}}(\mathbf{s},\mathbf{a})\right\rVert^{2},\,i=1,2.$

The target $y$ is defined as the minimum of two fixed target critic networks
to prevent overestimation of the $Q$ function.

$y(\mathbf{s}^{\prime},\mathbf{r})=\mathbf{r}+\gamma\min_{i=1,2}Q_{\theta^{\prime}_{i}}(\mathbf{s}^{\prime},\pi_{\phi^{\prime}}(\mathbf{s}^{\prime})).$

#### Structured Action Prediction

Figure 1: The interaction between the actor and the environment. The actor
network $\pi_{\phi}$ predicts a continuous move $\mathbf{a}$, which is then
projected to a discrete $\tilde{\mathbf{a}}$ in the set $\Omega(\mathbf{s})$
before being applied to the environment.

Due to the fact that our action space is discrete, one natural way is to
predict the action as a classification problem at each time step. However, its
feasibility is hindered by the large number of actions to compute and store in
advance. We instead make the actor network predict a continuous action
$\mathbf{a}=\pi_{\phi}(\mathbf{s})$. Then, we obtain the integral solution
$\tilde{\mathbf{a}}=P_{\Omega(\mathbf{s})}(\mathbf{a})$ by projecting
$\mathbf{a}$ to the feasible set of discrete actions encoded by the following
integer program.

$\displaystyle\min_{\mathbf{a}^{+},\mathbf{a}^{-}}\quad$
$\displaystyle\sum_{i,j}||\mathbf{a}^{+}-\mathbf{a}^{-}-\mathbf{a}||_{d}$ s.t.
$\displaystyle\sum_{i}\mathbf{a}^{+}_{i,j}-\mathbf{a}^{-}_{i,j}=\mathbf{0},\,\sum_{j}\mathbf{a}^{+}_{i,j}-\mathbf{a}^{-}_{i,j}=\mathbf{0}$
$\displaystyle\quad\mathbf{a}^{+}+\mathbf{a}^{-}\leq
1,\,\sum_{i,j}\mathbf{a}^{+}_{i,j}\geq 1,$ (2)
$\displaystyle\quad\mathbf{a}^{+},\,\mathbf{a}^{-}\in\\{0,1\\}^{m\times n},$

and we obtain the projected discrete action by
$\tilde{\mathbf{a}}=\mathbf{a}^{+}-\mathbf{a}^{-}$. We add constraint (2) to
exclude the action with all zeros. An illustration of the process is shown in
Figure 1. Splitting $\tilde{\mathbf{a}}$ into two binary variables
$\mathbf{a}^{+}$ and $\mathbf{a}^{-}$ not only speeds up the projection but
also provides more flexibility on the constraints of the actions. For
instance, we can bound the number of non-zero elements in the action by adding
$c_{1}\leq\sum_{i,j}\mathbf{a}^{+}_{i,j}\leq c_{2}$ to the system.

To train the critic network, we consider the projection operator a
deterministic part of the environment and directly learn
$Q(\mathbf{s},\mathbf{a})$. Similar strategies can be found in Dulac-Arnold et
al. (2015). It is worthwhile to mention that one can also learn
$Q(\mathbf{s},\tilde{\mathbf{a}})$. The non-differentiable projection layer
can be tackled by straight-through estimators (Bengio, Léonard, and Courville
2013; van den Oord, Vinyals, and kavukcuoglu 2017). However, for every mini-
batch update, calculating a target in the temporal difference learning
requires the projection operations to obtain $\tilde{\mathbf{a}}$. The
projection will become a bottleneck and significantly slows down the whole
training process. We also observed in experiments that learning
$Q(\mathbf{s},\tilde{\mathbf{a}})$ has no obvious performance gain. The actor
network is updated for each mini-batch $B$ by gradient ascent

$\nabla
J(\phi)=\frac{1}{|B|}\sum\nabla_{\mathbf{a}}Q_{\theta}(\mathbf{s},\mathbf{a})\nabla_{\phi}\pi_{\phi}(\mathbf{s}).$
(3)

### Learning from Demonstrations

Learning from demonstrations is an effective strategy to improve sample
efficiency. Due the the large action space of our problem, we generate a set
of demonstrations $\mathcal{B}_{D}$ using a greedy algorithm to speed up the
learning. We make sure that a fixed portion of samples in the mini-batch are
drawn from the demonstration during each training step. Since the
demonstrations generated by the greedy algorithm are not perfect, we adopt the
Q-filter strategy (Nair et al. 2017) to only enforce a supervised learning
loss when the demonstrated action $\mathbf{a}$ has a higher $Q$ value than the
actor’s action. Thus, the demonstration loss on mini-batch $B_{D}$ using
demonstrated action $\mathbf{a}_{D}$ can be summarized as:

$L_{D}=\frac{1}{|B_{D}|}\sum||(\mathbf{a}_{D}-\pi_{\phi}(\mathbf{s}))||^{2}\cdot\mathbbm{1}_{Q_{\theta}(\mathbf{s},\mathbf{a}_{D})>Q_{\theta}(\mathbf{s},\pi_{\phi}(\mathbf{s}))}.$

(a)

(b)

(c)

Figure 2: The learning curve of our RL agent compared with the behavior
cloning baseline in $5\times 5$ table games.

(a)

(b)

(c)

Figure 3: The learning curve of the RL agent compared to BC model on $10\times
10$ tables.

## Experiments

### Data Collection

The goal entries in $\mathbf{g}$ are selected randomly and remain fixed. The
initial state is also randomly generated, and we randomly generate forbidden
entries and fill in other entries with random numbers. To start an episode, we
randomly initialize the starting table $\mathbf{s}$. To improve the training
stability, we add lower and upper bounds on the 1-margins, i.e.,
$LB\leq\sum_{i}\mathbf{s}_{i}\leq UB$. As a result, the 1-margins are fully
specified by the initial state and remain the same throughout the episode. The
moves of the demonstrating greedy algorithm are calculated state-by-state by
selecting a valid move that maximizes the values of the entries in
$\mathcal{G}$.

### Network Architecture and Baseline

The actor and critics are parameterized by convolutional neural networks.
networks consist of multiple convolutional blocks where each block has a
convolution layer followed by batch normalization (BN) and ReLU. The number of
blocks depends on the size of the board. All convolution layers maintain the
same spatial dimensions. The final block of the actor network has a
convolution layer followed by tanh. In the critic network, we apply a global
average pooling layer before the final linear layer to predict the $Q$ value.

We also train a baseline model on the demonstration set using behavior cloning
(BC) (Ross, Gordon, and Bagnell 2010; Osa et al. 2018). The BC model is also a
neural network with the same architecture as the actor network.

### Training Details

We collect 100 demonstrations prior to the RL training and we sample $10\%$ of
transitions from the demonstration buffer for every mini-batch update. We use
Adam (Kingma and Ba 2015) as the optimizer with a learning rate $10^{-4}$ for
both actor and critics. The discount factor $\gamma$ is $0.99$. We use a batch
size of $32$. The exploration of DDPG-styled algorithm is achieved by adding a
Gaussian noise to the actor $\mathbf{a}=\pi_{\phi}(\mathbf{s})+\epsilon.$ We
use $\epsilon\sim\mathcal{N}(0,0.2)$ throughout the experiment.

Figure 4: The learning curve of the RL agent compared to BC model on $20\times
20$ tables.

### Results

To demonstrate the ability of our method to learn complex moves, we test our
agent on 2-way table of various grid (table) sizes with increasing maximum
elements. Larger maximum entries in the table would lead to longer horizons.
The results on $5\times 5$ table games is shown in Figure 2. The mean negative
episode length is shown in as the curve and the shaded region denotes the half
standard deviation. The BC model can achieve relatively good performance but
deteriorates as the upper bound on the entry increases. The RL model
outperforms the BC model by a margin and the advantage becomes more
significant with larger upper bounds. In Figure 3 we observe similar
performance on $10\times 10$ games. We tested three 1-margin bounds
$\\{20,30,50\\}$. The BC model does not perform well even with $UB=20$. On the
other hand, our RL agent is able to consistently reach the goal tables with
relatively short paths. The results on $20\times 20$ tables are shown in
Figure 4. The increase of the grid size also increases the action space
exponentially. The RL agent can solve the problem whereas the BC model has a
very low success rate and it takes longer steps to reach the goal state.

### Generalization Test

$UB$ | $20$ | $40$ | $60$ | $80$ | $100$ | $140$
---|---|---|---|---|---|---
$GS=5$ | $1.0$ | $1.0$ | $0.90$ | $0.60$ | $0.72$ | $0.39$
$GS=10$ | $1.0$ | $1.0$ | $0.79$ | $0.49$ | $0.34$ | $0.32$
Table 1: We test the trained model with margin bound $20$ on increased margins
and compare the how the success rate varies. The success rates drop as we
increase the bound, but the model is able to maintain a decent success rate
which shows its generalization ability.

In this section we wonder if the model can solve games that are unseen in the
training data. We set up the experiment by training the model on the fixed
upper 1-margin bound $20$ with grid size $5$ and $10$, and test its success
rates on larger bounds with the same corresponding grid size. The results in
Table 1 demonstrate that the trained model can solve games that it never
experiences during the policy training step. This further suggests that the
model can successfully recognize patterns in the table and produces
corresponding moves regardless of their magnitudes.

## Conclusions and Future Work

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.

## References

  * Bengio, Léonard, and Courville (2013) Bengio, Y.; Léonard, N.; and Courville, A. C. 2013.  Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation.  _CoRR_ , abs/1308.3432.
  * Bertsekas and Tsitsiklis (1991) Bertsekas, D. P.; and Tsitsiklis, J. N. 1991.  An Analysis of Stochastic Shortest Path Problems.  16(3): 580–595.
  * Bertsekas and Yu (2013) Bertsekas, D. P.; and Yu, H. 2013.  Stochastic Shortest Path Problems Under Weak Conditions.
  * Cox, Little, and O’Shea (2005) Cox, D. A.; Little, J.; and O’Shea, D. 2005.  _Using algebraic geometry_ , volume 185 of _Graduate Texts in Mathematics_.  Springer, New York, second edition.  ISBN 0-387-20706-6.
  * De Loera, Hemmecke, and Köppe (2013) De Loera, J. A.; Hemmecke, R.; and Köppe, M. 2013.  _Algebraic and geometric ideas in the theory of discrete optimization_ , volume 14 of _MOS-SIAM Series on Optimization_.  Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA.  ISBN 978-1-611972-43-6.
  * De Loera and Onn (2004a) De Loera, J. A.; and Onn, S. 2004a.  All Rational Polytopes Are Transportation Polytopes and All Polytopal Integer Sets Are Contingency Tables.  In Nemhauser, G. L.; and Bienstock, D., eds., _Integer Programming and Combinatorial Optimization, 10th International IPCO Conference, New York, NY, USA, June 7-11, 2004, Proceedings_ , volume 3064 of _Lecture Notes in Computer Science_ , 338–351. Springer.
  * De Loera and Onn (2004b) De Loera, J. A.; and Onn, S. 2004b.  The Complexity of Three-Way Statistical Tables.  _SIAM J. Comput._ , 33(4): 819–836.
  * Dulac-Arnold et al. (2015) Dulac-Arnold, G.; Evans, R.; Sunehag, P.; and Coppin, B. 2015.  Reinforcement Learning in Large Discrete Action Spaces.  _CoRR_ , abs/1512.07679.
  * Fujimoto, van Hoof, and Meger (2018) Fujimoto, S.; van Hoof, H.; and Meger, D. 2018.  Addressing Function Approximation Error in Actor-Critic Methods.  _CoRR_ , abs/1802.09477.
  * Guo et al. (2016) Guo, X.; Singh, S.; Lewis, R. L.; and Lee, H. 2016.  Deep Learning for Reward Design to Improve Monte Carlo Tree Search in ATARI Games.  In Kambhampati, S., ed., _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016_ , 1519–1525. IJCAI/AAAI Press.
  * Hoşten and Sullivant (2002) Hoşten, S.; and Sullivant, S. 2002.  Gröbner bases and polyhedral geometry of reducible and cyclic models.  _J. Combin. Theory Ser. A_ , 100(2): 277–301.
  * Hoffman (1963) Hoffman, A. J. 1963.  On simple linear programming problems.  In _Proc. Sympos. Pure Math., Vol. VII_ , 317–327. Amer. Math. Soc., Providence, R.I.
  * Kingma and Ba (2015) Kingma, D. P.; and Ba, J. 2015.  Adam: A Method for Stochastic Optimization.  In _3rd International Conference on Learning Representations, ICLR 2015_.
  * Lillicrap et al. (2016) Lillicrap, T. P.; Hunt, J. J.; Pritzel, A.; Heess, N.; Erez, T.; Tassa, Y.; Silver, D.; and Wierstra, D. 2016.  Continuous control with deep reinforcement learning.  In _ICLR_.
  * Mnih et al. (2015) Mnih, V.; Kavukcuoglu, K.; Silver, D.; Rusu, A. A.; Veness, J.; Bellemare, M. G.; Graves, A.; Riedmiller, M. A.; Fidjeland, A.; Ostrovski, G.; Petersen, S.; Beattie, C.; Sadik, A.; Antonoglou, I.; King, H.; Kumaran, D.; Wierstra, D.; Legg, S.; and Hassabis, D. 2015.  Human-level control through deep reinforcement learning.  _Nature_ , 518(7540): 529–533.
  * Nair et al. (2017) Nair, A.; McGrew, B.; Andrychowicz, M.; Zaremba, W.; and Abbeel, P. 2017.  Overcoming Exploration in Reinforcement Learning with Demonstrations.  _CoRR_ , abs/1709.10089.
  * Osa et al. (2018) Osa, T.; Pajarinen, J.; Neumann, G.; Bagnell, J. A.; Abbeel, P.; and Peters, J. 2018\.  An Algorithmic Perspective on Imitation Learning.  _CoRR_ , abs/1811.06711.
  * Ross, Gordon, and Bagnell (2010) Ross, S.; Gordon, G. J.; and Bagnell, J. A. 2010.  No-Regret Reductions for Imitation Learning and Structured Prediction.  _CoRR_ , abs/1011.0686.
  * Rudolf (1998) Rudolf, R. 1998.  On Monge sequences in $d$-dimensional arrays.  _Linear Algebra Appl._ , 268: 59–70.
  * Silver et al. (2017) Silver, D.; Schrittwieser, J.; Simonyan, K.; Antonoglou, I.; Huang, A.; Guez, A.; Hubert, T.; Baker, L.; Lai, M.; Bolton, A.; Chen, Y.; Lillicrap, T. P.; Hui, F.; Sifre, L.; van den Driessche, G.; Graepel, T.; and Hassabis, D. 2017\.  Mastering the game of Go without human knowledge.  _Nat._ , 550(7676): 354–359.
  * Sturmfels (1996) Sturmfels, B. 1996.  _Gröbner bases and convex polytopes_ , volume 8 of _University Lecture Series_.  American Mathematical Society, Providence, RI.  ISBN 0-8218-0487-1.
  * van den Oord, Vinyals, and kavukcuoglu (2017) van den Oord, A.; Vinyals, O.; and kavukcuoglu, k. 2017.  Neural Discrete Representation Learning.  In Guyon, I.; Luxburg, U. V.; Bengio, S.; Wallach, H.; Fergus, R.; Vishwanathan, S.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Vinyals et al. (2019) Vinyals, O.; Babuschkin, I.; Czarnecki, W. M.; Mathieu, M.; Dudzik, A.; Chung, J.; Choi, D. H.; Powell, R.; Ewalds, T.; Georgiev, P.; Oh, J.; Horgan, D.; Kroiss, M.; Danihelka, I.; Huang, A.; Sifre, L.; Cai, T.; Agapiou, J. P.; Jaderberg, M.; Vezhnevets, A. S.; Leblond, R.; Pohlen, T.; Dalibard, V.; Budden, D.; Sulsky, Y.; Molloy, J.; Paine, T. L.; Gülçehre, Ç.; Wang, Z.; Pfaff, T.; Wu, Y.; Ring, R.; Yogatama, D.; Wünsch, D.; McKinney, K.; Smith, O.; Schaul, T.; Lillicrap, T. P.; Kavukcuoglu, K.; Hassabis, D.; Apps, C.; and Silver, D. 2019.  Grandmaster level in StarCraft II using multi-agent reinforcement learning.  _Nat._ , 575(7782): 350–354.
  * Yemelichev, Kovalëv, and Kravtsov (1984) Yemelichev, V. A.; Kovalëv, M. M.; and Kravtsov, M. K. 1984.  _Polytopes, graphs and optimisation_.  Cambridge University Press, Cambridge.  ISBN 0-521-25597-X.  Translated from the Russian by G. H. Lawden.

## Appendix

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.

### Proofs of Lemma 2 and Theorem 5

###### Proof. (Lemma 2).

If $X\neq X^{\prime}$ it is clear that either $X\succ_{*}X^{\prime}$ or
$X^{\prime}\succ_{*}X$, and the relation is compatible with adding the same
table $Y$ to $X$ and $X^{\prime}$. So we just need to show that $\succ^{*}$ is
transitive. So let $X\succ_{*}X^{\prime}$ and
$X^{\prime}\succ_{*}X^{\prime\prime}$. There is a total of nine possibilities
to be checked depending on how the tables are aligned, so we give one of these
for illustration. Suppose $X\succ_{*}X^{\prime}$ because
$Proj_{x,z}(X)=Proj_{x,z}(X^{\prime})$ but
$Proj_{y,z}(X)\succ^{2}Proj_{y,z}(X^{\prime})$, and also suppose that
$X^{\prime}\succ_{*}X^{\prime\prime}$ because
$Proj_{x,z}(X^{\prime})\succ^{1}Proj_{x,z}(X^{\prime\prime})$. Then
$Proj_{x,z}(X)=Proj_{x,z}(X^{\prime})\succ^{1}Proj_{x,z}(X^{\prime\prime})$.
Hence $X\succ_{*}X^{\prime\prime}$. ∎

###### Proof.

(of Theorem 5) First we show that if $P$ is feasible then the $w_{x,z}$-weight
of $Proj_{x,z}(W)$ and the $w_{y,z}$-weight of $Proj_{y,z}(W)$ must be zero.
Suppose $U$ is a table corresponding to a feasible solution of $P$. Then
clearly the $w_{x,z}$-weight of $Proj_{x,z}(U)$ and the $w_{y,z}$-weight of
$Proj_{y,z}(U)$ are zero. But then if one of these weights for $W$ were bigger
than zero we would get a contradiction to the assumption that $W$ is the
unique sink obtained by reduction of $V$ with respect to $\succ_{*}$. Now
because the $w_{x,z}$-weight of both $Proj_{x,z}(W)$ and $Proj_{x,z}(U)$ are
zero, and since $Proj_{x,z}(W)$ is the unique sink of $2$-way $l\times n$
tables with row and column sums equal to those of $Proj_{x,z}(V)$, there is a
sequence of Gröbner basis elements in $G_{x,z}$ which reduce $Proj_{x,z}(U)$
to $Proj_{x,z}(W)$. These elements must have $w_{x,z}$-weight zero. This means
that we can reverse these moves and use their liftings to obtain a table
$W^{\prime}$ such that $Proj_{x,z}(W^{\prime})=Proj_{x,z}(U)$. Note that
$Proj_{y,z}(W^{\prime})=Proj_{y,z}(W)$, and we can use the same argument above
to conclude that one can reach to a table $T$ using lifted elements of
$G_{y,z}$ with $w_{y,z}$-weight zero such that $Proj_{y,z}(T)=Proj_{y,z}(U)$.
Of course, we also have $Proj_{x,z}(T)=Proj_{x,z}(U)$. The table $T$ will be
an element of $\mathcal{S}$ in Step 4 above, if we use the (reversed) elements
of $G_{x,z}$ and $G_{y,z}$ of respective weights zero to generate all possible
$2$-way $l\times n$ and $m\times n$ tables with the same row and column sums
as $Proj_{x,z}(W)$ and $Proj_{y,z}(W)$. By this construction, for each $1\leq
k\leq n$ the horizontal slices $T_{k}$ and $U_{k}$ have identical row and
column sums. Since the $w_{k}$-weight of $U_{k}$ is zero, if the same weight
of $T_{k}$ is not zero, one can find a sequence of Gröbner basis elements in
$G_{\succ_{k}}$ (and hence in
$\mathcal{F}(G_{\succ_{1}},\ldots,G_{\succ_{n}})$) to obtain $X$ where the
$w_{k}$-weight of $X_{k}$ is zero. Because
$Proj_{x,z}(X)=Proj_{x,z}(T)=Proj_{x,z}(U)$ and
$Proj_{y,z}(X)=Proj_{y,z}(T)=Proj_{y,z}(U)$, the table $X$ corresponds to a
feasible solution of $P$. ∎

### Preprocessing: Coefficient Reduction

Let $P=\\{y\geq 0:Ay=b\\}$ where $A=(a_{i,j})$ is an integer matrix and $b$ is
an integer vector. We represent it as a polytope $Q=\\{x\geq 0:Cx=d\\}$, in
polynomial-time, with a $\\{-1,0,1,2\\}$-valued matrix $C=(c_{i,j})$ of
coefficients, as follows. Consider any variable $y_{j}$ and let
$k_{j}:=\max\\{\lfloor\log_{2}|a_{i,j}|\rfloor\,:\,i=1,\dots m\\}$ be the
maximum number of bits in the binary representation of the absolute value of
any $a_{i,j}$. We introduce variables $x_{j,0},\dots,x_{j,k_{j}}$, and relate
them by the equations $2x_{j,i}-x_{j,i+1}=0$. The representing injection
$\sigma$ is defined by $\sigma(j):=(j,0)$, embedding $y_{j}$ as $x_{j,0}$.
Consider any term $a_{i,j}\,y_{j}$ of the original system. Using the binary
expansion $|a_{i,j}|=\sum_{s=0}^{k_{j}}t_{s}2^{s}$ with all
$t_{s}\in\\{0,1\\}$, we rewrite this term as
$\pm\sum_{s=0}^{k_{j}}t_{s}x_{j,s}$. It is easy to see that this procedure
provides a new representation, and we get the following.

######  Lemma 3.

Any rational polytope $P=\\{y\geq 0:Ay=b\\}$ is polynomial-time representable
as a polytope $Q=\\{x\geq 0:Cx=d\\}$ with $\\{-1,0,1,2\\}$-valued defining
matrix $C$.

### Representing Polytopes as 3-way Transportation Polytopes with 1-marginals
and forbidden entries

Let $P=\\{y\geq 0:Ay=b\\}$ where $A=(a_{i,j})$ is an $m\times n$ integer
matrix and $b$ is an integer vector: we assume that $P$ is bounded and hence a
polytope, with an integer upper bound $U$ (which can be derived from the
Cramer’s rule bound) on the value of any coordinate $y_{j}$ of any $y\in P$.

For each variable $y_{j}$, let $r_{j}$ be the largest between the sum of the
positive coefficients of $y_{j}$ over all equations and the sum of absolute
values of the negative coefficients of $y_{j}$ over all equations,

$r_{j}\,:=\,\max\left(\sum_{k}\\{a_{k,j}:a_{k,j}>0\\}\,,\,\sum_{k}\\{|a_{k,j}|:a_{k,j}<0\\}\right)\
.$

Let $r:=\sum_{j=1}^{n}r_{j}$, $R:=\\{1,\dots,r\\}$, $h:=m+1$ and
$H:=\\{1,\dots,h\\}$. We now describe how to construct vectors
$u,v\in\mathbb{Z}^{r},w\in\mathbb{Z}^{h}$, and a set $E\subset R\times R\times
H$ of triples - the “enabled”, non-“forbidden” entries - such that the
polytope $P$ is represented as the corresponding transportation polytope of
$r\times r\times h$ arrays with plane-sums $u,v,w$ and only entries indexed by
$E$ enabled,

$\displaystyle T\,=\,\\{\,x\in\mathbb{R}_{\geq 0}^{r\times r\times h}\ \,|\,\
x_{i,j,k}=0\ \,\mbox{for all}\ \,(i,j,k)\notin E\,,\,\ \,\mbox{and}\
\,\sum_{i,j}x_{i,j,k}=w_{k}\,,\ \sum_{i,k}x_{i,j,k}=v_{j}\,,\
\sum_{j,k}x_{i,j,k}=u_{i}\,\\}\ .$

We also indicate the injection $\sigma:\\{1,\dots,n\\}\longrightarrow R\times
R\times H$ giving the desired embedding of the coordinates $y_{j}$ as the
coordinates $x_{i,j,k}$ and the representation of $P$ as $T$ (see paragraph
following Theorem 1).

Basically, each equation $k=1,\dots,m$ will be encoded in a “horizontal plane”
$R\times R\times\\{k\\}$ (the last plane $R\times R\times\\{h\\}$ is included
for consistency and its entries can be regarded as “slacks”); and each
variable $y_{j}$, $j=1,\dots,n$ will be encoded in a “vertical box”
$R_{j}\times R_{j}\times H$, where $R=\biguplus_{j=1}^{n}R_{j}$ is the natural
partition of $R$ with $|R_{j}|=r_{j}$, namely with
$R_{j}:=\\{1+\sum_{l<j}r_{l},\dots,\sum_{l\leq j}r_{l}\\}$.

Now, all “vertical” plane-sums are set to the same value $U$, that is,
$u_{j}:=v_{j}:=U$ for $j=1,\dots,r$. All entries not in the union
$\biguplus_{j=1}^{n}R_{j}\times R_{j}\times H$ of the variable boxes will be
forbidden. We now describe the enabled entries in the boxes; for simplicity we
discuss the box $R_{1}\times R_{1}\times H$, the others being similar. We
distinguish between the two cases $r_{1}=1$ and $r_{1}\geq 2$. In the first
case, $R_{1}=\\{1\\}$; the box, which is just the single line
$\\{1\\}\times\\{1\\}\times H$, will have exactly two enabled entries
$(1,1,k^{+}),(1,1,k^{-})$ for suitable $k^{+}$, $k^{-}$ to be defined later.
We set $\sigma(1):=(1,1,k^{+})$, namely embed $y_{1}=x_{1,1,k^{+}}$. We define
the complement of the variable $y_{1}$ to be ${\bar{y}}_{1}:=U-y_{1}$ (and
likewise for the other variables). The vertical sums $u,v$ then force
${\bar{y}}_{1}=U-y_{1}=U-x_{1,1,k^{+}}=x_{1,1,k^{-}}$, so the complement of
$y_{1}$ is also embedded. Next, consider the case $r_{1}\geq 2$. For each
$s=1,\dots,r_{1}$, the line $\\{s\\}\times\\{s\\}\times H$ (respectively,
$\\{s\\}\times\\{1+(s\,\mbox{mod\,}r_{1})\\}\times H$) will contain one
enabled entry $(s,s,k^{+}(s))$ (respectively,
$(s,1+(s\,\mbox{mod\,}r_{1}),k^{-}(s))$. All other entries of $R_{1}\times
R_{1}\times H$ will be forbidden. Again, we set $\sigma(1):=(1,1,k^{+}(1))$,
namely embed $y_{1}=x_{1,1,k^{+}(1)}$; it is then not hard to see that, again,
the vertical sums $u,v$ force $x_{s,s,k^{+}(s)}=x_{1,1,k^{+}(1)}=y_{1}$ and
$x_{s,1+(s\,\mbox{mod\,}r_{1}),k^{-}(s)}=U-x_{1,1,k^{+}(1)}={\bar{y}}_{1}$ for
each $s=1,\dots,r_{1}$. Therefore, both $y_{1}$ and ${\bar{y}}_{1}$ are each
embedded in $r_{1}$ distinct entries.

To clarify the above description it is helpful to visualize the $R\times R$
matrix $(x_{i,j,+})$ whose entries are the vertical line-sums
$x_{i,j,+}:=\sum_{k=1}^{h}x_{i,j,k}$.

Next we encode the equations by defining the horizontal plane-sums $w$ and the
indices $k^{+}(s),k^{-}(s)$ above as follows. For $k=1,\dots,m$, consider the
$k$th equation $\sum_{j}a_{k,j}y_{j}=b_{k}$. Define the index sets
$J^{+}:=\\{j:a_{k,j}>0\\}$ and $J^{-}:=\\{j:a_{k,j}<0\\}$, and set
$w_{k}:=b_{k}+U\cdot\sum_{j\in J^{-}}|a_{k,j}|$. The last coordinate of $w$ is
set for consistency with $u,v$ to be $w_{h}=w_{m+1}:=r\cdot
U-\sum_{k=1}^{m}w_{k}$. Now, with ${\bar{y}}_{j}:=U-y_{j}$ the complement of
variable $y_{j}$ as above, the $k$-th equation can be rewritten as

$\displaystyle\sum_{j\in J^{+}}a_{k,j}y_{j}+\sum_{j\in
J^{-}}|a_{k,j}|{\bar{y}_{j}}=\sum_{j=1}^{n}a_{k,j}y_{j}+U\cdot\sum_{j\in
J^{-}}|a_{k,j}|=b_{k}+U\cdot\sum_{j\in J^{-}}|a_{k,j}|=w_{k}.$

To encode this equation, we simply “pull down” to the corresponding $k$th
horizontal plane as many copies of each variable $y_{j}$ or ${\bar{y}}_{j}$ by
suitably setting $k^{+}(s):=k$ or $k^{-}(s):=k$. By the choice of $r_{j}$
there are sufficiently many, possibly with a few redundant copies which are
absorbed in the last hyperplane by setting $k^{+}(s):=m+1$ or $k^{-}(s):=m+1$.
For instance, if $m=8$, the first variable $y_{1}$ has $r_{1}=3$ as above, its
coefficient $a_{4,1}=3$ in the fourth equation is positive, its coefficient
$a_{7,1}=-2$ in the seventh equation is negative, and $a_{k,1}=0$ for $k\neq
4,7$, then we set $k^{+}(1)=k^{+}(2)=k^{+}(3):=4$ (so $\sigma(1):=(1,1,4)$
embedding $y_{1}$ as $x_{1,1,4}$), $k^{-}(1)=k^{-}(2):=7$, and
$k^{-}(3):=h=9$.

This way, all equations are suitably encoded, and Theorem 1 follows from the
construction outlined above and Lemma 3.

######  Theorem 1 (Restated).

Any rational polytope $P=\\{y\in\mathbb{R}_{\geq 0}^{n}:Ay=b\\}$ is
polynomial-time representable as a plane-sum entry-forbidden $3$-way
transportation polytope

$\displaystyle T\ =\ \\{\,x\in\mathbb{R}_{\geq 0}^{r\times r\times h}\ \,|\,\
x_{i,j,k}=0\ \,\mbox{for all}\ \,(i,j,k)\notin E\,,\,\ \,\mbox{and}\
\,\sum_{i,j}x_{i,j,k}=w_{k}\,,\ \sum_{i,k}x_{i,j,k}=v_{j}\,,\
\sum_{j,k}x_{i,j,k}=u_{i}\,\\}\ .$