The goal of this paper is to develop some computational experience and test the practical relevance of the theory of condition numbers C(d) for linear optimization, as applied to problem instances that one might encounter in practice. We used the NETLIB suite of linear optimization problems as a test bed for condition number computation and analysis. Our computational results indicate that 72% of the NETLIB suite problem instances are ill-conditioned. However, after pre-processing heuristics are applied, only 19% of the post-processed problem instances are ill-conditioned, and log C(d) of the finitely-conditioned post-processed problems is fairly nicely distributed. We also show that the number of IPM iterations needed to solve the problems in the NETLIB suite varies roughly linearly (and monotonically) with log C(d) of the post-processed problem instances. Empirical evidence yields a positive linear relationship between IPM iterations and log C(d) for the post-processed problem instances, significant at the 95% confidence level. Furthermore, 42% of the variation in IPM iterations among the NETLIB suite problem instances is accounted for by log C(d) of the problem instances after pre-processin
Download Info
To download:
If you experience problems downloading a file, check if you have the
proper application to
view it first. Information about this may be contained
in the File-Format links below. In case of further problems read
the IDEAS help
page. Note that these files are not on the IDEAS
site. Please be patient as the files may be large.
Publisher Info
Paper provided by Massachusetts Institute of Technology (MIT), Sloan School of Management in its series Working papers with number
4337-02.
Length: Date of creation: 25 Sep 2003 Date of revision: Handle: RePEc:mit:sloanp:3547
Contact details of provider: Postal: MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA Phone: 617-253-2659 Web page: http://mitsloan.mit.edu/ More information through EDIRC
Order Information: Postal: MASSACHUSETTS INSTITUTE OF TECHNOLOGY (MIT), SLOAN SCHOOL OF MANAGEMENT, 50 MEMORIAL DRIVE CAMBRIDGE MASSACHUSETTS 02142 USA
For technical questions regarding this item, or to correct its listing, contact: (Christian Zimmermann).
References listed on IDEAS Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
Did you know? Citation analysis on IDEAS includes online papers that are freely accessible and whose text could be automatically analyzed, currently about 210000 papers.