======================
MINOS(IIS) version 5.2
======================

    User's Manual
    November 29, 1996

    John W. Chinneck
    Dept. of Systems and Computer Engineering,
    Carleton University,
    Ottawa, Ontario, CANADA, K1S 5B6
    telephone: (613) 520-5733
    email: chinneck@sce.carleton.ca


=====
Index
=====

1. Overview
   1.1 The Student/Demo version
   1.2 Limitations
2. Running MINOS(IIS)
   2.1 Input and Output Files
   2.2 Infeasibility Analysis Options
   2.3 Using the Guide Codes
	 2.3.1 An Example of Guided Search
   2.4 Using the Elastic Filter
   2.5 Finding IIS Set Covers
   2.6 Precedence Ordering of the Analysis Options
3. Example
   3.1 Interpreting the Output
4. Notes on Practice
5. Programming Notes
6. Version Update Log
7. References


===========
1. Overview
===========

MINOS(IIS) version 5.2 provides analysis of infeasible linear
programs to assist in isolating and repairing modelling errors.
Two types of analysis are available:

  (1) The identification of an Irreducible Infeasible Subset
	(IIS) of constraints.  An IIS is usually a very small
	subset of the complete set of constraints which define
	the model.  It has an interesting property: the IIS is
	infeasible, but any proper subset of it is feasible.
	Finding an IIS allows the analyst to focus the diagnostic
	effort on a small portion of the original model.

  (2) The identification of a Minimum Cardinality IIS Set Cover.
	If there are numerous different IISs in the model, then
	an IIS set cover is a set of constraints which includes at
	least one member of every IIS in the model.  A minimum
	cardinality IIS set cover is an IIS set cover which has the
	fewest possible members.  Removing the IIS set cover members
	from the model renders the remainder of the constraints 
	feasible.  The minimum cardinality IIS set cover problem is
	especially interesting because it also tells you the maximum
	number of constraints from the original set which can be
	satisfied simultaneously.

This brief user's manual is not the place for a full tutorial on
how the use IIS isolation and IIS set covering to analyze infeasible
LPs.  Please refer to the papers listed at the end of the manual
for information of that kind.

MINOS(IIS) is constructed from two pieces of code: 

  (1) The MINOS 5.4 code for solving linear and nonlinear programs.
	MINOS 5.4 was developed by Bruce Murtagh and Michael
	Saunders [1993], and is available through Stanford Business
	Software Inc., 2680 Bayshore Parkway, Suite 304, Mountain
	View, California 94043, USA.

  (2) The IISLOC 5.2 subroutines developed by John W. Chinneck at
	Carleton University (see references).

MINOS(IIS) is the combination of those two codes, and takes its
version number from the version number of the IISLOC routines.
Hence it is currently MINOS(IIS) 5.2.  Certain of the standard
MINOS routines were modified by Michael Saunders at Stanford
University to facilitate the integration with IISLOC.
     
MINOS(IIS) can be used just as if it were an unaltered version
of MINOS 5.4.  Infeasibility analysis happens only if the model is
infeasible; if the model is feasible, then the usual MINOS output 
is generated as usual.

----------------------------
1.1 The Student/Demo Version
----------------------------

A student/demo version of MINOS(IIS) 5.2 is available via the
world wide web at: 
   http://www.sce.carleton.ca/faculty/chinneck/minosiis.html

The student/demo edition is restricted to a maximum of 300
variables and 300 constraints in any model, and is available only
as a DOS executable file.  It is otherwise a fully functional 
edition of MINOS(IIS) 5.2.

To obtain a professional edition of MINOS(IIS), first contact
Stanford Business Software Inc. (address above) to obtain a
license for MINOS 5.4, and then contact Prof. Chinneck (address
at top) for a compiled version of the IISLOC routines.

---------------
1.2 Limitations
---------------

MINOS(IIS) version 5.2 can analyze only infeasible models defined
entirely by linear constraints.  It aborts if the constraint set
contains one or more nonlinear constraints.  A nonlinear objective
function is acceptable.

