Branch and Cut

Example ILP Problem

consider the integer programming problem:

Branch and Cut - Algorithm Details

Click here to expand...

1. relax the integer constraints, which gives new problem (i.e. LP relaxation):

   Relaxed LP Problem
   objective function: min Z = -5x1 - 6x2 linear constraints: x1 + 2x2 ≤ 7 2x1 - x2 ≤ 3 non-negative variables: x1, x2 ≥ 0

2. next solve the relaxed LP problem with a general LP solver
3. the Solver returns an optimal vector/point (x₁, x₂, …, x_n) = (a, b, …, c) with value Z = something
4. this optimal vector/point can be either:

• vector values are all integers (i.e. a valid solution for ILP problem)
• vector values contain a non-integer value (i.e. not a valid solution for ILP)

5. if the vector values are all integers, we go ahead and return this vector and Z value as the optimal solution of the ILP problem
6. if the vector contains non-integer values, we have 2 choices:
7. should the LP relaxation be improved by adding a cutting plane (i.e. Cutting Plane Algorithm) (e.g. adding constraint: x₁+ x₂≤ 4)?

Click here to expand... _optimal-1

then any integer vector x, that within the feasible region of the LP satisfies the inequality:

• cx ≤ ⌊cx_optimal-1⌋

note: If with a given c we cannot cut anymore (because cx_optimal-i is already an integer), then we use another arbitrary integer vector c’ 

now let’s add the inequality to the ILP problem (note that ⌊cx_optimal-1⌋ is a numerical constant, since x_optimal-1is already known)

New ILP Problem
objective function: max Z = cx linear constraints: Ax ≤ b cx ≤ ⌊cxoptimal-1⌋ integer variables: x1 ∈ ℤ x2 ∈ ℤ … xn ∈ ℤ

this new inequality “cuts down” some part of the polytope, but guarantees to keep all integer vectors of the original feasibility region

List indent undo

then we recursively solve this New ILP Problem by repeating the algorithm

let this vector be x

2. should the problem be divided into 2 by splitting on a variable (i.e. Branch and Bound Algorithm)?

Click here to expand...

1. let’s say the algorithm chooses to split on variable x₂whose optimal value is 2.2
2. now we introduce 2 new constraints:
   1. x₂ ≤ floor(2.2) = 2
   2. x₂ ≥ ceiling(2.2) = 3
3. we add these constraints to the original problem, giving 2 new subproblems:
4. now we introduce 2 new constraints:

   ILP Subproblem 1	ILP Subproblem 2
   objective function: min Z = -5x1 - 6x2 linear constraints: x1 + 2x2 ≤ 7 2x1 - x2 ≤ 3 x2≤ 2 non-negative integer variables: x1, x2 ∈ non-negative integers	objective function: min Z = -5x1 - 6x2 linear constraints: x1 + 2x2 ≤ 7 2x1 - x2 ≤ 3 x2≥ 3 non-negative integer variables: x1, x2 ∈ non-negative integers

5. the optimal solution to the original problem will be the better of the solutions to these 2 sub-problems
6. then we recursively repeat the algorithm for each of the subproblems
   1. the solution to the LP relaxation of the first sub-problem is (1,3) with value -23. since this solution is integral, it solves the first sub-problem. this solution becomes the incumbent best known feasible solution. The optimal solution for the LP relaxation of the second subproblem is (2.5, 2), with value -24.5. Since this point is non-integral, it does not solve the subproblem. Therefore, the second sub-problem must be attacked further
   2. we can then recursively repeat the algorithm for that subproblem

7. end

Branch and Cut - Algorithm Pseudocode

using Cutting Plane Algorithm and Branch & Bound - On Infinite Domain pseudocode

BRANCH-AND-CUT(ilp-problem) {
    relaxed-lp-problem = relax-integer-constraints(ilp-problem)
    (optimal-vector, optimal-z-value) = lp-solver(relaxed-lp-problem)
    if optimal-vector contains all integers
        return (optimal-vector, optimal-z-value)
    else
		// choose between cutting-plane or branch-and-cut
		return cpa(ilp-problem, optimal-vector)
		or
		retrun bb(ilp-problem, optimal-vector)
}

cpa() {
	c = get-arbitrary-vector()
    new-ilp-problem = add-constraint(ilp-problem, "cx ≤ floor(c- optimal-vector)")
    return BRANCH-AND-CUT(new-ilp-problem)
}

bb() {
	xᵢ = choose-variable-to-branch-from() # could be anything
    xᵢ-value = get-xᵢ-value-from(optimal-vector)
    ilp-subproblem-1 = add-constraint(ilp-problem, "xᵢ ≤ floor(xᵢ-value)")
    ilp-subproblem-2 = add-constraint(ilp-problem, "xᵢ ≥ ceiling(xᵢ-value)")
    (vector-1, value-1) = BRANCH-AND-CUT(ilp-subproblem-1)
    (vector-2, value-2) = BRANCH-AND-CUT(ilp-subproblem-2)
    if value-1 > value-2
        return (vector-1, value-1)
    else
        return (vector-2, value-2)
}