Discrepancy in computing facets of a mixed integer program

Questions and problems about using polymake go here.

Moderator: Moderators

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

Discrepancy in computing facets of a mixed integer program

Postby UserCplex » 26 Feb 2018, 10:58

Hello,

Attached is a mixed-integer program in .lp format "problemIP.lp" The optimal solution is 178 which I compute using CPLEX software.

I enumerate all feasible points of this mixed integer program using my own method outside of polymake and it lists 3104 points. Then, using polymake, I compute the facets of these set of 3104 points. There are 31 facets reported for this problem by polymake as:

Code: Select all

Facets: 0: 210 C1 + 30 C2 + 20 C4 - 20 C5 + 20 C7 + 120 x0_1_2 - 40 x0_1_3 - 40 x0_2_3 - 40 x0_6_3 - 80 x0_4_5 - 5 V0_7_8 - 8 V0_7_9 >= 950 1: -21 C1 - 3 C2 + C3 - 12 x0_1_2 + 6 x0_1_3 + 6 x0_2_3 + 2 x0_6_3 >= -75 2: 3 C1 + C2 - C3 - 6 x0_1_3 - 6 x0_2_3 - 2 x0_6_3 >= 1 3: 7 C1 + C2 + 4 x0_1_2 >= 29 4: -16 x0_5_7 + V0_7_8 >= 0 5: -6 C1 - 2 C2 - 4 C3 - 4 C4 - 12 C5 - 8 C6 - 4 C7 + 32 x0_5_7 - 3 V0_7_8 >= -426 6: 15 C1 + 5 C2 + 10 C3 + 10 C4 + 10 C5 + 20 C6 + 10 C7 - 2 V0_7_9 >= 745 7: -210 C1 - 30 C2 - 20 C7 - 120 x0_1_2 + 40 x0_1_3 + 40 x0_2_3 + 40 x0_6_3 - 40 x0_4_5 + 5 V0_7_8 + 8 V0_7_9 >= -1110 8: 210 C1 + 30 C2 - 20 C4 + 20 C5 + 20 C7 + 120 x0_1_2 - 40 x0_1_3 - 40 x0_2_3 - 40 x0_6_3 + 80 x0_4_5 - 5 V0_7_8 - 8 V0_7_9 >= 1190 9: 700 C1 + 100 C2 + 40 C7 + 400 x0_1_2 - 160 x0_1_3 - 160 x0_2_3 - 160 x0_6_3 - 80 x0_3_4 - 5 V0_7_8 - 12 V0_7_9 >= 3220 10: 40 C5 - 160 x0_5_7 + 15 V0_7_8 + 12 V0_7_9 >= 640 11: 7 C1 + C2 - C3 + 4 x0_1_2 - 6 x0_1_3 - 2 x0_2_3 - 2 x0_6_3 >= 17 12: -700 C1 - 100 C2 - 40 C3 + 40 C4 - 40 C7 - 400 x0_1_2 + 160 x0_1_3 + 160 x0_2_3 + 160 x0_6_3 + 160 x0_3_4 + 5 V0_7_8 + 12 V0_7_9 >= -3060 13: x0_1_3 >= 0 14: x0_5_7 >= 0 15: 168 C1 + 24 C2 + 8 C5 + 16 C7 + 96 x0_1_2 - 32 x0_1_3 - 32 x0_2_3 - 32 x0_6_3 + 32 x0_4_5 - V0_7_8 - 4 V0_7_9 >= 1016 16: -140 C1 - 20 C2 + 40 C4 + 40 C7 - 80 x0_1_2 + 80 x0_1_3 + 80 x0_2_3 + 80 x0_6_3 + 160 x0_3_4 - 5 V0_7_8 - 12 V0_7_9 >= 540 17: -700 C1 - 100 C2 + 40 C3 - 40 C4 - 40 C7 - 400 x0_1_2 + 160 x0_1_3 + 160 x0_2_3 + 160 x0_6_3 - 160 x0_3_4 + 5 V0_7_8 + 12 V0_7_9 >= -3540 18: x0_6_3 >= 0 19: -7 C1 - C2 + C3 + 6 x0_1_3 + 2 x0_2_3 + 2 x0_6_3 >= -17 20: -x0_9_3 >= -1 21: -x0_9_4 >= -1 22: -x0_9_5 >= -1 23: -x0_9_8 >= -1 24: -C9 >= -20 25: -7 C1 - C2 - 2 C7 - 4 x0_1_2 + 2 C9 >= -29 26: x0_9_5 >= 0 27: -3 C1 - C2 + C3 + 2 x0_1_3 + 2 x0_2_3 - 2 x0_6_3 >= -5 28: x0_9_3 >= 0 29: C1 - x0_1_3 >= 3 30: x0_9_8 >= 0 31: x0_9_4 >= 0
Then, I include these facets as hard inequalities into the MIP and change the MIP into an LP. That is, to the "problemIP.lp" file, I add these 31 constraints and then remove the general variables at the bottom. This creates a new file called "problem.lp". However, on solving "problem.lp" using CPLEX as a linear program, it reports the optimal LP solution as 168.62.

