Ill-Conditionedness and Interior-Point Methods

Asic, M.D., Kovacevic-Vujcic, V.V.

In this paper we construct a family of degenerate linear programming problems which cause difficulties to various IPM codes, such as HOPDM, PCx, etc. The smallest example has 7 equations and inequalities, 20 variables while coefficients are integers with at most 4 digits. A theoretical explanation is offered and a possible way out is outlined.

Technical Report, Laboratory for OR, February 1998, Faculty of Organizational Sciences, University of Belgrade, Jove Ilica 154, 11040 Belgrade, Yugoslavia