In previous chapters, we have encountered three powerful optimization procedures—the linear solver, the branch-and-bound procedure, and the nonlinear solver. For linear models, we use the linear solver. This algorithm is reliable: It always finds a global optimum when the model does not contain an unbounded objective function or conflicting constraints. For linear programming models with integer constraints, we also rely on the linear solver. The integer constraints are added in the problem formulation, informing the linear solver to use its branch-and-bound procedure in the search for an optimal solution. The branch-and-bound procedure relies on solving a series of linear programs, so if Solver does not run out of time, this is a reliable procedure, too. However, when the model does not satisfy the conditions of linearity, the linear solver is of no use.

For nonlinear programming problems, we use the nonlinear solver. This algorithm is not as reliable as the linear solver because it may stop its hill climbing at a local optimum. Moreover, it is unable to determine whether it has found a global optimum or stopped short of one. We can at least improve our chances of finding a global optimum by rerunning the nonlinear solver from a variety of different starting points, a process we can automate with the MultiStart option. However, when the problem is not composed of smooth functions, the nonlinear solver often fails to help.

The fourth solution procedure in Solver is the evolutionary solver, which is the subject of this chapter. This procedure is particularly useful for tackling optimization models containing nonsmooth functions. As suggested in Chapter 8, a nonsmooth function is one that exhibits gaps or kinks. The presence of a nonsmooth function undermines the performance of the linear and nonlinear solvers. However, the availability of a solution procedure suitable for nonsmooth functions allows us to build models with more flexibility than under the restrictions of the linear and nonlinear solvers. In particular, we can take advantage of several Microsoft^® Office Excel^® functions in the model. We can include the IF function, which allows us to represent some simple logical choices. We can include several other familiar mathematical functions, such as ABS, MIN, MAX, CEILING, FLOOR, ROUND, and INT. (Although it is sometimes possible to avoid using these functions directly, doing so may require the use of binary variables or auxiliary variables in cumbersome or unusual ways.) We can also include spreadsheet-oriented functions such as CHOOSE, COUNTIF, INDEX, and LOOKUP, which may provide convenience in spreadsheet calculations even though they are seldom used in other circumstances. Thus, another way of interpreting nonsmooth is any computation that uses one of these dozen functions or one of the other specialized functions in Excel.

The modeling flexibility comes at a price. Because the evolutionary solver makes virtually no assumptions about the nature of the objective function, it has a limited ability to identify an optimal solution. Essentially, it conducts a search, compares the solutions encountered as it proceeds with the search, and stops when it senses that it is making very little progress at finding improvements. The solution it generates may not even be a local optimum, such as the solution the hill-climbing procedure delivers, yet in many kinds of problems, the evolutionary solver delivers a good solution, if not an optimal one. This type of procedure is called a heuristic procedure, meaning that it is a systematic procedure for seeking good solutions, but it cannot guarantee optimality.

9.1 FEATURES OF THE EVOLUTIONARY SOLVER

A few features of the evolutionary solver are helpful to know. First, it is important to realize that the procedure contains some randomized steps. As a consequence, we may get different solutions when we run the evolutionary solver twice on exactly the same model.

The evolutionary solver works with a population of solutions. At intermediate stages of the solution procedure, it keeps track of several solutions rather than maintaining just the one, best solution found so far. This population of solutions develops, or evolves, in steps that mimic naturally occurring evolutionary processes. From the population of solutions that it builds and maintains, the procedure can generate new solutions, following the principle that an offspring solution should combine traits from each of two parent solutions. In addition, there are occasional mutations, which are offspring solutions with some random characteristics that do not come from their parents. Over the course of the procedure, the population is governed by a fitness criterion (based on the objective function) that removes the poorer solutions and keeps the better ones. This process of selection drives the population toward better levels of fitness (better values of the objective function). If there is evidence that the population is no longer improving or if one of the user-designated stopping conditions is met, then the procedure stops. When it stops, Solver displays the best member of the final population as the solution.

The inner workings of the evolutionary solver do not concern us at this stage. However, in the next section, we provide an example that will help explain conceptually how the procedure works. The main point is that the evolutionary solver is not handicapped by the presence of nonsmooth functions, as would be the case for the linear and nonlinear solvers. It is also helpful to set some user-controlled options when running the evolutionary solver. However, in the end, the evolutionary solver cannot guarantee that it has found a global optimum, so some judgment is required—even more than with the nonlinear solver—when applying it to a particular optimization problem.

In this chapter, we examine a series of examples that contain nonsmooth functions to illustrate how we might build models suitable for the evolutionary solver. In some cases, we revisit problems that we tackled with other solution procedures in earlier chapters, mainly to provide a contrast in modeling approaches. The variety of examples should provide a working knowledge of the evolutionary solver, but, more than the other solvers we have covered, this one requires practice and experience in order to use it effectively.

9.2 AN ILLUSTRATIVE EXAMPLE: NONLINEAR REGRESSION

As our first example, we look at a curve-fitting problem in which the relationship between two variables is nonlinear and in which the criterion is the sum of absolute deviations. As discussed in Chapter 8, the most appropriate tool for curve-fitting problems when the criterion is the sum of squared deviations is the nonlinear solver. But when the criterion is the sum of absolute deviations, several local optima may exist, and the nonlinear solver may not find the best fit. The evolutionary solver is often well suited to such problems.

Our purpose here is to describe, in an approximate way, how the evolutionary solver works. This is not meant to be a precise description of the algorithm, but rather a suggestive description of the evolutionary approach and the elements it contains. For a specific example, we revisit the data from Fitzpatrick Fuel Supply (Example 8.3), where we wanted to predict gas consumption on the basis of degree days.

Data from Example 8.3

A sample of 12 observations was made at customers’ houses on different days and the following observations of degree days and gas consumption were recorded.

To predict gas consumption, Fitzpatrick’s operations manager believes that the power curve y = ax^b is a good model. As a criterion, suppose that we want to minimize the sum of absolute deviations (rather than squared deviations) between model and observations. This is a less common criterion than the sum-of-squares measure that was used in Chapter 8, but it is just as plausible as a criterion for determining a close fit. Whereas the sum-of-squares measure penalizes large deviations more severely than small ones, that is not the case for the absolute-deviation measure.

Figure 9.1 displays a worksheet for this problem. The given data, consisting of 12 observations, can be found in the first three columns. The parameters a and b, which serve as the decision variables, are located in cells E3 and E4. Specifying these two parameters allows us to generate the values found in the column labeled Predicted in column D, and the differences between predicted values and observed values are calculated in column E. The absolute value of this difference appears in the next column, under the heading Deviation. The sum of these absolute deviations, which is the objective function to be minimized, appears in cell F5.

