Linear Programming Solver Software for Personal Computers: 1995 Report

PC hardware and software advances result in proliferation of LP/IP/NLP products

By Ramesh Sharda

Since linear programming software first became available for a microcomputer around 1980, a good deal of progress has been made in all three phases of decision support using models: formulation, solution and analysis. Formulation refers to construction of the model structure and the use of actual data elements to develop the matrix representation used by a solver. Typically, this matrix representation follows the MPS format. The solution step consists of solving the LP model saved in MPS or some similar matrix format and preparing the solver output. This is the step that has received the most amount of research and development effort. The analysis step entails understanding and analyzing the results obtained from one or more solutions of the LP model.

This survey focuses on the solution step. Algorithmic and computer implementation advances as well as hardware and software advances in desktop computers have resulted in a proliferation of LP/IP/NLP software. Many of these programs are offered by small companies; some are offered by the giants of the computer industry.

Procedure For the Survey
The table on the following pages includes basic information compiled through a survey on various LP programs. An initial call for participation in this survey appeared in an earlier issue of OR/MS Today. Several software vendors responded to this survey. A one-page survey form eliciting the software and company information was mailed to all of the vendors who participated in the earlier survey in addition to any new respondents. Vendors participating in the survey reported in Sharda [1993] were also contacted.

The table contains information received from the vendors, including comments that have been edited for length. In some cases the vendors supplied pricing and size information for the many versions offered by their firm. In the interest of brevity this information has not been reproduced fully. However, the table does indicate the range of prices and software capabilities.

This survey includes two types of solvers: stand-alone solvers and solvers integrated with modeling languages. Even though some of the packages in this survey can also qualify as modeling languages and were included as such in an earlier survey of modeling languages [OR/MS Today, June 1995], the packages are published here because they include an LP solver. In general, it is possible to select the model description language that fits one's needs, and solve the generated LP problem using a solver covered in this survey. Modeling languages bundling a solver can also send the generated LP matrix to another solver of your choice. This allows a customer to take the software with the best features of each LP model management system component and custom-build a system.

Of course, other modeling languages can also be bundled with one of the solvers to create another marketable package. The only modeling language/solver combos that we have considered as solvers are those where both components are also not being marketed separately. LINGO, SAS/OR, VMP/PC and XPRESS-MP appear to fit this definition. This classification is not to imply that stand-alone solvers are not good buys. As mentioned before, one can mix and match virtually any solver with virtually any modeling aid. We are only noting that some solvers are inseparable from the modeling aid functionality.

Some of the programs listed in the table are multiple offerings of the same solver. For example, LINDO, LINGO and What's Best! internally use the same solver. These are listed separately because the interface and functionality of those products is quite distinct from one another. Similarly, OMP and PC-PROG appear to use the same solver engine. Most vendors offer many different versions of their products. The distinction is usually based on the size of the problem the software is configured to solve.

A second common distinction is based on the platform or operating system for which a specific version is developed. For example, a version of XPRESS-MP is sold as XPRESS for Windows, and also as ROI XPRESS Development System. Another reason for distinct product offerings is the different bundling of products, especially a modeling language and a solver. Examples include CPLEX Modeler (CPLEX/XPRESS-MP), MAGIC/LAMPS, SCICONIC/MGG and MPSIII (CWHIZ/WHIZARD/DATAFORM versions). A fourth variation for products is based on the bundling of subroutines. For example, XA markets AXA Callable Library. Finally, other user support software may be bundled in some variation. For example, IBM's OSL/6000 is available as OSL/6000 GUI (Graphical User Interface).

The point is that the LP solver software from each vendor is available in many different capacity versions for several platforms, bundled with different modeling/support software, and at various price levels. Including a list of all these combinations is likely to be of little use. Thus we list the products in only major offerings. The vendor-supplied information in the table sometimes expands on these additional offerings.

Progress of the LP Solver Software
A scan of the table indicates that LP software is keeping pace with technical advances in hardware, software and communications. For example, the table includes E-mail addresses for a majority of vendors. This allows the customer, especially an overseas customer, to contact the vendors more easily. Some vendors have set up home pages on the World Wide Web to stay in touch with their customers.

Many programs are evolving to improve their communication capabilities with the rest of the programming environment. The ability to work with a spreadsheet program has been described in earlier surveys. At the highest level of integration, the solver is built into a spreadsheet program. Microsoft Excel and Borland's Quattro-Pro include a solver with the spreadsheet program. Since this solver is limited in capacity, the extended solvers available from Frontline Systems replace the free solver and can be automatically accessed in the spreadsheets.

The next level of spreadsheet linkage is through an add-in program that functions much like the built-in solver, but usually has its own command/menu structure. These are also accessed while using the spreadsheet program, offering a complete spreadsheet optimization environment.

The next spreadsheet interface comprises only the ability to read and write a spreadsheet file. These programs can read a specific spreadsheet for problem input and write the results back into the spreadsheet file so that the familiar spreadsheet program can be used for further report processing.

