What is the faster way I can compute the integer convex hull of an ILP formulation?

Questions and problems about using polymake go here.
matheusota
Posts: 1
Joined: 20 Mar 2019, 02:59

What is the faster way I can compute the integer convex hull of an ILP formulation?

Postby matheusota » 20 Mar 2019, 03:05

Hi guys,

I'm currently using polymake to try to discover new facets for a combinatorial optimization problem. So I'm following this tutorial:
https://polymake.org/doku.php/user_guid ... timization

The problem is that this is taking too long (more than 12 hours) even for small instances. Is there any way I can make this faster? On average, how much does it take? My current instance have 14 variables and 65 constraints.

Thanks!
Matheus

User avatar
joswig
Main Author
Posts: 280
Joined: 24 Dec 2010, 11:10

Re: What is the faster way I can compute the integer convex hull of an ILP formulation?

Postby joswig » 20 Mar 2019, 14:32

This is impossible to judge without seeing the data (and the precise steps that you took). Please also recall that deciding whether or not a polyhedron, given in terms of inequalities, admits a feasible point with integer coordinates is an NP-hard problem.

That said: computing integer hulls in polymake employs computing first all lattice points and then their convex hull. For more details, experiments and timings please see
  • Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz and Thomas Rehn. Computing convex hulls and counting integer points with polymake. Math. Program. Comput. 9 (2017), no. 1, 1-38. https://link.springer.com/article/10.10 ... 016-0104-z


Return to “Helpdesk”