# Difference between revisions of "Branch and cut"

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

Steward: Wei-Han Chen, Fengqi You

## Introduction

The Branch and Cut is a methodology that is used to optimize linear problems that are integer based. This concept is comprised of two known optimization methodologies - branch and bound and cutting planes. Utilizing these tools allows for the Branch and Cut to be successful by increasing the relaxation and decreasing the lower bound. The ultimate goal of this technique is to minimize the amount of nodes.

## Methodology & Algorithm

### Algorithm - Peter

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 ${\displaystyle LP_{0}}$ while setting the active nodes set as ${\displaystyle L}$. The set can be accessed via ${\displaystyle LP_{n}}$

#### Step 3. Iterate through list L:

While ${\displaystyle L}$ is not empty (i is the index of the list of L), then:

##### 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:
Else:
Continue.
```

#### Step 4. Pruning and Fathoming:

```If Z^l >= Z:
```
```If Z^l <= Z AND X_i is an integral feasible:
Z = Z^i
Remove all Z^i from Set(L)
```

#### Step 5. Partition (reference EXTERNAL SOURCE)

Let ${\displaystyle D_{j=1}^{lj=k}}$ be a partition of the constraint set ${\displaystyle D}$ of problem ${\displaystyle LP_{l}}$. Add problems ${\displaystyle D_{j=1}^{lj=k}}$ to L, where   is  with feasible region  restricted to  and  for j=1,...k is set to the value of  for the parent problem l. Go to step 3.