Chapter 12 - Integer programming Flashcards
What is the key limitation of linear programming
Requirement of divisibility
Define an Integer programming problem (IP)
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.
What happens if we have some decision variables that has divisibility properties and some that require integers?
We call it a mixed integer programming (MIP) problem.
What applications do we have with integer programming?
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.
Formally define a binary decision variable
x_j = [1 if decision j is yes], [0 if decision j is no]
What is a mutually exclusive constraint, and how do we represent it?
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
What are contingent constraints, and how do we represent them?
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
what is the benefit with binary integer programming vs pure integer programming?
binary are easier to deal with, can usually solve lots bigger problems
elaborate on fixed investments problems
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.
elaborate on fixed charges
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]
IN what scenarios could investment analysis use BIP?
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).
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
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.
How can we make an “either-or” constraint?
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.
Say we have N constraints and K of them must hold. How do we represent this?
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
Elaborate on relaxation in regards to IP
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.
Whats a mixed integer programming model? MIP
The case where some variables have the integer-restriction while some others have the divisibility-legality.
What is the divisibility assumption+
The divisibility assumption is that we assume that decision variables can have values that are not integers.
What is a BIP problem?
Binary Integer Programming problem. Problems that ONLY contain binary variables are sometimes called BIP.
IMPORTANT:
Name the different types of “binary restrictions”
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
Elaborate on binary representation of general integer variables
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.
Why is it natural to consider some kind of enumeration strategy to solve IP problems?
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.
How do we progress iterations on branch-and-bound?
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.
Why does the BIP branch and bound use “most recently created subproblem” instead of “best bound” to progress the procedure?
Because it can continue the use of ONE simplex tableau along a path. This allows for large-scale implementation.
Elaborate deeply on branch and bound on a general MIP problem
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..
