Optimization in Practice with MATLAB for Engineering Students and Professionals (2015)

PART 5


MORE ADVANCED TOPICS IN OPTIMIZATION

18


Physical Programming for Multiobjective Optimization

18.1 Overview

Engineering design problems are multiobjective in nature. These problems usually optimize two or more conflicting objectives - simultaneously. An approach to multiobjective problem formulation combines the multiple objectivesinto a single objective function, also known as the Aggregate Objective Function (AOF). This AOF is solved to obtain one Pareto solution. One of several challenges in the area of multiobjective optimization is to judiciouslyconstruct an AOF that satisfactorily models the designer’s preferences. This chapter provides a concise presentation of the Physical Programming method, which defines a framework to effectively incorporate the designer’spreferences into the AOF (Ref. [1]).

Several methods to solve multiobjective optimization problems have been discussed in Chapter 6, such as the weighted sum method, compromise programming, and goal programming. These weight-based approaches require thedesigner to specify numerical weights in defining the AOF. This process can be ambiguous. For example, consider the following: (1) How does the designer specify weights in weight-based approaches? (2) Do the weights reflect thedesigner’s preferences accurately? If the designer chooses to increase the importance of a particular objective, by how much should he/she increase the weight? Is 25% adequate? Or is 200% adequate? (3) Does the AOF denote a true mathematical representation of the designer’s preferences?

The above questions begin to explain that the problem of determining “good weights” can be difficult and dubious. Because of this ambiguity, the weight selection process is often a computational bottleneck in large scalemultiobjective design optimization problems. The above discussion paves the way for a multiobjective problem formulation framework that alleviates these ambiguities: Physical Programming (PP) developed by Messac [2].

Physical Programming systematically develops an AOF that effectively reflects the designer’s wishes. This approach eliminates the need for iterative weight setting, which alleviates the above discussed ambiguities. Instead ofchoosing weights, the designer chooses ranges of desirability for each objective. The PP method formulates the AOF from these ranges of desirability, while yielding interesting and useful properties for the AOF.

The PhysPro software embodies the Physical Programming method, which is described below and fully presented in Refs. [2, 3]. For information regarding PhysPro, please visit www.physpro.com (Ref. [4]).

Next, Linear Physical Programming (LPP) is studied in detail, followed by Nonlinear Physical Programming (NPP).

18.2 Linear Physical Programming (LPP)

18.2.1 Classification of Preferences: Soft and Hard

Using Physical Programming, the designer can express preferences for each design objective with more flexibility, as opposed to specifying maximize, minimize, greater than, less than, or equal to, which are the only choicesavailable in conventional optimization approaches. Using the PP approach, a designer can express preferences with respect to each design objective using four different classes.

Figure 18.1 illustrates the four classes available in LPP. A generic design objective, μi, is represented on the horizontal axis, and the function to be minimized for that objective, zi, henceforth called the preference function or theclass function, is represented on the vertical axis. Each class consists of two subclasses, hard and soft, referring to the sharpness of the preference. These subclasses are also illustrated in Fig. 18.1, and are characterized as follows:

Figure 18.1. LPP Ranges of Preferences for Soft Classes

1.Soft Classes:

a)Class 1S: Smaller-is-better (minimization)

b)Class 2S: Larger-is-better (maximization)

c)Class 3S: Value-is-better

d)Class 4S: Range-is-better

2.Hard Classes:

a)Class 1H: Must be smaller

b)Class 2H: Must be larger

c)Class 3H: Must be equal

d)Class 4H: Must be in range

Physical Programming offers a flexible lexicon to express ranges of desirability for both hard and soft classes. The lexicon consists of six ranges of desirability for classes 1S and 2S, ten ranges for the class 3S, and eleven ranges for the class 4S.

18.2.2 Ranges of Desirability for Various Classes

Following are the definitions of the differing ranges of desirability under LPP, with which a designer can express his/her preferences. To explain, consider the case of class 1S shown in Fig. 18.1. The ranges of desirability are definedas follows in order of decreasing preference.