This is highly surprising for me. I expected the optimal LP solution to "problem.lp" to be exactly 178 since we have added the 31 facets that approximate the integer convex hull.

I am using polymake 3.0 for enumerating the facets.

Also, when I use lp2poly function of polymake, on the MIP file, to enumerate the facets, as specified by

https://polymake.org/doku.php/tutorial/optimization

I get "INPUT polytope must be bounded error."

Is it possible to clarify why these discrepancies occur?

Thanks.
Attachments
problem.lp
(28.45 KiB) Downloaded 93 times
problemIP.lp
(28.2 KiB) Downloaded 78 times

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

Re: Discrepancy in computing facets of a mixed integer program

Postby gawrilow » 26 Feb 2018, 11:47

Regarding
...
I am using polymake 3.0 for enumerating the facets.

Also, when I use lp2poly function of polymake, on the MIP file, to enumerate the facets, as specified by

https://polymake.org/doku.php/tutorial/optimization

I get "INPUT polytope must be bounded error."
There was a bug in lp2poly fixed in the current release 3.2. Please give it a try.

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

Re: Discrepancy in computing facets of a mixed integer program

Postby UserCplex » 26 Feb 2018, 11:59

Hello,

Thank you. I am new to linux actually and am having sufficient struggle getting my system to work with various dependencies, etc. So, I don't want to install a time consuming polymake3.2 just yet. Is it possible for me to run the steps provided in

https://polymake.org/doku.php/tutorial/optimization

on https://polymake.org/shell/?

That is, does the web shell provide a way to store the .lp file "online" and read and compute the facets via lp2poly on that interface itself?

I am still keen in figuring out whether the facets reported by 3.0 (0 through 31) for the problem I indicated in the OP are valid.

Thanks.

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

Re: Discrepancy in computing facets of a mixed integer program

Postby gawrilow » 26 Feb 2018, 12:08

I am new to linux actually and am having sufficient struggle getting my system to work with various dependencies, etc. So, I don't want to install a time consuming polymake3.2 just yet.
Try the docker image. It's been designed for exactly such cases.
Does the web shell provide a way to store the .lp file "online" and read and compute the facets via lp2poly on that interface itself?
No, the web instance primarily serves a demonstration purpose, it does not allow to store files. Besides that, it's still running the old version with the bug.
I am still keen in figuring out whether the facets reported by 3.0 (0 through 31) for the problem I indicated in the OP are valid.
Surely, that's the most intriguing part. But even if it's a bug, it's only going to be fixed in the current version, therefore please verify that first.

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

Re: Discrepancy in computing facets of a mixed integer program

Postby UserCplex » 26 Feb 2018, 12:22

Okay. I will try as you suggest.

