Integer programming

Question 1

Difference between the fasible region of LP and IP problems?

Answer 1

LP has convex feasible region.

IP has non-convex feasible region

Question 2

Can we round off the LP relaxation to get solution, or soemthing good enough?

Answer 2

No, genenrelly not. Many cases have the LP relaxation extremely far away from the IP optimal solution.

Question 3

can we have non linear integer programming?

Answer 3

Yes, but this typically create extremely difficult problems to solve.

it is therefore common to approximate non linear functions using linear functions and apply integer variables as support

Question 4

Why do we need integers?

Answer 4

two reasons primiarily:
1) many sizes are naturally integers. For instance, quantities etc
2) Binary variables used for logical purposes to extend modelling abilities

Question 5

General rule for when we must use integers rather than continuous value and rounding off?

Answer 5

if the variable value is less than 10, we typically have to use integers

Question 6

elaborate on the usual suspects of what we can use integer variables for in terms of modelling

Answer 6

Yes no decisions

Modelling fixed costs

Description of non-convex areas

Approximation of non-linear functions (piece wiese)

Definition of logical restrictions

When only a discrete set of values are allowed (say 0,4,7,22).

Question 7

CASE

We consider a production machine that has a variable cost associated with each unit of production. However, starting up the machinery also cost cash. How can we model this?

Answer 7

This is a classic case of fixed cost problem.

We call the fixed cost “f”.

Logically, the fixed cost should be 0 if the nubmer of units is 0. If the number of units is greater than 0, the fixed cost should be applied in its entirety.

z = f + ca xa, if xa > 0
z = 0, if xa = 0

To express this, we introdice a binary variable, y. The interpretation of this variable is a yes/no decision “Start up the machinery”.

xa <= yM

the constant M must be chosen large enough.

Question 8

CASE

Suppose we have a problem where the feasible points are defined as lying in either area 1 or area 2 (or in both). The areas are defined as constraints. For instance, area 1:

x2 <= 3
x1 + x2 <= 4
x1, x2 >= 0

area 2:

-x1 + x2 <= 0
3x1 - x2 <= 8
x1, x2 >= 0

Express the feasible area mathematically

Answer 8

First off, we can add all constraints to create a new feasible region, because this would be an AND case. We have OR.

So, we introduce 2 new binary variables.

y1: 1 if the point is in area 1, 0 otherwise
y2: 1 if the point is in area 2, 0 otherwise

So, the general idea is that either the constraints of the first area must apply, or the constraints of the second area must apply. Both can apply, but this is not a requirement that we need to enforce. it is enough with only enforcing either.

x2 <= 3 + M(1-y1)
x1 + x2 <= 4 + M(1-y1)
-x1 + x2 <= M(1-y2)
3x1 - x2 <= 8 + M(1-y2)

Finally, enforce that one of them are always active:
y1 + y2 >= 1

Now, it is up to the objective function to decide which region to pick. It will naturally pick the area that gives the better value. Our only requirement is that the point that the model ultimately finds as optimal, must lie in one of the areas.

Question 9

What is the general model of a knapsack problem

Answer 9

for the binary variant:

max z = ∑cj xj

s.t.

∑aj xj <= b

xj in {0,1} for j=1,…,n

Then we can extend with multiple resource constraints:

max z = ∑cj xj
s.t.

∑aij xj <= bi, where this is a sum over j, giving us a constraint per “i”.

xj in {0,1}

Question 10

Give an example of a binary knapsack problem

Answer 10

the housing budget problem

Say we want to buy houses, and we have a budget. We’d like to maximize the value of the purchase.

Another example is investing in projects. Say we can only be in or out. the objective function give payoff from each project. THe technology coefficients tell us how expensive it is, probably in terms of cash, time, mental energy etc. Then the objective is to maximize payoff, given that we can only select a subset.

Question 11

Elaborate on the facility location problem

Answer 11

Choosing a set of facilities, and from these facilities, support a set of customers.

Suppose we have m potenatial facilities and n customers. Each facility i has a given capacity (supply) si and each customers j has a given demand dj.