1.Ideal Range (μiti1+) (Range 1): A range over which every value of the criterion is ideal, or the most desirable possible. Any two points in this range are of equal value to the designer (see discussion in [3]). For example,consider a hypothetical beam design problem, where the design objectives are to minimize the mass and deflection subject to certain constraints. The ideal range for the mass of the beam could be specified as M ≤ 2, 000 kg.

2.Desirable Range (ti1+μiti2+) (Range 2): An acceptable range that is desirable (for example, the desirable range for the mass of the beam could be specified as 2, 000 kg ≤ M ≤ 3, 000 kg).

3.Tolerable Range (ti2+μiti3+) (Range 3): This is an acceptable, tolerable range (for example, 3, 000 kg ≤ M ≤ 3, 500 kg could be specified as a tolerable range for the mass of the beam).

4.Undesirable Range (ti3+μiti4+) (Range 4): A range that, while acceptable, is undesirable (for example, the undesirable range for the mass of the beam could be specified as 3, 500 kg ≤ M ≤ 4, 000 kg).

5.Highly Undesirable Range (ti4+μiti5+) (Range 5): A range that, while still acceptable, is highly undesirable (for example, 4, 000 kg ≤ M ≤ 4, 500 kg could be specified as the highly undesirable range for the mass of thebeam).

6.Unacceptable Range (μiti5+) (Range 6): The range of values that the design objective must not take (the range M ≥ 4, 500 kg could be specified as the unacceptable range for the mass of the beam).

The range-defining parameters ti1+ through ti5+, defined above for soft classes, are physically meaningful constants that are specified by the designer to quantify the preferences associated with the ith design objective. For example,the set of tij+ values specified above for the mass of the beam are [2, 000, 3, 000, 3, 500, 4, 000, 4, 500].

In the case of hard classes, only two ranges are defined, acceptable and unacceptable. All soft class functions become constituent components of the AOF to be minimized, and all the hard class functions simply appear asconstraints in the LPP problem formulation.

The preference functions map the design objectives into non-dimensional, strictly positive real numbers. This mapping transforms disparate design objectives with different physical meanings onto a dimensionless scale through a unimodal convex function. The preference functions are piecewise linear and convex in the LPP method, as seen in Fig. 18.1.

18.2.3 Inter-Criteria Preferences: OVO Rule

Specifying intra-criterion preferences (preferences within one objective) using Physical Programming [3] has been explained. In order to completely formulate the multiobjective optimization problem, the designer also needs tospecify the inter-criteria preferences (preferences among several objectives). The PP method operates within an inter-criteria heuristic rule, called the One vs. Others rule (OVO). The inter-criteria preference for each soft criterion,μi, is defined as follows. Consider the following two options:

1.Full improvement of μi across a given range of preference, and

2.Full reduction of all the other criteria across the next better range of preference.

The PP method then formulates the AOF so that Option 1 is preferred over Option 2. The OVO rule has a built-in preemptive nature whereby the worst criterion tends to be minimized first.

For example, consider a multiobjective problem with ten objectives. According to the OVO rule, it is preferable for a single objective to improve over a full tolerable range, than it is for the remaining nine objectives to improveover the full desirable range. The next subsection explains how the OVO rule is implemented in the LPP method.

18.2.4 LPP Class Function Definition

The class function maps the design objectives into non-dimensional, strictly positive real numbers that reflect the designer’s preferences. To accomplish the above, the class function, zi, is required to possess the following properties.

1. A lower value of the class function is preferred over a higher value thereof (see Fig. 18.1). Irrespective of the class of a criterion (1S, 2S, 3S, or 4S), the ideal value of the criterion always corresponds to the minimum value of the class function, which is zero.

2. A class function is strictly positive (zi ≥ 0).

3. A class function is continuous, piecewise linear, and convex.

