1 Introduction

Integer programming is concerned with the determination of an integer or mixed-integer point in a polytope. As a powerful mechanism, integer programming has been extensively applied in economics [1, 2] and management [3]. Integer programming is an NP-complete problem [4]. To solve such a problem, several methods have been developed in the literature. As an application of linear programming, the cutting plane method was pioneered in [5]. The method iteratively refines a feasible set or objective function by means of linear inequalities. The branch-and-bound method was formulated in [6]. The method gradually improves upper and lower bounds of the objective function by solving linear programs and systematically enumerates candidate solutions in branches of a tree with the full set of candidate solutions at the root by checking against the upper and lower bounds. To test whether a given feasible integer point is optimal or not, the neighborhood method was proposed in [1, 2]. The method simply checks a minimal set of points in the neighborhood of a feasible point to determine whether one of them is in the polytope or yields a better objective function value. The basis-reduction method originates in [7, 8]. As that in a branch-and-bound method, the method searches for an integer point in a polytope along a set of vectors that forms a reduced basis. The simplicial method was developed in [9, 10]. The method starts from an arbitrary integer point in the space and follows a simplicial path that either leads to an integer point in a polytope or proves no such point exists when the polytope is in a specific form. Further developments of some of these methods and new methods can be found in the recent literature such as [3, 1118], and the references therein. These methods play an extremely important role in the development of integer programming, however, it remains a challenging problem and appeals for more endeavors. Thus, developing alternative integer programming methods is always an active research area.

Integer programming can be cast as a fixed point problem of an increasing mapping. More precisely, let ⪯ be a binary relation on a nonempty set S. The pair \((S,\preceq)\) is a partially ordered set if ⪯ is reflexive, transitive, and antisymmetric on S. A lattice is a partially ordered set \((S,\preceq)\), in which any two elements x and y have a least upper bound (supremum), \(\sup_{S}(x,y)=\inf\{z\in S \mid x\preceq z\mbox{ and }y\preceq z\}\), and a greatest lower bound (infimum), \(\inf_{S}(x,y)=\sup\{z\in S \mid z\preceq x\mbox{ and }z\preceq y\}\), in the set. A lattice \((S,\preceq)\) is complete if every nonempty subset of S has a supremum and an infimum in S. Let f be a mapping from S into itself. f is an increasing mapping if \(f(x)\preceq f(y)\) for any x and y of S with \(x\preceq y\). When \((S,\preceq)\) is a complete lattice and f is an increasing mapping, Tarski’s fixed point theorem [19] asserts that f has a fixed point in S. A significant feature of Tarski’s fixed point theorem is that S can be a finite set and there is no restriction on its topological structures. This feature has a profound implication for integer programming as evidenced in this paper. The computational complexity of Tarski’s fixed point theorem on \((S,\leq)\) has been studied in [20], and it is polynomial-time computable if the dimension is fixed. As an application of Tarski’s fixed point theorem to integer programming, an increasing-mapping approach was briefly described in [21]. However, the approach is very primitive and can only update one coordinate at each iteration.

Let \(N=\{1,2,\ldots,n\}\) and \(N_{0}=\{0,1,2,\ldots,n\}\). For x and y of \(R^{n}\), \(x\leq_{l}y\) if either \(x=y\) or both \(x_{i}=y_{i}\), \(i=1,2,\ldots,k-1\), and \(x_{k}< y_{k}\) for some \(k\in N\), and \(x\leq y\) if \(x_{i}\leq y_{i}\) for all \(i\in N\), where \(\leq_{l}\) is the lexicographic order on \(R^{n}\) and ≤ is the componentwise order on \(R^{n}\). Let S be any given finite set of \(R^{n}\). Then \((S,\leq_{l})\) is a complete lattice. We now convert integer programming into the computation of fixed points of an increasing mapping from a finite lattice into itself, which leads to the fixed point iterative method proposed in this paper and is the driving force behind our research endeavors.

Consider \(P=\{x\in R^{2} \mid Ax\leq b\}\) with

$$A =\left ( \textstyle\begin{array}{@{}c@{\quad}c@{}} -17 & 2\\ 6 & 5\\ -3 & -3 \end{array}\displaystyle \right ) $$

