Introduction, LP

Question 1

What will the constraints hit?

Answer 1

Constraints are restrictions on the DECISION VARIABLES.

Question 2

What is the purpose of the objective function?

Answer 2

To describe the objective. The objective is typically an economic or technical problem.

Question 3

What is a pre-requisite for using optimization models?

Answer 3

The objective, and the constraints, must be able to be described quantitatively using mathematical functions and relations.

Question 4

What is an assumption regarding optimization models in real life?

Answer 4

We assume that the number of variables and constraints are LARGE, so that we need computer power and algorithms that are efficient in order to actually find the optimal solution.

Question 5

Define programming

Answer 5

It means planning, and refers to creating a plan for how to do shit.

Question 6

What is the history of OR?

Answer 6

Operaitons research originates from WW2. Breakthrough methods originates from 1947 (Simplex method from George Dantzig)

Question 7

what do we call short term planning?

Answer 7

Operative, or operational

Question 8

what do we call long erm planning?

Answer 8

Strategic, tactical.

Lecturer says that strategic allows for all kinds of infrastructure changes.
Tactical allows for minor tweaks.
Operational allows for no changes.

Question 9

Define the optimization process

Answer 9

We begin with a “real problem”. Can be extremely complex, and there will likely be aspects in it that we do not include further. This is most likely due to how dofficult it would be to add to the model.
The first phase is therefore about identifying the real problem, and find the relevant components.

NB: An essential part about this step, that is often neglected, is to determine whether it is necessary to set up an optimization model at all. Sometimes, there are alternative approaches. There will be a large focus on the fact that shit is quantifiable.

The result of this filtering process is that we now have the simplified problem.

We now take the simplified problem and transforms it to the mathematical description. We are now talking about decision variables, parameters, constraints, objective function. In this step, we might have to make further simplifications to the problem. For instance, the problem size can cause trouble in real life.

Now we have the optimization model.

The next step is to take the model, and solve it using some method.

When solved, we need to check whether the solution is correct/test the model for potential errors. This is called model validation.

The next step is to perform sensitivity analysis to better understand the solution.

Only now, we have the result.

Question 10

how do we denote an optimal solution

Answer 10

x*

Question 10

What is the most general way of describing the optimization problem mathematically?

Answer 10

min f(x)

st. x in X

where X is the set of feasible solutions.
f is the optimization function.
x is the vector/set of decision variables.

We usually, however, describe the constraints a little bit differently:

st. gi(x) <= bi

to highlight the fact that the model has constraints on this shape, and not just a set of feasible values. However, the first general one is also 100% correct.

Question 10

There are two types of optimization methods…+

Answer 10

Exact methods

Heuristics.

Exact methods finds the optimal solution.
Heuristics find soltuions that are good enough

Question 11

How do we denote the optimal objective function value?

Answer 11

z*

Question 11

Define an optimal solution

Answer 11

An optimal solution is a set of values x in X that minimize (or maximize) f(x).

Question 12

Convertion between max and min is?

Answer 12

to maximize a problem is the same as minimizing the negative of the other problem.

For instance, consider:

max x+y

this problem get a better value when x and y grow large.

min -(x+y)

this problem gets a better value when x and y grow large.

They are identical.

Question 13

what do we mean by halfspace?

Answer 13

halfspace is a part of the space. We usually use halfspace to talk about the feasible side of the space as given by a constraint.

Question 14

The intersection of all halfspaces is called…?

Answer 14

The feasible region, which we usually call X.

Question 14

WHat is noteworthy on infeasibility

Answer 14

it is never by the objective function, but always on the constraints.

Question 14

A constraint that does not affect the feasible region is called …?

Answer 14

Redundant.

We can add that if the constraint affects the feasible region, but not in the optimal solution, we call it “redundant in optimum”.

Question 14

The constraints that are satisfied with equality in the optimal solution are called…?

Answer 14

Active, or binding constraints.

Question 15

Elaborate on global optimum vs local optimum, and define the neighborhood for continuous problems

Answer 15

We say that a feasible point x^(k) is a global optimum if f(x^(k)) >= f(x) for all x in X (max problem, opposite if min).

