Mixed-Integer Linear Representability, Disjunctions, and Variable Elimination

Abstract

Jeroslow and Lowe gave an exact geometric characterization of subsets of $\mathbb R^n$ that are projections of mixed-integer linear sets, a.k.a MILP-representable sets. We give an alternate algebraic characterization by showing that a set is MILP-representable if and only if the set can be described as the intersection of finitely many affine Chvátal inequalities. These inequalities are a modification of a concept introduced by Blair and Jeroslow. This gives a sequential variable elimination scheme that, when applied to the MILP representation of a set, explicitly gives the affine Chvátal inequalities characterizing the set. This is related to the elimination scheme of Wiliams and Williams-Hooker, who describe projections of integer sets using disjunctions of affine Chvátal systems. Our scheme extends their work in two ways. First, we show that disjunctions are unnecessary, by showing how to find the affine Chvátal inequalities that cannot be discovered by the Williams-Hooker scheme. Second, disjunctions of Chvátal systems can give sets that are not projections of mixed-integer linear sets; so the Williams-Hooker approach does not give an exact characterization of MILP representability.

A. Basu—Supported by the NSF grant CMMI1452820.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Researchers are interested in characterizing sets that are projections of mixed-integer sets described by linear constraints. Such sets have been termed MILP-representable sets; see [8] for a thorough survey. Knowing which sets are MILP-representable is important because of the prevalence of good algorithms and software for solving MILP formulations. Therefore, if one encounters an application that can be modeled using MILP-representable sets, then this sophisticated technology can be used to solve the application.

A seminal result of Jeroslow and Lowe [4] provides a geometric characterization of MILP-representable sets as the sum of a finitely generated monoid, and a disjunction of finitely many polytopes (see Theorem 1 below for a precise statement). An algebraic approach based on an explicit elimination scheme for integer variables was first developed by Williams in [9,10,11]. Williams (and later Williams and Hooker) adapted the Fourier-Motzkin elimination approach for linear inequalities to handle integer variables. Balas, in [1], also explores how to adapt Fourier-Motzkin elimination in the case of binary variables. In both instances, there is a need to introduce disjunctions of inequalities that involve either rounding operations or congruence relations. We emphasize that the geometric approach of Jeroslow-Lowe and the algebraic approach of Williams-Hooker-Balas both require the use of disjunctions.

Our point of departure is that we provide a constructive algebraic characterization of MILP-representability that does not need disjunctions, but instead makes use of affine Chvátal inequalities, i.e. affine linear inequalities with rounding operations (for a precise definition see Definition 1 below). We show that MILP-representable sets are exactly those sets that satisfy a finite system of affine Chvátal inequalities. In contrast, Williams and Hooker [9,10,11] require disjunctions of systems of affine Chvátal inequalities. Another disadvantage in their work is the following: there exist sets given by disjunctions of affine Chvátal systems that are not MILP-representable. Finally, our proof of the non-disjunctive characterization is constructive and implies a sequential variable elimination scheme for mixed-integer linear sets (see Sect. 5).

We thus simultaneously show three things: (1) disjunctions are not necessary for MILP-representability (if one allows affine Chvátal inequalities), an operation that shows up in both the Jeroslow-Lowe and the Williams-Hooker approaches, (2) our algebraic characterization comes with a variable elimination scheme, which is an advantage, in our opinion, to the geometric approach of Jeroslow-Lowe, and (3) our algebraic characterization is exact, as opposed to the algebraic approach of Williams-Hooker, whose algebraic descriptions give a strictly larger family of sets than MILP-representable sets.

Our algebraic characterization could be useful to obtain other insights into the structure of MIP representable sets that is not apparent from the geometric perspective. As an illustration, we resolve an open question posed in Ryan [6] on the representability of integer monoids using our characterization. Theorem 1 in [6] shows that every finitely-generated integer monoid can be described as a finite system of Chvátal inequalities but leaves open the question of how to construct the associated Chvátal functions via elimination. Ryan states that the elimination methods of Williams in [9, 10] do not address her question because of the introduction of disjunctions. Our work provides a constructive approach for finding a Chvátal inequality representation of finitely-generated integer monoids using elimination.

