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.

 

Advertisements

One thought on “Prioritization Cuts

  1. This is a very cool model. I especially like the IP formulation of a partition. Since it is somehow related to the idea of “cuts,” I’d like to recap the difference between two types of “on-the-fly” constraint generation: lazy constraints and user cuts.

    When a model has too many constraints to add all at once, it is often easier to begin with a subset of the constraints and jump right into the branch and bound tree. At an integer feasible node, we can check if the solution is feasible for the actual model we want to solve, or just feasible for the relaxed version. In the case of the latter, we can add lazy constraints to cut off this integer solution. The relaxed model is not valid without these lazy constraints.

    By contrast, user cuts hack away at the feasible space of the LP relaxation. They don’t remove any of the integer feasible points, and we can add them throughout the optimization process.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s