# Prioritization Cuts

Since I’ll be presenting the paper “Prioritization via Stochastic Optimization,” by Koç and Morton, on Tuesay, I’d like to delve a little deeper into a section of the paper that I won’t be covering in my presentation: Prioritization Cuts.

First things first, I’d like to refer you to a previous blog post for a bit more background on activity prioritization and motivation for the problem.

Next, I’d like to briefly explain the idea of a “cut.” When solving an optimization model, it is at times impracticable to solve the full model to optimality due to time or computational memory limits. Thus, clever optimizers often find ways to “relax” the model, basically removing or loosening constraints that contribute to the model’s difficulty. A prime example of this is integer programming, where it is common to remove the integrality restriction, allowing continuous decision variables in the solution. Of course, more often than not the relaxed solution won’t be feasible to the original problem, so optimizers have to find a way to work back to a feasible solution. Cuts, as their name implies, are constraints that can be added iteratively or all at once to “cut off” infeasible solutions. Once all the cuts are added – and hopefully well before – the solver returns an optimal feasible solution to the original model.

Recall the full two-stage stochastic integer program for the general activity prioritization problem. Clearly, this has numerous integral variables, making solving the actual model difficult. Thus, we’d like to solve the linear relaxation (which is quite easy to do) and add cuts that help us get back to a feasible solution. As a recap, our 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$

We’ll start by going over some terminology that we’ll need to discuss the prioritization cuts.

Let

$Y^\omega = \{(x,y) : x \in [0,1]^{|I|}, A^\omega x \leq b^\omega, (x,y) \in C^\omega\}$

and

$X^\omega = \{x : \exists y s.t. (x,y) \in Y^\omega\}.$

Also, for $x \in X^\omega$, let

$h^\omega(x) \equiv c_x^\omega + \min_{\{y : (x,y) \in C^\omega\}} c_y^\omega y$.

Improving: A scenario $\omega$ is called improving if for any two vectors $x, \bar{x} \in X^\omega$ with $S(\bar{x}) \subseteq S(x)$, we have $h^\omega(x) \leq h^\omega(\bar{x})$. (Note $S(x)$ refers to the set of selected activities in solution vector x). Let $\Omega_V \subseteq \Omega$ be the set of improving scenarios.

Dominating scenario: For two scenarios $\omega$ and $\hat{\omega} \in \Omega$, we say $\omega$ dominates $\hat{\omega}$ if $x \in X^{\hat{\omega}} \implies x \in X^{\omega}$. Let $\Omega_D$ be the set of dominating scenario pairs.

Dominating activity: Let $x \in [0,1]^{|I|}$. Construct a new vector $x_{(i,j)}$ such that every element is identical to $x$ except the ith element is set to 1 and its jth element is set to 0. We will say activity i dominates activity j if $x \in X^{\omega}$ with $x_i = 0$ and $x_{j} = 1 \implies x_{(i,j)} \in X^{\omega}$ and $h^{\omega}(x_{(i,j)}) \leq h^{\omega}(x)$ for all scenarios. Let $I_D$ be the set of dominating activity pairs.

Finally, we are ready to propose some cuts for the activity prioritization model.

Proposition 1: There exists an optimal solution to the activity-prioritization problem such that the optimal activity selection vector $\bar{x}$ satisfies $\bar{x}_i^{\omega} \geq \bar{x}_i^{\hat{\omega}}$ for every $i \in I$ and for all $(\omega,\hat{\omega}) \in \Omega_D$ such that $\omega \in \Omega_V$.

Proposition 2: There exists an optimal solution to the activity-prioritization problem such that the optimal activity selection vector $\bar{x}$ satisfies $\bar{x}_i^{\omega} \geq \bar{x}_{j}^{\omega}$ for every $\omega \in \Omega$ and for all $(i,j) \in I _D$..

An important characteristic of these sets of cuts is that they are what optimizers call “super-valid” inequalities, as opposed to plain-old valid inequalities. The reason for this is these new constraints cut off not only feasible points, but sometimes optimal points as well. What super-valid inequalities guarantee, however, is that there remains at least one optimal solution that is not cut off by these additional constraints.

That’s about it for prioritization cuts. For a formal proof of why these cuts work, I’ll refer you to the paper. Thanks for reading!

~AGS

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