facets of a mixed ILP

[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

[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

[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

[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

[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

[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

[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

Code: Select all

$p->COORDINATE_LABELS

, 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

[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