Abstract
In recent years, Machine Learning (ML) has become a pervasive technology across various scientific domains. One area poised for significant transformation is Combinatorial Optimization (CO). While the three pillars of CO—modeling, search, and optimization—have traditionally relied on manual expert design, ML techniques are increasingly used to boost their accuracy and efficiency. This paper surveys the modeling component, which is often the most significant bottleneck in solving complex problems. By leveraging ML to learn constraints, objective functions, or entire problem structures from data, researchers can bridge the gap between raw data and actionable optimization models.
Introduction: The Modeling Bottleneck
In traditional Combinatorial Optimization, creating a model is an arduous, iterative process. It requires intense collaboration between domain experts, who understand the system's nuances, and optimization experts, who translate those nuances into mathematical logic. This manual approach is not only error-prone but often results in oversimplified models because real-world "rules" are frequently too complex to express through standard mathematical constraints.
Furthermore, modern systems like power grids, supply chains, and chemical processes generate massive amounts of data. Traditional CO lacks a native mechanism to "digest" this data. The core challenge addressed in this survey is how to use ML to extract optimization models directly from data or embed trained ML models into solvers to handle components that defy manual description.
Methodological Framework
The paper categorizes the integration of ML into modeling into three primary approaches:
1. Learning via Native Constraint Languages
These methods use ML—specifically "Constraint Acquisition"—to learn rules that a solver already understands, such as linear inequalities or global constraints. Systems like CONACQ and Model Seeker analyze examples of "good" and "bad" solutions to induce the underlying rules of the problem. This results in human-readable models that are compatible with standard solvers.
2. Empirical Model Learning (EML)
Rather than translating data into standard constraints, EML embeds a "black-box" ML model (such as a Neural Network or Decision Tree) directly into the optimization framework (CP, MILP, or SMT). The solver treats the ML model as a complex, non-linear constraint. For example, a MILP solver might use specialized encodings to reason through the layers of a ReLU-based Deep Neural Network to find inputs that satisfy specific safety properties.
3. Learning While Solving
This involves an active learning loop. As the solver identifies promising solutions, it evaluates them—either through simulation or human feedback—and uses that information to refine its internal model of the objective function or constraints in real-time. This is particularly useful for problems where the objective function is unknown or computationally expensive to evaluate.
Key Insights and Challenges
The "Optimizer Bias" Trap
A crucial finding in the intersection of ML and CO is the risk of optimizer bias. If an ML model is used as an objective function, the optimizer will naturally gravitate toward the model's errors. If the ML model slightly underestimates the cost of a suboptimal solution, the optimizer will "exploit" that inaccuracy, leading to solutions that appear optimal on paper but fail in real-world application.
The Trade-off: Native vs. Embedded
There is a fundamental trade-off between "Native" learning and "Embedded" models. Native learning produces human-readable rules but is limited in its expressive power. Conversely, embedded models (like Deep Neural Networks) are highly accurate and expressive but are computationally expensive for solvers to process, requiring advanced "bound tightening" techniques to prune the search space effectively.
End-to-End Learning
The survey highlights a shift toward training ML models specifically for the task of being optimized. Rather than training for general accuracy (Maximum Likelihood), researchers are developing models that are structurally optimized to be handled by CO solvers.
Landmark Results and Applications
While primarily a qualitative synthesis, the survey highlights several quantitative milestones:
- Verification of Deep Networks: Specialized SMT solvers (like Reluplex) have successfully verified safety properties of unmanned aircraft control systems by treating the neural network as a combinatorial model.
- Efficiency Gains: Active learning approaches like QUACQ (Quick Acquisition) have demonstrated the ability to converge on correct problem models using significantly fewer examples than passive learning methods.
- Hybrid Success: Empirical Model Learning has proven successful in industrial settings where the "system" (e.g., a chemical process) is a black box, but the "decisions" (e.g., scheduling) remain combinatorial.
Future Directions
The field faces several open challenges, most notably the Accuracy-Complexity Trade-off. As ML models become deeper and more accurate, they become harder for solvers to digest. Future research must also address Uncertainty; most current methods treat ML predictions as absolute truth, whereas future solvers should incorporate the variance or confidence intervals of the ML model into the decision-making process. Finally, the authors call for Standardization across the CP, MILP, and SAT communities to create a unified toolbox for ML-boosted modeling.
Summary updated