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