Tutte seminar - Ricardo Fukasawa

Branch-and-cut-and-price approaches to some combinatorial optimization problems

Abstract:

Dynamic column and cut generation are very important tools in integer programming. However, their simultaneous use within a branch-and-bound approach (what is called branch-and-cut-and-price) is challenging. We show recent progress in overcoming those challenges and illustrate the usefulness of such approach in solving hard combinatorial optimization problems like the vehicle routing problem. In fact, for several combinatorial optimization problems, branch-and-cut-and-price approaches have been the ones with most practical success in solving benchmark instances to optimality.