Issues solving an LP

Questions and problems about using polymake go here.
Sangha52
Posts: 10
Joined: 25 Feb 2021, 00:01

Issues solving an LP

Postby Sangha52 » 19 May 2021, 20:57

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!
Attachments
untitled.lp
(6.88 KiB) Downloaded 234 times

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

Re: Issues solving an LP

Postby joswig » 20 May 2021, 09:29

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

opfer
Developer
Posts: 80
Joined: 04 Feb 2013, 11:12

Re: Issues solving an LP

Postby opfer » 20 May 2021, 21:06

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

Sangha52
Posts: 10
Joined: 25 Feb 2021, 00:01

Re: Issues solving an LP

Postby Sangha52 » 02 Jun 2021, 00:13

@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.
Last edited by Sangha52 on 02 Jun 2021, 00:23, edited 1 time in total.

Sangha52
Posts: 10
Joined: 25 Feb 2021, 00:01

Re: Issues solving an LP

Postby Sangha52 » 02 Jun 2021, 00:17

@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?

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

Re: Issues solving an LP

Postby joswig » 02 Jun 2021, 09:23

polymake employs a homogeneous coordinate model. That is, here and elsewhere you need to ignore the leading "1" in the solution.

opfer
Developer
Posts: 80
Joined: 04 Feb 2013, 11:12

Re: Issues solving an LP

Postby opfer » 02 Jun 2021, 19:54

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


Return to “Helpdesk”