Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

Question

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities? If it is not, then what is?

For $m$ inequalities in $d$ dimensions, the most expensive part of Avis's algorithm seems to complete in $\mathcal{O}(md^2)$ time, although it has to be repeated $N_b$ times where $N_b$ is the number of "bases", which is a bit unpredictable.

Answer 1

There are many algorithms suggested for converting the "external" representation of a polyhedron (i.e., the set of solutions to a finite set of linear inequalities) into an "internal" one (i.e., a finite set of generators, extreme points and extreme rays). At it's core there often is some sort of finding all (discrete) solutions to a set of linear inequalities. The Fourier-Motzkin Elimination comes to mind here. The additonal requirement of discreteness and "all solutions" came later, but there are implementations out there. A classic is porta and I would, still today, always start from there.

Answer 2

I am not familiar with the "reverse search" algorithm.

For solving systems of linear inequalities in practice, algorithms for integer programming or constraint programming are probably most applicable. If you are concerned about theoretical complexity, there exist algorithms to solve integer programming problems in polynomial time in fixed dimension. For example, see the LLL algorithm. These algorithms are interesting from a theoretical point of view, but are not often used in practice.

Answer 3

As far as I can tell from the information I could on the "Reverse Search" algorithm, it is a technique that helps to enumerate combinatorial structures. In particular the paper you mention in a comment deals with vertex and facet enumeration. Since it is a bit unclear what you mean by "discrete solutions", let us distinguish four cases.

1. Finding a single vertex of a polytope: for this case, you can use any Linear Programming solver. There tools can even produce a best vertex according to some linear objective function. Common tools to solve this in practice are the simplex method and interior point methods. Compared to those techniques, using an enumeration method is probably like shooting a mosquito with a bazooka.
2. Finding a single integer point within a polytope: in general this problem is NP-complete, so in the worst case we do not know a better way to do it that by some clever form of enumeration. However, the main reason why this is difficult is that we have no real guarantee that the vertices of a polytope are actually integer points. If we have a special case where we do know that the vertices of the polytope are integer, for example because your system of inequalities is totally unimodular, or if for some reason you are sure that your system of inequalities defines all the facets of the convex hull of the integer points within your polytope, this case reduces to case 1. In practice, this problem is solved using a combination of Branch-and-Bound and Linear Programming techniques: in each step you solve a linear program. If it results in an integer point, you are happy. If it does not, you take a fractional variable of the vertex you found, and create two sub-problems: one where that variable can be at most its current value rounded down, and another where that variable must be at least its current value rounded up. These sub-problems can be easily derived by introducing a new inequality into your system.
3. Enumerating all vertices of a polytope: since the number of vertices of a polytope can already be exponential in the number of inequalities and dimensions of your system, this is a problem that has exponential output. Since the amount of output of an algorithm is a lower bound on the running time, it is implied this problem takes exponential time in the worst case, even under the unlikely assumption that P=NP. This seems to be the problem that the "Reverse Search" algorithm tries to tackle. I think the number of vertices of the polytope gives a lower bound for the number of bases of the polytope (since the simplex method basically starts out with a base, and adjusts it to find a new vertex in each step). As the reverse search algorithm must be repeated for every base, this would imply it is an exponential time algorithm in the worst case. Note that even counting the number of vertices of a polytope, which is easier than enumeration since you do not need to output the actual vertices, is already difficult in general, see for example this paper or this paper.
4. Enumerating the vertices of the convex hull of integer points within a polytope: This problem combines the issues we have in case 2 and case 3. I did not read deep enough into the paper to see if this case is also covered, but I know that some researchers in the operations research communities use tools that can do this. I can imagine those tools are indeed based on the reverse search algorithm, although I don't know for sure. The main reason why these tools are used, is to obtain descriptions of the facets of an integer polytope, and check if some structure can be found in the inequalities that correspond to the facets. That way, researchers can try and develop valid inequalities.