and \(b = ( -8, 4, 7 )^{\top}\). This polytope is illustrated in Figure 1.

Figure 1
figure 1

An illustration of the idea.

Let \(D(P)\) denote the set of all the integer points with \(x^{l}\leq x\leq x^{u}\) in Figure 1. The idea is to define an increasing mapping h from \(D(P)\) into itself such that at least \(h(x)\leq_{l}x\) for any \(x\in D(P)\) with \(x\notin P\) and \(x\neq x^{l}\) and that \(h(x^{*})=x^{*}\) if and only if either \(x^{*}\in P\) or \(x^{*}=x^{l}\). Such a mapping is illustrated in Figure 1. This simple example stimulates the idea in this paper though the situation is far more complicated when the dimension is higher.

In this paper, with this constructing we develop a fixed point iterative method for integer programming. A self-dual technique is applied for a solution to a bounding linear program in the development. Given any polytope, within a finite number of iterations, the method either yields an integer or mixed-integer point in the polytope or proves no such point exists. Theoretically, one can make the method be a polynomial-time algorithm when the dimension is fixed. But a more appealing feature of the method is that it can easily be implemented in a distributed way. Furthermore, the construction implies that determining the uniqueness of Tarski’s fixed point is an NP-hard problem, and the method can be applied to compute all integer or mixed-integer points in a polytope and directly extended to convex nonlinear integer programming. Preliminary numerical results show that the method is promising, and may offer a comparable solution to integer programming though a comprehensive comparison with the existing methods is beyond the scope of this paper.

The rest of the paper is organized as follows. A fixed point iterative method is first developed for integer programming in Section 2. Then a distributed implementation of the method and the computation of all integer points in a polytope are discussed in Section 3. Preliminary numerical results are presented in Section 4.

2 A fixed point iterative method

Let

$$P=\bigl\{ x\in R^{n} \mid Ax+Gw\leq b\mbox{ for some }w\in R^{p}\bigr\} , $$

where \(A\in R^{m\times n}\) is an \(m\times n\) integer matrix with \(n\geq 2\), \(G\in R^{m\times p}\) an \(m\times p\) matrix, and b a vector of \(R^{m}\). We assume throughout this paper that P is bounded and full dimensional. For a real number α, let \(\lfloor\alpha\rfloor\) denote the greatest integer less than or equal to α. For \(x=(x_{1},x_{2},\ldots,x_{n})^{\top}\in R^{n}\), let \(\lfloor x\rfloor=(\lfloor x_{1}\rfloor, \lfloor x_{2}\rfloor,\ldots,\lfloor x_{n}\rfloor)^{\top}\).

Let \(x^{\mathrm{max}}=(x^{\mathrm{max}}_{1},x^{\mathrm{max}}_{2},\ldots,x_{n}^{\mathrm{max}})^{\top}\) with \(x^{\mathrm{max}}_{j}=\max_{x\in P}x_{j}\), \(j=1,2,\ldots,n\), and \(x^{\mathrm{min}}=(x^{\mathrm{min}}_{1}, x^{\mathrm{min}}_{2},\ldots,x^{\mathrm{min}}_{n})^{\top}\) with \(x^{\mathrm{min}}_{j}=\min_{x\in P}x_{j}\), \(j=1,2,\ldots,n\). Then \(x^{\mathrm{min}}\leq x\leq x^{\mathrm{max}}\) for all \(x\in P\). Let

$$D(P)=\bigl\{ x\in Z^{n} \mid x^{l}\leq x\leq x^{u} \bigr\} , $$

where \(x^{u}=\lfloor x^{\mathrm{max}}\rfloor\) and \(x^{l}=\lfloor x^{\mathrm{min}}\rfloor\). Thus, \(D(P)\) contains all integer points in P. We assume without loss of generality that \(x^{l}< x^{\mathrm{min}}\) (let \(x_{i}^{l}=x_{i}^{\mathrm{min}}-1\) if \(x_{i}^{l}=x_{i}^{\mathrm{min}}\) for some \(i\in N\)) and that

$$x_{1}^{u}-x_{1}^{l}\leq x_{2}^{u}-x_{2}^{l}\leq\cdots\leq x_{n}^{u}-x_{n}^{l}, $$

