Hints for Building Readable, Manageable Models

[Dividing Line Image]

Often we receive technical support calls from users who have built models of several megabytes in size, who can't figure out why the Solver doesn't find the correct solution. Occasionally these models are well-structured, and we can quickly determine what is wrong. But all too often, we encounter "spaghetti models" which take many hours, or even days to analyze. This is costly both for users and support personnel. You can save yourself a great deal of trouble by adhering to a few simple rules of spreadsheet design from the outset. Our suggestions are outlined below.

An Example Model

To illustrate the design ideas which are discussed below, we'll use a simple example of a Product Mix model. In this optimization model, we are assembling three finished products (TV sets, stereos and speakers) from five different kinds of parts. Each finished product earns a different profit margin, as shown in row 17. We have a limited inventory of parts on hand, shown in column B, and we want to determine the number of finished products of each type to assemble that will yield the greatest total profit. The screen shot below is from Microsoft Excel, but an almost identical look can be achieved in Lotus 1-2-3 97.

Identify the Index Sets

A good first step is to identify the "index sets" underlying your model. Index sets are a concept from algebraic modeling languages such as AMPL, which can be readily applied to spreadsheet models. You will typically find that your decision variables (changing cells) and constraints are defined over sets or groups of things such as products, regions or time periods. In the Product Mix example above, the index sets are Products (TV Sets, Stereos and Speakers) and Parts (Chassis, Picture Tubes, Speaker Cones, Power Supplies and Electronics).

Once you have identified the index sets, it will become much easier to determine exactly what variables and constraints you will need. In the Product Mix example, the decision variables (the number of products to build of each type) are indexed over Products. The primary constraints in this problem (that the parts used of each type cannot exceed the supply on hand) are indexed over Parts. There is also a "non-negativity" constraint (the number of products built of each type cannot be negative) which is indexed over Products.

Lay Out the Index Sets in Columns and Rows

As illustrated by the Product Mix example above, it pays to lay things out so that the index sets occupy columns or rows. It is very common for the members of the index sets to appear as labels at the top of columns or at the left edge of rows. Where elements of your model are defined over two index sets, it is useful to orient one set column-wise and the other row-wise. Of course, in a more complex model, you may have many more index sets, with different numbers of members. In a two-dimensional spreadsheet, you'll have to manage the layout so that adding or removing members from one set (regions, say) will minimally interfere with the layout of elements indexed over other sets. When a model element is indexed over three or more sets, you'll have to create two-dimensional tables and repeat them across or down the spreadsheet in order to capture the third (or greater) dimension. You may be able to improve the readability and manageability of such a model with the help of spreadsheet outlining.

Allocate Cells for Decision Variables and Constraints

Next, you should allocate cells in columns and rows to hold the values of decision variables, and constraint left and right hand sides. Where possible, place these cells adjacent to the labels which represent the index set members. In the example above, the decision variables are in cells D9:F9 in Excel (or D9..F9 in 1-2-3), directly below the Product labels. The constraint right hand sides (parts in inventory) are in cells B11:B15, and the left hand sides (number of parts used) are in cells C11:C15. With this layout, if we had to add another product, we could insert a column, and to add another part we could insert a row.

Allocate Cells for Coefficients or Other Parameters

In a linear problem, the objective function and constraint left hand sides can be written in the form:

a1 * x1 + a2 * x2 + ... + an * xn

where the ais, which are called coefficients, stand for constant values and the xis stand for decision variables. (As discussed in Linear and Nonlinear Functions, the ais need only be constant in the optimization problem, i.e. not dependent on any of the decision variables.) Rather than write this as a single formula in a spreadsheet cell, you should place the coefficients in their own cells and use the SUMPRODUCT or DOTPRODUCT function to compute the actual function value. In the Product Mix example, the formula for the objective function at cell D18 is SUMPRODUCT(D17:F17,$D$9:$F$9). To compute the constraint left hand sides, you can enter SUMPRODUCT(D11:F11,$D$9:$F$9) in cell C11 and then copy this formula down to the next four cells.

In a nonlinear model you typically won't have coefficients in exactly this form; but you will still have various parameters which are "constant" in the problem yet may need to be changed later. Place these parameters in their own cells and label them appropriately. Doing so will make your model more readable and more manageable when you decide to modify your objective and constraints.

Aim for Uniform Indexing of Variables and Constraints

Most larger models are sparse in nature: Groups of constraints will depend on only a small subset of the decision variables. Where these subsets correspond directly to the index sets, you can lay out the constraints in appropriate columns and rows. At other times the pattern of dependencies will be more complex. When this happens, strive for uniformity: For example, write the constraints as if they depended on all (or a whole subset) of the variables, and use coefficients of zero (or for nonlinear models, parameters of 0, 1, etc.) to express the fact that some of the variables do not enter into the calculation. Doing this will make everything clearer at a later time when you re-examine the model.

Use Fonts, Borders and Shading

You can use fonts, borders and shading to make it clear how your model breaks down into index sets and related groups of decision variables, constraints, and coefficients or other parameters. Your spreadsheet program's formatting facilities make it very easy to apply this kind of formatting. In the Product Mix example above, borders are used to highlight the decision variables, the constraint left and right hand sides, and the coefficients of the objective function at D17:F17. Italics are used to distinguish the labels for index set members from other kinds of labels. In a full-color rendition of this model, shading is used within the bordered areas to further highlight the different model elements. You can look at the worksheets in the sample workbook SOLVSAMP.XLS, included with the Microsoft Excel Solver, or SOLVSAMP.123, included with the Lotus 1-2-3 97 Solver, for more examples of the use of fonts, borders and shading.

Use Defined Names (Range Names in 1-2-3) for Variables and Constraints

If you have identified index sets and laid out your variables and constraint left and right hand sides in columns and rows, then it is very easy to create names for the cell ranges representing these model elements. In Microsoft Excel, you use the Insert Name Define... and Insert Name Create... menu options to do this; in Lotus 1-2-3 97, you use the Range Name... menu option. Once you have defined appropriate names, it is much easier to locate and manipulate the elements of your model. For example, the Go To function lets you look up a defined name and let your spreadsheet program select (and highlight) the related cells. And the names you define will appear in the Set Target Cell, By Changing Cells, and Constraint list box entries in the Solver Parameters dialog.

In the Product Mix example, we can define the following names: Products = D9:F9, Parts_Used = C11:C15, Inventory = B11:B15, Profit_Margin = D17:F17, and Total_Profit = D18. Once we've done this, we can write formulas like:

SUMPRODUCT(Profit_Margin,Products)

for the objective function. When we define the variables and constraints for the Solver, we can either type in these names or select the relevant cells, yielding a Solver Parameters dialog like the one below:

In Microsoft Excel, if we define a name for an entire block of constraint coefficients, such as Bill_of_Materials = D11:F15, we can write an array formula such as:

{=MMULT(Bill_of_Materials,TRANSPOSE(Products))}

to compute all of the constraint left hand sides at once in cells C11:C15.

Such defined names will generally preserve or enhance your ability to modify and extend a model easily. In the Product Mix example, you can add products or parts to the worksheet without having to redefine any of the names, or re-do any part of the Solver Parameters dialog. While it isn't always this easy, proper layout and use of defined names can certainly make it easier for you to manage the development of your Solver models.