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