On efficient matheuristic algorithms for multi-period stochastic facility location-assignment problems

In this work we present two matheuristic procedures to build good feasible solutions (frequently, the optimal one) by considering the solutions of relaxed problems of large-sized instances of the multi-period stochastic pure 0–1 location-assignment problem. The first procedure is an iterative one for Lagrange multipliers updating based on a scenario cluster Lagrangean decomposition for obtaining strong (lower, in case of minimization) bounds of the solution value. The second procedure is a sequential one that works with the relaxation of the integrality of subsets of variables for different levels of the problem, so that a chain of (lower, in case of minimization) bounds is generated from the LP relaxation up to the integer solution value. Additionally, and for both procedures, a lazy heuristic scheme, based on scenario clustering and on the solutions of the relaxed problems, is considered for obtaining a (hopefully good) feasible solution as an upper bound of the solution value of the full problem. Then, the same framework provides for the two procedures lower and upper bounds on the solution value. The performance is compared over a set of instances of the stochastic facility location-assignment problem. It is well known that the general static deterministic location problem is NP-hard and, so, it is the multi-period stochastic version. A broad computational experience is reported for 14 instances, up to 15 facilities, 75 customers, 6 periods, over 260 scenarios and over 420 nodes in the scenario tree, to assess the validity of proposals made in this work versus the full use of a state-of the-art IP optimizer.