M177 Project - Simplex Method Versus Interior Point Method

M177 Project - Simplex Method versus Interior Point Method and NEOS

Can be done in teams of two students Due May 2

Purpose:

To learn about the relative merits of the simplex method (SM) and interior point methods (IPM) for solving continuous linear programs by reading articles / books and by carrying out experiments.
To gain experience using NEOS or other web-based sites for solving optimization problems.
To gain experience with existing databases of linear programming (LP) and optimization test problems.
To learn about benchmarking.

Turn-in:

A five to ten page report. Your report should be well written with an introduction (perhaps briefly discussing the importance of a LP), a background section (briefly discuss some key ideas of SM and IPM), a body (discussing your investigations and experiments) and a conclusion.

The focus of this project is to determine for continuous linear programming whether IP methods are faster than simplex methods or whether simplex methods are faster or whether it depends on the problem. In general I want you to come to a conclusion about which method you would suggest if initially you knew little about the problem (except that it is a continuous linear programming problem). Also I want you to make a suggestion about which approach might be best if you could try out your problem using both approaches. I don't necessarily want you to recommend a particular routine or computer package. Rather focus on the question of whether IPM is better or SM better. This will, however, entail running specific packages that do each

The references mentioned below and other references are a source of information for your report. Make sure you use your own words in your report (except for occasional items placed in quotes) and provide citations.

In addition to using the references I want you to carry our some experiments on your own using the NEOS servers or other sites (see Q8 from reference 4) that will accept and solve optimizations problems. Note that the demo version of GAMS that you downloaded earlier in the semester will not be adequate for these experiments since the demo version can only solve problems of a limited size.

You will need to select problems to run. I would like you to run half a dozen or so different test problems. A summary of some sources of test problems is in Q4 of reference 4 above. References 1, 2 and 5 also list test problems. You can find test problem files to download at or at Reference 3, above (which then points to the sites ). I would suggest that for most of your tests you download one of the examples mentioned in reference 2. Examples used in this talk are all continuous (rather than integer) problems and in addition the results listed in the talk will provide some rough ideas about how much time the problem may take to run. Perhaps you could try to run an example or two that are not from that reference.

In choosing samples for benchmarking the size of the problem and the time it takes are important. Problems that are too small will not be suitable since short run times (a few seconds or less) cannot be reliably measured. The examples that appear in textbooks are typically too small for timing purposes. On the other hand you should not choose problems that are too large and will overtax the NEOS computers. For example do not choose problems that will take many hundreds of seconds. Test problems such as dano3mip, dfl001, gen4, ken-18, l30, lp22, nsct2, sgpf5y6, and storm125 from reference 2 should be fine. You might also choose one or two problems that will run somewhat longer. A choice like nug20 is NOT appropriate (see the times listed in Refence 2). Remember that you are using someone else's computer when you run programs on NEOS and it is important not to abuse their offer of free computer time.

Several issues will arise when you download example files for optimization problems. I will describe these in an appendix. For now let us assume that you have downloaded a file that you want to run in MPS format, a common input format. Suppose for example we have dowloaded dfl001.mps (third letter “el” not one). A description of how to get dfl001.mps is in the appendix.

To run an example in mps format using NEOS go click on "NEOS Solvers" and then click on "Linear Programming". Next click on "MPS" for one of the six solvers (BPMPD, Clp, Mosek, PCx, Xpress-MP/Barrier or Xpress-MP/Simplex) that accepts MPS format. For example you might choose Xpress-MP/Simplex. There are several ways to submit a problem to NEOS but I find the WWW Form to be the easiest way. To use this now click on "WWW Form". After doing this click on "Browse" and browse your hard drive to locate the file dfl001.mps or other mps file and choose the file. Many of the test problems are large and you probably want to also click the box "Suppress the solutions" if it is available. If you would like the results emailed to you type in your email address. This is optional. Next click on "Submit". Information about the waiting queue and the current jobs executing will appear. Your job may take seconds if the NEOS servers are not busy or potentially a number of minutes or perhaps overnight, depending on the current load.

When the problem is finished you will get output on the web screen similar to:

*************************************************************

NEOS Server Version 4.0

Job# : 520834

Solver : Xpress-MP/SIMPLEX

Start : 03/21/2005 17:19:38

End : 03/21/2005 17:21:07

Host : pergamon.iems.northwestern.edu

. . .

Reading Problem DFL001

Problem Statistics

6072 ( 0 spare) rows

12230 ( 0 spare) structural columns

41873 ( 0 spare) non-zero elements

Global Statistics

0 entities 0 sets 0 set members

>Presolved problem has: 3867 rows 9063 cols 31550 non-zeros *************************************************************

Its Obj Value S Ninf Nneg Sum Inf Time

0 17748.60000 D 1332 0 6190.000664 0

…

15573 11266396.05 P 0 0 .000000 84

Uncrunching matrix

15573 11266396.05 P 0 0 .000000 84

Optimal solution found

Finished calling XPRESS-SIMPLEX solver: no errors.

