Dagstuhl Seminar 24441
Machine Learning Augmented Algorithms for Combinatorial Optimization Problems
( Oct 27 – Oct 31, 2024 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/24441
Organizers
- Deepak Ajwani (University College Dublin, IE)
- Bistra Dilkina (USC - Los Angeles, US)
- Tias Guns (KU Leuven, BE)
- Ulrich Carsten Meyer (Goethe University - Frankfurt am Main, DE)
Contact
- Michael Gerke (for scientific matters)
- Susanne Bach-Bernhard (for administrative matters)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
- UCD CS academics invited to organise prestigious Dagstuhl seminars - University College Dublin School of Computer Science News, March 28, 2024
Combinatorial optimization problems are pervasive across critical domains, driving decades of research across diverse fields, including exact and approximation algorithms, algorithm engineering, operations research, and optimization solvers (such as mixed-integer linear programming and constraint programming solvers). In recent years, there has been a surge in research at the intersection between machine learning, optimization solvers, and algorithm engineering. While significant progress has been made, research efforts in this area remain fragmented across several distinct communities:
- “Learning to scale optimization solvers”: This community focuses on leveraging learning techniques to improve the performance of solvers, such as mixed-integer linear programming, constraint programming, and satisfiability solvers, often using generic, problem-agnostic features. This includes optimizing solver components and exploring “end-to-end” approaches that replace traditional solvers entirely.
- “Algorithm Engineering”: This community utilizes learning techniques to select the most effective components within algorithms, fill in the underspecified parts of the algorithms, and develop novel heuristics, often leveraging problem-specific features and algorithmic insights.
- “Algorithms with predictions”: This community develops algorithms that leverage predictions to improve performance, often treating the prediction system as a black box. These algorithms aim for good performance with accurate predictions while maintaining bounded worst-case performance with inaccurate predictions.
- “Decision-focused learning”: This research area focuses on systems where optimization decisions are made based on machine learning models, necessitating an integrated approach to avoid suboptimal solutions.
This seminar brought together researchers from these diverse communities, fostering a dialogue on effectively combining algorithm engineering techniques, optimization solvers, and machine learning. The seminar facilitated the development of a shared vocabulary, clarifying similarities and distinctions between concepts across different research areas. Notably, many concepts with different names (e.g., “learning to prune,” “predict then search”, “finding kernel”, “finding a backbone”, “learning to branch”, “learning constraints”) were found to represent similar ideas. Key differences often stem from the source of features, with “learning to prune” typically relying on problem-specific, algorithm-based features, while “learning to branch” often utilizes problem-agnostic features derived from the solver run. This shared understanding fostered significant synergy and cross-fertilization across research areas.
The seminar featured discussions on recent advancements, at the intersection of machine learning, algorithm engineering, and combinatorial optimization. For instance, the tutorial on “ML-Guided Solvers for MIP” focused on recent advances in using contrastive learning for MILP solvers, the talk on “Neural Combinatorial Optimization – One Model to Solve Them All?” described recent advances in foundation models for sequencing combinatorial optimization and the talk on “Graph Learning for Planning” described very impressive results on the usage of learning techniques for planning problems. In addition, many participant talks such as “Progress and Open Questions on DFL and Constrained NNs” and “Machine Learning for Edge Contractions in Multilevel Graph Partitinioning” highlighted interesting open problems in the area.
Furthermore, the seminar identified key research directions, including:
- Theoretical frameworks for machine learning augmented combinatorial optimization algorithms
- Learning to fill the underspecified parts of the algorithms
- Reinforcement learning for combinatorial optimization
- Contextual Stochastic Optimization and DFL
- Fast and/or interpretable machine learning techniques for combinatorial problems
- Scalability and Datasets for Decision Focused Learning
- Finding worst-case instances for algorithms using machine learning techniques
These directions are expected to serve as a valuable roadmap for advancing this exciting research area.
Seminar Overview
The seminar commenced with a vibrant round of introductions, allowing participants to share their research interests and backgrounds. The slides for this round of introductions were collected in advance. To foster interdisciplinary connections, participant order was randomized, encouraging interaction across the diverse research communities represented.
Following this, four insightful tutorials were presented, each from a different research community. These tutorials served to familiarize all participants with the unique vocabulary, key techniques, and recent advancements within each area, providing a common ground for subsequent discussions.
A series of engaging participant talks followed, showcasing cutting-edge research from across the field. The talk schedule was carefully randomized to maximize interaction and foster cross-pollination of ideas among the diverse research communities. This dynamic approach encouraged participants to step outside their immediate research areas and engage with novel perspectives.
Recognizing the importance of collective vision, participants were invited to submit key research directions and open challenges within the field. These valuable contributions were then clustered, enabling the identification of key research themes and areas of significant opportunity.
To delve deeper into these themes, three parallel discussion sessions were held. Each session featured three distinct discussion groups, allowing participants to select the group most aligned with their interests. This dynamic group composition, which changed daily, encouraged participants to engage with a variety of perspectives and fostered a truly inter-community exchange of ideas. It was particularly encouraging to observe that many discussion groups comprised members from all four research communities, demonstrating the successful integration of diverse perspectives throughout the seminar.
Creative Commons BY 4.0
Deepak Ajwani, Bistra Dilkina, Tias Guns, and Ulrich Carsten Meyer
Combinatorial optimisation problems arise naturally in a multitude of crucial applications, ranging from business analytics, engineering, supply-chain optimisation, transportation, bioinformatics etc. In recent years, motivated by the success of machine learning in diverse fields, researchers have explored if learning techniques can be used to efficiently solve combinatorial optimisation problems. This is challenging because these problems have highly correlated decision variables and the correlations are long-range with very little spatial or temporal coherence. As a result, the end-to-end learning systems that take the problem instance as an input and produce the optimal solution as an output often do not generalise well to instances of larger sizes and from a different input distribution. Experts in this area have advocated for using machine learning in combination with current combinatorial optimisation algorithms to benefit from the theoretical guarantees and state-of-the-art algorithms already available.
The discussion in this Dagstuhl Seminar will focus on how best to combine the machine learning techniques with algorithmic insights and optimisation solvers to solve larger and harder instances of combinatorial optimisation problems arising from real-world applications. These discussions are expected to accelerate the pace of research in this area and build collaborations and synergies between the researchers working in the areas of algorithm design and engineering, combinatorial optimisation, and machine learning.
The seminar will provide a forum to discuss topics at the intersection of combinatorial optimisation, algorithm engineering, and machine learning:
- Learning-augmented algorithms and data structures
- Going beyond worst-case analysis using algorithms with predictions
- Machine learning augmented optimisation solvers
- Smart predict + optimise systems for applications where optimisation decisions are taken on data that is predicted using machine learning techniques
- Integrating algorithmic insights into machine learning techniques for solving optimisation problems.
Deepak Ajwani, Bistra Dilkina, Tias Guns, and Ulrich Carsten Meyer
Please log in to DOOR to see more details.
- Deepak Ajwani (University College Dublin, IE) [dblp]
- Brandon Amos (Meta - New York, US) [dblp]
- Senne Berden (KU Leuven, BE)
- Quentin Cappart (Polytechnique Montréal, CA) [dblp]
- Eanna Curran (University College Dublin, IE)
- Marianne Defresne (KU Leuven, BE)
- Michelangelo Diligenti (University of Siena, IT) [dblp]
- Bistra Dilkina (USC - Los Angeles, US) [dblp]
- Adam Elmachtoub (Columbia University - New York, US) [dblp]
- Aaron Ferber (Cornell University - Ithaca, US) [dblp]
- Alexandre Forel (Polytechnique Montréal, CA)
- Emma Frejinger (University of Montreal, CA) [dblp]
- Paul Grigas (University of California - Berkeley, US) [dblp]
- Ernestine Großmann (Universität Heidelberg, DE) [dblp]
- Tias Guns (KU Leuven, BE) [dblp]
- Mikhail Khodak (Princeton University, US) [dblp]
- Sandra Kiefer (University of Oxford, GB) [dblp]
- Alexander Lindermayr (Universität Bremen, DE) [dblp]
- Michele Lombardi (University of Bologna, IT) [dblp]
- Nikolai Maas (KIT - Karlsruher Institut für Technologie, DE)
- Irfan Mahmutogullari (KU Leuven, BE) [dblp]
- Fredrik Manne (University of Bergen, NO) [dblp]
- Johannes Meintrup (THM - Gießen, DE) [dblp]
- Ulrich Carsten Meyer (Goethe University - Frankfurt am Main, DE) [dblp]
- Sofia Michel (NAVER Labs Europe - Meylan, FR) [dblp]
- Nysret Musliu (TU Wien, AT) [dblp]
- Mathias Niepert (Universität Stuttgart, DE) [dblp]
- Siegfried Nijssen (UC Louvain, BE & KU Leuven, BE) [dblp]
- Ryan O Connor (University College Dublin, IE)
- Manuel Penschuck (Goethe University - Frankfurt am Main, DE) [dblp]
- Adam Polak (Bocconi University - Milan, IT) [dblp]
- María Dolores Romero Morales (Copenhagen Business School, DK) [dblp]
- Louis-Martin Rousseau (Polytechnique Montréal, CA) [dblp]
- Jens Schlöter (CWI - Amsterdam, NL)
- Christian Schulz (Universität Heidelberg, DE) [dblp]
- Darren Strash (Hamilton College - Clinton, US) [dblp]
- Edward Tansley (University of Oxford, GB)
- Sylvie Thiébaux (University of Toulouse, FR & Australian National University, Canberra, AU) [dblp]
- Ali Vakilian (TTIC - Chicago, US) [dblp]
- Jacobus G. M. van der Linden (TU Delft, NL)
- Maurice Wenig (Friedrich-Schiller-Universität Jena, DE)
- Neil Yorke-Smith (TU Delft, NL) [dblp]
Classification
- Data Structures and Algorithms
- Discrete Mathematics
- Machine Learning
Keywords
- Combinatorial Optimisation
- Algorithm Engineering
- Machine Learning
- Constraint Solvers
