Classification of optimization Techniques

optimization problems and optimization algorithms are included

1. Classification of optimization
Technique/methods/
Activity 2
Sheleme Mosisa Feyisa (PhD Candidate, MEng)
[email protected] Email:
Phone:[phone]

2. Content
Optimization problem
Optimization process
Solution methods of optimization problems
Optimization software

3. An optimization problem seeks to find the largest (the smallest)
value of a quantity (such as maximum revenue or minimum surface
area) given certain limits to a problem.
An optimization problem can usually be expressed as “find the
maximum (or minimum) value of some quantity Q under a certain
set of given conditions”.
Definition of Optimization problems

4. Problems that can be modelled and solved by optimization
techniques
Scheduling Problems (production, airline, etc.)
Network Design Problems
Facility Location Problems
Inventory management
Transportation Problems
Minimum spanning tree problem
Shortest path problem
Maximum flow problem
Min-cost flow problem

7. 1. Classical Optimization
Useful in finding the optimum solution or unconstrained maxima
or minima of continuous and differentiable functions.
Analytical methods make use of differential calculus in locating
the optimum solution

8. cont.…

Have limited scope in practical applications as some of them
involve objective functions which are not continuous and/or
differentiable.
Basis for developing most of numerical techniques that involved
into advanced techniques more suitable to today’s practical
problem

9. Three main types of problems can be handled:
Single Variable functions
Multivariable functions with no constraints,
Multiple functions with both equality and inequality
constraints
In problems with equality constraints the LaGrange multiplier method
can be used
If the problem has inequality constraints, the Kuhn-Tucker conditions can
be used to identify the optimum solution

10. Linear Program (LP)
studies the case in which the objective function (f ) is linear and the set design
variable space (A) is specified Using only linear equalities and inequalities.
(P) Easy, fast to solve, convex
2. Numerical Methods
https://stanford.edu/class/ee364a/

11. Optimization Problem Types
Non-Linear Program (NLP)
studies the general case in which the objective function or the constraints or
both contain nonlinear parts.
(P) Convex problems easy to solve
 Non-convex problems harder, not guaranteed to find global optimum

12. Optimization Problem Types
Integer Programs (IP)
studies linear programs in which some or all variables are constrained to
take on integer values
Quadratic programming
allows the objective functions to have quadratic terms, while the set (A) must be
specified with linear equalities and inequalities

13. Optimization Problem Types
Stochastic Programming
studies the case in which some of the constraints depend on random variables
Dynamic programming
studies the case in which the optimization strategy is based on splitting the
problem into smaller sub-problems.

14. 3. Advanced Methods
Swarm Intelligence Based Algorithms
Bio-inspired (not SI-based) algorithms
Physical and chemistry based algorithms
others

15. Solution Methods for Discrete Optimization Problems
Integer Programming
Network Algorithms
Dynamic Programming
Approximation Algorithms

16. Flow chart of algorithm Optimization Problems
An algorithm is a step-by step procedure
to solve a given problem
A flowchart is a type of diagram that represents
an algorithm or process
A pseudo code is a compact and informal high-level
description of a program.

https://www.youtube.com/watch?v=vOEN65nm4YU&list=PLG6eP
ePp5vvYVEjRanyndt7ZSqTzillom&index=1

17. Software for Optimization problems
EXCEL
PYTHON
MATLAB
.
.
https://www.youtube.com/watch?v=ATd0MZQGN7I&list=PPSV

18. EXCEL
Microsoft Excel solver is a powerful add-on tool to solve and analyze
optimization problems.
Solver can be used to adjust parameters in a model to best fit data, increase
profitability of a potential engineering design, or meet some other type of
objective that can be described mathematically in a spread sheet.

19. Example: problem optimization by EXCEL
This problem has a nonlinear objective that the optimizer attempts to minimize. The variable
values at the optimal solution are subject to (s.t.) both equality (=40) and inequality (>25)
constraints. The product of the four variables must be greater than 25 while the sum of
squares of the variables must also equal 40. In addition, all variables must be between 1 and 5
and the initial guess is x
1 = 1, x
2 = 5, x
3 = 5, and x
4 = 1.
??????��??????�??????�????????????:��� ??????
�??????
�??????
�+??????
�+??????
�+??????
�
??????�����????????????���:??????
�??????
�??????
�??????
�≥��
??????
�
�
+??????
�
�
+??????
�
�
+??????
�
�
=40
�≤??????
�,??????
�,??????
�,??????
�≤�
??????
�=(�,�,�,�)

https://www.youtube.com/watch?v=ATd0MZQGN7I&list=PPSV

20. Input and process

21. Output

23. EXCEL

24. Python can be used to optimize parameters in a model to best fit data, increase
profitability of a potential engineering design, or meet some other type of
objective that can be described mathematically with variables and equations.
Mathematical optimization problems may include equality constraints (e.g. =),
inequality constraints (e.g. <, <=, >, >=), objective functions, algebraic
equations, differential equations, continuous variables, discrete or integer
variables, etc.
Python

25. Example: Non-linear problem solving by Python
Objective: &#3627408485;
2
−3=0
Constraint:&#3627408485;
2
+&#3627408486;
2
=20
y=&#3627408485;
2

Variable= (x,y)

26. Reference
https://apmonitor.com/che263/index.php/Main/ExcelSolver
https://www.youtube.com/watch?v=ATd0MZQGN7I&list=PPSV
https://www.youtube.com/watch?v=vOEN65nm4YU&list=PLG6ePePp5vvYVEjRanyndt7Z
SqTzillom&index=1
Arora, J. (2012). Introduction to Optimum Design. In Introduction to Optimum
Design. https://doi.org/10.1016/C2009-0-61700-1
Zemmari, A., & Benois-Pineau, J. (2020). Optimization methods. SpringerBriefs
in Computer Science, 21–33. https://doi.org/10.1007/978-3-030-34376-7_4