Knowing a little about the range of observations, we can make an educated guess that the best value of a lies between 0 and 50, while the best value of b lies between 0 and 1. These are coarse limits, but they are sufficient to get us started. We generate an initial set of pairs (a, b) by sampling randomly from these two ranges. Let’s suppose this process generates the values shown in Table 9.1. In each case, the fitness number is the objective function that corresponds to the values of a and b, and this value can be calculated directly by using the worksheet. Here, we have constructed a population of size 6. The best fitness is 440, and the average fitness is about 1706.

Next, we create new members of the population by the crossover method. In particular, we take the first two solutions and swap their a values. That way, the a value of the first solution is paired with the b value of the second solution and vice versa. In other words, the two new solutions are (30.8, 0.55) and (19.7, 0.19). We can think of these two solutions as being “offspring” of the original two solutions, with values of a and b (interpreted as genes) that are inherited from their “parents.”

Suppose that the next new member of the population is created by the mutation method. For the third solution, we keep the second gene (b) and randomly generate the first gene (a), obtaining (20.0, 0.82)

Next, we’ll perform the crossover step on solutions 4 and 5 and then generate another mutation from the sixth solution by keeping the first gene and randomly generating the second. The six new members are shown in Table 9.2.

We can think of this list as newcomers to the population in one generation or cycle. We’ll combine these members with the existing members and apply the fitness criterion. This means that we’ll select a second generation of size 6, keeping just the six best fitness values. The resulting list is displayed in Table 9.3. The best fitness in the new population has dropped from 440 to 322, and the average fitness has dropped from 1706 to 684.

To create the third generation, we follow a similar procedure. We use the first two solutions as parents to generate two offspring by the crossover operation. We use the third solution to generate a mutation by randomly replacing the a value. Then, we repeat the process, applying the crossover operation to the fourth and fifth solutions and generating another mutation by randomly replacing the b value in the sixth solution. The six new members of the populations are shown in Table 9.4.

Combining this list with the previous one, we use the fitness criterion to remove the least-fit members of the population, thus selecting the six best solutions as the third generation (Table 9.5).

Now, the best solution in the population has improved to 217, and the average has dropped to about 417. Another generation leaves the best solution unchanged, but the average drops to about 352.

As these first few iterations suggest, the crossover and mutation procedures, along with the fitness criterion, tend to generate populations with improving fitness values. Clearly, a generation of solutions always has a best value and an average value that are no worse than those of the previous generation. As we continue the process, which Solver can do at great speed, we tend to find additional improvements.

The evolutionary solver in Excel does not follow the precise details of the generation-building process we have outlined here, although it does rely on crossover and mutation procedures. The details of the actual implementation are not important in order to understand how to implement the evolutionary solver, but here are some relevant observations:

• For the purposes of implementing the crossover operation, the specific form of a gene depends on the model and is determined within the evolutionary solver.
• The frequency with which mutations appear is an option set by the user. The genetic form of a mutation, however, is determined within the evolutionary solver.
• The procedure contains some randomness, so two successive runs from the same starting point can produce different solutions when the random seed is left at its default value of zero.
• No guarantees of optimality can be given; the procedure may stop short of finding an optimum.

To understand how the procedure stops, let’s look at the various options available when we implement the evolutionary solver on a particular model in Excel.

In the Solver Parameters window, we select the evolutionary method from the drop-down list of solving methods and then press the Options button. Some options are tailored to the evolutionary solver, whereas others are common to the other solvers as well. For example, on the All Methods tab, the Max Time parameter limits the amount of time Solver searches for a good solution before stopping. With the evolutionary solver, we use this option as a kind of last resort. It should be set long enough for other options to have an opportunity to take effect, and it should reflect the amount of time we are willing to allow the procedure to run without intervening. For large and complicated problems, this could mean a long wait, but we often choose a short time limit so that we can get feedback quickly. When debugging a model or just trying to get a feel for performance on a given model, we might set this option to 10 or 20 seconds. We could also impose other limits (on iterations, subproblems, or feasible solutions), but the time limit alone is usually suitable for our purposes.

On the Evolutionary tab (Fig. 9.2), the user can set several additional parameters. An example is the Population Size parameter, which determines the number of solutions retained in the population. We used a population of size six in the Fitzpatrick example, but that would be small for the automated implementation used by Solver. In the course of solving a particular problem, we might start with a population size of 25 and later try a larger value for greater diversity. The evolutionary solver stops (and displays the convergence message) when 99% or more of the population has fitness values whose relative differences are less than the Convergence parameter shown on the same tab. Thus, a larger population size tends to generate more diversity and a longer search effort. The population size cannot exceed 200, but 25 or 50 might be adequate for even very difficult problems.

The Mutation Rate parameter affects the level of randomness in generating new members of the population. A low rate would create few mutations, whereas a high rate offers greater diversity. In our example, one-third of the new population contained mutations, but Solver’s default value is 7.5%, which is often sufficient. We might raise this value if we find evidence that the evolutionary solver stalls due to lack of diversity. As in our example, the population may gravitate toward a set of similar solutions. When that type of population convergence begins to take place, the search may be located near a global optimum, and our chances of locating that optimum become high. Raising the mutation rate in such a case is unlikely to produce much improvement. On the other hand, when convergence occurs at some distance away from a global optimum, the process is analogous to finding a local optimum with the nonlinear solver. In that case, we’d want to increase the diversity in the population, and it would be desirable to raise the mutation rate. Normally, we do not know whether we are close to a global optimum, but the effect of raising the mutation rate may provide a clue.

The Maximum Time without Improvement option provides an alternative stopping criterion. It allows us to stop short of the full-time allotment if we find that the search is making no progress at all. It makes sense to vary the maximum time without improvement according to previous outcomes, and a typical starting value might be half the maximum time limit.

Another option is the Require Bounds on Variables option, which asks whether to require upper and lower bounds on the decision variables. The box for this option should be checked, thus forcing the model to contain simple bounds entered as constraints. One of the bounds may be dictated by a nonnegativity requirement, which is most conveniently implemented by checking the Non-Negative box in the Solver Parameters window. The evolutionary solver tends to work more efficiently when the decision variables are bounded.

The list in Box 9.1 describes particular settings that would be appropriate in the initial stages of using the evolutionary solver. Some of the values are Solver default values, while others are entered by the user, in some cases overriding the default values.

Returning to our example of nonlinear regression, suppose we set the initial values of the decision variables to a = 30.0 and b = 0.50 and check the Non-Negative option (so that we have lower bounds on both decision variables). We specify the problem, including upper bounds, as follows:

For the sake of comparison, we might initially run the nonlinear solver. It produces a solution with a total absolute deviation of 173.40. We turn now to the evolutionary solver, keeping in mind that due to randomness in the algorithm, we may not find that any two runs of the evolutionary solver match exactly. (Here, we leave the random seed at its default value of zero.)

