Stochastic programming

Question 1

What is the simplest way of scenario representation?

Answer 1

Using fixed states, like up-state and down-state around a mean. For instance, 20% up and down.

Question 2

Given some scenarios, what are we interested in?

Answer 2

Whether the optimal solution will change or not when we have different scenarios.

Question 3

elaborate on scenario index

Answer 3

if we have multiple s enarios, we can dinstinguish between the variables in them by adding scenario indices. Each variable would get an additional index that represent the value of the variable in optimal solution in the specific scenario.

Very useful for comparing outcomes

Question 4

if we want to maximize long term profits, what are we?

Answer 4

Risk neutral. We go for the option with the largest expected return

Question 5

elaborate on extensive form

Answer 5

extensive form refer to modelling the problem in a way that explicitly describes the second stage variables for all scenarios.

Second stage refer to outcomes that are uncertain. For instance, the crop yields. We dont know the crop yield at the point in time where we make the decision. Therefore it is second stage.

however, we do know some tohter things, like the cost of planting and all that. Therefore, this is first-stage.

Extensive form looks like this:

min z = 150x1 + 230x2 + 260x2 - 1/3 (170w11 - 238y11 + 150w21 - 210y21 )…

We are modelling in the uncertain events.

IMPORTANT: The extensive form includes the scenario indices.

Question 6

What is the important outcome of the illustrateive example?

Answer 6

It is impossible/extremely difficult to find a solution that fits all scenarios when there is uncertainty involved.

In the farmer example, we would never sell Beet at the reduced price, but if yields are better than expected, we end up doing this. Likeqwise, we always want to fill the Beet quota. This is essentially what we loose from not having a perfect forecast.

Question 7

what is the loss i nvalue as a result of uncertainyy?

Answer 7

We use the term value of perfect informaiton, which is the difference between knowing the outcomes and not doing so and therefore choosing the options that maximize expected value.

Question 8

what is the expected value solution?

Answer 8

assuming a mean value, and using those results. Different from the separation fo stages

Question 9

elaborate on VSS

Answer 9

Value of stochasitc solution.

THe stochastic solution is hte one that consider scenarios (two stages). The value of stochastic soltion is defined as the differnece between the expected value solution adn the stochastic value solution.

Question 10

elaborate on the stages

Answer 10

the stages refer to uncertainty.

The first stage is about making decisions under uncertainty based on our forecasting. Will likely be a little wrong, but is an educated guess.

The second stage decisions represent our corrective decisions. When we receive the information in the future, what are we actually doing

We say that the first stage decisions are represented by a vector x, and then a vector e-dfucked up gives us full realizaiton. Then we make a corrective decisions which we denote y. BOld to idnicate random variable.

Question 11

elaborate on the general two-stage model formulation

Answer 11

min cx + E_eQ(x, e)
s.t. Ax=b
x>=0

So the only differnece if the expected value of the fucked up e is the expected value with respect to the information vector fcked up e.

Q(x,e) = min{qy | Wy = h-Tx, y>=0}

W is the fixed and known matrix.

the fucked up e (in the farmer example) is simply “s”.
The fucked up e is simply a placeholder for other variables.

So, only the T matrix is random.

What is the T-matrix?
The T matrix is the random component. In the farmer case, it represent the yield per acre of crop.
The T-matrix consist of values t_i(s) to represent the yield of crop i under scenario s.
Therefore, in this example, the T-matrix is a column only, but we of course have various scenarios and crop types. Therefore T matrix becomes as 2D matrix.

Question 12

In the farmer example, what is the uncertainty?

Answer 12

Only the yield.

if we are given the yield, we can compute the ideal decisions.

Question 13

elaborate on the general formulation of a stochastic probelm

Answer 13

We need the regular part and the stochastic part. Theregular part refer to the first stage deciisons.

min cx + E_e(Q(x,e))
s.t. Ax=b
x>=0

So basically, we minimize the cost when considering the decisions we have to make now, and what we expect in the future.

To find the expected value of the second stage fuckery, we look into what the Q function actually is. we know that the expected value is just a function that takes perhaps the Q function for various scenarios along with the probability of each scenario, and return the expected value.

The Q function is defined as:

Q(x,e) =min{qy | Wy = h-Tx, y>=0}

The Q function represent a specific outcome/scenario, where we only consider the second stage variables.

The two stage formulaiton is called the implicit form, and is commonly condensed down to:

min cx + L(x)
s.t.
Ax=b
x>=0

Question 14

what do we mean by nonanticipative

Answer 14

Nonanticipative refer to not being able to anticipate every possible outcome.

Question 15

in routing litterature, what is a “failure”?

Answer 15

Not meeting demand of a customer. you have to drive to the customer, fail to serve, drive back to depot, drive back to customer, and serve again. Brutal scenario

Question 16

what are recourse problems

Answer 16

recourse problems are problems that have soem deicsions that can made re-made later. In other words, after uncertinaty is removed

Question 17

elaborate on first stage vs second stage

Answer 17

First stage is with uncertainty. Decisions we need to take at this point in time are called first stage decisions. Typically represented by vector x.

Second stage is after the random experiment. Decisions at this point in time are referred to as second stage decisions. typically rperesented by vector y.

Question 18

Elaborate DEEPLY on the DEP and the two-stage model. Thsi is the important card

Answer 18

We solve a model that has the stage one decision variables, and these are set to values that are best for the overall expected solution that accounts for all scenarios. This means that these variables will most likely not be perfectly sat, because we dont know the actual future outcome and we will have to work with probabilities.
We also get a vast number of recourse variables from the second stage. We will get a set of such variables for each scenario we consider. Therefore, it is typical that the number of recourse variables will be a larger set than the number of first stage variables.

Here is an important part: We use the decision variables from the first stage to look at different scenarios in the second stage. If one of the first stage variables is that we have selected to plant say 5 acres of corn on our farm, we must use this number in the second stage. We pass this value through a transformation, q(w). w is the random event. Perhaps w is “good farming conditions” which produce a yield of say 200. if the farm conditions are shitty, we’d get yield of 50.

The function q(w) is directly tied between x and y, where x is the first stage variables and y is the second stage variables. We might as well change it to q(x, w) to highlight this. So, we have q(x,w)y in the objective function to represent the second stage. We also have the ∑probability…q(x,w)y to include the expectation here. y contains a list of scenario variables, and we would make it clearer by having it as: q(x,w)y_s.

Actually, nevermind the previous part. x is not included in the second stage part of the objective function. All costs associated with x is in its other part of the objective function. All the relaitionshups should be enforced through the constraints.

The general idea is that we set the various scenario variables to values based on what seems to improve the objective function the most in relation with its probability of the scenario event and the decision on first stage x’s. Of Course, using something like simplex or another tool, all of these variables are sat at once, so there is no actual “first we set the first stage variables, then we set the second stage” or something similar. The stages are only conceptual.

We minimize of maximize the objective function subject to constraints. We use the following general constraint line:
Ax=b
T(w)x+Wy(w) = h(w).

Here we basically have a set of constraints only applicable for the first stage. In the farmer example, this could be that the total number of acres we use cannot be larger than our farm capacity. This is not related to the second stage at all, strictly a structural constraint for the first stage.
However, the second stage constraints impact the decision we make on the first stage variables.
T(w)x performs a transformation on the variables that indicate a certain relationship. For instance, if the farming conditions are great, we could multiply the “x” with a constant that gives us crop yield per acre. T(good)=200, T(bad)=50, T(neutral)=100 or something like that.
This is then related to the W matrix, which is a fixed and known resource matrix that is used to transform the y-variables and relate to the crop yield (in this example). For instance, if we require a certain amount of crops for ourselves to feed cattle etc, we can represent one of the y-variables as a “amount of crop we need to buy”, and say that yieldacre + 1AmountTobuy >= requiredAmount. Since the yield is the uncertain event, we’d get one “AmountToBuy” variable per scenario.

it is important to understand that in this case with DEP, all variables are sat like normal LP or IP would do it. There is no “this happens firs,t then this happens”. The solver doesn’t care. The solver will only search in the feasible region using some kind of method, whether it is simplex or dual or IP branch and bound or cutting plane methods or whatever, and find the solution that gives the optimal objective function value.