MINOS(IIS): A Software Tool for Analyzing Infeasible Linear Programs

MINOS(IIS) is an LP solver which incorporates special routines for analyzing infeasible linear programs. It uses two main tools for infeasibility analysis:

• The identification of an Irreducible Infeasible Subset (IIS) of constraints. An IIS is usually a very small subset of the complete set of constraints defining 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 diagnostic effort on a small portion of the original model. Special features include the ability to guide the IIS search, and heuristics which help to find IISs having few row constraints.

• The heuristic identification of the smallest number of constraints to remove such that the remaining constraints form a feasible set. This is also known as a minimum-cardinality IIS set cover because the set of constraints removed must contain at least one member of every IIS. Finding the minimum-cardinality IIS set cover also gives you the maximum-cardinality feasible subset of constraints. This is an NP-complete problem, but the heuristic has been 100% accurate over a test set, though this behaviour cannot be guaranteed in general.

MINOS(IIS) is a combination of two codes: the linear programming routines from the MINOS 5.4 solver developed at Stanford University by Bruce Murtagh and Michael Saunders at Stanford University, and the IISLOC infeasibility analysis routines developed by John Chinneck at the Department of Systems and Computer Engineering at Carleton University .

MINOS(IIS) allows the user to select various combinations of the basic IIS routines, including deletion filtering, sensitivity filtering, elastic filtering, IIS set-covering, column protection, constraint prioritizing via guide codes, etc. A complete trace of algorithm activity is also available on user request.

For further information on infeasibility analysis of mathematical programs see the author's list of publications .

Obtaining a Student/Demo Copy of MINOS(IIS)

A student/demo edition of MINOS(IIS) version 5.2 is available for download. It is distributed as a DOS executable file, and has limits on the maximum model size as follows: no more than 300 constraints, no more than 300 variables. A user's manual is included. Note that is an old 32-bit windows executable and may not function on a 64-bit system.

As you should expect with any free software, this student/demo version of MINOS(IIS) is provided without warranty of any kind. All risks are assumed by you, the user.

You can download the software here. The file has been compressed using the 7-Zip compression utility. After decompression you will have the following files:

• man52sm.txt: This is the user's manual. Read this first to learn how to use the program.
• ver52sm.bat: This is a batch file which manages the various files needed by MINOS(IIS). See the user's manual for details.
• inf52sm.exe: The actual DOS executable for MINOS(IIS). It is called by the batch file ver52sm.bat.
• itest6.mps: The MPS file for a small test model.
• Itest6.spc: The specs file for a small test model.

Contact

For further information, or to inquire about a professional edition of MINOS(IIS) contact John W. Chinneck at Carleton University (email: chinneck@sce.carleton.ca). To acquire a professional edition, you will first need a license for MINOS 5.4, available from Stanford Business Software.

To Reference MINOS(IIS)

If you need to reference MINOS(IIS) in research papers, technical reports, etc., the suggested reference is:

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

Other possible references can be seen here .

Back to author's homepage .