I recently read a paper entitled “Prioritization via Stochastic Optimization” (Koç and Morton, 2014), which was a timely read based on what we’ve been discussing in class lately. [1] The purpose of the paper is to present a new approach to solving resource-constrained activity-selection problems (RCASPs) using stochastic optimization and activity prioritization. The example application given by the authors is for the p-median model, a model with which we’re all familiar by this point. (As a quick recap, the idea of the p-median model is that there exists a set of customers located at various points and a certain maximum number p of facilities that can be built to service the customers. The objective is to minimize the total Euclidean distance any customer has to travel to reach a facility.) Formally, the p-median model can be written

$\min_{x,y} \sum_{j\in J}\sum_{i\in I} d_{ij}y_{ij}\\ \text{s.t.} \phantom{XX} \sum_{i \in I}x_i \leq k\\ \phantom{XXXX} x_i \geq y_{ij}\phantom{XX} i \in I, j \in J\\ \phantom{XXXX} \sum_{i \in I} y_{ij} = 1\phantom{XX} j \in J\\ \phantom{XXXX} x_i \in \{0,1\}\phantom{XX} i \in I\\ \phantom{XXXX} y_{ij} \in \{0,1\}\phantom{XX} i \in I, j \in J$

When everything is deterministic, this model is relatively straightforward. Problems occur, however, when the maximum number of facilities is uncertain (which could be the result of uncertainty in the facility-building budget certain), but the decisions about where to place the facilities must be made before the uncertainty is realized. The figure below depicts optimal facility placement when the maximum number of facilities is known to be 4.

Now, we add uncertainty. If either one or two facilities could be built with equal probability, we get the first figure below. If up to three facilities or up to four facilities could be built with equal probabilities, we get the second and third figures, respectively.

We’ll formalize this model in a moment, but first I want to explicitly outline the series of events that occur in this prioritized model. First, a prioritized list of activities (facility locations) is selected without knowing the actual budget. Next, the uncertainty is realized .Finally, we make additional decisions (which facility covers each customer) depending on which scenario is encountered. Thus, perhaps the most “interesting” part of this problem is how to prioritize the activities. A priority list is a many-to-one assignment of activities to priority levels. We have two requirements for a priority list:

1. A lower priority activity cannot be selected before a higher priority one in any scenario.
2. Either all activities on priority level $t$ are selected or none are.

The first-stage problem, then, corresponds to creating a priority list. Suppose $F^\omega(\mathscr{L})$ corresponds to the optimal objective value for scenario $\omega \in \Omega$. We write the first-stage problem as

$\min_{\mathscr{L}} \sum_{\omega \in \Omega}q^\omega F^\omega(\mathscr{L})\\ \text{s.t.} \phantom{XX} \mathscr{L} = [\mathscr{L}_1,\dotsm,\mathscr{L}_L]\\ \phantom{XXXX}\mathscr{L}_t \subseteq I \phantom{XX} t = 1,\dotsm,L\\ \phantom{XXXX}\mathscr{L}_t \neq \emptyset\phantom{XX} t = 1,\dotsm,L\\ \phantom{XXXX}\mathscr{L}_t \cap \mathscr{L}_{t'}= \emptyset \phantom{XX} t \neq t', t,t' = 1,\dotsm,L\\ \phantom{XXXX} \bigcup_{t=1,\dotsm,L} \mathscr{L}_t = I$

Essentially, these constraints require the priority list $\mathscr{L} = [\mathscr{L}_1,\dotsm,\mathscr{L}_L]$ to be a list of subsets of the activities such that at least one activity is found in a given priority level, no activity is found in multiple priority levels, and taken together the whole list covers all the possible activities.

The second-stage problem is

$\min_{x,y} \sum_{\omega \in \Omega}q^\omega\sum_{j\in J}\sum_{i\in I} d_{ij}y_{ij}^\omega\\ \text{s.t.} \phantom{XX} \sum_{i \in I}x^\omega_i \leq k^\omega\\ \phantom{XXXX} x_i^\omega \geq y_{ij}^\omega\phantom{XX} i \in I, j \in J\\ \phantom{XXXX} \sum_{i \in I} y_{ij}^\omega = 1\phantom{XX} j \in J\\ \phantom{XXXX} x_i^\omega \in \{0,1\}\phantom{XX} i \in I\\ \phantom{XXXX} y_{ij}^\omega \in \{0,1\}\phantom{XX} i \in I, j \in J\\ \phantom{XXXX} x_i^\omega \geq x_{i'}^\omega \phantom{XX} i \in \mathscr{L}_{t}, i' \in\mathscr{L}_{t'}, t < t', t,t' = 1,\dotsm,L\\ \phantom{XXXX} x_i^\omega = x_{i'}^\omega \phantom{XX} i,i' \in\mathscr{L}_t, t = 1,\dotsm,L$

where the second-to-last constraint enforces the requirement that all higher-priority activities are selected before lower priority ones and the final constraint requires either all activities or no activities on a given priority level to be selected. The rest of the constraints are the same as in the original p-median model, but the variables and parameters are scenario-dependent. Of course, the first-stage model is not a standard integer program, so we would like to find a formulation for this problem that can be solved by standard stochastic optimization techniques. Toward that end, we create additional decision variables $s_{ii'}$, which are 1 if activity i has no lower priority than activity i’ and 0 otherwise. The corresponding two-stage stochastic integer model is

$\min_{x,y,s} \sum_{\omega \in \Omega}q^\omega\sum_{j\in J}\sum_{i\in I} d_{ij}y_{ij}^\omega\\ \text{s.t.} \phantom{XX} \sum_{i \in I}x^\omega_i \leq k^\omega\\ \phantom{XXXX} s_{ii'} + s_{i'i} \geq 1 \phantom{XX} i < i', i,i' \in I\\ \phantom{XXXX} s_{ii'} \in \{0,1\} \phantom{XX} i \neq i', i,i' \in I\\ \phantom{XXXX} x_i^\omega \geq x_{i'}^\omega + s_{ii'} - 1 \phantom{XX} i \neq i', i,i' \in I, \omega \in \Omega\\ \phantom{XXXX} x_i^\omega \geq y_{ij}^\omega\phantom{XX} i \in I, j \in J\\ \phantom{XXXX} \sum_{i \in I} y_{ij}^\omega = 1\phantom{XX} j \in J\\ \phantom{XXXX} x_i^\omega \in \{0,1\}\phantom{XX} i \in I\\ \phantom{XXXX} y_{ij}^\omega \in \{0,1\}\phantom{XX} i \in I, j \in J$

The first constraint ensures either activities i and i’ have the same priority level or one is higher than the other. It’s also relatively straightforward to check that the third constraint becomes the final two constraints in the previous model depending on the values of the pair $s_{ii'}$ and$s_{i'i}$.

Now, the activity-prioritization model isn’t particularly easy to solve in general (in fact, it’s NP-hard), but it does allow for potential stochastic or structural interdependencies between activities, which is an improvement on historical ways of looking at activity portfolios where each activity is treated as an independent entity. For more details on alternative formulations and some valid inequalities, I’ll refer you to the paper. Thanks for reading!

[1] Koç, Ali, and David P. Morton. “Prioritization via stochastic optimization.”Management Science 61.3 (2014): 586-603.