Enumerating all integer feasible points, CPLEX vs Polymake

[UserCplex]

Hello,

I am noticing a big difference in the time taken to enumerate integer feasible points for a bounded integer program between CPLEX and Polymake.

Attached is an integer program, "problemIP.lp".

On running this through the attached "populate.c" cplex code file, I am able to obtain the 4722 integer feasible points in two files that are output by the "populate.c" file within about a second or so. One of the files produced is points.txt file while the other file is points_varname.txt. The only difference between the two files is that the latter file contains a first line that lists the variable names as picked up from the lp file. These files are in the zip folder since the forum says unzipped these files are too large.

Now, when I attempt to obtain the lattice points for the same problem under polymake thus:

$f = lp2poly('problemIP.lp');

$p=new Polytope<Rational>($f);

$p->LATTICE_POINTS;

the last function takes forever. I have to terminate it after about 10 minutes with nothing to show on the terminal.

Is there anything wrong that I am doing in obtaining the lattice points under polymake? I am using polymake version 3.2.

Thanks.

[opfer]

I think this has 2 reasons:

1. polymake uses exact arithmetic. Exact calculations are much slower than floating point arithmetic used in CPLEX.

2. If I remember correctly, polymake currently uses convex hull algorithms to enumerate the lattice points. A year ago, I wrote a Cut&Branch algorithm that can also enumerate lattice points (similar to CPLEX). Unfortunately, it has not been added to polymake, yet. I tested this algorithm and it finds 4722 (exact rational) solutions for your problem in around 90 seconds.

Best regards,
Thomas

[UserCplex]

Thomas,

Thanks.

I have very rudimentary knowledge about floating point vs exact arithmetic.

Due to the excessive time Polymake takes to figure out lattice points, my preferred method thus far has been to use cplex to quickly enumerate the points (using faster but less accurate floating point arithmetic) and then have polymake give me the facets/affine hull (using more time consuming but exact arithmetic)

Is there any software you are aware of that computes facetial inequality and equations of the affine hull using faster but less accurate floating point arithmetic when it is provided with the set of lattice points?

Or else, is there any option in polymake itself that allows the user to work with floating point in lieu of exact arithmetic?

The thing is, we have good structural knowledge of the underlying integer program we are trying to solve. So, if we are able to get an approximate (?) facetial inequality, we would be able to figure out what it should mean exactly. So, 100% accuracy is not what we are after in our project. I hope that makes sense?

[opfer]

Is there any software you are aware of that computes facetial inequality and equations of the affine hull using faster but less accurate floating point arithmetic when it is provided with the set of lattice points?

As far as I know, both cdd and lrs should be able to do this. But you should also be able to call cdd and lrs from polymake.

Or else, is there any option in polymake itself that allows the user to work with floating point in lieu of exact arithmetic?

This should happen if you use Polytope<Float> instead of Polytope<Rational>.

[opfer]

I just did another test: I used PPL (Parma Polyhedra Library) to calculate the H-representation from these 4722 points. It took around 20 seconds to generate 414 exact rational (in)equalities. Do you know whether this number is correct?

Best regards,
Thomas

[joswig]

polymake has more than one algorithm to enumerate integer points. It is next to impossible to tell which one is best without studying the input in details. This is a rather complicated topic, and there is no easy answers to be expected here. This is why we wrote a lengthy survey with lots of experiments. Of course, floating point arithmetic is always faster (e.g., by a factor of 50 or so), but it may be unreliable, depending on the input.

Code: Select all

@article{polymake:2017, author = {Assarf, Benjamin and Gawrilow, Ewgenij and Herr, Katrin and Joswig, Michael and Lorenz, Benjamin and Paffenholz, Andreas and Rehn, Thomas}, title = {Computing convex hulls and counting integer points with \polymake}, journal = {Math. Program. Comput.}, volume = {9}, year = {2017}, number = {1}, pages = {1-38}, mrclass = {90C57 (52 90-04)}, mrnumber = {3613012}, doi = {10.1007/s12532-016-0104-z}, url = {http://dx.doi.org/10.1007/s12532-016-0104-z}, arxiv = {1408.4653v2}, }

[UserCplex]

Thomas,

I am simply unable to get such results at my end. Could you please share with me the steps you take to get the facetial representation in 20 seconds?

At my end, I have the files (within the zip file specified in the OP) containing the lattice points in a folder. From within that folder, I run the following command

linuxterminalprompt$ polymake --script getfacets.sh | tee facets.txt

getfacets.sh is the following file in the same folder:

Even though I have prefer_now "ppl";

the terminal displays:

polymake: used package cdd
cddlib
Implementation of the double description method of Motzkin et al.
Copyright by Komei Fukuda.
http://www-oldurls.inf.ethz.ch/personal ... /cdd_home/

Now the terminal is stuck for about 10 minutes with no output even though I don't have any Rational's within the script file.

[opfer]

Thomas,

I am simply unable to get such results at my end. Could you please share with me the steps you take to get the facetial representation in 20 seconds?

Yes, sure. But as I said, this was just a test (completely without polymake). Here is what I did:

1. Configure, compile and install PPL (configure with --enable-ppl_lcdd ).

2. Write all 4722 lattice points to a file suitable for PPL/CDD (see test2.txt from test2.zip -- I hope this is correct, never did this before, that's why I asked whether 414 (in)equalities sounds correct).

3. Run "ppl_lcdd test2.txt".

I would not use this in a production environment. Instead, I would write a C++ code that generates the 4722 lattice points (e.g. with CPLEX). Then I would call some API to generate the H-representation (e.g. PPL, cdd or lrs, see the paper that Michael mentioned).

Best regards,
Thomas

[UserCplex]

Thomas,

Thanks. But it is not working for me

I downloaded ppl from their website, then did configure with the enabling on, make and install.

Then, after restarting the machine, ppl_lcdd says "bash: ppl_lcdd command not found"

Is there anyway ppl can be run via polymake? In the opening credits of polymake, there seems to be ppl alread installed. Can I not just use that? I thought prefer_now in my script would do just that.

Thanks anyway.

[gawrilow]

polymake does not use ppl in the floating-point mode yet, rather for rational numbers only. There was simply no demand for that, until you came across

So if you want to use ppl with floats, you should indeed run it standalone,as Thomas proposes. I have no idea why ppl_lcdd was not built on your machine - maybe there was a warning message about some missing dependency you've overlooked when building ppl?
Have you configured a non-standard installation location not in your PATH? Do you have permissions to write to that location? By default it's /usr/local.