Machine Learning Augmented Algorithms for Combinatorial Optimization Problems

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.

Increasingly, combinatorial optimisation problems follow a predict + optimize paradigm, where part of the parameters (costs, volumes, capacities) are predicted from data, and those predictions are fed into a downstream combinatorial optimisation problem. How to best train these predictive models? Decision-focused learning (DFL) is an emerging paradigm in machine learning which trains a model to optimize decisions, integrating prediction and optimization in an end-to-end system. This paradigm holds the promise to revolutionize decision-making in many real-world applications which operate under uncertainty, where the estimation of unknown parameters within these decision models often becomes a substantial roadblock to high-quality solutions. This talk presents a comprehensive review of DFL. It provides an in-depth analysis of the various techniques devised to integrate machine learning and optimization models, introduces a taxonomy of DFL methods distinguished by their unique characteristics, and conducts an extensive empirical evaluation of these methods proposing suitable benchmark dataset and tasks for DFL. Finally, we’ll provide valuable insights into current and potential future avenues in DFL research.

I will talk about utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. I will cover prior results going in that direction, and then I will talk about our recent work in which we propose a generic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear-time algorithms for, e.g., Vertex Cover, Steiner Tree, Min-Weight Perfect Matching, Knapsack, and Clique. Our algorithms produce an optimal solution when provided with perfect predictions and their approximation ratio smoothly degrades with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond the reach without predictions in given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem. I will conclude with an empirical evaluation of our approach. This is based on joint work with Antonios Antoniadis, Marek Eliáš, and Moritz Venzin.

In this tutorial talk, I present recent advances on (i) augmenting discrete optimization algorithms with learning components and (ii) learning methods that incorporate the combinatorial decisions they inform. While the first set of techniques focus on infusing discrete optimization with machine learning, the second set of techniques focus on infusing machine learning with constrained decision making. The talk is based on my recent publications [1, 2, 3].

Prompting LLMs is a challenging art where different ways of expressing the same idea can lead to drastically different responses. Not prompting in the right way gives suboptimal performance and has led to the budding space of prompt engineering and optimization techniques. A standard example here is that appending the string “let’s think step by step” to the prompt may significantly improve the quality on few-shot classification tasks. In this session, we’ll first cover how prompt optimization can be expressed as a combinatorial optimization problem (over the token sequence space) and overview the standard methods here. Beyond this, prompt optimization problems are often not solved a single time in isolation, but are repeatedly solved for every new task or piece of information we want to extract from the language model. So, we’ll conclude with an overview of learned optimization, or amortization, to share the information between the repeatedly-solved optimization problems.

Constraint programming (CP) is a well-established method for tackling combinatorial problems. Traditionally, CP has focused on solving isolated problem instances, often overlooking the fact that these instances frequently originate from related data distributions. In recent years, there has been a growing interest in leveraging machine learning, particularly neural networks, to enhance CP solvers by utilizing historical data. Despite this interest, it remains unclear how to effectively integrate learning into CP engines to boost overall performance. In this presentation, I will share my experience in tackling this challenge, from my initial attempts to my current research directions.

Real-life decision making often involves reasoning on ill-defined problems, where exact constraints or parameters (such as costs) are unknown. The goal of Decision-Focused Learning (DFL) is to automatize the definition of problem parameters by using Deep Learning to extract knowledge out of the environment. The main challenge here is to combine discrete optimization for reasoning with continuous optimization for learning. I will present one method to learn discrete graphical models, the reasoning framework we chose. We first assessed it on learning the rules of Sudoku, a popular benchmark for DFL methods. We then apply it to Computational Protein Design, a real-world problem that can be described and tackled with graphical models. We deep learned the interactions within existing proteins to better guide the design towards new proteins of interest.

The feasibility pump algorithm is a widely used heuristic to find feasible primal solutions to mixed-integer linear problems. Many extensions of the 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 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 instances from the MIPLIB library and show that these modifications can substantially reduce the number of iterations needed to find a primal solution.

