Software Review
Premium Solver Platform for Excel
Developed by Frontline Systems, popular spreadsheet add-in expands capabilities with several new extensions
By Chris Albright
For many management science practitioners, especially those of us in a teaching environment, Excel's Solver add-in, developed by Frontline Systems, has become the preferred program for performing optimization. The purpose of this review is to describe extensions to Excel's built-in Solver (which I will refer to as the "standard" Solver from here on) that are now available from Frontline. These extensions, listed in the accompanying Product Summary, make it possible to solve much more difficult and much larger problems than ever before.
I assume that virtually all readers have at least a basic familiarity with the standard Solver add-in and its capabilities. However, many of you are probably not aware of the relatively new Solver extensions and what they can do. Indeed, Frontline's list of Solver products is growing rather quickly, and keeping track of the capabilities of the various products can be difficult. Therefore, I will initially arrange this so you can make a more intelligent decision about your needs.
Basic Descriptions of the Products
Standard Solver. I will begin with the standard Solver, which is bundled with Excel (or Microsoft Office). It is capable of solving linear, integer and "smooth" nonlinear problems with up to 200 decision variables ("changing cells" in Solver terminology) and, for nonlinear problems, up to 100 constraints in addition to simple bounds on the variables. It uses the simplex method for linear problems, branch and bound methods for integer problems, and the GRG (generalized reduced gradient) method for nonlinear problems. It provides several types of reports, and it supports an interface with the Visual Basic for Applications (VBA) macro language through functions such as SolverOK and SolverSolve. It works well with the small problems we tend to solve in the classroom (i.e. up to 50 changing cells), but probably its most frustrating feature is its inability to handle "non-smooth" models containing functions such as IF, COUNTIF, MAX and MIN-naturals in many Excel models.
Premium Solver. To overcome this drawback, Frontline developed Premium Solver. It incorporates somewhat improved algorithms for the basic linear, integer and nonlinear models. It can also solve larger problems: up to 400 variables and 200 constraints (in addition to bounds on variables) for smooth nonlinear problems, and up to 1,000 variables and no limit on the number of constraints on linear problems. In addition, it supports "fast problem setup" with linear and integer models built with the SUM, SUMPRODUCT, MMULT and Frontline's DOTPRODUCT functions.
For large problems, this feature can result in problem setup 5 to 50 times faster than with the standard Solver. However, the greatest advantage of Premium Solver is that it incorporates an Evolutionary Solver that is based on genetic algorithms. This allows us to model non-smooth nonlinear problems in a natural way. Instead of having to "trick" problems into a linear form, we can now use IF, MAX and other functions to model them more naturally. Of course, genetic algorithms tend to be slower, and there is never a guarantee that they will converge to the optimal solution, but the models themselves are much easier to generate and understand. (See Chapter 8 of Winston and Albright [2] for a sampling of such problems.)
Premium Solver for Education. Fortunately for textbook authors and students, Frontline has developed an educational version of Premium Solver. It is now included free with several management science textbooks, including Winston and Albright [2]. It is limited to 200 variables and, for nonlinear and non-smooth problems, 100 constraints in addition to bounds on variables, and its speed is about the same as the standard Solver. Again, its biggest advantage is the inclusion of Evolutionary Solver.
Premium Solver Platform. Most recently, Frontline has developed the Premium Solver Platform (PSP). PSP includes a wide range of improvements to the linear, GRG and Evolutionary Solver engines, and it supports multiple, field-installable Solver engines that can solve much larger and more difficult problems. These include the large-scale LP Solver, capable of handling 16,000 variables and 16,000 constraints (there is an even larger version that can handle up to 65,000 variables and 65,000 constraints), and a large-scale GRG Solver, capable of handling 4,000 variables and 4,000 constraints in addition to bounds on the variables. In addition, there are other, more powerful engines that can be hooked on to PSP, including XPRESS Solver and OptQuest Solver, but this review will not examine them.
The "standard" features of PSP (that is, without the extra Solver engines) that differentiate it from Premium Solver include the following:
- It handles larger non-smooth problems — up to 500 decision variables and 250 constraints, plus bounds on the variables. Its Evolutionary Solver is actually a hybrid of genetic and classical optimization methods, thus taking advantages of "smoothness" or linearity whenever possible.
- The GRG engine supports "multistart" or "clustering" methods for global optimization, essentially allowing the algorithm to start from many different starting solutions without any user involvement.
- The LP Simplex Solver handles both LP and quadratic programming (QP) problems, each of which can have up to 2,000 variables with no effective limit on constraints. A QUADPRODUCT function, essentially the equivalent of SUMPRODUCT for quadratic forms, is provided. It not only results in simpler formulas for quadratic forms, but it also provides the benefit of fast problem setup for QP models.
- The branch and bound algorithms for integer problems employ a more powerful set of extensions, which can speed up the solution by a factor of 100 or more over the standard Solver.
- There is a new type of constraint called the "alldifferent" constraint. (It is specified exactly like a binary or integer constraint — from a drop-down list.) This constraint specifies that the values in a range with N cells must be a permutation of the integers 1 to N. As such, it is a perfect a variety of combinatorial problems, such as the traveling salesman problem.
Installation
The installation of any of these products is extremely easy and takes only a few seconds. From the CD-ROM, you simply "run" the setup program for the product you want to install and then go through typical dialog boxes to perform the installation. It renames the current Solver .xla and .dll files (so that they can be restored easily later on, if needed) and then installs new ones. When you then launch Excel and run Solver, you will automatically run the version you just installed. It's that easy. Frontline claims that all you need is Excel 97 or later and Windows 95 or later, including NT/2000. However, it also states that your performance will depend on the amount of RAM you have — the more, the better.
The User Interface
If you are familiar with the standard Solver, you will have little difficulty getting used to the interfaces of Premium Solver, PSP or the large-scale extensions. They are all very similar to the standard Solver interface, except that they have extra options. Figure 1 shows the first dialog box for PSP. In the dropdown box to the right, I have chosen the Evolutionary Solver from a list of Solver engines. (Of course, this list will depend on what you have installed.) Note the Variables button. This is a toggle. If it reads Variables, you see the usual list of constraints to the left. If you click on this button, its caption changes to Constraints, and you then see a list of variables (changing cells) to the left. This is especially useful if your list of changing cells is long. (Long-time users of Solver will know what I mean, especially if they have graded students' assignments!)
Figure 1: Solver parameters
All of the Solver products have an Options button. When you click on it, the resulting dialog will depend on which Solver product you are using and which engine you are employing. Figure 2 shows the Options dialog for PSP when the Evolutionary Solver is being used, with the default settings selected. Some experience with the Solver engine (and the type of problem) is required to choose the "best" settings, but my experience is that you can always try the default settings and then change them, if necessary, to achieve or speed up convergence. Note the two check boxes that are marked. The first allows you to bypass the creation of reports, thus speeding up the solution process. If you do not tend to use these reports, you should check this box. The second forces you to put bounds on the changing cells. This is an especially good idea for the Evolutionary Solver, in that it reduces the size of the solution space and speeds up convergence considerably. The other options in this dialog are more technical, and it would take more space than I have to describe them adequately here. Besides, they differ from one Solver version and engine to another. However, they are well described in Frontline's supporting documentation.
Figure 2: Evolutionary solver options
Depending on the product, there may also be one other dialog, obtained by clicking on the Limit Options button in Figure 2. (It will read Integer Options for integer problems.) For PSP and the Evolutionary Solver, this dialog appears in Figure 3. The options at the top essentially tell the Evolutionary Solver how long to run, although you will still have a chance to select "Continue" if progress stops because of one of these conditions being met. The bottom read-only section of the dialog is handy. It shows the size of your problem in relation to the limits for this particular Solver product.
Figure 3: Evolutionary solver limit options
Once you fill out all of the dialog boxes and then click on Solve in Figure 1, the Solver "sets up" the model — which can take the majority of the solution time for some models — and then uses the selected algorithm to optimize. Fortunately, you can watch the progress in the Windows taskbar. This is particularly useful in Evolutionary or branch and bound runs, where you can see the incumbent and how fast it is changing. If you see that it is not making progress, you can always press the Ctrl-Break key combination to halt the algorithm and accept the incumbent solution.
Assuming that you let the Solver run to completion, you will eventually encounter a dialog similar to the one in Figure 4. This should be familiar to all Solver users. However, with the newer versions of Solver, there are more messages that can occur at the top. Frontline's documentation clearly explains what each of these means. Also, you now have the option of returning immediately to the Solver Parameters dialog box (Figure 1), which can be handy. Finally, if you asked to bypass reports in Figure 2, then these reports are disabled, as in Figure 4. Of course, if you did not ask to bypass the reports, then this is the time when they are created and placed on separate worksheets.
Figure 4: Solver results
Speaking of reports, the usual Answer, Sensitivity and Limits reports are still available. However, PSP offers three new reports: Linearity, Feasibility and Population. The Linearity report is useful if you obtain the "The linearity conditions required by this Solver engine are not satisfied." This report helps you locate the section of the model responsible for the nonlinearity. Similarly, the Feasibility report helps you locate the section of the model responsible for infeasibility, in case you should get that message. The Population report is especially geared toward the Evolutionary Solver. It gives you summary information about the entire population of candidate solutions at the end of the solution process. As with the standard Solver, these reports, if they are requested, are placed in separate worksheets.
Programming with VBA
All of the Solver products, including the standard Solver, allow you to automate the solution process with VBA, Excel's macro language. Essentially, Frontline has "exposed" a number of its functions to developers. For example, you can easily write a program to fill in the dialog boxes in Figures 1, 2 and 3, without the user ever seeing them, by using functions such as SolverOK, SolverAdd, SolverOptions and SolverSolve. (You can generate the code by recording the filling out of the dialogs. This is a convenient way to learn the Solver functions in the first place.) You can even capture the message reported in Figure 4, so that you can take appropriate actions. (For many examples of VBA Solver applications, see Albright [1].) As newer versions of Solver are developed, Frontline simply exposes more functionality to VBA programmers.
Frontline's Documentation
The documentation for these products is quite good. I received a 147-page User Guide for PSP and another 68-page User Guide for the extensions (OptQuest, Large-Scale LP and Large-Scale GRG). They clearly explain all of the functionality, the dialog options, the reports and the available VBA functions. They give you a few insights into good modeling techniques (including a few sample spreadsheets), but the majority of the coverage is geared to an explanation of the algorithms and dialog box options. These guides are probably not intended to be read from cover to cover but are more for reference. In any case, they are well written and contain all of the important material. In addition, this same information is available online.
Modeling and Performance
Now that I have explained the array of Solver products and have described their user interfaces, two questions remain: First, if you solve moderate-sized models, such as the kinds in Winston and Albright [2], is there any point in moving up to Premium Solver or PSP, possibly with the extra engines? Second, if you are solving large, difficult optimization problems, should you use a spreadsheet Solver at all?
In response to the first question, the answer obviously depends on the types of problems you need to solve. I see two basic limitations of the standard Solver. The first is that it is limited to 200 changing cells. This limit is not a big concern for typical classroom problems, but it can quickly become a concern for certain types of models. The types that come to mind immediately are network models. It doesn't take many nodes to generate a network with more than 200 arcs. For this reason alone, you might want to move up to a product that supports more changing cells.
The second drawback is the inability of the standard Solver to handle non-smooth models that contain IF, MAX and other Excel functions. Granted, some of these models can be linearized, in which case they can be solved quickly with the simplex method. However, the tricks necessary to linearize models are difficult for many users to understand. In these cases you can really benefit from the Evolutionary Solver, which can handle such non-smooth models. Although typical users will have little understanding of the details behind the genetic algorithms, they will at least be able to model a much wider set of problems — and do so with relative ease.
The second question is more difficult to answer. If you want to solve difficult problems with thousands of variables, should you use a spreadsheet? Here it is important to realize that all of the Solver products are able to do one thing only: they can optimize already existing spreadsheet models. They do not provide any help in formulating the models. It is still up to you to store the required data in the spreadsheet, create all of the logic with appropriate formulas, and do it in such a way that the Solver will recognize your formulas and constraints as valid. This is easier said than done for large models.
For a typical example, consider the standard product mix model with N products and M resources. The usual version of this model requires four sets of input data: a unit profit for each product, a unit usage for each product/resource combination, an availability for each resource, and (possibly) an upper bound for each product's production quantity. Besides non-negativity, there are two types of constraints: the usage of each resource cannot exceed availability, and the production quantity of each product cannot exceed its upper bound. The usual way to model this is to have a column for each product and a row for each resource. If we do it this way, consider the potential problems when N>256, the number of columns in Excel. (Of course, if N tends to be much larger than M, we could put products along rows and resources along columns — and I did this in the sample problems reported below — but there is still be a problem when M>256.)
To store the unit profits, the upper bounds on production, and the changing cells, we need to "wrap around" when we get to column IV (the last column in Excel). So for a 500-product problem, we might store the unit profits, say, in the "union" range Union(A1:IV1, A2:IJ2), and we could store the production quantities in a similar-shaped range. Similarly, the unit usage data, which is of size M by N, would have to be stored in several blocks of size M by 256 (or less than 256 for the last such block). This is not a big problem if we are importing the data from a database with a VBA program. It just requires some careful programming.
Now consider entering formulas and setting up the Solver if we store the data in this way. For the total profit, we cannot use the usual SUMPRODUCT function if N>256 because Excel requires the arguments of SUMPRODUCT to be rectangular. Fortunately, Frontline's DOTPRODUCT function will work, as in =DOTPRODUCT(Production, UnitProfits), where Production and UnitProfits are range names for the Union ranges. But consider the formula for the amount used of a particular resource, the dot product of the production quantities and unit usages for that resource. The unit usages for this resource will be spread over several noncontiguous rows, and a formula such as =DOTPRODUCT(Production, (UnitUsages!$A$1:$IV$1,UnitUsages!$A$52:$IJ $52)) is necessary. It can be done, but it is not exactly intuitive.
Finally, how do we specify the upper bound constraints in the Solver dialog box? It turns out that Solver will not accept the constraint Production <= UpperBounds, assuming these are the range names for the Union ranges. Instead, we have to specify these constraints row by row. In VBA, this can be done fairly easily with a For Each loop, where we loop through the Areas collection of the Union ranges, as in the following code. So again, it is possible, but it isn't exactly intuitive.
For Each area In UBRange.Areas
AreaCount = AreaCount + 1
SolverAdd Range("Production").Areas(AreaCount), 1,
"UpperBounds!" & area.Address
Next
As another example, consider the typical minimum cost network flow model. I believe the most natural spreadsheet formulation of this model is to list the data for arcs (origins, destinations, flows, unit costs and capacities) in columns and then specify the flow balance constraints for the nodes by using SUMIF functions. (See Chapter 5 of Winston and Albright [2].) Also, if the data for this problem are contained in a database, it is relatively easy to import them into Excel. (See Chapter 19 of Albright [1].) However, because of the SUMIF functions, the resulting model cannot take advantage of PSP's Fast Problem Setup. It will indeed optimize problems with thousands of arcs in a few seconds, but only after it has spent minutes setting them up.
Experience with Large Problems
Although I do not usually solve large optimization problems, I created a few to test the capabilities of PSP and the large-scale LP extension. The problems included: (1) standard product mix problems, (2) network flow problems, (3) fixed-charge transportation problems, (4) knapsack problems, and (5) a difficult assignment problem. All of these except for "(5)" are well known, so I will not describe them here. However, the assignment problem "(5)" is an interesting combinatorial problem suggested to me by a student who was about to be a summer camp counselor. The problem: Given that each of n boys has a list of other boys he would prefer to room with, and that there are k cabins with n/k boys each (with n/k assumed to be integer), find an assignment of boys to cabins that maximizes the total number of preferences achieved.
I make no claim that the data for my test problems are "realistic." For all of them, I used VBA programs to generate random data for problems of various sizes. (My files are available from www.indiana.edu/~mgtsci.) Then I experimented with "good" ways to model them in Excel. As I discovered, some ways yield much quicker solutions than others do. For example, for N-product, M-resource product mix problems, with N much larger than M and M<256, it is much better to list products down rows and resources across columns. As another example, large network flow models that take advantage of the SUMIF function to generate flows out of and into nodes can take PSP and the large-scale LP extension over an hour just to set up (and then mere seconds to solve). Therefore, for these problems I wrote a VBA program that lists, for each node, the identities of the nodes with arcs pointing in and those to which arcs are pointing out. This modeling technique allows the use of SUM rather than SUMIF functions, and it led to a vast improvement in setup time — from over an hour to about a minute.
As a final example, the camp assignment problem clearly calls for the Evolutionary Solver, but the form of the model still makes a difference. My first attempt had a changing cell for each boy that specified the cabin number to which he was assigned. This required a set of constraints saying that each cabin must have the right number of boys assigned to it. (Frontline claims that PSP's Evolutionary Solver can handle constraints, other than upper bound on variables, in the usual Solver way. However, my experience is that it is better to treat constraints as deviations from goals, with penalties in the objective.) A somewhat less obvious but more efficient model (suggested to me by Wayne Winston) was again to have a changing cell for each boy, but to let these be any permutation of 1 to n. The first n/k boys are then assigned by convention to cabin 1, the next n/k to cabin 2, and so on. The logic required another VBA program (and a custom function for counting achieved preferences), but it yielded a much quicker solution.
Table 1 contains results from a selected set of problems. All of these used PSP, and all were solved on an IBM T21 laptop, with a Pentium III 750-mHz processor and 128 MB of RAM. The first four problem types used the large-scale LP extension, whereas the camp assignment problem used the Evolutionary Solver. For the integer problems, I kept the integer tolerance at its default value of 0.05 (so that I cannot be certain that the final solutions are optimal), and for the Evolutionary Solver problems, I let the program run until there was no improvement in the last 100 seconds (one of its built-in options). With these provisions, the Solver reported that all problems were solved successfully. To save space, the only times reported are averages, rounded to the nearest second, over several problems with different random inputs. To be fair, I should note that there was some variation in these solution times, especially in the integer and Evolutionary Solver problems.
| Product Mix | ||||
| Number of Products | Number of Resources | Average Solution Time* | ||
| 1,000 | 200 | 20 | ||
| 5,000 | 200 | 275 | ||
| 10,000 | 200 | 833 | ||
| Network Flow | ||||
| Number of Suppliers | Number of Transshipment Points | Number of Demanders | Number of Arcs | Average Solution Time* |
| 10 | 10 | 50 | 1,528 | 6 |
| 10 | 20 | 100 | 5,643 | 59 |
| 10 | 60 | 100 | 10,706 | 219 |
| Fixed-Charge Transportation | ||||
| Number of Suppliers | Number of Demanders | Number of Variables | Average Solution Time* | |
| 50 | 100 | 5,050 | 201 | |
| 20 | 500 | 10,020 | 487 | |
| 10 | 1,000 | 10,010 | 554 | |
| Knapsack (Capital Budgeting) | ||||
| Number of Investments | Average Solution Time* | |||
| 1,000 | 16 | |||
| 5,000 | 234 | |||
| Camp Assignment | ||||
| Number of Kids | Number per Cabin | Average Solution Time* | ||
| 60 | 5 | 290 | ||
| 96 | 8 | 3 | 64 | |
| 180 | 6 | 595 | ||
| * All times have been rounded to the nearest second | ||||
I believe the results in Table 1 are encouraging. They show that large and/or difficult optimization problems can be solved in reasonable time with Frontline's Solver products. However, given the work that must be devoted to getting some models in the "right" form, especially for the network flow and camp assignment problems, I am not totally convinced that spreadsheet optimization is the best choice for really large optimization problems.
|
|
References
- Albright, S. Christian, "VBA for Modelers," Duxbury Press, 2001.
- Winston, Wayne and Albright, S. Christian, "Practical Management Science," 2nd edition, Duxbury Press, 2001.
Chris Albright teaches courses in the Operations & Decision Technologies Department in the Kelley School of Business at Indiana University. He has published more than 20 articles in the area of applied probability, and he has authored the books "Statistics for Business and Economics, Student Execustat 3.0 MiniGuide," "Practical Management Science, Data Analysis and Decision Making, and Managerial Statistics," and most recently the Excel-based "VBA for Modelers."
OR/MS Today copyright © 2001 by the Institute for Operations Research and the Management Sciences. All rights reserved.
Lionheart Publishing, Inc.
506 Roswell Street, Suite 220, Marietta, GA 30060, USA
Phone: 770-431-0867 | Fax: 770-432-6969
E-mail: lpi@lionhrtpub.com
URL: http://www.lionhrtpub.com
Web Site © Copyright 2001 by Lionheart Publishing, Inc. All rights reserved.