which can be obtained by interchanging the columns of A if necessary.

For \(z\in R^{n}\) and \(k\in N_{0}\), let

$$P(z,k)=\{x\in P \mid x_{i}=z_{i}, 1\leq i\leq k\mbox{ and }x_{i}\leq z_{i}, k+1\leq i\leq n\}. $$

Given an integer point \(y\in D(P)\) with \(y_{1}>x_{1}^{l}\), we present in the following a fixed point iterative method to determine whether there is an integer point \(x^{*}\in P\) with \(x^{*}\leq_{l}y\).

Initialization::

Let \(y^{0}=y\), \(k=n-1\), and \(q=0\).

Step 1::

If \(y^{q}\in P\) or \(y^{q}=x^{l}\), Stop; else, go to Step 2.

Step 2::

If \(y^{q}_{i}\leq x_{i}^{l}\) for some \(i\in N\) or \(P(y^{q},k)=\emptyset\), go to Step 5; else, go to Step 3.

Step 3::

Solve the linear program

$$\begin{aligned}& \max \sum_{j=k+1}^{n} x^{j}_{j} \\& \quad \mbox{subject to } x^{j}\in P\bigl(y^{q},k\bigr),\quad j=k+1,k+2,\ldots,n, \end{aligned}$$

to obtain the optimal value of \(x^{j}_{j}\), denoted by \(x^{j}_{j}(y^{q})\), \(j=k+1,k+2,\ldots,n\), and go to Step 4.

Step 4::

If \(y^{q}_{j}> x^{j}_{j}(y^{q})\) for some \(j\geq k+1\), let \(y^{q+1}=(y_{1}^{q+1},y^{q+1}_{2},\ldots,y^{q+1}_{n})^{\top}\) with

$$y^{q+1}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{q}_{i} & \mbox{if }1\leq i\leq k, \\ \lfloor x^{i}_{i}(y^{q})\rfloor& \mbox{if }k+1\leq i\leq n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\), and \(q=q+1\), and go to Step 1; else, let \(k=k+1\) and go to Step 3.

Step 5::

If \(k=0\), let \(y^{q+1}=x^{l}\) and \(q=q+1\); else, let \(y^{q+1}=(y_{1}^{q+1},y^{q+1}_{2},\ldots,y^{q+1}_{n})^{\top}\) with

$$y^{q+1}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{q}_{i} & \mbox{if }1\leq i\leq k-1, \\ y^{q}_{i}-1 & \mbox{if }i=k, \\ x^{u}_{i} & \mbox{if }k+1\leq i\leq n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\), \(q=q+1\), and \(k=k-1\). Go to Step 1.

At each iteration, the method needs to solve a bounding linear program, which may have no feasible solution. To effectively address this issue, one can apply the self-dual embedding technique in [22, 23] or any best available software packages. The following two examples illustrate how the method works.

Example 1

Consider \(P=\{x\in R^{3} \mid Ax\leq b\}\) with

$$A =\left ( \textstyle\begin{array}{@{}c@{\quad}c@{\quad}c@{}} -1 & 0 & 2\\ 0 & -2 & 1\\ -1 & 0 & -2\\ 1 & 1 & 0 \end{array}\displaystyle \right ) $$

and \(b = ( 0, 1, 1, 0, )^{\top}\). We have \(x^{u}=(1,0,0)^{\top}\) and \(x^{l}=(-1,-2,-2)^{\top}\).

Let \(y=x^{u}\), \(y^{0}=y\), and \(k=3-1=2\).

Iteration 1::

Since \(P(y^{0},2)=\emptyset\), we obtain from Step 5

$$y^{1}=\bigl(y^{0}_{1},y^{0}_{2}-1,x^{u}_{3} \bigr)^{\top}=(1,-1,0)^{\top} $$

and \(k=k-1=2-1=1\).

Iteration 2::

Solving

$$\begin{aligned}& \max x_{2}^{2}+x_{3}^{3} \\& \quad \mbox{subject to } x^{j}\in P\bigl(y^{1},1\bigr), \quad j=2,3, \end{aligned}$$

we obtain \(x_{2}^{2}(y^{1})=-1\) and \(x_{3}^{3}(y^{1})=-1\). Since \(y^{1}_{3}=0>-1=x_{3}^{3}(y^{1})\), we obtain from Step 4

