Most optimization software belongs to the family of Linear Programming and its extensions. Linear Programming is remarkable above all for the fact that it works: that it is possible routinely to find the optimum solution to systems of thousands of linear constraints relating many thousands of decision variables to one another; and that this can be done in a matter of minutes on a PC costing a couple of thousand dollars. Inaccuracies in Computers What makes this more remarkable is that the solutions are found despite the inaccuracies of computers. I am not referring here to the Pentium's inability correctly to divide 5505001 by 294911 (try it: the answer should be 18.666651973). If you have ever tried solving tiny LPs by hand using the Simplex method, you will know that while you may start with coefficients which are small whole numbers, they rapidly become apparently random strings of digits as the calculations proceed. Problems arise because the calculations involve subtracting one coefficient from another and then dividing by the result. Minuscule inaccuracies are present in every number (except those which are of the form m.2^{n} for integer m,n) because only a finite number of (binary) decimal places is used. For instance, if one calculates 1.0 / (5505001/294911 - 9333/500), the result is given as 1533.805922801, but of this only 1533.80 is significant; the less significant decimal places are random "noise". (Do this with a Pentium chip and the answer will be 1075268.8!) The vast bulk of Linear Programming packages are able to cope with these inaccuracies, at least for problems of up to a few hundred rows and columns. It is in solving larger problems that differences in the quality of their algorithms begin to tell. It is then that one package may find the optimal solution while another goes on for ever or, worse still, declares optimal a non-optimal solution. Extensions to LP When you venture beyond Linear Programming, matters become more problematical. On top of the practical difficulties of handling rounding errors, there are theoretical difficulties of obtaining optimum solutions. For integer programming (where some of the decision variables must take integer values) it is theoretically possible to find the optimum solution, but often this is of no practical value because the calculations would take longer than the age of the universe. For non-linear programming (where constraints and the objective can be non-linear) not even this is true and the most that can be aimed for is a "local" optimum together with some statements about there being no better solution within some region provided certain properties hold for the non-linear functions. As a result, the differences in performance among optimization packages are much larger for the extensions to Linear Programming. One package may solve a problem readily while another flounders. There is greater variability in design too, and in the way in which the analyst can interact with the package to guide it towards the optimum solution. Interface to LP Optimizers Just as the PC market has flourished because there was a standard and despite its limitations (e.g. the 640KB limit), so the market for LP software has flourished because there has been a standard for the specification of LP matrices. This is the MPS format which was introduced by IBM in the 1960s. Despite its archaic structure (it harks back to computers of the 1950s, when tape drives were used as extra memory devices), MPS format has remained the industry standard for 30 years. Almost all LP packages are able to read MPS format matrices and optimize them. Likewise, most matrix generation software can produce MPS format matrices so there really is plug compatibility between matrix generators and LP optimizers. Many LP codes can also read their own "improved" formats, but there is little compatibility across vendors. Unfortunately, there is no comparable format for the solution file and so you need to ensure that your report writing software can read the optimum solution produced by the optimizer (or be prepared to rewrite the solution-reading routines or reformat the solution file). Interface to LP Extensions From the point of view of specifying a problem, integer programming is the most straightforward extension to LP: some of the decision variables are declared to be integers. Unfortunately, it's not quite so simple in communicating that to an optimizer. IBM's original MPS package only solved LPs and the integer programming extensions followed later, as a separate add-on product. Further, the format which IBM chose was clumsy and alternatives are widely used. Even greater variety exists for more advanced integer programming structures such as Special Ordered Sets. What this means is that if you are interested in doing integer programming, you really do need to check the compatibility of the matrix generation software with the optimizer. Declarations by each vendor that his software supports MPS format are insufficient. With non-linear programming there is even less consensus as to how to specify instances of problems. This is really an area where integration is needed between the matrix generation software and the optimizer so that, for instance, the optimizer can obtain the partial derivatives of the functions without having to estimate them itself. As a result, one tends to evaluate an optimizer in combination with a matrix generator, for instance GAMS/MINOS. LP Codes and Subroutine Libraries Most optimizers take the form of free-standing programs which are controlled by their own command language. They can either be run interactively or from a command file. They read the matrix from one file and write the solution to another. Although such a structure may seem old-fashioned, it is well-suited to a process which is CPU-intensive and where the occasional hiccup may occur. File interfaces have the great merit of being able to be inspected and of making it possible to isolate a problem and pass it to the software vendor to resolve. Some free-standing optimizers are also available as subroutine libraries. These enable the overheads to be reduced when embedding optimization routines within applications. Subroutine libraries also facilitate advanced optimization techniques where there is interaction between the matrix generation and optimization routines. IBM's OSL is unusual among the leading LP codes in being available only as a subroutine library. For use under Microsoft Windows, some LP codes are available as Dynamic Link Libraries (DLLs). Choosing The Software If your problems are up to a few hundred rows and columns and purely linear, you are unlikely to find an LP code that won't solve them adequately. In this case, you should not be too concerned about selecting the LP code itself. Instead you should be concentrating on selecting modelling software with which you are comfortable (see November's article). You may as well choose whatever is the cheapest LP code recommended by the vendor of the modelling software. As with PCs, buy what is adequate for your needs now and reckon to buy something better (or upgrade) when you need to. You will be much better placed to make a good long-term decision from the vantage-point of experience. If your problems have thousands of rows and columns or you are interested in integer or non-linear programming, no doubt you will already have had some experience of LP modelling. This is when you need to make a good choice of optimizer. Even then, however, your requirements are unlikely to be so specific that you need to choose the optimizer first and then find which modelling software is compatible with it. More normally, you will draw up a shortlist of LP codes which are compatible with your modelling software. At this point you should carry out some benchmark tests. Although most software suppliers offer their packages on free trial or for a nominal fee, there are significant costs in undertaking benchmarks. You will need to learn how to use each of the software packages and select appropriate options. It is tempting simply to use the default options, but this can do an injustice, particularly to the more advanced packages. The vendor will offer help in undertaking benchmarks, but remember that if you send him your matrix, you have no idea how much effort he puts into identifying the options which he then recommends and whether you would be able to use the package effectively yourself. Support and Upgrades In choosing a package you will also need to consider the support offered. If you are relatively new to LP, this is likely to be general assistance in using the package. If you are solving particularly large matrices or doing sophisticated things, it is quite possible that you will excite a "bug" in the code. This won't necessarily be a true "bug", i.e. a coding mistake, but may reflect inadequacies in the algorithm. How can you judge the quality of support offered? You can reckon that the support which you get as a customer will never exceed that which you get as a prospect. If you're not satisfied with the trial period, don't license the software. Don't make assumptions about support based on image or name: instead ask to see the record of releases and maintenance upgrades issued for your hardware platform. These will show how much effort is being put into keeping the product competitive. A Shortlist Finally, putting my head on the block, I offer a personal shortlist. I consider that there are three LP codes which lead the way in speed, robustness and extensions to the basic LP techniques. These are (in alphabetical order):
CPLEX and OSL have well-established interior-point algorithms for problems with tens of thousands of rows while XPRESS's is new to Revision 8. As noted before, OSL is unique in being available only as a subroutine library. XPRESS has the advantage to UK-based users of being developed and supported in the UK. Other products worth considering include:
Inevitably this list is personal and exclusion from it should not be taken as a slur. Other products are no doubt of comparable quality and will provide excellent service. Related articles include A Comparative Survey of Mathematical Programming Software and But my Problem Isn't Linear. To find other articles, refer to the MP in Action page. An up-to-date list of optimization software is available in OR/MS Today, the magazine of INFORMS. |
MP in Action > Software >