Chapter 12 - Integer programming

Question 1

What is the key limitation of linear programming

Answer 1

Requirement of divisibility

Question 2

Define an Integer programming problem (IP)

Answer 2

Exactly the same as linear programming, but with the requirement of integers are the decision variables.

We have the same constraints as with linear programming, BUT we also have additional constraints describing the Integer situation.

Question 3

What happens if we have some decision variables that has divisibility properties and some that require integers?

Answer 3

We call it a mixed integer programming (MIP) problem.

Question 4

What applications do we have with integer programming?

Answer 4

THere is the direct extension of linear programming models that just require whole numbers.

Then there are the cases of “ a number of interrelated yes/no decisions”. In such decisions, there are only two possible outcomes. With only yes or no we can use binary variables, making it a binary integer programming problem. Also called 0-1 integer problems.

Question 5

Formally define a binary decision variable

Answer 5

x_j = [1 if decision j is yes], [0 if decision j is no]

Question 6

What is a mutually exclusive constraint, and how do we represent it?

Answer 6

A mutually exclusive constraint is one where, in a binary scenario, we can only have one or the other. We cannot have both equal to 1.
Typically the case is the we have permission to perform at most one project, and we have the option to do none. In such a scenario, it would make sense to add it as a mutually exclusive constraint; ∑yj <= 1. It is smaller than, or equal to, because we need to include the possibility of doing none.

We represent this as a constraint like this:

say x_1 and x_2 are mutually exclusive, and are binary. Then we have the this constraint:

x_1 + x_2 <= 1

MORE GENERALLY, we define mutually exclusive events to be a case where no more than one event is allowed to occur. Therefore, we can have a group of events where only one of them can be equal to 1.

∑xj <= 1

Question 7

What are contingent constraints, and how do we represent them?

Answer 7

Contingent constraints involve cases on decision variables where the outcome of one variable is dependent on the choice of another variable.

Say variable x_3 can only be set to 1 (be chosen) if variable x_1 is chosen (1). Then we have this constraint:
x_1 >= x_3, or x_3 <= x_1

Question 8

what is the benefit with binary integer programming vs pure integer programming?

Answer 8

binary are easier to deal with, can usually solve lots bigger problems

Question 9

elaborate on fixed investments problems

Answer 9

They are asking for a combination of fixed investments. We have a list of possible investments, their cost and their reward. The problem is to figure out the best combination. Since the investments are fixed, we are only considering decision as yes or no. Therefore, such problems are typically BIP problems.

Question 10

elaborate on fixed charges

Answer 10

Fixed charges refer to cases where there is some cost involved in initiating an activity. For instance, say we’re looking at some decision that is “should we produce product X?” The cost in this case will be both the start-up cost (facility etc) AND the cost of production.

IF we have proportional cost of production, we can use BIP, and formulate the constraint like this:

f{j}(x{j}) = [k_j +c_j x_j if x_j >0], [0 if x_j = 0]

Question 11

IN what scenarios could investment analysis use BIP?

Answer 11

Whenever we’re interested in whether or not to invest in a certain (or in several) projects. We use a single variable to represent a decision, YES or NO (1 or 0).

Question 12

It is problematic to use LP/IP to work on decisions involving both start up cost and variable cost. Elaborate why this is, and what to do with it

Answer 12

It is difficult because the total cost looks like this: TC = C_initial + C_variable
or more formally: f(xj) = kj + cjxj.
Since we are trying to optimize with regards to minimizing costs, this function is included in the objective function. However, due to the fixed cost, we dont know what to do.

So, how do we fix this?

We consider this: x_j represent some activity j. We are essentially asking “should we perform activity j?”.
We introduce an auxillery variable, called y_j. This new variable will be 1 if its corresponding x-variable is greater than 0. It is 0 otherwise. So, it follows xj.

We get this: fj(xj) = kjyj + cjxj.

So, when we set up the objective function, we get the following one:

min Z = f1(x1) + f2(x2) + … + fn(xn)

min Z = ∑(cjxj + kjyj)[j=1, n]

