# Difference between revisions of "Branch and cut"

Peterghaddad (talk | contribs) (Adding Branch and Cut alg.) |
(added info) |
||

Line 3: | Line 3: | ||

Steward: Wei-Han Chen, Fengqi You | Steward: Wei-Han Chen, Fengqi You | ||

− | === Algorithm === | + | == Introduction - Lindsay == |

+ | |||

+ | == Methodology & Algorithm == | ||

+ | |||

+ | === Methodology - Haris === | ||

+ | |||

+ | === '''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). | 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: | Below is an Algorithm to utilize the Branch and Cut algorithm with Gomery cuts and Partitioning: | ||

− | Step 0: | + | ==== Step 0: ==== |

Upper Bound = ∞ | Upper Bound = ∞ | ||

Lower Bound = -∞ | Lower Bound = -∞ | ||

− | |||

+ | ==== Step 1. Initialize: ==== | ||

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

− | Step 2. Terminate: | + | ==== Step 2. Terminate: ==== |

− | |||

− | |||

+ | ==== Step 3. Iterate through list L: ==== | ||

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

− | Step 3.1. Convert to a Relaxation: | + | ===== Step 3.1. Convert to a Relaxation: ===== |

+ | Replace in by two constraints and | ||

− | + | ===== Solve 3.2. ===== | |

+ | Solve for the Relaxed | ||

− | + | ===== Step 3.3. ===== | |

− | |||

− | |||

− | |||

− | Step 3.3. | ||

If Z is infeasible: | If Z is infeasible: | ||

Return to step 3. | Return to step 3. | ||

Line 39: | Line 42: | ||

Else: | Else: | ||

Continue. | Continue. | ||

− | Step 4. Pruning and Fathoming: | + | |

+ | ==== Step 4. Pruning and Fathoming: ==== | ||

If Z^l >= Z: | If Z^l >= Z: | ||

return to step 3. | return to step 3. | ||

Line 46: | Line 50: | ||

Z = Z^i | Z = Z^i | ||

Remove all Z^i from Set(L) | Remove all Z^i from Set(L) | ||

− | |||

− | Let | + | ===== Step 5. Partition (reference EXTERNAL SOURCE) ===== |

+ | Let be a partition of the constraint set of problem . Add problems 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. | ||

+ | |||

+ | == Numerical Example - Chris == | ||

+ | |||

+ | == Application - Jon == | ||

+ | |||

+ | == Conclusion - Lindsay == | ||

+ | |||

+ | == References == |

## Revision as of 08:54, 19 November 2020

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

Steward: Wei-Han Chen, Fengqi You

## Introduction - Lindsay

## Methodology & Algorithm

### Methodology - Haris

**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 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: Return to step 3. 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: return to step 3.

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 be a partition of the constraint set of problem . Add problems 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.