Typically include the fixed cost of using a facility, and a unit cost for each unit that is transported between facility i and custyomer j.

This is a mixed integer programming problem, because it use the fixed cost with binary, and it has a flow of units that is measured as a continuous variable.

Typically, the idea is to minimize costs.

min z = ∑∑cij xij + ∑fi yi

s.t.

∑xij <= si yi

∑xij >= dj

Basically, choose a set of facilities in a way that meet the overall demand.

IMPORTANT: The customers are the same regardless of facilities. Therefore, the problem is how to most efficiently select faciities to balance the cost of each facility (fixed and variable) vs the cost of transporting.

Question 12

elaborate on assignment problems

Answer 12

Objects in one set are to be assigned/allocated to objects in some other set.

For instance, assigning staff to various projects or tasks.

Typically, the goal is to minimize either cost or time. Therefore, depending on whether it is cost of time we solve for, we need to know how expnesive variouys objects are.

Generally speaking, we say that theassignment problem is a special case of the transportation problem, where we only have a bipartite graph.

We have one set of objects, which is the set of sources.
We have one set of objects, which is the set of sinks.

We assume there is an arc going from a source to all sinks, for all sources.

We need the following parameters:
aij = resource use if machine i is assigned to job j
cij = cost if machine i is assigned to job j
bi = resource capacity of machine i

variable: xij = 1 if machine i has been assigned to job j. 0 otherwrise.

Then the model becomes:

min z = ∑∑cij xij

s.t.
∑aij xij <= bi

∑xij [i]= 1

the first constraint limits how much a single machine can be utilized. If actual machine, this may be in terms of hours.

THe second constraint make sure that for each j (j = job/task) we have assigned a machine

Question 13

elaborate on set-partitioning

Answer 13

We have m objects/tasks, and these objects/tasks are listed in a variety of different subsets so that some are included in some subsets, while not in others.

Our objective is to pick a certain selection of subsets so that all of the objects/tasks are represented. Typically with the lowest possible cost.

General model:

xj = 1 if alternative j is used. 0 otherwise

min z = ∑cj xj

s.t.

∑aij xj = 1

where aij is 1 if activity/task/object “i” is included in set j. 0 otherwise. We get one such constraint for each object that needs to be included.

Question 14

What is the difference between set partitining and set covering?

Answer 14

Set partitionign is concerned with picking each object/task exactly once.

Set covering just wants to cover all tasks. Allows overlaps.

we get set covering when instead of using = constraint as in set partitioning, we use >= constraint

Question 15

set packing?

Answer 15

Same as set covering and set partitioning, but with <= constraint instead

Question 16

elaborate on the travelling salesman problem

Answer 16

need to visit n nodes exactly once, start and stop must be the same place, with the aim of minimizing total distance.

There is a differnece between the symmetrical and assymetrical TSP. The symmetrical problem has the same cost in both directions along a path. The asymmetric variant has differnet cost for differnet directions oalong the same edge.

Question 17

What constraints are important/necessary in the TSP

Answer 17

Recall that the variable is binary xij, and is 1 if edge ij is included in the tour or not.

we need 2 constraints that make sure that we are no going multiple ways from same node.

∑xij [j] = 1
∑xij [i] = 1

These two ensure that the number of edges OUT from i is 1, and the number of edges IN to a node is 1.

Then we need the constriant that makes sure that the tour is connected, and dont just consist of sub tours.

∑∑xij [i in S][j in S] <= |S| - 1

Question 18

why are IP cnsidered hard to solve, while LP is more easy?

Answer 18

Hard becasue of exponentual time complexity.

LP is easy because we know so much about where the optimal solution will be. Simplex utilize the fact that optimal solutions must liue at vertices.

Question 19

What 4 important strategies for solving IP problems do we have?

Answer 19

1) Enumeration methods
2) Relaxation and decomposition methods
3) Cutting plane methods
4) Heuristics

Question 20

What technique is branch and bound based on?

Answer 20

Enumeration. It use implicit enumeraiton, where implicit enumeration refer to using various “tests” to see/conclude that some solutions cannot lead ti better solutions than the best available.