$$y^{2}=\bigl(y^{1}_{1},\bigl\lfloor x_{2}^{2}\bigl(y^{1}\bigr)\bigr\rfloor ,\bigl\lfloor x_{3}^{3}\bigl(y^{1}\bigr)\bigr\rfloor \bigr)^{\top}=(1,-1,-1)^{\top}, $$

which is an integer point in P.

An illustration of \(y^{0}\), \(y^{1}\), and \(y^{2}\) can be found in Figure 2.

Figure 2
figure 2

An illustration of the method.

Example 2

Consider \(P=\{x\in R^{3} \mid Ax\leq b\}\) with

$$A =\left ( \textstyle\begin{array}{@{}c@{\quad}c@{\quad}c@{}} -4 & 3 & 2\\ -1 & 4 & -2\\ -1 & -5 & -1\\ 2 & 1 & 1 \end{array}\displaystyle \right ) $$

and \(b = ( -2, 0, 1, 1)^{\top}\). We have \(x^{u}=(1,0,0)^{\top}\) and \(x^{l}=(0,-1,-2)^{\top}\).

Let \(y=x^{u}\), \(y^{0}=y\), and \(k=n-1=2\).

Iteration 1::

Since \(P(y^{0},2)=\emptyset\), we obtain from Step 5

$$y^{1}=\bigl(y^{0}_{1},y^{0}_{2}-1,x^{u}_{3} \bigr)^{\top}=(1,-1,0)^{\top} $$

and \(k=k-1=2-1=1\).

Iteration 2::

Since \(P(y^{1},1)=\emptyset\), we obtain from Step 5

$$y^{2}=\bigl(y^{1}_{1}-1,x^{u}_{2},x^{u}_{3} \bigr)^{\top}=(0,0,0)^{\top} $$

and \(k=k-1=1-1=0\).

Iteration 3::

Since \(P(y^{2},0)=\emptyset\), we obtain from Step 5

$$y^{3}=x^{l}=(0,-1,-2)^{\top}, $$

which shows that there is no integer point in P.

An illustration of \(y^{0}\), \(y^{1}\), \(y^{2}\), and \(y^{3}\) can be found in Figure 3.

Figure 3
figure 3

An illustration of the method.

For \(q=0,1,\ldots\) , let \(k_{q}\) denote the value of k at which the method determines \(y^{q}\). Clearly, \(x^{l}-e\leq y^{q}\leq x^{u}\) with \(e=(1,1,\ldots,1)^{\top}\in R^{n}\).

Lemma 1

For \(q=0,1,\ldots\) ,

$$y^{q+1}\leq y^{q}\quad \textit{or}\quad y^{q+1} \leq_{l} y^{q} $$

with \(y^{q}\neq y^{q+1}\).

Proof

This lemma is proved in two cases.

Case 1: Suppose that \(P(y^{q},k_{q})=\emptyset\). Then the method will perform Step 5. If \(k_{q}=0\), we obtain from Step 5 that \(y^{q+1}=x^{l}\), and consequently, \(y^{q+1}\leq y^{q}\) with \(y^{q}\neq y^{q+1}\). Assume that \(k_{q}>0\). Then we obtain from Step 5 that \(y^{q+1}=(y_{1}^{q+1},y^{q+1}_{2},\ldots,y^{q+1}_{n})^{\top}\) with

$$y^{q+1}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{q}_{i} & \mbox{if }1\leq i\leq k_{q}-1, \\ y^{q}_{i}-1 & \mbox{if }i=k_{q}, \\ x^{u}_{i} & \mbox{if }k_{q}+1\leq i\leq n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\). Thus, \(y^{q+1}_{k_{q}}< y^{q}_{k_{q}}\). Therefore, \(y^{q+1}\leq_{l} y^{q}\) with \(y^{q}\neq y^{q+1}\).