Combinatorial optimization problems play a pivotal role in various domains, challenging researchers to find optimal solutions within large solution spaces. One key strategy to tackle the complexity of these problems is data reduction, where instances are simplified to facilitate more efficient algorithms. Even though there are numerous reduction rules available, they are often not used in applications since the time needed to test them for the whole graph exhaustively becomes infeasible. With this, a new problem in the form of early reduction screening emerges. In this talk, we tackle this problem in the context of maximum weight independent sets using graph neural networks. Before checking if an expensive data reduction rule is applicable, we consult a GNN oracle to decide if the probability of successfully reducing the graph is sufficiently large. With this approach, we can use even expensive reduction rules successfully in feasible time. We introduce a new supervised learning dataset and provide first results using established graph neural network architectures.

Augmenting classical algorithms with learned predictions or configurations has found many successful applications in energy management, database systems, scientific computing, and beyond. At the same time it has been theoretically challenging to go beyond the computationally inefficient learning of static predictors and configurations. We study the problem of sequentially solving linear systems, a fundamental problem in numerical computing, and introduce an algorithm that efficiently learns to do instance-optimal linear solver configuration while using only the number of iterations as feedback. Our approach points towards new directions for analyzing iterative methods, designing surrogate objectives for optimizing algorithmic costs, and incorporating tools from online learning into algorithm design.

Graph Neural Networks (GNNs) are a machine learning architecture to learn functions on graphs. For example, since problem instances for combinatorial optimisation tasks are often modelled as graphs, GNNs have recently received attention as a natural framework for finding good heuristics in neural optimisation approaches. The question which functions can actually be learnt by message-passing GNNs and which ones exceed their power has been studied extensively. In this talk, I will consider it from a graph-theoretical perspective. I will survey the Weisfeiler-Leman algorithm as a combinatorial procedure to analyse and compare graph structure, and I will discuss some results concerning the power of the algorithm on natural graph classes. The findings directly translate into insights about the power of GNNs and of their extensions to higher-dimensional neural networks.

In this talk, we explore some recent and ongoing advancements in non-clairvoyant scheduling in the learning-augmented framework, which integrates error-prone predictions into online algorithm design. We examine various prediction models, showcasing algorithms for non-clairvoyant scheduling with strong error-dependent performance guarantees. In particular, we ask which type of information is required and how an algorithm should receive it to achieve reasonable performance guarantees. Moreover, we consider recently popular prediction models for other problems, and discuss how they may be integrated into scheduling problems.

This talk will provide perspectives, progress, and open questions on two distinct forms of integration between optimization and learning. First, we will present an analysis of Decision Focused Learning approaches, highlighting structural problem properties that can cause their advantage w.r.t. classical techniques to be significantly diminished. We will suggest a possible way out, with interesting practical applications, together with one solution technique. Second, we consider the problem of enforcing hard constraints in Neural Networks, discussing a training-time approach with satisfaction guarantees. The method combines Projected Gradient Descent with a neural architecture that embeds a trainable over-approximation module. For both the considered setting, we highlight open problems and promising research directions.

In this talk, I will discuss some open problems in applying machine learning for edge contractions in multilevel graph partitioning. This will be in the context of our graph partitioning software Karlsruhe Hypergraph Partioning (KaHyPar).

The graph coloring problem asks for an assignment of the minimum number of distinct colors to vertices in an undirected graph with the constraint that no pair of adjacent vertices share the same color. The problem is a thoroughly studied NP-hard combinatorial problem with several real-world applications. As such, a number of greedy heuristics have been suggested that strike a good balance between coloring quality, execution time, and also parallel scalability. In this work, we introduce a graph neural network (GNN) based ordering heuristic and demonstrate that it outperforms existing greedy ordering heuristics both on quality and performance. Previous results have demonstrated that GNNs can produce high-quality colorings but at the expense of excessive running time. The current paper is the first that brings the execution time down to compete with existing greedy heuristics. Our GNN model is trained using both supervised and unsupervised techniques. The experimental results show that a 2-layer GNN model can achieve execution times between the largest degree first (LF) and smallest degree last (SL) ordering heuristics while outperforming both on coloring quality. Increasing the number of layers improves the coloring quality further, and it is only at four layers that SL becomes faster than the GNN. Finally, our GNN-based coloring heuristic achieves superior scaling in the parallel setting compared to both SL and LF.

