Data-Driven Optimization: Enhancing Combinatorial Optimization Solvers with Machine Learning

Machine learning (ML) and operations research (O.R.) have traditionally been two distinct disciplines with two nonoverlapping communities of practitioners. Each field has a different focus, tools and objectives. Both approaches are often complementary, and there is great potential for combining them. Anand Subramanian and Holger Teichgraeber, in their article “The Interplay between Operations Research and Machine Learning,” take a look at this recent trend and explore various ways ML and O.R. approaches can be combined.

One particular way ML can be applied in O.R. is to improve the process of designing algorithms and solvers. O.R. is sometimes called the science of decision-making. Interestingly, within optimization algorithms, numerous decisions are constantly made. These decisions are themselves difficult computational problems, and various ways of making these decisions have been worked out. This is one particularly promising place in which ML can explore hidden patterns. Let’s look at different examples of how this can be done in practice.

Strong Branching

Branch-and-bound methods (B&B) are powerhouses of modern mixed-integer linear program (MILP) solvers. One of the repeat decisions is selecting a fractional variable to branch on. This is a key step in any B&B algorithm because the quality of these decisions influences the size of the B&B tree and subsequently the running time of the entire algorithm. Not surprisingly, many research efforts have been devoted to designing better ways to choose a variable to branch on.

The branching strategy consistently resulting in the smallest B&B trees is strong branching. Strong branching is a look-ahead strategy: The algorithm considers different integer choices for each fractional variable in the linear programming (LP) relaxation and selects the most promising one. Although this is a strategy performing well in practice, it is very expensive computationally.

Gasse proposed using a graph neural network (GNN) for the variable selection problem to imitate the branching decisions of the strong branching heuristic [1]. A GNN is a type of deep learning model designed to process and analyze structured data represented as graphs, enabling it to capture relationships and patterns within the graph. The GNN of Gasse operates on a binary representation of a MILP in which variables and constraints are nodes and an edge connects a variable node to a constraint node if the variable appears in that constraint.

The authors use imitation learning to train the model from the strong branching expert rule. Imitation learning is an ML approach (similar to reinforcement learning) in which an agent learns a task by observing and mimicking the behavior of an expert, often using a data set of expert demonstrations to train the model. The training process involves running the B&B algorithm and collecting sub-problems and their corresponding strong branching decisions (all done offline).

The reasoning behind this approach is that training the model to replicate the complete strong branching heuristic should result in a computationally efficient model that, while not necessarily perfect, can reliably identify good variables for branching. The authors report promising results across different data sets. Successful deployment of a machine learning model in this context is a blend between the accuracy of the model and the speed of inference. Some of the competing models offer better accuracy, but GNNs beat them in total time to run the B&B.

The model’s objective is to identify potential underlying patterns in the data, specifically focusing on the topology of the variable-constraint graph and structure of the coefficients to determine suitable fractional variables for branching. By employing GNNs, the need for manual feature engineering is eliminated, which allows the network to capture these patterns. Additionally, GNN uses a shared parametric representation, enabling its application to networks of different sizes. Impressively, the approach performs well even on larger graphs than those used for training. It is worth noting that there have been subsequent developments and ongoing efforts to refine these techniques.

Chip Placement

The chip placement problem is a critical challenge in semiconductor design, in which electronic components (macros) must be strategically arranged on a silicon wafer to optimize the performance, minimize wiring lengths, reduce signal congestion and manage thermal considerations, all while adhering to stringent design constraints. This is an enormous combinatorial task (millions to billions of nodes) similar to fitting a complex jigsaw puzzle. Achieving an optimal placement is crucial for the functionality, speed and efficiency of integrated circuits found in various electronic devices. Traditionally, this task has heavily relied on human expertise and heuristic methods, which become increasingly challenging as chip designs grow in complexity.

Mirhoseini proposes a new, learning-based approach to attack this problem that achieves superhuman performance [2]. The central innovation of the paper revolves around the utilization of deep reinforcement learning techniques to make intelligent decisions regarding component placement. It employs an edge-based convolutional GNN, which is trained by reinforcement learning – a machine learning paradigm in which an agent learns to make sequential decisions by interacting with an environment to maximize a cumulative reward signal.

In each iteration of training, the model sequentially places all of the macros of the chip block. The reward to the model at the end of each iteration is a negative weighted sum of proxy wirelength and congestion. These are two parameters of the design that reflect how well it will perform. Through repeated iterations, the agent learns to make decisions that result in superior chip layouts. Reinforcement learning enables the agent to efficiently explore the placement space and discover optimal configurations, ultimately reducing design time and potentially improving chip performance.

