Tutte seminar - Ricardo Fukasawa

Friday, November 26, 2010 3:30 pm - 4:30 pm EST (GMT -05:00)

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

Speaker: Ricardo Fukasawa
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

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.