Learning to Handle Parameter Perturbations in Combinatorial Optimization: an Application to Facility Location

Andrea Lodi, Luca Mossina, Emmanuel Rachelson

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:

  1. Binary Classifier: Predicts whether the entire reference configuration should remain open (i.e., $\gamma = 1$).
  2. 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.

The two-stage decision process and algorithm for applying learned bounds to new problem instances.

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.
Distribution of the number of facilities kept open across different reference instances, illustrating the data imbalance and the 'no change' scenario.

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

BibTeX
@article{lodi2020learning,
  author = {Andrea Lodi and Luca Mossina and Emmanuel Rachelson},
  title = {{Learning to Handle Parameter Perturbations in Combinatorial Optimization: an Application to Facility Location}},
  journal = {EURO J. Transp. Logist.},
  year = {2020},
  doi = {10.1016/j.ejtl.2020.100023},
}
Figure