Recent years have seen considerable progress in machine learning–based heuristics for combinatorial optimization, particularly constructive neural heuristics that use neural networks to build solutions step by step. Despite their success across a variety of combinatorial tasks, these methods often require specialized models trained separately for each problem and instance distribution. In this talk, I will discuss recent works on improving the generalization of neural combinatorial optimization approaches. I will introduce a framework that leverages the symmetries inherent in many combinatorial problems to boost the out-of-distribution generalization. Building on this framework, I will present GOAL, a generalist model capable of efficiently solving multiple combinatorial problems and which can be fine-tuned to handle new ones. By tackling a broad range of tasks – including routing, scheduling, packing, location, and graph problems – GOAL represents a promising step toward developing a foundation model for combinatorial optimization. I will finish with some current challenges and open questions.

Algorithm selection addresses the challenge of determining which of the available algorithms is most appropriate for solving a particular problem instance. Hyper-heuristics are a high-level, problem-independent approach that aims to automate the design of heuristic methods by combining and selecting low-level heuristics.

In this talk, we will present our work on algorithm selection for various problem domains, including scheduling and tree decomposition. We will also discuss our recent work on reinforcement learning for selection hyper-heuristics.

Counterfactual Analysis has shown to be a powerful tool in the burgeoning field of Explainable Artificial Intelligence. In Supervised Classification, this means associating with each record a so-called counterfactual explanation: an instance that is close to the record and whose probability of being classified in the opposite class by a given classifier is high. In this talk we take a stakeholder perspective, and we address the setting in which a group of counterfactual explanations is sought for a group of instances. We introduce some mathematical optimization models as illustration of each possible allocation rule between counterfactuals and instances and tasks beyond Supervised Classification.

Predictive models are playing an increasingly pivotal role in optimizing decision-making. This talk introduces an approach wherein a series of (possibly) stochastic sequential decision problems are initially solved offline, and subsequently, a predictive model is constructed based on the offline solutions to facilitate real-time decision-making. The applicability of this methodology is demonstrated through two use cases: patient radiation therapy, where managers need to preserve capacity for emergency cases, and a novel dynamic employee call-timing problem for the scheduling of casual personnel for on-call work shifts.

In many combinatorial optimization problems, access to input data is modeled in an abstract way via oracles, e.g., independence oracles for matroids, distance functions in a metric space, or comparators for sorting elements. Depending on the underlying application, the actual use of such oracles can be computationally expensive, as it may require access to slow database systems or large machine learning (ML) models. In the two-oracle model, we assume access to a second, weaker oracle, which is computationally cheap but may provide inaccurate answers. The goal is to design algorithms that exploit the information provided by the cheap oracle to minimize the number of calls to the expensive oracle.

Two-oracle models have been studied in several ML applications, such as data labeling with weak and strong data labelers, text clustering with two oracles for text similarity, or more generally in ML pipelines that combine the use of scalable and expensive models. More recently, Bai and Coester [NeurIPS’23] considered two-oracle models from the point of view of learning-augmented algorithm design for sorting with access to two comparators. As usual, the goal is to design robust algorithms with performance guarantees that improve with the quality of the second, cheap oracle. In this talk, we discuss the two-oracle model and its applications, and study it from the perspective of learning-augmented algorithms by applying it to the fundamental problem of finding a maximum-weight basis in a matroid.

The talk is based on a joint work with Franziska Eberle, Felix Hommelsheim, Alexander Lindermayr, Nicole Megow, and Zhenwei Liu.

I will present recent work on graph representation learning to guide the search of AI planners. I will introduce GNN and other graph learning representations that exploit the relational structure of planning domains. They allow our planner GOOSE to learn search guidance (e.g. heuristic cost estimates, state rankings) from solutions to just a few small problems, and solve substantially larger problems than trained on. Perhaps surprisingly, our experimental results show that classical machine learning approaches vastly outperform deep learning ones in this context. Moreover, Greedy Best-First Search guided by our best learnt heuristics outperforms the state of the art model-based planner, Lama, on the problems of the latest International Planning Competition Learning track, leading to the possibility that learnt heuristics may replace existing model-based heuristics in the near future.

This is joint work with Dillon Chen, Mingyu Hao, Joerg Hoffmann, and Felipe Trevizan