4. The value of the class function at a given range limit, zi(tis+), is always fixed (see Fig. 18.1). From criterion to criterion, only the location of the limits (tis+) changes, but not the corresponding zi values. Because of this property,as one travels across all the criteria, and observes a given range type, the change in the class function value, i, will always be of the same magnitude (see Fig. 18.1). This property of the class function results in a normalizingeffect, eliminating numerical conditioning problems that arise because of improper scaling between design objectives of disparate magnitudes.

5.The magnitude of the class function’s vertical excursion across any range must satisfy the OVO rule. (This property is represented in Eq. 18.3). Observe in Fig. 18.1 that the value of 2 (desirable) is less than that of 5 (highlyundesirable). This is in keeping with the OVO rule.

Based on the above properties, the mathematical relations used in the LPP algorithm are now presented. From Property (4.), the following relation holds

(18.1)

where s and i denote a generic range intersection and the soft criterion number, respectively.

The change in zi across the sth range is given by

s = zs - zs-1; (2 ≤ s ≤ 5); z1 = 0

(18.2)

The OVO rule is enforced by the equation

s > (n sc - 1) s-1; (3 ≤ s ≤ 5); (n sc > 1)

(18.3)

or,

s = β(n sc - 1) s-1; (3 ≤ s ≤ 5); n sc > 1; β > 1

(18.4)

where nsc denotes the number of soft criteria, and β is used as a convexity parameter. To use Eq. 18.4, the value of 2 needs to be specified. Assume 2 to be equal to a small positive number (say 0.1) in practice. Eq. 18.4 by itselfdoes not guarantee convexity of the class function. The convexity also depends on the targets chosen by the decision maker.

The relations that specifically enforce convexity of the class function are defined by the following quantities:

(18.5)

(18.6)

Note that the above equations define the length of the sth range of the ith criterion. Using the above definition, the magnitude of the slope of the class function is given by

(18.7)

(18.8)

Note that these slopes change from range to range, and from criterion to criterion. The convexity requirement can be enforced by using the relation

(18.9)

where

(18.10)

(18.11)

(18.12)

The quantities is+ and is- defined above are the slope increments of the class function between the different ranges of desirability. Equation 18.9 implies that if all the incremental weights are positive, the class function (which ispiecewise linear) will be convex. The LPP weight algorithm can be used to define the class function using the equations given in this subsection.

18.2.5 LPP Weight Algorithm

The LPP weight algorithm is given below.

1.Initialize: β = 1.1; wi1- = wi1+ = 0; 2 = small positive number, say 0.1.
i = 0; s = 1; nsc = number of soft criteria.

2.Set i = i+ 1.

3.Set s = s+ 1.

4.Evaluate in the same order: s, is+, is-, wis+, wis-, is+, is-, and min.

5.If min is less than some chosen small positive value (say 0.01), increase β. Set i = 0, s = 1, and go to Step 2..

6.If s 5, go to Step 3..

7.If i = nsc, terminate. Otherwise, go to Step 2..

A MATLAB code that uses this algorithm to compute weights, given the preference values for each criterion, is given in the book website (www.cambridge.org/Messac). Once the weights are obtained from the above algorithm, thepiecewise linear class function can be defined for each criterion.

The formulation of the LPP problem involves the presence of numerous weights because of the piecewise linear nature of the class function. However, the designer need not choose these weights. All the required weights areautomatically evaluated by the LPP weight algorithm. The LPP AOF is defined using deviational variables, denoted by dis-and dis+. A deviational variable is defined as the deviation of the ith design criterion from its sth rangeintersection. The class function for soft classes can then be defined in terms of the deviational variables as

(18.13)

18.2.6 LPP Problem Formulation

The LPP application procedure consists of four distinct steps.

1.Specify the class type for each design objective (1S-4H).

2.Provide the ranges of desirability (tis+, or tis-, or both) for each class (see Fig. 18.1). The designer specifies five limits for classes 1S or 2S, nine limits for the class 3S, and ten limits for the class 4S. For hard classes, the designerspecifies one limit for classes 1H, 2H, and 3H, and two limits for 4H (see Fig. 18.1).

