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 methodology was discovered in the 90s as a way to solve/optimize Mixed-Integer Linear Programs (Karamanov, Miroslav). This concept is comprised of two known optimization methodologies - Branch and Bound and Cutting Planes. Utilizing these two tools allows for the Branch and Cut to find an optimal solution through relaxing the problem to produce the upper bound. Relaxing the problem allows for the complex problem to be simplified in order for it to be solve more easily. Furthermore, the upper bound represents the highest value the objective can take in order to be feasible. The optimal solution is found when the objective is equal to the upper bound (Luedtke, Jim). This methodology is critical to the future of optimization since it combines two common tools in order to utilize each component in order to find the optimal solution. Moving forward, the critical components of different methodologies could be combined in order to find optimality in a more simple and direct manner.

Methodology & Algorithm

Methodology

Abbreviation Details

Acronym	Expansion
LP	Linear Programming
B&B	Branch and Bound

Most Infeasible Branching:

Most infeasible branching is a very popular method that picks the variable with fractional part closest to $0:5$, i.e.,$si=0:5-|xA_{i}-xA_{i}-0:5|$. Most infeasible branching picks a variable where the least tendency can be recognized to which side the variable should be rounded. However, the performance of this method is not any superior to the rule of selecting a variable randomly.

Strong Branching:

For each fractional variable, strong branching tests the dual bound increase by computing the LP relaxations result from the branching on that variable. As a branching variable for the current for the current node, the variable that leads to the largest increases is selected. Despite its obvious simplicity, strong branching is so far the most powerful branching technique in terms of the number of nodes available in the B&B tree, this effectiveness can however be accomplished only at the cost of computation.

Pseudo Cost:

Pure psuedo cost branching

Another way to approximate a relaxation value is by utilizing a pseudo cost method. The pseudo-cost of a variable is an estimate of the per unit change in the objective function from making the value of the variable to be rounded up or down.  For each variable we choose variable with the largest estimated LP objective gain.  

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).

$$min:c^{t}x$$

$s.t.Ax<b$

$x>=0$

$x_{i}=int,i=1,2,3...,n$

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

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:

Solve 3.2.

Solve for the Relaxed

Step 3.3.

If Z is infeasible:
   Return to step 3.
else:
   Continue with solution Z.

Step 4. 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 5. Pruning and Fathoming:

(a)If ≥ Z:, then go 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 6. Partition

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

Numerical Example

First, list out the problem:

min z = -8x1 - 7x2

s.t. 5x₁ - x₂ ≤ 13

    -x1 + 5x2 ≤ 4

    x1, x2 ≥ 0 

First Solution of MILP = Min = -32.625 (x₁ = 2.875, x₂ = 1.3750)

Branch:

min z = -8x₁ - 7x₂

s.t. 5x₁ - x₂ ≤ 13

    -x1 + 5x2 ≤ 4

    x1 ≤ 2

    x2 ≥ 0 

    Second Solution of MILP = Min = -24.4 (x1 = 2, x2 = 1.2) 

Branch:

min z = -8x₁ - 7x₂

s.t. 5x₁ - x₂ ≤ 13

    -x1 + 5x2 ≤ 4

    x1 ≤ 2

    x2 ≥ 0 

Add Cut:

min z = -8x₁ - 7x₂

s.t. 5x₁ - x₂ ≤ 13

    -x1 + 5x2 ≤ 4

    2x1 ≤ 6 (Cut Dividing equation 1 by 2)

    x1 ≤ 2

    x2 ≥ 0 

Solution with cut = Min = -24.4 (x₁ = 2, x₂ = 1.2)

Application

Several of the Branch and Cut applications are described below in more detail and how they can be used. These applications serve as methods in which Branch and Cut can be used to optimize various problems efficiently.

Combinatorial Optimization

Combinatorial Optimization is a great application for Branch and Cut. This style of optimization is the methodology of utilizing the finite known sets and information of the sets to optimize the solution. The original intent for this application was for maximizing flow as well as in the transportation industry. This combinatorial optimization has also taken on some new areas where it is used often. Combinatorial Optimization is now an imperative component in studying artificial intelligence and machine learning algorithms to optimize solutions. The finite sets that Combinatorial Optimization tends to utilize and focus on includes graphs, partially ordered sets, and structures that define linear independence call matroids.

Bender’s Decomposition

Bender’s Decomposition is a great use in Stochastic Programming instances. Bender’s Decomposition is where you take the initial problem and divide into two distinct subsets. By dividing the problem into two separate problems you are able to solve each set easier than the original instance. Therefore the first problem within the subset created can be solved for the first variable set. The second sub problem is then solved for, given that first problem solution. Doing this allows for the sub problem to be solved to determine whether the first problem is infeasible. Bender’s cuts can be added to constrain the problem until a feasible solution can be found.

Large-Scale Symmetric Traveling Salesmen Problem

The Large-Scale Symmetric Traveling Salesmen Problem is a common problem that was always looked into optimizing for the shortest route while visiting each city once and returning to the original city at the end. On a larger scale this style of problem must be broken down into subsets or nodes. By constraining this style of problem such as the methods of Combinatorial Optimization, the Traveling Salesmen Problem can viewed as partially ordered sets. By doing this on a large scale with finite cities you are able to optimize the shortest path taken and ensure each city is only visited once.

Submodular Function

Submodular Function is another function in which is used throughout artificial intelligence as well as machine learning. The reason for this is because as inputs are increased into the function the value or outputs decrease. This allows for a great optimization features in the cases stated above because inputs are continually growing. This allows for machine learning and artificial intelligence to continue to grow based on these algorithms. By enforcing new inputs to the system the system will learn more and more to ensure it optimizes the solution that is to be made.

Conclusion

The Branch and Cut is an optimization algorithm used to optimize integer linear programming. It combines two other optimization algorithms - branch and bound and cutting planes in order to utilize the results from each method in order to create the most optimal solution. There are three different methodologies used within the specific method - most infeasible branching, strong branching, and pseudo code. Furthermore, Branch and Cut can be utilized it multiple scenarios - Submodular function, large-scale symmetric traveling salesmen problem, bender's decomposition, and combination optimization which increases the impact of the methodology.

References

1. A. Krause and C. Guestrin, Beyond Convexity: Submodularity in Machine Learning, Tutorial at ICML-2008
2. Benders, J. F. (Sept. 1962), "Partitioning procedures for solving mixed-variables programming problems", Numerische Mathematik 4(3): 238–252.
3. Karamanov, Miroslav. “Branch and Cut: An Empirical Study.” Carnegie Mellon University , Sept. 2006, https://www.cmu.edu/tepper/programs/phd/program/assets/dissertations/2006-operations-research-karamanov-dissertation.pdf.
4. Luedtke, Jim. “The Branch-and-Cut Algorithm for Solving Mixed-Integer Optimization Problems.” Institute for Mathematicians and Its Applications, 10 Aug. 2016, https://www.ima.umn.edu/materials/2015-2016/ND8.1-12.16/25397/Luedtke-mip-bnc-forms.pdf.
5. Maltby, Henry, and Eli Ross. “Combinatorial Optimization.” Brilliant Math & Science Wiki, https://brilliant.org/wiki/combinatorial-optimization/.
6. Society for Industrial and Applied Mathematics. “SIAM Rev.” SIAM Review, 18 July 2006, https://epubs.siam.org/doi/10.1137/1033004.
7. S. Tschiatschek, R. Iyer, H. Wei and J. Bilmes, Learning Mixtures of Submodular Functions for Image Collection Summarization, NIPS-2014.