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