Hybridizing Mixed Integer and Constraint Programming

J. Christopher Beck

Date and Time: 

Wednesday, November 6, 2013 - 4:00pm

Event Location: 

Mohler Lab # 453

Over the past 10 years there has been a growing body of work at the intersection of mathematical programming as commonly studied in Operations Research and constraint programming (CP) with its origins in Artificial Intelligence (AI) and programming languages. Much of CP's success in solving challenging combinatorial problems comes from the exploitation of inference as embodied in so-called global constraints. This talk provides a brief introduction to CP and then discusses two patterns of hybridization of mixed integer programming (MIP) and CP that have been proposed. I show how these patterns can be used to solve hard combinatorial problems and that they can also inform each other, leading to a more general view of hybridizations centred around the exploitation of problem structure embodied in global constraints. In particular, I propose that the further development of solving techniques associated with global constraints leads to novel research directions in both mathematical and constraint programming.

Bio Sketch: 

Chris Beck is an Associate Professor and Associate Chair, Research in the Department of Mechanical & Industrial Engineering, University of Toronto. Chris' MSc and PhD degrees both come from the Department of Computer Science, University of Toronto, in the area of Artificial Intelligence. Chris then spent three years at ILOG, Paris as a Senior Scientist and Software Engineer on the team responsible for their constraint-based scheduling library (ILOG Scheduler) before spending two years as a StaffScientist at the Cork Constraint Computation Centre. He returned to Toronto in 2004 to join the Department of Mechanical & Industrial Engineering. Chris' research interests include scheduling, constraint programming, AI planning, reasoning under uncertainty, queueing theory, mixed integer programming, and hybrid optimization techniques. Chris currently serves in an editorial capacity for four journals and one website in AI and OR. He is the President-Elect of the Executive Council for the International Conference on Automated Planning and Scheduling.