Suppose we initialize the model with the decision variables as before, with a = 30.0 and b = 0.50, and run the evolutionary solver with a time limit of 20 seconds and a maximum time without improvement of 10 seconds. Solver runs to the time limit, finishing with a solution that reaches an objective of 160.106. Starting with this solution and rerunning the evolutionary solver achieves a small improvement in the objective to 160.104. (We can think of this run as repeating the first run but from a different starting point or as continuing the run that stopped at the time limit.) Starting instead with the solution produced by the nonlinear solver, and running the evolutionary solver with a 20-second time limit, also leads to a solution of 160.104. In each case, the Max Time parameter provides the stopping condition, but that may not be the case for other random seeds.

Whenever the Max Time limit is reached, Solver produces a Show Trial Solution window with the message: The maximum time limit was reached; continue anyway? At this stage, the user can choose whether to continue or stop. When we press the Stop button, the run terminates, and it is usually preferable to start a second run with the best solution found in the first run, as we illustrated earlier. By observing the real-time improvements displayed for the Incumbent in Excel’s message area, it seems likely that further runs should try to increase diversity, either by expanding the population size (e.g., to 50) or by increasing the mutation rate (e.g., to 0.10). However, a few such efforts cannot push the objective function below 160.104, as shown in Figure 9.3, where the two parameters and the objective function value are displayed to three decimal places. In a problem with so few variables and constraints, we might well be satisfied with this outcome, even though we cannot know (at least, from running the evolutionary solver) whether it is optimal.

Our example of nonlinear regression served two purposes. First, it allowed us to examine the main workings of the evolutionary solver—crossovers, mutations, and selection by a fitness criterion. Second, it illustrated a straightforward optimization problem in which the nonlinear solver may not work as well as the evolutionary solver. This is partly due to the existence of many local optima in the example, but it’s also true that evolutionary methods have proven particularly effective on complex regression problems. In the examples that follow, we focus more on the model than on the refinements needed in the options to produce a good solution.

9.3 THE MACHINE-SEQUENCING PROBLEM REVISITED

In the machine-sequencing problem, a set of jobs is waiting to be processed. The machine can work on only one job at a time, so the jobs must be processed in a sequence. The problem is to find the best sequence for a given objective function. In Chapter 7, we saw how to build an integer programming model for this problem. That model requires a number of disjunctive constraints to incorporate the conditions of feasibility. An alternative approach is available if we use the evolutionary solver.

We revisit the Miles Manufacturing Company (Example 7.4), in which we have six jobs waiting to be scheduled. Each job will be either on time or late, depending on the sequence chosen. If a job is late, the amount of time by which it misses its due date is called its tardiness. Tardiness is zero when a job completes prior to its due date. The objective is to minimize the total tardiness in the schedule.

Data from Example 7.4

This morning’s workload consists of six jobs, as described in the following table.

The problem is to sequence the six jobs so that total tardiness is minimized.

Figure 9.4 displays a model for this problem. The first module contains the tabulated data describing the specific problem to be solved. The next module contains a row of decision variables corresponding to the job sequence. Each position in sequence is assigned a job number (from 1 to 6). In the figure, jobs are sequenced in reverse numerical order. Since the job sequence does not necessarily match the numbered sequence in which the data appear, we use the INDEX function to access the processing times and due dates that match the job in each sequence position. For example, the formula in cell C11, for the processing time of the first job, is =INDEX($C$4:$H$6,2,C$10). The INDEX function references the element in the second row of the data in the column corresponding to the number in C10. A similar function in cell C13 references the third row of the data, with the formula =INDEX($C$4:$H$6,3,C$10).

The given processing times and due dates thus appear in rows 11 and 13. From the processing times, we can compute the completion times directly, as shown in row 12. In row 14, we compute tardiness values, working from the completion time and due date in the two rows directly above and using the formula =MAX(0,C12-C13) in cell C14, and then copying the formula to the right. We sum the tardiness values in cell C16; this total represents the value of the objective function.

In the cells corresponding to decision variables, we want to choose integers between 1 and 6. Therefore, our first instinct might be to add constraints that restrict the decision variables to integers no less than 1 and no greater than 6. However, those constraints permit the choice of some jobs more than once. We would have to add a module that tests for duplication and discards solutions that choose any job multiple times. Wouldn’t it be nice if we could avoid the intricacies of this filtering device and generate only solutions for which the integers in the decision cells contain no duplicates?

The capability we seek is usually called an alldifferent constraint: It ensures that the values of the decision variables form a consecutive set of integers with no duplicates. To implement the alldifferent constraint, we enter the cell range as the left-hand side and then use the drop-down menu of constraint types to select dif, as shown in Figure 9.5. The alldifferent constraint fills the designated range of cells with the integers from 1 to n in some order, where n is the number of cells in the range.

A comparison with the integer programming model of Figure 7.14 shows that the evolutionary solver model is more compact and easier to understand. Its layout on the worksheet resembles the calculations we might make if we were verifying the value of total tardiness with pencil-and-paper calculations. However, because the objective function relies on the INDEX function and on the MAX function, it is a nonsmooth model and cannot be solved using the linear solver.

We specify the problem as follows:

We run the evolutionary solver, starting arbitrarily with the solution 6-5-4-3-2-1 and using the options in Box 9.1, except that we need not check the box for bounds on the variables (or specify them as Non-Negative) when they are covered by an alldifferent constraint. In this case, evolutionary solver terminates quickly, with an objective of 35. In the Solver Results window, we find the convergence message: Solver has converged to the current solution. All constraints are satisfied. Because the convergence message indicates lack of diversity in the population before the time limit was met, a logical next step is to increase diversity. In this case, we increase the mutation rate to 0.10 and rerun, and our second run finds an improvement. This cycle can be repeated while improvements are found. If not, we can try modifying the initial sequence and rerunning Solver. After a few trials of this sort, Solver is likely to produce the solution shown in Figure 9.6, with a value of 33. We recognize this as the optimal value, from our work in Chapter 7. There is no guarantee, however, that another run of the very same model will terminate with this solution.

9.4 THE TRAVELING SALESPERSON PROBLEM REVISITED

We encountered the traveling salesperson problem in Chapter 7, and we saw how to find optimal solutions by starting with an assignment model and appending subtour elimination constraints as needed. This approach required the solution of a series of integer programs with an unpredictable number of constraints. For large problems, the manual task of keeping track of the appended constraints could be daunting even if the resulting integer programming problems could be solved in a reasonable amount of time. As an alternative, we look at a solution approach that relies on the evolutionary solver, revisiting the Douglas Electric Cart Company (Example 7.5).

Data from Example 7.5

Today’s schedule contains six colors (C1–C6) with cleaning times as shown in the table below.

The entry in row i and column j of the table gives the cleaning time required between product batches of color Ci and color Cj. Each production run consists of a cycle through the full set of colors, returning to the initial color, and the operations manager wishes to sequence the colors so that the total cleaning time in a cycle is minimized.

