September 27
@
12:00 PM
–
1:00 PM
Professor Andrea Lodi
We consider range minimization problems featuring exponentially many variables, as frequently arising in fairness-oriented or bi-objective optimization. While branch and price is successful at solving cost-oriented problems with many variables, the performance of classical branch-and-price algorithms for range minimization is drastically impaired by weak linear programming relaxations. We propose range branching, a generic branching rule that directly tackles this issue and can be used on top of problem-specific branching schemes. We show several desirable properties of range branching and show its effectiveness on a series of instances of the fair capacitated vehicle routing problem and fair generalized assignment problem. Range branching significantly improves multiple classical branching schemes in terms of computing time, optimality gap, and size of the branch-and-bound tree, allowing us to solve many more large instances than classical methods. Moreover, we show how range branching can be successfully generalized to order-based objective functions, such as the Gini deviation.
Bio: Andrea Lodi is an Andrew H. and Ann R. Tisch Professor at the Jacobs Technion-Cornell Institute at Cornell Tech and the Technion. He is a member of the Operations Research and Information Engineering field at Cornell University. Before joining Cornell, he was a Herman Goldstine Fellow at the IBM Mathematical Sciences Department, NY in 2005–2006, full professor of Operations Research at DEI, University of Bologna 2007-2015 and Canada Excellence Research Chair in “Data Science for Real-time Decision Making” at Polytechnique Montréal 2015-2022. His main research interests are in Mixed-Integer Linear and Nonlinear Programming and Data Science and his work has received several recognitions including the IBM and Google faculty awards. Andrea is the recipient of the INFORMS Optimization Society 2021 Farkas Prize and has been elected an INFORMS Fellow in 2023. Andrea has been the principal investigator of scientific projects (often involving industrial partners) for Italy, European Union, Canada and USA. In the period 2006-2021, he was a consultant of the IBM CPLEX research and development team, developing CPLEX, one of the leading software for Mixed-Integer Optimization.