Lesson 1

Question 1

General problem - solving method

Answer 1

1. Problem § data
   - Identification of a real-world problem (Precise problem statement, objectives and constrains, interrelations)
   - Gather data
2. Model
   - Formal model building (Mathematical model, optimization model (Decision variables, objective function, constrains, parameters))
   - Decision about detail level
3. Method (Identify the best possible solution)
   - Standard approach or
   - Customized solution method
4. Application (Model validation)
   - Evaluation of solution
   - Application to original problem

Question 2

Scientific process of transforming data into insights to improve decisions

Answer 2

• Descriptive (What is happening?; locate and retrieve relevant data; data mining)
• Diagnostic (Identify patterns, understand what is going on; data mining)
• Predictive (Predict what will happen in the future; statistical forecasts)
• Prescriptive (Using data to prescribe what should be done in the future; Optimization using OR)

Question 3

Applications of linear problem?

Answer 3

1. Allocation of limited resources among competing activities.
2. Maximum/minimum of linear objective function with respect to a set of linear constrains

Question 4

Linear Optimization - Properties

Answer 4

1. Proportionality (The contribution of each activity to the value of the objective function 𝑍 is proportional to the level of activity 𝑥j)
2. Additivity (Every function in a linear program is the sum of the individual contributions of the respective activities)
3. Divisibility (Decision variables are real numbers (𝑥𝑗 ∈ ℝ) and can therefore provide fractional values)
4. Certainty (All model parameters are known and constant)

Question 5

What is the solution, feasible solution, infeasible solution, optimal solution?

Answer 5

• A solution is any specification of values of the decision variables
• A feasible solution is a solution in which all constraints (functional + nonnegativity) are satisfied.
• An infeasible solution is a solution which violates at least one constraint.
• An optimal solution is a feasible solution that provides the most favorable value (maximum or minimum) for the objective function.

Question 6

The feasible region, optimal solution, a corner point feasible solution?

Answer 6

• The feasible region is the collection of all feasible solutions.
• The optimal solution must consequently lie within the feasible
  region.
• A corner point feasible solution (CPF) is a solution which lies
  at the corner of the feasible region.
• In case that a LP has an optimal solution, it also has a CPF optimal solution!
• CPF solution are adjacent to each other if they share n-1 constrain boundaries.

Question 7

Algebraic approach

What is augmented solution
What is the basic solution?
What is a basic feasible solution?

Answer 7

• An augmented solution is a solution for the original variables that has been augmented by the corresponding values of the slack variables.
• A basic solution is an augmented corner-point solution.
• A basic feasible solution (BF) is an augmented CPF solution.

Question 8

Properties of the basic solution

Answer 8

1. Each variable is designated either nonbasic or basic.
2. The number of basic variables is equal to the number of functional constraints.
3. Nonbasic variables are always equal to 0.
4. The values of the basic variables can be obtained by solving the system of constraints (equations).
5. The set of basic variables is referred to as “the basis”.
6. If the basic variables satisfy the nonnegativity constraints, the basic solution is a BF solution.

Question 9

Duality properties

Answer 9

1. Weak duality property

𝒄𝑇 𝒙 ≤ 𝒃𝑇 y

2. Strong duality

𝒄𝑇 𝒙= 𝒃𝑇 𝒚

Question 10

Applications of duality theory

Answer 10

1. Computational effort: The number of functional constraints affects computational effort of the simplex method much more than the number of decision variables
2. Optimality test:
   - If 𝒄𝑇 𝒙 = 𝒃𝑇 𝒚 both solutions are optimal
   - if 𝒄𝑇 𝒙 < 𝒃𝑇 𝒚 applies instead, 𝒃𝑇 𝒚 is an upper bound
   of the optimum solution in the primal problem.
   - If the gap 𝒃𝑇 𝒚 − 𝒄𝑇 𝒙 is small, we can still accept 𝒙 as an almost optimum solution

Question 11

Sensitivity analysis

Answer 11

Sensitivity analysis help to know to which extent it is possible to change values of A, b or c such that the current optimal solution remains optimal.

Question 12

Integer optimizatiin

• Integer variables?
• Binary variables?

Answer 12

1. Integer variables (Variables which may not represent fractional values, such as number of trucks, cars, number of plants, warehouses)
2. Binary variables (limited domain:
   ▪ Variables which can only be 0 or 1.
   ▪ Useful for “yes/no”-decisions.

Question 13

Classification of solution methods

Answer 13

1. Optimization methods are able to find the optimum
solution of a problem given enough time and memory to
solve.
For Linear programming:
- Simplex algorithm
- Inner point algorithm
For IP/MIP problems:
- Branch-and-bound algorithms
- Branch-and-cut algorithms

2. Heuristics aim to find a good solution with acceptable
   effort (Solutions are at least feasible, but not
   necessarily optimal)
   - Classic heuristics
   - Metaheuristics

Question 14

Branch and Bound solutions

Answer 14

• A “lower bound” can be generated by rounding x1 and x2
  to the next lower integer value
• The lower bound (LB) is (always) a feasible solution (in a
  maximization problem).
• As a next step, we are picking the subproblem with the highest upper bound, since we have here the highest chance for a good solution
• Variable with the greatest fractional part should be branched
• Solution is infeasible, if for example in the previous branch we have x >= 6, and right now x>=2.

Question 15

Optimization gap

Answer 15

• During the optimization approach, the algorithm tries to reduce the
  optimization gap (between upper and lower bound) to zero.
• Only in case that the gap is zero, we can be sure to know the
  optimal solution.
• If there is still a gap left, we only have an estimation of the
  solution quality (in a worst case)

Question 16

Optimization studio advantages

Answer 16

–Among those advantages are to model and solve big LPs or
MIPs with thousands of variables and constraints,
–as well as to be able to separate model description and
parameters/data.