Page 1 of 1
facets of a mixed ILP
Posted: 18 Apr 2018, 13:06
by patro
Hello,
In the spirit of this
tutorial I'm trying to use polymake to learn about potential facets of a graph partitioning mixed ILP. I am able to get some useful output for the simple graphs \( P_2 \) and \( P_3 \) within a matter of seconds but anything beyond this (\( P_4 \) or \( C_4 \) ) seems to be too much for it. Could this be normal, or am I doing something wrong?
For \( P_4 \) the ILP has ~30 variables, mostly binary, and ~200 constraints. I can post the CPLEX .lp file if that would help.
Many thanks,
Patro
Re: facets of a mixed ILP
Posted: 18 Apr 2018, 16:30
by opfer
Please post the LP file. I don't know whether it helps, but it might be interesting to have a look at it.
Best regards,
Thomas
Re: facets of a mixed ILP
Posted: 18 Apr 2018, 17:19
by patro
Here's the .lp file for partitioning \( P_4 \) into 2 connected partitions.
Thanks again.
Code: Select all
Maximize
obj: 1 y_1_2 + 1 y_2_3 + 1 y_3_4 + 1 y_4_5
Subject To
c1: -1 x_1_2 <= 0
c2: 1 x_1_2 <= 1
c3: -1 x_2_1 <= 0
c4: 1 x_2_1 <= 1
c5: -1 x_2_3 <= 0
c6: 1 x_2_3 <= 1
c7: -1 x_3_2 <= 0
c8: 1 x_3_2 <= 1
c9: -1 x_3_4 <= 0
c10: 1 x_3_4 <= 1
c11: -1 x_4_3 <= 0
c12: 1 x_4_3 <= 1
c13: -1 x_4_5 <= 0
c14: 1 x_4_5 <= 1
c15: -1 x_5_4 <= 0
c16: 1 x_5_4 <= 1
c17: -1 z_1_1 <= 0
c18: 1 z_1_1 <= 1
c19: -1 z_1_2 <= 0
c20: 1 z_1_2 <= 1
c21: -1 z_1_3 <= 0
c22: 1 z_1_3 <= 1
c23: -1 z_1_4 <= 0
c24: 1 z_1_4 <= 1
c25: -1 z_1_5 <= 0
c26: 1 z_1_5 <= 1
c27: -1 z_2_2 <= 0
c28: 1 z_2_2 <= 1
c29: -1 z_2_3 <= 0
c30: 1 z_2_3 <= 1
c31: -1 z_2_4 <= 0
c32: 1 z_2_4 <= 1
c33: -1 z_2_5 <= 0
c34: 1 z_2_5 <= 1
c35: -1 z_3_3 <= 0
c36: 1 z_3_3 <= 1
c37: -1 z_3_4 <= 0
c38: 1 z_3_4 <= 1
c39: -1 z_3_5 <= 0
c40: 1 z_3_5 <= 1
c41: -1 z_4_4 <= 0
c42: 1 z_4_4 <= 1
c43: -1 z_4_5 <= 0
c44: 1 z_4_5 <= 1
c45: -1 z_5_5 <= 0
c46: 1 z_5_5 <= 1
c47: -1 y_1_2 <= 0
c48: 1 y_1_2 <= 1
c49: -1 y_2_3 <= 0
c50: 1 y_2_3 <= 1
c51: -1 y_3_4 <= 0
c52: 1 y_3_4 <= 1
c53: -1 y_4_5 <= 0
c54: 1 y_4_5 <= 1
c55: 1 z_1_1 + 1 z_2_2 + 1 z_3_3 + 1 z_4_4 + 1 z_5_5 = 2
c56: 1 z_1_1 = 1
c57: 1 z_1_2 + 1 z_2_2 = 1
c58: 1 z_1_3 + 1 z_2_3 + 1 z_3_3 = 1
c59: 1 z_1_4 + 1 z_2_4 + 1 z_3_4 + 1 z_4_4 = 1
c60: 1 z_1_5 + 1 z_2_5 + 1 z_3_5 + 1 z_4_5 + 1 z_5_5 = 1
c61: 1 z_1_2 - 1 z_1_1 <= 0
c62: 1 z_1_3 - 1 z_1_1 <= 0
c63: 1 z_1_4 - 1 z_1_1 <= 0
c64: 1 z_1_5 - 1 z_1_1 <= 0
c65: 1 z_2_3 - 1 z_2_2 <= 0
c66: 1 z_2_4 - 1 z_2_2 <= 0
c67: 1 z_2_5 - 1 z_2_2 <= 0
c68: 1 z_3_4 - 1 z_3_3 <= 0
c69: 1 z_3_5 - 1 z_3_3 <= 0
c70: 1 z_4_5 - 1 z_4_4 <= 0
c71: 1 z_1_2 + 1 z_1_1 + 1 y_1_2 <= 2
c72: 1 z_1_3 + 1 z_1_2 + 1 y_2_3 <= 2
c73: 1 z_2_3 + 1 z_2_2 + 1 y_2_3 <= 2
c74: 1 z_1_4 + 1 z_1_3 + 1 y_3_4 <= 2
c75: 1 z_2_4 + 1 z_2_3 + 1 y_3_4 <= 2
c76: 1 z_3_4 + 1 z_3_3 + 1 y_3_4 <= 2
c77: 1 z_1_5 + 1 z_1_4 + 1 y_4_5 <= 2
c78: 1 z_2_5 + 1 z_2_4 + 1 y_4_5 <= 2
c79: 1 z_3_5 + 1 z_3_4 + 1 y_4_5 <= 2
c80: 1 z_4_5 + 1 z_4_4 + 1 y_4_5 <= 2
c81: 1 x_1_2 - 1 z_1_2 + 1 z_1_1 <= 1
c82: 1 x_1_2 - 1 z_1_1 + 1 z_1_2 <= 1
c83: 1 x_2_1 - 1 z_1_1 + 1 z_1_2 <= 1
c84: 1 x_2_1 - 1 z_1_2 + 1 z_1_1 <= 1
c85: 1 x_2_3 - 1 z_1_3 + 1 z_1_2 <= 1
c86: 1 x_2_3 - 1 z_1_2 + 1 z_1_3 <= 1
c87: 1 x_2_3 - 1 z_2_3 + 1 z_2_2 <= 1
c88: 1 x_2_3 - 1 z_2_2 + 1 z_2_3 <= 1
c89: 1 x_3_2 - 1 z_1_2 + 1 z_1_3 <= 1
c90: 1 x_3_2 - 1 z_1_3 + 1 z_1_2 <= 1
c91: 1 x_3_2 - 1 z_2_2 + 1 z_2_3 <= 1
c92: 1 x_3_2 - 1 z_2_3 + 1 z_2_2 <= 1
c93: 1 x_3_4 - 1 z_1_4 + 1 z_1_3 <= 1
c94: 1 x_3_4 - 1 z_1_3 + 1 z_1_4 <= 1
c95: 1 x_3_4 - 1 z_2_4 + 1 z_2_3 <= 1
c96: 1 x_3_4 - 1 z_2_3 + 1 z_2_4 <= 1
c97: 1 x_3_4 - 1 z_3_4 + 1 z_3_3 <= 1
c98: 1 x_3_4 - 1 z_3_3 + 1 z_3_4 <= 1
c99: 1 x_4_3 - 1 z_1_3 + 1 z_1_4 <= 1
c100: 1 x_4_3 - 1 z_1_4 + 1 z_1_3 <= 1
c101: 1 x_4_3 - 1 z_2_3 + 1 z_2_4 <= 1
c102: 1 x_4_3 - 1 z_2_4 + 1 z_2_3 <= 1
c103: 1 x_4_3 - 1 z_3_3 + 1 z_3_4 <= 1
c104: 1 x_4_3 - 1 z_3_4 + 1 z_3_3 <= 1
c105: 1 x_4_5 - 1 z_1_5 + 1 z_1_4 <= 1
c106: 1 x_4_5 - 1 z_1_4 + 1 z_1_5 <= 1
c107: 1 x_4_5 - 1 z_2_5 + 1 z_2_4 <= 1
c108: 1 x_4_5 - 1 z_2_4 + 1 z_2_5 <= 1
c109: 1 x_4_5 - 1 z_3_5 + 1 z_3_4 <= 1
c110: 1 x_4_5 - 1 z_3_4 + 1 z_3_5 <= 1
c111: 1 x_4_5 - 1 z_4_5 + 1 z_4_4 <= 1
c112: 1 x_4_5 - 1 z_4_4 + 1 z_4_5 <= 1
c113: 1 x_5_4 - 1 z_1_4 + 1 z_1_5 <= 1
c114: 1 x_5_4 - 1 z_1_5 + 1 z_1_4 <= 1
c115: 1 x_5_4 - 1 z_2_4 + 1 z_2_5 <= 1
c116: 1 x_5_4 - 1 z_2_5 + 1 z_2_4 <= 1
c117: 1 x_5_4 - 1 z_3_4 + 1 z_3_5 <= 1
c118: 1 x_5_4 - 1 z_3_5 + 1 z_3_4 <= 1
c119: 1 x_5_4 - 1 z_4_4 + 1 z_4_5 <= 1
c120: 1 x_5_4 - 1 z_4_5 + 1 z_4_4 <= 1
c121: 1 x_1_2 + 1 x_2_1 + 1 y_1_2 <= 1
c122: 1 x_2_3 + 1 x_3_2 + 1 y_2_3 <= 1
c123: 1 x_3_4 + 1 x_4_3 + 1 y_3_4 <= 1
c124: 1 x_4_5 + 1 x_5_4 + 1 y_4_5 <= 1
c125: 1 z_1_1 + 1 x_2_1 = 1
c126: 1 z_2_2 + 1 x_1_2 + 1 x_3_2 = 1
c127: 1 z_3_3 + 1 x_2_3 + 1 x_4_3 = 1
c128: 1 z_4_4 + 1 x_3_4 + 1 x_5_4 = 1
c129: 1 z_5_5 + 1 x_4_5 = 1
c130: 1 l_1 = 0
c131: -1 l_1 <= 0
c132: 1 l_1 <= 4
c133: 1 l_1 + 5 z_1_1 <= 5
c134: -1 l_2 <= 0
c135: 1 l_2 <= 4
c136: 1 l_2 + 5 z_2_2 <= 5
c137: -1 l_3 <= 0
c138: 1 l_3 <= 4
c139: 1 l_3 + 5 z_3_3 <= 5
c140: -1 l_4 <= 0
c141: 1 l_4 <= 4
c142: 1 l_4 + 5 z_4_4 <= 5
c143: -1 l_5 <= 0
c144: 1 l_5 <= 4
c145: 1 l_5 + 5 z_5_5 <= 5
c146: 5 x_1_2 - 1 l_2 + 1 l_1 <= 4
c147: 1 l_2 - 1 l_1 + 5 x_1_2 <= 6
c148: 5 x_2_1 - 1 l_1 + 1 l_2 <= 4
c149: 1 l_1 - 1 l_2 + 5 x_2_1 <= 6
c150: 5 x_2_3 - 1 l_3 + 1 l_2 <= 4
c151: 1 l_3 - 1 l_2 + 5 x_2_3 <= 6
c152: 5 x_3_2 - 1 l_2 + 1 l_3 <= 4
c153: 1 l_2 - 1 l_3 + 5 x_3_2 <= 6
c154: 5 x_3_4 - 1 l_4 + 1 l_3 <= 4
c155: 1 l_4 - 1 l_3 + 5 x_3_4 <= 6
c156: 5 x_4_3 - 1 l_3 + 1 l_4 <= 4
c157: 1 l_3 - 1 l_4 + 5 x_4_3 <= 6
c158: 5 x_4_5 - 1 l_5 + 1 l_4 <= 4
c159: 1 l_5 - 1 l_4 + 5 x_4_5 <= 6
c160: 5 x_5_4 - 1 l_4 + 1 l_5 <= 4
c161: 1 l_4 - 1 l_5 + 5 x_5_4 <= 6
Bounds
0 <= x_1_2 <= 1
0 <= x_2_1 <= 1
0 <= x_2_3 <= 1
0 <= x_3_2 <= 1
0 <= x_3_4 <= 1
0 <= x_4_3 <= 1
0 <= x_4_5 <= 1
0 <= x_5_4 <= 1
l_1 free
l_2 free
l_3 free
l_4 free
l_5 free
z_1_1 free
z_1_2 free
z_1_3 free
z_1_4 free
z_1_5 free
z_2_2 free
z_2_3 free
z_2_4 free
z_2_5 free
z_3_3 free
z_3_4 free
z_3_5 free
z_4_4 free
z_4_5 free
z_5_5 free
y_1_2 free
y_2_3 free
y_3_4 free
y_4_5 free
General
x_1_2
x_2_1
x_2_3
x_3_2
x_3_4
x_4_3
x_4_5
x_5_4
l_1
l_2
l_3
l_4
l_5
End
Re: facets of a mixed ILP
Posted: 18 Apr 2018, 20:57
by opfer
Hi,
thanks for the LP file. Could you please elaborate a little on which information you need. Solving the LP and iterating the integer solutions seems rather easy. There are only 4 different feasible assignments for the integer variables. Are you looking for facets that belong to the convex hull of all feasible solutions of the problem? Or are you just looking for some/"all" solutions?
Best regards,
Thomas
Re: facets of a mixed ILP
Posted: 18 Apr 2018, 22:33
by patro
Are you looking for facets that belong to the convex hull of all feasible solutions of the problem? Or are you just looking for some/"all" solutions?
The former. I'm hoping I can learn something from facets of the convex hull of these small problems that might scale up to larger problems.
Thanks again.
Patro
Re: facets of a mixed ILP
Posted: 19 Apr 2018, 07:39
by opfer
Well, I have to admit that I don't know whether there is an algorithm for calculating mixed-integer polytopes in polymake. We will have to ask my colleagues.
In the tutorial that you mentioned, the continuous variables are projected out. Do you want to keep them or do you want to project them out?
Best regards,
Thomas
Re: facets of a mixed ILP
Posted: 19 Apr 2018, 17:29
by patro
Yes, perhaps I should look at projecting out the continuous variables. Some of these variables are /implicitly/ binary though. Will there a performance gain in polymake if I explicitly declare in the .lp file variables to be binary (that are implicitly so)?
Also, I note that the projection command takes as argument a vector of dimension numbers to project onto. Is there a dictionary in polymake that I can lookup so that I get the right dimension number for, say, x_1_3? Something like a hash in perl, along the lines, $dimNum{'x_1_3'}? (Edit: maybe this is possible through an inversion of
, right?)
Finally, I note from browsing the "Computing convex hulls and counting integer points with polymake" paper that you performed experiments on \( C_{10}, K_7 \) yet I am struggling with \( P_4 \) in my model. Do you think this is down to the number of constraints in my model? There are ~105 constraints in the associated model.
Thanks,
Patro
Re: facets of a mixed ILP
Posted: 19 Apr 2018, 20:46
by opfer
Yes, perhaps I should look at projecting out the continuous variables. Some of these variables are /implicitly/ binary though. Will there a performance gain in polymake if I explicitly declare in the .lp file variables to be binary (that are implicitly so)?
I cannot answer this for sure, but I think projecting out fewer variables might lead to (much) fewer constraints. But of course, you might experience other difficulties.
Maybe, you also want to have a look at
this post.
Concerning your other questions, my colleagues will have to answer them.
Best regards,
Thomas