Chapters fro mWilliams

Question 1

Two purposes for Integer variables

Answer 1

Integer quantities and decision variables

Question 2

Elaborate on indicator variables

Answer 2

Indicator variables are those that rperesent a certain state. We can use them to see if a state is achieved, and then use the indicator variable further to represent scenarios where this state applies.

An indicator variable is typically linked to some other variable (it must be).

For instance, we can have the condition:

x > 0 –> y=1

To model this, we can treat its other form:

not(y=1) –> not (x > 0)

which gives:

y = 0 –> x <= 0

x <= y will enforce this, but to make sure that x > 0 –> y=1, we need the big M as well
x <= My

The important thing to understand here is that this constraint does not enforce that y is smaller than or equal to x, i.e. x = 0 –> y=0

This is typically a condition we enforce from the objective function, by adding a penality on y.

however, we can enforce it (to a degree) as constraint.

x = 0 –> y = 0

not (y=0) –> not(x=0)
y=1 –> x > 0

If x is integer, we can have:
x >= y, or y<=x.
So, we’d get:
x <= My
y <= x

However, if x is continuous, this does not work.
We actually need a small m:

my <= x

Now, if y=1, x must be larger than or equal to m. However, this is not as elegant as we’d hope, but it can be enough for small values of m.

This is typically a good solution for cases where m represent a certain threshold of a value that is considered as “on” or “active” or “off”.
For instance, if we want an indicator variable for whether or not the heart rate is “active” or not, we can set the pulse level threshold to 100, and this gives m=100.
100y <= x
We also need the other constraint:
x <= My

We can check these:
y=0: x = 0
y=1: x >= 100
x = 2: y=1

EXTREMELY IMPORTANT:
The check above seems counter intuitive because x=2 force y=1, which is not exactly what we want. However, this will then activate the other constraint, which makes x>=100. this gives the model a choice between setting x>=100, or equal to 0.

Question 3

when do we consider adding constraitns that enforce the logical structure of :

y = 1 –> x>0

Answer 3

This is the one that cannot be solved with absolute precision.

We need this in cases where the problem description require the “if-then” relationship, but the objective function does not add a penality on the matter.

Basically, we never want to allow the model to take the state of y=1 UNLESS the x-variable is greater than 0 (or small m).
This condition is not satisfeid by
x <= My, because this will only enforce that y=0 if x is greater than 0.

Question 4

What values of big M can be chosen?

Answer 4

any, as long as the value does not restrict the specific variable’s value range at all.

Question 5

elaborate on showing whether an inequality holds or not

Answer 5

We want to have an indicator variable that represent a state. the state is whether the constraint is included or not in the considerations of the model.

The model has a choice: it can include the constraint, or it can choose not to.
Tyupically, the decision of not including a constraint has implications, and we want to capture these implications. This is why we need the indicator vairable.

We say:

y=1 –> ∑aj xj <= b

same as:

∑aj xj > b –> y=0

We can represent it like this:

∑aj xj + yM <= M + b
if y=1: ∑ajxj <= b
if y=0: ∑ajxj <= M+b (notihng is imposed)

We can structure it differnetly:

∑ajxj <= b + M(1-y)

Question 6

elaborate on enforcing:

∑ajxj <= b –> y=1

Answer 6

Same as:

y=0 –> ∑ajxj > b

same type of logical structure as earlier. Cannot be solved to perfection.

We rewrite the constraint:

∑ajxj > b now is written as: ∑ajxj >= b + epsilon

The interpretation is that epsilon value decides when the condition is broken.

If all coefficients and variables are integers, epsilon can be sat to 1.

Anyways, now we have the logical structure:

y=0 –> ∑ajxj -b - epsilon >= +

or alternatively:

y=0 –> -∑ajxj + b + epsilon <= 0

There is more bullshit here

Question 7

§