Data-Driven 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:

• $\mathrm{■}$

  What is the equivalent of saving models/checkpoints in ML or natural language processing (NLP) in data-driven CO (DDCO)?

• $\mathrm{■}$

  Can we share pre-trained models to generate SAT/CP/MIP embeddings without training again?

• $\mathrm{■}$

  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.

• $\mathrm{■}$

  What is the equivalent of “large” aspect from large language NLP models for DDCO?

• $\mathrm{■}$

  Is there a (super) GLUE benchmark equivalent for DDCO?

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.

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:

• $\mathrm{■}$

  Scalability. OR methods tend to be limited when dealing with extremely large datasets that are often associated with ML applications.

• $\mathrm{■}$

  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.

• $\mathrm{■}$

  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.

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:

• $\mathrm{■}$

  Does the ML model output individual actions or does it output an instance-specific heuristic?

• $\mathrm{■}$

  Can we learn insights about the problem from the predictions?

• $\mathrm{■}$

  Where does or could deep RL work best?

• $\mathrm{■}$

  Can we make a unified routing model (a ‘foundation model’)?

This working group started from the general questions: which is the big challenge in MIP solving? And, will 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.