We consider the problem of graph searching with prediction recently introduced by [1]. In this problem, an agent, starting at some vertex $r$ has to traverse a (potentially unknown) graph $G$ to find a hidden goal node $g$ while minimizing the total distance travelled. We study a setting in which at any node $v$, the agent receives a noisy estimate of the distance from $v$ to $g$. We design algorithms for this search task on unknown graphs. We establish the first formal guarantees on unknown weighted graphs and provide lower bounds showing that the algorithms we propose have optimal or nearly optimal dependence on the prediction error. Further, we perform numerical experiments demonstrating that in addition to being robust to adversarial error, our algorithms perform well in typical instances in which the error is stochastic. Finally, we provide alternative simpler performance bounds on the algorithms of [1] for the case of searching on a known graph, and establish new lower bounds for this setting.

The presentation is based on the results in [2].

We discussed key connections, shared concepts and research directions across the related paradigms of machine learning for combinatorial optimization, decision-focused learning (DFL), algorithms with predictions, and neuro-symbolic computing.

This discussion focused on identifying commonalities in theoretical frameworks and results between contextual optimization, decision-focused learning (DFL), ML augmented CO solvers and algorithms with predictions. For the purpose of this discussion, we established that DFL can be considered a sub-class of contextual optimization problems. We observed that many theoretical results in CO/DFL rely on learning theory, focusing on out-of-sample generalization based on in-sample training data. While ML-augmented CO solvers also exhibit generalization properties, extending these results to prove stronger generalization bounds for techniques like ML-augmented branch-and-bound would be highly valuable. On the other hand, algorithms with predictions often focus on consistency-robustness trade-offs, considering the level of prediction performance as an input. Understanding how to merge these results with the statistical generalization bounds prevalent in CO/DFL would significantly advance our understanding of these interconnected fields.

Specific research questions that emerged in this theme include:

• $\mathrm{■}$

  Robustness in ML-Augmented CO: Can we better understand how ML augmented CO solvers have robustness guarantees that are stronger/more fine-grained than just preserving optimality in the worst-case, and instead depend on the learning guarantees and may use distribution shift concepts (for example) to understand how robust ML augmented solvers are when they are applied to out of distribution data?

• $\mathrm{■}$

  Defining Robustness for CO/DFL: What constitutes the “correct” notion of robustness for CO/DFL? If we consider learning with a perfect future information (PFL) model as a baseline, how can we theoretically compare the performance of DFL and PFL models in a meaningful way?

• $\mathrm{■}$

  Point Predictions in Nonlinear Settings: Under what conditions are point predictions sufficient for 2-stage problems and more generally, for nonlinear optimization problems? How significant can the bias of DFL-trained models be?

• $\mathrm{■}$

  Can we prove some consistency-robustness properties when algorithms with predictions framework is used on branch-and-bound problems? Can we build a bridge between generalization guarantees and algorithms-with-predictions guarantees?

• $\mathrm{■}$

  Fairness and Out-of-Distribution Considerations: How can we incorporate fairness properties and out-of-distribution robustness into DFL formulations? Can counterfactual explanations be leveraged to build fairer DFL models? Can we establish generalization guarantees for fairness metrics in DFL?

• $\mathrm{■}$

  Computational Complexity in DFL, algorithms with prediction and ML augmented combinatorial optimization: How can we define and analyze the computational complexity in these areas, considering factors like the number of gradient or oracle calls? How can we optimally trade off the computational costs of training, inference, and optimization within the DFL framework? What are the optimal sample sizes for training ML-augmented CO algorithms, and are there scaling laws that govern this relationship? Can we get useful lower bounds on the sub-optimality gap while training?

• $\mathrm{■}$

  Dynamic Optimization and Regret: How can we effectively apply ML techniques in dynamic optimization settings, especially when traditional regret bounds may not be well-defined? How can we dynamically update ML models to adapt to changing environments?

Many combinatorial optimization algorithms incorporate design choices that do not impact their worst-case theoretical bounds. However, these choices can significantly influence their practical performance, e.g., in terms of running time. By leveraging machine learning techniques to learn optimal or near-optimal choices for typical input instances, we can significantly enhance the efficiency of these algorithms.

We considered two concrete examples:

• $\mathrm{■}$

  The classic Bellman-Ford algorithm for finding shortest paths with negative edge weights relaxes all edges multiple times. While the worst-case running time remains unaffected by the order of edge relaxations, the practical performance can vary dramatically. By learning a near-optimal relaxation order for a given input distribution, we can potentially reduce the number of iterations required for convergence, significantly improving the algorithm’s efficiency.

