Module 1.pptx

OPTIMIZATION METHODOLOGIES 20CS2037 Introduction & Elementary concepts Mrs.S.V.Evangelin Sonia Assistant Professor Division of Computer Science Karunya Institute of...

OPTIMIZATION METHODOLOGIES 20CS2037 Introduction & Elementary concepts Mrs.S.V.Evangelin Sonia Assistant Professor Division of Computer Science Karunya Institute of Technology and Sciences Agenda › Syllabus › Why Optimization Methodology? › Elementary Concepts in Optimization Methodology › Examples Syllabus Course Objectives: Enable the student to › understand the mathematical formulation of optimization problems. › apply appropriate the optimization techniques. › describe the various queuing models Course Outcomes: The Student will be able to › formulation of optimization problems › define and use optimization terminology and concepts › describe the appropriate the linear programming techniques. › choose the appropriate optimization for real world problems › customize the optimization methodologies for real time problems › apply the knowledge to solve the queuing problems Syllabus › Module 1: Mathematical Preliminaries › Formulation of design problems as mathematical programming problems, classification of optimization problems. › Module 2: Linear Programming › Graphical method, Simplex method, revised simplex method, Duality in linear programming, Sensitivity analysis, Interior point method for solving LP problems. › Module 3: Integer Programming › Transportation Problem, Fleet Management Problem & Production Planning. Integer Programming Concepts, Transportation Problem, Assignment Problem. Syllabus Contd › Module 4: Non-Linear Programming › Unconstrained optimization techniques, Direct search methods, Descent methods, Constrained optimization, Direct and indirect methods, Optimization with calculus, Khun-Tucker conditions. › Module 5: Dynamic Programming › Longest common subsequence (LCS) & Flight control and robotics control. Introduction, Sequential optimization, computational procedure, curse of dimensionality. › Module 6: Queuing Theory › Kendall’s notation, M/M/1 queue, M/G/1 queue, bulk arrival queue, M/G/1 queue, bulk arrival Text Books 1. Hamdy A. Taha, “Operations Research: An Introduction”, Eighth Edition, 2007, Pearson Prentice Hall, ISBN: 0131889230, 978-0131889231. Reference Books: 1. Shu-Cherng-Fang, SaratPuthenpura, “Linear Optimizations and Extensions”, First Edition,1993, Pearson Education, ISBN: 0139152652, 978-0139152658. 2. G. Hadley, “Linear Programming”, 2002, Narosa Publishing House, New Delhi, ISBN: 8185015910, 978-8185015910. 3. Kalyanmoy Deb, “Optimization for Engineering Design-Algorithms and Design”, Second Edition, 2012, Prentice Hall India Learning Private Limited, ISBN: 8120346785, 978-8120346789. Management, Operation Research and Optimization Methodology Management is the attainment of organizational goals in an effective and " efficient manner through planning, organizing, leading, and controlling organizational resources." management science, decision science. mathematical programming.  Optimization in real life › News Paper Hawker Cooking › Maximize Taste Minimize Time duration Operations Research Models › OR Dated back to World War II. › Mathematical modeling, feasible solutions, optimization, and iterative search. › Defining the problem correctly is the most important thing. › Solution to a decision-making problem requires answering three questions: – What are the decision alternatives? – Under what restrictions is the decision made? – What is an appropriate objective criterion for evaluating the alternatives? Example  Optimal Problem Formulation Source: Kalyanmoy Deb, “Optimization for Engineering Design-Algorithms and Design”, Second Edition, 2012, Prentice Hall India Learning Private Limited, ISBN: 8120346785,12 978- 8120346789. Optimization: Basic Ideas › Major field within the discipline of Data Analytics, Operations Research and Management Science › Optimization Problem Components – Design Variables – Constraints (requirements or limitations) – Objective Function (to maximize or minimize) – Variable Bounds › Basic Idea – Find the values of the decision variables that maximize (minimize) the objective function value, while staying within the constraints. 13 Design Variables › The formulation of an optimization problem begins with identifying the underlying design variables, which are primarily varied during the optimization process. › The efficiency and speed of optimization algorithms depend on the number of chosen design variables to a large extent. › The choice of the important parameters in an optimization problem largely depends on the user › Thumb Rule : to choose few design variables 14 Constraints › Constraints represent some functional relationships among the design variables and other design parameters satisfying certain physical phenomenon and certain resource limitations. › Used for restricting the size of a component › The nature and number of constraints to be included in the formulation depend on the user. › Thumb Rule : to choose few constraints 15  Constraints › Two types of Constraints – Inequality type - Most of the constraints encountered in engineering design problems are of this type. e.g. Can also be represented as or Other examples like 16  Constraints – Equality type - State that the functional relationships should exactly match a resource value. e.g. Can also be replaced by two constraints like- – Equality constraints are usually more difficult to handle and, therefore, need to be avoided wherever possible. 17 Objective Function › The objective function can be of two types- – Either the objective function is to be maximized or it has to be minimized. › If the algorithm is developed for solving a minimization problem, it can also be used to solve a maximization problem by simply multiplying the objective function by -1 and vice versa. 18 Variable Bounds › The final task of the formulation procedure is to set the minimum and the maximum bounds on each design variable. › This information is required in order to confine the search algorithm within these bounds. › The variable bounds can be determined by making a guess about the optimal solution and set the minimum and maximum bounds so that the optimal solution lies within these two bounds. 19 Final NLP format › After the above four tasks are completed, the optimization problem can be mathematically written in a special format, known as nonlinear programming (NLP) format. – Denoting the design variables as a column vector – The objective function as a scalar quantity , – J inequality constraints as – and K equality constraints as 20 Final NLP format 21 Operations Research Models A solution of a model is feasible if it satisfies all the constraints. It is optimal if it yields to the best value of the objectives. OR models are designed to “Optimize” a specific objective criterion. Suboptimal solution: in case we can not determine all the alternatives. Solving the OR Model › In OR, we do not have a single general technique to solve all mathematical models. › The type and complexity of the mathematical models dictate the nature of the solution method (e.g. the previous examples). › The most prominent OR technique is linear programming. › Integer programming. › Dynamic programming. › Network programming. › Nonlinear programming. Cont.. › Solution to OR model may be determined by algorithms. › The algorithm provides fixed computational rules that are applied repetitively to the problem. › Each repetition moves the solution closer to the optimum. › Some mathematical models may be so complex. › In the above case we may use some other methods to find a good solution. Queuing and Simulation Models › Queuing and simulation deal with the study of waiting lines. › They are not optimization technique. › They determine measures of performance of the waiting lines, such as: – Average waiting time in queue. – Average waiting time for service. – Utilization of service facilities › The use of simulation has drawbacks. Art of Modeling › The previous examples are true representation of a real situation. › That is a rare situation in OR. › Majority of applications usually involve approximation. › Figure 1.1 in your textbook. › The assumed real world is derived using the dominant variables in the real system. › In order to design a model we should consider the main variables in the real system. › Example: A manufacturing company that produce a variety of plastic containers. Phases of an OR study › 1. Definition of the problem. › 2. Construction of the model. › 3. Solution of the model. › 4. Validation of the model. › 5. Implementation of the solution Engineering Optimization Problems › Data Fitting and Regression › Design and Manufacturing › Modelling › Control Systems › Scheduling and Routing › Data Mining › Intelligent System Design Data Fitting and Regression › Data fitting and regression analysis are activities commonly used by scientists, engineers and managers. › Software - Used to fit a curve on a set of data. › software formulates and solves an optimization problem to arrive at the fitted curve. › For a set of given data › points (say (xi,p, yi,p) for i = 1, 2,... ,K) involving input variable set x and output y, any curve y = f(x) is assigned an objective function as the sum of the squared difference between the yi,p and f(xi,p): Scheduling and Routing › Scheduling and routing problems are different kinds of optimization tasks › Finding an optimal schedule for a classroom timetabling, or an examination scheduling, or airline time-tabling, or nurse timetabling in hospitals are some such problems that are commonly faced in practice. › Job-shop scheduling in which the different machining tasks (or jobs)need to be performed on a set of machines and the optimization task is to find a schedule of tasks so that overall time of completion of the machining process is minimum. Travelling Salesman Problem › Minimum stopping time: A vehicle cannot start as soon as it stops; it has to wait at the stop for a certain period of time, or › Maximum stopping time: A vehicle cannot stop for more than a certain period of time even if it means increasing the total transfer time on the network, or › Maximum allowable transfer time: No passenger on the transit network should have to wait more than a certain period of time T at any transfer station. › Maximum headway: The headway between two consecutive vehicles should be less than or equal to the policy headway, Data Mining using Optimization Intelligent System Design Classification of Optimization Algorithms/ Methodology The formulation of engineering design problems differ from problem to problem. They are: (i) Linear terms for constraints and objective function (Linear Programming Problems) (ii) Non linear terms for constraints and objective function. (Non Linear Programming Problems) › Single-variable optimization algorithms. – The algorithms are classified into two categories—direct methods and gradient-based methods. – Direct methods do not use any derivative information of the objective function; only objective function values are used to guide the search process. – Gradient-based methods use derivative information (first and/or second-order) to guide the search process. – single-variable optimization algorithms are mainly used as unidirectional search methods in multivariable optimization algorithms. Solution space, Feasible region, candidate solutions › Multivariable optimization algorithms – These algorithms demonstrate how the search for the optimum point progresses in multiple dimensions. – Depending on whether the gradient information is used or not used, these algorithms are also classified into direct and gradient-based techniques. › Constrained optimization algorithms. – These algorithms use the single-variable and multivariable optimization algorithms repeatedly and simultaneously maintain the search effort inside the feasible search region › Specialized optimization algorithms. – A number of structured algorithms, which are ideal for only a certain class of optimization problems. – Two of these algorithms — integer programming and geometric programming – Integer programming methods can solve optimization problems with integer design variables. – Geometric programming methods solve optimization problems with objective functions and constraints written in a special form. › Nontraditional optimization algorithms. – There exist a number of other search and optimization algorithms which are comparatively new and are becoming popular in engineering design optimization problems in the recent past. Two such algorithms—genetic algorithms and simulated annealing – stochastic programming methods and dynamic programming › multimodal optimization algorithms – The optimization algorithms that attempt to find multiple optimal solutions › multimodal optimization algorithms – The optimization algorithms that attempt to find multiple optimal solutions – Reasons › a design suitable in one situation may not be valid in another situation. › it is also not possible to include all aspects of the design in the optimization problem formulation. Thus, there always remains some uncertainty about the obtained optimal solution. › designers may not be interested in finding the absolute global solution, instead may be interested in a solution which corresponds to a marginally inferior objective function value but is more amenable to fabrication. – Multiobjective optimization problems give rise to a set of optimal solutions known as Pareto-optimal solutions › Deterministic optimization problem – meaning that the objective function, constraint function or parameters are fixed from the beginning till the end of the optimization run. › stochastic optimization problems (dynamic optimization problems) – the optimal solution changes frequently – The solution that was optimal during morning may not remain optimal in the noon time. Need for customizing an optimization algorithm › there may not exist a known efficient optimization algorithm for a particular problem at hand. › the size and complexity of solving a problem using an algorithm may be computationally too expensive for it to be pragmatic. › In many scenarios, the user may not be interested in finding the exact optimal solution, rather a reasonably good (or better than an existing solution) may be adequate.  Note: The concept described in this section is considered to solve minimization problems of the following type: Optimality criteria Minimize f(x) Where f(x) is the objective function and x is a real variable. The purpose of an optimization algorithm is to find a solution x, for which the function f(x) is minimum. There are three different types of optimal points are: (i) Local Optimal point: A point or solution x* is said to be a local optimal point, if no point in the neighbourhood has a function value smaller than f(x*). (ii) Global Optimal point: A point or solution x** is said to be a global optimal point, if no point in the entire search space has a function value smaller than f(x**). (iii) Inflection point: x* is an inflection point if f(x*) increases locally as x* increases & decreases locally as x* reduces or f(x*) decreases locally as x* increases and increases locally as x* decreases  Let the objective function f(x) is the chosen search space f '(x) and f ''(x) are first and second derivatives A point x is a minimum if f'(x) = 0 & f''(x) > 0. If f ‘(x) = 0, the point is either a minimum, a maximum or an inflection point Suppose at point x*, the first derivative is zero and the first non-zero higher order derivative is denoted by n, then  If n is odd, x* is an inflection point  If n is even, x* is a local optimum (i) If the derivative is +ve, x* is a local minimum (ii) If the derivative is –ve, x* is a local maximum 5 0 Example: 1 Consider f (x) = x3, optimal point x = 0 as shown in Fig.6. Fig. The function f(x) = x 3 ›From the figure, we can see that point x = 0 is an inflection point as f(x) increases for x ≥ 0 decreases for x ≤ 0 Using the sufficient conditions f '(x 0) 3x2 x 0 0 f ''(x 0) 6x 0 x 0 f '''(x 0) 6 x 0 6( Nonzero value) Example : 2 Consider f(x) = x4, optimal point x = 0 as shown in Fig.6a. Fig. The function f(x) = x4 From the figure, we can see that the point x = 0 is a minimal point. Using sufficient conditions  f '(x 0) 4x 3 0 x 0 f ' (x 0) 12x 2 0 x 0 f '''(x 0) 24 x 00 f ' ' (x 0) 24 x x 0 24(Nonzero value) Fourth order derivative is positive, n = 4 is even, hence x = 0 is a local minimum point. 53