Skip to main navigationSkip to main content
The University of Southampton
Southampton SIAM Student Chapter

A beginner's approach to branch-and-price methods Seminar

15:00 - 16:00
30 May 2018
The Ketley Room (B54 / lvl 4)

For more information regarding this seminar, please email Marton Benedek at .

Event details

Branch-and-price (B&P) methods are very popular for solving Mixed-Integer Linear Programming (MILP) problems with many variables. The most common version of the B&P algorithm starts with a reformulation of the original MILP by applying the Dantzig-Wolfe decomposition, thus generating a master problem and a subproblem (a.k.a. pricing problem). The master problem can then be solved by the Column Generation (CG) technique. A B&P algorithm consists of combining branch-and-bound and CG. In this talk, we shall introduce the basic concepts behind B&P methods from a practical point of view. In other words, we will look through an implementation of a B&P algorithm for solving the Bin Packing Problem (BPP). The BPP, in my opinion, presents a perfect combination of simplicity and complexity for a first contact with CG and B&P.

Speaker information

Walton Pereira Coutinho,, University of Southampton. Postgraduate Research Student of Joerg Fliege

Privacy Settings