- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
In the last five years, an area now being influenced in a new way by machine learning (ML) is combinatorial optimisation (CO). Combinatorial optimisation is studied for both its importance in theory, since CO problems are NP-hard problems, and for its importance in real-world decisions, for example, planning drivers and routes for a fleet of delivery vehicles. CO problems are studied in operations research (OR) and also traditionally in symbolic artificial intelligence (AI) such as constraint programming (CP) and satisfiability modulo theories.
This Dagstuhl Seminar built on the fast-growing interest in combining ML with ‘traditional’ AI methodologies like CP, and with OR more generally [1, 2]. Surveying the scattered initiatives, the seminar had the ambition to set the agenda for constraint-based ‘Combinatorial Optimisation 2.0’. Historically, several communities have focussed on different approaches to CO, mostly in a disjoint manner. This division between, on the one hand, the OR and symbolic AI communities, and on the other, the ML and functional AI communities, is historically strong. While in recent years a dialogue between symbolic and functional AI communities has emerged, there remains too little connection between the discrete OR and ML communities.
The seminar was organised by Emma Frejinger (Canada), Andrea Lodi (USA), Michele Lombardi (Italy) and Neil Yorke-Smith (Netherlands). Michele was unable to attend in person, due to last minute circumstances, and joined plenary parts of the seminar online. Similarly, it was necessary for Pierre-Luc Bacon to give his tutorial remotely.
The seminar opened with four tutorials, whose abstracts are given in this report, on the topics of CP (by Tias Guns), mixed (non)-linear integer programming (MIP) (by Ruth Misener), end-to-end ML for CO (by Ferdinando Fioretto), and reinforcement learning (RL) (by Pierre-Luc Bacon).
The seminar included a set of informal short introductory and topical talks, and sessions of collaborative planning. The overarching questions that structured this planning are, on the one hand, (1) how ML can help in modelling or solving CO problems – or both modelling and solving – and in particular constraint-based models and solving; and on the other hand, (2) how CO can help in tasks approached using ML, including ML training and algorithms. Then, (3) what problems and tasks can be addressed (only) by the synergistic combinations of these methodologies?
Through discussions, the participants identified jointly six topics to be approached in smaller working groups: (i) self-supervised representation learning for combinatorial optimisation, (ii) uncertainty, prediction, optimisation and decision-focussed learning, (iii) OR for ML, (iv) vehicle routing and the role of ML, (v) ML-augmented MIP solvers, and (vi) fairness. The groups discussed challenges, existing work and identified open research questions with promising future avenues at the intersection between OR and ML. The working groups are summarised below.
The outcomes of the seminar in furthering the development of a community at the intersection of OR and ML are expected to be felt in the coming couple of years. Already, however, there are tangible outcomes in terms of roadmap ideas, an open online discussion forum (Slack)1, multiple new collaborations, and a research grant submitted. A special issue of the journal Frontiers in Applied Mathematics and Statistics is organised by one of the participants.
The scientific programme was beautifully facilitated by the surroundings and academic services of Schloss Dagstuhl. Further, on the opening evening of the seminar, volunteers among the participants took part in “slide bingo”. During this humorous session they improvised presenting the slides of others. On Wednesday afternoon, the participants took a walk to a nearby village in unexpectedly fine sunny weather for October.
Reflections on the Week
All communities present at the seminar found benefit from the interactions and discussions. Meeting in person at the scale of a Dagstuhl Seminar was much appreciated! Participants were aware of the differing emphases, mindsets, and publication practices of different communities. In general, it was felt that strengthening the connection between ML and OR helps in bridging the gap between predictive and prescriptive analytics, which can benefit industrial or government actors and citizens alike.
In this section, we briefly summarise the discussions in the six working groups.
Self-supervised representation learning for combinatorial optimisation
This working group enjoyed lively discussions around the concept of a "foundational model" for CO. The motivation is to avoid retraining from scratch when there is a relatively small change. The group discussed transfer learning in terms of problem formulation, downstream task and instance distributions.
The group identified open questions:
- What is the equivalent of saving models/checkpoints in ML or natural language processing (NLP) in data-driven CO (DDCO)?
- Can we share pre-trained models to generate SAT/CP/MIP embeddings without training again?
- NLP has the concept of a tokeniser that preprocesses the text before it gets fed into the network; in DDCO we would need similar pre processors that transfer the problem instances into the model’s expected (graph) structure.
- What is the equivalent of “large” aspect from large language NLP models for DDCO? Is there a (super) GLUE benchmark equivalent for DDCO?
Uncertainty, prediction, optimisation and decision-focussed learning
Decision-focussed learning aims at training prediction models against a loss reflecting the quality of decisions instead of a classic prediction loss. This working group weighed up the questions: when is decision-focussed learning (DFL) better than (traditional) alternatives? The group gave energy into thinking about stochastic formulations, data perturbation and interpretability of DFL. The group also identified a connection with RL, in particular contextual bandits (single-stage decision). Since there has been some confusion around the terminology, the group recommended to use "decision-focussed learning" instead of "predict and optimise" or "predict + optimise".
The group wrote down example problems for three settings of decision focussed learning for CO. First, unknown parameters in the objective. This is the most studied case and there are several applications in the literature. Second, unknown parameters in the right-hand side of the constraints. For example, transport network planning where demand predictions occur in capacity constraints. Third, unknown parameters in the left-hand side of the constraints. For example, healthcare scheduling problems where treatment durations are predicted and should not exceed a given schedule length.
Operations research for machine learning
This working group was provoked by the feeling in the OR community that the ML community is seldom happy with discrete optimisation. In other words, how can CO have an influence on problems that generally come from the ML community? Those from OR background in the group expressed that they want to make real contributions to ML.
The group proceeded to outline three major obstacles:
- Scalability. OR methods tend to be limited when dealing with extremely large datasets that are often associated with ML applications.
- Optimality. OR methods have been designed in general to provide guarantees. Computing confidence bounds for ML applications would be excellent but one major obstacle is that the loss function is computed over samples from an unknown distribution. In other words, there is uncertainty with respect to the real objective function, which would require a re-interpretation of what confidence bounds are.
- Software. Whereas the ML community is used to working with self-installing open-source software, the OR community uses more cumbersome, often commercial software.
The recommendation was for research into a new generation of optimisation-based heuristics. The group identified four areas in which discrete optimisation methods are likely relevant: (i) optimal transport problems, (ii) neural-network verification, (iii) the broad area of fairness, explainability and interpretability, and (iv) training for Gaussian processes with tree kernels.
Vehicle routing and the role of machine learning
This working group ascertained exciting research on using ML to help solve routing problems. Two main aspects are, first, that the current state of (deployed) routing software has no idea whether it has seen a problem before, the types of problems being solved, and so forth; and second, anticipating the future -- for instance dynamic settings, demand estimation, service time estimation, and so forth -- would make the solution of routing problems even more relevant in practice. The working group felt that leveraging ML in both aspects could lead to significant improvements.
The group identified open questions:
- Does the ML model output individual actions or does it output an instance-specific heuristic?
- Can we learn insights about the problem from the predictions?
- Where does or could deep RL work best?
- Can we make a unified routing model (a `foundation model')?
Machine learning augmented MIP solvers
ML-augmented MIP solvers be ever significantly better than improved versions of the current solvers?
The group found that one significant motivation to go for ML-augmented MIP is `democratisation': ML could allow the more general use of MIP technology by automatising some steps of MIP development and solution that depend on the specific a class of problems in hand without requiring the intervention of experts in the loop. Such a democratisation would require the definition of a robust pipeline on how to learn - from data - tasks like branching, cutting, preprocessing, etc. on the specific class of instances in hand, i.e., characteristic of the application one wants to solve. Such a robust pipeline does not exist yet though there is strong evidence of successful stories where ML-augmented tasks are performed more efficiently than in classical MIP solvers. Some of those successful examples have been already integrated into the solvers, even commercial ones.
The group identified a number of interesting directions, as yet unexplored in the fast-moving subfield of ML-for-MIP. Among these are hypothesis generation, defining appropriate performance metrics, learning for cutting plane generation and selection. The group also discussed benchmark libraries.
This working group sought to learn more about data-driven CO models for fairness. The group recognised that an issue with fairness is already in its definition. While in the ML community, the concept of fairness is related to a tradeoff between overall accuracy and group accuracy, in CO for decision making, there is not a clear definition of fairness.
The group discussed an application in the online scheduling of radiologists and neuro-radiologists of CT scans. In this context, because of the scarcity of the resources, fairness is associated with their correct and "fair" use.
Fairness at large is also related to explainability and interpretability and the working group discussed the use of classical CO methods that tend to be more interpretable of the ML ones that are often perceived as black-boxes. Further, a potential important area in this context is that of integrating ML and OR to achieve a higher level of explainability, for example by improving methods like decision trees and ML classification algorithms.
- Yoshua Bengio, Andrea Lodi, Antoine Prouvost: Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2): 405-421 (2021). https://doi.org/10.1016/j.ejor.2020.07.063
- James Kotary, Ferdinando Fioretto, Pascal Van Hentenryck, Bryan Wilder: Endto- End Constrained Optimization Learning: A Survey. IJCAI 2021: 4475-4482. https:// doi.org/10.24963/ijcai.2021/610
In less than a decade, public attention has become captivated by artificial intelligence in the form of deep neural networks. Deep learning, as a branch of machine learning (ML), has brought us human or super-human level performance on tasks such as image classification and game playing. This ‘Software 2.0’ paradigm now reaches across computer science and well beyond in the form of the application of deep ML algorithms.
The most studied connection between optimisation and machine learning is continuous optimisation. However, an area beginning to be influenced in a new way by ML is combinatorial optimisation. This research area is studied for both its importance in theory (combinatorial optimisation problems are NP-hard problems), and for its importance in real-world decision problems, such as planning drivers and routes for a fleet of delivery vehicles. Combinatorial optimisation problems are studied in operations research (OR) and also traditionally in symbolic artificial intelligence (AI) such as constraint programming (CP) and satisfiability modulo theories.
This Dagstuhl Seminar builds on recent scattered initiatives for combining ML with CP, and with OR more generally, having the ambition to set the agenda for constraint-based ‘Combinatorial Optimisation 2.0’. Mostly disjoint communities have focussed on different approaches to combinatorial optimisation. This division between, on the one hand, the OR and symbolic AI communities, and on the other, the ML and functional AI communities, is historically strong. While in recent years a dialogue between symbolic and functional AI communities has emerged, there remains little to no connection between the discrete OR and ML communities. CP is seen as a connecting bridge between OR and AI, and therefore the CP–ML dialogue as having potential to be particularly influential; indeed, recent attention indicates that the combination of CP and ML is very promising.
Although the first emphasis of the seminar is on the use of ML techniques to improve combinatorial optimisation, benefits also flow in the other direction: there is a growing realisation that integrating optimisation techniques and ML can lead to an improved interplay between learnt models and domain experts, and that optimisation can support certification and diagnosis of ML models. In general, strengthening the connection between these two research areas will help bridging the gap between predictive and prescriptive analytics.
The structure of the seminar is group discussions to develop a research agenda. The seminar’s discussions begin with eight questions that help to define the synergistic frontier among ML, CP and OR: (1) What are the potentials and limitations of end-to-end solving of combinatorial optimisation by ML approaches? (2) How can CP and discrete optimisation models be acquired or refined from data? (3) How can CP methods and classical OR methods be enhanced by incorporating ML? (4) How can ML models be embedded within CP models? (5) How can OR–CP hybrid approaches benefit from recent ML ideas? (6) How can ML benefit from combinatorial optimisation ideas? (7) How can combinatorial optimisation mitigate the weaknesses of ML methodologies? (8) What forms of human-in-the-loop modelling and solving are promising?
The key outcomes this seminar aims for are (1) a research agenda, flowing from the above questions, (2) a journal special issue (tentatively in Artificial Intelligence, Constraints or INFORMS Journal of Computing), and (3) activities to support and expand interactions between the involved fields.
- Karen Aardal (TU Delft, NL) [dblp]
- Claudia D'Ambrosio (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Bistra Dilkina (USC - Los Angeles, US) [dblp]
- Ferdinando Fioretto (Syracuse University, US)
- Emma Frejinger (University of Montreal, CA) [dblp]
- Maxime Gasse (Polytechnique Montréal, CA) [dblp]
- Stefano Gualandi (University of Pavia, IT)
- Oktay Gunluk (Cornell University - Ithaca, US) [dblp]
- Tias Guns (KU Leuven, BE) [dblp]
- Serdar Kadioglu (Brown University - Providence, US) [dblp]
- Lars Kotthoff (University of Wyoming - Laramie, US) [dblp]
- Hoong Chuin Lau (SMU - Singapore, SG) [dblp]
- Pierre Le Bodic (Monash University - Clayton, AU) [dblp]
- Andrea Lodi (Cornell Tech - New York, US) [dblp]
- Marco Lübbecke (RWTH Aachen, DE) [dblp]
- Sofia Michel (NAVER Labs Europe - Meylan, FR)
- Andrea Micheli (Bruno Kessler Foundation - Trento, IT) [dblp]
- Ruth Misener (Imperial College London, GB) [dblp]
- Laurent Perron (Google - Paris, FR) [dblp]
- Sebastian Pokutta (Zuse Institut Berlin, DE) [dblp]
- Louis-Martin Rousseau (Polytechnique Montréal, CA) [dblp]
- Helge Spieker (Simula Research Laboratory - Oslo, NO)
- Kevin Tierney (Universität Bielefeld, DE) [dblp]
- Pashootan Vaezipoor (University of Toronto, CA)
- Pascal Van Hentenryck (Georgia Institute of Technology, US) [dblp]
- Stefan Voß (Universität Hamburg, DE) [dblp]
- Neil Yorke-Smith (TU Delft, NL) [dblp]
- Yingqian Zhang (TU Eindhoven, NL) [dblp]
- Artificial Intelligence
- Discrete Mathematics
- Machine Learning
- combinatorial optimisation
- machine learning
- constraint programming
- data science
- operations research