# Branch and cut

Author: Lindsay Siegmundt, Peter Haddad, Chris Babbington, Jon Boisvert, Haris Shaikh (SysEn 6800 Fall 2020)

Steward: Wei-Han Chen, Fengqi You

### Algorithm

Branch and Cut for is a variation of the Branch and Bound algorithm. Branch and Cut incorporates Gomery cuts allowing the search space of the given problem. The standard Simplex Algorithm will be used to solve each Integer Linear Programming Problem (LP).

Below is an Algorithm to utilize the Branch and Cut algorithm with Gomery cuts and Partitioning:

Step 0:

```Upper Bound = ∞
Lower Bound = -∞
```

Step 1. Initialize:

Set the first node as  while setting the active nodes as .

Step 2. Terminate:

Step 3. Iterate through list L:

While L is not empty (i is the index of the list of L), then:

Step 3.1. Convert  to a Relaxation:

Replace  in  by two constraints  and

Solve 3.2.

Solve  for the Relaxed

Step 3.3.

```If Z is infeasible:
else:
Continue with solution Z.
```

Step 3.2. Cutting Planes:

```If a cutting plane is found:
then add to the linear Relaxation problem (as a constraint) and return to step 3.2
Else:
Continue.
```

Step 4. Pruning and Fathoming:

```If Z^l >= Z:
```If Z^l <= Z AND X_i is an integral feasible: