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