Boosting Combinatorial Problem Modeling with Machine Learning

Michele Lombardi, Michela Milano

Abstract

Traditionally, combinatorial optimization (CO) relies on manual modeling by domain experts, a process prone to bottlenecks and inaccuracies. This paper surveys the emerging synergy between Machine Learning (ML) and CO, focusing on how ML can automate and enhance the modeling of complex problems. By learning constraints and objective functions directly from data, researchers are transitioning toward hybrid systems that are more efficient, adaptive, and capable of handling real-world uncertainty. This survey categorizes current methodologies, explores the trade-offs between model accuracy and computational solvability, and highlights the reciprocal relationship where CO is used to verify ML models.

Introduction

Building a combinatorial optimization model—such as scheduling a factory floor or routing a logistics fleet—has historically required a "knowledge engineering" bottleneck. Domain experts must collaborate with optimization specialists to translate nuanced real-world rules into rigid mathematical constraints and objective functions. This manual process is often flawed: rules may be too complex to formalize, experts may overlook edge cases, and static models fail to adapt as underlying systems evolve.

Recent research addresses these challenges by treating modeling as an inductive process. Rather than relying solely on human intuition, Machine Learning (ML) is used to learn the "rules of the game" from observations. This shift allows for more robust modeling that can capture complex system behaviors that are difficult to express through traditional mathematical programming.

Methodologies in ML-Enhanced Modeling

The integration of ML into CO modeling generally follows three distinct approaches:

1. Learning via Native Constraint Languages

Systems such as CONACQ and Model Seeker aim to "discover" constraints that already exist within a solver's library (e.g., "all-different" constraints or linear inequalities). By analyzing examples of valid and invalid solutions, these systems can automatically induce the underlying structure of a problem without manual specification.

2. Empirical Model Learning (EML)

Instead of translating a physical or logical rule into a formula, EML embeds a pre-trained ML model—such as a Neural Network or Decision Tree—directly inside the optimization model. The solver treats the ML model as a complex constraint. This is achieved either by writing custom "propagators" for the solver or by "linearizing" the ML model into a format compatible with Mixed-Integer Linear Programming (MILP) solvers.

3. Learning while Solving

This approach involves active learning or "preference elicitation." As the solver proposes solutions, a user or simulator provides feedback. The model then updates its internal understanding of the objective function or constraints on the fly, refining the search space based on real-time interaction.

Key Insights and Trade-offs

The Accuracy vs. Optimization Trade-off

A critical challenge in hybrid modeling is the balance between model fidelity and computational overhead. While a deep neural network might offer high predictive accuracy, its complexity can make the resulting optimization problem intractable. Finding the "sweet spot"—a model accurate enough to be useful but simple enough to be solved efficiently—is a central theme in current research.

Optimizer Bias

A fascinating phenomenon identified in the literature is "optimizer bias." If an ML model contains even minor errors, an optimization solver will likely exploit them. For instance, if a model slightly underestimates the cost of a suboptimal solution, the solver may identify that point as a global optimum, leading to poor real-world performance despite high theoretical accuracy.

Active vs. Passive Learning

Passive learning relies on historical data, which often lacks information regarding the "boundaries" of the feasible region. Active learning, where the solver queries specific data points, is more efficient at mapping these boundaries but requires a human-in-the-loop or a high-fidelity simulator.

Applications and Results

While this survey focuses on qualitative progress, it highlights several key application areas and benchmarks:

  • HVAC Control: Using Deep Neural Networks to model state transitions in building climate control systems.
  • Thermal-aware Workload Assignment: Learning how computational tasks impact hardware temperature to optimize scheduling.
  • Algorithm Portfolios: Systems like SATzilla use ML to predict which optimization algorithm will perform best for a specific problem instance, significantly reducing total computation time.
  • ML Verification: The relationship is reciprocal; CO is increasingly used to verify ML models. Solvers like Reluplex have demonstrated the ability to formally prove properties of neural networks with thousands of nodes, ensuring safety in critical applications like autonomous driving.

Limitations and Future Directions

Despite significant progress, several hurdles remain:

  • Data Requirements: Deep learning models require massive datasets, which are often unavailable in specialized industrial contexts.
  • Handling Uncertainty: Most current CO models are deterministic. Integrating the probabilistic nature of ML (e.g., "I am 80% sure this constraint holds") into hard optimization solvers remains a major open challenge.
  • End-to-End Learning: Future research is moving toward "task-based learning," where ML models are trained specifically to produce high-quality optimization results rather than just high prediction accuracy. This requires the development of techniques to differentiate through the optimization process itself.

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