OR/MS Today - June 2001



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

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

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

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

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.

Product Summary
Premium Solvers for Microsoft Excel are available from:
Frontline Systems
P.O. Box 4288
Incline Village, NV 89450
Phone: 775-831-0300/888-831-0333
Fax: 775-831-0314
E-mail: info@frontsys.com
URL: www.solver.com

Product Pricing

Premium Solvers for Microsoft Excel
Premium Solver for Microsoft Excel V3.5 $495
Premium Solver Plus for Excel V3.5: $750
Premium Solver Platform for Excel V3.5: $995
Large-Scale LP Solver Engine V3.5*: $995
Extended Large-Scale LP Solver Engine V3.5: $2,495
XPRESS Solver Engine V3.5: $6,995
Large Scale GRG Solver Engine V3.5*: $995
OptQuest Solver Engine V3.5*: $995
LGO Global Solver Engine V3.5*: $995

Solver Engines require the Premium Solver Platform to run. These are commercial single-user license prices. Qualified academic users are eligible for discounts of up to 70 percent

Vendor Comments
Editor's note: It is the policy of OR/MS Today to allow developers of reviewed software an opportunity to clarify and/or comment on the review article. Following are comments from Daniel Fylstra, president of Frontline Systems.

We very much appreciate the effort that Professor Albright put into this review of Frontline's Premium Solver Platform (PSP). We're pleased that his test problems demonstrated the practicality of the PSP for larger-scale optimization problems. Even faster solution times are often possible; for example, the smallest mixed-integer fixed-charge transportation model in Table 1 can be solved in about 1 second, and the largest one in about 15 seconds (following problem setup) using the XPRESS Solver Engine for the PSP.

The Premium Solver Platform includes the equivalent of an algebraic modeling language processor, as well as several optimizers. "Problem setup" in the PSP involves model processing, and this processing time is included in the reported solution times. "Fast problem setup" provides a way to greatly speed up model processing, for LP models that use a limited set of Excel's functions, in the PSP Version 3.5. Frontline is currently testing the PSP Version 4.0, in which the equivalent of "fast problem setup" is extended to essentially all Excel functions and to linear, nonlinear and non-smooth models. This greatly simplifies the task of getting a large-scale model into the "right form."

As Professor Albright says, the Premium Solver products "do not provide any help in formulating the models" (outside of the documentation and examples provided). We feel this is true of most current approaches to optimization modeling. Creation of large-scale models that are both maintainable and quickly solvable is a craft of its own, as nearly any consultant to industry can attest. Indeed, we've seen many large and awkwardly formulated models created by industrial users of modeling languages such as GAMS or AMPL, some of which we have re-created as better structured models in spreadsheet form. The tools may change, but the need to teach good modeling skills will never go out of style!

We accept that Professor Albright isn't "totally convinced that spreadsheet optimization is the best choice for really large optimization problems," but we note that — as someone who usually doesn't build large models — he was able to quickly build and then improve several large-scale spreadsheet models in the course of this review. We've seen many less experienced modelers do the same thing with the Premium Solver Platform. We believe that the best tool is the one that is easiest to learn and that meets all the needs of the application, not just the optimization model. This often includes accessing a database, creating reports and graphs, and building a custom interface for end users — things that are very easy to do in Microsoft Excel and Office.

The OptQuest Solver, LGO Global Solver, XPRESS Solver, and, of course, future Solver engines for the PSP are not reviewed here, but we hope they will be the subject of future reviews. The XPRESS Solver Engine offers remarkable performance for LP/MIP problems. For users with global optimization or non-smooth optimization problems, commercial-quality software has traditionally been hard to find — but the OptQuest Solver and LGO Global Solver, plus the PSP's Evolutionary Solver and multi-start options for nonlinear Solvers, make it a powerful new platform for such problems. Our aim is to make many of the world's best optimizers available to Excel spreadsheet users through the Premium Solver Platform in the coming year.


References

  1. Albright, S. Christian, "VBA for Modelers," Duxbury Press, 2001.
  2. 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."





  • Table of Contents

  • OR/MS Today Home Page


    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.