EURO Bulletin Board - Webinars
EURO OSS on Operational Research and Machine Learning. January 13, 2025, 16.30 – 17.30 (CET). Prof Andrea Lodi. The differentiable Feasibility Pump.
EURO – The Association of European Operational Research Societies - the EURO Online Seminar Series (EURO OSS).
Links to participate are typically sent Monday morning.
The EURO OSS on Operational Research and Machine Learning is an online seminar series with the goal to brand the role of Operational Research in Artificial Intelligence. The format is a weekly session that takes place every Monday, 16.30-17.30 (CET). It is 100% online-access, and it will have leading speakers from Operational Research, as well as neighbouring areas, that will cover important topics such as explainability, fairness, fraud, privacy, etc. We also have the YOUNG EURO OSS on Operational Research and Machine Learning. In each YOUNG session, three junior academics will show their latest results in this burgeoning area. The Online Seminar Series is free thanks to the support given by EURO, as well as Universidad de Sevilla (US) and Copenhagen Business School (CBS). This is gratefully acknowledged.
Season II
January 13, 2025, 16.30 – 17.30 (CET)
The differentiable Feasibility Pump
To receive the link to attend the seminar, please register to the mailinglist here.
Speaker: Prof Andrea Lodi
Andrew H. and Ann R. Tisch Professor
Jacobs Technion-Cornell Institute
Cornell University
USA
Abstract:
Although nearly 20 years have passed since its conception, the feasibility pump algorithm remains a widely used heuristic to find feasible primal solutions to mixed-integer linear problems. Many extensions of the initial algorithm have been proposed. Yet, its core algorithm remains centered around two key steps: solving the linear relaxation of the original problem to obtain a solution that respects the constraints, and rounding it to obtain an integer solution. This paper shows that the traditional feasibility pump and many of its follow-ups can be seen as gradient-descent algorithms with specific parameters. A central aspect of this reinterpretation is observing that the traditional algorithm differentiates the solution of the linear relaxation with respect to its cost. This reinterpretation opens many opportunities for improving the performance of the original algorithm. We study how to modify the gradient-update step as well as extending its loss function. We perform extensive experiments on MIPLIB instances and show that these modifications can substantially reduce the number of iterations needed to find a solution. (Joint work with M. Cacciola, A. Forel, A. Frangioni).
Posted on 2024-12-16 by Sarah Fores