The basics of LP Flashcards
Define a search method
A search method is a solution procedure that iteratively move from point to point where each new point will improve the value of the objective function. A general search method will find a local optimum.
Simplex is a search method.
in some search methods, the obj func value may be the same between two consecutive iterations.
What is the formula that determines the sequence of points we get from a continuous search method?
x^(k+1) = x^(k) + t^(k)d^(k)
d is a search direction, t is a step length. NOTE: it only applies to continuous problems
What distinguish one search method from another?
The way in which the step length and the search direction is selected. Every search method use the previous point as starting point, but the step length and search direction may differ.
What is usually common among various search methods?
it relates to the step length and the search direction.
it is common that the search direction is a “feasible search direction”. with “feasible” we mean that it should be possible to make a very small step in the direction without moving out of the feasible region. In other words, there must exist a small value t^(bar), such that x^(k)+t^(bar)d^(k) is in X, for all t in 0<t<t^(bar).
It is also common that the search direction is “an improving search direction”. This means that we usually expect that the search direction is picked because it will improve our objection function value.
Elaborate on the principles of search direction and step length in regards to IP problems
For integer problems, it is much more difficult to use these principles, since IP problems are not continuous.
Instead, we must check all neighbors of a current point. If one of the neighbors are better, we move there.
What is a very important point regarding IP problems
they are non-convex. This means that using a regular search method will only guarantee local optimum, and nothing more. This is not good enough for us, so such methods are no-go
Elaborate on how to find search directions
Search direction is a play between basic and non basic variables.
It is easy to determine the direction of the non-basic variables. The difficult part is the direciton of the basic variables.
However, to find these, we use the constraint matrix and set up all the basic variables as functions of non-basic variables. From those, we can easily see how the basic variables change from a unit change in one of the non basic variables.
This is information that will be provided in each step of the simplex tableau as well.
what is important regarding finding the search direction?
We must remember that the non-basic variables that we do NOT PICK as entering basic variable, will always have a search direction of 0. This is because we will not relax their constraints. We are moving along them.
What happens if we have a search direction that is all non-negative?
The problem is unbounded.
