Discrepancy in computing facets of a mixed integer program

[gawrilow]

Well, there are not that many ways to define a facet, I guess. The only source of confusion I could imagine might be the concrete matrix representation: if you have a linear system A*x <= B, you have to specify INEQUALITIES and FACETS as a block matrix (B | -A)
because polymake's polyhedra are always defined as (FACETS)*x >= 0, but you surely know this already.

I don't know what do you call "affine hull". In polymake, AFFINE_HULL has a different meaning, it's the matrix B such that B*x=0 for all x in the polyhedron, aka linear span. It can't be taken "instead" of facets but they always have to come together. In the raw (possibly redundant) input they are called INEQUALITIES and EQUATIONS, later the non-redundant properties can be computed which are called FACETS and AFFINE_HULL. So you are probably using some CPLEX terminology?

Where do you obtain the "better" optimal value - with polymake (which algorithm?) or with some third-party software?

[UserCplex]

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.

Hi gawrilow,

Given a system of linear inequalities Ax <= b, x integer and linear objective function Cx to be minimized, the optimal solution to this problem is 178. Please refer to problemIP.lp for the case.

Then, I enumerate the lattice points of Ax <= b, x integer as 3104 lattice points.

I use polymake to get the facets of these 3104 lattice points. They are Dx <= e

Now, when solve the linear program

Min Cx
Such that Ax <= b, Dx <= e, x can be continuous

I expect to get the optimal solution value of 178.

Unfortunately, I do not get 178 but instead get a number lower than this. Please refer to problem.lp in my OP which represents this problem.

Even though I use CPLEX to get this objective function values, user opfer has confirmed that the same issue arises (which slightly different numbers) when using polymake solver that uses exact arithmetic. To get polymake to do this, he has taken the "problemIP.lp" file and changed all decimals in equations, multiplied them by appropriate integers and obtained an equivalent constraint that only has integer coefficients.

Thanks.

[opfer]

Well, there are not that many ways to define a facet, I guess. The only source of confusion I could imagine might be the concrete matrix representation: if you have a linear system A*x <= B, you have to specify INEQUALITIES and FACETS as a block matrix (B | -A)
because polymake's polyhedra are always defined as (FACETS)*x >= 0, but you surely know this already.

I don't know what do you call "affine hull". In polymake, AFFINE_HULL has a different meaning, it's the matrix B such that B*x=0 for all x in the polyhedron, aka linear span. It can't be taken "instead" of facets but they always have to come together. In the raw (possibly redundant) input they are called INEQUALITIES and EQUATIONS, later the non-redundant properties can be computed which are called FACETS and AFFINE_HULL. So you are probably using some CPLEX terminology?

Hmm, maybe I got confuesed another time. I took the user's code:

...
$s = new Polytope<Rational>(POINTS=>$M, COORDINATE_LABELS=>[@keys]);
print_constraints($s);

It provides "Facets" and "Affine Hull". This is what I was refering to. Maybe, you can explain what both mean in this context?

Where do you obtain the "better" optimal value - with polymake (which algorithm?) or with some third-party software?

For all other tests, I used my code (TOSimplex and my MIP solver that I recently pushed to the repository, but that has not been added to polymake, yet). I use it together with my own LP reader. Everything works on exact arithmetic without any kind of rounding.

Best regards,
Thomas

[gawrilow]

Then AffineHull is exactly what I said, the equations defining the linear span. If there are some, they must be taken together with Facets, not instead of! And they are equations, not inequalities. So you must have computed the second LP on a polyhedron of a much higher dimension!

[gawrilow]

I use polymake to get the facets of these 3104 lattice points. They are Dx <= e

Now, when solve the linear program

Min Cx
Such that Ax <= b, Dx <= e, x can be continuous

I expect to get the optimal solution value of 178.

Unfortunately, I do not get 178 but instead get a number lower than this.

Could it be that you made the same mistake as Thomas did, namely forgot to add the AFFINE_HULL computed by polymake to the list of equations of your second LP?

[UserCplex]

Hi gawrilow

Yes, I did not add the AFFINE_HULL listings. The problem I am solving is not full dimensional. So, it is indeed the case that I might have had to add those.

Let me think about this.

I will do a check later on. But I think I am beginning to make sense of the output of polymake. In 3 dimension, for a cube, polymake will only report facets and no equalities as part of the AFFINE_HULL. In 4 dimension, a 3d cube will have both FACETS as well as AFFINE_HULL. Am I right?

Thanks anycase for your help.

[gawrilow]

Every Polytope object has FACETS and AFFINE_HULL, the latter can just be empty (more precisely, is a matrix with 0 rows) when the polyhedron is full-dimensional. FACETS are by definition non-trivial inequalities, that is, for every facet there is at least one vertex point not lying in the hyperplane.

[opfer]

Thanks for elaborating. When implementing my solver code, these things were all just "constraints", as it makes a minor difference in my codes whether something is an equality or an inequality, so I somehow lost some theoretical understanding.

Best regards,
Thomas

[gawrilow]

it makes a minor difference in my codes whether something is an equality or an inequality, so I somehow lost some theoretical understanding.

Hmm, at least you should deal with them differently when importing them as input, shouldn't you?

[opfer]

it makes a minor difference in my codes whether something is an equality or an inequality, so I somehow lost some theoretical understanding.

Hmm, at least you should deal with them differently when importing them as input, shouldn't you?

Yes and no. The interface to polymake (which was not written by me) does take care of this. My LP file reader of course also checks whether a constraint is <=, >= or ==.

In the simplex code internally, this only means to set one or two bounds to the slack/artificial variable. So of course this makes a difference, but only a minor one for the rest of the implementation. Even ranged constraints (L <= a'x <= U) are possible, setting two different bounds to the slack/artificial variable.

Best regards,
Thomas