applied mathematics Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathematical s ...

, branch and price 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 programming 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 objective ...

(ILP) and mixed integer linear programming (MILP) problems with many variables. The method is a hybrid of

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

and

column generation Column generation or delayed column generation is an efficient algorithm for solving large linear programs. The overarching idea is that many linear programs are too large to consider all the variables explicitly. The idea is thus to start by solv ...

methods.

Description of the algorithm

Branch and price is a branch and bound method in which at each node of the search tree, columns may be added to the

linear programming relaxation In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form :x_i\in\. The relax ...

(LP relaxation). At the start of the algorithm, sets of columns are excluded from the LP relaxation in order to reduce the computational and memory requirements and then columns are added back to the LP relaxation as needed. The approach is based on the observation that for large problems most columns will be nonbasic and have their corresponding variable equal to zero in any optimal solution. Thus, the large majority of the columns are irrelevant for solving the problem. branch and price diagram

The algorithm typically begins by using a reformulation, such as

Dantzig–Wolfe decomposition Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have s ...

, to form what is known as the Master Problem. The decomposition is performed to obtain a problem formulation that gives better bounds when the relaxation is solved than when the relaxation of the original formulation is solved. But, the decomposition usually contains many variables and so a modified version, called the Restricted Master Problem, that only considers a subset of the columns is solved. Then, to check for optimality, a subproblem called the pricing problem is solved to find columns that can enter the basis and reduce the objective function (for a minimization problem). This involves finding a column that has a negative

reduced cost In linear programming, reduced cost, or opportunity cost, is the amount by which an objective function coefficient would have to improve (so increase for maximization problem, decrease for minimization problem) before it would be possible for a c ...

. Note that the pricing problem itself may be difficult to solve but since it is not necessary to find the column with the most negative reduced cost, heuristic and local search methods can be used. The subproblem must only be solved to completion in order to prove that an optimal solution to the Restricted Master Problem is also an optimal solution to the Master Problem. Each time a column is found with negative reduced cost, it is added to the Restricted Master Problem and the relaxation is reoptimized. If no columns can enter the basis and the solution to the relaxation is not integer, then branching occurs. Most branch and price algorithms are problem specific since the problem must be formulated in such a way so that effective branching rules can be formulated and so that the pricing problem is relatively easy to solve. If cutting planes are used to tighten LP relaxations within a branch and price algorithm, the method is known as branch price and cut.

Applications of branch and price

The branch and price method can be used to solve problems in a variety of application areas, including: *Graph multi-coloring. This is a generalization of the

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

problem in which each node in a graph must be assigned a preset number of colors and any nodes that share an edge cannot have a color in common. The objective is then to find the minimum number of colors needed to have a valid coloring. The multi-coloring problem can be used to model a variety of applications including job scheduling and telecommunication channel assignment. * Vehicle routing problems. * Generalized assignment problem.

External references

Lecture slides on branch and pricePrototype code for a generic branch and price algorithmSCIP
an open source framework for branch-cut-and-price and a mixed integer programming solver
ABACUS – A Branch-And-CUt System
– open source software

References

* {{Optimization algorithms Combinatorial optimization Optimization algorithms and methods

Description of the algorithm

Applications of branch and price

See also

External references

References