Question 21

elaborate on relaxation and decomposition methods

Answer 21

Relaxation is about solving an easier problem. Common ways are LP relaxation and Lagrangian relaxation.

Decomposition is about splitting up the problem and sovling smaller problems in a systematic way and later combine the findings to conclude with optimalituy

Question 22

Elaborate on cutting plane methpds

Answer 22

Repeatdely solve the LP relaxation of the IP problem. In each new iteration, we add a constraint so that we make the next LP relaxation closer and closer to the optimal IP solution.

Related to findng the convex hull

Question 23

Elaborate on heuristics

Answer 23

No guarantee of fidning optimal solution, however they are very ffast.

Utilize simple rules of thumb

Question 24

the difficulty in solving IP problems depends on …?

Answer 24

1) Nubmero f integer variables
2) Problem structure

Question 25

In LP, what determines the difficulty in solving a problem?

Answer 25

Typically the number of constraints.

This is a contrast to IP, where there is more focus on the number of integer variables and the structure of the problem.

Question 26

For LP problems, how can we prove a solution is optimal or not?

Answer 26

KKT conditions along with convexity analyss

Question 27

Are there optimality conditions for IP?

Answer 27

No.

Question 28

if we want to prove optimality for IP, what do we do?

Answer 28

We need to use some iterative procedure where we find optimistic and pessimistic bounds that are iteratively brought closer together. We stop when the error (upperbound - lowerbound) is smaller than some pre defined error constant.

Question 29

elaborate on pessimistic bounds

Answer 29

A pessimistic bound is always given by any feasible solution to a problem. For max problems, pessimistic bounds is a lower bound.
For min problems, pessimistic bound is an upper bound.

Question 30

elaborate on optimistic bounds

Answer 30

we find optimistic bounds by solving a relaxed variant of the problem. Relaxation can be done in a variety of ways:
1) Remove integer constraint
2) Make feasible region larger by removing one of several of the constraints

Question 31

What are pessimistic bounds alternatively called?

Answer 31

Primal bounds

Question 32

What are optimistic bounds alternatively called?

Answer 32

Dual bounds

Question 33

what happens if the relaxation of a problem has no feasible solution?

Answer 33

The problem (without relaxation) will not have any feasible solutions either

Question 34

elaborate on weak and strong LP formulations

Answer 34

A problem is weak if its LP relaxation gives an optimal solution that is far away from the optimal solution of the IP problem.

The closer the stronger.

We say that the formulation is IDEAL if the optimal solution is the same for both problems.

Question 35

what is the mathematical foundation we need to go further in the discussion on good models in IP?

Answer 35

Convex hull.

Question 36

Elaborate on convex hull

Answer 36

“Convex hull of feasible integer points”.

A point y is a convex combination of a set of points x^(k), k in K, if:
y = ∑lambda_k x^(k) [k in K], where ∑lambda_k [k in K]= 1, and lambda_k >= 0 for all k in K.

So, a point is called a convex combination of a set of points if it is a weighted average of those set of points in a way where the sum of the weights is equal to 1.

Crucial about convex combinaitons: They define a convex set.

Then we can define the convex hull:
The convex hull of a set of points x^(k), k in K, conists of all possible convex combinations of the points.

So, the convex hull of a set of points refer to the entire possible set region defiend by considering all convex combinations of the set of points.

Question 37

In IP, can the convex hull be diagonal lines between points, or do we require straight lines in the dimeniosnal directions+

Answer 37

Obviously we allow linear hyperplanes. The definition of convex hull applies.

Question 38

Relate a convex hull to linear shite

Answer 38

We can define a convex hull by inequalities that essentially create a feasible region.

Question 39

What is the important outcome of convex hulls?

Answer 39

If we had them available, we could solve the IP as an LP

Question 40

Do we search for the convex hull in practice?

Answer 40

No, it is too time consuming. However, there are many methods that reduce the differnece between the feasible region and the convex hull, by performing changes to the IP formulation.

Question 41

How can we achieve a smaller differnece between the feasible region and the convex hull?

Answer 41

