Learning to handle parameter perturbations in Combinatorial Optimization: An application to facility location

We present an approach to couple the resolution of Combinatorial Optimization problems with methods fromMachine Learning. Specifically, our study is framed in the context where a reference discrete optimizationproblem is given and there exist data for many variations of such reference problem (historical or simulated)along with their optimal solution. Those variations can be originated by disruption but this is not necessarily thecase. We study how one can exploit these to make predictions about an unseen new variation of the referenceinstance.The methodology is composed by two steps. We demonstrate how a classifier can be built from these data todetermine whether the solution to the reference problem still applies to a perturbed instance. In case the referencesolution is only partially applicable, we build a regressor indicating the magnitude of the expected change, andconversely how much of it can be kept for the perturbed instance. This insight, derived froma prioriinformation,is expressed via an additional constraint in the original mathematical programming formulation.We present the methodology through an application to the classical facility location problem and we provide anempirical evaluation and discuss the benefits, drawbacks and perspectives of such an approach.Although it cannot be used in a black-box manner, i.e., it has to be adapted to the specific application at hand,we believe that the approach developed here is general and explores a new perspective on the exploitation of pastexperience in Combinatorial Optimization