This assignment gives you a little exposure to LPs that are a bit larger than the ones we have been implementing in class. You will also let various algorithms (primal simplex, dual simplex, interior point) go at it mano a mano.
You will run CPLEX (outside of AMPL) on a number of LPs with thousands of variables and constraints. They come from the collection of LP test problems maintained in the NETLIB software repository at http://www.netlib.org/lp .
One thing to keep in mind about LP test problems is that they are often kept around as test problems because they are considered difficult or challenging to solve.
Here is a description of the LPs you will solve.
Name Rows Cols Nonzeros Optimal Value MPS file size
(lines)
DFL001 6072 12230 41873 1.1266396047E+07 29923
GFRD-PNC 617 1092 3467 6.9022359995E+06 3099
MAROS 847 1443 10006 -5.8063743701E+04 6250
MODSZK1 688 1620 4158 3.2061972906E+02 2973
SIERRA 1228 2036 9252 1.5394362184E+07 8977
As for the provenance of these LPs, hear what the accompanying
documentation
says.
1. MAROS.
Concerning the problems he submitted, Istvan Maros says that MAROS is an industrial production/allocation model about which "the customer does not want to reveal the exact meaning".
2. GFRD-PNC.
R. Helgason, J. Kennington, and P. Wong, "An Application of Network Programming for National Forest Planning", Technical Report OR 81006, Dept. of Operations Research, Southern Methodist University.
3. MODSZK1.
MODSZK1 is a "real-life problem" that is "very degenerate" and on which a dual simplex algorithm "may require up to 10 times" fewer iterations than a primal simplex algorithm. It "is a multi-sector economic planning model (a kind of an input/output model in economy)" and "is an old problem of mine and it is not easy to recall more."
4. SIERRA.
R. Helgason, J. Kennington, and P. Wong, "An Application of Network Programming for National Forest Planning", Technical Report OR 81006, Dept. of Operations Research, Southern Methodist University.
5. DFL001.
DFL001, says Marc Meketon, "is a 'real-world' airline schedule planning (fleet assignment) problem. This LP was preprocessed by a modified version of the KORBX(r) System preprocessor. The problem reduced in size (rows, columns, non-zeros) significantly. The row and columns were randomly sorted and renamed, and a fixed adjustment to the objective function was eliminated. The name of the problem is derived from the initials of the person who created it."
Here is what you'll need to do. You'll need to be logged in to mathbg on the Mathematics Department network to use CPLEX (you can also ssh to mathbg). In addition, you will need to add the following line to your .cshrc file. (If you don't have one you will need to create one.)
You should also be aware that only one person can use CPLEX at at time.setenv ILOG_LICENSE_FILE /home/ms3/buckaroo/pub/ilog/ilm/license.dat
The interactive CPLEX program is
If this directory is included in your path, you just need to type cplex to provoke the executable./home/ms3/buckaroo/pub/ilog/cplex110/bin/x86_rhel4.0_3.4/cplex
You will also need the MPS data files. These files are rather large. Alternatively you may copy the gzipped versions of these files by right clicking on the blue filenames below. You will need to unzip them before loading them into CPLEX.
Now you should be ready to rock and roll. When you start up the interactive CPLEX program, you'll get a prompt like this:
You can type help to get a list of the interactive commands.CPLEX>To read one of the MPS files, say, sierra.mps type
To solve this problem using the primal simplex method, typeCPLEX> read sierra.mpsTo solve this problem using the dual simplex method, typeCPLEX> primoptTo solve this problem using an interior point barrier method, typeCPLEX> tranoptIn order to start from scratch, you'll need to re-read the MPS file after each solution.CPLEX> baropt
The assignment (finally!) 1. For each of these problems, compute the sparsity of the constraint matrix A:
sparsity = number of nonzeros / total number of entries.2. Solve each of these problems using CPLEX, using the primal simplex, the dual simplex method, and the barrier method. Record the solution time and the number of iterations. Check that your optimal objective agrees with the values above.
The primal and dual simplex methods will give you a report of solution time and the number of iterations once they are done.
The output from the barrier method is a bit different. The barrier method approaches the solution through the interior of the feasible polyhedron. You'll see an iteration history that ends with
Barrier time = xxxx sec.Record the number of iterations up to this point, and the time. Once the barrier method is close to the optimal solution, which we know lies on the boundary, it switches to a clean-up phase where it moves onto the boundary. Record the final solution time as well.One way to view the operation of the barrier method interior point algorithm is that it is taking steps in both the primal and dual variables to try to reduce the difference between the primal and dual objectives to zero. We know that if the primal and dual objectives agree, we must be at the optimal solution.
2a. Special instructions for SIERRA and GFRD-PNC. These two problems are actually network LP. Unfortunately, MPS format has no explicit provision for specifying network problems. On the other hand, it is possible to extract the network structure (remember the peculiar form of network constraints), and codes like CPLEX can do so. In addition to solving these two problem with the primal and dual simplex methods and the barrier method, you should also try the network simplex method on them. To do so, re-read the problem (so you start from scratch) and solve them with the network simplex method netopt: To solve this problem using the network simplex method, type
Record the solution time and number of iterations.CPLEX> netopt2b. Special instructions for DFL001. This problem is by far the hardest of these LP and takes a while to solve. If you don't want to wait around (though it is kind of fun to watch CPLEX grind away at the solution) you can solve this program in background. Just put the commands
read dfl001.mps primpopt read dfl001.mps tranopt read dfl001.mps baropt quitin a file, say, foo.in. Then redirect CPLEX's input to be from foo.in and redirect the output to (say) foo.out, running the whole thing in background:cplex < foo.in > foo.out &Then you can logout and look for the results in foo.out later. (Just make sure you correctly figure out which output goes with which solution method.)3. For DFL001 and one or two of other the problems, compare the solution times and number of iterations. Also, compare the time per iteration for the different methods.
In addition, compare the number of iterations to the number of constraints (Rows). How do these results compare with the claim that the number of iterations needed by the simplex method to solve an LP is bounded by 1-3 times the number of constraints? By this criterion, do you agree that DFL001 is "hard"?
4. The default pricing scheme in CPLEX is a version of partial pricing. You can switch the pricing scheme to Devex (see page 227 of our Nash and Sofer, Linear and Nonlinear Programming for details concerning Devex) via the command:
set simplex pgradient 1to steepest edge pricing byset simplex pgradient 2or to full pricing byset simplex pgradient 4For DFL001, try the more sophisticated steepest edge pricing scheme and see how your execution time compares to those obtained with the default pricing scheme. If the more sophisticated scheme slows you down, can you explain why?What you are to turn in. Your results from 1, 2, 3, and 4.
Rex Kincaid
Last update: 11/27/2007