Case 2: Suppose that \(P(y^{q},k_{q})\neq\emptyset\). Then the method will repeatedly perform Steps 3 and 4 right before it goes to Step 1. Since \(y^{q}\notin P\), as k increases one by one, it will reach a value \(k_{q+1}\) such that \(y^{q}_{j}>x^{j}_{j}(y^{q})\) for some \(j\geq k_{q+1}+1\). When this occurs, we obtain from Step 4 that \(y^{q+1}=(y_{1}^{q+1},y^{q+1}_{2},\ldots,y^{q+1}_{n})^{\top}\) with

$$y^{q+1}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{q}_{i} & \mbox{if }1\leq i\leq k_{q+1}, \\ \lfloor x^{i}_{i}(y^{q})\rfloor& \mbox{if }k_{q+1}+1\leq i\leq n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\). Moreover, one can see from Step 3 that

$$x_{j}^{j}\bigl(y^{q}\bigr)\leq y^{q}_{j}, \quad j=k_{q+1}+1,k_{q+1}+2, \ldots,n. $$

Therefore, \(y^{q+1}\leq y^{q}\) with \(y^{q}\neq y^{q+1}\). The proof is completed. □

Theorem 1

Given an integer point \(y\in D(P)\) with \(y_{1}>x_{1}^{l}\), the method, within a finite number of iterations, either yields an integer point \(x^{*}\in P\) with \(x^{*}\leq_{l} y\) or proves no such point exists.

Proof

Let y be any given integer point in \(D(P)\) with \(y_{1}>x_{1}^{l}\). Suppose that \(y\notin P\) and there is some integer point \(z^{0}\in P\) with \(z^{0}\leq_{l} y\). We assume without loss of generality that \(z^{0}\) is the largest integer point of P satisfying that \(z^{0}\leq_{l} y\). Applying mathematical induction, we show in the following that \(z^{0}\leq_{l} y^{q}\), \(q=1,2,\ldots\) .

1. Consider the case of \(q=1\). From the method, we know that \(k_{0}=n-1\).

(a) Suppose that \(P(y^{0},k_{0})=\emptyset\). Then the method will perform Step 5, and we obtain from Step 5 that \(y^{1}=(y_{1}^{1},y^{1}_{2},\ldots,y^{1}_{n})^{\top}\) with

$$y^{1}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{0}_{i} & \mbox{if }1\leq i\leq n-2, \\ y^{0}_{i}-1 & \mbox{if }i=n-1, \\ x^{u}_{i} & \mbox{if }i= n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\), and \(k_{1}=n-2\). If \(y_{i}^{0}>z^{0}_{i}\) for some \(i\leq n-2\), then \(z^{0}\leq_{l}y^{1}\) with \(z_{j}^{0}< y^{1}_{j}\) for some \(j\leq k_{1}\). Assume that \(y_{i}^{0}=z^{0}_{i}\) for all \(i\leq n-2\). Then, from \(P(y^{0},k_{0})=\emptyset\) and \(z^{0}\leq_{l} y^{0}\), we derive that \(z^{0}_{n-1}< y_{n-1}^{0}\) since otherwise \(P(y^{0},k_{0})\neq\emptyset\). Therefore, \(z^{0}\leq y^{1}\).

(b) Suppose that \(P(y^{0},k_{0})\neq\emptyset\). Then the method will perform Steps 3 and 4. Since \(y^{0}\notin P\), \(y^{0}_{n}>x^{n}_{n}(y^{0})\). Thus, we obtain from Step 4 \(y^{1}=(y_{1}^{1},y^{1}_{2},\ldots,y^{1}_{n})^{\top}\) with

$$y^{1}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{0}_{i} & \mbox{if }1\leq i\leq n-1, \\ \lfloor x^{n}_{n}(y^{0})\rfloor& \mbox{if }i= n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\), and \(k_{1}=n-1\). If \(y_{i}^{0}>z^{0}_{i}\) for some \(i\leq n-1\), then \(z^{0}\leq_{l}y^{1}\) with \(z^{0}_{j}< y^{1}_{j}\) for some \(j\leq k_{1}\). Assume that \(y^{0}_{i}=z_{i}^{0}\) for all \(i\leq n-1\). Then we derive from \(z^{0}\leq_{l} y^{0}\) that \(z^{0}\in P(y^{0},k_{0})\). Thus, \(z^{0}_{n}\leq \lfloor x^{n}_{n}(y^{0})\rfloor\). Therefore, \(z^{0}\leq y^{1}\).