Using the evolutionary solver, our formulation can be much more compact and readable than the integer programming model. Figure 9.7 displays a spreadsheet model for Example 7.5. The first module contains the distance array, which serves as the given data for the problem. Then, in the second module, the decision variables are listed in row 13, showing the sequence of cities in the tour. For an n-city problem, this simply means a single row listing the integers from 1 to n, in some order. By definition, a tour must return to its starting point, so we repeat the starting city in cell I13. (This cell is not a decision variable; it is simply a reference to cell C13.)

Directly below the cells of the tour, we capture the distances between pairs of cities on the tour, as shown in Figure 9.7. Again, we can use the INDEX function for this purpose. For example, the distance corresponding to the pair in cells C13 and D13 is isolated in cell D14 with the formula =INDEX($C$5:$H$10,C13,D13), which is copied to the right. In the third module, consisting of cell D17, we compute the sum of the pairwise distances calculated in row 14. This sum represents the total tour length.

The inputs and outputs of this calculation are more natural than in the case of an integer programming formulation. More specifically, in our integer program, we used variables x_ij to indicate whether city j follows city i in sequence. (We also needed a set of constraints to ensure that the x_ij-values made sense.) In our evolutionary solver model, we use the layout to indicate the location of cities in sequence, leading to a model that matches the layout we might use when verifying the tour length manually. However, because we use the INDEX function as a component in the model’s objective function, this is a nonsmooth model, and it is not appropriate for either the linear solver or the nonlinear solver.

We specify the problem as follows:

Even with the default settings, we are likely to obtain a solution of 167, as shown in Figure 9.8. (In Chapter 7, we found that this value was optimal.) The evolutionary solver rather quickly finds the tour 3-1-2-4-6-5-3, which matches the optimal tour found in Chapter 7. (Starting the tour at city 1 corresponds to the solution 1-2-4-6-5-3-1.)

Is the evolutionary solver always capable of finding an optimum with such limited effort? Unfortunately, that’s not the case. It is difficult to generalize about the effectiveness of the evolutionary solver on sequencing problems, but some experience suggests that problems of finding the best sequence can be solved to optimality with modest effort if the sequence length is 10 or sometimes 15. In the traveling salesperson problem, as in the machine-sequencing problem, the model is simpler and the solution is obtained more quickly using the evolutionary solver than with an integer programming approach. The evolutionary solver deals with fewer variables and just one constraint in these sequencing models. However, the evolutionary solver cannot guarantee optimality, and its effectiveness declines as the number of variables increases. Next, we turn to problems that we have not previously solved, so that we will not know the optimum when we set out to find a solution.

9.5 BUDGET ALLOCATION

The evolutionary solver provides us with an opportunity to build a compact model, often using more natural spreadsheet logic than we might encounter in a linear programming or nonlinear programming model. We can often capture feasibility requirements in the details of our layout rather than with the explicit use of variables and constraints. However, the ability to exploit clever spreadsheet layouts disguises a relevant feature of the evolutionary solver: Specifying several constraints in the model formulation may compromise the effectiveness of the evolutionary solver and ultimately degrade its performance. Indeed, as a general guideline, we say that the ideal number of constraints to have in a model for the evolutionary solver is actually zero.

Of course, we have already recommended the Solver option for requiring bounds on variables, but that is a very minor imposition on the model. In fact, by limiting the range of values that the search will explore, a set of intelligent bounds on the decision variables can improve the effectiveness of the search. Moreover, it is often convenient to use the check box for making otherwise unconstrained variables nonnegative. These features aside, the ideal number of additional constraints is still zero. This guideline is not intended to discourage the recognition of constraints; rather, constraints may often be necessary in modeling. What we actually want to avoid, as much as possible, is the specification of constraints in the Solver Parameters window. The evolutionary solver’s ability to accommodate nonsmooth functions provides us with an indirect way of representing constraints while keeping the model specification simple: We can incorporate penalty functions that penalize infeasibilities without actually requiring them to appear in the Solver Parameters window. The budget allocation decision at Wilson Corporation provides a case in point.

A spreadsheet model for the committee’s decisions is shown in Figure 9.9. Normally, in the Solver Parameters window, we would prescribe upper and lower bounds on the variables (B5:D5 <= D13 and B5:D5 >=B11:D11) and then add the budget constraint as B13 <= D13. As mentioned earlier, it is a good idea to require bounds on the decision variables, but we can avoid the explicit budget constraint. We do so with a penalty for infeasibility. In other words, we can check whether the budget constraint is satisfied, and if not, we can penalize the objective function.

The modifications are displayed in Figure 9.10. First, we impose a penalty in cell F13 with the formula =IF(B13>D13,999,0). Whenever a set of budget allocations exceeds 64, this cell will take the value 999. Next, we create a new cell to serve as the objective function in F7, with the formula =B7-F13, thus subtracting the penalty from the total benefit. When we ask Solver to maximize this value, the penalty of 999 is large enough to provide a strong incentive to meet the budget constraint, even though no constraint is explicitly recognized. The Solver Parameters window holds no constraints other than the required bounds on the decision variables, and this streamlined specification allows the evolutionary solver to perform more effectively than it would if the budget constraint were explicit. By applying this method, the committee members at Wilson Corporation can use the evolutionary solver to find a budget allocation that is virtually optimal, even though the model contains nonsmooth functions and local optima.

Obviously, this penalty technique could be applied in minimization problems by simply adding a penalty to the original objective function, and it could be extended to deal with several constraints in either maximization or minimization models.

9.6 TWO-DIMENSIONAL LOCATION

In many location decisions, costs are mainly determined by geographic distances, and it is possible to gain some insight into location possibilities by building models based on the geometry of physical location. Consider the location problem facing Drezner Chemical Company.

A model for the problem is shown in Figure 9.11, with some columns omitted. The first module contains the customer location data—100 pairs of (x, y) values describing each customer’s location, organized into 10 sets for each of 10 clusters. The second module contains the decision about the plant’s location, represented by x- and y-coordinates in cells B20:C20. This module also contains the objective function. The Results module contains distances from the plant to each of the 100 customers, again organized in 10 sets of 10. At the bottom of the Results module, we calculate the minimum distance in the cluster, and the objective function (cell E20) sums the lengths of the 10 distances and multiplies by two to account for round trips.

We specify the model as follows:

The last of these constraints can be omitted if we check the box for nonnegative variables, but in any case, this model is ready for the evolutionary solver.

It is instructive to attack this problem with the nonlinear solver. Although the reliance on the square-root formula for distances might suggest that the nonlinear solver should work effectively, it turns out that the solution is sensitive to the starting point and several local minima exist. The table below lists five cases, showing the starting point, the solution produced by the nonlinear solver, and the corresponding value of the objective function.

We might be inclined to conclude that the optimal location is in the vicinity of (50, 50), with an objective function value close to 250. However, we discover a different story when we use the evolutionary solver.

