pickups

Question 1

What kind of constraints are always shite to add as valid ineiqualiteis

Answer 1

those that can never be violated. We need to violate the LP solution for it to be effective.

If some inequality can never be violated, it will do noithing.

Question 2

elaborate on the reference row in sos

Answer 2

The reference row is the monotonic set of numbers that we associate with the variables.

Question 3

what is fractionality?

Answer 3

Fractionality is a quantity/size the is used to describe the “centre of gravity” in the current sets values. This means, to find the fractionality we need the monotonic reference row AND the current values of the variables.

Fractionality is given as:

∑ajxj / ∑xj

Question 4

elaborate on the entirety of the separation problem

Answer 4

CASE AND MOTIVATION:
For a given LP relaxation solution, we want to figure out if there exists a cover inequality we can use to cut away the LP solution and progress the search. We are in a cutting plane method, and this will make us progress the search.

We have 2 requirements:
1) The inequality must be based on a cover
2) The current LP solution must be affected by the cover inequality. If not, there is no point in adding it.

Mahtematically, these are described like this:

1)
∑aj [j in S] > b

2)
∑(1-xj^(LP)) [j in S] < 1

Notice how the second constraint require the set of variables to be so that the variables, which are allowed to be between 0 and 1, must be very close to 1. This ensure that cutting away one of them will make the solution be switched.

A better way of structuring this is:

min[S] {∑(1-xj^(LP)) [j in S] : ∑aj [j in S] > b}

In order to solve this, we introduce the variables zj, that are 1 if variable j is included in the cover set. 0 otherwise.

min alpha = ∑(1 - xj^(LP))zj [j in N]

s.t.
∑ajzj [j in N] > b
zj in {0,1}

since we know that alpha ideally is below 1, we have the following interpretation:
if alpha < 1: we have a valid inequality that will cut away the current LP optimal solution. ∑xj <= ∑zj - 1
if alpha >= 1, it doesnt affect the soluiton.

if alpha = 0, it means that the LP optimal solution was integer. It would cut away 1-alpha = 1.

Question 5

elaborate on sensitivity analysis in regards to objective function coefficients

Question 6

clearly state the definition of a minimal cover

Answer 6

A set of variables that has the sum ∑aj > b, but also have the property that the constraint is satisfied by removing any (only one) of the variables in the set.

Question 7

elaborate on lifting

Answer 7

lifting is a technique that makes an inequality (valid) stronger.

It utilize the concept of how choosing one variable to be 1 can sometimes represent a case where the other binary variables in the valid inequality can never be anything but 0. In such cases, we can lift the coefficient of this special variable to be the same as the inequality’s RHS.

For instance:
x1 + x2 + x3 + x4 <= 2
If we know that x1 has a constraint coefficient that will make it so that choosing x2 or x3 or x4 = 1 makes the constraint infeasible, we can do this:
2x1 + x2 +x3 + x4 <= 2
This just tightens the constraint.

Lifting is a relationship between a valid inequality and the constraint coefficients.

Question 8

elaborate on stochastic DP

Answer 8

There is now a stochastic element, which introduce some random variable.

A random variable has values that it can take, and each of these values are associated with a probability.
So, when we say that for instance the cost (profit) function now has a random variable included, it means that we need to account for the fact that the cost or profit of doing a certain action at some stage given a state, now depends on the outcome of the random variable as well as the state+action combination.

in the options example, the profit function was the profit of selling the option at some stage. This actually never included the random variable at this part.
c = St - 152, where 152 was the strike price.

In stochastic modelling, we need to be very clear about what the random variable is.
In the case of options, the random variable represented a per-stage price movement with fixed values and fixed distribution.
The entire transition function relied upon it.
S_(t+1) = S_t + RV_t

How about the recursion that we need for DP?
The recursion is defined as:
f_t(s_t) = min ∑ci(si, xi) [i=t, T]

This is then written as:

f_t(s_t) = min [c_t(s_t, x_t) + f_(t+1)(s_(t+1))]

To account for the random variable:

f_t(s_t) = min E_rv [c_t(s_t, x_t, rv_t) + f_(t+1)(T(s_t, x_t, rv_t))]

So basically, we say that we want the expected value maximization actions.
There is a random component in the cost function, and the same random component (random variable) is included in the transition function.

To make it easier, we change expected value with the sum multiplied by corresponding probabilities of the various scenarios.

f_t(s_t) = min ∑(i=1, s)pi [c_t(s_t, x_t, rv_t) + f(t+1)(Tt(s_t, x_t, rv_t))]
Split into two summations

f_t(s_t) = min ∑pi c_t(s_t, x_t, rv_t) + ∑pi f_(t+1)(T_t(s_t, x_t, rv_t))