2. Induction hypothesis: For any given \(1\leq h\leq q\), we assume that \(y^{h}\notin P\) and that \(z^{0}\leq y^{h}\) or \(z^{0}\leq_{l}y^{h}\) with \(z^{0}_{j}< y^{h}_{j}\) for some \(j\leq k_{h}\).

3. With this induction hypothesis, we prove in the following that \(z^{0}\leq y^{q+1}\) or \(z^{0}\leq_{l} y^{q+1}\) with \(z^{0}_{j}< y^{q+1}_{j}\) for some \(j\leq k_{q+1}\) under two cases.

Case 1: Suppose that \(P(y^{q},k_{q})=\emptyset\). Then the method will perform Step 5. Assume that \(k_{q}=0\). From the method, we know that Step 5 must be performed at least once before \(y^{q}\) is generated. Let \(y^{q_{0}}\) be the point obtained by the method in the last performance of Step 5 before \(y^{q}\) is generated. Thus, \(k_{q_{0}}=k_{q}=0\), \(k_{q_{0}-1}=1\), and \(P(y^{q_{0}-1},k_{q_{0}-1})=\emptyset\). From Step 5, we know that \(y^{q_{0}}=(y_{1}^{q_{0}},y^{q_{0}}_{2},\ldots,y^{q_{0}}_{n})^{\top}\) with

$$y^{q_{0}}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{q_{0}-1}_{i}-1 & \mbox{if }i=1, \\ x^{u}_{i} & \mbox{if }2\leq i\leq n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\). This together with \(P(y^{q_{0}-1},k_{q_{0}-1})=\emptyset\) and the induction hypothesis for \(h=q_{0}-1\) leads to that \(z^{0}\leq y^{q_{0}}\). If \(q=q_{0}\), then \(z^{0}\leq y^{q}=y^{q_{0}}\). Suppose that \(q>q_{0}\). Then \(q=q_{0}+1\) and the method will perform Steps 3 and 4 to generate \(y^{q}\) right after \(y^{q_{0}}\) is generated. Since \(k_{q}=k_{q_{0}}\), the method will perform once Steps 3 and 4 to generate \(y^{q}\). With \(k_{q}=0\), we obtain from Step 4 that \(y^{q}=(y^{q}_{1},y^{q}_{2},\ldots,y^{q}_{n})^{\top}\) with

$$y^{q}_{i}=\bigl\lfloor x^{i}_{i} \bigl(y^{q_{0}}\bigr)\bigr\rfloor ,\quad i=1,2,\ldots,n. $$

Thus, it follows from \(z^{0}\in P(y^{q_{0}},k_{q_{0}})\) that \(z^{0}\leq y^{q}\). Therefore, \(z^{0}\in P(y^{q},k_{q})\). It contradicts with \(P(y^{q},k_{q})=\emptyset\). So, we must have \(k_{q}>0\).

From Step 5, we obtain \(y^{q+1}=(y_{1}^{q+1},y^{q+1}_{2},\ldots,y^{q+1}_{n})^{\top}\) with

$$y^{q+1}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{q}_{i} & \mbox{if }1\leq i\leq k_{q}-1, \\ y^{q}_{i}-1 & \mbox{if }i=k_{q}, \\ x^{u}_{i} & \mbox{if }k_{q}+1\leq i\leq n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\), and \(k_{q+1}=k_{q}-1\). If \(z^{0}_{i}< y^{q}_{i}\) for some \(i\leq k_{q}-1\), then \(z^{0}\leq_{l} y^{q+1}\) with \(z^{0}_{j}< y^{q+1}_{j}\) for some \(j\leq k_{q+1}\). Suppose that \(y_{i}^{q}=z_{i}^{0}\), \(i=1,2,\ldots,k_{q}-1\). Hence, \(z_{k_{q}}^{0}< y^{q}_{k_{q}}\) from the induction hypothesis since otherwise \(P(y^{q},k_{q})\neq\emptyset\). Therefore, \(z^{0}\leq y^{q+1}\).