3.Use the LPP weight algorithm to obtain the incremental weights, is+ and is-. Note that the designer does not need to explicitly define the class function zi.

4.Solve the following linear programming problem.

(18.14)

subject to

(18.15)

(18.16)

(18.17)

(18.18)

(18.19)

(18.20)

(18.21)

where i = {1, 2,...,nsc}, s = {2,..., 5}, j = {1, 2,...,nhc}, nhc is the number of hard classes, x is the design variable vector, and μi = μi(x).

A recent application of LPP is provided in Ref. [5].The Nonlinear Physical Programming (NPP) method is described next.

18.3 Nonlinear Physical Programming (NPP)

The NPP method can be more advantageous than the LPP method for solving certain optimization problems. The piecewise linear nature of the class function in LPP may lead to computational difficulties because of thediscontinuities in the class function derivatives at the intersection of the range limits. The NPP method alleviates this difficulty by defining a class function that is smooth across all range limits. However, the NPP method can becomputationally expensive, since it is formulated as a nonlinear optimization problem.

This section provides a brief discussion of the NPP method. Interested readers can refer to [2] for a more detailed description of the NPP method. First, the similarities and differences between LPP and NPP will be identified.

18.3.1 LPP vs. NPP

The LPP and NPP methods share certain similarities, as listed below.

1.The class and the subclass definitions are the same in LPP and NPP.

2.The PP lexicon and the classification of preferences are the same for NPP and LPP, with one exception; the analog of ideal (LPP) is highly desirable (NPP). Figure 18.2 provides the classification of the design objectives, and theranges of differing preferences for soft classes in NPP.

Figure 18.2. NPP Ranges of Preferences for Soft Classes

3.The OVO rule is defined in the same manner in LPP and NPP.

The difference between NPP and LPP can be observed by comparing the class function plot in Fig. 18.2 with that in Fig. 18.1. In the case of LPP, the class functions are piecewise linear. For NPP, they are nonlinear and smooth.

The class functions in NPP are defined using a special class of splines. A detailed discussion regarding the mathematical development of these splines can be found in [2]. A summary of the mathematical background for NPP ispresented next.

18.3.2 NPP Class Function Definition

A suitable class function in NPP must possess the following properties.

1.All soft class functions must:

a)be strictly positive,

b)have continuous first derivatives, and

c)have strictly positive second derivatives (implying convexity of the class function).

2.All the above defined properties must hold for any practical choice of range limits.

The NPP class function (Fig. 18.2) in the highly desirable range is defined by a decaying exponential function; while in all the other ranges, the class functions are defined by spline segments [2]. A detailed description of the classfunction properties and definition is provided in [2].

18.3.3 NPP Problem Model

The following steps are used to generate the NPP problem.

1.Specify the class type for each design objective (1S - 4H).

2.Provide the ranges of desirability for each design objective (see Fig. 18.2).

3.Solve the constrained nonlinear minimization problem that is given by

(18.22)

subject to

(18.23)

(18.24)

(18.25)

(18.26)

(18.27)

(18.28)

(18.29)

(18.30)

where ti,min, ti,max, and ti,val represent the specified preferences values for the ith hard objective; and xj,min and xj,max are the minimum and the maximum values for xj, respectively. The ranges of desirability, ti5+ and ti5-, are providedby the designer, and nsc is the number of soft objectives. The hard classes are treated as constraints, while the soft classes are part of the objective function. Plans are for a limited edition of the NPP software to be provided in thebook website (www.cambridge.org/Messac).

18.4 Comparison of LPP with Goal Programming

The flexibility offered by the LPP method is now compared to that offered by goal programming, previously discussed in Chapter 6. As shown in Fig 18.3, the GP method offers limited flexibility, with the option of choosing twoweights and a target value for each objective. The LPP method, in contrast, allows the designer to choose up to ten physically meaningful target values or ranges of desirability for each design objective. While the designer isrequired to choose the weights in the GP method, the LPP method completely eliminates the often ambiguous task of choosing weights.

