Bio:  Andrea Lodi received a PhD in System Engineering from the University of Bologna in 2000 and he was a Herman Goldstine Fellow at the IBM Mathematical Sciences Department, NY from 2005–2006. He was a full professor of Operations Research at DEI, University of Bologna between 2007 and 2015. Since 2015 he has been the Canada Excellence Research Chair in “Data Science for Real-time Decision Making” at the Polytechnique Montréal. His main research interests are in Mixed-Integer Linear and Nonlinear Programming and Data Science and his work has received recognition including the IBM and Google faculty awards. He is author of more than 80 publications in the top journals of the field of Mathematical Optimization. He serves as Associate Editor for several prestigious journals in the area. He has been the network coordinator and principal investigator of two large EU projects/networks, and, since 2006, consultant of the IBM CPLEX research and development team. Finally, Andrea Lodi is the co-principal investigator (with Yoshua Bengio) of the project “Data Serving Canadians: Deep Learning and Optimization for the Knowledge Revolution”, recently funded by the Canadian Federal Government under the Apogée Programme.

On Wide Split Cuts for Mixed-Integer Programming

Cutting planes (or simply cuts) are a fundamental component of modern Mixed-Integer Linear Programming (MILP) solvers because they help in strengthening the linear programming relaxation, a proxy to make the branchand-bound tree small. A classical way of devising cuts is to exploit disjunctions, for example in the domain of an integer variable, where, of course, no fractional value leads to any feasible solution. Cutting planes of this type, called split cuts, classically exploit disjunctions whose ‘width’ is always equal to one, i.e., no fractional value is feasible between two consecutive integer values. We investigate cutting planes that arise when widening the associated disjunctions. This allows, e.g., to model non contiguous domains of (integer) variables (or, stated differently, ‘holes’ in the domains). The validity of the disjunctions in a MILP can come from either primal or dual information, and we present examples and computational results in both cases. We further explore an exact MILP approach based on these cutting planes, that in addition tackles non-contiguity directly via branching and as a side-effect reduces the model size. (Joint work with P. Bonami, F. Serrano, A. Tramontani, S. Wiese.)

This seminar is co-sponsored by the U-M Department of Industrial & Operations Engineering