**February 11, 2002**

Olivier Guieu assembled most of the infeasible mixed-integer linear programming problems collected here. Many were created by modifying existing MIP problems by adding a constraint that is parallel to the objective function, but that has an orientation and right-hand side value that makes the MIP LP-feasible, but MIP-infeasible. MIPs that are LP-infeasible are easily analyzed by LP analysis tools, so it is only interesting if the model is LP-feasible but MIP-infeasible.

Two
of the models have original MIP-infeasibility that was not artificially
introduced by adding an objective-parallel constraint: *dell, *provided by Robert Dell of the Naval Postgraduate School, and
*p0201i,* provided by Ed Klotz of CPLEX
Optimization Inc. The source of the
infeasibility is not known for these two problems.

You can find more details in the following publications:

O. Guieu and J.W. Chinneck (1999), "Analyzing
Infeasible Mixed-Integer and Integer Linear Programs", *INFORMS Journal
on Computing*, vol. 11, no. 1, pp. 63-77.

O. Guieu (1995), **Analyzing Infeasible
Mixed-Integer and Integer Linear Programs**, M.Sc. thesis, Systems and
Computer Engineering, Carleton University, Ottawa, Canada.

**January 10, 2005**

Ed Klotz of Ilog contributed the *jjliu_clique* model. This is an MPS format replacement for the
identical model in LP format named *klotz1.lp* and posted last week. *klotz1.lp*
has now been removed.

*jjliu_clique* arises in the context of finding the optimal register
allocations in compilers: the infeasibility is original. For further information see: K. Wilken, J.
Liu, and M. Heffernan, *Optimal instruction scheduling using integer
programming* in Proceedings of ACM SIGPLAN 2000 Conference on Programming
Language Design and Implementation, pages 121-133, Vancouver, Canada, 2000.

John W. Chinneck

Systems and Computer Engineering

Carleton University

Ottawa, Canada