Page 1 of 1

Issues solving an LP

Posted: 19 May 2021, 20:57
by Sangha52
Hello team,

I have a MIP in the file, untitled.lp that is attached. I have used 'lp2poly' to load the problem into Polymake. This MIP has both 0/1 binary variables, as well as continuous variables with their respective ranges. I'm not sure why I'm getting warnings in finding the MINIMAL_SOLUTION of this problem. I think It should be straight forward. For verification, I have checked the properties: the problem is Unbounded, Feasible and Pointed.

The Polymake script used is as follows:

Code: Select all

polytope > $x = lp2poly("Downloads/untitled.lp"); polytope > $obj= new Vector([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]); polytope > $milp = $x->MILP(LINEAR_OBJECTIVE=>$obj); polytope > print $milp->MINIMAL_SOLUTION; polymake:  WARNING: could not compute 'MINIMAL_SOLUTION' probably because of unsatisfied preconditions: precondition : POINTED ( BOUNDED: ) ( applied to parent ) precondition : BOUNDED ( to.milp: MILP.MINIMAL_VALUE, MILP.MINIMAL_SOLUTION : MILP.LINEAR_OBJECTIVE, FACETS | INEQUALITIES ) ( applied to parent ) precondition : FEASIBLE ( FACETS, AFFINE_HULL, CONE_DIM : CONE_AMBIENT_DIM ) ( applied to parent ) precondition : FEASIBLE ( VERTICES, LINEALITY_SPACE, CONE_DIM : CONE_AMBIENT_DIM ) ( applied to parent ) polytope > print $x->POINTED; true polytope > print $x->BOUNDED; false polytope > print $x->FEASIBLE; true
I tried solving it as LP by removing the "GENERAL x#13 x#31 ....." conditions in the attached 'untitled.lp'. I was able to get the MINIMAL_VALUE = 7 but how can I find all the minimal feasible solutions/computation time reports etc.?

Code: Select all

polytope > $lp = $x->LP(LINEAR_OBJECTIVE=>$obj); polytope > print $lp->MINIMAL_SOLUTION; polymake:  ERROR: Can't locate object method "MINIMAL_SOLUTION" via package "Polymake::polytope::LinearProgram__Rational" polytope > print $lp->MINIMAL_VALUE; 7
Please help me solve this MILP and find all the feasible solutions.
Thanks for your time in advance!

Re: Issues solving an LP

Posted: 20 May 2021, 09:29
by joswig
There are two issues.

(1) There is a small glitch in polymake's design of subobject properties (such as LP or MILP). The following works:

Code: Select all

> $x = lp2poly("untitled.lp"); > $obj= new Vector([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]); > $x->MILP(LINEAR_OBJECTIVE=>$obj); > print $x->MILP->MINIMAL_SOLUTION; 1 100000000000000000000 0 1 0 0 0 100000000000000000000 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 3 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 2 0 0 0 0 0
The problem is that the subobject MILP sometimes does not exist independently before you computed, e.g., the MINIMAL_SOLUTION.

(2) For MILP you want MINIMAL_SOLUTION, while for LP you want MINIMAL_VERTEX:

Code: Select all

> $x->LP(LINEAR_OBJECTIVE=>$obj); > print $x->LP->MINIMAL_VERTEX; 1 0 1/2 1/2 0 0 0 0 0 0 0 0 1 1/2 0 1/2 0 0 0 1/2 0 1/2 0 0 0 0 1/2 0 0 1/2 0 0 1/2 0 0 1/2 0 0 0 0 0 1/2 1/2 0 1 1 0 0 0 0 0 0 0 0 3 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1/2 1/2 0 0 0 0 0 0 0 0 0 2 1/2 0 0 1 0 0 0 1/2 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0

Re: Issues solving an LP

Posted: 20 May 2021, 21:06
by opfer
Please help me solve this MILP and find all the feasible solutions.
It is typically impossiple to iterate all feasible solutions of a MILP, because if the remaining LP has several solutions for the same integer assignments, any convex combination is also feasible, yielding infinitely many solutions.

Despite of this, you can possibly calculate all feasible assignments for the integer variables. Then for each of them you might be able to calculate the vertices of the remaining LP. (I doubt this helps.)

For your problem, I found 240 feasible assignments for the integer variables. I just wanted to see whether it is possible to do this calculation in appropriate time. I didn't do any further analysis of your problem.

Best regards,
Thomas

Re: Issues solving an LP

Posted: 02 Jun 2021, 00:13
by Sangha52
@joswig: your response certainly clarifies the issue. Can this solution be converted to something like "x13 = 0, x31 = 1,....." i.e. in terms of the variables and its corresponding value?
On the side note, it seems (I can be wrong here) like the number of entities in the solution are more than the number of variables included. The enumeration of the solution in terms of variables would clarify this.

Re: Issues solving an LP

Posted: 02 Jun 2021, 00:17
by Sangha52
@opfer: Thanks for the detailed response. I understand that.
For your problem, I found 240 feasible assignments for the integer variables
Can you elaborate on how were you able to find the 240 feasible solutions/assignments for the integer variables?

Re: Issues solving an LP

Posted: 02 Jun 2021, 09:23
by joswig
polymake employs a homogeneous coordinate model. That is, here and elsewhere you need to ignore the leading "1" in the solution.

Re: Issues solving an LP

Posted: 02 Jun 2021, 19:54
by opfer
Can you elaborate on how were you able to find the 240 feasible solutions/assignments for the integer variables?
I used TOSimplex (one of the MILP codes in polymake) directly. It seems, polymake is currently not capable of doing this calculation. (It requires BOUNDED for the whole thing while for TOSimplex, implicitly/explicitly bounded integer variables are sufficient.)

You can also use CPLEX to iterate all integer feasible solutions. It also finds 240 different integer feasible solutions. (Still, you have to keep in mind that CPLEX uses floating point arithmetic which can provide wrong results.)

Best regards,
Thomas