MINOS(IIS) alters the model as it operates on it to isolate an IIS,
gradually destroying the original data by freeing columns and rows.  For
this reason, MINOS(IIS) terminates upon completion of the IIS isolation,
abandoning any MATMOD solution sequence that may be in progress.

It is possible that an LP may contain several IISs.  MINOS(IIS) will
find one IIS and stop.  It must be used repeatedly in a 
find-and-repair cycle until the LP is completely free of infeasibilities.

Using the guide codes, it is possible to protect constraints from
dropping during the IIS filtering process.  In this case, the output set
of constraints will be an infeasible set, but it is no longer possible
to guarantee that it is a minimal set (i.e.  an IIS).  Be careful when
using the guide codes.  In most cases there is no need to use the guide
codes at all:  an IIS will still be found and reported.

The MINOS(IIS) 5.2 routines conflict with certain of the crash options 
in MINOS 5.4, so at present MINOS(IIS) accepts only crash option 0 or 1.  
If crash option 3 or 4 is specified, it is overridden and reset to 1.

=====================
2. Running MINOS(IIS)
=====================

--------------------------
2.1 Input and Output Files
--------------------------

The usual MINOS input files are required:  the MPS and Specs
files.  As usual, MINOS expects these files to be named
MINOS.MPS and MINOS.SPC.  Parameters peculiar to MINOS(IIS) are 
also specified via the Specs file.  In addition, an optional 
input file defining search guide codes (named MINOS.GUI) can be
specified.

The MINOS(IIS) output is appended to the usual MINOS
output in the file MINOS.PRN.  If requested via a Specs file parameter,
a more easily parsed listing of the IIS is produced in a separate file
named MINOS.IIS.  This is used, for example by Harvey Greenberg's
ANALYZE system.

Batch files specific to the operating system are used to copy or
rename files appropriately to provide the MINOS.* input and output
files.  The DOS batch file for MINOS(IIS) version 5.2 is called
ver52.bat and it is used as follows:
   ver52 modelname
   e.g. "ver52 itest2" which expects to find itest2.mps and
	  itest2.spc (and possibly itest2.gui), and will return 
	  itest2.prn (and possibly itest2.iis).
The batch file will attempt to read a default .spc file if one is
not provided for the model.  The batch file copies the .mps and .spc 
files before calling MINOS(IIS), so the original files are safe from 
corruption.

----------------------------------
2.2 Infeasibility Analysis Options
----------------------------------

Infeasibility analysis options are specified in the Specs file.  
These are described below.  The default values are chosen in
each case to set up an algorithm which finds IISs with few rows (see
[Chinneck 1996b]).

IIS ON or IIS OFF.  Default: IIS ON.
Controls whether or not an IIS isolation is to be undertaken at all.
If IIS OFF is specified, then an IIS isolation is not
initiated, even if the problem is infeasible.

IIS PREPRINT.  No default.  
If this statement is present, then the usual MINOS output is 
generated before the IIS isolation is undertaken.  This is useful 
where the variable values or sensitivities for the infeasible problem 
are used for other purposes, such as in Harvey Greenberg's ANALYZE software.

IIS LOG.  No default.  
If this statement is present, then various logging messages are printed 
to the output file as the solution proceeds, and a final feasibility 
check is undertaken when the algorithm terminates.  Useful for debugging.

IIS FILE unit-number.   No default.  
If this statement is present, then the file MINOS.IIS attached to 
unit-number is generated, which contains an easily parsed listing of
the IIS plus a few lines of information about the solution method etc.
This is useful for interfacing MINOS(IIS) with other software,
such as Harvey Greenberg's ANALYZE.

IIS REVERSE or IIS FORWARD.  Default IIS REVERSE.  
Controls the direction of the deletion filter.  
FORWARD deletion filters the variables in order from 1 to n, i.e.
variable bounds followed by rows.  REVERSE deletion filters
the variables in order from n to 1, i.e. rows followed by variable
bounds.