• $\mathrm{■}$

  In graph partitioning, particularly $ϵ$-balanced partitioning, multilevel approaches are state-of-the-art. These methods involve coarsening the graph by repeatedly contracting edges, generating an initial partitioning, and then uncoarsening to obtain a partition for the original graph. Current coarsening strategies often rely on greedy heuristics. However, by learning which edges should not be contracted using machine learning techniques, we can potentially improve the quality of the initial partitioning and ultimately the final solution.

In the context of leveraging reinforcement learning for combinatorial optimization, there has been some progress on end-to-end reinforcement learning (RL) algorithms for combinatorial optimization problems with no global constraints, and for which all constraints can be checked incrementally at each step. The key challenge in this area lies for problems with at least one global constraint. In this case, determining whether a candidate solution satisfies the global constraints often requires evaluating the solution as a whole. This presents a significant challenge, as it is not possible to incrementally check constraint satisfaction during the solution construction process. Potential approaches to address this challenge include:

• $\mathrm{■}$

  Penalty-based Methods: Penalizing “nogoods” (violations of global constraints) during RL training.

• $\mathrm{■}$

  Repair Strategies: Checking constraints at the end of the solving process and then repairing the infeasible solution.

• $\mathrm{■}$

  Predicting Feasibility: Predicting the likelihood that a partial solution can be extended to a complete, consistent solution.

• $\mathrm{■}$

  Perturbation Methods: Working with perturbations of existing feasible solutions rather than directly constructing solutions from scratch.

In contrast to integrating RL within or alongside a combinatorial optimization solver, end-to-end RL approaches may require backtracking mechanisms to handle constraint infeasibility.

A crucial challenge lies in the generalizability of end-to-end and learning-augmented solving. This includes generalization across problem instance sizes, generalization between related problem classes, and the inherent generality of the underlying combinatorial optimization solvers.

Key research questions to address in this area also include (i) developing a comprehensive theoretical framework for reinforcement learning in the context of combinatorial optimization problems and (ii) exploring the potential benefits of active learning techniques for improving the efficiency and effectiveness of learning-based optimization solvers.

A key question in the area of machine learning for combinatorial optimization is “Can we develop foundation models that capture the underlying structural properties of different combinatorial optimization tasks?” These foundation models could then be fine-tuned for specific pruning or branching tasks.

Herein, we list some of the other research questions identified in this theme:

• $\mathrm{■}$

  Model Depth: A fundamental question is: How much expressive power, specifically in terms of model depth (e.g., the number of layers in a graph neural network), is necessary for an ML model to effectively address various combinatorial optimization tasks? For instance, what level of expressivity is required for a GNN to act as an effective proxy solver or for learning-to-prune?

• $\mathrm{■}$

  What are the advantages of decision focused learning (DFL) over the standard mean squared error loss functions?

• $\mathrm{■}$

  How can neural networks be effectively trained within the DFL framework?

• $\mathrm{■}$

  What biases get introduced when using point prediction for stochastic settings? There are potential connections between these biases and the field of inverse optimization, which aims to infer the underlying parameters of an optimization problem given observed decisions.

• $\mathrm{■}$

  Can we enable more compact and efficient representations of complex optimization problems in higher-dimensional spaces?

• $\mathrm{■}$

  Drawing inspiration from NLP, where foundation models like large language models (LLMs) are pre-trained on large text corpora, can we explore analogous pre-training tasks for combinatorial optimization? What simple, yet informative, tasks can be used for pre-training in the context of combinatorial optimization? In NLP, next-token prediction serves as a powerful pre-training objective. Can we identify an analogous task for combinatorial optimization problems, perhaps involving predicting partial solutions or exploring the local neighborhood of a given solution?

• $\mathrm{■}$

  What constitutes suitable training data for pre-training such foundation models? Should it include solutions, explored search trees, or other relevant information?

When integrating machine learning (ML) models into combinatorial optimization algorithms, the trade-off between efficiency, interpretability and accuracy is crucial. We first outline the motivation for efficiency and interpretability of the learning techniques in the context of optimization problems.

• $\mathrm{■}$

  Efficiency: If an ML model is used as a subroutine within a combinatorial optimization algorithm, it might be invoked very frequently. A fast inference of the learnt model can help ensure scalability of the optimization algorithm to large data.

• $\mathrm{■}$

  Interpretable models can facilitate the development of hand-crafted heuristics, enabling manual optimization and providing a deeper understanding of the algorithm’s behavior.

