This article and a linked one provide a guide to Mathematical Programming software and suggest which products you should consider further for your own requirements. The Phases of a Project We may divide the process of tackling a problem using Mathematical Programming into three phases:
Some projects will consist of only the first phase, for instance where an MP model is being used to provide advice to decision-makers. Others will go through all three phases; or perhaps the first two phases will have been done long ago and you are brought in to bring a model up to date. Although the same software can be used for all phases, the requirements differ and software which is ideal for one purpose may be unsuitable for another. As well as reflecting the phase of activity, the selection of software must also take account of the type of problem, its size and the particular algorithms required (linear programming, mixed integer, etc). Stages of Running an MP Model Whichever phase you are in, there are the same three stages to running an MP model:
Although there is a trend towards integration of these stages, it remains a useful categorisation. Most MP software tackles either matrix generation and report writing; or optimization. Optimization packages are generally referred to as "LP codes", even though they often go far beyond straight Linear Programming (LP). The greatest differences between packages lie in the matrix generation and report writing software. By contrast, optimization packages are fundamentally all alike. The differences between them lie in the matrix formats supported, their performance and the extensions which they offer to the basic linear programming (LP) capability. They will be discussed further in the companion article. Categories of Modelling Software Matrix generation and report writing software falls into three broad categories:
Spreadsheet Add-ins Spreadsheets have become as ubiquitous as PCs. Given the way in which they are used to calculate derived quantities from the values in other cells, it was inevitable that they should be extended so that the values in cells could float so as to enable the value in the target cell to be maximised. In this way the spreadsheet itself has become another format for expressing an MP matrix. Leading spreadsheets such as Excel and Lotus 1-2-3 incorporate optimization add-ins which find the optimum solution to problems, albeit with relatively few decision variables (typically fewer than 100; more with the priced versions of the add-ins). If one can do MP in a spreadsheet, isn't that the ideal solution? Well, not really. Spreadsheets are notorious for their habit of hiding errors in formulae. As they become larger they become less manageable. For all but the smallest problems, the "total cost of ownership" of tackling an MP problem is reduced by using a special-purpose MP package to extract the data from a spreadsheet, set up the matrix, optimise it and return the results to the spreadsheet for use there. The savings come in more efficient use of the practitioner's time in setting up and maintaining the model. From the user's point of view, he is still just using a spreadsheet and pressing a macro button to find the best solution. In fact, because dedicated MP software is used, the results are usually obtained faster than with the native optimization add-in. Conventional Programming Languages Few people now use conventional programming languages to write matrix generator programs. They are less efficient in practitioner's time than using dedicated MP software and so are unattractive during the consultancy and development phase of an MP project. They have the advantages of total flexibility, raw speed and a lack of royalties to be paid. This means that they may be used in some implementations, particularly for the most complex applications and where an application package is being produced which is to be distributed widely. They may also be met in maintenance, where a fine judgement is required as to whether to modify the existing programs or start again using dedicated MP software. Matrix Generator Languages Matrix generator languages were developed in the 1960s as an alternative to Fortran for writing matrix generator programs. They are marginally better for this but force the user into thinking of his problem in terms of blocks of columns and their entries in rows. They have become very well established in refinery modelling but are unlikely to appeal to new users when compared with more modern algebraic MP languages. The main packages are OMNI from Haverly Systems and GAMMA from Bonner and Moore. Algebraic MP Languages Algebraic MP languages mimic the way in which one naturally writes an MP formulation as algebraic relationships between decision variables. As such they are the tool of the OR practitioner and are ideal during the consultancy and development phase of an MP project. They differ in the details of their language, their interfaces to data sources and their facilities. The leading packages are, in alphabetical order:
Selecting Your MP Software How then should you set about selecting which MP software to use? First consider your own level of experience and familiarity with other programming languages. The easiest of the packages for relative novices is MPL for Windows and this will appeal particularly to those who are reaching the limits of what is practicable in a spreadsheet. Those who are hardened C programmers will like AMPL while Fortran programmers will continue to be able to exercise those skills with MGG. GAMS and XPRESS occupy the middle ground. Note that the progression from easiest-to-use MPL for Windows through GAMS and XPRESS to AMPL and MGG is to a considerable extent reversed in their suitability for large and complex implementations. Secondly, consider the sources of the data which you will be using in your modelling. Unless your problems are so specific that they require the special facilities offered by one package, you should restrict your attention to packages which have a good interface to the data source, whether it be spreadsheet, database or whatever. Interfaces to data sources are generally two-way so choosing a package which enables you to access your data readily will also enable you to return your results. This will enable you to build your optimization application using the same tools for the user interface as for your other applications. This makes the whole process more efficient and will hep to secure user acceptance. Finally, try out one or two packages and weigh up commercial considerations: the cost of buying the software; the cost and quality of support offered; the time which it will take to use it effectively. One additional factor is whether you are content to use the optimization software implied by the selection of MGG or XPRESS. These packages are effectively tied to their related LP codes (Sciconic and XPRESS-OPT). By contrast, the vendors of AMPL, GAMS and MPL for Windows do not sell optimization codes and so interface their software to a variety of optimization packages. This maximises the chance that you will be able to find an optimization package which can tackle your problem effectively and helps to keep the vendors of optimization packages on their toes. Related articles include How to Choose an LP Code and How to Build a Mathematical Programming Model. To find other articles, refer to the MP in Action page. An up-to-date list of optimization software is published every other year in OR/MS Today, the magazine of INFORMS. |
MP in Action > Software >