We again use M as a large value with this constraint:

xj <= Myj

This constriant will ensure that yj =1, rather than 0, whenever xj > 0.

The only remaining problem is that yj is free to be whatever when xj is 0. However, this is actually automatically solved by the objective function as long as we’re minimizing the function. The minimizing objective function will always choose yj = 0 whenever xj = 0, because it reduce the cost the most.

Question 13

How can we make an “either-or” constraint?

Answer 13

We use the large value M to eliminate a constraint in certain scenarios:

Say we have the following case: We need either one of these constraints to hold:

3x1 + 2x2 <= 18
x1 + 4x2 <= 16

In order to make sure than one of them holds, we do this:

3x1 + 2x2 <= 18+My
x1 + 4x2 <= 16 + M(1-y)

y is a binary variable. If it is 0, we will include the first constraint. If y is 1, we include the second constraint.

Question 14

Say we have N constraints and K of them must hold. How do we represent this?

Answer 14

Assume that K < N

The N-K constraints that are not chosen will be eliminated. Note that they may still be satisfied, but they are not enforced by the model.

We add n new variables, y1, y2, … , yn. we multiply them with M, and add them to their corresponding constraint.

then we add these constraints:
1) y_j is binary.

2) ∑(yj)[j=1, n] = N - K

Question 15

Elaborate on relaxation in regards to IP

Answer 15

We say that an integer programming problem’s corresponding linear programming problem is its “relaxed problem”, or “LP relaxation”. This is because, the LP one will always be easier to solve, and if the solution (optimal) to the LP relaxation satisfy the integer constraints, then this solution is the optimal solution to the integer problem as well.

Question 16

Whats a mixed integer programming model? MIP

Answer 16

The case where some variables have the integer-restriction while some others have the divisibility-legality.

Question 17

What is the divisibility assumption+

Answer 17

The divisibility assumption is that we assume that decision variables can have values that are not integers.

Question 18

What is a BIP problem?

Answer 18

Binary Integer Programming problem. Problems that ONLY contain binary variables are sometimes called BIP.

Question 19

IMPORTANT:

Name the different types of “binary restrictions”

Answer 19

1) Mutually exclusive: We can only pick ONE option among several. For instance, we have N different decisions, and we can only make one of them. Perhaps this is “choosing which project to do” or “investment to make” etc. The important thing is to consider all the binary variables (decisions) as a sum that can never be greater than 1:

∑Xi <= 1

Ex: x3 + x4 <= 1

2) Mutually exclusive extension: Pick K from N decisions. The same principle applies, we do this:

∑Xi [i=1, n] = N - K

3) Contingent decisions. A decision is contingent on some other variable/decision if its outcome depends on the other variable’s outcome. for instance, say we “can only build a warehouse in a city in which we have already built a facility in”. Or “we can only do projects with a domain that we have knowledge on”. To enforce contingency, we do this:

Say x3 is contingent on x1 in the way that “we can never choose decision x3 if x1 is not chosen”. In other words, “we can only choose x3 if x1 is chosen as well”:

x3 <= x1

This leads to:

x3 - x1 <= 0

This will make sure that x3 never becomes chosen if x1 is not.

4) “if decision xi, then xj as well.”: This means “forcing xj to be chosen if xi is chosen”. We can do this like this:

Say x2 must be chosen if we choose x1:

x1 <= Mx2

This constraint says: If x1 is chosen, which sets it to “1”, then x2 must be 1 as well, because it needs to satisfy the constraint. M is just a big number.

5) Either-Or constraints. This refer to cases where one of the constraints MUST hold, while the other can be flexible. The point is not on which one holds, but rather that ONE OF THEM is certain to hold.

SUpposoe we have these two constraints where at least one of them must hold:
3x1 + 2x2 <= 18
x1 + 4x2 <= 16

What we do is add a new variable, which we call an “auxiliary” variable, y. This variable in binary as well, and represent the choice “choose this constraint to hold with certainty”. We use it like this:

3x1 + 2x2 <= 18 + My
x1 + 4x2 <= 16 + M(1-y)

This has the effect of “eliminating”/”removing” one of the constraints from the model, given that M is sufficiently large.

6) Either-Or with more than 2 constraints and more to hold: THe same logic applies, but we cannot use y vs (1-y) anymore. We must use one y variable per constraint we are considering:

∑y_i [i=1, n] = N - K

7) Fixed-charge problems. Consider the case where choosing some decision will have a fixed-cost AND a variable unit cost. In such cases, the “cost function” would look like this:
f(x) = FixedCost + VariableCost*x
In order to add the fixed cost to the model (recall linearity etc) we need to add an auxiliary variable which we mulitiply with fixedCost. This new variable represent the choice “we select/choose decision x”, and therefore we must also select the incurred fixed cost.

With this, we must use the all-important forced contingency constraint:

Say x1 is a decision, and the fixed-charge cost is represented by y1. Then the following constraint must be added:

x1 <= My1

This force y1 to be something other than 0 if x1 is 1. Due to the model, it would never choose y1 to be 1 if x1 is 0, because it is not optimized. However, we could add a constraint to improve readability:

y1 <= x1

Question 20

Elaborate on binary representation of general integer variables

Answer 20

The first thing we need to understand, is what we use this for:
We use binary representaiton of integer variables when we want to solve a pure BIP problem. Say we have a case where we have 49 binary variables and 1 integer variable. We would like to use one of the efficient BIP solvers, so we want to represent the general integer variable as a sum of binary variables.

Suppose an integer variable X has a bound like this:

0 <= x <= u

Then we can use this to represent this variable by using a series of binary variables:

We define an integer N such that:

2^N <= u < 2^{N+1}

Pay EXTRA attention to the fact that it is only smaller than symbol above.

then the binary representation of X is:

X = ∑2^{i}y_{i} [i=0, N]

ex consider the bound=15, so that 0<=x<=15.
15 is between 2^3 and 2^4, so N=3
X = y0 + 2y1 + 4y2 + 8y3
Since y equals decisions (binary) this sum can be every number from 0 to 15 included.

If we replace each occurance of X in our model with the sum of binary variables, we get the same result as we otherwise would.

So, the new model will consists of a shit-load of new y-variables, but it will be easy to treat because they are binary.

The important part is to sum together afterwards to get the final answer.

NB: We also need to add constraints to make sure that the sum of new variables is smaller than the bound for the original variable.

Question 21

Why is it natural to consider some kind of enumeration strategy to solve IP problems?

Answer 21

Because they have a finite number of possible solutions. Unlike regular LP problems, we can actually quantify the lot.

of course, we want some enumeration method that works better than a brute force search. Dynamic programming is one alternative.
Branch-and-bound is another alternative.

Question 21

How do we progress iterations on branch-and-bound?

Answer 21

We need some selection policy for the variables that we fix to a point. This is usually a crucial part of the algorithm, but for simplicity, we choose their natural order.

Question 22

Why does the BIP branch and bound use “most recently created subproblem” instead of “best bound” to progress the procedure?

Answer 22

Because it can continue the use of ONE simplex tableau along a path. This allows for large-scale implementation.

Question 22

Elaborate deeply on branch and bound on a general MIP problem

Answer 22

A MIP problem consists of variables where some of them are restricted to be integers and some are not. Some may be binary, but this is not a general requirement.

We say that the “I” first variables are integer-restricted.

THe problem goes like this:

Max Z = ∑CjXj [i=1, n]

subject to:
∑aij Xj <= bi, for i=1,2,…,m

and
Xj >= 0 for all j
Xj is integer, for j = 1,2,3,…., I; i<=n

WHEN choosing a variable, we only choose among the variables that are integer-restricted that have a non-integer value in the optimal solution for the LP relaxation for the current subproblem.

We also need to change the way we “select a value” for the branching variable. With the BIP problem, we could just set to 0 or 1. What we do is this: We still only specify 2 new subproblems, but each with a possible range of values. We do this because it would be extremely difficult to enumerate every possible domain value.
How is it done actually?

Let xj be the current branching variable, and let xj* be its (noninteger) value in the optimal solution in the relaxed LP problem. We use square brackets to denote:
[xj] = reatest integer <= xj, we have the following range of values for the two new subproblems:
xj <= [xj] and xj >= [xj]+1

Each inequality comes an additional constraint for that new subproblem. For example: If xj* = 3.5, then:
xj <= 3 AND xj>=4, are the respective additional constraint for the new subproblem.

The third change between BIP and MIP is that we dont round down the solution for a subproblem, since we are no longer restricted to only integers.

The fourth change is kind of given, but it is that we only require integer-restricted decision variables to be integer in the final solution. This distinguish MIP from BIP, since BIP requires ALL to be integer/binary..

Question 23

in MIP branch and bound, what is x_j*?

What is [xj-star]?

Answer 23

x_j* represent the value of the variable xj in the solution of the LP relaxation.

[xj-star] is the greatest integer <= xj-star. If xj-star is 3.5, then [xj-star] is 3.

We use this value, and variable, to create the additional constriants:
xj <= [xj]
xj >= [xj]+1

The constraints are not both added to some subproblem. We add one of them one subproblem, and the other to the other subproblem.

Question 24

When do we “stop” branch and bound?

Answer 24

We stop it when there are no remaining subproblems that are not fathomed. Then, the current “incumbent” is optimal. Otherwise, we perform a new iteration.

Question 25

Elaborate on “bounding step” for both BIP and MIP. What are we doing here?

Answer 25

We need to find a bound on how good its best feasible solution can be. WE do this by solving the LP relaxation of the problem.
the result we get from solving the LP relaxation will be the very best it can possibly be. This means that if the LP relaxation got this solution, then the BIP or MIP subproblem can never be better. They can be just as good, but never better.

with BIP problems, we round Z down. Why? Because all coefficients in the objective function will be integers. NB: this is not the case with MIP.

**What is the bound used for?***
Fathoming step.

Long story short:
A subproblem is fathomed (discarded) if:
1: Its bound <= Z*
2: Its LP relaxation has no feasible solutions
3: The optimal solution for the LP relaxation is integer.

The reason we discard subproblems with a bound smaller than or equal to Z*, is because this value represent the incumbent. The incumbent is an integer solution to the subproblem. Since it is an integer solution, it is the optimal solution to this subproblem. Therefore, we can never get a better result than this.
So, if we consider two subproblems at the same level, and the first one yield incumbent 16, and the second has a bound that is lower than 16, there is no damn point in investigating this path further. therefore, we discard.
The optimal solution at the end, is the incumbent value and its corresponding solution.

Question 26

How do we treat a binary branching variable to get an LP relaxation?

Specifically, how does the constraint look like?

Answer 26

xj can be either 0 or 1. We relax it to also include all numbers in between:

0 <= xj <= 1

Question 27

In the MIP branch and bound, how do we choose branching variable?

Answer 27

We use the “first” integer-restricted variable that has a value that is NOT integer (from solving LP relaxation using simplex). Among these, we select the first one according to their natural ordering.

Question 28

when do we round down in the branch and bound procedure?

Answer 28

If all variables are integer-restricted AND all coefficients in the objective function is integer, we can round down the solutions to the LP relaxation if it is not integer already.

Question 29

Give a thourough walkthrough of the MIP branch and bound

Answer 29

We start with a problem. This problem have some variables that are integer-restricted and some that are not.

INIT: we set the incumbent value Z* = -infinity. Then we perform BOUNDING, fathoming and optimality test.

ITERATION:

We start by branching. Among the unfathomed subproblems, select the one that was created most recently. At the beginning, this is only the “whole problem”.

