Simplex, LP, duality, extensions Flashcards

1
Q

Elaborate on search methods

A

A search method iteratively finds better and better solutions to a problem.

They typically start from a feasible solution to the problem.

When no better point can be found, a local optimum is determined.

The objectuve function value will be better or equal to the previous iteration value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

elaborate on search methods for continuous problems

A

key about continuous problems, is that the search sequence of points is given by the following formula:

x^(k+1) = x^(k) + t^(k)d^(k)

t is the step length.
d is the vector that describe the direction we move in. In other words, we want to find the vector d that says “we move in this direction”. In LP and simplex, this will basically mean that we consider increasing a variable by one unit, and looking at what the other variables respond with.

In general, we say that the search direction d, and the step length, can define many search methods.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is common for almost all search methods in regards to the search direction?

A

The search direction is feasible. this means that it should be possible to take a very small step in the direction (step s for all values between 0 and s) and keeping the solution feasible.

Also, the search direction should improve the value of the objective function.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Elaborate on searhc methods for integer programming problems

A

The case here is that we cannot use the concept of step length and search direction. Instead, we are talking about neighboring solutions. We search the space of neighboring solutions until we have local optimum.

it is absolutely key to remember that IP problems are non-convex. This means that any local optimum cannot be guaranteed to be global optimum. Therefore, those problems are more difficult to solve than LP problems.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

what can we say about the feasible region of an LP problem?

A

The feasible region of an LP problem is a convex set.

PROOF:

we consider two arbitrary points x^(1) and x^(2) that are feasible with regards to constraint i,

∑aijxj^(1) <= bi,
∑aijxj^(2) <= bi

Then we consider a third point that lie somewhere between (on the line) x^(1) and x^(2), which we use lambda to find:

x = (1-L)x^(1) + Lx^(2)

Now we want to see if x is inside the region as well.

We multiply the first inequality by (1-L) and the other by L.

(1-L)∑aijxj^(1) + L∑aijxj^(2) <= (1-L)bi + Lbi

(1-L)∑aijxj^(1) + L∑aijxj^(2) <= bi

∑aijxj^(1)(1-L) + aijxj^(2)L <= bi

∑aij ((1-L)xj^(1) + Lxj^(2)) <= bi

now we have proved that the arbitrary middle point is also inside the constraint region.

Then we also make use of the fact that there is a theorem saying that the intersection of convex sets is a convex set itself. Therefore, we can conclude that the feasible region of LP problems are convex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

When is a basic solution to the system of equation Ax=b obtained?

A

A basic solution is obtained if n-m variables are set to 0 and the remaining variables get their unique values when we solve the remaining mxm system.

The variables that we set to 0 are called non-basic variables.
the other are called basic.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the requirement for there to exist a basic solution in the remainng mxm system?

A

The columns must be linearly independent.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How many constraint needs to be active to define a vertex?

A

n-m.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

what is required to uniquely define a vertex?

A

Every basic feasible solution corresponds to a unique vertex. Therefore, we can uniquely define a vertex by setting non basic variables equal to 0.

it is worth noting that a vertex can hold SEVERAL basic solutions, but a basic solution can only represent a single vertex.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Two vertices are adjacent if …

A

the set of active constraints in the two point differ in one element only

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Two basic solutions are adjacent if …

A

They have m-1 basic variables in common

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

From some basic solution, how to find the set of search directions?

A

The set of search directions is defined by those directions that are obtained if for each of the active constraints, we release the condition that this constraint should be active, and let the corresponding non-basic variable increase its value from 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

how do we find reduced cost of a searc hdirectoin

A

c = C^(T)d

If c > 0, the search direction “d” is ascent direction
if c < 0, the search direction d is descent direction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What does reduced cost tell us?

A

The reduced cost tells us how much one unit increase of some variable changes the objective function value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What happens if no value id d is negative?

A

We have an unbounded solution

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

how can we interpret the re-writing of the system of equations?

A

Making row operations on the original system of equaitons so that we obtain IDENTITY VECTORS in the columns corresponding to the NEW basic variables.

this is done through a pivot operation.

A pivot operation works by selecting the pivot row, which is the row that contains the leaving basic variable. Arrange the equations so that we have a coefficient of “1” i nfront of the new basic variable in the pivot row. Typically done through multiplication.

Then we arrange the equations so that we obtain zeros in all other positions in the new basic variable column.

The whole point of doing the pivot operation is that the result is a system where everything is expressed in terms of non-basic variables. this makes reduced costs easy to interpret, and changes to non-basic variables also become easy to interpret.

