This thesis focuses on several aspects of data perturbation for Linear Programming. Classical questions of degeneracy and post-optimal analysis are given a unified presentation, in a view of new interior point methods of linear programming. The performance of these methods is compared to the simplex algorithm; interior point methods are shown to alleviate some difficulties of representation and solution of linear programs. An affine scaling algorithm is implemented in conjunction with a simple rounding heuristic to asses the benefit of interior point trajectories to provide approximate solutions of linear integer programming.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/6709 |
| Date | January 1994 |
| Creators | Karamalis, Constantinos. |
| Contributors | Thizy, Jean-Michel, |
| Publisher | University of Ottawa (Canada) |
| Source Sets | Université d’Ottawa |
| Detected Language | English |
| Type | Thesis |
| Format | 198 p. |
Page generated in 0.0016 seconds