Error in using lp2poly

[UserCplex]

Thank you gawrilow.

I confirm being able to get the optimal MIP solution using the workaround you provided.

For this very same problem (.lp file as attached in my immediately previous message), I was trying to project the solution space into the space of pure binary variables only (_e*) variables in the .lp file.

I followed the steps as specified in https://polymake.org/doku.php/user_guid ... timization

Specifically, I ran the following code via a script:

Code: Select all

use application "polytope"; use vars qw($f $p $q $s); $f=lp2poly('problemIP_polymake.lp');#lp file from cplex. Should be OK $p = new Polytope<Rational>($f); $q = projection($p, [1,2,3,4,5,6,7,8,9,10]);#projects p into space of 1st through 10th variables. $s = new Polytope(POINTS=>$q->LATTICE_POINTS); print_constraints($s);

The only difference between my code and the code example provided in https://polymake.org/doku.php/user_guid ... timization is that in my case, I would like to project into the space of the first 10 variables (hence the numbering 1, 2, through 10 and this ordering is obtained as the ordering in the "Bounds" section in the .lp file) since these alone are the binary 0/1 integer variables.

On running this script, my computer essentially hangs and I have to restart my machine after 30 minutes or so.

However, I cannot think of a mathematical reason for why the computation should be so expensive. If I understand the projection algorithm correctly, it should essentially enumerate 2^10 = 1024 points, (since there are 10 binary integer _e* variables in the .lp MIP file), discard the infeasible points and construct the polytope over these 10 dimensions.

Now, the very first constraint of the .lp file is:

Code: Select all

C1_0: _e0_1#0 + _e0_2#1 + _e0_3#2 + _e0_4#3 + _e1_2#4 + _e1_3#5 + _e1_4#6 + _e2_3#7 + _e2_4#8 + _e3_4#9 = 4

So, we don't even have to enumerate all 1024 point. We only have to enumerate a much smaller number of points where the sum of the coordinates is 4. Then, over these much smaller points, one would have to verify that the continuous variables can be set without causing infeasibility to them.

Would it be possible to know at which step polymake encounters the hotspot in the above computation? It appears to me that getting the facets of the feasible integer space should be a reasonably fast operation/computation in this case because the number of feasible integer points should be substantially lesser than 1024.

Thanks again for your continued support.

[gawrilow]

If you enter the lines one by one in the interactive shell, you'll see at which step it hangs.

You don't need to enter the first two lines, starting with "use".

[UserCplex]

Inside polymake, I typed sequentially.

Code: Select all

$f=lp2poly('problemIP_polymake.lp');#lp file from cplex. Should be OK $p = new Polytope<Rational>($f); $q = projection($p, [1,2]);#projects p into space of 1st and 2nd variable, which are binary integer _e0_1#0 and _e0_2#1

The last of the lines, where the projection of p into the space of two binary variables is where it hangs.

This is highly surprising to me. The space of the two variables are:

(1st feasible subvector) 0 0
(2nd feasible subvector) 0 1
(3rd feasible subvector) 1 0
(4th feasible subvector) 1 1

That is, for either values 0 or 1 of both these binary variables, the rest of the MIP is indeed feasible. I know this because I know the underlying problem allows for this. As I mentioned in the previous post, it is quite surprising that this should take this long within polymake. It appeared to me to be a small enough problem instance. I tried to change Rational to Float and that did not help either.

[gawrilow]

For every eliminated coordinate a Fourier-Motzkin elimination step is executed, which can potentially double the number of inequalities.
You are trying to eliminate 90-2=88 coordinates...

Conversion to Float is not an option, since it only can make your polyhedron infeasible, as you have experienced recently, but does not change the nature of the Fourier-Motzkin procedure.

[UserCplex]

Thank you for the additional information. I am not very knowledgeable about how FM elimination is used within the projection algorithm.

However, in this case atleast where I am projecting into the subspace of two binary integer variables, it seems to me that full fledged FM elimination (assuming that is what is causing the excessive times) is uncalled for.

The following "simplified" procedure is guaranteed to provide the lattice points of the subspace projected into.

(1) List all possibilities of the variables of the space projected into:
Given that the space in this example has two binary variables, this is (0,0), (0,1), (1,0), (1,1).
(2)For each one of these possibilities (a,b), solve reduced MIP_(a,b) where the first variable is fixed to a, and second variable is fixed to b
So, in this step, we need to check whether MIP_(0,0), MIP_(0,1), MIP_(1,0) and MIP_(1,1) have a feasible solution.
(Note) Each of the feasibility check in Step (2) is of course NP Hard in itself in general. But for this simplified problem, since the MIP is not hard to solve, this should not be computationally expensive.
(3)The lattice points are all (a,b)'s in Step (2) for which the corresponding MIP_(a,b) was integer feasible.
So, for this example, the lattice points of the subspace are (0,0), (0,1), (1,0), (1,1), since each of the four MIPs are feasible.

So, the facets of the space projected into are

(1) Variable 1 >= 0
(2) Variable 2 >= 0
(3) Variable 1 <= 1
(4) Variable 2 <= 1

Of course, as the number of binary variables increases, this will become computationally burdensome and perhaps FM elimination is more efficient as opposed to solving a sequence of MIPs for feasibility.

[opfer]

Hi UserCplex,

can you tell us, what the question is that you really want to anwer? Maybe, we need no projection to do so.

By the way, I used TOSimplex and found out that your problem has 125 different feasible solutions for the integer variables.

Best regards,
Thomas

[UserCplex]

Hi Thomas,

I am mostly (only) interested in figuring out the facets of the feasible region of the integer/binary variables in my .lp file. So, in this example, in the .lp file, I would like to know the equations defining the facets of the polyhedron (defined for integer feasible solutions) projected down/onto the space of the binary 0/1 variables. I was just following the example provided in polymake documentation (on the lp2poly page previously linked to in this thread) in the context of my problem and it seemed to run forever.

For instance, if I understand correctly, you have found that there are 125 different feasible (i.e., all the _e* variables in the .lp file have values at 0 or 1) solutions. I would like to know the facetial representation of the polytope which has these 125 different solutions as the lattice points -- i.e., the inequalities of the convex hull of these points as well as the affine hull equations that all these 125 different lattice points satisfy (if there are any).

Thanks.

[opfer]

Maybe, it is easier to feed polymake with these 125 points and let it calculate the inequalities and equalities from them. But I am really not sure about that.

Let's wait what the others say.

Best regards,
Thomas

[UserCplex]

(post edited)

Yes, that approach did work for me. I was able to get the 125 points myself and have been able to obtain the facets of the projection polytope using polymake bypassing the time-consuming FM elimination projection algorithm.

Thanks for your help.

[opfer]

By the way, this feature seems to be missing in polymake. TOSimplex can return all feasible solutions for the integer variables of a MILP, but this feature is missing in the interface to polymake.

In polymake, TOSimplex can only be used to obtain all lattice points of a polyhedron (which have to be integer in every dimension).

Anyway, I think, only few people will work with MILPs in polymake.