We now perform the branching step. Among the remaining (unfathomed) subproblems, pcik the one that was created most recently. Among the integer-restricted variables that have a noninteger value in the optimal solution for the LP relaxation (recall that we have solved this problem before) pick the “first one” as the branching variable. Say this is xj, and that xj-star is its value, as given by the solution from the LP relaxation.
we “branch” from this node/subproblem to create two new subproblems. We create the new subproblems by adding a new constraint to them each. We add xj <= [xj-star] to one of them, and xj>=[xj-star]+1 to the other subproblem. These constraints carry along their path.

After we have branched out to two new subproblems, we do the bounding step. For each new subproblem, the bound is found by performing simplex to its LP relaxation, now with a new constraint.
replace current incumbent if possible.

THen we perform the fathoming tests. Discard a subproblem if:
1) Its bound <= Z-star
2) Its LP relaxation has no feasible solutions
3) The optimal solution for the LP relaxation has integer values for the integer-restricted variables.

Now, optimality test: stop when there are no remaining subproblems that are not fathomed. Then the current incumbent is optimal.

Question 30

What is the most important application of integer programming?

Answer 30

yes/no decisions using binary variables.

Question 31

What is the most important part about BIP problems?

Answer 31

The constraints. For instance, we typically represent the objective function like this:

max Z = ∑cjxj [j=1, J]

In most cases, we cannot make every decision. If this was the case, the case would be trivial to solve, as we would simply choose “yes” on every decision. Because of this, we have to carefully create the constraints so that we can only select the decisions we should.

Question 32

What is the only thing distinguishing LP scenarios from IP scenarios?

Answer 32

LP requires the divisibility assumption, while IP does not.

Question 33

What is the actual complete name of IP problems?

Answer 33

Integer linear programming. ILP.

Question 34

Define MIP

Answer 34

Mixed Integer programming. Refers to cases where some variables are required to be integers, and some are just real.

Question 35

What do we call integer programming models using only integers?

Answer 35

PURE integer programming. PIP.

Question 36

What are the common applications for integer programming?

Answer 36

We have the classical cases of considering shit where we are only interested in whole amounts of something.

But, more commonly, we have decisions.

Question 37

Define BIP

Answer 37

Binary Integer Programming. IP problems that only contain binary integer restricted variables.

The category of BIP gives rise to another category: Non-binary decisions.

Question 38

Say we have a minimum cost flow problem. Say all values are integers. how do we solve it?

Answer 38

Simplex will do it. Regardless of whether the undelying problem is integer og not. The property of minimum cost flow problems being all integers will yield integer solution. Since this is required, and we know that an integer solution returned from simpelx is always valid, we can use simplex.

Question 39

How does simplex indicate no feasible solutions?

Answer 39

There is a sequence of steps.

First, we recognize that our standard form needs to be violated. Since we cannot pick the origin as the starting BFS, we need to use artificial variables. Then we use something like the two-phase method. Two phase minimize the sum of artificial variables without any cost. If the minimized sum of variables correspond to a solution that carry artificial variables with values larger than 0, it means that we have not found a possible feasible solution as our starting point. This would also mean that the entire problem has no feasible solutions.

ON THE NEGATIVE CASE OF NO ORIGIN FEASIBLE:
Say the origin is not feasible because all variables are required to be less than some negative value. We know that we solve this by multiplying with -1 on both sides. This will change the inequality (flip it). Then we need to use surplus + artificial variable to solve. Therefore, it is NATURAL to use artificial variables for such types of problems. Therefore, we WILL apply the two-phase method, and we can use the result of the two-phase method to see if there are any feasible positions in the region.

Question 40

Consdiering the best algorithms today, what cap are we talking about for pure BIP problems?

Answer 40

We can solve some models that have approximately 1000 variables. This is a lot better than exponential exhaustive search/enumeration, but it is still a limitation.

There are also problems significantly smaller that are difficult to solve. We are talking a couple hundred variables, and we cannot solve them in reasonable time.

Also, when looking at integer programming problems, the set of solvable problems tend to be EVEN smaller.

Because of all this, we know that IP is really bad.

Question 41

IP has much fewer solutions than LP. Why is LP so much better regardless?

Answer 41

LP has the advantage of adjacency. Adjacency allows us to travel insanely fast to the next solution in a way that greatly benefits us.

