forum.polymake.org

Hi opfer,

Thank you very much for the inputs. They are very helpful.

Hi,

if you don't find the solution, could you post your 3104 points and the code you use to find the facets?

By the way: you have 32 factes (not 31) as you for some reason start counting at 0.

Best regards,
Thomas

Sure Thomas.

Here is the code to get the facets once I have the integer lattice points (3104 in number)

The files accessed in code above are output from cplex and they are provided as attachment. OOps...I am unable to attach the files, since they are too large for the system 1.3 MB in size.

Roughly "points.txt" has 3104 rows, one for each point, with coordinates space separated. The "varname.txt" file is the exact same file but one extra top row which includes the variable names space separated, both files are output from cplex.

Regards

Hi!

Could you try to zip the file and attach it afterwards? If this still does not work, could you upload it somewhere?

Best regards,
Thomas

Sure. Attaching the zipped file.

Hi,

if I add the output of "Affine hull:" (189 constraints) instead of "Facets:" (32 constraints) to the IP and make in an LP, then I obtain 178 as optimal value. (Adding the factes yields 163.429 .) I hope my colleagues can explain this. I am not an expert on how Polymake handles LPs/polyhedra.

Best regards,
Thomas

Hmm...that does seem strange. The facets of the convex hull H of an IP's feasible region should suffice to solve the IP with linear objective function. The affine hull, A, is a superset of the feasible integer region. But I am guessing that while A contains H, A need not necessarily contain L, where L is the linear programming relaxed feasible region of the IP. (I could be wrong. My real analysis is a bit rusty by now.)

That may explain why when adding the constraints pertaining to A to L, we get A\intersect L to be tighter than L.

Unless I am missing something obvious, this seems like a bug in polymake.

... Unless I am missing something obvious, this seems like a bug in polymake.

Sorry, I've kind of got lost in the lengthy discussion, it contains several possible solutions to the same problem achieved after different roundings and other modifications. Could you please reformulate this claim as a self-contained reproducible task, like this:

"Given a system of linear inequalities A*x <= B and objective function C, I expect the optimal solution V attained with x = X, with all A, B, C, V and X specified as rationals or integers."

Then we can debug it.

I am not an expert on how Polymake handles LPs/polyhedra.

There is absolutely no magic. You create a Polytope object with INEQUALITIES and EQUATIONS, then add an LP subobject with LINEAR_OBJECTIVE vector and ask for LP.MINIMAL_VALUE or LP.MAXIMAL_VALUE or LP.MINIMAL_VERTEX or LP.MAXIMAL_VERTEX. Depending on your current preferences, either your implementation of the simplex algorithm (TOSimplex) or that from lrslib or cddlib is executed.

There is absolutely no magic. You create a Polytope object with INEQUALITIES and EQUATIONS, then add an LP subobject with LINEAR_OBJECTIVE vector and ask for LP.MINIMAL_VALUE or LP.MAXIMAL_VALUE or LP.MINIMAL_VERTEX or LP.MAXIMAL_VERTEX. Depending on your current preferences, either your implementation of the simplex algorithm (TOSimplex) or that from lrslib or cddlib is executed.

This is not what I meant. I could reproduce the "problem". If I take an appropriate integer program, I get points as lattice points. If I create a new polytope out of these points and ask for the polytope's facets and add these facets to the IP and convert the IP to an LP, then the objective value is still better than the IP optimal value. I would have expected that they have the same optimal value as the "facets" should define the polytope. Maybe, polymake and I, we have a different understanding of the term "facets". If I take the affine hull constraints and add them instead, then the optimal values coincide.

Best regards,
Thomas