On the interplay between data and decisions in discrete location problems

The capacitated facility location problem (CFLP) is a core problem in location science. Several exact and heuristic solution approaches and various modeling extensions integrating time, uncertainty, or further supply chain network design decisions exist. However, the average-case-based analysis underlying the majority of works in this field leaves several questions unaddressed: Why does the runtime of state-of-the-art MIP solvers differ drastically between seemingly similar problem instances? Why does an explicit consideration of the temporal development of the parameters in a multi-period model lead to a significant improvement of the objective value in some instances and is negligible in others? When does moving to a more complex model result in different decisions and when are the same decisions merely evaluated differently? None of these questions are easy to address, yet one thing is clear: when the same model and algorithm are used, the reason for the observable differences must lie in the problem data. The present work offers new insights into the relationship between data and the optimal decisions of CFLP instances.

A new methodological approach that characterizes instances based on their decisions in well-performing, that is optimal and near-optimal solutions is presented. ... mehr
It is shown that the combination of spatial patterns, the capacity-to-demand, and fixed-costs-to-profit ratio result in the facilities operating in the optimal solution to individual instances interdepending to varying degrees. A newly proposed measure based on the decisions in well-performing solutions of an instance allows the quantification of the level of this interdependence. It gives rise to a classification of CFLP instances as either primarily composed of independent or primarily composed of interdependent facilities. This distinction allows the anticipation and explanation of the performance of different exact and heuristic solution algorithms.

It is demonstrated that facilities serving the same subset of customers interdepend more strongly, which induces an implied separation of the sets of candidates and customers into distinct regions. A pattern-based approach to retrieve these regions already from integer-infeasible solutions is introduced. It is shown that knowledge of the interdependence relationships and, more precisely, the implied regions opens up new opportunities for algorithm development. Computational experiments show that integrating it into the branch-variable selection step of CPLEX's branch-and-cut solver leads to a significant runtime reduction.

Moving to a more complex model increases the flexibility of a decision-maker but also comes at the cost of added complexity. Thus, it is important to understand the conditions under which a model extension results in an added value. Model extensions of the CFLP in the two most commonly found directions for location problems are analyzed: time and uncertainty. For the first, a multi-period CFLP with phase-in constraints is examined; for the latter, a two-stage stochastic program and an adjustable robust program of the CFLP are compared. A central question regards the quantification of the added value. For the multi-period CFLP, the value of the multi-period solution is used; for the uncertainty-aware formulations, novel measures to assess and compare the added value are presented.
For the multi-period model, it is shown that not the degree to which parameters change over the planning horizon but the degree to which the model extensions allow the reduction of relevant cost components of the objective value is decisive. Consequently, the mere fact that decisions are taken in a temporal context does not necessarily make time an important aspect to include in the model.
For uncertainty-aware models, the characterization of instances allows the anticipation of the level of flexibility with which location decisions can be adapted to hedge against uncertainty. When the implied patterns are rigid in the sense that few candidates clearly dominate, the added value of moving to a robust or stochastic approach diminishes as the more complex model proposes the same location decisions. Both results encourage further research on data-driven modeling.

This work presents novel methods to analyze solutions in the decision space. Insights are validated by experiments on several sets of benchmark instances from literature. Deriving and subsequently analyzing multi-sets of optimal and near-optimal solutions to these instances is possible only with the help of state-of-the-art potent MIP solvers and efficient data analytics tools. As such, this thesis demonstrates that recent advances in computing power not only allow addressing larger and more complex problems but also open up new perspectives on problems that have been studied for decades – like the CFLP.