17
Q

explain the step-by-step process of the simplex method

A

Step 0: Start from a basic feasible solution, x^(0). Let k=0.

Step 1: Determine all possible search directions and reduced costs cj^(bar) for all the non-basic variables.

Step 2: Check the convergence critereon. The point x^(k) is optimal if cj^(bar) >= 0, for all j (minimization)
or
cj^(bar) <= 0, for all j (maximization)
for all non-basic variables.

Step 3: Determine the entering basic variable according to the crieteria of “largest cj^(bar) is max, smallest cj^(bar) is min”

Step 4: Determine step length by t^(k) = x^(k)_r / -d_r^(k) = min j{x^(k)_j / -d^(k)_j | d^(k)_j < 0}

if all componenets in d^(k) are non-negative, the problem becomes unbounded/is unbounded.
Recall that xj becomes leaving basic variable. The who ppoint is to find the basic variable that has a value that makes it go to its boundary quikest.

Step 5: New point is found, regular search method formul,a go back to step 1 with k+=1

18
Q

What change in consideration to min vs max problems?

A

The convergence criterion change, and the way we select entering basic variable change. All other things, like choosing leaving basic variable, remains the same.

19
Q

given LP problem in standard form, what is the first step in terms of the matrix notation

A

The first step is to partition everything into its corresponding basic and non basic parts. What variables we consider to be basic and non-basic is completely determined by our own choice, and in terms of simplex, it is determined by wherever we currently are in the searching method.

We split the variables x into two parts: x = (xb xn), where xb is the basic variables and xn are the non basic variables.

We do the same with the constraint matrix A = (B | N)

B consists of the columns in A that belong to basic variables, and N of non basics.

We also partition the objectiuve function coefficients into cb and cn.

The result is:

max z = cb^T xb + cn^T xn
st. Bxb + Nxn = b
and xb, xn >= 0

20
Q

Given the partitioned LP problem, what is the next step in terms of matrix notation?

A

We have selected basics and non-basics, and partitioned the problem into those parts. Now we want to solve the system so that we find the solution, which is the basic solution.

To do this, we make use of the fact that we want the basic variables (non basics set to 0, trivial to find). Therefore, we are interested in the constraints:

Bxb + Nxn = b

However, as we have sat xn = 0, for all the variables in xn, we actually have:

Bx_b = b

This we can solve with the inverse of B, B^(-1)

x_b = B^(-1)b

So, we know that multiplying by B^(-1) from the left will solve the system. Therefore, we know it will also solve the larger system that includes Nx_n:

x_b + B^(-1)Nx_n = B^(-1)b

IF we somehow knew that this solution was optimal, we would be done as the x_b values are completely known. However, we usually do not know this. Therefore, we must perform the convergence criterion, which requires the objective function to be in canonical form. How to we get it there? We use the result we found to swap some valuies.

Recall the objective function row:

max z = cbxb + cnxn

We have an expression for xb, which we use here:

max z = c_b (B^(-1)b - B^(-1)Nx_n) + c_n x_n

max z = c_b B^(-1)b - c_b B^(-1)Nx_n + c_n x_n

max z = c_b B^(-1)b + (c_n - c_b B^(-1) N) x_n

Now we have expressed the objective function row as a function of only non basic variables. The coefficient of the x_n part gives us the vector of all reduced costs. The constant term is the current objectve funciton value.

we can now use this row to determine if the current solution is optimal or not. Since it is a maximizaation provblem, it is optimal if the reduced cost vector has only negative or 0 entries.

21
Q

Given a partition of variables and all that, give the simplex tableau at initial iteration

A

Col 1: BV, z, x_s
Col2: z, 1, 0
Col3: x_b, -c_b, B
Col4: x_n, -c_n, N
Col5: x_s, 0, Identity (OPTIONAL)
Col6: RHS, 0, b

22
Q

Given the partition of variables and all that, give the simplex tableau after we have solved for x_b

A

col1: BV, z, x_b
col2: z, 1, 0
col3: x_b, 0, identity
col4: x_n, -(c_n - c_bB^(-1)N), B^(-1)N
col5: x_s, c_bB^(-1), B^(-1)
col6: RHS, c_bB^(-1)b, B^(-1)b

23
Q

what happens with regards to matrix notation if one of the constraints have the type of >=?

A

The corresponding column in the B^(-1) matrix will have flipped signs in all coefficients

24
Q

What happens with regards to matrix notation if one of the constraint have th etype =?

A

The correspondingf column in B^(-1) is missing

25
Q
A