• $\mathrm{■}$

  Interpretability enhances our understanding of how ML-augmented algorithms function, improving our ability to analyze and debug them.

Next, we consider the two popular models in terms of this trade-off between efficiency, interpretability and accuracy.

• $\mathrm{■}$

  Decision Trees: Offer high efficiency and interpretability but may have limited expressive power for complex tasks.

• $\mathrm{■}$

  Neural Networks (NNs): More expressive but generally less efficient and more difficult to interpret.

Specifically, the discussion focused on Graph Neural Networks (GNNs) and we noted that the expressive power of GNNs (without additional features) is equivalent to the Weisfeiler-Leman graph isomorphism test. This connection can be leveraged to reinterpret GNN decisions in terms of the colors assigned by the WL algorithm. However, developing automated techniques for interpreting GNN decisions beyond manual analysis of WL colorings remains an open challenge.

In terms of interpretability of standard neural networks, increasing the number of features or hidden layers in a NN significantly increases its complexity and hinders interpretability. However, the following techniques are used in this context:

• $\mathrm{■}$

  Distillation: Train a simpler model (e.g., using symbolic regression) to imitate the behavior of the original NN.

• $\mathrm{■}$

  LIME: Ranks the feature importance for specific decisions and given input instances.

• $\mathrm{■}$

  Visualization Techniques: Visualize the activation patterns within the NN to understand how it processes information.

• $\mathrm{■}$

  Encode the learning model as a combinatorial optimization problem, e.g., a MIP.

• $\mathrm{■}$

  Model Simplification: Pruning of low-weight connections and quantization can help to simplify a NN.

Unfortunately, the applicability of these techniques is limited and they are often not sufficient to understand complex NNs.

In terms of improving efficiency, the following techniques were discussed:

• $\mathrm{■}$

  Modular Subproblems: Decompose complex problems into smaller, more manageable subproblems, which can be solved more efficiently. An example application for this is planning.

• $\mathrm{■}$

  Select the appropriate ML model (classification, regression, ranking) based on the specific task to optimize efficiency and interpretability.

• $\mathrm{■}$

  GPU Acceleration: Utilize GPUs for efficient inference, although data transfer overhead must be considered. GPU acceleration can be particularly beneficial when the algorithm itself already runs on the GPU.

Decision-focused learning (DFL) has witnessed significant progress in recent years. However, to achieve real-world success and broader applicability, DFL methods must become more scalable. This session focused on open challenges and potential contributions to DFL in terms of:

• $\mathrm{■}$

  Open-Source Code and Datasets: Expanding the availability of open-source code and datasets specifically designed for DFL applications.

• $\mathrm{■}$

  Scalability for Real-World Problems: Enhancing the ability of DFL methods to handle the complexities of real-world data and problem sizes.

Currently, the most widely used open source software for DFL is PyEPO by Khalil et al.⁵⁵5https://github.com/khalil-research/PyEPO. Although it has some limitations, such as being able to be used only for the objective coefficients of a single linear programming instance, it is still a good starting point for implementing DFL methods. The repository of the DFL survey paper [1] has implementations for several problems, namely, optimization, knapsack, matching, portfolio optimization, (Warcraft) shortest path independent of PyEPO.

A key hurdle in research on DFL methodologies is finding real-world data that aligns well with DFL’s requirements. For example, in many routing applications, the travel time information is only observed for the selected path. A potential solution to this hurdle is to generate optimization problems synthetically whenever appropriate data is available. An example is the bike-sharing applications where there is a lot of data made available, but a synthetic problem such as a shortest path or traveling salesman problem can be defined on this real data. In addition, there is a need to develop a standardized format for storing data and optimization problems specifically for DFL applications. This would facilitate sharing and collaboration within the DFL research community.

Scalability in DFL can encompass various aspects, including the size of the optimization problem and the available data volume. Notably, problem size doesn’t always directly correlate with optimization instance difficulty. To address the scalability issues, a potential approach is to train the learning model with small instances of the optimization problem, and then perform inference on larger instances. This kind of scaling can be done, for example, when the mapping from the features to the problem parameters is deterministic, but the feature is random. This mapping can be learned for small instances in a DFL fashion, and the learned mapping can be used in larger instances.

By addressing these challenges and fostering collaboration through open-source code and datasets, DFL can unlock its full potential for solving real-world decision-making problems at scale.