<  Back to the Polytechnique Montréal portal

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

Andrea Lodi, Luca Mossina, Emmanuel Rachelson

Article (2020)

Open Acess document in PolyPublie and at official publisher
[img]
Preview
Open Access to the full text of this document
Published Version
Terms of Use: Creative Commons Attribution Non-commercial No Derivatives
Download (1MB)
Show abstract
Hide abstract

Abstract

We present an approach to couple the resolution of Combinatorial Optimization problems with methods from Machine Learning. Specifically, our study is framed in the context where a reference discrete optimization problem 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 the case. We study how one can exploit these to make predictions about an unseen new variation of the reference instance.The methodology is composed by two steps. We demonstrate how a classifier can be built from these data to determine whether the solution to the reference problem still applies to a perturbed instance. In case the reference solution is only partially applicable, we build a regressor indicating the magnitude of the expected change, and conversely how much of it can be kept for the perturbed instance. This insight, derived from a priori information,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 an empirical 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 past experience in Combinatorial Optimization.

Uncontrolled Keywords

Mathematical programming, Machine learning, Recurrent problems

Subjects: 2950 Applied mathematics > 2959 Mathematics of communications
Department: Department of Mathematics and Industrial Engineering
Research Center: Other
Funders: CERC in Data Science for Real-Time Decision-Making, ISAE-SUPAERO foundation
PolyPublie URL: https://publications.polymtl.ca/9272/
Journal Title: EURO Journal on Transportation and Logistics (vol. 9, no. 4)
Publisher: Elsevier
DOI: 10.1016/j.ejtl.2020.100023
Official URL: https://doi.org/10.1016/j.ejtl.2020.100023
Date Deposited: 05 Apr 2022 14:34
Last Modified: 11 Nov 2022 13:53
Cite in APA 7: Lodi, A., Mossina, L., & Rachelson, E. (2020). Learning to handle parameter perturbations in Combinatorial Optimization : an application to facility location. EURO Journal on Transportation and Logistics, 9(4), 13 pages. https://doi.org/10.1016/j.ejtl.2020.100023

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Dimensions

Repository Staff Only

View Item View Item