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.

Creative Commons BY 4.0

Emma Frejinger, Andrea Lodi, Michele Lombardi, and Neil Yorke-Smith