The same applies for local optimums, but we need to define the area/neighborhood in which the feasible point is a local optimum.
We do this by having “for all x in X and x in N(x^(k))”, where N is a function that defines a certain neighborhood.

For continuous problems, a neighborhood can be defined as

N(x^(k)) = {x | abs(x^(k) - x) < const e, const e > 0}

Question 16

Can a set be concave?

Answer 16

No. A set is either convex or non-convex

Question 16

What is the use of a convex problem?

Answer 16

A convex problem has the property that a local optimum is also global.

Question 16

What is a search method?

Answer 16

A search method use information about the problem or the functions in the close neighborhood of current points to search towards optimum. Classical local-optimum finder.

Question 16

What is a concave problem?

Answer 16

There is no such thing. A problem is either convex or non-convex.

Question 17

When is it easy for search methods to find global optimum?

Answer 17

When we can guarantee that the local optimum is in fact a global optimum as well.

Question 18

Define a convex problem

Answer 18

The problem

min f(x)

s.t. x in X

is convex if f(x) is a convex function and X is a convex set. A problem is also convex if it is a maximization problem and the function f(x) is concave and X is a convex set.

Question 19

Elaborate on the general procedure of a search method

Answer 19

A search method starts from a known feasible point, which we call a solution to the problem. It is a solution, but not necessarily the optimal solution.

The procedure then iteratively make moves to new points with improving objective function values. When no better point can be found (according to the objective function), a local optimum has been found.

So, given the general problem

min f(x)
s.t. x in X,

the search method will generate a sequence of feasible points whose objective function values become successively better.

In some search methods, the objective function value may be the same between two consecutive iterations.

It is an iterative process, and to highlight that fact, we can specify the next point recursively:

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

t^(k) is a step length/size.
d determines the direction of the step size.

Question 19

Discuss whether LP, IP or non-linear are convex

Answer 19

LP is always convex, due to the fact that the optimization function is linear, and linear functions are always both convex and concave.
Its constraints follow the same logic.

IP is always non-convex.

non-linear can be either.

Question 19

what is the search criterion?

Answer 19

The search criterion is the search direction, d^(k).

Question 20

Give the formal definition of a convex function

Answer 20

A function f(x) is convex on the feasible region X if for all choices of points x^(1) and x^(2) in X, and 0<= lambda<= 1, we have that :

f(lambda x^(1) + (1-lambda)x^(2)) <= lambda f(x^(1)) + (1-lambda) f(x^(2))

Basically, what this says is that all points between the selected points must lie under the straight line going from one point to another.

Question 20

Define a convex set

Answer 20

A set X in R^n is a convex set if for any pair of points x^(1) and x^(2) in X and 0<= lambda <= 1, we have:

x = lambda x^(1) + (1-lambda) x^(2) in X

Basically, it means that the line between any two points in the set X must be completely inside of the set X as well.

Question 21

discuss primal vs dual methods

Answer 21

Primal methods are based on the principle that in each iteration we have a feasible solution, and that we iteratively generate solutions with better and better objective function values until we stop in a local (possibly global) optimum.

Dual methods dont work like that. Their principle is to move between infeasible points in a systematic way, and ultimately in the last iteration find a feasible solution. However, we then know that this solution is local (possible global) optimum.

Question 22

Define a polyhedron

Answer 22

A polyhedron is a shape that has straight edges and sharp corners.

In LP, we typically use polyhedrons to describe feasible region.

The intersection of half spaces (divided by hyperplanes) is called a polyhedron. We can mathematically define a polyhedron like this:

H = {x | ∑aij xj <= bi, i=1,2,…,n}

Question 23

Define a hyperplane

Answer 23

A hyperplane is a set H that consists of all points x in R^n that satisfy the equation ∑ajxj = k. In R^2 we call a hyperplane a line. In R^3 we call it a plane.

We further say that a hyperplane divides the space into halfspaces.

Question 24

Define a convex combination of a set of points

Answer 24

A convex combination of the points x^1 etc… is a new point x such that

x = ∑lamba j x^(j) [j=1, n]
and ∑lambda j [j=1, n] = 1,
and lambda j >= 0.