Figure 18.3. GP vs. LPP—Comparison

In Fig. 18.4, three-dimensional visualizations of the AOF for the GP and the LPP methods are presented. The XY plane of each figure provides the contour plots of the AOF for each method. In typical GP form, there are two-sided goals/criteria, yielding an intersection of four planes. Also, note that the contour plots of the GP AOF are quadrilaterals.

Figure 18.4. GP vs. LPP—AOF Visualization

The AOF surface for LPP is obtained by the intersection of 81 planes (for the 4-S criterion), which reflects a more realistic preference. Observe the multi-faceted contours of the AOF for the LPP method.

The effectiveness of LPP comes from the well defined class function, which tailors itself to the complex nature of the designer’s choices. A numerical example to illustrate the LPP approach is presented.

18.5 Numerical Example

This example solves the optimization problem using the LPP method, and compares the results to those obtained by the GP method. A company manufactures two products, A and B. The ideal production levels per month for A andB are 25 units and 10 units, respectively. The profit per unit sold for A and B are $12k and $10k, respectively. Under these conditions, the total monthly profit is $400k. The company needs to make a profit of at least $580k to stay inbusiness. The designer has certain target preferences for the production levels for A and B, given in Table 18.1. Define μ1 and μ2 as the two design criteria, which denote the production levels of products A and B, respectively. The profit constraint function is given as

12μ1 + 10μ2 ≥ 580

(18.31)

Table 18.1. Preference Ranges for μ1 and μ2



Preference level

μ1

μ2


Ideal

< 25

< 10

Desirable

25 - 31

10 - 18

Tolerable

31 - 36

18 -26

Undesirable

36 - 44

26 - 33

Highly Undesirable

44 - 50

33 - 40

Unacceptable

> 50

> 40



18.5.1 Goal Programming Solution

The details for formulating a GP problem are given in Chapter 6. The GP formulation for this problem is given by

(18.32)

subject to

(18.33)

(18.34)

(18.35)

(18.36)

(18.37)

(18.38)

The slopes of the preference functions for the GP formulation are specified by wGP1+ and wGP2+. The target for μ1 is 25, and the target for μ2 is 10. The results obtained using GP are shown in Fig. 18.5 (a), (b), and (c). The threesolutions obtained with GP are for the cases where the ratio of slopes wGP1+∕w GP2+ is less than, equal to, and greater than 1210 = 1.2.

Figure 18.5. GP vs. LPP—Example Results

In Fig. 18.5, the shaded area represents the feasible region, and the solid dots represent the optimum solutions. The solution when wGP1+∕w GP2+ < 1.2 is the point P =(40, 10) in Fig. 18.5 (a). The solution when wGP1+∕w GP2+ > 1.2is the point Q = (25, 28) in Fig. 18.5 (c). In Fig. 18.5 (b), when wGP1+∕w GP2+ = 1.2, the slope of the objective function given in Eq. 18.32 is equal to that of the constraint given in Eq. 18.35. There are infinitely many solutions alongthe straight line segment shown by the thick line in Fig. 18.5 (b). We now examine how LPP can be used to solve this problem.

18.5.2 Linear Physical Programming Solution

From the values of the preferences provided in Table 18.1, note that μ1 and μ2 belong to the class 1S. The LPP model is formulated using the linear programming model, given in Sec. 18.2.6, Eq. 18.14. The solution obtained is R = (31, 20.8), as shown in Fig. 18.5 (d).