When we switch to the evolutionary solver, we are very likely to find improvements. Recall that there is some built-in randomness and the evolutionary solver does not necessarily stop with the same solution each time. In addition, the developers of the evolutionary solver offer the following advice for producing solutions:

• Restart the evolutionary solver, using the solution it produced on the first run, to see if an improvement can be found.
• Restart with a larger Population Size parameter and/or a larger Mutation Rate parameter. These changes will result in longer runs, and they tend to examine a larger number of candidate solutions.
• Restart the evolutionary solver with a tighter convergence value.
• Switch to the nonlinear solver and see whether it can produce an improvement.

Finally, some insight may come from examining Solver’s population report. Stability in the best values and relatively small standard deviations are signs to look for. Those signs suggest little room for improvement.

Using just the first of the listed suggestions and restarting Solver a few times, we are likely to encounter a solution that improves on the result found by the nonlinear solver, reducing the objective to 244.05. Expanding the population size to 50 and then to 100 and the mutation rate to 0.10 and then to 0.15, we can produce a solution with the objective function value of 217.61 at a plant location of (87.33, 53.43). By using the evolutionary solver, Drezner can find a location that improves on the solution generated by the nonlinear solver. If the distance metric is a good proxy for annual distribution expenses, Drezner will be able to reduce its expenses more than 13% by using the evolutionary solver, as compared to the decisions it would have reached using the nonlinear solver.

9.7 LINE BALANCING

The line-balancing problem arises in the design of a new production process for assembled products. Examples might include home appliances (refrigerators), electronics (televisions), light vehicles (lawn mowers), and automobiles. At the end of the product design phase, the product and its components are well known, and so are the specific tasks that must be carried out to make the product. The next step is to design the production line on which the product will be assembled.

The first type of information is the time required for each task. Required times might be based on previous experience with the same task in other lines or estimated by experts in work measurement techniques. The second type of information is precedence information. In other words, we need to know which tasks must be completed before some other task can begin. We say “task j precedes task k” to mean that k cannot begin until j is completed. Precedence information can be expressed in a list or in a diagram.

The production line typically has a target output rate—so many units per hour. The cycle time is the inverse of the output rate. For example, if we specify a target of 5 units per hour, the cycle time is 1/5 of an hour, or 12 minutes.

The physical production line consists of several workstations, typically numbered according to their position along the line. At each station, a single operator carries out a set of tasks. The problem is to assign the various tasks to stations. The criterion is to use as few stations as possible, since the number of stations dictates the number of operators and therefore the labor cost per unit. Two types of constraints apply. First, the amount of work assigned to any individual station may not exceed the cycle time; otherwise, the target production rate cannot be met. Second, no task can appear earlier in the line (i.e., at a lower-numbered station) than any of its predecessor tasks. An example arises at Munoz Manufacturing Company, in the assembly of microwave ovens.

The precedence relations among activities in a line-balancing problem present a significant challenge in formulating and implementing an optimization model. Moreover, optimization models usually require a large number of variables for a design of realistic scale. For those reasons, line-balancing problems are often solved by heuristic methods. Here, we describe an approach to solving the line-balancing problem that relies on the evolutionary solver.

Figure 9.12 shows a spreadsheet model, with the given information reproduced in columns A–D. The optimization model occupies columns F–L. Row 3 contains the desired cycle time, a penalty, and the objective function. The penalty, shown in this example as the value 999, must be a large number adjusted to the scale of the data in the problem.

The range F7:F18 contains the decision variables of the model. These are the station numbers assigned to the tasks. These variables must be integers starting at 1 and increasing to the number of stations in the solution. Although we don’t know that number in advance, we can make a conservative guess and use this guess as an upper bound when we specify the problem. The solution in column F of Figure 9.12 arbitrarily assigns two tasks to each station, proceeding roughly in order of the tasks. Columns G and H reference the predecessors in columns C and D and look up their stations using the INDEX function. The two columns allocated to the predecessor list in the given data (columns C and D) and the two columns allocated to the predecessor-station list in the model (columns G and H) are used because no task in the problem has more than two predecessors. Obviously, this layout would have to be modified for problems that contain more than two predecessors for some tasks.

Column I contains a feasibility check to see whether each task is assigned a station number at least as large as that of its predecessors. If not, the penalty from cell E2 is displayed. In the solution of Figure 9.12, task 10 is assigned to station 6 and task 11 to station 5. But task 10 is a predecessor to task 11, so those assignments are out of precedence order. Hence, the penalty in cell I17 is imposed with the use of an IF function.

Columns J, K, and L represent a table that examines the solution station by station. (This table may actually not need the same number of rows as the rest of the model, but extra rows can simply be assigned zeros.) Column K shows the total time assigned to each station, using the SUMIF function (see Box 9.2). Finally, column L contains another feasibility check and assigns a penalty to any station assigned a total time that exceeds the desired cycle time in cell C3.

Finally, cell G3 is the objective function. It contains the maximum value among the decision variables (the assigned station numbers), augmented by the total of the penalties. The use of penalties thus substitutes for explicit feasibility constraints. The only constraints that need to be specified for Solver are the upper and lower limits on the station assignments. As mentioned earlier, the lower limit is obviously one, but the upper limit requires an educated guess. In the worst case, each task would be assigned its own station, so we can always use the number of tasks as an upper limit. We specify the problem as follows:

One last step is helpful in the line-balancing model. As we use the evolutionary solver to search among solutions, it is helpful to know a lower bound on the minimum possible number of stations. This lower bound can be calculated by taking the sum of the task times, dividing by the desired cycle time, and rounding up to the next larger integer. This bound follows from the observation that if the tasks were packed into stations with perfect efficiency, the sum of the task times at each station would equal the desired cycle time, and the total sum of the task times divided by the cycle time would give the number of stations. In Example 9.2, the sum of the task times divided by the desired cycle time yields the value 4.67, which rounds up to 5. This calculation appears in cell G20. It allows us to stop searching if we see that the evolutionary solver has located a solution with this value. However, it is important to keep in mind that the lower bound may not be achievable; the optimal solution may lie above the lower bound, so we will not always be able to tell whether our searching should be terminated. In Example 9.3, the evolutionary solver leads us repeatedly to a solution with six stations, but we cannot be sure whether an improvement to five is possible. Figure 9.13 shows one of those solutions. In this solution, task 1 alone is assigned to station 1, tasks 2–4 are assigned to station 2, and then tasks are assigned in numerical order, two to a station. From this solution, however, we cannot know whether a five-station solution exists, but Munoz still has a reasonably efficient set of station assignments for its assembly line.

9.8 GROUP ASSIGNMENT

In several different application areas, a common problem involves the organization of items or people into groups. Often, the goal is to place similar items in the same group, as in cellular manufacturing (where we try to group similar parts together) or in positioning analysis (where we try to group similar products together). Sometimes, the goal is the opposite: to place different items in the same group. A familiar example in educational programs involves the formation of diverse student teams (where we try to form groups of students with dissimilar backgrounds for the purposes of carrying out a particular group task). Business applications of the same type of model arise when consultants are assigned to different project teams or trainees are assigned to discussion groups. An example of forming student groups arises in a typical course project.