Initially choose a strong formulation

Adding problem specific valid inequalities. Valid inequalities is a topic for later.

Question 42

What can we say about problem structure in terms of “better” or “worse” (stronger/weaker)

Answer 42

for IP, we can often find multiple ways of structuring the very same feasible region. Now, this is the feasible region in regards to the IP solution points. However, once we perform the LP relaxation, we of course get another feasible region. it benefits us if the difference between the convex hull (given by the convex combination area of the solution points) and the feasible region of the LP relaxation is as small as possible. Therefore, adding more constraints (while keeping the IP feasible region the same) is beneficial for this purpose. Of course, doing so adds complexity since we have more constraints. However, the problem structure is typically much more important than adding some constraints.

Question 43

elaborate on M

Answer 43

The smaller we can set it, the better the LP relaxation will be.

it is based on the same principle as constriants. Why? Because the bigM is a part of a constraint, so naturally it makes a difference. The point is to reduce the differnece between the feasible region of the LP relaxation and the convex hull.

Question 44

What is a valid inequality?

Answer 44

A valid inequality is an inequality
that is satisfied for all x in Xip.

Adding a valid inequality will not change the feasible region of the IP problem, but will reduce the difference between the feasible region of the LP relaxation and the convex hull.

Question 45

what is the advantage of adding valid inequalities?

Answer 45

since it yield a better approximation of the convex hull, the LP relaxation will be better (at least not worse)

Question 46

Elaborate on the Face of a convex hull

Answer 46

we say that the face of a convex hull is given by the set of points that satisfy:

F = {x : x in Xc, ∑aj xj = b}

This means, not all valid inequalities will produce a face.

Question 47

What is facet?

Answer 47

A face F of a convex hull Xc with dimension dum(Xc)=n is called a facet if dim(F)=n-1

In other words, if the face is of dimension one less than the convex hull, it is a facet.

Question 48

What shapes can the face be?

Answer 48

A valid inequality that defines a surface of dimension 2, can support the convex hull along an edge or a point

Question 49

broadly what is cutting plane methods about?

Answer 49

approximate the convex hull better and better.

it is not a goal to construct the entire convex hull, as some areas are more important than others.

Question 50

what are the cuts in cutting plane?

Answer 50

Constrains: Valid inequalities

Question 51

why must the cuts be valid inequalities

Answer 51

If not valid, then they can remove points from the feasible region. this might shave off the optimal solution.

Question 52

What is the general algorithm for cutting plane?

Answer 52

1) Choose a suitable mathemtical formualtion of the problem. If possible, add some initial valid inequalities

2) Solve the LP relaxation of hte problem
3) If integer solution, stop. If not, continue

4) Add one or several valid inequalities that cut away the LP optimal solution.
a) Based on problem specific cuts
b) Based on a general cutting plane method, like Gomory’s method

5) Resolve the LP relaxation and go to step 3

Question 53

elaborate on Gomory’s method

Answer 53

Gomorys generate the valid inequalities based on the optimal tableau from LP relaxation. This is nice, because we dont need to know much about the structure of the IP problem.

One requirement for generating cuts: All coefficients in the problem must be integers. However, note that we can multiply coefficeints by a suitable constant if not.

Each row in the system of equations (including the obj func row) that has a fractional RHS value can be used to generate a cut.
The constraint must cut away the current LP optimal solution, but not any integer solutions (just the same as saying we want to add a valid inequality).

Here is what we do:

We solve the LP relaxation. This gives us basic solution. for each row in the optimal tableau that is not integer on RHS, we study it.
Each can be written like this:

xi + ∑aij xj = bi

Since xj are all non basic, we basically have that xi = bi.

Then we split bi and aij into their integer parts and fractional parts.

xi + ∑(int(aij) + frac(aij))xj = int(bi) + frac(bi)

Now we re structure the equation so that we get all the integer parts on the LHS, while the fractionals are on the RHS

xi + ∑int(aij)xj - int(bi) = frac(bi) - ∑frac(aij)xj

Instead of using int and frac names, we use regular to indicate integer, and “f” to indicate fracitonal:

xi - bi + ∑aij xj = fi - ∑fij xj

Since LHS only consist of integers, the total is an integer. Therefore, the LHS must also be an integer.
However, we also know that fi can NEVER be equal to 1. fi must always be smaller than 1, since it is the fractional part of a fractional number.
When we combine the fact that the RHS must be smaller than 1 and must be integer, we know that the LHS basically is 0 or smaller.
Sidenote: Why do we know that ∑fij xj is positive? It is positive because xj is either 0 or 1, and fij is a positive fraction part.

So, we have:

xi - bi + ∑aij xj <= 0

Alternatively,

xi + ∑aij xj <= bi

Now, remember that aij and bi are floored functions.

This final result is teh Gomory cut. It is an integer cut, since it consist only of the integer parts.
We could also use the RHS result of being smaller than or equal to 0 as well, which is called the “fractional cut”.

One last thing: It is common to take the Gomory cut, and perform substitution so that we dont give it in terms of slack variables. We therefore visit the orgiinal problem description and find the suitable substitution before we add the constraint to the problem.

Question 54

Define a cover and elaborate

Answer 54

for a binary knapsack problem iwth feasible region:

X = {x in {0,1} : ∑aj xj <= b}

the set S is a cover if ∑aj [j in S] > b.

The set S is a minimal cover if for each selection of “k”, removing k from the set will make that S is no longer a cover.

So, this means that if the set of all indices is not a cover, the constraint can never be violated.

More importantly, a specific “cover” will violate the constraint.

Question 55

What is the theorem we can gain from the minimal cover foundation

Answer 55

If S is a minimal cover, then the constraint

∑xj [j in S] <= |S|-1

must be a valid inequality for X.

The reasoning is that since S is a minimal cover, we can not include it in the otpimal solutino. However, specifying that gives us a constraint that reduce the feasible region of the LP relaxation.

Question 56

How can we strengthen the valid inequalities?=

Answer 56

We use the theorem that says tghat if S is a cover of X, then the augmented cover constraint

∑xj [j in E(S)] <= |S|-1

is a valid inequality if E(S) = S Union {j : aj >= ai, for all i in S}

In other words, we can add a variable to the mix IF its coefficient is greater than or equal to all coefficients in the set already.

Question 57

What is the general foundation of branch and bound problems?

Answer 57

Split the feasible region into smaller regions and solve relaxed problems. By making use of information from each subproblem, we can find the optimal solution to the original problem.

Question 58

In branch and bound, what do we “want”=

Answer 58

We want to collect information in areas of the feasible region where it is likely that solutions with good objective function values can be found, while at the same time avoid searching shitty areas.

Question 59

Why is it called “branching”?

Answer 59

We split a problem into subproblems with smaller feasible regions

Question 60

Why is it called “bounding”?

Answer 60

In each subproblem, we find an optimistic bound to the objective function value by solving its relaxed problem. This bound represent the best possible solution this part of the problem can be (not necessarily that it will be this value, because obviously it is an optimistic bound, not necessarily realistic).

Question 61

how do we branch?

Answer 61

adding a constraint (or several) in a systematic way.

Question 62

What determines how good our “cuts” in the search tree can be?

Answer 62

The cuts are based on comparing the current best pessimistic value vs the optimistic bound of a new sub tree. If the pessimistic value is better, we can cut.

Therefore, there is significant amount of performance that depend on being able to find good pessimistic values as early as possible.

Question 63

what methods of node selection do we have?

Answer 63

Depth first
Breadth first
Best first

Question 64

elaborate on depth first

Answer 64

Always pick a subproblem to solve that has been branched the most times.

The advantage of depth first is that it quickly finds a feasible soltuion (pessimistic solution).

Question 65

elaborate on breadth first

Answer 65

Completes a level before starting on the next level.

Breadth first works well in cases where it is possible to find good solutions without adding too many constraints.

Question 66

elaborate on best first

Answer 66

Move to the subproblem with the most promising optimistic bound.

Disadvantage of this is that we need to start over with simplex

Question 67

elaborate on termination criterion

Answer 67

