Branch and price

Short description: Mathematical combinatorial optimization method

In applied mathematics, branch and price is a method of combinatorial optimization for solving integer linear programming (ILP) and mixed integer linear programming (MILP) problems with many variables. The method is a hybrid of branch and bound and column generation methods.

## Contents

* 1 Description of the algorithm
* 2 Applications of branch and price
* 3 See also
* 4 External references
* 5 References

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

Outline of branch and price algorithm. Adapted from [1]

The algorithm typically begins by using a reformulation, such as Dantzig–Wolfe decomposition, 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.[2] 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. 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.[3] 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.[1]

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.[4]

If cutting planes are used to tighten LP relaxations within a branch and price algorithm, the method is known as branch price and cut.[5]

## 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.[3] This is a generalization of the graph coloring 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.[2]
* Generalized assignment problem.[6]

## See also

* Branch and cut
* Branch and bound
* Delayed column generation

## External references

* Lecture slides on branch and price
* Prototype code for a generic branch and price algorithm
* BranchAndCut.org FAQ
* SCIP 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

1. ↑ 1.0 1.1 Akella, M.; S. Gupta. "Branch and Price: Column Generation for Solving Huge Integer Programs". http://www.acsu.buffalo.edu/~nagi/courses/684/price.pdf.
2. ↑ 2.0 2.1 Feillet, Dominique (2010). "A tutorial on column generation and branch-and-price for vehicle routing problems". 4OR 8 (4): 407–424. doi:10.1007/s10288-010-0130-z.
3. ↑ 3.0 3.1 Mehrota, Anuj; M.A. Trick (2007). "A Branch-And-Price Approach for Graph Multi-Coloring". Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies. Operations Research/Computer Science Interfaces Series. 37. pp. 15–29. doi:10.1007/978-0-387-48793-9_2. ISBN 978-0-387-48790-8. https://archive.org/details/extendinghorizon0000info/page/15.
4. ↑ Gamrath, G.. "Generic Branch-Cut-and-Price". http://www.zib.de/gamrath/publications/gamrath2010_genericBCP.pdf.
5. ↑ Desrosiers, J.; M.E. Lubbecke (2010). "Branch-Price-and-Cut Algorithms". Wiley Encyclopedia of Operations Research and Management Science.
6. ↑ Savelsbergh, M. (1997). "A branch-and-price algorithm for the generalized assignment problem". Operations Research. 831-841 45 (6): 831–841. doi:10.1287/opre.45.6.831.

* Barnhart, Cynthia; Johnson, Ellis L. (1998), "Branch-and-price: column generation for solving huge integer programs", Operations Research 46 (3): 316–329, doi:10.1287/opre.46.3.316

* v
* t
* e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

| … functions|

* Golden-section search
* Interpolation methods
* Line search
* Nelder–Mead method
* Successive parabolic interpolation

|

… and gradients|

| Convergence|

* Trust region
* Wolfe conditions

|

Quasi–Newton|

* Berndt–Hall–Hall–Hausman
* Broyden–Fletcher–Goldfarb–Shanno and L-BFGS
* Davidon–Fletcher–Powell
* Symmetric rank-one (SR1)

Other methods|

* Gauss–Newton
* Gradient
* Levenberg–Marquardt
* Conjugate gradient
* Truncated Newton

… and Hessians|

* Newton's method

Constrained nonlinear

| General|

* Barrier methods
* Penalty methods

|

Differentiable|

* Augmented Lagrangian methods
* Sequential quadratic programming
* Successive linear programming

Convex optimization

| Convex
minimization|

* Cutting-plane method
* Reduced gradient (Frank–Wolfe)
* Subgradient method

|

Linear and
quadratic|

| Interior point|

* Affine scaling
* Ellipsoid algorithm of Khachiyan
* Projective algorithm of Karmarkar

|

Basis-exchange|

* Simplex algorithm of Dantzig
* Revised simplex algorithm
* Criss-cross algorithm
* Principal pivoting algorithm of Lemke

Combinatorial

| Paradigms|

* Approximation algorithm
* Dynamic programming
* Greedy algorithm
* Integer programming
* Branch and bound/cut

|

Graph
algorithms|

| Minimum
spanning tree|

* Borůvka
* Prim
* Kruskal

|

* Bellman–Ford
* Dijkstra
* Floyd–Warshall

Network flows|

* Dinic
* Edmonds–Karp
* Ford–Fulkerson
* Push–relabel maximum flow

Metaheuristics

* Evolutionary algorithm
* Hill climbing
* Local search
* Simulated annealing
* Tabu search

* Software

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Branch and price. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Branch_and_price&oldid=3372565"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template