LP extensions Flashcards
What is the motivation for treating the simple upper/lower bounds constraint differently from regular constraints?
we could use them like regular constraints, and add them as rows in the B matrix etc, but there are ways in which this is not needed. We can drastically reduce our computational requirements by doing this.
By doing this, we also remove a number of variables, which is also good.
What do we do if we have a lower-bound variable?
like xj >= lj
We perform a substitution:
xj^(new) = xj - lj
This new variable will have only non-negativity constraint.
elaborate on simplex with upper bounded variables
Technique that allows for more speedy simplex.
Works like this:
It works exactly like regular simplex, but with a tweak: We change the way we select leaving basic variable.
leaving basic variable is now a competition between the regular condition to reach 0 first, and the race for the entering basic variable to reach its upper bound first, or for some other upper bounded variable to reach their upper bound first.
If the first case happens, we continue like normal.
If the second or third case happens, we make whatever variable that reached first the leaving basic, and perform substitution xj^(bar) = uj - xj. This sub must be converted back when finished with procedure.
If the current entering basic variable happens to reach its upper bound before the other cases, this variable immediately becomes the leaving basic variable. Remember to add the substitution as well.
what are the conditions competing against each other to become leaving basic variable?
We want to smallest one.
t1 : regular ocndition
t2: up, same value as the upper bound. this case only applies when the variable p is the entering basic variable.
t3 : min(j) {(uj - xj) / dj}, where dj is the j part of the search direction.
what are the simplest types of constraints in an LP problem?
lower and upper bounds for a single variable.
These are simple in terms of whats involved, and we can leverage this simplicity to make a LP model procedure that is not as demanding in terms of the number of constraints included.
In a summarizing sentence, what is the “jist” of the upper bounded method?
The core idea is to use the same principle of non-negativity constraints, but with upper bound instead of lower bound.
Recall that regular lower bound (non-negativity) works by figuring out “only” what basic variable will reach 0 first. This is done with the minimum ratio test. Recall that the MRT works by considering the current value (x_b value) of a basic variable, and looking at the effect of increasing the value of the entering basic variable. if the basic variable has value 10, and the entering basic variable affect the basic variable by a factor of 2, it will take 5 steps until we reach the point where the specific basic variable becomes infeasible as a result of the increase in the entering basic variable. We naturally want to find which of the current basic variables that has the smallest step length until they become infeasible, as this will represent where our adjacent BFS is.
So, how does this relate to simplex for upper bounds?
We need to change the minimum ratio test so that we also test for these upper-bounded variables. We want to test for whether their upper limit is reached or not by increasing the selected non-basic variable as entering basic variable. So, in addition to finding the step length until infeasible for the regular basic variables, we need to find the step length until infeasible for the upper bounded variable.
Here is what we do:
If we have selected an entering basic variable that has an upper bound, we need to include the step length before it becomes infeasible. Since the variable with the bound is currently non-basic, it holds the value 0. Therefore, the feasible step length is equal to its upper bound limit value.
If we selected an entering basic variable, and we have other variables that are impacted by a change in the entering basic variable value, we also need to account for this. We dont need to care about the other non-basic variables, because their values remain at 0. we care about basic variables that are affected by changing the current entering basic variable. We need their step lengths before they become infeasible. We find the step length by considering the difference between the upper limit value and the current value of the basic variable, and then accounting for the specific rate of change by dividing the difference on the specific corresponding part in the search direction vector that corresponds to the basic variable we are interested in. We only need to make sure that the sign is flipped in regards to the search direction element that we use to divide the difference on.
if we selected leaving basic variable by upper bound limit, we perform a substitution: x^(bar) = upperLimit - x
This basically makes the new value 0.
what is a primal method?
A primal method iterates between feasible solutions. When it eventually reach a point that is both primal feasible and dual feasible, we have the optimal solution.
quickly describe a dual method?
A dual method is one that iterates between infeasible primal solutions, and when it reach a solution that is primal feasible, it is optimal.
Another way to say this is that it iterates between dual feasible solutions.
What is a benefit of the dual simplex method?
We can start from a previous otpimal solution, make some changes to coefficients etc, and continue solving from this point. Thus, we dont have to redo everything.
the dual simplex method is great in cases where we add another constraint to an already-optimal solution, and see that adding the constraint makes the solution infeasible, because dual simplex can use this infeasible point as a starting point, and make the assumption that this point is closer to the solution (by using dual simplex method) than starting the primal regular simplex from scratch
If we add a new constraint, and the current optimal solution becomes infeasible, what can we say about the situation?
The constraint will be binding. This means that its corresponding dual variable will be non-zero.
Say we add a new constriant. How many iterations will be required from the dual simplex method?
we cannot tell. May be 1, may be many.
Consider the dual simplex method. What do we do if we want to add an equality constraint?
We first add the corresponding inequality constraint that cuts away the optimal solution. Once the new optimal solution has been found using the dual simplex method, we remove the column representing the slack variable of the new inequality constraint.
The slack variable has the value 0 because it is binding in the new optimal solution. Removing this column has the effect that the constraint will always be satisfied with equality.
Elaborate on the procedure of dual simplex method.
Elaborate on the procedure of dual simplex method.
We start from the point where we finished the primal simplex, typically as a result of adding a constraint that made the solution become infeasible. Infeasible primal solution means that one of, at least, basic variables has a negative value, which is typically not allowed because we enforce all variables to be non-negative.
This starting point is dual feasible. if the point is not dual feasible, there are some artificial variable-tehcnoiques that can kickstart it.
Assuming a dual feasible (primal infeasible) starting point. We want to start the procedure:
Step 1) Check convergence crtierion. The point is an optimal solution if the solution is primal feasible.
Step 2) If not primal feasible, determine the leaving basic variable. We do so according to the criterion “x_k = min [j] {x_j | xj < 0}”
This basically means, we select the variable that has the largest negative value, which can be interpreted as the variable that is “most infeasible”.
This variable is now selected as leaving basic variable.
Step 3) Determine entering basic variable according to the following criterion:
“Choose x_p as entering basic variable when |c^(bar)_p / a^(bar)_sp| = min [j] {|c^(bar)_j/a^(bar)_sj|, | a^(bar)_sj < 0}”
This basically means: For all coefficients in objective function c, if the corresponding technology coefficient is smaller than 0, we fidn the minimum ratio of obj coefficeint and technology coefficeint. I suppose “s” refers to the row corresponding to the variable we selected as leaving basic variable in the step above.
The coefficient-technologyCoeff ratio with the smallest value is selected as entering basic variable.
IF there is no entering basic variable, which would mean that all the technology coefficeints are positive or 0, we have infeasible solution.
Step 4) rewrite the system as before. This means canonical form so that all basic variables are expressed as functions of only non-basic variables.
