I have a Binary linear programming problem with a maximization objective and a set of assignment constraints like a + b + c + d + e = 1; x + y + z + w + k = 1 and so on. All the variables are binary. I am trying to solve the problem using CPLEX and the upper bounds i.e., LP relaxation is very weak. The LP solution takes the values a=b=c=d=e=1/5 and x=y=z=w=k=1/5 and so one. This makes the convergence of the branch and cut in CPLEX very bad. I was wondering if there is a way to tighten the bounds or if there are a class of valid inequalities that is capable of doing so when we have such assignment constraints. Thanks in advance.
asked
pondy |

There does not exist cutting planes or valid inequalities which cut into the polytope defined by \[ \text{conv}(\{ x\in\{ 0,1\}^n \ :\ \sum_{i\in S_j}x_i=1,\forall j\in J \}) \] where \( (S_j)_{j\in J}\) is a partition of the set \( S\) of variables. This is simply due to the polytope having all integral extreme points, wherefore the linear relaxation of the set of integer points is exactly the convex hull of integer points. This means that whenever you have a point satisfying the equalities it is in the convex hull of integer solutions and cannot be cut of. Instead you should focus on other substructures of your program or combinations of the assignment constraints and and other substructures.
answered
Sune |

I can't offer any wisdom about tightening bounds. If you have any problem-specific information that hints at some variables being preferable to others in a solution, it
answered
Paul Rubin ♦♦ |