Compare the solutions P and Q obtained by the GP method, and the solution R obtained by the LPP method. The solution obtained with GP is highly sensitive to the weights chosen for each objective. For the point P = (40, 10)(see Fig. 18.5 (a)), μ1 lies in the undesirable range, while μ2 lies in the desirable range. For the point Q = (25, 28) (see Fig. 18.5 (c)), μ1 lies in the desirable range, while μ2 lies in the undesirable range. The solutions P and Q lie in the undesirable ranges because the GP problem formulation does not fully represent the designer’s preferences given in Table 18.1. The LPP method, on the other hand, utilizes all the information provided by the designer inTable 18.1 to formulate the problem. With the LPP method, observe that the optimum point R = (31, 20.8) (Fig. 18.5 (d)) lies on the desirable/tolerable boundary for μ1, and within the tolerable range for μ2.

In addition, it is interesting to contrast the contours of the LPP AOF against those of the GP AOF in Fig. 18.5. The shape and the number of sides of these contours are significantly different. These observations can be betterunderstood from Fig. 18.4, where a three-dimensional representation is provided.

18.6 Summary

Most numerical optimization algorithms are developed for application to single objective problems. To pose the multiobjective problem in a single objective framework, the designer needs to effectively aggregate the criteria into a single AOF. In doing so, he/she has to model the intra-criterion and inter-criteria preferences into the AOF. This chapter presented the Physical Programming framework for AOF formulation. The PP method provides a frameworkto unambiguously incorporate the designer’s preferences into the AOF. The PP method precludes the need for the designer to specify physically meaningless weights. The PP algorithm generates the weights of the class functionbased on the designer’s preferences, allowing the designer to focus on specifying physically meaningful preference values for each objective. This renders the PP method unique, and provides an effective framework formultiobjective decision-making. The PP method has been applied to a wide variety of applications, such as product design, multiobjective robust design, production planning, and aircraft structure optimization (seeRefs. [6, 7, 8, 9, 10, 11]).

18.7 Problems

Graduate Level Problems

18.1Read the paper: Messac, A., “From Dubious Construction of Objective Functions to the Application of Physical Programming” (Ref. [12]). Prepare a two page summary of this paper in your own words, emphasizing the keymessages and approach.

BIBLIOGRAPHY OF CHAPTER 18

[1] K. E. Lewis, W. Chen, and L. C. Schmidt. Decision Making in Engineering Design. ASME Press, 2006.

[2] A. Messac. Physical Programming: Effective optimization for computational design. AIAA Journal, 34(1):149-158, 1996.

[3] A. Messac, S. Gupta, and B. Akbulut. Linear Physical Programming: A new approach to multiple objective optimization. Transactions on Operational Research, 8:39-59, 1996.

[4] PhysPro. www.physpro.com.

[5] K. K. Pochampally and S. M. Gupta. Use of linear physical programming and Bayesian updating for design issues in reverse logistics. International Journal of Production Research, 50(5):1349-1359, 2012.

[6] B. H. Wilson, C. Erin, and A. Messac. Optimal design of a vibration isolation mount using Physical Programming. Journal of Dynamic Systems, Measurement, and Control, 121(2):171-178, 1999.

[7] A. Messac and A. Ismail-Yahaya. Multiobjective robust design using Physical Programming. Structural and Multidisciplinary Optimization, 23(5):357-371, 2002.

[8] A. Maria, C. A. Mattson, A. Ismail-Yahaya, and A. Messac. Linear Physical Programming for production planning optimization. Engineering Optimization, 35(1):19-37, 2003.

[9] A. Messac, W. M. Batayneh, and A. Ismail-Yahaya. Production planning optimization with Physical Programming. Engineering Optimization, 34(4):323-340, 2002.

[10] M. P. Martinez, A. Messac, and M. Rais-Rohani. Manufacturability-based optimization of aircraft structures using Physical Programming. AIAA Journal, 39(3):517-525, 2001.

[11] A. Messac and P. D. Hattis. Physical programming design optimization for high speed civil transport. Journal of Aircraft, 33(2):446-449, 1996.

[12] A. Messac. From the dubious construction of objective functions to the application of Physical Programming. AIAA Journal, 38(1):155-163, January 2000.