OR

Question 1

Linear Programming

Answer 1

Overall goal: Minimize total system costs with respect to a given service level!

• Based on:
  
  • E.g: Location (strategical level)
  • Network Flows(tactical Level)
  • Routing(operational Level)

Definition:

• Linear optimization/linear programming (LP): Calculating the maximum/minimum if a linear objective function with respect to a set of linear constraints.

Question 2

Matrix Representation:

Answer 2

Question 3

Linear Optimization Features

Answer 3

Question 4

Simplex Graphical solving

Answer 4

Question 5

Single extreme point:

Answer 5

Question 6

Infinite optimum solutions:

Answer 6

Question 7

No feasible solution space

Answer 7

Question 8

No optimum solution - unbound space

Answer 8

Question 9

The Simplex Algorithm

Answer 9

• In the simplex method it is not necessary to examine all the feasible solutions (anyways, that would be impossible).
• It deals only with a small and unique set of feasible solutions, the set of vertex points (i.e., extreme points) of the convex feasible space that contains the optimal solution.
• The Simplex Method is computationally efficient, despite it is not theoretically efficient.

Question 10

Steps involved in simplex

Answer 10

• 1. Locate an extreme point of the feasible region.
• 2. Examine each boundary edge intersecting at this point to see whether movement along any edge improves the value of the objective function.
• 3. If the value of the objective function improves along any edge, move along this edge to the adjacent extreme point. If several edges indicate improvement, the edge providing the greatest rate of improvement is selected (other strategies possible).
• 4. Repeat steps 2 and 3 until movement along any edge no longer improves the value of the objective function.

Question 11

Integer programming

Answer 11

• (Linear) Integer problem (IP): Linear problem with only integer decision variables.

• (Integers can take negative and positive values, but not fractions and decimals)

• (Linear) Binary problem (BP): Linear problem with only binary decision variables.

• (Only 0 or 1, or x>= 0 <= 1)

• (Linear) Mixed-integer problem (MIP): Linear problem with both continuous and integer/binary decision variables.

Question 12

The Knapsack Problem

Answer 12

see the one note part

Question 13

Classification of solution methods

Answer 13

Optimization methods

Optimization methods need to be able to solve problems give enough computational time and enough memory.

For Linear Programming problems:

• Simplex Algorithm
• Interior point Method

For Integer P/ and MIP

• Branch and bound algorithms
• Branch and cut algorithms

Heuristics

Heuristics aim to find a good solution with acceptable effort

• Solutions are at least feasible, but not necessarily optimal
• Even in case that a heuristic has found an optimum solution, its optimality can neither be recognized nor proven

Examples

• Optimization methods which are interrupted after a certain solution time.
• Classic heuristics (local search): problem specific approach
• Metaheuristics (tabu search, simulated annealing): non problem-related approach

Question 14

Branch and Bound algorithm

Answer 14

• When the problem to solve requires solutions as integers, the use of the Simplex Algorithm becomes no longer feasible even if the solution to the objective function is good optimized.
• For this is necessary to reduce the solution space to just the integer solution available.
• The branch and bound algorithm round the solutions to the factors down to integers and calculates with this the so called lower bound.
• The Upper bound remains as the solution from the relaxed problem, since for this problem there is no better integer solution than this.
• The lower bound (LB) is (always) a feasible solution (in a maximization problem).
• If two of more of the factors have decimals, then the highest factor will be taken for the branching.
• Now since the solutions have to be Integers we need to define that for example: if =2.3 then our new branches will take the values . This are the new branches for the optimizatio problem, and we will try to find the one that maximizes Z the most but at the same time gives us an integer solution.
• The two new problems will be also Relaxated(solved by Simplex for example) in order to find two new solutions. In this case the new factor will be added to the constrains in order to solve the problem.
• if one of these Solutions give us already a integer solution we can take this as the “Lower Bound Solution” but still the algorithm will search the other path for better solutions until these become at some point infeasible, or we reach decrease the gap between Lower and Upper bound

Question 15

Cutting Plane method

Answer 15

In the cutting plane method the solution space will be reduced in order to fit only the integer feasible solutions. This is done by adding additional constraints to the problem where there is no integer solution e.g.

• It is (numerically) not easy to find good cuts, which reduce solution space quickly enough.
• Therefore sophisticated approaches combine branch-and-bound with cutting planes to a “Branch-and-cut”- approach..