Branch and cut is a method of
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...
for solving
integer linear program
An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objectiv ...
s (ILPs), that is,
linear programming
Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...
(LP) problems where some or all the unknowns are restricted to
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
values. Branch and cut involves running a
branch and bound
Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate soluti ...
algorithm and using
cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called branch and cut.
Algorithm
This description assumes the ILP is a maximization problem.
The method solves the
linear program without the integer constraint using the regular
simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...
. When an optimal solution is obtained, and this solution has a non-integer value for a variable that is supposed to be integer, a
cutting plane algorithm may be used to find further linear constraints which are satisfied by all
feasible integer points but violated by the current fractional solution. These inequalities may be added to the linear program, such that resolving it will yield a different solution which is hopefully "less fractional".
At this point, the
branch and bound
Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate soluti ...
part of the algorithm is started. The problem is split into multiple (usually two) versions. The new linear programs are then solved using the simplex method and the process repeats. During the branch and bound process, non-integral solutions to LP relaxations serve as upper bounds and integral solutions serve as lower bounds. A node can be
pruned if an upper bound is lower than an existing lower bound. Further, when solving the LP relaxations, additional cutting planes may be generated, which may be either ''global cuts'', i.e., valid for all feasible integer solutions, or ''local cuts'', meaning that they are satisfied by all solutions fulfilling the side constraints from the currently considered branch and bound subtree.
The algorithm is summarized below.
#Add the initial ILP to
, the list of active problems
#Set
and
#
''while'' is not empty
##Select and remove (de-queue) a problem from
##Solve the LP relaxation of the problem.
##If the solution is infeasible, go back to 3 (while). Otherwise denote the solution by
with objective value
.
##If
, go back to 3.
##If
is integer, set
and go back to 3.
##If desired, search for cutting planes that are violated by
. If any are found, add them to the LP relaxation and return to 3.2.
##Branch to partition the problem into new problems with restricted feasible regions. Add these problem to
and go back to 3
#return
Pseudocode
In
C++
C++ (pronounced "C plus plus") is a high-level general-purpose programming language created by Danish computer scientist Bjarne Stroustrup as an extension of the C programming language, or "C with Classes". The language has expanded significan ...
-like
pseudocode
In computer science, pseudocode is a plain language description of the steps in an algorithm or another system. Pseudocode often uses structural conventions of a normal programming language, but is intended for human reading rather than machine re ...
, this could be written:
// ILP branch and cut solution pseudocode, assuming objective is to be maximized
ILP_solution branch_and_cut_ILP(IntegerLinearProgram initial_problem)
In the above pseudocode, the functions
LP_relax
,
LP_solve
and
branch_partition
called as subroutines must be provided as applicable to the problem. For example,
LP_solve
could call the
simplex algorithm
In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming.
The name of the algorithm is derived from the concept of a simplex and was suggested by T. S. Motzkin. Simplices are n ...
. Branching strategies for
branch_partition
are discussed below.
Branching strategies
An important step in the branch and cut algorithm is the branching step. At this step, there are a variety of branching heuristics that can be used. The branching strategies described below all involve what is called branching on a variable.
Branching on a variable involves choosing a variable,
, with a fractional value,
, in the optimal solution to the current LP relaxation and then adding the constraints
and
; Most infeasible branching: This branching strategy chooses the variable with the fractional part closest to 0.5.
; Pseudo cost branching: The basic idea of this strategy is to keep track for each variable
the change in the objective function when this variable was previously chosen as the variable to branch on. The strategy then chooses the variable that is predicted to have the most change on the objective function based on past changes when it was chosen as the branching variable. Note that pseudo cost branching is initially uninformative in the search since few variables have been branched on.
; Strong branching: Strong branching involves testing which of the candidate variable gives the best improvement to the objective function before actually branching on them. Full strong branching tests all candidate variables and can be computationally expensive. The computational cost can be reduced by only considering a subset of the candidate variables and not solving each of the corresponding LP relaxations to completion.
There are also a large number of variations of these branching strategies, such as using strong branching early on when pseudo cost branching is relatively uninformative and then switching to pseudo cost branching later when there is enough branching history for pseudo cost to be informative.
References
External links
Mixed Integer ProgrammingSCIP framework for branch-cut-and-price and a mixed integer programming solver
ABACUS – A Branch-And-CUt System– open source software
COIN-OR Cbc– open source software on
GitHub
GitHub, Inc. () is an Internet hosting service for software development and version control using Git. It provides the distributed version control of Git plus access control, bug tracking, software feature requests, task management, continuous ...
{{Optimization algorithms, combinatorial, state=expanded
Combinatorial optimization
Optimization algorithms and methods