Error in using lp2poly

Questions and problems about using polymake go here.
UserCplex
Posts: 31
Joined: 11 Jan 2018, 13:37

Error in using lp2poly

Postby UserCplex » 26 Nov 2019, 14:31

Hello,

I have a cplex generated LP file, problemIP_polymake.lp that is attached. This is a mixed integer program with both 0/1 binary variables, as well as continuous variables which range in [0,1]. The problem is bounded.

I have a file lp2poly.sh the contents of which are:

However, on doing so, I get the error:

Code: Select all

inhomog_var _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 y0_0_1#10 y0_1_0#11 y0_0_2#12 y0_2_0#13 y0_0_3#14 y0_3_0#15 y0_0_4#16 y0_4_0#17 y0_1_2#18 y0_2_1#19 y0_1_3#20 y0_3_1#21 y0_1_4#22 y0_4_1#23 y0_2_3#24 y0_3_2#25 y0_2_4#26 y0_4_2#27 y0_3_4#28 y0_4_3#29 y1_0_1#30 y1_1_0#31 y1_0_2#32 y1_2_0#33 y1_0_3#34 y1_3_0#35 y1_0_4#36 y1_4_0#37 y1_1_2#38 y1_2_1#39 y1_1_3#40 y1_3_1#41 y1_1_4#42 y1_4_1#43 y1_2_3#44 y1_3_2#45 y1_2_4#46 y1_4_2#47 y1_3_4#48 y1_4_3#49 y2_0_1#50 y2_1_0#51 y2_0_2#52 y2_2_0#53 y2_0_3#54 y2_3_0#55 y2_0_4#56 y2_4_0#57 y2_1_2#58 y2_2_1#59 y2_1_3#60 y2_3_1#61 y2_1_4#62 y2_4_1#63 y2_2_3#64 y2_3_2#65 y2_2_4#66 y2_4_2#67 y2_3_4#68 y2_4_3#69 y3_0_1#70 y3_1_0#71 y3_0_2#72 y3_2_0#73 y3_0_3#74 y3_3_0#75 y3_0_4#76 y3_4_0#77 y3_1_2#78 y3_2_1#79 y3_1_3#80 y3_3_1#81 y3_1_4#82 y3_4_1#83 y3_2_3#84 y3_3_2#85 y3_2_4#86 y3_4_2#87 y3_3_4#88 y3_4_3#89 polymake: ERROR: initial check failed: size mismatch between COORDINATE_LABELS and CONE_AMBIENT_DIM
I am using polymake version 3.2

Any help as to what I am doing wrong is appreciated.
Thank you.
Attachments
problemIP_polymake.lp
(8.1 KiB) Downloaded 359 times
Last edited by UserCplex on 28 Nov 2019, 11:16, edited 1 time in total.

User avatar
gawrilow
Main Author
Posts: 423
Joined: 25 Dec 2010, 17:40

Re: Error in using lp2poly

Postby gawrilow » 26 Nov 2019, 17:50

You have apparently hit an old bug - your polymake version is quite ancient.

With the current version 3.6, I don't get any error messages. However, the polytope $s is empty because $p has no lattice points.
Probably in the old version this special case wasn't handled properly.

Just upgrade your polymake installation and enjoy :)

UserCplex
Posts: 31
Joined: 11 Jan 2018, 13:37

Re: Error in using lp2poly

Postby UserCplex » 26 Nov 2019, 18:53

Thank you. I will install the latest version and try.

However, I am a bit puzzled as to why your correct version of polymake says that there is no lattice point. I know, for instance, that the following variable values is indeed optimal for the given MIP. (variable values are displayed towards the bottom of the Code segment)

Code: Select all