Case 2: Suppose that \(P(y^{q},k_{q})\neq\emptyset\). Then the method will repeatedly perform Steps 3 and 4 right before it goes to Step 1. Since \(y^{q}\notin P\), as k increases one by one, it will reach a value \(k_{q+1}\geq k_{q}\) such that \(y^{q}_{j}>x^{j}_{j}(y^{q})\) for some \(j\geq k_{q+1}+1\). When this occurs, we obtain from Step 4 that \(y^{q+1}=(y_{1}^{q+1},y^{q+1}_{2},\ldots,y^{q+1}_{n})^{\top}\) with

$$y^{q+1}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} y^{q}_{i} & \mbox{if }1\leq i\leq k_{q+1}, \\ \lfloor x^{i}_{i}(y^{q})\rfloor& \mbox{if }k_{q+1}+1\leq i\leq n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\). If \(z_{i}^{0}< y^{q}_{i}\) for some \(i\leq k_{q}\), then \(z^{0}\leq_{l}y^{q+1}\) with \(z^{0}_{j}< y^{q+1}_{j}\) for some \(j\leq k_{q+1}\). Suppose that \(y^{q}_{i}=z_{i}^{0}\) for all \(i\leq k_{q}\). Thus, \(z^{0}\leq y^{q}\) from the induction hypothesis for \(h=q\).

  • Consider \(k_{q+1}=k_{q}\). Since \(z^{0}\in P(y^{q},k_{q})\), \(z^{0}_{i}\leq\lfloor x^{i}_{i}(y^{q})\rfloor\) for all \(k_{q+1}+1\leq i\leq n\). Therefore, \(z^{0}\leq y^{q+1}\).

  • Consider \(k_{q+1}>k_{q}\). If \(z^{0}_{i}< y^{q}_{i}\) for some \(k_{q}< i\leq k_{q+1}\), then it follows from Steps 3 and 4 that \(z^{0}\leq_{l}y^{q+1}\) with \(z^{0}_{j}< y^{q+1}_{j}\) for some \(j\leq k_{q+1}\). Suppose that \(y^{q}_{i}=z^{0}_{i}\) for all \(k_{q}< i\leq k_{q+1}\). Since \(z^{0}\leq y^{q}\), \(z^{0}\in P(y^{q},k_{q+1})\) and consequently, \(z^{0}_{i}\leq\lfloor x^{i}_{i}(y^{q})\rfloor\) for all \(k_{q+1}+1\leq i\leq n\). Therefore, \(z^{0}\leq y^{q+1}\).

The above results together with mathematical induction show that

$$z^{0}\leq_{l}y^{q},\quad q=1,2,\ldots. $$

From Lemma 1, we know that \(y^{q+1}\leq y^{q}\) or \(y^{q+1}\leq_{l}y^{q}\) with \(y^{q+1}\neq y^{q}\). Therefore, within a finite number of iterations, the method meets \(z^{0}\) since there are only a finite number of integer points in the set

$$\bigl\{ z\in Z^{n} \mid z^{0}\leq_{l} z \leq_{l} y\mbox{ and }x^{l}-e\leq z\leq x^{u}\bigr\} . $$

This completes the proof. □

As a corollary of Theorem 1, we come to the following conclusion.

Corollary 1

Starting from \(y^{0}=x^{u}\), the method, within a finite number of iterations, either yields an integer point in P or proves no such point exists.

3 Distributed computation and computing all integer points in a polytope

For any given positive integer ν, let \(x^{i}\), \(i=1,2,\ldots,\nu\), be a sequence of different integer points in \(D(P)\) with \(x^{l}\leq x^{1}\leq_{l}x^{2}\leq_{l}\cdots\leq_{l}x^{\nu}=x^{u}\). Then the method can easily be implemented in a distributed way by starting from \(x^{i}\), \(i=1,2,\ldots,\nu\), simultaneously.

The method can also be applied to compute all integer points in P, which is as follows.

Step 0::

Use the method starting from \(x^{u}\) to compute an integer point in P. If no integer point has been found, Stop. Otherwise, let \(s^{1}\) be the solution found by the method and \(g=1\), and go to Step 1.

Step 1::

Let \(y^{0}=(y_{1}^{0},y_{2}^{0},\ldots,y^{0}_{n})^{\top}\) with