In many practical applications, it is not feasible to search and investigate all subproblems. Therefore, it can be necessary to specify a terminatio ncriterion that basically is a given level of accuracy that we are happy with. We refer to this error as “epsilon”.

Then we terminate the search once the (best optimistic bound - best pessimistic bound)/best pessimistic bound is smaller than the epsilon.

Question 68

In practice, how do we solve the LP relaxations in Land-Doig-Dakin?

Answer 68

We use dual simplex to re-optimize starting from the previous spot.

Question 69

how do we treat the variable selection in terms of choosing which variable (not which subproblem) to branch on?

Answer 69

Depends on the strategy.

if we use depth first to find a solution quickly, we want to use the “largest fractional value” as the pick, because this reduce teh search space the most.

other methods include:
- choosing the one closest to integer
- Select the variable with the best obj func coefficient
- select from a pre-determined list
- indices

Question 70

are all IP problems equally solvable in regards to branch and bound?

Answer 70

No. The problem structure is very important, because if we know something specifically, we can leverage this to make modifications to the branch and bound and solve more efficiently.

Question 71

What are the usual suspects in regards to problems that we can leverage certain tactics using branch and bound?

Answer 71

Knapsack
TSP
Job scheduling

there might be more. Perhaps set partition, covering and packing? What about network problems

Question 72

what is the motivation for the knapsack branch and bound fuckery

Answer 72

LP relaxation can be solved by inspection
AND
We can always round off the relaxed solution and get a pessimistic bound.

Question 73

For knapsack fuckery, what is upper bound of a variable

Answer 73

For the linear problem, we can set the variable to be the ratio of the b-value and its coefficient.

upper bound variable j = b / aj

For the integer problem ,we can round it down, so we get:
upper bound variable j = floor(b / aj)

The reason why we can round down like that is that if there are no other constraints, the variable is flexible.

Question 74

elaborate on the procedure of knapsack bb

Answer 74

Find the sorted order of the cj/aj. Rperesent the order which we want to choose from.

Then given a set of constraints on the integers:
Initialize all variables to be their lower bounds. In the first subprob lem, all arel ikely 0. Later, they will be other than 0 (when branched on).

Based on the lower bound, compute how many resources are left. Then we go through the sorted order, and fill it up. This basically solves the LP relaxation by inspection.

If all variables are integer restricted, we know that the solution can be rounded down (basic solution), for instance from (1.75, 0, 0, 0) to (1,0,0,0).
if all coefficents in the objective rfunction are also integer, we can round the optimistic bound as well.

This gives us 2 important things:
1) Each step gives us a pessimistic bound.
2) LP relaxation solved by inspection

Question 75

what happens if a matrix is total unimodular?

Answer 75

if the A matrix is total unimodular, the constraint

Ax<=B defines the convex hull.

Therefore, solving a single LP relaxation solves the entire problem.

Question 76

how do we know if a matrix is total unimodular?

Answer 76

Each square submatrix must have determinant equal to 0, -1 or +1.

We dont do this in practice, but there are some easier ways.

We have some properties that guarantee that the matrix is total unimodular:

1) Each element is 0, 1 or -1
2) No more than 2 non-zero elements in each column
3) Rows can be split into two subsets P1 and P2 where
a) if a column contains two of the same number (+1 or -1) the rows have to be in differnet subsets
b) If a column contains +1 and -1, bith rows have to be in the same subset.

So, for eahc column: If there are 2 non zero elements, we must be able to create a partition so that all of the columns are satisfied

Question 77

what is the relationship between A and A transposed in regards to total unimodular?

Answer 77

If one is total unimodular, the other is as well

Question 78

The unimodualr requiremet, is it requirement, necessity, or what is it?

Answer 78

It is a condition that says if the matrix posess it, it happens to be total unimodular.

There are other matrices that does not have this condition, but can still be totally unimodular

Question 79

what is a smart subset probably?

Answer 79

one empty, annd the other one include all the rows. In such a case, we must of course have that if there are more than 2 non zero elements, they must have opposite sign in eahc column

Question 80