Question 42

Elaborate on branch and bound on an abstract level.

Tell about the overall workings. What is it based on?

Answer 42

It is a divide and conquer procedure. Naturally, this means that the original problem is typically considered to be too difficult to solve outright. Therefore, we want to split it somehow into smaller subproblems that are easier to solve, and can then be combined into a solution.

We call the “divide” part “branching”
We call the “conquer” part “fathoming”.

Question 43

Elaborate deeply on the entire procedure of BIP branch and bound

Answer 43

Recall divide and conquer - The point is to solve subproblems and then construct the solution of the original problem by using the solutions to the smaller problems.

The first step is branching.
Since we’re dealing with binary variables, we can easily split the problem by considering an arbitrary variable, say x1, and splitting the problem into subsets where x1 is either 0 or 1. This essentially eliminates x1 from the subproblem, making it smaller. Note: while it eliminates x1, the value we use for x1 remains fixed, and we use it like a normal constant. In constraints we just move this value into RHS.

We typically draw the branching tree to keep track of states.

In regards to selection of branching variable, this step is rather important. However, we dont consider any thing other than arbitrary.

The next step is called bounding.
This step involves solving the relaxed version of the problem. Typically, this involves removing the constraint(s) that made the problem difficult. Note as well that the easier we make the problem, the worse the bound gets. However, we usually change the binary constraints to 0<=x<=1 instead.

IF the optimal solution we get from this step is non-integer, AND ALL COEFFICIENTS of the objective function are integers, then we can round the optimal solution down. However, if as much as a singel objective function coefficient is non-integer, we cannot round.

So, we find the bound of the entire problem and the bounds of subproblems as we get them.

The bounding step is only about finding the bounds.

The next step is called fathoming.
Fathoming means dismissing the problem/subproblem for further evaluation. This is what we want.
Once a subproblem is fathomed, we do not need to check it further.

We consider 3 fathoming tests:
1) If the solution to the LP relaxation of a problem/subproblem is an INTEGER solution, then we know that the entire solution to this problem/subproblem is as good as its gets. As a result, we have found the solution for this path.
We store the solution as the “incumbent”, z-star.

2) If the bound on some subproblem is lower than the current incumbent, we can fathom. this stems naturally from the fact that this path can never generate a solution as good as the one we currently have as our current best.

3) The third fathoming test is that we fathom is the subproblem’s LP relaxation has no feasible solutions. If the relaxed (LP relxation) has no solutions, then the original problem has no solutions as well.

General
We start the procedure by setting the incumbent equal to negative infinity.
We then perform initial bound and fahtoming tests.
Then we start branching and the iterations (if not immediatly fathomed due to integer solution on the first, original problem).

Question 44

What happens if we use BIP branch and bound and never find any incumbent?

Answer 44

No feasible solutions.

Question 45

What is the standrd approach to sovling MIP problems?

Answer 45

MIP branch and bound. Widely used

Question 46

Elaborate on the changes between BIP and MIP branch and bound

Answer 46

1) When we select branching variables, we only consider integer-restricted variables that have a non-integer value in the current LP relaxation of the subproblem we are currently looking at.

2) Regarding the values assigned to the selected branching variable: Previously (BIP) we fixed this value at either 0 or 1. Now, since integer, we use a range. How do we do this?
Say x1 is the current branching variable. Say x1-star is its value from the LP relaxation. We then use brackets notation [x1-star] to reference the “greatest integer” smaller than, or equal to, the x1-star value. So, this is the basis for the split:
One subproblem gets xj <= [xj-star], and the other subproblem gets
xj >= [xj-star]+1
This is done by adding these as constraints to the corresponding subproblems.

Recall that recurring branching variables is normal.

3) We cannot round down the bound anymore because some variables may not be integer-restricted. Of course, if PURE IP, we can round down.

4) With BIP, fathoming test x said that we fathom is the LP relaxation is integer-solution. Now with MIP, we modify this a little so that only the Integer-restricted variables must have integers in order to fathom.