116:20 — Recent developments in branch-price-and-cut algorithms

The success of optimization algorithms that are based on column generation can be attributed to four aspects: (1) an extensive formulation often has a stronger linear-relaxation bound compared to the original formulation (the extensive formulation is the one with a large number of variables derived by a Dantzig-Wolfe decomposition from an original model); (2) an extensive formulation can eliminate inherent symmetry; (3) column-generation subproblems can cope with non-linearities of the original formulation; and (4) powerful algorithms have been developed to solve subproblems for important real-world and theoretical problems. The talk discusses important developments in branch-price-and-cut algorithms, giving examples from applications in vehicle routing and scheduling, cutting and packing, and problems in networks.