The column and nonzero counts in the PROBLEM SUMMARY TABLE below exclude
slack and surplus columns and the right-hand side vector, but include
the cost row. We have omitted other free rows and all but the first
right-hand side vector, as noted below. The byte count is for the
compressed file; it includes a newline character at the end of each
line. These files start with a blank initial line intended to prevent
mail programs from discarding any of the data. The BR column indicates
whether a problem has bounds or ranges: B stands for "has bounds", R
for "has ranges". The BOUND-TYPE TABLE below shows the bound types
present in those problems that have bounds.
The problems below are sorted (according to the ASCII collating
sequence) on their names. Unless problem characteristics suggest a
more rational order, we suggest using this order for reporting results.
PROBLEM SUMMARY TABLE
Name Rows Cols Nonzeros Bytes BR Optimal Value
25FV47 822 1571 11127 70477 5.5018458883E+03
80BAU3B 2263 9799 29063 298952 B 9.8723216072E+05
ADLITTLE 57 97 465 3690 2.2549496316E+05
AFIRO 28 32 88 794 -4.6475314286E+02
AGG 489 163 2541 21865 -3.5991767287E+07
AGG2 517 302 4515 32552 -2.0239252356E+07
AGG3 517 302 4531 32570 1.0312115935E+07
BANDM 306 472 2659 19460 -1.5862801845E+02
BEACONFD 174 262 3476 17475 3.3592485807E+04
BLEND 75 83 521 3227 -3.0812149846E+01
BNL1 644 1175 6129 42473 1.9776292856E+03
BNL2 2325 3489 16124 127145 1.8112365404E+03
BOEING1 351 384 3865 25315 BR -3.3521356751E+02
BOEING2 167 143 1339 8761 BR -3.1501872802E+02
BORE3D 234 315 1525 13160 B 1.3730803942E+03
BRANDY 221 249 2150 14028 1.5185098965E+03
CAPRI 272 353 1786 15267 B 2.6900129138E+03
CYCLE 1904 2857 21322 166648 B -5.2263930249E+00
CZPROB 930 3523 14173 92202 B 2.1851966989E+06
D2Q06C 2172 5167 35674 258038 1.2278423615E+05
D6CUBE 416 6184 43888 167633 B 3.1549166667E+02
DEGEN2 445 534 4449 24657 -1.4351780000E+03
DEGEN3 1504 1818 26230 130252 -9.8729400000E+02
DFL001 6072 12230 41873 353192 B 1.12664E+07 **
E226 224 282 2767 17749 -1.8751929066E+01
ETAMACRO 401 688 2489 21915 B -7.5571521774E+02
FFFFF800 525 854 6235 39637 5.5567961165E+05
FINNIS 498 614 2714 23847 B 1.7279096547E+05
FIT1D 25 1026 14430 51734 B -9.1463780924E+03
FIT1P 628 1677 10894 65116 B 9.1463780924E+03
FIT2D 26 10500 138018 482330 B -6.8464293294E+04
FIT2P 3001 13525 60784 439794 B 6.8464293232E+04
FORPLAN 162 421 4916 25100 BR -6.6421873953E+02
GANGES 1310 1681 7021 60191 B -1.0958636356E+05
GFRD-PNC 617 1092 3467 24476 B 6.9022359995E+06
GREENBEA 2393 5405 31499 235711 B -7.2462405908E+07
GREENBEB 2393 5405 31499 235739 B -4.3021476065E+06
GROW15 301 645 5665 35041 B -1.0687094129E+08
GROW22 441 946 8318 50789 B -1.6083433648E+08
GROW7 141 301 2633 17043 B -4.7787811815E+07
ISRAEL 175 142 2358 12109 -8.9664482186E+05
KB2 44 41 291 2526 B -1.7499001299E+03
LOTFI 154 308 1086 6718 -2.5264706062E+01
MAROS 847 1443 10006 65906 B -5.8063743701E+04
MAROS-R7 3137 9408 151120 4812587 1.4971851665E+06
MODSZK1 688 1620 4158 40908 B 3.2061972906E+02
NESM 663 2923 13988 117828 BR 1.4076073035E+07
PEROLD 626 1376 6026 47486 B -9.3807580773E+03
PILOT 1442 3652 43220 278593 B -5.5740430007E+02
PILOT.JA 941 1988 14706 97258 B -6.1131344111E+03
PILOT.WE 723 2789 9218 79972 B -2.7201027439E+06
PILOT4 411 1000 5145 40936 B -2.5811392641E+03
PILOT87 2031 4883 73804 514192 B 3.0171072827E+02
PILOTNOV 976 2172 13129 89779 B -4.4972761882E+03
QAP8 913 1632 8304 (see NOTES) 2.0350000000E+02
QAP12 3193 8856 44244 (see NOTES) 5.2289435056E+02
QAP15 6331 22275 110700 (see NOTES) 1.0409940410E+03
RECIPE 92 180 752 6210 B -2.6661600000E+02
SC105 106 103 281 3307 -5.2202061212E+01
SC205 206 203 552 6380 -5.2202061212E+01
SC50A 51 48 131 1615 -6.4575077059E+01
SC50B 51 48 119 1567 -7.0000000000E+01
SCAGR25 472 500 2029 17406 -1.4753433061E+07
SCAGR7 130 140 553 4953 -2.3313892548E+06
SCFXM1 331 457 2612 19078 1.8416759028E+04
SCFXM2 661 914 5229 37079 3.6660261565E+04
SCFXM3 991 1371 7846 53828 5.4901254550E+04
SCORPION 389 358 1708 12186 1.8781248227E+03
SCRS8 491 1169 4029 36760 9.0429998619E+02
SCSD1 78 760 3148 17852 8.6666666743E+00
SCSD6 148 1350 5666 32161 5.0500000078E+01
SCSD8 398 2750 11334 65888 9.0499999993E+02
SCTAP1 301 480 2052 14970 1.4122500000E+03
SCTAP2 1091 1880 8124 57479 1.7248071429E+03
SCTAP3 1481 2480 10734 78688 1.4240000000E+03
SEBA 516 1028 4874 38627 BR 1.5711600000E+04
SHARE1B 118 225 1182 8380 -7.6589318579E+04
SHARE2B 97 79 730 4795 -4.1573224074E+02
SHELL 537 1775 4900 38049 B 1.2088253460E+09
SHIP04L 403 2118 8450 57203 1.7933245380E+06
SHIP04S 403 1458 5810 41257 1.7987147004E+06
SHIP08L 779 4283 17085 117083 1.9090552114E+06
SHIP08S 779 2387 9501 70093 1.9200982105E+06
SHIP12L 1152 5427 21597 146753 1.4701879193E+06
SHIP12S 1152 2763 10941 82527 1.4892361344E+06
SIERRA 1228 2036 9252 76627 B 1.5394362184E+07
STAIR 357 467 3857 27405 B -2.5126695119E+02
STANDATA 360 1075 3038 26135 B 1.2576995000E+03
STANDGUB 362 1184 3147 27836 B (see NOTES)
STANDMPS 468 1075 3686 29839 B 1.4060175000E+03
STOCFOR1 118 111 474 4247 -4.1131976219E+04
STOCFOR2 2158 2031 9492 79845 -3.9024408538E+04
STOCFOR3 16676 15695 74004 (see NOTES) -3.9976661576E+04
TRUSS 1001 8806 36642 (see NOTES) 4.5881584719E+05
TUFF 334 587 4523 29439 B 2.9214776509E-01
VTP.BASE 199 203 914 8175 B 1.2983146246E+05
WOOD1P 245 2594 70216 328905 1.4429024116E+00
WOODW 1099 8405 37478 240063 1.3044763331E+00
HEARTY THANKS go to the people who supplied the above problems.
Michael Saunders provided 13 problems from the Systems Optimization
Laboratory at Stanford University: ADLITTLE, AFIRO, BANDM, BEACONFD,
BRANDY, CAPRI, E226, ETAMACRO, ISRAEL, PILOT, SHARE1B, SHARE2B, STAIR.
Four problems are from a tape that John Reid sent me (David Gay) several
years ago: 25FV47, CZPROB, FFFFF800, SHELL. Linus Schrage sent GANGES
and SEBA. Bob Fourer supplied 44 problems: 80BAU3B, BORE3D, FIT1D,
FIT1P, FIT2D, FIT2P, FORPLAN, GFRD-PNC, GREENBEA, GREENBEB, GROW15,
GROW22, GROW7, NESM, PILOT.JA, PILOT.WE, PILOT4, PILOTNOV, RECIPE,
SC205, SCAGR25, SCAGR7, SCFXM1, SCFXM2, SCFXM3, SCORPION, SCRS8, SCSD1,
SCSD6, SCSD8, SCTAP1, SCTAP2, SCTAP3, SHIP04L, SHIP04S, SHIP08L,
SHIP08S, SHIP12L, SHIP12S, SIERRA, STANDATA, STANDGUB, STANDMPS,
VTP.BASE. Mauricio Resende provided AGG, AGG2, and AGG3, which were
formulated by R. C. Leachman. Gus Gassmann contributed STOCFOR1,
STOCFOR2, and STOCFOR3. Nick Gould supplied BLEND, BOEING1, BOEING2,
FINNIS, PEROLD, SC105, SC50A, and SC50B from the Harwell collection of
LP test problems. Vahid Lotfi submitted LOTFI. With the permission of
Ketron, John Tomlin provided BNL1, BNL2, CYCLE, D2Q06C, DEGEN2, DEGEN3,
KB2, TUFF, WOOD1P, and WOODW. At the request of Olvi Mangasarian,
Rudy Setiono supplied the generator and description (both written by
Michael Ferris) and data for TRUSS. Istvan Maros provided MAROS,
MAROS-R7, and MODSZK1. Irv Lustig supplied PILOT87, which he obtained
from John Stone. Marc Meketon submitted DFL001. Robert Hughes supplied
D6CUBE. Problems QAP8, QAP12, and QAP15 are from a generator by Terri
Johnson (communicated by a combination of Bob Bixby, Matt Saltzman, and
Terri Johnson).
Thanks also go to Irv Lustig for helpful comments on this index file.
STOCFOR1,2,3 are stochastic forestry problems from Gus Gassmann. To
quote Gus, "All of them are seven-period descriptions of a forestry
problem with a random occurrence of forest fires, and the size varies
according to the number of realizations you use in each period."
STOCFOR1 "is the deterministic version, STOCFOR2 has 2 realizations
each in periods 2 to 7, and the monster STOCFOR3 has 4,4,4,2,2, and 2
realizations, respectively." The compressed form of STOCFOR3 would be
652846 bytes long, so requesting STOCFOR3 will instead get you a bundle
of about 174 kilobytes that includes source for Gus's program, the
data files for generating STOCFOR3 and a summary of "A Standard
Input Format for Multistage Stochastic Linear Programs" by J.R. Birge,
M.A.H. Dempster, H.I. Gassmann, E.A. Gunn, A.J. King, and S.W. Wallace
[COAL Newsletter No. 17 (Dec. 1987), pp. 1-19]. Data files are also
included for generating versions of STOCFOR1,2 that have more decimal
places than the versions in lp/data.
Concerning the problems he supplied, Nick Gould says that BLEND "is
is a variant of the [oil refinery] problem in Murtagh's book (the
coefficients are different) which I understand John Reid obtained
from the people at NPL (Gill and Murray?); they were also the original
sources for the SC problems"; BOEING1 and BOEING2 "have to do with
flap settings on aircraft for economical operations"; PEROLD "is
another Pilot model (Pilot1)"; and FINNIS "is from Mike Finnis at
Harwell, a model for the selection of alternative fuel types."
BOEING1 and BOEING2 were originally mixed-integer programming problems.
The COLUMNS section of BOEING1 had
INTBEG 'MARKER' 'INTORG'
between the coefficients for columns GRDTIMN6 and N1001AC1, and that
BOEING2 had such a line between columns GRDTIMN4 and N1003AC1. Both had
INTFIN 'MARKER' 'INTEND'
just before the start of the ROWS section. These 'MARKER' lines have
been removed. These problems also had a few rows defined as linear
combinations of other rows. These rows are now given explicitly, since
the compression/expansion programs do not understand D lines in the ROWS
section.
LOTFI, says Vahid Lotfi, "involves audit staff scheduling. This problem
is semi real world and we have used it in a study, the results of which
are to appear in Decision Sciences (Fall 1990). The detailed
description of the problem is also in the paper. The problem is
actually an MOLP with seven objectives, the first is maximization and
the other six are minimization. The version that I am sending has the
aggregated objective (i.e., z1-z2-z3-z4-z5-z6-z7)."
Concerning PILOT87, Irv Lustig says, "PILOT87 is considered (by John
Stone, at least) to be harder than PILOT because of the bad scaling in
the numerics."
TRUSS is a problem of minimizing the weight
of a certain structure.
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."
Of D6CUBE, Robert Hughes says, "Mike Anderson and I are working on the
problem of finding the minimum cardinality of triangulations of the
6-dimensional cube. The optimal objective value of the problem I sent
you provides a lower bound for the cardinalities of all triangulations
which contain a certain simplex of volume 8/6! and which contains the
centroid of the 6-cube in its interior. The linear programming
problem is not easily described."
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". MAROS-R7 is "an interesting
real-life LP problem which appeared hard to some solvers." It "is an
image restoration problem done via a goal programming approach. It is
structured, namely, its first section is a band matrix with the
dominating number of nonzeros, while the second section is also a band
matrix with bandwidth equals 2 and coefficients +1, -1. The problem is
a representative of a family of problems in which the number of rows and
the bandwidth of the first section can vary. This one is a medium size
problem from the family. MAROS-R7 became available in cooperation with
Roni Levkovitz and Carison Tong." 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."
** On an IEEE-arithmetic machine (an SGI 4D/380S), I (dmg) succeeded in
getting MINOS 5.3 to report optimal objective values, 1.1261702419E+07
and 1.1249281428E+07, for DFL001 only by starting with LOAD files
derived from the solution obtained on the same machine by Bob
Vanderbei's ALPO (an interior-point code); starting from one of the
resulting "optimal" bases, MINOS ran 23914 iterations on a VAX before
reporting an optimal value of 1.1253287141E+07. When started from the
same LOAD file used on the SGI machine, MINOS on the VAX reported an
optimal value of 1.1255107696E+07. Changing the FEASIBILITY TOLERANCE
to 1.E-10 (from its default of 1.E-6) led MINOS on the SGI machine to
report "optimal" values of 1.1266408461E+07 and 1.1266402835E+07. This
clearly is a problem where the FEASIBILITY TOLERANCE, initial basis, and
floating-point arithmetic strongly affect the "optimal" solution that
MINOS reports. On the SGI machine, ALPO with SPLIT 3 found
primal: obj value = 1.126639607e+07 FEASIBLE ( 2.79e-09 )
dual: obj value = 1.126639604e+07 FEASIBLE ( 1.39e-16 )
Bob Bixby reports the following about his experience solving DFL001
with CPLEX:
First, the value for the objective function that I get running
defaults is 1.1266396047e+07, with the following residuals:
Max. unscaled (scaled) bound infeas.: 4.61853e-14 (2.30926e-14)
Max. unscaled (scaled) reduced-cost infeas.: 6.40748e-08 (6.40748e-08)
Max. unscaled (scaled) Ax-b resid.: 4.28546e-14 (4.28546e-14)
Max. unscaled (scaled) c_B-B'pi resid.: 8.00937e-08 (8.00937e-08)
The L_infinity condition number of the (scaled) optimal basis is
213737. I got exactly the same objective value solving the problem in
several different ways. I played a bit trying to get a better
reduced-cost infeasibility, but that seems hopeless (if not pointless)
given the c-Bpi residuals.
Just as an aside, this problem exhibits very interesting behavior when
solved using a simplex method. I ran reduced-cost pricing on it in
phase I, with the result that it took 465810 iterations to get
feasible. Running the default CPLEX pricing scheme, the entire
problem solved in 94337 iterations (33059 in phase I) on a
Sparcstation. Steepest-edge pricing (and a different scaling) took
25803 iterations. This is a nasty problem.
Sources for the problems from Bob Fourer:
BORE3D, RECIPE, SHIP04L, SHIP04S, SHIP08L, SHIP08S, SHIP12L,
SHIP12S, STANDATA, STANDGUB, STANDMPS, VTP.BASE: consulting.
80BAU3B: W. Kurator and Harvey Greenberg, Energy Information
Administration (Greenberg is now at the Univ. of Colorado - Denver).
GREENBEA, GREENBEB: a large refinery model; see the book
"A Model-Management Framework for Mathematical Programming" by Kenneth
H. Palmer et al. (John Wiley & Sons, New York, 1984).
GROW15, GROW22, GROW7: R. Fourer, "Solving Staircase Linear Programs
by the Simplex Method, 2: Pricing", Math. Prog. 25 (1983), pp. 251-292.
PILOT.JA, PILOT.WE, PILOT4, PILOTNOV: SOL, Stanford University.
GFRD-PNC, 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.
SC205, SCAGR25, SCAGR7, SCFXM1, SCFXM2, SCFXM3, SCORPION, SCRS8,
SCSD1, SCSD6, SCSD8, SCTAP1, SCTAP2, SCTAP3: J.K. Ho and E. Loute,
"A Set of Staircase Linear Programming Test Problems",
Math. Prog. 20 (1981), pp. 245-250.
NESM: Gerald Brown, Naval Postgraduate School.
FORPLAN: John Mulvey, Princeton.
FIT1D, FIT1P, FIT2D, FIT2P: Bob Fourer himself.
Concerning FIT1D, FIT1P, FIT2D, FIT2P, Bob Fourer says
The pairs FIT1P/FIT1D and FIT2P/FIT2D are primal and
dual versions of the same two problems [except that we
have negated the cost coefficients of the dual problems
so all are minimization problems]. They originate from
a model for fitting linear inequalities to data, by
minimization of a sum of piecewise-linear penalties.
The FIT1 problems are based on 627 data points and 2-3
pieces per primal pl penalty term. The FIT2 problems
are based on 3000 data points (from a different sample
altogether) and 4-5 pieces per pl term.
Contributions are welcome, either problems in MPS format or source code
for problem generators. Send questions, comments, contributions to
David M. Gay
Bell Laboratories, Lucent Technologies
600 Mountain Avenue, room 2C-463
Murray Hill, NJ 07974-2070
U.S.A.
phone (908) 582-5623; FAX (908) 582-5857
E-mail dmg@research.bell-labs.com