ࡱ> % Zbjbj%% "GGVl0$ 06C|2_~dABBBBBBB$D FB="_B(qB((( 8B(B((,>@ n>$R90!4?@ C06C?GI$ZG@(00M177 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  HYPERLINK "http://www.netlib.org/lp/" http://www.netlib.org/lp/,  HYPERLINK "http://www.netlib.org/lp/data/" http://www.netlib.org/lp/data/ or at Reference 3, above (which then points to the sites  HYPERLINK "http://miplib.zib.de/" http://miplib.zib.de/  HYPERLINK "ftp://plato.asu.edu/pub/lptestset/" ftp://plato.asu.edu/pub/lptestset/,  HYPERLINK "http://www.sztaki.hu/~meszaros/public_ftp/lptestset/" http://www.sztaki.hu/~meszaros/public_ftp/lptestset/ ). 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  HYPERLINK "http://www-neos.mcs.anl.gov/neos/" http://www-neos.mcs.anl.gov/neos/ 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  HYPERLINK "http://www-neos.mcs.anl.gov/neos/neos-cgi/check-status.cgi" http://www-neos.mcs.anl.gov/neos/neos-cgi/check-status.cgi 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 dont suggest extensive use of the later approach since we dont 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)  HYPERLINK "ftp://plato.asu.edu/pub/papers/paper85.pdf" 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,  HYPERLINK "http://plato.asu.edu/talks/lp.pdf" http://plato.asu.edu/talks/lp.pdf H. D. Mittelmann, Benchmarks for Optimization Software,  HYPERLINK "http://plato.asu.edu/bench.html" http://plato.asu.edu/bench.html Optimization Technology Center, "Linear Programming Frequently Asked Questions"  HYPERLINK "http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html" http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html Readme file from the Netlib collection of optimization problems  HYPERLINK "http://www.netlib.org/lp/data/readme" http://www.netlib.org/lp/data/readme The optimization software guide and other information at NEOS  HYPERLINK "http://www-neos.mcs.anl.gov/neos/" http://www-neos.mcs.anl.gov/neos/ The performance links page  HYPERLINK "http://www.gamsworld.org/performance/links.htm" http://www.gamsworld.org/performance/links.htm at GAMSWORLD. Look for other references using google, ( HYPERLINK "http://www.google.com" www.google.com), google scholar ( HYPERLINK "http://scholar.google.com/" http://scholar.google.com/), MathSciNet (  HYPERLINK "http://www.ams.org/mathscinet" www.ams.org/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  HYPERLINK "http://www-neos.mcs.anl.gov/neos/server-solvers-in.html" http://www-neos.mcs.anl.gov/neos/server-solvers-in.html ). 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  HYPERLINK "ftp://plato.la.asu.edu/pub/ampl_files/" ftp://plato.la.asu.edu/pub/ampl_files/ has many of these same examples in AMPL format and the GAMS web site  HYPERLINK "http://www.gamsworld.org/performance/plib/" http://www.gamsworld.org/performance/plib/ has many of the same examples in GAMS input format. Finally I should note that there are facilities to translate between different formats. See  HYPERLINK "http://www.gamsworld.org/translate.htm" http://www.gamsworld.org/translate.htm 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  HYPERLINK "http://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/" http://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/ 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 dont want to use Powerdesk or Winzip there is a standalone command line style program called gzip.exe at  HYPERLINK "http://www.gzip.org/" http://www.gzip.org/ . 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  HYPERLINK "http://www.gzip.org/gzip124xN.zip" zip or  HYPERLINK "http://www.gzip.org/gzip124xN.exe" 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  HYPERLINK "http://www.math.sjsu.edu/~foster/math177.html" http://www.math.sjsu.edu/~foster/math177.html . 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  HYPERLINK "ftp://plato.asu.edu/pub/lptestset/misc/" 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  HYPERLINK "http://www.math.sjsu.edu/~foster/math177.html" http://www.math.sjsu.edu/~foster/math177.html . 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  HYPERLINK "ftp://plato.asu.edu/pub/lptestset/misc/" 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  HYPERLINK "http://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/" http://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/ ): Double compressedEmps compression onlyNo compressionRecompressed with zip (only)Recompressed with gzip (only)File:adlittle.gzadlittleadlittle.mpsadlittle.zipadlittle.mps.gzSize:2.0 kb3.7 kb16.8 kb2.7 kb2.7 kbFile:dfl001.gzdfl001dfl001.mpsdfl001.zipdfl001.mps.gzSize:177 kb345 kb1,432 kb244 kb241 kbFile:neos1.bz2neos1neos1.mpsneos1.zipneos1.mps.gzSize:1,083 kb3,535 kb16,096 kb1,930 kb2,094 kb The compressed files are much smaller. Note that some of these files become large neos1.mps is 16 megabytes!! In order to upload these to NEOS you may need a fast internet connection. For example you might try a connection in one of our on campus labs. I was successful in uploading neos1.mps in several minutes from my office. You can gzip or zip a file and submit the zipped file. NEOS will automatically decompress them for you. (see  HYPERLINK "http://www-neos.mcs.anl.gov/neos/faq.html#bashful" http://www-neos.mcs.anl.gov/neos/faq.html#bashful ). Apparently NEOS will not successfully decompress files that have been emps compressed . If you want to upload a file that has emps compression you will first need to uncompress the file completely, as described above. After this, prior to uploading to NEOS, you may want to recompress the file in zip or gzip format (and not emps) using gzip.exe or a utility like Winzip or PowerDesk.  EF}*3 -./MN_`bcEI/##$$$V$W$222_3`3a33aJjUCJOJQJ^JCJOJQJ^JaJCJjUjU0JjU jUjCJUmHnHu55\CEF|}K )*3NO: ;    34^$h^ha$$ & Fa$$a$$a$ZZ4+,[\pcv BEGI/0) * j k ;"<"}"~"""$$/'0'((9)$a$9)+U.011122222345 66977\99999?A3B & F & F & Fh^h & F333333333@4A4p4q4r444444444455n5o5555 6 6K6L6~66666667777787T7U7777777788 8.8/8B8C8k8j Uj Uj UjUj?UjJU0JaJjMUaJ jUaJaJaJ0J jUj,U>k8l8m888888888899;;J;K;L;;;L<M<<<<<<<<*=+=,=V=W===> >!>G>H>@@M@N@O@@@EEFFF*F+FFFFFFFFFGG#G$GKKKjUjUj UjUjUjU5\j U0J jUj UF3BBEJNSuUvUwUUUUUUUUU $$Ifa$8^8 & F & FKKKLLNNNNNNN!P"P]P^P_PPPSSSSTSUS|S}STT3U4U5UpUqUwUU[VaVVVXX:Y;YW?WfW:44^$$Iflֈh  X"00!64 la $$Ifa$fWgWZZZZZ^ 1h/ =!"#8$%DyK http://www.netlib.org/lp/yK 4http://www.netlib.org/lp/DyK http://www.netlib.org/lp/data/yK >http://www.netlib.org/lp/data/DyK "http://www-neos.mcs.anl.gov/neos/yK Dhttp://www-neos.mcs.anl.gov/neos/aDyK ;http://www-neos.mcs.anl.gov/neos/neos-cgi/check-status.cgiyK vhttp://www-neos.mcs.anl.gov/neos/neos-cgi/check-status.cgi!DyK +ftp://plato.asu.edu/pub/papers/paper85.pdfyK Vftp://plato.asu.edu/pub/papers/paper85.pdfDyK "http://plato.asu.edu/talks/lp.pdfyK Dhttp://plato.asu.edu/talks/lp.pdfDyK  http://plato.asu.edu/bench.htmlyK @http://plato.asu.edu/bench.htmlDyK Fhttp://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.htmlyK http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html DyK %http://www.netlib.org/lp/data/readmeyK Jhttp://www.netlib.org/lp/data/readmeDyK "http://www-neos.mcs.anl.gov/neos/yK Dhttp://www-neos.mcs.anl.gov/neos/1DyK /http://www.gamsworld.org/performance/links.htmyK ^http://www.gamsworld.org/performance/links.htmDyK www.google.comyK .http://www.google.com/DyK http://scholar.google.com/yK 6http://scholar.google.com/DyK www.ams.org/mathscinetyK <http://www.ams.org/mathscinetUDyK 8http://www-neos.mcs.anl.gov/neos/server-solvers-in.htmlyK phttp://www-neos.mcs.anl.gov/neos/server-solvers-in.htmlDyK 'ftp://plato.la.asu.edu/pub/ampl_files/yK Nftp://plato.la.asu.edu/pub/ampl_files/!DyK +http://www.gamsworld.org/performance/plib/yK Vhttp://www.gamsworld.org/performance/plib/DyK 'http://www.gamsworld.org/translate.htmyK Nhttp://www.gamsworld.org/translate.htmeDyK <http://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/yK xhttp://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/DyK http://www.gzip.org/yK *http://www.gzip.org/-DyK .http://www.math.sjsu.edu/~foster/math177.htmlyK \http://www.math.sjsu.edu/~foster/math177.htmlDyK (ftp://plato.asu.edu/pub/lptestset/misc/yK Pftp://plato.asu.edu/pub/lptestset/misc/-DyK .http://www.math.sjsu.edu/~foster/math177.htmlyK \http://www.math.sjsu.edu/~foster/math177.htmlDyK (ftp://plato.asu.edu/pub/lptestset/misc/yK Pftp://plato.asu.edu/pub/lptestset/misc/eDyK <http://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/yK xhttp://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/ADyK 2http://www-neos.mcs.anl.gov/neos/faq.html#bashfulyK Thttp://www-neos.mcs.anl.gov/neos/faq.htmlbashfulV0Ddg5=T  C 0Aglobe_smallR/^a}giq)/F/^a}giq)JFIFddDucky<&Adobed /o       {) 0@!1"2P`3$5#&!1AQ aq"2BRb#@3rS0PC$s4! @1AP`pQaq!1AQa q0@P ̚SGQ44Mjl].$s$3ef36^l.|;BP;<#L)Y6iMjt&K"̂2ea6Tա6jjւJ* :Z&MvtK:eƙ X hje:́5JZ_'Ѽ}1^w&Õ۠^-wL' J(UuH'BO™`85Ktm0-+ҝn}Rbؖl<]w|5ſ#ε~Ѽd{0׍He;kL^wιE6Qƴ/ UT$VQUhQF̿y=`=lohS}?SMSW~^n?n>7pNwؔF1^Nd,nQ#iR) ]5i}^]#(HI*3u!|>1g}WeK~ViI㳶,cQ*ZcU Q2>ڋAnKavU6*Ne+{#Ҳ83(6@q>tpzNώV|/r:mϸ-"ڗ}Ub'̓7cQ[,*(oF 1 )U)/E YI ܈{p&{w)'lY_D"e -o Hx N]p3(*WYvFu|@QUB'cĥ%b Tvo4C^lJ~NS&B ng~ZE gLn8?^~(hRi]I;k8b?/j`ErK"Zߋk;Xޗq{s9-I)/K^Ƕל֓IV7Vcx%P̆u󻳳Ui%DsteΨ[wl,봶 @B{mh>GbN6eof&ghd5zA aG2}_g5[3AZG*ZZ HHg&xf 6UyK @_ʱ=Sړ{! 3@dNf-dinep%(u fFW]'u#a"@k4WϞd.Bl- %%C)4JZRHђ'Y`"΄ ȆT.v C R"t&B)r#D:YYYYYYY/r]K++++g:wDi-όLLJD9IԒ9ʴO$-n l1)C$ӧF\g7av.}y!lG؃ҰYff]BJ N:'Yavϔ(­9PIlu>']8;*'Nt͖x]IMUhəPP%r˅, WB<:t_^c(ț/$B>0'NLrݕ#’,FRWʆ.%;#"@N:v_OEqrYY+> aaco?2یp3 '7x3:d:gNɛXLV|YYY+ʶIY#WC]5A3?`?e+7ՠ/ؚ͝W}Dkb^a*vV?no@G7Xo3湭z~}e`ݕ;Ir}n\&RT{|о+7S]$G-piIbou%nތm4w;uwEy[F= ,0i`5ڍIf?*-Gl[ކ<-~!yW"PB"ÍrMW27ڎlC\S?ubM)6oopd]A˷QqhC:5mھ؛Wμӧ0 7hedCb)e>s +|WLHl ?~+ . ~UHnI菛x1hs09X/}IT){wF Ϫnc;,h8$J6":yLmEN\2vNV#]Y0o8uMЋw(<>h0uou? coa_iShr acb+d-۶ Oԣ6AoiƽWG ɧ\~ΠOv\YMeI `UᲹ דʫn=7޸*gT")g;bjdɨđ-eJ4w?;Dɧ ǚqDi #y|Pq$Nd>+doГoa_G27ăǺ*O~R<8I~#"aZl"KJmAQf_PaԉayTl\㗼wTreH-Vgʂ'p[X5:WgT:1V`j#1I5v7=8C3m쫬a5c<Ʊ7R2w, 6 WVYgv/n̙൶p7ڦ]m֦vC~N1=p5n2DHmU2"=FoG37,˷ ޤ_+}XٿA>S^qlkMc. |)fH4Z8>}L$\c={G(OFIA,ܵ^RKη£80͕j->BLWa50 T˹DzH@ݦ\~VZQud_{4>d6v$yU-vP@7iei8u wxU,r~)Oюꬆޅ#£ mZ_Υ7C'=Q߆Z>aLJϭ]O}`֒wN8.+G$Br{ ac>Ҁ 6 Op!XuC jekhgb~.+a2#֏qx*wqݧ!j[1Y0k>byvG>eY-3il:]p Og aGoX?1 /3!iG\qm`MdTv9rS^,2%PW3R>=/n=aWʅ҅w(VF\K(r8H|q4Yw@ޯۧ_ ~ʃ1Z|BK70_bGS_C~*K;@1`w/: MȠX Y #xO1ڍwWR[XcF  {IUJe ̢0,`Yl )(@}i2%RNJ>Ywd*ZOj"90E%aze(A'Z8o^.Q] bK͚QHy qW-Wt}*8k*iKǘ: ^G--vo+3#On#'j<}dz[ɳL»vnNgeݟܬK>< 4ʾuꘈp6JoRͰ}5CkRQ7ArNQ@FI U.leaHQ|MS_,5-_KcEM9ie,du 61G@ S~6: `!xp}\XQ8bWnCC'v = 3,?0u9C C"mN;y\ZX!ķ^Pڔ(4kPʠ0m(Q6g+c5ݢ s_̥25%Yyh3wrHY|J~ȀTeӇ܈zZGa)`Z` `X/mПص9eK^#0YOXfVVA55c$K+F:pB( |ǞMb-SX/R:36v3.ۿ_l1GdrQ=\} Бp^~ sXk9  PxJ5h7Waߴlˮ?AD Byt}Fd4&eQ^fr,S%۵]ۛNUrB:bȟȧkXڷp1l90j= N L64^ԷWySvOl2hcB #fIjϘU{ʯ#>nR1kQ W}}:-(!WB9| [ k8-VݹVșVnIZ0 ۘhCb\v-jkZ12DT2S/K3hKM(eA<]p4b䅮ceLÚ`WoDuG"d}Bh/ܗ 0ZQc;IGZu=X"uqp-aPl{}n!i 7+^,"E(u8r,nj h)!APn\5kcLZЉHJإ!( 3,$=d5ī?xi .xQ@.q7 Mxf0!4У+0GP4V/ֆJbdFOlK܉w#6>"OcJO-4ZX9gh b֎Tk.FQϒ Ljo6#YȝQa6%|'3 3A28C?*ғ ˀX,>d'JjƯE*kG"U˘_%~c iK\`kE vhB":l-@6K4‹,1L)c:4 ġ]߳ ˛uUq5157(Ufc!|M{u}gӨ|8/ˀhr:VjEo|A*$ O4g2eE0w|8/0%Al 9 XZmd ze 5"J;ow#kǥ$ `JPmAhKrY+Wr=X8򥂻 AaUF]H5ś lXqͱccŮ7i_m" 5NYTjnwws;ܑB'QSfo0S +coOeKf4f$M\F.BoaOtcny00qhRe"n52!9ic$ $@ŻXPycht f钍j^XT`NHQp)`z 0R8|' ʄJ;oqJe‚\M 76~h_gh7h616UƇͪ,xhŽQPie/e7 & OE՟6KfsQGC؞h q7W @Do3G%CKmD+xuFcTA!u~l&vDEK5M D_I>f =!k:<{PQ Z%BpĨ@bEUyYRV*MxerՅ 3\OcIB71R]\uR))(`zPB:B3*z9ھ%U"l,@C52֘JL@<;ΉٕzU|uz#veuZz$!A ë0apT++0y"Dxs3k^-oW@`zט]yb7!BO'qܾ7-+,V_kYlY|Yo܅%Kgg|I|oO`}?!@ Tc(b I eB cŦ(UQm<1.!:~@"E4KM%4uA./Ԧw/?(](!gٗr&Y)dUU_A|wĶU?hm-L&_be)0ÇnQw5RHTPeT}|_ +x7p"(y_@,U̯\{E֬lX 0XFyĠ]0p4RoK^.a'/5QtN fM"i\X5i !EJ, "FbW#XRYr'uűx/,[&0D68 *qc!s8b)fcĪ=#xl%N>*Q+LC "6.?J=2̆e_l8  2;$H2Dj mZĮYC4z"\rWD-_ϤG} ʑ*$HH۠'l!k6}-2ߏg&*7??EtHt2+jENz@1툟W0I\H(/x#J 5%0!:$GbL:>%1Ǚiim%E5K@4TgV2U,UBj: g?B2\ F:}qao")VTvBЄ}̸QJj +R؄\ya.)2!zM=2bf:Hظt! zDt)"]QΕҥJ+JxTL 1`,K)^J2Gd@,C&1B@:HcaJT F"fr= =GDWhB\!]lRBbДOE;KeQ\jY`{!Fp0o˗.Q@Tq>g[_Kԃ*WAIr1r?_ i8@8 NormalCJ_HaJmH sH tH Z@Z Heading 1dd@&[$\$"5CJ0KH$OJPJQJ\^JaJ0<A@< Default Paragraph Font*>@* Title$a$5\,B@, Body Text$a$.U@. Hyperlink >*B*ph>V@!> FollowedHyperlink >*B* phVVEF|}K )*3NO:; 34+,[\pcv BEGI/0)*jk;<}~ /#0#$$9%'U*,---...../01 22933\55555;=3>>AFJOuQvQwQQQQQQQQQQRR0R6R=RDRLR[R\R]R^R_RbRhRrRyRRRRRRRRRRRRRRRRR SSS!S+S4S=S>S?SfSgSVVV00000 0 0 0 00000000000000000000000000000000000000000000000000000000000000000000000000 0 0 0 00000000 0 0 0 0 0 0 0 00000 0 0 0 0 0 0 0 0 0000000000@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@0@00000@0000000003k8KZ067949)3BUVLV^VrVVVVV+WfWZ13458:;<=>?@ABCDZ2 . M   _ b V `///@0q00001n11 2K2222373T33334.4B4l444447K77L8888+9V99 :G:<N<<AB*BBBBBC#CGGHJJJ!L^LLOTO|OP4QpQT;UmUVXXXXXXXXXXXXXXXXXXXXXXXX4X4XXXXXX8@((    c R. ``TT`TT B S  ?V!=@, _Hlt99272020 _Hlt99272021 _Hlt99271983 _Hlt99354361 _Hlt99354362 _Hlt99354330 _Hlt99354326 _Hlt99354327 _Hlt99354106 _Hlt99354107 _Hlt99349451 _Hlt99349452 _Hlt99355098 _Hlt99355099 _Hlt99354406 _Hlt99354407 _Hlt99350917 _Hlt99350918 _Hlt99349472 _Hlt99357839 _Hlt99357840 _Hlt99267171 _Hlt99267150 _Hlt99267139 _Hlt99267140 _Hlt99267159 _Hlt99271408 _Hlt99271409 _Hlt99271518 _Hlt99271507 _Hlt99271508 _Hlt99271132 _Hlt99271133 _Hlt99270439 _Hlt99270440 _Hlt99271360 _Hlt99271361 _Hlt99269289 _Hlt99269290 _Hlt99271775 _Hlt99271776 _Hlt99268118 _Hlt99351771 _Hlt99351772     k k r x x //u0u0{0 1 11111111111122(4k<k<V@@@@@@@@@ @ @ @ @ @@@@@@@@@@@@@@@@@@@ @!@"@#@$@%@&@'@(@)@*@+@     l l s y y //v0v0|0 1 11111111111122)4l<l<V035:<?AGV\}CLuv=JT[ &O\fm!!!!/ />/B///00 22 2&23324844455;5C5 ;;<<C=G=L=P=^=b=====%>,>Y>`>????*@0@Q@Z@@@[AdAAAAA0D7DDDEEBEDE_EaEbEmEEEEEEE'F+F0F;F>FFFXFcFFF GGG GHHHHII+I-I.I9IIIJJKKKKKLLLDMGMlMnMMMMMMM2N6N9NBNENRN3P7P//$00444455556 6Q6^677L888W99H:;;<<o=o=A+BCCCCGHJJ!LLO}OPsQtQuQvQvQwQQQR/R6R:R=RARDRIRLRZR[R_RaRbRRRRRRRRRRRRRRRRRRRR SSSSSSSSS#S$S'S(S+S>S?SeSeSiTiTTnU~UULVVVVVVVVVV Leslie FosterfosterF:\m177\M177_Project.docfosterF:\m177\M177_Project.docfosterF:\m177\M177_Project.docfosterD:\Fdrive\m177\M177_Project.docfoster"J:\htmlfiles\m177\M177_Project.docfoster"J:\htmlfiles\m177\M177_Project.docfosterfC:\Documents and Settings\foster\Application Data\Microsoft\Word\AutoRecovery save of M177_Project.asdfosterfC:\Documents and Settings\foster\Application Data\Microsoft\Word\AutoRecovery save of M177_Project.asdfoster"J:\htmlfiles\m177\M177_Project.doc.~$@$$4&L.P )\'I1|;iT"yIh ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(h^`OJQJo(hHh^`OJQJ^Jo(hHohpp^p`OJQJo(hHh@ @ ^@ `OJQJo(hHh^`OJQJ^Jo(hHoh^`OJQJo(hHh^`OJQJo(hHh^`OJQJ^Jo(hHohPP^P`OJQJo(hHh^`OJQJo(hHh^`OJQJ^Jo(hHohpp^p`OJQJo(hHh@ @ ^@ `OJQJo(hHh^`OJQJ^Jo(hHoh^`OJQJo(hHh^`OJQJo(hHh^`OJQJ^Jo(hHohPP^P`OJQJo(hHh ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(h  ^ `OJQJo(hHh^`OJQJ^Jo(hHoh^`OJQJo(hHh| | ^| `OJQJo(hHhLL^L`OJQJ^Jo(hHoh^`OJQJo(hHh^`OJQJo(hHh^`OJQJ^Jo(hHoh^`OJQJo(hHh ^`OJQJo(h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(h^`.h ^`OJQJo(oh pp^p`OJQJo(h @ @ ^@ `OJQJo(h ^`OJQJo(oh ^`OJQJo(h ^`OJQJo(h ^`OJQJo(oh PP^P`OJQJo(i )\'"y1|;$@$$&                                                               vQwQQQQQQQQQRRR/R0R6R=RDRLRSRZR[R\R]R^R_R`RaRbRhRrRyRRRRRRRRRRRRRRRRRRRRRRRRS SSS!S+S4S=S>SV@uQuQHuQuQh"V`@UnknownGz Times New Roman5Symbol3& z Arial?5 z Courier NewI& ??Arial Unicode MS;Wingdings"qh“I#&“ G$ ;H$!820dXT53QH;M177 Project - Simplex Method versus Interior Point MethodfosterfosterOh+'0 , <H d p | <M177 Project - Simplex Method versus Interior Point Method177fosteroostost Normal.dottfosterd4stMicrosoft Word 9.0p@ @{0@?0@#R9 G՜.+,D՜.+,< hp  San Jose State Universityl$X <M177 Project - Simplex Method versus Interior Point Method Title 8@ _PID_HLINKSAl%1Z*http://www-neos.mcs.anl.gov/neos/faq.htmlbashful)CW<http://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/#:T(ftp://plato.asu.edu/pub/lptestset/misc/Q.http://www.math.sjsu.edu/~foster/math177.html#:N(ftp://plato.asu.edu/pub/lptestset/misc/K.http://www.math.sjsu.edu/~foster/math177.htmlR@H"http://www.gzip.org/gzip124xN.exeMQE"http://www.gzip.org/gzip124xN.zipRVBhttp://www.gzip.org/)C?<http://www.sztaki.hu/~meszaros/public_ftp/lptestset/netlib/l/<'http://www.gamsworld.org/translate.htm`u9+http://www.gamsworld.org/performance/plib/1M6'ftp://plato.la.asu.edu/pub/ampl_files/2;38http://www-neos.mcs.anl.gov/neos/server-solvers-in.htmlJW0http://www.ams.org/mathscinet)$-http://scholar.google.com/3!*http://www.google.com/67'/http://www.gamsworld.org/performance/links.htmF_$"http://www-neos.mcs.anl.gov/neos/!%http://www.netlib.org/lp/data/readmeFhttp://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.htmlu0 http://plato.asu.edu/bench.html "http://plato.asu.edu/talks/lp.pdfz=+ftp://plato.asu.edu/pub/papers/paper85.pdf6d;http://www-neos.mcs.anl.gov/neos/neos-cgi/check-status.cgiF_"http://www-neos.mcs.anl.gov/neos/Z( 5http://www.sztaki.hu/~meszaros/public_ftp/lptestset/=0 #ftp://plato.asu.edu/pub/lptestset/Shttp://miplib.zib.de/pdhttp://www.netlib.org/lp/data/_[http://www.netlib.org/lp/PZ globe_small  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklnopqrstuvwxyz{|}~Root Entry FP*dLm@Data FL1TablemGWordDocument"SummaryInformation(DocumentSummaryInformation84CompObjjObjectPool D$R9 D$R9   FMicrosoft Word Document MSWordDocWord.Document.89q ]8O8m0T@HPX ,urn:schemas-microsoft-com:Win32CreationTime.urn:schemas-microsoft-com:Win32LastAccessTime0urn:schemas-microsofBagaaqy23kudbhchAaq5u2chNd8 {YLmP*dLmCONTENTSt-com:Win32LastModifiedTimeMon, 04 Apr 2005 20:09:01 GMTMon, 04 Apr 2005 20:09:01 GMTMon, 04 Apr 2005 20:09:02 GMT