$$y^{0}_{i}=\left \{ \textstyle\begin{array}{l@{\quad}l} s^{g}_{i} & \mbox{if }i< n, \\ s^{g}_{i}-1 & \mbox{if }i=n, \end{array}\displaystyle \right . $$

\(i=1,2,\ldots,n\), and go to Step 2.

Step 2::

If \(y^{0}\in P\), let \(s^{g+1}=y^{0}\) and \(g=g+1\), and go to Step 1. Otherwise, go to Step 3.

Step 3::

Use the method starting from \(y^{0}\) to compute an integer point in P. If no integer point has been found, Stop. Otherwise, let \(s^{g+1}\) be the solution found by the method and \(g=g+1\), and go to Step 1.

4 Numerical results

In this section, we apply the method to determine whether there is an integer point in the polytope of the market split problem and the polytope of the 0-1 knapsack feasibility problem though a comprehensive comparison with the existing methods is beyond the scope of this paper. The method has been coded in C++ and run on a workstation of Lenovo ThinkStation D20 4155-BM4 with 16 processors. In our implementation of the method, each linear program is solved by the linear program solver of ILOG CPLEX with all the parameter values automatically set by ILOG CPLEX itself. We have also run ILOG CPLEX on the same problem instance and found that the branch-and-cut strategy is the best of ILOG CLEX. In the presentation of numerical results, NumLPs stands for the total number of linear programs solved by the method and the branch-and-cut strategy of ILOG CLEX for each instance. In the feasibility category, ‘Feasible’ appears if an instance has a feasible integer point and ‘Infeasible’ otherwise. In our numerical experiments, to convert a problem into an equivalent problem of determining whether there is an integer point in a full-dimensional polytope given by \(P=\{x\in R^{n} \mid Ax\leq b\}\), we apply the basis-reduction algorithm of [24] in the same way as that in [11] and in the appendix with \(N_{1}=10\text{,}000\) and \(N_{2}=100\text{,}000\).

Example 3

(The market split problem)

The market split problem given in [15] is to determine whether the system, \(Cx = d\), has a 0-1 integer solution, where \(C=(c_{ij})\) is a \(p\times q\) (e.g., \(q=10(p-1)\)) nonnegative integer matrix and \(d=(d_{1},d_{2},\ldots,d_{p})^{\top}\) is an integer vector given by \(d_{i}=\lfloor\sum_{j=1}^{n} c_{ij}/2\rfloor\), \(i=1,2,\ldots,p\). In our numerical experiments, \(c_{ij}\in[0, 99]\), \(i=1,2,\ldots,p\), \(j=1,2,\ldots,q\), are generated randomly.

For the problem with \(p=5\) and \(q=40\), we have solved 25 instances using the method and the best CPLEX strategy. Numerical results for 25 instances of the problem are given in Table 1.

Table 1 The market split problem

To demonstrate the capability of distributed computation of the method, we have implemented the method in a distributed way to solve the market split problem with \(p=6\) and \(q=50\). We divide the problem space into 32 parts and run 16 subproblems simultaneously on the workstation. In the presentation of numerical results, MAX NumLPs stands for either the largest number of linear programs consumed by the method for any of the 32 subproblems when an instance is infeasible or the smallest number of linear programs consumed by the method for the subproblem in which a feasible solution is found. Numerical results for five instances of the problem are given in Table 2.

Table 2 The market split problem

Example 4

(The 0-1 knapsack feasibility problem)

Find a 0-1 solution of \(p^{\top}x=d\), where \(p=(p_{1},p_{2},\ldots,p_{n+1})^{\top}>0\) and \(p_{i}\neq p_{j}\) for all \(i\neq j\). In our numerical experiments, \(p_{j}\in[10^{2}, 10^{4}]\), \(j=1,2,\ldots,n+1\), and \(d\in[10^{2}, 10^{4}]\) are generated randomly. Numerical results of the method for this problem are given in Table 3.

Table 3 The 0-1 knapsack feasibility problem

This paper has no intention to make a comprehensive comparison of the proposed method with the existing methods. Nevertheless, one can see from these preliminary numerical results that the numbers of linear programs solved by the method for most instances of two specific problems are less than those of the best CPLEX strategy: branch and cut. An efficient implementation of the method requires a considerable amount of additional research, which is beyond the scope of this paper and will be carried out in another research project.