Chapter 6: Identifying Efficient Alternatives PDF

+ Chapter 6: Identifying Efficient Alternatives CEIE 450/550 + Recap Defined bounded rationality condition Learned how to rank alternatives (and how difficult it may be!) Investigated 3 decision making methods: MAVT (and MAUT) AHP Elec...

+ Chapter 6: Identifying Efficient Alternatives CEIE 450/550 + Recap Defined bounded rationality condition Learned how to rank alternatives (and how difficult it may be!) Investigated 3 decision making methods: MAVT (and MAUT) AHP Electre + Recap Choosing the decision-making method Formulate and solve the MO (multi-objective) design problem  Today Estimating effects  Ch. 7 Evaluation  Ch. 8 Negotiation  Ch. 9 Mitigation & compensation  Ch. 10 + Today’s objectives To formulate an optimization problem To select the set of feasible solutions/alternatives To distinguish between a feasible alternative and an optimal alternative To define Pareto efficiency (or optimality) To determine the Pareto Frontier (i.e., identify the set of efficient alternatives) + 6.1 Mathematical Optimization + Optimization Optimizationis everywhere, from engineering design to computer sciences and from scheduling to economics. However, to realize that everything is optimization does not make the problem- solving easier. In fact, many seemingly simple problems are very difficult to solve. The Traveling Salesman Problem: A salesman intends to visit 50 cities, exactly once so as to minimize the overall distance travelled or the + Optimization (cont’d) Mathematical optimization is the selection of a best element (with regard to some criteria) from a set of available alternatives. Inthe simplest case, an optimization problem consists of maximizing (or minimizing) a function by systematically choosing input values from a given set and computing the value of the function + History Fermat (1601-1655) and Lagrange (1736-1813) found calculus-based formulas for identifying optima Newton (1742-1726) and Gauss (1777-1855) proposed iterative methods for moving towards an optimum. Historically, the first term for optimization was linear programming*, due to George B. Dantzig (1914-2005), although much of the theory had been introduced by Leonid Kantorovich (1912- 1986) *The term programming in this context does not refer to computer programming. Rather, the term comes from the use of a program by the United States military referring to training and logistics schedules, which is what Dantzig studied at that time + History In 1947, Dantzig published the Simplex Algorithm for linear programming. Fastercomputers have greatly expanded the size and complexity of optimization problems that can be solved. Thedevelopment of optimization techniques has paralleled advances not only in computer science, but also in operations research, numerical analysis, game theory, economics, control theory. +The Elements of the Optimization Problem 1. The objective function that is to be maximized or minimized. Ex: expected return on a stock portfolio, a company’s production costs or profits, the time of arrival of a vehicle at a specified destination, or the vote share of a political candidate. 2. The decision variables, which are quantities whose values can be manipulated in order to optimize the objective. Ex: quantities of stock to be bought or sold, the amount of various resources to be allocated to different production activities, the route to be followed by a vehicle through a traffic network, or the policies advocated by a candidate. 3. A set of constraints, which are restrictions on the values that the variables can take Ex: a manufacturing process cannot require more resources than are available, nor can it employ less than zero resources. +Formulation The most general formulation of an optimization problem may be written as:  objective function  equality constraints  inequality constraints  variable bounds + The Objective Function Objective functions tell us how to rate decisions There is no fundamental or practical difference between max or min problems + The Objective Function (cont’d) No objective function: In some cases (for example, design of integrated circuit layouts), the goal is to find a set of variables that satisfies the constraints of the model. The user does not particularly want to optimize anything. This type of problems is usually called a feasibility problem. Single objective function Multiple objective functions: Users may like to optimize a number of different objectives concurrently. Usually, the different objectives are not compatible; the variables that optimize one objective may be far from optimal for the others. Problems with multiple objectives are often reformulated as single-objective problems by either forming a weighted + Decision Variables Examples: Design (Planning Actions): reactor volume, reservoir volume, reclaimed area for agriculture, etc. Operations/ Management (Management Actions): released flow, diverted flow, crop rotation policy, etc. + Constraints What limits the possible solutions to the problem? Safety Product quality Equipment damage Equipment operation Legal/ethical considerations Examples of equality constraints: Material, energy, current, etc. balances {accumulation} = {rate in} – {rate out} + {generated rate} Constitutive relations Equilibrium relations Imposed by the DM(s) Examples of inequality constraints: Max investment available Max flow rate due to pump limit MEF Max flow + Constraints They specify the restrictions that limit decision variable values We must be careful to prevent defining problems incorrectly with no feasible region or an unbounded solution. 1. Inequality constraints: These are one-way limits on the systems. If there were many inequality constraints, g(x) would be a vector. + Constraints 2. Equality constraints: Equality constraints are written with a zero right-hand side. If there were many equality constraints, h(x) would be a vector. There cannot be more (independent) equality constraints than decision variables in the model. Do you see why? 3. Variable bounds + Variable Bounds Variable bounds specify the domain of definition for decision variables: the set of values for which variables have meaning Setting the decision variables to a constant value (e.g., min and max) In environmental eng., the most common variable bound constraint is non-negativity + Optimization Classes Linear programming: indicates that no variables are raised to higher powers, such as squares. Problems involve minimizing (or maximizing) a linear objective function whose variables are real numbers that are constrained to satisfy a system of linear equalities and inequalities. Nonlinear programming: the variables are real numbers, and the objective or some of the constraints are nonlinear functions (possibly involving squares, square roots, trigonometric functions, or products of the variables). Stochastic programming: the objective function or the constraints depend on random variables, so that the optimum is found in some “expected,” or + Feasibility A point x is called admissible if it satisfies all constraints. The set of all points satisfying all constraints is called feasible region. The feasible region for an equality constraint is a line or a curve (in 2-D). The feasible region for an inequality constraint is a boundary line or curve, where the constraint holds with equality, along with all points on whichever side of the boundary that satisfy the constraint as an inequality. + Feasible Regions + Optimal Solution An optimal solution x* is a feasible choice for decision variables with the objective function value at least equal to that of any other solution satisfying all constraints (i.e., the best feasible point). For a minimization problem: Optimal solutions show graphically as points lying on the best objective function contour that intersects the feasible region. The optimal value f* in an optimization model is the objective function value of any optimal solutions: f* = f(x*) + Optimization Outcomes An optimization model may have: 1. A unique optimal solution 2. Several alternative optimal solutions 3. No optimal solutions (unbounded or infeasible models) + Graphic Solutions Tofind out the best feasible point, the objective function must be introduced to the plot Objectivefunctions are normally plotted in the same coordinate system as the feasible set by introducing contours Thecontour Cz of an objective function (in the decision variable space) is the line or curve passing through points having equal objective values z: + Graphic Solutions (cont’d) + Let’s practice: Problem Statement A company that produces both copper and nickel owns two mines whose ore contains both minerals. The two mines have different costs, production rates, and products. The company has been contracted to provide 100 tons/week of copper and 140 tons/week of nickel. The company wants to know the most efficient way to allocate effort at the two mines, by operating the mines no more than 5 days a week Mine 1 Mine 2 Fraction of ore that is 0.025 0.015 copper Fraction of ore that is nickel 0.00875 0.035 Produced tons of ore per 1600 1000 day Cost in thousand of dollars + Let’s practice: Problem Formulation The objective of the company is to determine a strategy for operating both mines to minimize the costs while adhering to all production constraints: At least 100 tons/wk of copper must be mined At least 140 tons/wk of nikel must be mined Mine 1 cannot operate more than 5 days/wk Mine 2 cannot operate more than 5 days/wk In the definition of the problem mining cost is a function of the # of days that each mine is operated  the manager is responsible for deciding how many days each mine will be in operation during the week. + 6.2 The Multi- Objective Problem + Example Management of a regulated reservoir: Infinite alternatives (regulation policies) q objectives J1 J1 min [upstream flooding] J2 min [downstream flooding] A0 J3 min [agriculture deficit] J4 min [hydropower deficit] J5 min [navigation losses] J2 J6 min [environmental risk] J7 min [mosquitos] A0=current conditions. Is it worth it to move? + Example: The Sinai Plan Objective: to improve quality of life in Egypt by increasing the agricultural land surface Actions: reclaim deserted regions in the 7 zones Zj using water from 4 canals Ss and choosing the most appropriate crop rotation Ri and irrigation technique Ih in each zone Evaluation criterion: net benefit in the long term (economic) + One more criterion… The socio-political criterion: At the time of the project, the Egyptian Government expected that in the near future the Sinai peninsula would return under its sovereignty This was 1977, just before the Camp David agreements, on the basis of which the Sinai was returned to Egypt from Israel, which had occupied it in the ‘six day war’ The Ministry wanted the peninsula to be as populated as possible with the condition of the development be balanced among the different areas + Example: The Sinai Plan Objective: to improve quality of life in Egypt by increasing the agricultural land surface and increase population in the region Actions: reclaim deserted regions in the 7 zones Zj using water from 4 canals Ss and choosing the most appropriate crop rotation Ri and irrigation technique Ih in each zone Evaluation criteria: net benefit in the long term (economic) populating the region (socio- Phases 0 and 1 political) + The official plan for land reclamation + Data + Phase 2: Criteria and Indicators Economic criterion (CBA): Socio-political criterion: maximize the smallest fraction of reclaimed land in all regions area [feddan] to be dedicated to rotation Ri in zone Zj with irrigation technique Ih + Phase 3: Model Same as before + Model simulations + Phase 4: Designing Alternatives The design problem can be formulated as: Subject to these constraints: + 6.2.1 Efficient Alternatives + Pareto Efficiency (or Optimality) Vilfredo Federico Damaso Pareto (1848 – 1923) was an Italian engineer, sociologist, economist, political scientist, and philosopher. He introduced the concept of Pareto efficiency and helped develop the field of microeconomics. He was also the first to discover that income follows a Pareto distribution, which is a power law probability distribution. The Pareto principle was named after him, and it was built on observations such as that 80% of the land in Italy was owned by about 20% of the population. + Pareto Efficiency (or Optimality) Let’s assume we want to minimize 2 objectives J1 and J2 and we want to compare 3 alternatives A, B, C J1 A C is preferred to A Case 1 C B because better with respect to both objectives  A is J2 dominated by C J1 A Case 2 B C A and B are semi- dominated by C J2 + Pareto Efficiency (or Optimality) An efficient solution (i.e., alternative) is a solution that is NOT dominated by other solutions The set of these solutions is known as the Pareto Frontier J1 J1 J2 J2 + Pareto Efficiency (or Optimality) A solution to a problem having multiple and conflicting objectives is EFFICENT/OPTIMAL/NON-INFERIOR if there exists no other feasible solution with better performance with respect to any objective, without worsening the performance of at least one other objective For more on Pareto Optimality, please watch this video: https://www.youtube.com/watch?v=idHVAUEeaqE&ab_channel=SystemsInnovation + But what is the best of the best? The Utopia Point It is the point in the objective space that minimizes (or maximizes) all the objectives J1 U J2 Often outside the feasible region + How to solve a MO problem Two phases: a. Determine the efficient decisions, i.e., define the Pareto Frontier: Lexicographic method Weighting method Constraint method Reference point method b. Choose the best compromise (DM’s decision) Utopia method Maximum curvature method Global utility function method There are also methods that do not split the solving process into two phases (DM’s interactive participation)  Pareto Race + Determining the Pareto Frontier Lexicographic method Weighting method Constraint method Reference point method + The lexicographic method Sort the objectives according to decreasing importance  establish a ranking rule (similarly to the rule used to order words in a lexicon) Example: Galli Law in Italy (1993) established that water use for human consumption is a priority with respect to other uses. + The lexicographic method Let’s suppose we have 2 objectives J1, J2 : Z = decision variables i J2 primary J1secondary Problem #1 J2 minimu z1 Z J1 m J1 and J2 Problem minimum #2 z2 J2 subset Z2 where J2 is minimized + The lexicographic method Let’s reverse the order: J1 primary J2secondary Problem #1 J1 and J2 z 1 Z J 1 minimum Problem #2 z2 J2 J1 subset Z1 where J1 is minimized minimum + The lexicographic method Let’s reverse the order: J1 primary J2secondary Extreme points of the Pareto frontier Problem #1 z1 Z J1 Problem #2 z2 J2 + The lexicographic method If more than two objectives  iterate the procedure considering subsequent objectives This method only allows us to determine the extreme points of the Pareto frontier and not the other points + Determining the Pareto Frontier Lexicographic method Weighting method Constraint method Reference point method + Weighting method When we ask the DM to illustrate their opinion about the relative importance of two objectives, they might say that they weigh the first λ (with 0≤λ≤1) and, as a consequence, (1-λ) the second. Once the weights are known, the 2 objectives can be combined into a single function that expresses the score with which the DM evaluates a decision. + Weighting method J1 Pareto point By modifying the weights J 2 By varying {λi} we generate points of the Pareto frontier + Weighting method Pro: an optimal point is always found Con: not always all the optimal points are identified (when the Pareto frontier is convex) J1 Points that cannot be obtained J2 + Determining the Pareto Frontier Lexicographic method Weighting method Constraint method Reference point method + Constraint method When we ask the DM to illustrate their evaluation of the alternatives, they answer that they would like the smallest possible value for the first objective with the condition that the value of the second doesn’t exceed a threshold L2 that they establish. + Constraint method J1 P Potential Pareto point P By modifying the threshold L2 L2 L2 J2 By varying the threshold {Li} we generate points that may belong to the Pareto frontier + Constraint method !!! Not all the generated points are optimal (i.e., belong to the Pareto frontier) J1 J1 J2 =L2 P P J2 J2 P may be semi- If we have an equality efficient (semi- constraint, this method may dominated)! identify dominated points as + Determining the Pareto Frontier Lexicographic method Weighting method Constraint method Reference point method Not discussed here + How to choose the right method? Lexicographic: only for the extreme points Pure planning problem: weighting, constraint, reference point Pure and mixed management (or control) problem: Weighting methods when all the objectives are defined with the Laplace criterion Reference point when all the objectives are defined with the Wald criterion + 6.2.2 Example – The pure planning problem + The Sinai Plan The design problem can be formulated as: Subject to these constraints: The min is problematic  reformulate the indicator + The socio-political criterion Maximize the smallest fraction of reclaimed land in all regions Maximize η, which is the minimum ratio between the reclaimed area and the maximum reclaimable area Aj in that zone + Revised design project The design problem can be formulated as: Subject to these constraints: + Revised design project The design problem can be formulated as: Non-linear mathematical Subject to theseprogramming constraints: problem with 55 decision variables and 80 + 7 constraints. Let’s adopt the constraint method, by setting different thresholds of η + The Pareto Frontier Efficient solutions Admissibl e solutions Whittington and Guariso, 1983 + Sensitivity analysis It is advisable to check the robustness of the optimal alternative with a sensitivity analysis. For instance, you can verify whether it is excessively sensitive to the estimate of the parameters in the model, such as the opportunity cost os of the water or the installation cost Lh of the irrigation systems. Simply check the solution for different values of the parameters. + Sensitivity analysis With respect to the With respect to the the opportunity cost of water losses from the canals (Whittington and Guariso, 1983)