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

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.