Nonlinear Programming:SEPARABLE PROGRAMMING

SEPARABLE PROGRAMMING

The preceding section showed how one class of nonlinear programming problems can be solved by an extension of the simplex method. We now consider another class, called sep- arable programming, that actually can be solved by the simplex method itself, because any such problem can be approximated as closely as desired by a linear programming problem with a larger number of variables.

As indicated in Sec. 13.3, in separable programming it is assumed that the objective func- tion f(x) is concave, that each of the constraint functions gi(x) is convex, and that all these functions are separable functions (functions where each term involves just a single variable). However, to simplify the discussion, we focus here on the special case where the convex and separable gi(x) are, in fact, linear functions, just as for linear programming. (We will turn to the general case briefly at the end of this section.) Thus, only the objective function requires special treatment for this special case.

Under the preceding assumptions, the objective function can be expressed as a sum of concave functions of individual variables

so that each fj(xj) has a shape16 such as the one shown in Fig. 13.15 (either case) over the feasible range of values of xj. Because f (x) represents the measure of performance (say, profit) for all the activities together, fj(xj) represents the contribution to profit from activ- ity j when it is conducted at level xj. The condition of f (x) being separable simply implies additivity (see Sec. 3.3); i.e., there are no interactions between the activities (no cross- product terms) that affect total profit beyond their independent contributions. The as- sumption that each fj(xj) is concave says that the marginal profitability (slope of the profit curve) either stays the same or decreases (never increases) as xj is increased.

Concave profit curves occur quite frequently. For example, it may be possible to sell a limited amount of some product at a certain price, then a further amount at a lower price, and perhaps finally a further amount at a still lower price. Similarly, it may be necessary to purchase raw materials from increasingly expensive sources. In another common situation, a more expensive production process must be used (e.g., overtime rather than regular-time work) to increase the production rate beyond a certain point.

These kinds of situations can lead to either type of profit curve shown in Fig. 13.15. In case 1, the slope decreases only at certain breakpoints, so that fj(xj) is a piecewise lin- ear function (a sequence of connected line segments). For case 2, the slope may decrease continuously as xj increases, so that fj(xj) is a general concave function. Any such function can be approximated as closely as desired by a piecewise linear function, and this kind of approximation is used as needed for separable programming problems. (Figure 13.15 shows an approximating function that consists of just three line segments, but the approximation can be made even better just by introducing additional breakpoints.) This approximation is very convenient because a piecewise linear function of a single variable can be rewritten as a linear function of several variables, with one special restriction on the values of these variables, as described next.

Reformulation as a Linear Programming Problem

The key to rewriting a piecewise linear function as a linear function is to use a separate variable for each line segment. To illustrate, consider the piecewise linear function fj(xj) shown in Fig. 13.15, case 1 (or the approximating piecewise linear function for case 2), which has three line segments over the feasible range of values of xj. Introduce the three new variables xj1, xj2, and xj3 and set

However, the special restriction permits only the first possibility, which is the only one giving the correct value for fj(1).

Unfortunately, the special restriction does not fit into the required format for linear programming constraints, so some piecewise linear functions cannot be rewritten in a linear programming format. However, our fj(xj) are assumed to be concave, so sj1 > sj2 > ···, so that an algorithm for maximizing f (x) automatically gives the highest priority to using xj1 when (in effect) increasing xj from zero, the next highest priority to using xj2, and so on, without even including the special restriction explicitly in the model. This observa- tion leads to the following key property.

Key Property of Separable Programming. When f (x) and the gi(x) satisfy the as- sumptions of separable programming, and when the resulting piecewise linear functions are rewritten as linear functions, deleting the special restriction gives a linear program- ming model whose optimal solution automatically satisfies the special restriction.

We shall elaborate further on the logic behind this key property later in this section in the context of a specific example. (Also see Prob. 13.8-6a.)

To write down the complete linear programming model in the above notation, let nj be the number of line segments in fj(xj) (or the piecewise linear function approximating it), so that

Example. The Wyndor Glass Co. (see Sec. 3.1) has received a special order for hand- crafted goods to be made in Plants 1 and 2 throughout the next four months. Filling this or- der will require borrowing certain employees from the work crews for the regular products, so the remaining workers will need to work overtime to utilize the full production capacity of the plant’s machinery and equipment for these regular products. In particular, for the two new regular products discussed in Sec. 3.1, overtime will be required to utilize the last 25 percent of the production capacity available in Plant 1 for product 1 and for the last 50 percent of the capacity available in Plant 2 for product 2. The additional cost of using overtime work will reduce the profit for each unit involved from $3 to $2 for product 1 and from $5 to $1 for product 2, giving the profit curves of Fig. 13.16, both of which fit the form for case 1 of Fig. 13.15.

Management has decided to go ahead and use overtime work rather than hire addi- tional workers during this temporary situation. However, it does insist that the work crew for each product be fully utilized on regular time before any overtime is used. Furthermore, it feels that the current production rates (x1 = 2 for product 1 and x2 = 6 for product 2) should be changed temporarily if this would improve overall profitability. Therefore, it has instructed the OR team to review products 1 and 2 again to determine the most profitable product mix during the next four months.