IIS SENSITIVITY.  No default.  
If this statement is included, then the sensitivity filter is invoked 
at appropriate points in the algorithm.  If this statement is not 
present, then the sensitivity filter is never invoked during the IIS 
isolation.

IIS PROTECTION integer-value.  Default: IIS PROTECTION 2.  
This parameter selects from among the column protection
options.  "Column protection" means preventing the elimination of
column bounds, as far as possible, as the IIS isolation proceeds.
This is useful when trying to find IISs having few rows, which are
generally easier to interpret. The integer-values have these meanings:
  0 (or anything other than 1 or 2): no special column protection.
  1: column bounds are protected as much as possible; they
     can be eliminated only by a deletion test.
  2: columns are protected until all of the rows have been
     deletion tested, then the columns are deletion/sensitivity filtered
     (even if sensitivity filtering was not initially enabled).
Note that specifying a protection option supercedes certain other
analysis options; see Section 2.6 about the precedence order of the
options.

IIS GUIDECODE unit-number. No default.  
If this statment is present, then MINOS(IIS) expects to find IIS
guide codes in the file MINOS.GUI designated by unit-number.
A discussion of how to use the guide codes is included elsewhere
in this manual.

IIS ECHO.  No default.  
If this statement is present,
then the error messages generated while processing the guide codes
are included with the MINOS(IIS) output.  If this statement
is not present, then the error messages are suppressed.  Suppression
is sometimes desirable when wild-card characters are used in the
matching mask because voluminous `no-match' messages may be generated.

IIS ELASTIC.  No default.  
If this statement is included, an initial elastic filter is undertaken.  
Note that using the elastic filter supercedes certain other analysis
options; see Section 2.6 about the precedence order of the options.

IIS COVER.  No default.
If this statement is present, then MINOS(IIS) undertakes a heuristic
method to find a small-cardinality (hopefully minimum-cardinality)
set of constraints which define an IIS set cover.  Note that using
the set cover option supercedes certain other analysis options; see
Section 2.6 about the precedence order of the options.

-------------------------
2.3 Using the Guide Codes
-------------------------

The guide codes are optional, and are not needed at all in most
applications.  They are intended for use by expert MINOS(IIS)
users on mature models to help guide the search for the infeasibility
away from well-tested parts of the model and towards the more suspect
portions.  They also provide a tool for manipulation of the
infeasibility algorithms for research purposes.

Note carefully the provisions about the precedence ordering of the
analysis options in Section 2.6 before attempting to use guide 
codes.

The guide codes appear in the file MINOS.GUI and are fixed
format lines with the following format:

column 1:  Row or column designation (R or C).  R is for row
  (constraint) and C is for column (variable)

columns 3-10:  Row or column name.  The wildcard character * can
  replace any single character in the name.  For example, abc*oil matches
  abc1oil and abczoil, but does NOT match abc1gas, or abc1oils.

column 12:  Upper or lower bound designation (U or L).  U is for
  upper bound, L is for lower bound.  It doesn't matter which code is used
  for equality constraints:  the same action is applied to both bounds,
  regardless.

column 14: Guide code (integer 0-4).
   0: null action,
   1: relax the bound immediately,
   2: never relax the bound,
   3: encourage relaxation of the bound,
   4: discourage relaxation of the bound.

If the MINOS.GUI file has more than one line assigning
a guide code to a particular bound, then only the first guide code
assignment is accepted.

Guide codes 3 and 4 are most commonly used.  If guide code 1 is used,
then an extra feasibility test is carried out just after the indicated
bounds are dropped, to make certain that the model is still infeasible
before the IIS isolation algorithm begins.

Guide code 2 is intended for use in only very special circumstances
because of its effect on the integrity of the results.  If any
constraints were protected by code 2, then it is possible that the
output set reported is *not* an IIS:  a warning is generated in this
case and a final pass of the sensitivity filter checks the protected
constraints to see if they are droppable.  This added information is
reported, but there is still no guarantee that even if the droppable
constraints are removed that what remains is an IIS.  It is possible,
for example, that there are *two* IISs among the constraints
reported.

---------------------------------
2.3.1 An Example of Guided Search
---------------------------------

The second example in Chinneck and Dravnieks [1991] (the ITEST2 model)
is given below. Note that x3 does not appear in this set of constraints.

   1: -0.5x1 + x2 >= 0.5
   2:    2x1 - x2 >= 3
   3:    3x1 + x2 <= 6
   4:     x5      <= 2
   5:    3x4 - x5 <= 2
   6:     x4      >= 5
   7:     x1 + x5 <= 10
   8:     x1 + 2x2 + x4 <= 14
   9:     x2 + x4 >= 1
all variables are nonnegative.

There are two obvious IISs in this example: {1,2,3} and {4,5,6}.  
The IIS {1,2,3} is discovered by running MINOS(IIS) without any 
guide codes.  The IIS {4,5,6} is discovered by running MINOS(IIS) 
with the constraints for rows 1,2,3 encouraged to relax (code 3).

However, the surprising thing about this example is that there are
other, nonobvious IISs that are discovered by using various other
different combinations of guide codes.  For example, if we run the
problem with constraints 1 and 4 immediately relaxed (code 1) in an
attempt to remove both of the IISs, we discover a previously hidden
IIS: {x2>=0,2,5,6,7}.

Now, in an attempt to remove this IIS, we run the problem with
constraints 1 and 4 immediately relaxed, and with the nonnegativity
constraint on x2 removed.  This results in the IIS
{2,5,6,7,9}.  Now we add another guide code which immediately
relaxes constraint 2, and the result is yet another IIS: {x1>=0,5,6,7}.

----------------------------
2.4 Using the Elastic Filter
----------------------------

The elastic filter is very effective in finding IISs having few rows.
However, extra phantom columns and extra phantom elements must be
reserved beforehand for use in the elastic filter.  If this is not done
explicitly by the user, then 2m phantom columns and 4m phantom
elements are reserved automatically.  This is sometimes a gross
overestimate of the space needed, so if memory is a problem, then
request the exact number of phantom columns and elements needed via the
Specs file rather than using the default numbers.  How to determine the
exact number needed is described next.

It is necessary to know the number of "normal", "fixed", and 
"bounded" rows to make the space calculations.  "Normal" rows are
rows having a single upper or lower bound.  "Fixed" rows are
equality constraints.  "Bounded" rows have distinct and finite upper
and lower bounds.  MINOS provides counts of these items as part
of the standard output, so you may wish to run MINOS once to
get an accurate count of the number of rows in each category in
order to calculate the amount of extra resources to request.

MINOS lists the number of rows and columns in a format such as
shown in Figure 1 for the ITEST2 problem:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Figure 1: Matrix statistics returned by MINOS for the ITEST2 model.
											 
 Matrix statistics
 -----------------
		    Total      Normal        Free       Fixed     Bounded
 Rows             10           9           1           0           0
 Columns          13           4           0           9           0

 No. of matrix elements                   35     Density      26.923

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The number of phantom columns needed is:  {(normal rows) + 2*[(fixed
rows) + (bounded rows)]} and the number of phantom elements needed is
2*(number of phantom columns).

These are requested via the Specs file.  The entries are of this
form (for the matrix statistics given above):
     PHANTOM COLUMNS 9
     PHANTOM ELEMENTS 18

Remember that space for the phantom columns and elements must be included
within the overall COLUMNS and ELEMENTS requests in the Specs file.  In
the example above, the Specs file should then have these lines:
     IIS ELASTIC
     ROWS 10
     COLUMNS 21         * (i.e. 13 + 9 phantom)
     ELEMENTS 53        * (i.e. 35 + 18 phantom)
     PHANTOM COLUMNS 9
     PHANTOM ELEMENTS 18

If the ROWS or COLUMNS limit is too small to accommodate the
total of the model columns and the PHANTOM COLUMNS request or the
model elements and the PHANTOM ELEMENTS request, MINOS
5.4 may go into a loop, repeatedly rereading the files and attempting
to find enough space.  Manual intervention may be required.  If
insufficient phantom rows or columns are requested to permit the elastic
filter to proceed, then MINOS(IIS) prints a message and the
elastic filter is abandoned, but IIS isolation proceeds by other
methods.

Note that the elastic filter takes precedence over certain other
analysis options; see Section 2.6.

--------------------------
2.5 Finding IIS Set Covers
--------------------------

Specifying IIS COVER in the specs file initiates a heuristic 
algorithm for finding a small-cardinality IIS set cover.  The
heuristic algorithm makes extensive use of elastic filtering,
so that when IIS COVER is specified, provision must also be
made for phantom columns and phantom elements in exactly the
same manner as for Elastic Filtering (see Section 2.4).

Note that the set covering heuristic takes precedence over certain 
other analysis options; see Section 2.6.

-----------------------------------------------
2.6 Precedence Ordering of the Analysis Options
-----------------------------------------------

The various infeasibility analysis options have a precedence
ordering. For example, if IIS COVER is specified, then the column 
protection and guide code options are disregarded.  Items higher 
in the following list take precedence over those lower in the list.
	   1. IIS set cover identification
	   2. the elastic filter
	   3. column protection > 0
	   4. guide codes
	   5. all other options

If you wish to use the guide codes, you must not request the
identification of an IIS set cover, you must not specify elastic 
filtering, and you must turn the column protection options off.


==========
3. Example
==========

A complete example is given below, including the MPS, Specs, output, and
IIS files for the ITEST2 example.  The equations for this problem also
appear in the tutorial on guiding the IIS search.  Note that there is no
X3 variable in this problem.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Figure 2: MPS file for ITEST2 problem.

NAME          PAPER2
ROWS
 G  ROW1
 G  ROW2
 L  ROW3
 L  ROW4
 L  ROW5
 G  ROW6
 L  ROW7
 L  ROW8
 G  ROW9
 N  OBJ10
COLUMNS
    X1        ROW1      -0.5           ROW2      2.0
    X1        ROW3      3.0            ROW7      1.0
    X1        ROW8      1.0
    X2        ROW1      1.0            ROW2      -1.0
    X2        ROW3      1.0            ROW8      2.0
    X2        ROW9      1.0
    X4        ROW5      3.0            ROW6      1.0
    X4        ROW8      1.0            ROW9      1.0
    X5        ROW4      1.0            ROW5      -1.0
    X5        ROW7      1.0
RHS
    RHS1      ROW1      0.5            ROW2      3.0
    RHS1      ROW3      6.0            ROW4      2.0
    RHS1      ROW5      2.0            ROW6      5.0
    RHS1      ROW7      10.0           ROW8      14.0
    RHS1      ROW9      1.0
ENDATA
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Figure 3: SPC file for ITEST2 problem.

BEGIN PAPER2
MINIMIZE
OBJECTIVE  = OBJ10
ROWS       50
COLUMNS    150
ELEMENTS   500
MPS FILE   11
IIS LOG
IIS FILE 17
IIS ELASTIC
END  PAPER2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Figure 4: MINOS.PRN output from MINOS(IIS) for ITEST2 problem.  
	    Only output relevant to the IIS isolation is shown.

	   ==============================
	   M I N O S    5.4    (Dec 1992)  
	   ==============================
				.
				.
 IIS: Crash option reset to 1 for possible IIS search.
				.
				.
 EXIT -- the problem is infeasible

 PAPER2  
 No. of iterations                   4   Objective value      0.0000000000E+00
 No. of infeasibilities              2   Sum of infeas        1.6301095630E+00
 No. of degenerate steps             0   Percentage                       0.00

 ----------------------------------------------------------------------
 |                 IISLOC version 5.2 ,   July  1996                  |
 |       John W. Chinneck, Carleton University, Ottawa, Canada        |
 |       tel: (613) 520-5733   email: chinneck@sce.carleton.ca        |
 ----------------------------------------------------------------------

     2 bounds cover the IIS sets.

 IIS LOG > Initial infeasible variables:
 row variable for ROW2    
 row variable for ROW6    

 -------------------------- Messages Log ----------------------------
 IIS LOG > Beginning elastic iteration     1
 IIS LOG > Elastic objective value:  0.446667E+01
 IIS LOG > Row    1 de-elasticized.
 IIS LOG > Row    6 de-elasticized.
 IIS LOG > Beginning elastic iteration     2
 IIS LOG > Elastic objective value:  0.121429E+02
 IIS LOG > Row    2 de-elasticized.
 IIS LOG > Row    5 de-elasticized.
 IIS LOG > Beginning elastic iteration     3
 IIS LOG > Elastic objective value:  0.190000E+02
 IIS LOG > Row    3 de-elasticized.
 IIS LOG > Row    4 de-elasticized.
 IIS LOG > Row    7 de-elasticized.
 IIS LOG > Beginning elastic iteration     4
 IIS LOG > Elastic objective value:  0.190000E+02

 -------------------------- Messages Log ----------------------------
 IIS LOG > row ROW7     upper bound deleted: infeasible       
 IIS LOG > row ROW6     lower bound deleted: infeasible       
 IIS LOG > row ROW5     upper bound deleted: infeasible       
 IIS LOG > row ROW4     upper bound deleted: infeasible       
 IIS LOG > row ROW3     upper bound deleted: feasible         
 IIS LOG > row ROW2     lower bound deleted: feasible         
 IIS LOG > row ROW1     lower bound deleted: feasible         
 IIS LOG > col X5       lower bound deleted: infeasible       

 IIS LOG > Model is infeasible at final check

 --------------------------------------------------------------------
 An IIS (Irreducibly Inconsistent Subsystem) causing infeasibility
 in the constraint set has been found.

 ---------------- Variable (column) bounds in the IIS ----------------

 ----------------- Constraint (row) bounds in the IIS ----------------
 lower bound on ROW1    
 lower bound on ROW2    
 upper bound on ROW3    

 ---------------------------- IIS SUMMARY ---------------------------
				 variables (columns)     constraints (rows)
 lower bounds (>=):                0                       2
 upper bounds (<=):                0                       1
 fixed values (=):                 0                       0
	totals:                      0                       3
    Grand Total:                               3

 ---------------------------- STATISTICS ----------------------------
							 bounds
 finite bounds in MINOS revised problem:     13
   finite row bounds:                         9
   finite column bounds:                      4
 relaxed immediately:                         0
 in the IIS:                                  3
 eliminated by elastic filter:                2
 eliminated by sensitivity filter:            3
 eliminated by deletion filter:               5
 eliminated by reciprocal filter:             0

 number of elastic filter iterations:         3
 number of deletion filter iterations:        8
 number of sensitivity filter passes:         1

 number of rows de-elasticized:               7

 ------------------------- End of MINOS(IIS) --------------------------
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Figure 5: MINOS.IIS output file for the ITEST2 problem.

PROBLEM NAME:
SPECIFICATIONS:
IIS METHOD: ELAS, REV DEL, COL PROT 2.
BEGIN IIS
BEGIN COLUMNS
END COLUMNS
BEGIN ROWS
ROW1     lower bound
ROW2     lower bound
ROW3     upper bound
END ROWS
END IIS
NUMBER OF COLUMNS IN IIS:     0
NUMBER OF ROWS IN IIS:     3
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---------------------------
3.1 Interpreting the Output
---------------------------

The IIS report is attached to the usual MINOS output, as shown
in Fig. 4.  Note that the crash option is overridden for the
purposes of IIS isolation.  Crash option 3 or 4 of MINOS 5.4
conflicts with the deletion filter, and crash option 3 is the
MINOS default.

After MINOS reports infeasibility, a statement indicating the
number of violated bounds in the initial phase 1 solution is generated.
Note that the usual listing of variable values etc. has been suppressed
by default in this example.  Because the IIS logging function is turned
on in Fig. 3, the names of the variables violating their bounds are
also given.

The IIS log follows next.  Information on the progress of the elastic
filter is printed, then a listing of the deletion filter tests and
outcomes.  MINOS(IIS) 5.2 logs no information about the
sensitivity or reciprocal filters.  The logging function also activates
the final feasibility check, which is useful when experimenting with new
analysis algorithms.

A listing of the IIS is next, followed by various statistics on the IIS
isolation procedure.

Note that the PROBLEM NAME and SPECIFICATIONS lines in the
IIS output file in Fig. 5 are blank.  These are reserved for future use.


====================
4. Notes on Practice
====================

A single error causing infeasibility is often reflected in numerous
different IISs.  Experience shows that the IIS with the fewest rows is
the easiest to interpret.  Chinneck [1996b] examines which methods
return IISs with the fewest rows.  The best method is the elastic filter
teamed with the reverse deletion/sensitivity filter with column
protection option 2.  The reverse deletion filter with column protection
option 2 gives results that are almost as good, but does not require the
phantom columns and elements needed by the elastic filter.  This is the
default method set up by MINOS(IIS) 5.2.


====================
5. Programming Notes
====================

MINOS(IIS) 5.2 makes use of several alternative versions
of MINOS 5.4 routines that were prepared by Michael
Saunders at Stanford University.  These are:

File MI20AMAT.FOR (alternative name IMI20AMA.FOR).  Subroutine
  M2CORE grabs space in the Z array for the IIS variables.

File MI30SPEC.FOR (alternative name IMI30SPE.FOR).  Subroutine
  M3DFLT sets up the default IIS parameter values; subroutine M3KEY parses
  the IIS parameters in the Specs file.

File MI50LP.FOR (alternative name IMI50LP.FOR).  Subroutine
  M5SOLV, under the control of IPARM(6), can return immediately upon
  recognition of feasibility.

The file MI10MACH has been altered by John Chinneck at Carleton
University to interface with the IIS subroutines.  All changes are
in the MISOLV subroutine, and involve an override of the crash
option setting if necessary, and the insertion of a call to IISLOC,
the main IIS localizing subroutine.

These alternative MINOS 5.4 files must be compiled and
linked with the file IIS, created by John Chinneck at Carleton
University, which contains all of the MINOS(IIS) 5.2 routines.


=====================
6. Version Update Log
=====================

Omitted.

=============
7. 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, pp. 157-168.

J.W. Chinneck (1994).  "MINOS(IIS):  Infeasibility
Analysis Using MINOS", Computers and Operations Research,
vol. 21, no. 1, pp. 1-9.

J.W. Chinneck (1996a).  "Localizing and Diagnosing
Infeasibilities in Networks", INFORMS Journal on Computing,
vol. 8, no. 1, pp. 55-62.

J.W. Chinneck (1996b).  "Finding A Useful Subset of
Constraints for Analysis in an Infeasible Linear Program", 
INFORMS Journal on Computing, to appear.

J.W. Chinneck (1996c). "Computer Codes for the Analysis of Infeasible
Linear Programs", Journal of the Operational Research Society,
vol. 47, pp. 61-72.

J.W. Chinneck (1996d). "An Effective Polynomial-Time Heuristic for
the Minimum-Cardinality IIS Set-Covering Problem", Annals of
Mathematics and Artificial Intelligence, vol. 17, pp. 127-144.

B.A. Murtagh and M.A. Saunders (1993). "MINOS 5.4 User's Guide
(preliminary)", Technical Report SOL 83-20R, Department of 
Operations Research, Stanford University.