In Example 9.4, each student is described by a string of four binary digits. For example, a male student from the United States who had not majored in accounting but had worked for an accounting firm would be represented by the string {0, 1, 1, 0}. A natural definition of decision variables for this problem is the following:

• x_jk = 1 if student j is assigned to group k, and 0 otherwise

Suppose now that we want to form five teams of four students each. We can express the essential constraints in the problem as follows:

The first set of these constraints fixes the size of each group; the second set ensures that each student is assigned to a unique group. If we model the decisions this way, the problem contains 25 constraints and 100 variables. This is too large a pair of numbers to expect the evolutionary solver to perform effectively.

The usual approach to an objective function builds on a metric that, for each attribute, calculates the sum of squared differences from the population average. Suppose, for example, that there are 10 accounting majors in the group of 20. Then, the average number per group is two. Suppose that the number of accounting majors assigned to the respective groups follows the profile {1, 2, 2, 3, 2}. Then, the calculation of the performance measure is as follows:

For the profile {1, 0, 2, 3, 4}, the metric is 10. Clearly, the ideal distribution of accounting majors among the groups would generate a metric of zero. For an objective function, we usually calculate the metric for each attribute and then sum over the attributes. This objective function can thus be expressed as a nonlinear function of the decision variables x_jk.

Although this is a natural formulation of the problem, it creates difficulties for two types of solution approaches. First, a direct formulation as an optimization problem leads to a nonlinear programming model with integer variables. As we pointed out in Chapter 8, this class of problems is poorly suited to the nonlinear solver. Instead, it makes sense to tackle the problem with the evolutionary solver. However, the natural formulation is also poorly suited to the evolutionary solver because it has many constraints and variables.

An alternative formulation of the problem can take advantage of the alldifferent constraint. Here, we let

where there are 20 positions: four corresponding to the first group, four for the second group, and so on. The assignment of students to positions is equivalent to an assignment of students to groups. In our example, the y_i values need to satisfy the alldifferent constraint for the integers from 1 to 20. From that definition, we can build a spreadsheet model well suited to the evolutionary solver. Figure 9.14 shows the model. The problem data occupy columns A–E, with a four-element string for each student. The solution is described in columns I–K, where the shaded decision cells give the assignment of student numbers to groups and positions. The squared differences between each group’s attribute count and the population mean are calculated in columns P–S, and their sum appears in cell G5 as the objective function. Although this may seem to be a complicated way of computing the objective, it is nevertheless suitable for the evolutionary solver.

We specify the problem as follows:

Again, the alldifferent constraint is sufficient to capture the constraints of the model. Starting with different assignments, the evolutionary solver takes us in most cases to a solution with a metric of 4 quite quickly (see Fig. 9.15), suggesting, perhaps, that this is likely to be the optimal value. Alternative starting points and modifications of the options do not seem to produce any improvement. Again, this is stronger evidence that we might have found the optimum, although the evidence is not conclusive.

By using the evolutionary solver, administrators at the Accounting Department can achieve their assignment goals where other methods, such as nonlinear integer programming, would likely have failed.

The group assignment problem illustrates the fact that there may be creative ways of formulating models to take advantage of the alldifferent constraint. This means that we may want to think beyond the typical structures of linear and nonlinear programming models, but no standard templates have been developed in this regard.

SUMMARY

The evolutionary solver contains an algorithm that complements the linear solver, the nonlinear solver, and the branch-and-bound procedure. Unlike those algorithms, however, it does not explicitly seek a local optimum or a global optimum. Nevertheless, it can often find optimal solutions to very difficult problems, and it may be the only effective procedure we can apply when a nonsmooth function exists in the model.

The considerations influencing the building of models for the evolutionary solver are different from those for linear and nonlinear programs. Because nonsmooth functions are permitted, we have great flexibility in drawing on Excel’s various built-in functions if we wish to calculate complex results in convenient ways. Also, experience suggests that the evolutionary solver performs best if the number of variables and the number of constraints is not large. To avoid constraints, we can often impose a numerical penalty when a condition is violated and include the penalty in the objective function instead of entering the constraint explicitly. Having built a model this way, it is helpful if we can start with an initial solution that satisfies all constraints—that is, a solution without penalties. Otherwise, the evolutionary solver may not be effective at finding feasible solutions (those without penalties) in models that contain penalty terms in the objective.

A conceptual guideline for building models for the evolutionary solver imagines a scenario in which we’re asked to verify an optimal solution. The first question we might ask is how to present the decision variables—that is, what is the most convenient way to display the decisions? Recall that in the case of sequencing problems, we were able to envision the layout of a task sequence. In effect, we were able to visualize tasks adjacent to each other and then duplicate this structure on the spreadsheet. In general, we want to choose the simplest way to describe the decisions and place them in the spreadsheet.

Once we have a layout for decisions, the next question is how to calculate the corresponding value of the objective—that is, what calculations would we make, starting with the decision variables, to confirm that a proposed objective function value was actually correct? The logic of these calculations is then brought directly to the spreadsheet, forming the logical structure at the heart of the model while using any functions that perform the task conveniently.

The evolutionary solver is not likely to be trapped by local optima, as is the case with the nonlinear solver. This feature is advantageous in searching for good solutions to problems containing nonsmooth functions, especially nonlinear problems with integer variables. On the other hand, we must realize that the search procedure is both random (subject to probabilistic variation) and heuristic (not guaranteed to find an optimum). For that reason, we usually reserve the use of the evolutionary solver for only the most difficult problems.

The evolutionary solver works with a set of specialized parameters. Although we offered default settings, these settings are merely a starting point. Different choices might be suitable for different problem types. In addition, we may want to use one set of choices at the start and then other settings in subsequent runs, while we look for improvements. As compared to arbitrary settings, the intelligent selection of these parameters can enhance the performance of the evolutionary solver considerably. Aside from the guidelines given here, practice and experience using the evolutionary solver are the key ingredients in effective parameter selection.

EXERCISES

1. 9.1 Miles Manufacturing (Revisited): Revisit the scenario of Example 7.4, and associate a weighting factor with each job. Now, we can take our objective to be the smallest maximum weighted tardiness in the schedule, where a job’s weighted tardiness is the product of its tardiness and its weight. The weights of the jobs are listed in the full table of data given below.

   Job number	1	2	3	4	5	6
   Processing time (hours)	5	7	9	11	13	15
   Weight	8	8	6	6	4	2
   Due date (hours from now)	28	35	24	32	30	40

   1. What is the smallest maximum weighted tardiness for the sequence (5-3-1-2-4-6) found in Example 7.4?
   2. Build a model for this problem for solution with the evolutionary solver. Initialize the run with the sequence in part (a). What is the optimal value of maximum weighted tardiness?