In the meantime, assuming you have access to an MIP solver (and therefore an LP solver) at your end that can read in the files I provided in the OP, I would be really grateful if any of the polymake developers can verify if the discrepancy exists on 3.2. My OP is detailed enough to be able to replicate and see the issues.

Please do not get me wrong. I appreciate the help all of you provide -- afaik, this is the only polytope software for which there is an active interaction between users and developers. I am grateful and I can understand your time constraints as well.

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

Re: Discrepancy in computing facets of a mixed integer program

Postby joswig » 26 Feb 2018, 16:46

In the meantime, assuming you have access to an MIP solver (and therefore an LP solver) at your end that can read in the files I provided in the OP, I would be really grateful if any of the polymake developers can verify if the discrepancy exists on 3.2. My OP is detailed enough to be able to replicate and see the issues.
Sorry, but this is really asking for too much. We are ready to provide all the help with using our software, but we cannot analyze the use of other software.

Let me give you one hint though (which may or may not be relevant): commercial LP/ILP/MIP solvers employ floating point arithmetic, and this does not go well with combinatorial computations.

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

Re: Discrepancy in computing facets of a mixed integer program

Postby joswig » 26 Feb 2018, 16:51

OK, I did one test with your example.

Code: Select all

polytope> $lp=lp2poly "/tmp/problem.lp";

Code: Select all

polytope> print $lp->LP->MINIMAL_VALUE; 2917698461538468882086/17303076923076959125

Code: Select all

polytope> print convert_to<Float>($lp->LP->MINIMAL_VALUE); 168.623099493198
So cplex seems to be right about the LP.

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

Re: Discrepancy in computing facets of a mixed integer program

Postby UserCplex » 26 Feb 2018, 17:14

Hi joswig and gawrilow:

My intention was never to request help from you regarding CPLEX. This was more a question about the polyhedral aspect of the problem in the OP -- an IP's solution is 178 and yet the LP relaxed solution of the same problem with added facets did not return the same solution of 178 -- which is completely independent of whether the LP or IP is solved by CPLEX or by some other tool.

In any case, I appreciate your assistance.

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

Re: Discrepancy in computing facets of a mixed integer program

Postby opfer » 26 Feb 2018, 21:36

Hi,

I solved your IP file in exact arithmetic and obtained 217 as optimal value. The polytope has 704 lattice points. Maybe the CPLEX solution is slightly infeasible in respect to your data.

Your file contains some fractional values like 4.61538461538461. This might be ill-posed. While floating point based solvers work with tolerances, polymake does not. I guess what you mean is the following:

4.61538461538461 -> 60/13
1.53846153846154 -> 20/13
0.142857142857143 -> 1/7
0.285714285714286 -> 2/7
0.428571428571429 -> 3/7
0.475247524752475 -> 48/101
1.18811881188119 -> 120/101
0.99009900990099 -> 100/101
1.78217821782178 -> 180/101

If I do these substitutions and multipliy the corresponding constraints with the common denominator, 178 is the optimal solution. (I have not yet determined the number of lattice points.)

So, if you want to do theoretical research, please stop relying on inexact solvers. They work very well for practical problems and in applied research, but not for theoretical problems.

I don't know whether this is the reason for the discrepancy, but without reliable input data, it will be hard to determine the problem. I think in a first step, you should somehow verify the 3104 points. Unfortunately, my algorithm has not terminated yet. (I don't know whether it will ever terminate...)

Best regards,
Thomas

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

Re: Discrepancy in computing facets of a mixed integer program

Postby opfer » 26 Feb 2018, 22:37

Good news: My algorithm terminated. Result:
Normally Finished. Solution status: optimal
Optimal value: 178
3104 solutions.
So with the file containing the above mentioned substitutions, I obtain the same optimal value and the same amount of lattice points. While I did not check that these are the same points as in CPLEX, I would expect it as the numerics is not too bad.

Another question: Did you check that all coordinates of your 3104 points are integer, not something like 1.0000001 which happens in CPLEX from time to time. In doubt, please round them.

Best regards,
Thomas


Return to “Helpdesk”

cron