Finally, some programs can read a spreadsheet file only through a text file. One has to export a problem specification to a text file and read it into the solver. The solver can create a text file that can be imported into a spreadsheet program.

Clearly, the levels of spreadsheet integration are hierarchical. First, the higher level integration offers a better direct linkage. Second, a program offering a higher level link can easily offer the lower level linkage.

LP software is also offering more and better linkages with external databases. Some programs offer fairly open links to databases. Others feature SQL query capability for model generation and storage of results. Still others allow report generation through DBMS. We believe that more progress will be made in expanding these links and making them even easier.

Many LP programs are now available in form of a Windows DLL callable library for full integration into another program (e.g., AXA, CPLEX, LP/MIP Solver DLL, XPRESS-MP). This capability is useful for developing turnkey applications that employ LP as the underlying modeling tool.

Most LP programs do not specify size limits any more. The programs are able to solve large problems by using available memory. Of course, very large problems still require sophisticated tuning of the algorithms using empirical experimentation and expensive hardware. But a large majority of problems can be solved in an acceptable time frame using the default settings of the LP programs with the usually available desktop PC hardware.

Most LP solver packages now offer integer programming capability including SOS1/SOS2. Some programs are also able to detect embedded network structure and employ specialized algorithms to achieve fast solution times.

The quest to solve LP problems faster continues. Some programs also offer parallel implementation (CPLEX, Fort MP, OSL) to achieve more speed by employing multiple CPUs. Other programs include Interior Point Methods (CPLEX, Fort MP, LOQO, OSL). Of course, this quest to solve ever larger problems has to continue. Advances in solution technologies to solve really large problems eventually translate into practical improvements for most smaller problems as well. Also, the financial impact of being able to solve even one really large problem can be significant. The savings accrue not in terms of the reduced CPU time cost, but through implementing better solutions and scenarios. This is especially true of problems including integer variables.

The LP software technology empowers a user to solve a large problem, but it also needs to offer more help in formulating a problem and analyzing the results produced by a solution algorithm. In commenting on an earlier LP survey prepared by me, Tomas Gal [1992] laments the lack of analysis software in LP software. He argues that the standard shadow prices and objective and RHS range analyses provided by many packages are not enough. He also argues that most programs do not provide enough support for multiple objective optimization and report generation.

I believe that his first concern about analytical support tools is justified. Much more needs to be done to make sure that the results of an LP model run are understood and used correctly. Programs such as ANALYZE (Greenberg 1983, 1992) and MINOS-IIS (included in this survey) are making important first steps in this direction, but these tools are not yet developed enough to be handed over to a novice LP user. I believe that Professor Gal's concerns about report generators and multi-objective optimizations are likely to be answered sooner. Many programs included in this survey do a fairly good job of producing reports or interfacing with other programs for report generation. The spreadsheet oriented programs are clearly the best equipped in this regard. Many programs offer links with database software enabling an even better linkage.

With regard to multiple objectives, my view is that the problem formulation support will probably need to evolve first before the solution capability is needed. Of course, the algorithmic capability already exists for multicriteria optimization, but it has not been incorporated in most of the software included here because the demand for such functionality is not there. As the skill level of LP users grow, multi-objective optimization will become a standard subset of the LP software.

Optimization software is progressing at a rapid speed. Growing availability of linear and nonlinear programming techniques in spreadsheets is an encouraging indicator of the acceptance of MS/OR approaches. Other developments in modeling languages, user interfaces and parallel processing suggest that all three phases of LP modeling are being facilitated through LP software summarized in this article.

As has been stated in my earlier articles, surveys of this type are inherently risky undertakings because some vendors may have been left out or the information may be incorrect or incomplete. All attempts were made to ensure its accuracy. Notwithstanding these concerns, we hope that the survey will serve as a good indicator of the state of the art of LP software in 1995.

1. Gal, T., "Putting the LP Survey Into Perspective," OR/MS Today, Vol. 19, No. 6, p. 93, 1992.
2. Llewellyn, J., and R. Sharda, "Linear Programming Software: 1990 Survey," OR/MS Today, Vol. 17, No. 5, pp. 35-47, 1990.
3. Sharda, R., "Linear and Discrete Optimization and Modeling Software: A Resource Handbook," Lionheart Publishing Inc., 1993.
4. Sharda, R., "Linear Programming Software for Personal Computers: 1992 Survey," OR/MS Today, Vol. 19, No. 3, pp. 50-51, 1992
5. Sharda, R. and G. Rampal, "Algebraic Modeling Languages on PCs," OR/MS Today, Vol. 22, No. 3, pp. 58-63, 1995.

Ramesh Sharda is the Conoco/DuPont Professor of Management of Technology at Oklahoma State University. He is also serving as the interim director of the MS in Telecommunications Management Program this year.
OR/MS Today copyright © 1995 by the Institute for Operations Research and the Management Sciences. All rights reserved.

Click here to return to the table of contents.