2. 9.2 Scheduling a Shop: Midwest Parts Supply (MPS) is a fabricator of small steel parts that are sold as components to manufacturers of electronic appliances and medical equipment. In the MPS fabrication department, steel sheets are subjected to a series of three main operations—cutting, trimming, and polishing. Each job must have the operations completed in this order, and each machine sees the same job order, so it is sufficient to specify a single job sequence in order to describe a schedule. No machine can process more than one job at a time.

   This morning, 10 jobs have been released to the shop by the ERP system, and the production manager is interested in minimizing the time it takes to complete the entire schedule, usually referred to as the schedule makespan. The following table gives the number of hours required for each operation.

   Job	1	2	3	4	5	6	7	8	9	10
   Cutting time	1	5	3	7	9	7	8	8	3	6
   Trimming time	2	9	2	10	7	6	9	9	1	1
   Polishing time	9	7	3	4	7	8	9	4	1	3

   Build a model for this problem for solution with the evolutionary solver. Initialize the run with the jobs in numbered order. What sequence achieves the minimum makespan and what is the minimum length of a schedule?

3. 9.3 Planning a Tour: Recent graduate and amateur world traveler Alastair Bor is planning a European trip. He has decided to make one stop in each of 12 European capitals in the time he has available. He wants to find a sequence of the cities that involves the least total mileage. He has calculated intercity distances using published data on latitude and longitude and applying the geometry for arcs of great circles. These distances are shown below.

   		Ams.	Ath.	Ber.	Brus.	Cope.	Dub.	Lis.	Lon.	Lux.	Mad.	Par.	Rom.
   From	Amsterdam	—	2166	577	175	622	712	1889	339	319	1462	430	1297
   	Athens	2166	—	1806	2092	2132	2817	2899	2377	1905	2313	2100	1053
   	Berlin	577	1806	—	653	348	1273	2345	912	598	1836	878	1184
   	Brussels	175	2092	653	—	768	732	1738	300	190	1293	262	1173
   	Copenhagen	622	2132	348	768	—	1203	2505	942	797	2046	1027	1527
   	Dublin	712	2817	1273	732	1203	—	1656	440	914	1452	743	1849
   	Lisbon	1889	2899	2345	1738	2505	1656	—	1616	1747	600	1482	1907
   	London	339	2377	912	300	942	440	1616	—	475	1259	331	1419
   	Luxembourg	319	1905	598	190	797	914	1747	475	—	1254	293	987
   	Madrid	1462	2313	1836	1293	2046	1452	600	1259	1254	—	1033	1308
   	Paris	430	2100	878	262	1027	743	1482	331	293	1033	—	1108
   	Rome	1297	1053	1184	1173	1527	1849	1907	1419	987	1308	1108	—

   Build a model for this problem suited to the evolutionary solver. Initialize the model with the alphabetic sequence of the cities and optimize the tour length. What sequence achieves a minimum distance tour, and what is the minimum tour length?

4. 9.4 Cutting Stock: Poly Products sells packaging tape to industrial customers. All tape is sold in 100-foot rolls that are cut in various widths from a master roll, which is 15 in. wide. The product line consists of the following widths: 2″, 3″, 5″, 7″, and 11″. These can be cut in different combinations from a 15-in. master roll. For example, one combination might consist of three cuts of 5″ each. Another combination might consist of two 2″ cuts and an 11″ cut. Both of these combinations use the entire 15-in. roll without any waste, but other combinations are also possible. For example, another combination might consist of two 7″ cuts. This combination creates one inch of waste for every roll cut this way.

   Each week, Poly Products collects demands from its customers and distributors and must figure out how to configure the cuts in its master rolls. To do so, the production manager lists all possible combinations of cuts and tries to fit them together so that waste is minimized while demand is met. (In particular, demand must be met exactly, because Poly Products does not keep inventories of its tape.) This week’s demands are shown in the table.

   Size	2″	3″	5″	7″	11″
   Demand	60	50	40	30	20

   1. How many combinations can be cut from a 15-in. master roll so that there is less than 2 in. of waste (i.e., the smallest quantity that can be sold) left on the roll?
   2. Build a model for this problem suited to the evolutionary solver. Initialize the model with one of each possible combination. Find a set of combinations that meets demand exactly and generates the minimum amount of waste. (Stated another way, the requirement is to meet or exceed demand for each size, but any excess must be counted as waste.) What is the minimum amount of waste?
   3. Repeat part (b) for the following set of demands and find the minimum amount of waste.

   Size	2″	3″	5″	7″	11″
   Demand	20	30	40	50	60

5. 9.5 Locating Warehouses: Southeastern Foods has hired you to analyze their distribution system design. The company has 11 distribution centers, with monthly volumes as listed below. Seven of these sites can support warehouses, in terms of the infrastructure available, and are designated by (W).

   Center	Volume	Center	Volume
   Atlanta (W)	5000	Memphis (W)	7800
   Birmingham (W)	3000	Miami	4400
   Columbia (W)	1400	Nashville (W)	6800
   Jackson	2200	New Orleans	5800
   Jacksonville	8800	Orlando (W)	2200
   Louisville (W)	3000

   The monthly fixed cost for operating one of these warehouses is estimated at $3600, although there is no capacity limit in their design. Southeastern could build warehouses at any of the designated locations, but its criterion is to minimize the total of fixed operating costs and variable shipment costs. Information has been compiled showing the cost per carton of shipping from any potential warehouse location to any distribution center.

   	Atl	Bir	Col	Jac	Jvl	Lvl	Mem	Mia	Nash	NewO	Orl
   Atlanta	0.00	0.15	0.21	0.40	0.31	0.42	0.38	0.66	0.25	0.48	0.43
   Birmingham	0.15	0.00	0.36	0.25	0.46	0.36	0.26	0.75	0.19	0.35	0.55
   Columbia	0.21	0.36	0.00	0.60	0.30	0.50	0.62	0.64	0.44	0.69	0.44
   Louisville	0.42	0.36	0.50	0.59	0.73	0.00	0.38	1.09	0.17	0.70	0.86
   Memphis	0.38	0.26	0.62	0.21	0.69	0.38	0.00	1.00	0.21	0.41	0.78
   Nashville	0.25	0.19	0.44	0.41	0.56	0.17	0.21	0.91	0.00	0.53	0.69
   Orlando	0.43	0.55	0.44	0.70	0.14	0.86	0.78	0.23	0.69	0.65	0.00

   1. Build a model for this problem suited to the evolutionary solver. Initialize the model with all warehouses in the configuration. What is the minimum total cost?
   2. To achieve the cost in (a), which warehouse locations should be used?