CPLEX> read problemIP_polymake.lp Problem 'problemIP_polymake.lp' read. Read time = 0.14 sec. (0.01 ticks) CPLEX> optimize Tried aggregator 1 time. Reduced MIP has 61 rows, 90 columns, and 290 nonzeros. Reduced MIP has 10 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.05 sec. (0.10 ticks) Found incumbent of value 4709.000000 after 0.16 sec. (0.22 ticks) Probing time = 0.00 sec. (0.01 ticks) Tried aggregator 1 time. Reduced MIP has 61 rows, 90 columns, and 290 nonzeros. Reduced MIP has 10 binaries, 0 generals, 0 SOSs, and 0 indicators. Presolve time = 0.03 sec. (0.14 ticks) Probing time = 0.00 sec. (0.01 ticks) MIP emphasis: balance optimality and feasibility. MIP search method: dynamic search. Parallel mode: deterministic, using up to 4 threads. Root relaxation solution time = 0.03 sec. (0.11 ticks) Nodes Cuts/ Node Left Objective IInf Best Integer Best Bound ItCnt Gap * 0+ 0 4709.0000 0.0000 100.00% 0 0 1869.0000 7 4709.0000 1869.0000 21 60.31% * 0+ 0 3680.0000 1869.0000 49.21% 0 0 2101.7167 5 3680.0000 Cuts: 47 39 42.89% * 0+ 0 2158.0000 2101.7167 2.61% * 0 0 integral 0 2145.0000 Cuts: 25 42 0.00% 0 0 cutoff 2145.0000 2145.0000 42 0.00% Elapsed time = 0.33 sec. (1.71 ticks, tree = 0.01 MB, solutions = 4) Flow cuts applied: 12 Mixed integer rounding cuts applied: 4 Multi commodity flow cuts applied: 8 Lift and project cuts applied: 1 Gomory fractional cuts applied: 9 Root node processing (before b&c): Real time = 0.34 sec. (1.72 ticks) Parallel b&c, 4 threads: Real time = 0.00 sec. (0.00 ticks) Sync time (average) = 0.00 sec. Wait time (average) = 0.00 sec. ------------ Total (root+branch&cut) = 0.34 sec. (1.72 ticks) Solution pool: 4 solutions saved. MIP - Integer optimal solution: Objective = 2.1450000000e+03 Solution time = 0.39 sec. Iterations = 42 Nodes = 0 Deterministic time = 1.72 ticks (4.41 ticks/sec) CPLEX> display sol var * Incumbent solution Variable Name Solution Value y0_0_1#10 1.000000 y0_1_2#18 0.500000 y0_1_4#22 0.500000 y1_1_2#38 0.428571428571429 #(I copy pasted the exact value from the .lp file right hand side here) y1_1_3#40 0.0714285714285714 #(I copy pasted the exact value from the .lp file right hand side here) y1_1_4#42 0.500000 y2_2_1#59 1.000000 y2_1_3#60 0.125000 y2_1_4#62 0.875000 y3_3_1#81 1.000000 y3_1_4#82 1.000000 _e0_1#0 1.000000 _e1_2#4 1.000000 _e1_3#5 1.000000 _e1_4#6 1.000000 All other variables matching '*' are 0.
Given that the .lp file only indicated that the _e* variables are integer, the above solution has all the _e* variables as 1 and other _e* variables not displayed in the output at 0. Does this not count as a lattice point? All of the y variables are anyway continuous in [0, 1]

UserCplex
Posts: 31
Joined: 11 Jan 2018, 13:37

Re: Error in using lp2poly

Postby UserCplex » 26 Nov 2019, 20:01

I figured out that lattice points in polymake refer exclusively to all integer points of all variables. It is indeed the case that my original .lp file does not have a feasible integer solution where all variables have to be either 0 or 1.

However, now, I am running into a different error (I upgraded to 3.6) on following the projection example given on

https://polymake.org/doku.php/user_guid ... timization

as applied to my Mixed Integer Program.

On running the following 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, which are binary 0 or 1 in the .lp file. $q->LATTICE_POINTS; print $q->COORDINATE_LABELS; printf "\n"; print $q->LATTICE_POINTS; $s = new Polytope(POINTS=>$q->LATTICE_POINTS, COORDINATE_LABELS=>$q->COORDINATE_LABELS); print_constraints($s);
the error obtained points to arbitrary_coords.rules line 194: projection: LINEAR SPAN has wrong number of rows.