18For a specialized algorithm for solving this model very efficiently, see R. Fourer, “A Specialized Algorithm for Piecewise-Linear Programming III: Computational Analysis and Applications,” Mathematical Programming, 53: 213–235, 1992. Also see A. M. Geoffrion, “Objective Function Approximations in Mathematical Program- ming,” Mathematical Programming, 13: 23–37, 1977, as well as Selected Reference 8.

We now need to modify this model to fit the new situation described above. For this pur- pose, let the production rate for product 1 be x1 = x1R + x1O, where x1R is the production rate achieved on regular time and x1O is the incremental production rate from using over- time. Define x2 = x2R + x2O in the same way for product 2. Thus, in the notation of the general linear programming model for separable programming given just before this ex- ample, n = 2, n1 = 2, and n2 = 2. Plugging the data given in Fig. 13.16 (including maximum rates of production on regular time and on overtime) into this general model gives the specific model for this application. In particular, the new linear programming problem is to determine the values of x1R, x1O, x2R, and x2O so as to

(Note that the upper bound constraints in the next-to-last row of the model make the first two functional constraints redundant, so these two functional constraints can be deleted.)

However, there is one important factor that is not taken into account explicitly in this formulation. Specifically, there is nothing in the model that requires all available regular time for a product to be fully utilized before any overtime is used for that product. In other words, it may be feasible to have x1O > 0 even when x1R < 3 and to have x2O > 0 even when x2R < 3. Such solutions would not, however, be acceptable to management. (Prohibiting such solutions is the special restriction discussed earlier in this section.)

Now we come to the key property of separable programming. Even though the model does not take this factor into account explicitly, the model does take it into account implicitly! Despite the model’s having excess “feasible” solutions that actually are unacceptable, any optimal solution for the model is guaranteed to be a legitimate one that does not replace any available regular-time work with overtime work. (The reasoning here is analogous to that for the Big M method discussed in Sec. 4.6, where excess feasible but nonoptimal solutions also were allowed in the model as a matter of convenience.) There- fore, the simplex method can be safely applied to this model to find the most profitable ac- ceptable product mix. The reasons are twofold. First, the two decision variables for each product always appear together as a sum, x1R + x1O or x2R + x2O, in each functional con- straint other than the upper bound constraints on individual variables. Therefore, it always is possible to convert an unacceptable feasible solution to an acceptable one having the same total production rates, x1 = x1R + x1O and x2 = x2R + x2O, merely by replacing overtime production by regular-time production as much as possible. Second, overtime production is less profitable than regular-time production (i.e., the slope of each profit curve in Fig. 13.16 is a monotonic decreasing function of the rate of production), so converting an unaccept- able feasible solution to an acceptable one in this way must increase the total rate of profit Z. Consequently, any feasible solution that uses overtime production for a product when regular-time production is still available cannot be optimal with respect to the model.

For example, consider the unacceptable feasible solution x1R = 1, x1O = 1, x2R = 1, x2O = 3, which yields a total rate of profit Z = 13. The acceptable way of achieving the same total production rates x1 = 2 and x2 = 4 is x1R = 2, x1O = 0, x2R = 3, x2O = 1. This latter solution is still feasible, but it also increases Z by (3 - 2)(1) + (5 - 1)(2) = 9 to a total rate of profit Z = 22.

Similarly, the optimal solution for this model turns out to be x1R = 3, x1O = 1, x2R = 3, x2O = 0, which is an acceptable feasible solution.

Another example that illustrates the application of separable programming is in- cluded in the Solved Examples section of the book’s website.

Extensions

Thus far we have focused on the special case of separable programming where the only nonlinear function is the objective function f (x). Now consider briefly the general case where the constraint functions gi(x) need not be linear but are convex and separable, so that each gi(x) can be expressed as a sum of functions of individual variables where each gij(xj) is a convex function. Once again, each of these new functions may be approximated as closely as desired by a piecewise linear function (if it is not already in that form). The one new restriction is that for each variable xj ( j = 1, 2, . . . , n), all the piecewise linear approximations of the functions of this variable [ fj(xj), g1j(xj), . . . , gmj(xj)] must have the same breakpoints so that the same new variables (xj1, xj2, . . . , xjn ) can be used for all these piecewise linear functions. This formulation leads to a linear program- ming model just like the one given for the special case except that for each i and j, the xjk variables now have different coefficients in constraint i [where these coefficients are the corresponding slopes of the piecewise linear function approximating gij(xj)]. Because the gij(xj) are required to be convex, essentially the same logic as before implies that the key property of separable programming still must hold. (See Prob. 13.8-6b.)

One drawback of approximating functions by piecewise linear functions as described in this section is that achieving a close approximation requires a large number of line segments (variables), whereas such a fine grid for the breakpoints is needed only in the immediate neighborhood of an optimal solution. Therefore, more sophisticated approaches that use a succession of two-segment piecewise linear functions have been developed19 to obtain successively closer approximations within this immediate neighborhood. This kind of approach tends to be both faster and more accurate in closely approximating an optimal solution.

The key property of separable programming depends critically on the assumptions that the objective function f(x) is concave and the constraint functions gi(x) are convex. However, even when either or both of these assumptions are violated, methods have been developed for still doing piecewise-linear optimization by introducing auxiliary binary variables into the model.20 This requires considerably more computational effort, but it provides a reasonable option for attempting to solve the problem.