10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you need all integer solutions or just one? Do you want to optimize over the set of integer solutions? $\endgroup$ – Brian Borchers Sep 21 at 18:18
  • $\begingroup$ Do you have a link to the paper? Is it this one: cgm.cs.mcgill.ca/~avis/doc/avis/AF96a.pdf ? $\endgroup$ – JakobS Sep 21 at 19:34
  • $\begingroup$ @JakobS: That is one of the older papers, but there's improved ones that were published later. For me to find them would involve the exact same steps as it would for you (i.e. checking Google Scholar) because this is not my field of expertise :) $\endgroup$ – user1271772 Sep 21 at 19:36
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can "porta" find all vertices of a polyhedral cone? $\endgroup$ – user1271772 Sep 22 at 23:06
  • $\begingroup$ @user1271772 a polyhedral cone has only one vertex (the origin), but yes, porta lists all vertices and extreme rays of a polyhedron - problem is: Fourier Motzkin is not polynomial space. $\endgroup$ – Marco Lübbecke Sep 22 at 23:09
  • 1
    $\begingroup$ Thank you for the clarification! PORTA seems to have 138 citations since 1997: scholar.google.com/…. David Avis's LRS has 820 citations. Are you sure Porta is state-of-the-art for finding all vertices and extreme rays of a polyhedron? $\endgroup$ – user1271772 Sep 22 at 23:28
  • 1
    $\begingroup$ As often, "it depends"; when e.g., the polyhedron is super degenerate, a simplex-type method like lrs might suffer a lot. If you have a specific application and have access to both codes, why not try both and see what works for you? I know, not an advise we want, but often true in the computational world... $\endgroup$ – Marco Lübbecke Sep 23 at 8:24
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I've added that the $\mathcal{O}(md^2)$ step has to be repeated for each "basis" and the number of bases is unpredictable. I am not trying to solve equalities, only inequalities. $\endgroup$ – user1271772 Sep 21 at 17:16
  • $\begingroup$ That was indeed not clear to me, thank you for the clarification. I have removed the irrelevant part of my answer, and I hope that a reverse search expert drops by to provide a more detailed answer. $\endgroup$ – Kevin Dalmeijer Sep 21 at 17:24
  • $\begingroup$ According this this: link.springer.com/article/10.1007/s12532-017-0129-y, Avis's code has done 71 inequalities in 60 dimensions, and 1023 inequalities in 10 dimensions, but the most expensive one was actually 91 inequalities in 37 dimensions because there was 10 trillion bases! So when you say "algorithms for integer programming or constraint programming are probably most applicable", are there any of them that you know that have done this many inequalities/dimensions? I am looking for the state-of-the-art algorithm for finding discrete solutions to a system of linear inequalities. $\endgroup$ – user1271772 Sep 21 at 17:55
  • $\begingroup$ Integer programming is routinely used to find the best discrete solution to systems of thousands of linear inequalities in thousands of dimensions. For example, see the MIPLIB 2017 benchmarks. However, it could very well be that the problems that Avis looks at are more difficult, and integer programming is not appropriate. For example, in integer programming you often have $0 \le x \le 1$. Again, I am not an expert on what you are really asking about. $\endgroup$ – Kevin Dalmeijer Sep 21 at 18:05
  • $\begingroup$ What is meant by $0\le x \le 1$? The solutions $x$ of the system of linear inequalities satisfy $0\le x \le 1$? Then since they are integers, why not say $x\in\{0,1\}$? $\endgroup$ – user1271772 Sep 21 at 19:41
4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Thank you for the very informative answer! Avis's code finds all vertices of a polyhedron, so I wonder if it's the state-of-the-art algorithm at that. $\endgroup$ – user1271772 Sep 22 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.