Given a set of facilities and a set of customers, discrete location problems aim to open a subset of facilities and assign each customer to an open facility so that a given cost is optimized. This class of problems has a wide range of applications and has been studied extensively. We discuss different formulations of some of these problems by Mixed Integer Linear Programming (MILP) and point out characteristics of these formulations, namely the size of the formulation and the quality of its linear programming relaxation bound. Our goal is to illustrate how the choice of formulation can affect the running time required to compute an optimal solution. 

Retour page d'accueil du séminaire