how can we model a constraint saying that logical OR of a list of binary variables should indicate the value of some other binary vairable

Answer 80

y1 v y2 v y3 …

we can model this by

y1 + y2 + … <= n w

we force w to be 1 if as much as one of the variables on the LHS is 1.

Question 81

What is an indicator variable?

Answer 81

A binary variable that indicate a certain state.

For instance, yes no decision.

it is very common to distinguish between states where we have 0 aciton, and “some” action. For instance in production at various facilities. We cna use an indicator variable to indicate whether produciton at facility is beign done or not.

Question 82

for indicator variables, what is important regarding M?

Answer 82

we have a constriant like this:

x <= My

this will force y to be selected as 1 if x is going to be larger than 0.

The important part is what we choose M to be.
It shiuld be as small as possible, but not be restricting in terms of x. The upper bound for x is a safe value for M.

Question 83

How can we model a constraint that does this:

y = 1 –> x >= m

Answer 83

x >= my, where m is a small value

if y is sat to 1, then we see that x must be larger than or equal to the value of the lower bound “m”.

Question 84

How can we model

x = 0 –> y = 0

Answer 84

It is not actually possible to represnet this as a constraint.

y <= x
x <= My

Question 85

how to model “if A then B” as a constraint?

Answer 85

Say we have continuous variables xA and xB.

First we need indicator variables as to whether they are used or not:

xA <= MyA
xB <= MyB

Then we can use the indicator variables to enforce the relationship:

yA <= yB
Alternatively:
yA - yB <= 0

Question 86

How can we use indicator variable to show whether a constraint holds or not?

Answer 86

We add M multiplied by indicator variable to the LHS, while adding M to the RHS.
FOr instance:

∑ajxj + My <= b + M

This makes sure that if the constraint holds, y=1.
If the constraint doesnt hold, y=0.

The phrasing is a little weird. “Showing whether a constraint holds or not” must be considered in relaiton to the objective funciton. If there is a penality for not including the constraint.

It is actually a very powerful tool. consider cases where we can avoid a constraint for a fine or something like that. In these cases, this indicator variable is necessary.

Question 87

Consider the constraint with indicator variable:

∑ajxj + My <= b + M

What should M be here?

Answer 87

Should be equal to:

∑ajxj - b <= M

In other words, M must be an upper bound on this LHS expression. Depends very much on what x can be.

Question 88

Elaborate on enforcing the condition of:

x = 0 –> y = 0

Answer 88

the case that the book try to explain is that if we want bi directional to work, where setting y=1 enforce a x larger than 0, then we need to add another constraint. However, adding this constraint still isn’t perfect because we need to find a level (epsilon) that we define as the lower threshold. So, we end up enforcing x to be not just positive if y=1, but it must be larger than the epsilon value. Sure, we can set epsilon extremely small and achieve a somewhat desired effect, but it is not as elegant as we might have hoped for.

The constraint

x >= ey, where e is epsilon value, force x to be larger than epsilon if we set y=1. if y=0, nothing is enforced.

We can then combine them:

x >= ey
x <= My

Alternatively:

x >= my
x <= My

in any case, if y=0 then x is forced to be 0.
if y=1, x is forced to be larger than “m”.
if x is larger than 0, y is forced to 1.
forcing y to 1 will then force x larger than epsilon.

to sum up, this constraint is impossible to model without epsilon.

Question 89

elaborate on enforcing this logical expression as a constraint:

∑aj xj <= b –> y = 1

Answer 89

Recall that the other way around:

y=1 –> ∑aj xj <= b, is enforced by:

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

however, this does not say that if y=0, then the constraint cannot hold. It just removes it from conisederation. The key here is that if y=0, no relationship is enforced.

from the relation we now want to enforce, it can be structured as:

not(y=1) –> not (∑aj xj <= b)
which of course equals:

y=0 –> ∑aj xj > b

This is where we are stuck with the other constraint.
The other constraint only say that if y=0, then nothing is required.
In order to enforce some kind of constraint that make the ∑aj xj > b if y=0, then we need to add epsilon again.

We then say:

ey <= ∑aj xj - b