MILP Insights and Algorithms

John W. Chinneck

Event Location: 

Mohler Lab, Room 453

Over the last several years I have developed a variety of algorithms for faster solution of mixed-integer linear programs, based on a number of insights about branch and bound methods. The seminar will review the insights, the resulting algorithms, and their experimental validation. Topics will include (i) active constraint branching, (ii) branching to force change, (iii) node selection rules based on common patterns seen in MILP solutions, and (iv) general disjunctions.

Bio Sketch: 

John W. Chinneck is a professor in the Department of Systems and Computer Engineering at Carleton University in Ottawa, Canada. His degrees are from the University of Waterloo in Systems Design Engineering (BASc 1977, MASc 1978, PhD 1983).
He conducts research in applied optimization, covering three main topics: (i) improved algorithms for solving various difficult classes of optimization problems, (ii) algorithms for analyzing modelling problems, such as infeasibility, and (iii) applications, e.g. in cloud computing and telecommunications. His algorithms for the analysis of infeasible linear programs are incorporated in many commercial linear programming solvers, including LINDO, CPLEX, Gurobi, XPRESS-MP, Frontline Systems Excel solvers, and IBM's OSL. Various MILP algorithms also appear in some of those solvers as well as SCIP.

He is a member of the advisory board and former Editor-in-Chief (2007-2012) of the INFORMS Journal on Computing, a member of the editorial board for the journal Constraints, and a past member of the editorial board for Computational Management Science. He is a past Chair (2005-2007) of the INFORMS Computing Society.

Professor Chinneck was awarded a Carleton University Scholarly Achievement Award in 1988, a Carleton University Research Achievement Award in 1995, an IBM Faculty Award in 2006, and an NSERC Discovery Accelerator Supplement in 2014. He has held various administrative positions at Carleton University over the years including Associate Dean (Research) for the Faculty of Engineering and Design, Chair and Associate Chair of the Department of Systems and Computer Engineering, and Associate Dean (Planning) for the Faculty of Graduate and Postdoctoral Affairs. He has also served on the Senate and the Board of Governors.