Solving Congested Facility Location by Branch-and-Cut

Session : SS1-1 / SS1 : Challenging Mixed-Integer Problems in Network Optimization
Mercredi 10 février 15:00 - 16:00 Salle : CI2-06
Matteo Fischetti, Ivana Ljubic et Markus Sinnl

Congested Facility Location (CFL) is an extension of the Capacitated (or p-median) Facility Location problem in which higher load at facilities imposes longer waiting times. The underlying diseconomies of scales are therefore expressed through convex cost functions depending on the facility load. We propose to solve CFL using generalized Benders cuts embedded in a branch-and-cut framework. Prior to that, we consider a perspective reformulation of its standard MINLP model. This reformulation greatly improves the quality of lower bounds of the underlying continuous relaxation. We finally derive generalized Benders cuts by projecting out allocation variables from the perspective reformulation. We will provide details of a simplified practical implementation of generalized Benders cuts. Computational results will be presented at the conference.

Mots clés :