Abstract
Combinatorial optimization problems, such as the Capacitated Facility Location Problem (CFLP), are computationally demanding and frequently subject to parameter disruptions in real-world applications. This paper proposes a hybrid machine learning (ML) and operations research (OR) framework to accelerate re-optimization. By predicting a scalar bound on the proportion of a known reference optimal solution that remains valid, and injecting this prediction as a linear constraint into a Mixed Integer Programming (MIP) solver, the method achieves significant speedups with a negligible average optimality gap of 0.03%.
Introduction
In logistics and supply chain management, decisions such as warehouse placement are modeled as NP-hard combinatorial problems. While an optimal configuration may be found for a "normal" state, real-world disruptions—such as sudden capacity drops—often necessitate re-solving the model. Standard MIP solvers may be too slow for the real-time response required in these scenarios. This research explores whether historical or simulated data can be used to learn how much of a previous optimal solution remains applicable, providing a data-driven "head start" for exact solvers.
Proposed Methodology
Rather than attempting to predict the exact new solution, which is often brittle in high-dimensional spaces, the authors predict a learned bound on the solution.
The Two-Stage ML Pipeline
To address the inherent data imbalance where minor disruptions often result in no change to the optimal configuration, a two-stage architecture is employed:
- Binary Classifier: Predicts whether the entire reference configuration should remain open (i.e., $\gamma = 1$).
- Regressor: If a change is predicted, this model estimates the proportion ($\gamma \in [0, 1)$) of originally open facilities that should be maintained.
Integration with MIP Solvers
The predicted proportion $\hat{\gamma}$ is translated into a simple linear cardinality constraint: $$\sum_{r \in R_{ref}} y_r \ge \hat{\gamma} N_{ref}$$ This constraint restricts the solver's search space to a neighborhood of the reference solution, allowing it to converge on high-quality solutions much faster.
Experimental Setup and Datasets
The approach was evaluated using standard CFLP instances. Three reference problems (A, B, and C) were selected, each with 100 potential facilities. For each reference, 10,000 perturbed instances were generated by applying Gaussian noise to facility capacities. These were solved offline to provide ground-truth optimal solutions for training. Evaluation was conducted on 50 unseen instances per reference problem.
Key Insights
- Scalar vs. Vector Prediction: Predicting a scalar bound (how many facilities to keep) is a significantly more robust task than predicting exactly which facilities to open. This approach guides the solver without over-constraining it.
- ML-OR Synergy: The framework treats ML and OR as complementary. ML provides a heuristic bound based on patterns in data, while the MIP solver handles the complex feasibility constraints and final optimization.
- Handling Robustness: The distribution of optimal solutions under perturbation shows that many instances require no change to the facility configuration. The two-stage architecture successfully filters these "no change" scenarios, improving the accuracy of the subsequent regression.
Results and Discussion
- Solver Acceleration: The ML-constrained model consistently outperformed standard formulations under tight time budgets (5 to 120 seconds), finding significantly better objective values.
- Minimal Optimality Loss: When allowed to run for one hour, the ML-bounded solutions were, on average, only 0.03% worse than the true optimum, demonstrating that the learned constraints rarely cut off the optimal region.
- Model Performance: Extremely Randomized Trees (Extra Trees) proved superior to Neural Networks and other baselines for both classification (0.75–0.86 accuracy) and regression tasks.
Conclusion
This work demonstrates that learning simple cardinality bounds can drastically reduce the time required to solve disrupted combinatorial problems. While there is a risk of "negative transfer" if predictions are highly inaccurate, the empirical results show that the bias introduced is negligible compared to the massive gains in solver efficiency. Future research will focus on extending this framework to other problem classes and designing more complex learned constraints.
Summary updated