6. 9.6 Locating Emergency Centers: After the damage caused in Florida by a series of severe hurricanes, the governor ordered the Florida Emergency Management Agency (FLEMA) to design a systematic plan for emergency services following severe weather events. The state has 11 emergency offices, and it would be possible to build a warehouse next to each of the offices to store emergency equipment. As a consultant to FLEMA, you were asked to determine how many centers would be needed to ensure that there would be a warehouse within 50 miles of any emergency office. After studying your recommendation, however, FLEMA’s director decided that the cost of the plan would be prohibitive, so a revised formulation was developed. This one requires building just four warehouses.

   With this standard in mind, you have obtained the distances between the 11 offices (identified by their cities). FLEMA would like to ensure that there will be a warehouse center within x miles of any office.

   	DB	Ft L	Ft M	Gain	Mia	Nap	Orl	St P	Sara	Talla	Tam
   Daytona Beach	0	229	207	98	251	241	54	159	186	234	139
   Ft Lauderdale	229	0	133	312	22	105	209	234	202	444	234
   Ft Myers	207	133	0	230	141	34	153	110	71	356	123
   Gainesville	98	312	230	0	331	264	109	143	179	144	128
   Miami	251	22	141	331	0	107	228	251	214	463	245
   Naples	241	105	34	264	107	0	187	143	107	389	156
   Orlando	54	209	153	109	228	187	0	105	132	242	85
   St Petersburg	159	234	110	143	251	143	105	0	39	250	20
   Sarasota	186	202	71	179	214	107	132	39	0	286	53
   Tallahassee	234	444	356	144	463	389	242	250	286	0	239
   Tampa	139	234	123	128	245	156	85	20	53	239	0

   What is the minimum value of x that can be achieved when there are four warehouses in the system? To answer this question, build a model for this problem suited to the evolutionary solver. Initialize the model with all (11) warehouses in the configuration.

7. 9.7 Scheduling Power Plants: During the next 8 months, Metropolis Power Company forecasts the demands shown below (measured in thousands of kwh).

   Month	1	2	3	4	5	6	7	8
   Demand	96	154	148	77	84	92	119	126

   The power will be supplied from the four generating facilities, GF1–GF4. The facilities are each characterized by a generating capacity, a monthly operating cost, a startup cost, and a shutdown cost. These are each shown in thousands of dollars in the table below. When a generator is in operation, it provides service at its full capacity, even if that exceeds demand. No operating cost is saved by partial (rather than full) use of a generator’s capacity. At the beginning of each month, it is possible to shut down any of the facilities that have been operating or to start up any of the facilities that have been idle, with the cost implications indicated in the table. At the start of month 1, facilities GF1 and GF2 are in operation.

   Facility	Capacity	Cost	Startup	Shutdown
   GF1	70	8	4	3
   GF2	60	7	3	2
   GF3	50	6	3	2
   GF4	40	5	2	3

   Build a model for this problem suited to the evolutionary solver. Initialize the model with your intuitive guess as to a good policy. What is the minimum total cost of providing the power demanded?

8. 9.8 Balancing Workloads: You have four (identical) facilities with existing workloads of 150, 170, 220, and 240. You have 10 incoming orders, and you know how much of a workload each represents. You want to distribute the workload across the facilities in such a way as to balance the total workload (existing plus new) as evenly as possible. No order can be split among different facilities. If the workloads cannot be made equal, then the objective is to minimize the maximum workload on any of the facilities. The new arrivals have workloads of 17, 28, 32, 47, 55, 58, 64, 66, 72, and 88.
   1. Invent a rule of thumb for making the workload assignments one at a time, without revisions. What is the maximum workload generated by your rule of thumb?
   2. Build a model for this problem suited to the evolutionary solver. Initialize the model with the solution produced by your rule of thumb in (a). What is the optimal value of the objective function and what are the corresponding assignments?
9. 9.9 Assigning Teams: A new class of 15 students has been admitted to the graduate Film Studies program at the State University. During much of the first year, these students will be working on teams, producing short films. The program director wants to assign students to teams so that the teams are as diverse as possible. There will be three teams of five students each.

   Diversity is measured based on four characteristics or factors: undergraduate film major (1 if yes, 0 if no), previous employment in the film industry (1 if yes, 0 if no), interest in documentaries (1 if so, 0 otherwise), and gender (1 if female, 0 if male). Thus, each student is represented by four factor ratings.

   Student	UG	Emp	Int	Feml
   1	0	0	0	0
   2	0	1	1	0
   3	1	0	1	1
   4	1	0	0	0
   5	0	1	1	0
   6	0	0	1	1
   7	1	0	0	0
   8	0	0	1	0
   9	0	0	1	1
   10	0	1	0	0
   11	1	1	1	0
   12	0	0	1	0
   13	1	0	0	1
   14	1	0	1	0
   15	0	1	0	0
   Total	6	5	9	4
   Average	2.00	1.67	3.00	1.33

   For a given factor j, team i has a factor rating (c_i,j for factor j) equal to the total number of 1’s among its team members. The challenge is to convert a profile of factor ratings into a quantitative measure of diversity. A specific diversity measure has been adopted, based on the principle that if the teams “resemble” each other, then the makeup of the teams must be diverse. The calculation is made as follows. Find the average factor rating per team. (This figure can be computed from the raw data, as shown in the table.) For each group, calculate the absolute deviation between its rating and the average factor rating on the same factor. Sum the four deviations to get the group value. Sum the three group values to get a total. Minimize the total. This measure would have a value of zero if the teams resembled each other perfectly. In symbols, the diversity measure is

   

   Build a model for this problem suited to the evolutionary solver. Initialize the model with your intuitive guess as to a good policy. Find the assignment of students to teams that minimizes the diversity measure z.

10. 9.10 Assigning Rides: You are organizing rides for a group of campers going on an all-day, off-site trip. You have lined up some drivers, and your problem, essentially, is to assign campers to drivers. The drivers, and the capacities of their cars, are provided in the following table.

    Driver	Capacity
    Saul	5
    Chris	4
    Rob	3
    Erick	5
    Anna	6
    Jim	5

    The campers represent different age groups. Each age group is to be delivered to a different location. Thus, if a car holds campers of different ages, then the driver will have to drive to different destinations. An ideal solution would require each driver to go to just one location. However, such a solution is unattainable. The campers and their age groups are listed in the table below.

    Group	Camper	Group	Camper
    Age 7	George	Age 9	Eric
    	Marcia		Scott
    	Steve		Sarah
    	Andrew		Gretchen
    	Brian		Jamie
    	Suzanne		Liz
    Age 8	Lisa	Age 10	Patty
    	Ben		Francesca
    	Tommy		Adrian
    	Vanessa		Ali
    	Alberto		Cliff
    	Jason		Mickey
    	Sean		Matt

    Although we know what an “ideal” solution would look like, we need a metric for evaluating less-than-ideal solutions. One suitable metric is the total number of delivery stops.

    Build a model for this problem suited to the evolutionary solver. Initialize the model with your intuitive guess as to a good policy. Find the minimal number of stops and the assignment of campers to cars that achieves it.