Boosting Combinatorial Problem Modeling with Machine Learning

Michele Lombardi, Michela Milano

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

Abstract

In the past few years, the area of Machine Learning (ML) has witnessed tremendous advancements, becoming a pervasive technology in a wide range of applications. One area that can significantly benefit from the use of ML is Combinatorial Optimization. The three pillars of constraint satisfaction and optimization problem solving, i.e., modeling, search, and optimization, can exploit ML techniques to boost their accuracy, efficiency and effectiveness. In this survey we focus on the modeling component, whose effectiveness is crucial for solving the problem. The modeling activity has been traditionally shaped by optimization and domain experts, interacting to provide realistic results. Machine Learning techniques can tremendously ease the process, and exploit the available data to either create models or refine expert-designed ones. In this survey we cover approaches that have been recently proposed to enhance the modeling process by learning either single constraints, objective functions, or the whole model. We highlight common themes to multiple approaches and draw connections with related fields of research.
BibTeX
@inproceedings{lombardi2018boosting,
  author = {Michele Lombardi and Michela Milano},
  title = {{Boosting Combinatorial Problem Modeling with Machine Learning}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/772},
}
Figure