Branch and cut

Question 1

Motivation for branch and cut

Answer 1

Making the LP relaxations stronger by using valid inequalities.

With regular branch and bound, we used no such things. Only the cutting plane method of Gomory was used, and that approach is very different.

Question 2

Motivation for constraint branching

Answer 2

The standard way of picking a variable to branch on, is to take the one with the largest fractional value. This works well on some problems, but other problems have a structure that is not idea lfor this.

Consider partitioning problems. Set partitioning is about choosing a number of sub-sets so that all objects are represented exactly once.

What we ideally want, is to set one variable (subset) to 1, and force other variables (subsets with shared items) to 0. this would make a significant impact on the feasible region.

We can achieve the desired effect by constraint branching

Question 3

broadly explain constraint branching for a BIP case

Answer 3

instead of branching by forcing a variable to take value 0, and value 1, we use a constraint with value 0 or 1.

∑xj = 0
∑xj = 1

for a suitable selection set of the entire set of variables

Question 4

elaborate on constraint branching with regards to set partitioning

Answer 4

in set partitioning, we have one constraint per object. Basically, we force that the sum of variables, for each object, must equal to 1.

we say that each constraint will be covered by one or more variables, essentially saying that (given soltuion exist) a number between 1 and infinite number of variables (sub set objects) will make the constraint satisfied, which means that the specific item is represented.

For each pair of constraints, p and q, we can define variables j in J_pq that have a constraint coefficient that is non-zero for both constraint p and constraint q.

J_pq = {j | a_pj = 1 and a_qj = 1}

in the constraints, we always sum over j. Therefore, these are from 2 different constraints, p and q. p and q correspond to items. And the requirement is that the item is represented in the same set, j. So, this is the same as saying that we want to find variables j that have the property of including both p and q.

Now that we have found a set of variables with the property that the same two items are represetned in all of these sub-set-objects, we can create a constraint:
∑xj [j in J_pq] = 1
and one other constraint:
∑xj [j in J_pq] = 0

We need both because we are essentially saying “either we pick a subset where both are included, or we pick a subset where both are not included”. In either case, we enforce many restrictions on variables.