In other words, a convex combination is the same as the definition of convex point, but it generalize to multiple points. Each point drag in a direction with a weight.

every point satisfied by the convex combination is also convex. This means that a convex combination defines a convex set.

Question 25

Define an extreme point in a set X

Answer 25

The point x^(k) is an extreme point in X if it is not possible to express x^(k) as a strict (0 < lambda < 1) convex combination of two points in X

Question 26

What is the fundamental theorem of linear programming?

Answer 26

Assume that the feasible region X of an LP problem is unbounded and non-empty. Then the minimum value of the objective function cx is obtained in (at least) one extreme point.

PROOF,

Suppose that the opposite is true. We have a point x^(hat) that is a better point (smaller) than an extreme point x(k).
Since x^(hat) is a convex combination of the extreme points of the feasible region, we can write:

x^(hat) = ∑lambda k x^(k), where ∑lambda j = 1.

Then we have:

cx^(hat) = c∑lambda k x^(k) = ∑lambda k cx^(k) > ∑lambda k cx^(hat) = cx^(hat)∑lambda k = cx^(hat)

which is a contradiction.

Question 27

what could be the interpretation of a positive slack variable?

Answer 27

rhs resource amount not yet utilized

Question 28

negative slack variable means

Answer 28

the current point is not feasible

Question 29

say we have a constraint like this:

x <= 0,

how do get to standard form?

Answer 29

we add new variable, y, and say that

y = -x

and y >= 0

Question 30

why do we care about standard form?

Answer 30

It is adventaguous to have standard form when doing math on the problem

Question 31

how do we create equality constraint from a >= constraint?

Answer 31

we must subtract a surplus (no negative) variable.

Question 32

a vertex is characteruzed by that it lies on an intersection of constraints. But how many constraints are required to define a vertex uniquely?

Answer 32

n-m.

n is the number of variables in standard form.

m is the number of constraints.

i.e. we must have n-m number of variables equal to 0, nonbasic, to uniquely define a vertex.

Question 33

Define a basic solution to the system of equations Ax = b

Answer 33

A basic solution to the system of equations Ax=b 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 of equations.

The variables that are set to 0 are called nonbasic.

The variables that are among the remaining m variables are called basic variables.

Question 34

When does a basic solution exist?

Answer 34

A basic solution exists if the columns in the remaining (mxm) matrix are linearly independent.

Question 35

Every basic feasible solution correspond to a …

Answer 35

… unique vertex to the feasible region.

however, a single vertex can represent multiple basic feasible solutions.

Question 36

What is the relation between BFS and vertices?

Answer 36

The relationship is that a BFS has one and only one vertex, while a vertex can have multiple BFS.

Question 37

What do we call a basic solution in which one or more basic variables have the value zero?

Answer 37

A degenerated basic solution.

Question 38

For a general LP problem, how many basic solutions are there?

Answer 38

This is a combinatorial problem.

nCm = n! / (m! (n-m)!)

Question 39

The simplex method searches for …

Answer 39

the basis that give the best value according to the given objective function

Question 40

Define adjacency of basic solutions

Answer 40

Two basic solutions are adjacent if they have m-1 basic variables in common.

Except for degeneracy, where things are a little different.

Question 41

What do we mean by a change of basis?

Answer 41

Change of basis refer to changing one basic variable with a non-basic variable, and changing their status.

The new basic variable is called the entering basic variable, and the old basic variable is called leaving basic variable.

Question 42

From a given BFS, how many search directions are there?

Answer 42

We have n-m non-basic variables. These represent search directions. Therefore there are n-m search directions.

Question 43

Define reduced cost mathematically

Answer 43

We can calculate the reduced cost in the point x^(k) when we move in direction d as:

c^(bar) = gradient(f(x^(k)))d = cd

if c^(bar) > 0, the search direction d is an ascent direction

if c^(bar) < 0, the search direction d is a descent direction.

The reduced cost tells us how much the objective function change from a unit increase in x.

Question 44

What is the downside of using less indices to describe (mathematically) our decision variables?

Answer 44

Altough the number of decision variables would remain the same, we will get more difficulty in making the constraints.

More indices on the decision variables also make the model more generalizable.