From IPM to simplex basis
Jeroen J. Dirks
solutions.
What are the best sources on this subject ?
--
Jeroen J. Dirks
Student Technical Mathematics
Delft Univerity of Technology
J.J....@TWI.TUDELFT.NL
Sarah Gwyneth Owens
: I am looking for information on Basis recovery from interior point
: solutions.
: What are the best sources on this subject ?
The one I know of is:
| AUTHOR: Bixby, R. E.; Saltzman, M. J.
| TITLE: Recovering an optimal LP basis from an interior point solution
|JOURNAL NAME: Operations research letters : a journal of the Operations
| Research Society of America ...
| VOL, ISSUE: Volume 15, Number 4
| PAGES: 169
| YEAR: 1994
| TYPE: Article
| ISSN: 0167-6377
Note that Bixby is part of CPLEX Optimization, so you can be sure that
this work has been partially implemented in a commercial code.
(Irv Lustig may correct me if I am wrong :)
--
S. Gwyneth Owens | "A mathematician is a device for
Rice University | for turning coffee into theorems"
Houston, TX | -- P. Erdos
http://chico.rice.edu/~gwyneth/ |
Irv Lustig
I guess I have to do some correcting :.)
What's in CPLEX is based upon a method of Megiddo, described in the paper
@article{int:Megiddo9,
author = "N. Megiddo",
title = "On finding primal-- and dual--optimal bases",
journal = "ORSA Journal on Computing",
volume = "3",
year = "1991",
pages = "63--65"
}
Our experiments on lots of real-world problems indicated that this method
was far superior to the method described in the Bixby-Saltzman paper,
especially on problems with lots of primal degeneracy (like airline
crew scheduling, for example). We started to write a paper on the
implementation, but then I left academia, and the paper never got finished.
It turns out that NETLIB is just not interesting for analyzing the
crossover problem, and you have to have a strong implementation of
the dual simplex method in order to get the best performance out
of that algorithm.
Another paper that I have recently seen describes an implementation of an
algorithm similar to Megiddo's algorithm with some modifications to it,
and other ideas. The reference is:
Erling D. Andersen and Yinyu Ye, "Combining interior-point and pivoting
algorithms for linear programming"
There's no tech. report number that I have for the above paper. The first
author's e-mail address is e...@busieco.ou.dk and the second author's
e-mail address is bbu...@vaxa.weeg.uiowa.edu .
-Irv Lustig
Director of Numerical Optimization
CPLEX Optimization, Inc.
i...@dizzy.cplex.com