Our new algebraic characterization could also lead to novel algorithmic ideas where researchers optimize by directly working with affine Chvatal functions, rather than using traditional branch-and-cut/cutting plane type of methods for mixed-integer optimization.

2 Preliminaries

${\mathbb Z}, {\mathbb Q}, \mathbb R$ denote the set of integers, rational numbers and reals, respectively. Any of these sets subscripted by a plus means the nonnegative elements of that set. For instance, ${\mathbb Q}_+$ is the set of nonnegative rational numbers. The projection operator $\mathrm {proj}_Z$ where $Z \subseteq \left\{ x_1, \dots , x_n\right\}$ projects a vector $x \in \mathbb R^n$ onto the coordinates in Z. Following [4] we say a set $S \subseteq \mathbb R^n$ is mixed integer linear representable (or MILP-representable) if there exists rational matrices A, B, C and a rational vector d such that

$$\begin{aligned} S = \mathrm {proj}_x \left\{ (x,y,z) \in \mathbb R^n \times \mathbb R^p \times {\mathbb Z}^q : Ax + By + Cz \ge d\right\} . \end{aligned}$$

(1)

The following is the main result from [4] stated as Theorem 4.47 in [3]:

Theorem 1

A set $S \subset \mathbb R^n$ is MILP-representable if and only if there exists rational polytopes $P_1, \dots , P_k \subseteq \mathbb R^n$ and vectors $r^1, \dots , r^t \in {\mathbb Z}^n$ such that

$$\begin{aligned} S = \bigcup _{i=1}^k P_i + \mathrm {intcone}\left\{ r^1, \dots , r^t\right\} , \end{aligned}$$

(2)

where $\mathrm {intcone}\left\{ r^1, \dots , r^t\right\}$ denotes the set of nonnegative integer linear combinations of $r^1, \ldots , r^t$.

The ceiling operator $\lceil a \rceil$ gives the smallest integer no less than $a \in \mathbb R$. Chvátal functions, first introduced by [2], are obtained by taking linear combinations of linear functions and using the ceiling operator. We extend this original definition to allow for affine linear functions, as opposed to homogenous linear functions. Consequently, we term our functions affine Chvátal functions. We use the concept of finite binary trees from [5] to formally define these functions.

Definition 1

An affine Chvátal function $f:\mathbb R^n\rightarrow \mathbb R$ is constructed as follows. We are given a finite binary tree where each node of the tree is either: (i) a leaf, which corresponds to an affine linear function on $\mathbb R^n$ with rational coefficients; (ii) has one child with corresponding edge labeled by either a $\lceil \cdot \rceil$ or a number in ${\mathbb Q}_+$, or (iii) has two children, each with edges labelled by a number in ${\mathbb Q}_+$.

The function f is built as follows. Start at the root node and (recursively) form functions corresponding to subtrees rooted at its children. If the root has a single child whose subtree is g, then either (a) $f = \lceil g \rceil$ if the corresponding edge is labeled $\lceil \cdot \rceil$ or (b) $f = \alpha g$ if the corresponding edge is labeled by $a \in {\mathbb Q}_+$. If the root has two children with corresponding edges labeled by $a \in {\mathbb Q}_+$ and $b \in {\mathbb Q}_+$ then $f = ag + bh$ where g and h are functions corresponding to the respective children of the root.¹

The depth of a binary tree representation T of an affine Chvátal function is the length of the longest path from the root to a node in T, and $\mathrm {cc}(T)$ denotes the ceiling count of T, i.e., the total number of edges of T labeled $\lceil \cdot \rceil$.

The original definition of Chvátal function in the literature requires the leaves of the binary tree to be linear functions, and the domain of the function to be ${\mathbb Q}^n$ (see [2, 5, 6]). Our definition above allows for affine linear functions at the leaves, and the domain of the functions to be $\mathbb R^n$. We use the term Chvátal function, as opposed to affine Chvátal function, to refer to the setting where the leaves are linear functions. In this paper, the domain of all functions is $\mathbb R^n$.

