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.