The exact output that you will get depends on the solver chosen. The information that we want to know from this output is the time required. One way to get this is by subtracting the reported end time from the start time. For this problem we get

17:21:07-17:19:38 (hours:min:sec) = 1:29 (min:sec) = 89 seconds

This technique should work for any solver that you choose. In addition some solvers will have a separate report the time required. In the above run the time reported by Xpress-MP/SIMPLEX was 84 seconds which is in reasonably close agreement with the 89 seconds calculated above. The goal of your experiments is to get times for a number of different examples and two or more solvers. Note that a separate submission of dfl001.mps to Xpress-MP/Barrier required

17:26:11-17:23:30 (hours:min:sec) = 2:41 (min:sec) = 161 seconds

For this example the Xpress-MP simplex based code was somewhat faster than the Xpress-MP interior point method code.

I should note that sometimes after you submit a problem the queues are backed up and you may not want to wait on line for the run to finish. If you write down the job number and password you can later go to the web site and use the job number and password to retrieve the completed results. I am not sure how long they keep the results.

In choosing your solvers you want to choose one that is an interior point method and another that is a simplex method. Solvers that labeled “barrier” are interior point methods. One natural choice is to choose to compare Xpress-MP/Barrier and Xpress-MP/Simplex. However I hope that some of you try other methods. You will have to look for documentation about a method to determine if it is an IPM or SM. Some of the solvers include alternatives that are either IP methods or simplex methods and for these you will need to try to determine what the default selection is again by looking at documentation.

In addition to the run times you should note if anything strange happen, for example if an optimal solution is not found or errors are reported In comparing two approaches one wants to look at the reliability of the approaches as well as the speed. Try to summarize your data in a table that clearly illustrates the relative times of your various examples for several solvers and that notes any problems that may have arose.

There are some cautions that you must keep in mind when doing benchmark tests like this one.

One concern is that you may be sharing the computer assigned with other jobs or users. This will potentially affect the run times. Ideally one would choose to use a computer where you were the sole user. However for NEOS use one does not have that option. One way to partly overcome this problem would be to try your runs at a time when there are few users ( 2 am ?) or to try repeated runs at different times and take an average. I don’t suggest extensive use of the later approach since we don’t want to overuse the NEOS servers. However you could try to repeat a few runs to see the variation.
Another possibility on NEOS is that the same example might be assigned different computers when comparing your IPM method and SM for that example. It may not be fair to compare run times for different computers. One way to reduce this possibility is to submit the problem for the SM and IPM at nearly the same time, perhaps by using two different browser windows. The hope would be that NEOS would assign them to the same computer. You can tell the computer used by checking the host name in the NEOS final output. For the dfl001 example above the host was “Host : pergamon.iems.northwestern.edu” for both the simplex method and the barrier method. Therefore it is fair to compare these times.
Another concern is that the time required by a particular method depends very much on the programming details of the code used. One implementation of the simplex method (or IPM method) could be much faster than another implementation depending on the coding details. One way to partially overcome this problem would be to try lots of different solvers for each approach and choose the average time or perhaps the best times. This is not practical for this project. However I do hope that some of you report on more than one solver for the simplex method or more than one solver for IP methods.
A fourth concern relates to the options and parameter that can be chosen for any solver. By tweaking these parameters one could potentially speed up the code for a particular problem. For this project may rely on the default parameters.

You may not be able to overcome all these difficulties in this project. Do the best you can without overusing the NEOS servers. Comment on any limitations that appear in your times and interpret your results “with a grain of salt.” Base your final conclusions on the existing published results as well as your runs.

Web Sites and References:

H. D. Mittelmann, "Benchmarking Interior Point LP/QP Solvers", Opt. Meth. Software 12, 655-670 (1999)ftp://plato.asu.edu/pub/papers/paper85.pdf
H. D. Mittelmann,"An Independent Evaluation of Continuous LP Codes" INFORMS Annual Meeting. Denver, CO 26 October 2004,
H. D. Mittelmann, Benchmarks for Optimization Software,
Optimization Technology Center, "Linear Programming Frequently Asked Questions"
Readme file from the Netlib collection of optimization problems
The optimization software guide and other information at NEOS
The performance links page at GAMSWORLD.
Look for other references using google, ( google scholar ( MathSciNet ( ), the SJSU Library (??), etc. To use MathSciNet from off campus you may need the username "spartans" and password "analyze"

Note: I hope that you can find and use at least one relevant reference from 7 or 8.

Appendix: Downloading test example files (a long story):

There are many different input formats used to describe optimization models Some of the most common input formats are AMPL, GAMS and MPS. There is a brief overview of MPS format in Q5 of reference 4. The choice of the input format limits the NEOS solvers that can be used (see ). MPS is the format that is usually used in the sites containing data sets mentioned above and therefore, I expect, that you will usually want to use MPS input format. However apparently the site ftp://plato.la.asu.edu/pub/ampl_files/ has many of these same examples in AMPL format and the GAMS web site has many of the same examples in GAMS input format. Finally I should note that there are facilities to translate between different formats. See or search internet for mps2gms or mps2gams. Due to these translation services and the existing translations of standard examples the various optimization input formats are not quite a tower of babel.
Many of the files that you download will be in compressed format. Typically you will need to download the file to your hard drive by right clicking on the file name and uncompressing it after it is downloaded. As an example, from the site one can right click on adlittle.gz (which is a relatively small LP problem) and save it to your hard drive. Often the files are compressed simultaneously by two different techniques (gzip and emps or bzip2 and emps). Here is a description of how to uncompress the file once it is downloaded.
gzip format ( .gz extension) -- This is a standard form of compression. There are a number of ways to uncompress a gzipped file:
Depending on your browser settings a gzipped file may be automatically uncompressed by your browser (you can tell if the file is readable or at least partly readable when you try to view it).
If not you can download the file (often by right clicking on the file and saving the file to your hard drive). Standard utilities for uncompressing files can then be used to uncompress the file. Two common such utilities are PowerDesk and Winzip. If you do not have these or similar utilities you can use google to search for them. I believe PowerDesk can be downloaded for free and that Winzip can also be downloaded for free but asks for money after a while. With either of these utilities you need to open the file in the utility and then choose the extract button (which is behind the archive button in PowerDesk) to uncompress the file.
If you don’t want to use Powerdesk or Winzip there is a standalone command line style program called gzip.exe at . At this site you can download the file gzip124xN.exe by right clicking on "self-extract" in the "Windows 9x/NT/2000/ME/XP in zip or self-extract format" option . Next install the gzip.exe program by using Windows explorer to move to the folder containing the file gzip124xN.exe and then double clicking on the gzip124xN.exe file. After this installation the program called gzip.exe can be used to uncompress a gzipped file using command line (DOS window) style commands. The gzip.exe program and the file to be unzipped should be in the same folder. Open a DOS window by clicking Start and run. Type cmd and click ok. Use the command line cd command to move to the proper folder ("cd .." to move up a folder, "cd folder_name" to move down a folder and "drive:" to change disk drives where "drive:" is typically "c:" or "d:"). Now type "gzip –dc file_name.gz > file_name" to uncompress the file. For example "gzip –dc adlittle.gz > adlittle" will uncompress adlittle.gz and names the uncompressed file adlittle (with no extension).
bzip2 format (bz2 extension) -- This is a less common form of compression and standard utilities such as PowerDesk or Winzip may not work. I put a copy of bunzip2.exe, a utility that I found on the web that unzips bzip2 files, on my web site at . This is a command line (DOS style) program. The bunzip2.exe program and the file to be unzipped should be in the same folder. Open a DOS window by clicking Start and Run. Type cmd and click ok. Use the command line cd command to move to the proper folder ("cd .." to move up a folder, "cd folder_name" to move down a folder and "drive:" to change disk drives where "drive:" is typically "c:" or "d:"). Now type "bunzip2 < file_name.bz2 > file_name" to uncompress the file. For example "bunzip2 < neos1.bz2 > neos1" will uncompress neos1.bz2 and names the uncompressed file neos1 (with no extension). Note that you can get neos1.bz2 from the site ftp://plato.asu.edu/pub/lptestset/misc/ .
emps format -- This is a compressed format that is specific to optimization problems stored in mps format. Standard decompression utilities such as Winzip and PowerDesk will not work. I put a copy of emps.exe, a utility that I found on the web that uncompresses emps files, on my web site at . This is a command line (DOS style) program. The emps.exe program and the file to be uncompressed should be in the same folder. Open a DOS window by clicking Start and Run. Type cmd and click ok. Use the command line cd command to move to the proper folder ("cd .." to move up a folder, "cd folder_name" to move down a folder and "drive:" to change disk drives where "drive:" is typically "c:" or "d:"). Now type "emps < file_name > file_name.mps" to uncompress the file. For example "bunzip2 < neos1 > neos1.mps" will uncompress neos1 and names the uncompressed file neos1.mps Note that you can get neos1 by first copying neos1.bz2 from the site ftp://plato.asu.edu/pub/lptestset/misc/ and following the instructions for uncompressing bz2 files.
Note that for most or all of the mps files at the web sites mentioned above one needs to decompress the file with both gzip and emps or with both bunzip2 and emps. The reason for this is clear when we compare the file sizes (adlittle.gz and neos1.bz2 are discussed above and the file dfl001.gz is at ):

Double compressed / Emps compression only / No compression / Recompressed
with zip (only) / Recompressed
with gzip
(only)
File: / adlittle.gz / adlittle / adlittle.mps / adlittle.zip / adlittle.mps.gz
Size: / 2.0 kb / 3.7 kb / 16.8 kb / 2.7 kb / 2.7 kb
File: / dfl001.gz / dfl001 / dfl001.mps / dfl001.zip / dfl001.mps.gz
Size: / 177 kb / 345 kb / 1,432 kb / 244 kb / 241 kb
File: / neos1.bz2 / neos1 / neos1.mps / neos1.zip / neos1.mps.gz
Size: / 1,083 kb / 3,535 kb / 16,096 kb / 1,930 kb / 2,094 kb

The compressed files are much smaller.