An inequality $f(x) \le b$, where f is an affine Chvátal function and $b\in \mathbb R$, is called an affine Chvátal inequality. A mixed-integer Chvátal (MIC) set is a mixed-integer set described by finitely many affine Chvátal inequalities. That is, a set S is a mixed integer Chvátal set if there exist affine Chvátal functions $f_i$ and $b_i \in \mathbb R$ for $i = 1, \dots , m$ such that $S = \{ (x,z) \in \mathbb R^n \times {\mathbb Z}^q : f_i(x,z) \le b_i \text { for } i = 1, \dots , m \}.$ A set S is a disjunctive mixed-integer Chvátal (DMIC) set if there exist affine Chvátal functions $f_{ij}$ and $b_{ij} \in \mathbb R$ for $i = 1, \dots , m$ and $j = 1, \dots , t$ such that $S = \bigcup _{j = 1}^t \{ (x,z) \in \mathbb R^n \times {\mathbb Z}^q : f_{ij}(x,z) \le b_{ij} \text { for } i = 1, \dots , m \}.$

3 MILP-representable Sets as DMIC Sets

From the perspective of MILP-representability, the following result summarizes the work in [9,10,11] that relates affine Chvátal functions and projections of integer variables.

Theorem 2

Every MILP-representable set is a DMIC set.

Theorem 2 is not explicitly stated in [9,10,11], even though it summarizes the main results of these papers, for two reasons: (i) the development in [11] works with linear congruences and inequalities as constraints and not affine Chvátal inequalities and (ii) they only treat the pure integer case. These differences are only superficial. For (i), an observation due to Ryan in [6] shows that congruences can always be expressed equivalently as affine Chvátal inequalities. For (ii), continuous variables (the y variables in (1)) can first be eliminated using Fourier-Motzkin elimination, which introduces no complications.

The converse of Theorem 2 is not true. As the following example illustrates, not every DMIC set is MILP-representable.

Example 1

Consider the set $E {:=} \{(\lambda , 2\lambda ): \lambda \in {\mathbb Z}_+\} \cup \{(2\lambda , \lambda ): \lambda \in {\mathbb Z}_+\}$ as illustrated in Fig. 1. This set is a DMIC set because it can be expressed as $E =\{x \in {\mathbb Z}^2_+ : 2x_1 - x_2 = 0\} \cup \{x \in {\mathbb Z}^2_+ : x_1 - 2x_2 = 0\}.$

Fig. 1.

A DMIC set that is not MILP-representable.

E is not the projection of any mixed integer linear program. Indeed, by Theorem 1 every MILP-representable set has the form (2). Suppose E has such a form. Consider the integer points in E of the form $(\lambda , 2 \lambda )$ for $\lambda \in {\mathbb Z}_+$. There are infinitely many such points and so cannot be captured inside of the finitely-many polytopes $P_k$ in (2). Thus, the ray $\lambda (1, 2)$ for $\lambda \in {\mathbb Z}_+$ must lie inside $\mathrm {intcone}\{r^1, \dots , r^t\}$. Identical reasoning implies the ray $\lambda (2,1)$ for $\lambda \in {\mathbb Z}_+$ must also lie inside $\mathrm {intcone}\{r^1, \dots , r^t\}$. But then, every conic integer combination of these two rays must lie in E. Observe that $(3,3) = (2,1) + (1,2)$ is one such integer combination but $(3,3) \notin E$. We conclude that E cannot be represented in the form (2) and hence E is not MILP-representable.

4 Characterization of MILP-representable Sets as MIC Sets

In this section we characterize MILP-representable sets as MIC sets. This is achieved in two steps across two subsections. The main results are Theorems 4 and 6, which are converses of each other.

4.1 MIC Sets are MILP-representable

