Integral polyhedra

[gordonfroyle]

I am working with "matroid ports" and need to test whether certain polyhedra, given by hyperplanes, are integral (that is, have vertices with integer coordinates) or not.

So far I have been using cdd to convert the H-representation to a V-representation and then just seeing whether it is all integral (in fact, if integral it must be all 0/1).

However while polymake works fast (enough) on most of my problems, there are some, that do not seem to be of any particular size or structure, that seem to take an extreme amount of time. (In general I am looking at around 100 constraints in 25 variables, everything is 0/1.)

I am not a polyhedron expert, and so have a few questions for those who ARE polyhedron experts:

(1) Is there a better way to detect integrality, or non-integrality of a polyhedron than just computing all its vertices and looking at them?

(2) For some applications, randomly re-labelling the problem can have a massive effect on solution time; is this one such problem?

Thanks

Gordon

[paffenholz]

(1) Is there a better way to detect integrality, or non-integrality of a polyhedron than just computing all its vertices and looking at them?

Without any assumptions on the inequalities defining your polyhedron computing the vertices is the only option. There are faster ways if the defining inequalities have some special structure (e.g. the facet matrix is unimodular).

(2) For some applications, randomly re-labelling the problem can have a massive effect on solution time; is this one such problem?

Running time of most convex hull algorithms indeed depends on the order the data is presented to the algorithm. Both the order of the variables and the order of the constraints may matter, and it is hard to guess a good order a priori (e.g. reverse search depends on the order in a similar way as the simplex algorithm of linear programming). Running time of convex hull algorithms also depends on the size of the output, and their particular performance depends on the structure of the problem (e.g. whether the polyhedron is simplicial or not). Again, deciding this a priori is not possible without further assumptions on the input.

With the information you have given I cannot suggest any particular method. The dimension of your problem is already fairly big for convex hull computations. Switching to a different algorithm if one does not succeed often helps (in polymake you can choose lrs, cdd, beneath_beyond" with

Code: Select all

prefer "cdd";

or similar prior to asking for VERTICES). If you only need some of the vertices you could look into integer optimization methods. If you have some information on where a non-integral vertex should lie, then linear optimization might suffice.

Andreas

[joswig]

It seems that there is a custom made piece of software for your needs: azove by Behle. There is even a polymake interface, install azove, and then do "reconfigure 'azove.rules';" within polymake's polytope application.

This could be useful for your more tricky input. Please try it and give feedback here!

Sorry, I mixed things up. What I meant was: zerone by Lübbecke. Not so sure though that this still works. At any rate, even this other program does not fully solve the orginal problem, as it only enumerates the 0/1-vertices (and does not tell if there are others). Yet, once the 0/1-vertices are known one can either solve the polytope completeness problem to decide if the list of vertices is complete, for instance, by computing the convex hull of the 0/1-vertices. While this is not an improvement theoretically, it might very well be useful in practice.

[gordonfroyle]

Thanks for taking the time to answer my question; I have tried changing to lrs and will try reordering the constraints and see what happens. Your comments also implied another approach, but I need a few more pointers..


Every constraint in my problem has the form

x_a + x_b + ... + x_k >= 1

with all coefficients equal to one, all the right-hand-sides equal to one, and all the variables being non-negative.

Given a problem with, say, 20 variables, it would be relatively easy to enumerate all the 0/1-vectors satisfying all the constraints. So if I could identify which of the feasible points are vertices, then I'd have a list of all the vertices if the polyhedron were integral.

Could I then compare the hypothetical "integral polyhedron" with the original one and confirm that they are identical? Or rather, how can I do this in polymake?

Thanks for any other advice..

Gordon

[joswig]

First, a few general remarks: It is NP-complete to decide if a polyhedron contains one integer point or not. Checking if a polytope, given by its facets, is integral is also NP-hard [Papadimitriou and Yannakakis (1990)]. For variations and related results see the recent paper by Boros et al., Ann Oper Res (2011) 188:63–76. This means that there is no easy way out, in general.

Given a polyhedron P in R^n in terms of inequalities and one point, say x, it is easy to decide if x is a vertex of P. Then x is a vertex if and only if the dimension of the linear span of the normal vectors to the hyperplanes defined by those inequalities satisfied with equality by x equals n.