The authors report that their approach produces chip placements that either surpass or are on par with those created by human expert chip designers. In contrast, the top-performing alternatives require human experts’ involvement and consume multiple weeks for each of the multiple blocks in a contemporary chip.

More Approaches

These are just two examples from already large but still growing literature on applying ML to design optimization algorithms. These instances exemplify the emerging paradigm of automated algorithm design. Within this literature, numerous other concepts and techniques are explored.

At a fundamental level, numerous solvers are equipped with a range of adjustable parameters that can be fine-tuned, either prior to solving or dynamically during runtime. Clearly, this presents an ideal opportunity for the application of ML. An ML model can be trained to determine the optimal parameter configuration for a given problem instance or based on historical choices made during runtime [3].

Algorithm selection is another approach where the most suitable algorithm for a specific problem instance is selected from a portfolio of algorithms. This task can be delegated to an ML model, which can be trained using either engineered features extracted from the optimization problem instance or a feature-free deep learning model [4].

There are also several valuable survey papers that cover various aspects of this field [5-7].

Key Takeaways

Machine learning has witnessed remarkable progress in computer vision, natural language processing and robotics. ML models can play computer games on a superhuman level, beat humans in chess, and autonomously navigate and perform complex tasks in simulated and real-world environments. Algorithms are taking over new disciplines. This raises questions about the potential for algorithms to excel in designing algorithms themselves. One might wonder why optimization, as a field, wouldn’t be among the first to benefit from these advancements.

End-to-end approaches, which learn algorithms directly from data as observed in other domains, currently appear to be out of reach in optimization. Nevertheless, a middle-ground approach that integrates ML into existing O.R. methods and techniques appears to be the promising path forward. This approach allows for the development of new solvers while leveraging the wealth of optimization theory and methods that have been developed over the years.

Integrating ML into O.R. solvers and consequently automating the design of optimization solvers presents several compelling advantages. First, it reduces the demand for extensive human domain expertise, minimizes labor resources and significantly cuts down the time required for crafting new algorithms for optimization problems as compared to the prevalent manual design process.

Second, by thoroughly exploring the algorithmic landscape, automated design has the potential to surpass human-level design, thereby outperforming traditionally engineered algorithms. Third, it may democratize the accessibility of O.R. tools, extending their use to a broader spectrum of practitioners, including data scientists who may not possess extensive training in optimization.

Next, it opens the door to the development of solvers, whether exact or heuristic, that are finely tailored to specific types of problem instances. Finally, it is conceivable that large-scale models could emerge with exposure to a substantial number of MILP examples, enabling them to deliver universally effective solutions. Think of this in the context of large language models that have demonstrated remarkable capabilities through extensive exposure to diverse language data.

References

1. Gasse, Maxime, Didier Chetelat, Nicola Ferroni, Laurent Charlin and Andrea Lodi, 2019, “Exact combinatorial optimization with graph convolutional neural networks,” Advances in Neural Information Processing Systems, Vol. 32 (NeurIPS 2019).
2. Mirhoseini, Azalia, et al., 2021, “A graph placement methodology for fast chip design,” Nature, 594, No. 7862, pp. 207-212.
3. Stützle, Thomas and Manuel López-Ibáñez, 2019, “Automated design of metaheuristic algorithms,” Handbook of Metaheuristics, New York: Springer, pp. 541-579.
4. Kerschke, Pascal, Holger H. Hoos, Frank Neumann and Heike Trautmann, 2019, “Automated algorithm selection: Survey and perspectives,” Evolutionary Computation, Vol. 27, No. 1, pp 3-45.
5. Bengio, Yoshua, Andrea Lodi and Antoine Prouvost, 2021, “Machine learning for combinatorial optimization: A methodological tour d’horizon,” European Journal of Operational Research, Vol. 290, No. 2, pp. 405-421.
6. Cappart, Quentin, Didier Chetelat, Elias B. Khalil, Andrea Lodi, Christopher Morris and Peter Velickovic, 2023, “Combinatorial optimization and reasoning with graph neural networks,” Journal of Machine Learning Research, Vol. 24.
7. Karimi-Mamaghan, Maryam, Mehrdad Mohammadi, Patrick Meyer, Amir Mohammad Karimi-Mamaghan and El-Ghazali Talbi, 2022, “Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: A state-of-the-art,” European Journal of Operational Research, Vol. 296, No. 2, pp. 393-422.