We show how to “lift” a MIC set to a mixed-integer linear set. The idea is simple – replace ceiling operators with additional integer variables. However, we need to work with an appropriate representation of an affine Chvátal function in order to implement this idea. The next result provides the correct representation.

Theorem 3

For every affine Chvátal function f represented by a binary tree T, one of the following cases hold:  

Case 1::

$\mathrm {cc}(T) = 0$, which implies that f is an affine linear function.

Case 2::

$f = \gamma \lceil g_1 \rceil + g_2$, where $\gamma >0$ and $g_1, g_2$ are affine Chvátal functions such that there exist binary tree representations $T_1, T_2$ for $g_1, g_2$ respectively, with $\mathrm {cc}(T_1) + \mathrm {cc}(T_2) + 1 \le \mathrm {cc}(T)$.

 

Proof

We use induction on the depth of the binary tree T. For the base case, if T has depth 0, then $\text {cc}(T) = 0$ and we are in Case 1. The inductive hypothesis assumes that for some $k \ge 0$, every affine Chvátal function f with a binary tree representation T of depth less or equal to k, can be expressed in Case 1 or 2.

For the inductive step, consider an affine Chvátal function f with a binary tree representation T of depth $k + 1$. If the root node of T has a single child, let $T'$ be the subtree of T with root node equal to the child of the root node of T. We now consider two cases: the edge at the root node is labeled with a $\lceil \cdot \rceil$, or the edge is labeled with a scalar $\alpha > 0$. In the first case, $f = \lceil g \rceil$ where g is an affine Chvátal function which has $T'$ as a binary tree representation. Also, $\mathrm {cc}(T') + 1 = \mathrm {cc}(T)$. Thus, we are done by setting $g_1 = g$, $g_2 = 0$ and $\gamma = 1$. In the second case, $f = \alpha g$ where g is an affine Chvátal function which has $T'$ as a binary tree representation, with $\mathrm {cc}(T') = \mathrm {cc}(T)$. Note that $T'$ has smaller depth than T. Thus, we can apply the induction hypothesis on g with representation $T'$. If this ends up in Case 1, then $0 = \mathrm {cc}(T') = \mathrm {cc}(T)$ and f is in Case 1. Otherwise, we obtain $\gamma ' > 0$, affine Chvátal functions $g'_1, g'_2$, and binary trees $T'_1, T'_2$ representing $g'_1, g'_2$ respectively, with

$$\begin{aligned} \mathrm {cc}(T'_1) + \mathrm {cc}(T'_2) + 1 \le \mathrm {cc}(T') = \mathrm {cc}(T) \end{aligned}$$

(3)

such that $g = \gamma '\lceil g'_1 \rceil + g'_2$. Now set $\gamma = \alpha \gamma '$, $g_1 = g'_1$, $g_2 = \alpha g'_2$, $T_1 = T'_1$ and $T_2$ to be the tree whose root node has a single child with $T'_2$ as the subtree, and the edge at the root labeled with $\alpha$. Note that $\mathrm {cc}(T_2) = \mathrm {cc}(T'_2)$. Also, observe that $T_1, T_2$ represents $g_1, g_2$ respectively. Combined with (3), we obtain that $\mathrm {cc}(T_1) + \mathrm {cc}(T_2) + 1 \le \mathrm {cc}(T)$.

If the root node of T has two children, let $S_1, S_2$ be the subtrees of T with root nodes equal to the left and right child, respectively, of the root node of T. Then, $f = \alpha h_1 + \beta h_2$, where $\alpha , \beta >0$ and $h_1, h_2$ are affine Chvátal functions with binary tree representations $S_1, S_2$ respectively. Also note that the depths of $S_1, S_2$ are both strictly less than the depth of T, and

$$\begin{aligned} \mathrm {cc}(S_1) + \mathrm {cc}(S_2) = \mathrm {cc}(T) \end{aligned}$$

(4)

By the induction hypothesis applied to $h_1$ and $h_2$ with representations $S_1, S_2$, we can assume both of them end up in Case 1 or 2 of the statement of the theorem. If both of them are in Case 1, then $\mathrm {cc}(S_1) = \mathrm {cc}(S_2) = 0$, and by (4), $\mathrm {cc}(T) = 0$. So f is in Case 1.

Thus, we may assume that $h_1$ or $h_2$ (or both) end up in Case 2. There are three subcases, (i) $h_1, h_2$ are both in Case 2, (ii) $h_1$ is Case 2 and $h_2$ in Case 1, or (iii) $h_2$ in Case 2 and $h_1$ in Case 1. We analyze subcase (i), the other two subcases are analogous. This implies that there exists $\gamma '>0$, and affine Chvátal functions $g'_1$ and $g'_2$ such that $h_1 = \gamma ' \lceil g'_1 \rceil + g'_2$, and there exist binary tree representations $T'_1, T'_2$ for $g'_1, g'_2$ respectively, such that

$$\begin{aligned} \mathrm {cc}(T'_1) + \mathrm {cc}(T'_2) + 1 \le \mathrm {cc}(S_1). \end{aligned}$$

(5)

Now set $\gamma = \alpha \gamma '$, $g_1(x) = g'_1(x)$ and $g_2(x) = \alpha g'_2(x) + \beta h_2(x)$. Then $f = \gamma \lceil g_1 \rceil + g_2$. Observe that $g_2$ has a binary tree representation $T_2$ such that the root node of $T_2$ has two children: the subtrees corresponding to these children are $T'_2$ and $S_2$, and the edges at the root node of $T_2$ are labeled by $\alpha$ and $\beta$ respectively. Therefore,

$$\begin{aligned} \mathrm {cc}(T_2) \le \mathrm {cc}(T'_2) + \mathrm {cc}(S_2). \end{aligned}$$

(6)

Moreover, we can take $T_1 = T'_1$ as the binary tree representation of $g_1$. We observe that

$$\begin{aligned} \begin{array}{rcl} \mathrm {cc}(T_1) + \mathrm {cc}(T_2) + 1 &{}\le &{}\mathrm {cc}(T'_1) + \mathrm {cc}(T'_2) + \mathrm {cc}(S_2) + 1 \\ &{} \le &{} \mathrm {cc}(S_1) + \mathrm {cc}(S_2) = \mathrm {cc}(T) \end{array} \end{aligned}$$

where the first inequality is from the fact that $T_1 = T'_1$ and (6), the second inequality is from (5) and the final equation is (4).    $\square$

For a system of affine Chvátal inequalities where each affine Chvátal function is represented by a binary tree, the total ceiling count of this representation is the sum of the ceiling counts of all these binary trees. The next lemma shows how to reduce the total ceiling count of a MIC set by one, in exchange for an additional integer variable.

Lemma 1

Given a system $C=\{x \in \mathbb R^n\times \mathbb {Z}^q: ~ f_i(x) \le b_i\}$ of affine Chvátal inequalities with a total ceiling count $c \ge 1$, there exists a system $P=\{(x,z) \in \mathbb R^n\times \mathbb {Z}^q \times {\mathbb Z}: ~ f'_i(x) \le b'_i\}$ of affine Chvátal inequalities with a total ceiling count of at most $c-1$, and $C = \mathrm {proj}_{x}(P)$.

Proof

Since $c\ge 1$, at least one of the $f_i$ is given with a binary tree representation T with strictly positive ceiling count. Without loss of generality we assume it is $f_1$. This means $f_1$, along with its binary tree representation T, falls in Case 2 of Theorem 3. Therefore, one can write f as $f_1 = \gamma \lceil g_1 \rceil + g_2,$ with $\gamma >0$, and $g_1, g_2$ are affine Chvátal functions such that there exist binary tree representations $T_1, T_2$ for $g_1, g_2$ respectively, with $\mathrm {cc}(T_1) + \mathrm {cc}(T_2) + 1 \le \mathrm {cc}(T)$. Dividing by $\gamma$ on both sides, the inequality $f_1(x) \le b_1$ is equivalent to $\lceil g_1(x) \rceil +(1/\gamma ) g_2(x) \le b_1/\gamma .$ Moving $(1/\gamma ) g_2(x)$ to the right hand side, we get $\lceil g_1(x) \rceil \le -(1/\gamma ) g_2(x) + b_1/\gamma .$ This inequality is easily seen to be equivalent to two inequalities, involving an extra integer variable $z \in \mathbb {Z}$: $\lceil g_1(x) \rceil \le z \le - (1/\gamma ) g_2(x) + b_1 / \gamma ,$ which, in turn is equivalent to $g_1(x) \le z \le -(1/\gamma ) g_2(x) + b_1 / \gamma ,$ since $z \in \mathbb {Z}$. Therefore, we can replace the constraint $f_1(x) \le b_1$ with the two constraints

$$\begin{aligned}&g_1(x) - z \le 0, \end{aligned}$$

(7)

$$\begin{aligned}&(1/\gamma ) g_2(x) + z \le b_1/ \gamma \Leftrightarrow g_2(x) + \gamma z \le b_1 \end{aligned}$$

(8)

as long as we restrict $z \in {\mathbb Z}$. Note that the affine Chvátal functions on the left hand sides of (7) and (8) have binary tree representations with ceiling count equal to $\mathrm {cc}(T_1)$ and $\mathrm {cc}(T_2)$ respectively. Since $\mathrm {cc}(T_1) + \mathrm {cc}(T_2) + 1 \le \mathrm {cc}(T)$, the total ceiling count of the new system is at least one less than the total ceiling count of the previous system.   $\square$

The key result of this subsection is an immediate consequence.

Theorem 4

Every MIC set is MILP-representable.

Proof

Consider any system of affine Chvátal inequalities describing the MIC set, with total ceiling count $c \in {\mathbb N}$. Apply Lemma 1 at most c times to get the desired result.   $\square$

4.2 MIP-representable Sets Are MIC Sets

We now turn to showing the converse of Theorem 4, that every MILP-representable set is a MIC set (Theorem 6 below). This direction leverages some established theory in integer programming, in particular,

Theorem 5

For any rational $m \times n$ matrix A, there exists a finite set of Chvátal functions $f_i: \mathbb R^m \rightarrow \mathbb R$, $i\in I$ with the following property: for every $b\in \mathbb R^m$, $\{ x \in {\mathbb Z}^n \, : \, Ax \ge b\}$ is nonempty if and only if $f_i(b) \le 0$ for all $i\in I$. Moreover, these functions can be explicitly constructed from the matrix A.

The above result is quite similar to Corollary 23.4 in [7]. This result from [7] was originally obtained by Blair and Jeroslow in [2, Theorem 5.1]). This work in turn builds on seminal work on integer programming duality by Wolsey in [12]. Wolsey showed that the family of subadditive functions suffices to give a result like Theorem 5; Blair and Jeroslow improved this to show that the smaller family of Chvatal functions suffice. The main difference between Corollary 23.4 in [7] and our result here is that we allow the right hand side b to be non rational. This difference is indispensable in our analysis (see the proof of Theorem 6). Although our proof of Theorem 5 is conceptually similar to the approach in [7], we need to handle some additional technicalities related to irrationality. We omit this analysis from this extended abstract; it will be included in the full version. The following lemma is easy to verify.

Lemma 2

Let $T:\mathbb R^{n_1} \rightarrow \mathbb R^{n_2}$ be an affine transformation involving rational coefficients, and let $f:\mathbb R^{n_2} \rightarrow \mathbb R$ be an affine Chvátal function. Then $f\circ T :\mathbb R^{n_1} \rightarrow \mathbb R$ can be expressed as $f\circ T(x) = g(x)$ for some affine Chvátal function $g : \mathbb R^{n_1}\rightarrow \mathbb R$.

Theorem 6

Every MILP-representable set is a MIC set. Moreover, given an explicit inequality description of the MILP-representable set, the MIC set can be obtained algorithmically.

Proof

Let $m, n, p, q \in {\mathbb N}$. Let $A \in {\mathbb Q}^{m \times n}, B \in {\mathbb Q}^{m\times p}, C \in {\mathbb Q}^{m\times q}$ be any rational matrices, and let $d\in {\mathbb Q}^m$. Define $\mathcal {F} = \{(x,y,z) \in \mathbb R^n \times \mathbb R^p \times {\mathbb Z}^q \;: \;\;Ax + By + Cz \ge d\}.$ It suffices to show that the projection of $\mathcal {F}$ onto the x space is a MIC set.

By applying Fourier-Motzkin elimination on the y variables, we obtain rational matrices $A', C'$ with $m'$ rows for some natural number $m'$, and a vector $d'\in {\mathbb Q}^{m'}$ such that the projection of $\mathcal {F}$ onto the (x, z) space is given by $\overline{\mathcal {F}}:= \{(x,z) \in \mathbb R^n \times {\mathbb Z}^q \;: \;\;A'x + C'z \ge d'\}.$

Let $f_i:\mathbb R^{m'}\rightarrow \mathbb R$, $i\in I$ be the set of Chvátal functions obtained by applying Theorem 5 to the matrix $C'$. It suffices to show that the projection of $\overline{\mathcal {F}}$ onto the x space is $\hat{\mathcal {F}}:=\{x\in \mathbb R^n \;: \; f_i(d' - A'x) \le 0, \;\; i\in I\}$ since for every $i\in I$, $f_i(d' - A'x) \le 0$ can be written as $g_i(x) \le 0$ for some affine Chvátal function $g_i$, by Lemma 2.² This follows from the following sequence of equivalences.

   $\square$

Remark 1

We note in the proof of Theorem 6 that if the right hand side d of the mixed-integer set is 0, then the affine Chvátal functions $g_i$ are actually Chvátal functions. This follows from the fact that the function g in Lemma 2 is a Chvátal function if f is a Chvátal function and T is a linear transformation.

5 An Sequential Variable Elimination Scheme for Mixed-Integer Chvátal Sytems

Ryan shows (see Theorem 1 in [6]) that Y is a finitely generated integral monoid if and only if there exist Chvátal functions $f_{1}, \ldots , f_p$ such that $Y = \{ b \, : \, f_{i}(b) \le 0, \, i = 1, \ldots , p\}.$ By definition, a finitely generated integral monoid Y is MILP representable since $Y = \{ b \, : \, b = Ax, x \in {\mathbb Z}^{n}_{+}\}$ where A is an $m \times n$ integral matrix. Thus, an alternate proof of Ryan’s characterization follows from Theorems 4 and 6 and Remark 1.

Ryan [6] further states that “It is an interesting open problem to find an elimination scheme to construct the Chvátal constraints for an arbitrary finitely generated integral monoid.” The results of Sect. 4 provide such an elimination scheme, as we show below.

A number of authors have studied sequential projection algorithms for linear integer programs [1, 9,10,11]. However, their sequential projection algorithms do not resolve Ryan’s open question because they do not generate the Chvátal functions $f_{i}(b)$ required to describe Y. Below, we show that, in fact, all these schemes have to necessarily resort to the use of disjunctions because they try to adapt the classical Fourier-Motzkin procedure and apply it to the system $b = Ax, x \in {\mathbb Z}^{n}_{+}$.

Our resolution to Ryan’s open question hinges on the observation that the Chvátal functions that define Y can be generated if certain redundant linear inequalities are added to those generated by the Fourier-Motzkin procedure, and then the ceiling operator is applied to these redundant inequalities. We illustrate the idea with Example 2 below and then outline the general procedure. Rather than work with $Ax = b,$ $x \in {\mathbb Z}^n_{+}$ we work with the system $Ax \ge b$ and $x \in {\mathbb Z}^n$.

Example 2

Let $\mathcal {B}$ denote the set of all $b = (b_1, \ldots , b_5) \in \mathbb R^5$ such that there exist $x_1, x_2, x_3 \in {\mathbb Z}$ satisfying the following inequalities.

$$\begin{aligned} \begin{array}{rrrcr} - x_1 &{}+\frac{1}{2} x_2 &{}-\frac{1}{10} x_3&{} \ge &{} b_1 \\ x_1 &{}-\frac{1}{4} x_2&{}&{}\ge &{} b_2\\ &{}-x_2&{}+x_3&{}\ge &{} b_3\\ &{}&{}x_3&{}\ge &{} b_4\\ &{}&{}-x_3&{}\ge &{} b_5 \end{array} \end{aligned}$$

(9)

Performing Fourier-Motzkin elimination on the linear relaxation of (9) gives

$$\begin{aligned} 0&\ge 2b_1 + 2 b_2 + \tfrac{1}{2} b_3 + \tfrac{3}{10} b_5 \end{aligned}$$

(10)

$$\begin{aligned} 0&\ge \tfrac{1}{10}b_4 + \tfrac{1}{10}b_5. \end{aligned}$$

(11)

Unfortunately, there is no possible application of the ceiling operator to any combination of terms in these two inequalities that results in affine Chvátal functions that characterize $\mathcal {B}$. In particular, $b^1 = (0,0,0,1,-1) \notin \mathcal {B}$ while $b^2 = (-1, 0,0,1,-1) \in \mathcal {B}$. Consider $b^1$. This forces $x_3 = 1$ and the only feasible values for $x_1$ are $1/10 \le x_1 \le 4/10.$ Therefore, for this set of b values applying the ceiling operator to some combination of terms in (10)–(11) must result in either (10) positive or (11) positive. Since $b_1 = b_2 = b_3 = 0$ and $b_5 = -1$ there is no ceiling operator that can be applied to any term in (10) to make the right hand side positive. Hence a ceiling operator must be applied to (11) in order to make the right hand side positive for $b_4 = 1$ and $b_5 = -1.$ However, consider $b^2$. For this right-hand-side, $x_{1} = x_{2} = x_{3} = 1$ is feasible. Since we still have $b_4 = 1$ and $b_5 = -1$, the ceiling operator applied to (11) will incorrectly conclude that there is no integer solution with $b^2$.

However, Fourier-Motzkin elimination will work in conjunction with ceiling operations appropriate redundant inequalities are added. Consider the inequality $x_1 \ge b_1 + 2 b_2 + \frac{1}{10} b_4$which is redundant to (9). Integrality of $x_1$ implies $x_1 \ge \lceil b_1 + 2 b_2 + \frac{1}{10} b_4 \rceil .$ Applying Fourier-Motzkin elimination to (9) along with $x_1 \ge \lceil b_1 + 2 b_2 + \frac{1}{10} b_4 \rceil$ generates the additional inequality $0 \ge b_1 + \frac{1}{2} b_3 + \lceil b_1 + 2 b_2 + \frac{1}{10} b_4 \rceil + \frac{4}{10} b_5$, which separates $b^1$ and $b^2$.

Our proofs in Sect. 4 give a general method to systematically add the necessary redundant constraints, such as $x_1 \ge b_1 + 2 b_2 + \frac{1}{10} b_4$ in Example 2. This results in the following variable elimination scheme: at iterative step k maintain a MIC set with variables $(x_k, \ldots , x_n)$ that is indeed the true projection of the original set onto these variables. By Theorem 4, this MIC set is MILP representable with a set of variables $(x_k, \ldots , x_n, z).$ Then by Theorem 6 we can project out variable $x_k$ and additional auxiliary z variables that were used to generate the MILP representation and obtain a new MIC in only variables $(x_{k+1}, \ldots , x_n).$ The key point is that adding these auxiliary variables and then using Theorem 6 introduces the necessary redundant inequalities. Repeat until all variables are eliminated and a MIC set remains in the b variables. This positively answers the question of Ryan [6] and provides a projection algorithm in a similar vein to Williams [9,10,11] and Balas [1] but without use of disjunctions.