forum.polymake.org

Dear developers,

I am interested in vertex enumeration for a system of equations and inequalities. My question is does the CDD algorithm implemented in polymake computes a certain (insertion) ordering for the input ? or it is sensitive to the ordering of the rows of equations/inequalities in the input ?

Regards, Satya

cdd uses some heuristics to decide on the order in which the inequalities (or, dually, the points) are processed. There are ways to tweak it, if I remember correctly, but polymake just uses the default behavior. For details on cdd see http://www.inf.ethz.ch/personal/fukudak/cdd_home/.

If you find it difficult to solve a specific convex hull problem, you can also try the other implementations: beneath_beyond, lrs and ppl (where the latter is only available in recent betas). All of them have pros and cons. beneath_beyond is original polymake code, lrs (like cdd) is shipped with polymake under the GPL. For ppl we only provide bare interfaces, the code itself must be installed extra (but this is available as a package for most distros). ppl implements the same algorithm as cdd and is often faster.

We are in the middle of writing a paper with massive tests on these algorithms resulting in a few "rules of thumb". Stay tuned.

Thank you for the suggestion.

The model I am investigating is quite large but its possible to solve it with >4000 secs time threshold, but I have other models which are extremely large and the hope to solve it in all the three algorithms is extremely low. I have an (unbounded) polyhedron and interested to enumerate its generators. This large model do have some inherent structure in it but I do not know if it can be exploited to improve running time, Is there some way to compute some properties (before going for vertex enumeration) from the input and then to decide on the possible solving strategies/certain input ordering , etc ?

Regards, Satya

Try ppl and see what you get. It is totally impossible to predict the running time required if you only have the size of the input. In most cases you can only explain which algorithm would have been best after the job!