lp/infeas contains infeasible linear programming test problems collected by John W. Chinneck. See the "SUMMARY OF INFEASIBLE LPs" below for more details. The test problems are in the form of MPS files. If you are not familiar with MPS files, see Chapter 9 of "Advanced Linear Programming" by Bruce A. Murtagh, McGraw-Hill, 1981. To reduce transmission times, the test problems are stored in a compressed format; issue the netlib request send emps.f from lp/data to obtain a Fortran 77 Subset program for expanding the test problems into MPS-standard input form. The program includes comments giving test data. To get a (more efficient and convenient) C version of this program (without the test data), issue the netlib request send emps.c from lp/data All the material described in summary.txt is available by netlib ftp from research.att.com (login: netlib; Password: your E-mail address; cd lp/infeas). If you can, please use ftp to obtain the larger problems. Note that the *.Z files in lp/infeas must be copied in binary mode and uncompressed two ways: first with uncompress, then with emps. If you are using a Unix system and your solver reads standard input, you can save some disk space by executing, e.g., zcat greenbea.Z | emps | solver On some Unix systems and with solvers that require a named file, you may also be able to use a named pipe, e.g., /etc/mknod greenbea.mps p zcat greenbea.Z | emps >greenbea.mps & solver greenbea.mps rm greenbea.mps ************************************************************************* SUMMARY OF INFEASIBLE LPs November 3, 1993 John W. Chinneck Systems and Computer Engineering Carleton University Ottawa, Ontario K1S 5B6 Canada telephone: (613) 788-5733 fax: (613) 788-5727 email: chinneck@sce.carleton.ca INTRODUCTION ------------ Recent years have seen a great deal of research on the analysis, diagnosis, and repair of infeasible linear programming models. Issues such as the speed and quality of the diagnosis reached by various algorithms are being raised. Other researchers are working on methods of handling infeasible LPs when using interior point solution methods. The NETLIB collection of infeasible LPs assists in this research by providing an accessible collection of standard problems which can be used to compare different approaches. All datasets are in standard MPS format. In the following, IIS stands for Irreducible Infeasible Subsystem, a set of constraints which is itself infeasible, but becomes feasible when any one member is removed. Isolating an IIS from within the larger set of constraints defining the model is one analysis approach. PROBLEM DESCRIPTIONS -------------------- ITEST6, ITEST2: very small problems having numerous clustered IISs. These match problems 1 and 2, respectively, in Chinneck and Dravnieks [1991]. Contributors: J.W. Chinneck and E.W. Dravnieks, Carleton University. FOREST6, WOODINFE: very small problems derived from network-based forestry models. The IIS in FOREST6 includes most of the rows. WOODINFE is the example problem discussed in detail in Greenberg [1993], and has a very small IIS. Contributor: H.J. Greenberg, University of Colorado at Denver. GALENET: a very small network problem. Contributor: H.J. Greenberg, University of Colorado at Denver. CHEMCOM, QUAL, REFINERY, REACTOR, VOL1: medium size problems derived from a petrochemical plant model. Doctored to generate infeasibility due to inability to meet volume or quality restrictions. With the exception of REACTOR, these are highly volatile problems, yielding IISs of varying sizes when different IIS isolation algorithms are applied. See Chinneck [1993] for further discussion. Contributor: Tom Baker, Chesapeake Decision Sciences. MONDOU2: medium size problem generated as a subproblem to a larger facility sizing algorithm used by Hydro-Quebec. The diagnosis of the infeasibility in the subproblem is useful to the larger algorithm. Contributor: J.-F. Mondou, Hydro-Quebec. PILOT4I: medium size problem generated by doctoring the original NETLIB PILOT4 model. Contributor: John Stone, Ketron Management Science. GREENBEA: this large problem is the original version of the NETLIB GREENBEA problem. The feasible NETLIB version was created by Bob Fourer by repairing the version given here. The GREENBEA problem is network based and originates in the petrochemical industry. Contributor: Bob Fourer, Northwestern University. GOSH, GRAN, PANG: these very large, large, and medium size models, respectively, problems arose from British Petroleum operations models. Contributor: Roger Main, BP Oil. KLEIN1, KLEIN2, KLEIN3: related small and medium size problems. Contributor: Ed Klotz, CPLEX Optimization Inc. CPLEX1, CPLEX2: medium and large problems respectively. CPLEX1 referred to as CPLEX problem in Chinneck [1993], and is remarkably non-volatile, showing a single small IIS regardless of the IIS algorithm applied. CPLEX2 is an almost-feasible problem. Contributor: Ed Klotz, CPLEX Optimization Inc. CERIA3D: large problem which has some peculiarities. There are no column bounds, and it is highly degenerate. Contributor: Ed Klotz, CPLEX Optimization Inc. BOX1, EX72A, EX73A: medium problems derived from research on using the infeasibility version of viability analysis [Chinneck 1992] to analyze petri net models. All three problems are volatile, showing IISs of widely differing size depending on the algorithm applied. Contributor: Zhengping You, Carleton University. BGDBG1, BGETAM, BGINDY, BGPRTR: BGDBG1 is a medium problem that was originally an integer program for a plant operation model. Infeasibility is original. BGETAM is a medium model that is a version of the ETAMACRO test problem in which one right hand side has been altered to make it infeasible. BGINDY is a large problem that was originally an integer program of unknown origin. Infeasibility is original. BGPRTR is a small model for a multiproduct, multiperiod production scheduling model. One right hand side has been altered to make it infeasible. Contributor: Linus Schrage, University of Chicago and LINDO Systems Inc. PROBLEM SUMMARY TABLE --------------------- Summary table compiled by Xiaojie Xu (University of Iowa): Name Rows Cols Nonzeros Bounds Notes bgdbg1 349 407 1485 B bgetam 401 688 2489 B bgindy 2672 10116 75019 bgprtr 21 34 90 box1 232 261 912 B all cols are LO bounded ceria3d 3577 824 17604 B FR dense col (> 967) chemcom 289 720 2190 B cplex1 3006 3221 10664 B dense col (> 1500) cplex2 225 221 1059 B ex72a 198 215 682 B all cols are LO bounded ex73a 194 211 668 B all cols are LO bounded forest6 67 95 270 B galenet 9 8 16 B gosh 3793 10733 97257 B FR 242 free cols gran 2569 2520 20151 B FX greenbea 2505 5405 35159 B FR FX itest2 10 4 17 itest6 12 8 23 klein1 55 54 696 klein2 478 54 4585 klein3 995 88 12107 mondou2 313 604 1623 B pang 362 460 2666 B FR FX pilot4i 411 1000 5145 B FR FX qual 324 464 1714 B FX reactor 319 637 2995 B FX refinery 324 464 1694 B FX vol1 324 464 1714 B FX woodinfe 36 89 209 B REFERENCES ---------- J.W. Chinneck and E.W. Dravnieks (1991). "Locating Minimal Infeasible Constraint Sets in Linear Programs", ORSA Journal on Computing, Volume 3, No. 2. J.W. Chinneck (1992). "Viability Analysis: A Formulation Aid for All Classes of Network Models", Naval Research Logistics, Vol. 39, pp. 531-543. J.W. Chinneck (1993). "Finding the Most Useful Subset of Constraints for Analysis in an Infeasible Linear Program", technical report SCE-93-07, Systems and Computer Engineering, Carleton University, Ottawa, Canada. H.J. Greenberg (1993). "A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions: A User's Guide for ANALYZE", Kluwer Academic Publishers, Boston.