On polyhedral projection and parametric programming
Jones C.N. and Kerrigan E.C. and Maciejowski J.M.
Journal of Optimization Theory and Applications, Volume 138, Pages 207-220, 2008Abstract
This paper brings together two fundamental topics: polyhedral projection and parametric linear programming. First, it is shown that, given a parametric linear program (PLP), a polyhedron exists whose projection provides the solution to the PLP. Second, the converse is tackled and it is shown how to formulate a PLP whose solution is the projection of an appropriately defined polyhedron described as the intersection of a finite number of halfspaces. The input to one operation can be converted to an input of the other operation and the resulting output can be converted back to the desired form in polynomial time—this implies that algorithms for computing projections or methods for solving parametric linear programs can be applied to either problem class.
Pre-Prints
[PDF]
BibTex Entry
- @Article{,
- author = {Jones C.N. and Kerrigan E.C. and Maciejowski J.M.},
- journal = {Journal of Optimization Theory and Applications},
- title = {On polyhedral projection and parametric programming},
- year = {2008},
- pages = {207-220},
- volume = {138}
- }
|
![[Dept of Engineering]](http://www.eng.cam.ac.uk/images/house_style/engban-s.gif)
