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

Laureano F. Escudero (), María Araceli Garín (), Celeste Pizarro () and Aitziber Unzueta ()
Additional contact information
Laureano F. Escudero: Universidad Rey Juan Carlos
María Araceli Garín: Universidad del País Vasco, UPV/EHU
Celeste Pizarro: Universidad Rey Juan Carlos
Aitziber Unzueta: Universidad del País Vasco, UPV/EHU

Computational Optimization and Applications, 2018, vol. 70, issue 3, No 9, 865-888

Abstract: Abstract 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.

Keywords: Location-assignment; Multi-period stochastic 0–1 optimization; Scenario cluster Lagrangean problem; (Dual) Lagrange multipliers updating; Partial linear relaxation; Lazy (primal) heuristic (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-018-9995-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:70:y:2018:i:3:d:10.1007_s10589-018-9995-0

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-018-9995-0

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().