User avatar
gawrilow
Main Author
Posts: 423
Joined: 25 Dec 2010, 17:40

Re: Error in using lp2poly

Postby gawrilow » 26 Nov 2019, 20:14

BTW: lp2poly returns nowadays a rational polyhedron by default, an explicit copy `$p = new Polytope<Rational>($f);` is not neccesary anymore.

User avatar
gawrilow
Main Author
Posts: 423
Joined: 25 Dec 2010, 17:40

Re: Error in using lp2poly

Postby gawrilow » 26 Nov 2019, 20:48

Well, the error message deserves an improvement, but the fact is that your polyhedron seems to become infeasible after a conversion to rational coordinates. There are two suspicious equations in your initial LP with floating-point fractional RHS; it could be that CPLEX still finds some "almost feasible" points after some tricky perturbing or generous rounding...

User avatar
gawrilow
Main Author
Posts: 423
Joined: 25 Dec 2010, 17:40

Re: Error in using lp2poly

Postby gawrilow » 26 Nov 2019, 20:57

If you leave the polyhedron with floating-point coordinates: `$p=lp2poly<Float>("input file");`
it is reported as feasible by the cdd solver, and its linear span vectors contain some very adventurous coordinates like -1.110223025e-16. The solution area of your problem seems to be defined by the intrinsic error margin of the floating-point processor.

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

Re: Error in using lp2poly

Postby opfer » 26 Nov 2019, 21:52

I guess, 0.0714285714285714 means 1/14 and 0.428571428571429 means 3/7 (never use such floating point numbers in exact arithmetic). If I multiply the corresponding constraints by 14 on the one hand and by 7 on the other hand and then make the right hand side integer, I get 2145 as optimal solution.

Best regards,
Thomas

UserCplex
Posts: 31
Joined: 11 Jan 2018, 13:37

Re: Error in using lp2poly

Postby UserCplex » 27 Nov 2019, 03:17

Thomas,

I did what you suggested -- changed the two problem constraints into integer RHS (that modified .lp file is attached with this message).

Then, I ran the following set of commands in a script:

Code: Select all

use application "polytope"; use vars qw($f $p); $f=lp2poly('problemIP_polymake.lp');#lp file from cplex. Should be OK $p = new Polytope<Rational>($f); print $p->LP->MINIMAL_VALUE; printf "\n";
Doing so, however, in my case gives the LP relaxed solution of 1869, even though the .lp file read in indicates that the _e* variables should be integer.

Could you please tell me the steps you followed within polymake to obtain 2145 as the optimal MIP solution?
Attachments
problemIP_polymake.lp
(8.1 KiB) Downloaded 357 times

User avatar
gawrilow
Main Author
Posts: 423
Joined: 25 Dec 2010, 17:40

Re: Error in using lp2poly

Postby gawrilow » 27 Nov 2019, 11:03

poly2lp produces a Polytope with an LP subobject, which is by definition a linear program without any integrality constraints. The list of INTEGER_VARIABLES is merely attached to it as a kind of comment.

Since recently, polymake can also solve MILPs, but they have to be created as MILP subobjects. poly2lp has unfortunately not yet been taught to do this, sorry for the inconvenience - this will be improved in the next release.

As a workaround for now, you have to "repackage" the Polytope object with following operations:

Code: Select all

$ints=indices(new SparseVector<Int>([ @{$f->LP->get_attachment("INTEGER_VARIABLES")} ])); $p=new Polytope<Rational>(INEQUALITIES=>$f->INEQUALITIES, EQUATIONS=>$f->EQUATIONS, 'MILP.LINEAR_OBJECTIVE'=>$f->LP->LINEAR_OBJECTIVE, 'MILP.INTEGER_VARIABLES'=>$ints, COORDINATE_LABELS=>$f->COORDINATE_LABELS);
Then you can obtain the desired result:

Code: Select all

> print $p->MILP->MINIMAL_VALUE; 2145 > print $p->MILP->MINIMAL_SOLUTION; 1 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1/2 0 0 0 1/2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3/7 0 1/14 0 1/2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1/8 0 7/8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0


Return to “Helpdesk”