Lesson 1 Flashcards
1
Q
General problem - solving method
A
- Problem Β§ data
- Identification of a real-world problem (Precise problem statement, objectives and constrains, interrelations)
- Gather data - Model
- Formal model building (Mathematical model, optimization model (Decision variables, objective function, constrains, parameters))
- Decision about detail level - Method (Identify the best possible solution)
- Standard approach or
- Customized solution method - Application (Model validation)
- Evaluation of solution
- Application to original problem
2
Q
Scientific process of transforming data into insights to improve decisions
A
- 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)
3
Q
Applications of linear problem?
A
- Allocation of limited resources among competing activities.
- Maximum/minimum of linear objective function with respect to a set of linear constrains
4
Q
Linear Optimization - Properties
A
- Proportionality (The contribution of each activity to the value of the objective function π is proportional to the level of activity π₯j)
- Additivity (Every function in a linear program is the sum of the individual contributions of the respective activities)
- Divisibility (Decision variables are real numbers (π₯π β β) and can therefore provide fractional values)
- Certainty (All model parameters are known and constant)
5
Q
What is the solution, feasible solution, infeasible solution, optimal solution?
A
- 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.
6
Q
The feasible region, optimal solution, a corner point feasible solution?
A
- 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.
7
Q
Algebraic approach
What is augmented solution
What is the basic solution?
What is a basic feasible solution?
A
- 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.
8
Q
Properties of the basic solution
A
- Each variable is designated either nonbasic or basic.
- The number of basic variables is equal to the number of functional constraints.
- Nonbasic variables are always equal to 0.
- The values of the basic variables can be obtained by solving the system of constraints (equations).
- The set of basic variables is referred to as βthe basisβ.
- If the basic variables satisfy the nonnegativity constraints, the basic solution is a BF solution.
9
Q
Duality properties
A
- Weak duality property
ππ π β€ ππ y
- Strong duality
ππ π= ππ π
10
Q
Applications of duality theory
A
- Computational effort: The number of functional constraints affects computational effort of the simplex method much more than the number of decision variables
- 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
11
Q
Sensitivity analysis
A
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.
12
Q
Integer optimizatiin
- Integer variables?
- Binary variables?
A
- Integer variables (Variables which may not represent fractional values, such as number of trucks, cars, number of plants, warehouses)
- Binary variables (limited domain:
βͺ Variables which can only be 0 or 1.
βͺ Useful for βyes/noβ-decisions.
13
Q
Classification of solution methods
A
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
- Heuristics aim to find a good solution with acceptable
effort (Solutions are at least feasible, but not
necessarily optimal)
- Classic heuristics
- Metaheuristics
14
Q
Branch and Bound solutions
A
- 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.
15
Q
Optimization gap
A
- 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)
