On Polyhedral Projection and Parametric Programming

C. N. Jones (), E. C. Kerrigan and J. M. Maciejowski
Additional contact information
C. N. Jones: ETH Zurich
E. C. Kerrigan: Imperial College London
J. M. Maciejowski: University of Cambridge

Journal of Optimization Theory and Applications, 2008, vol. 138, issue 2, No 5, 207-220

Abstract: Abstract 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.

Keywords: Parametric programming; Polyhedral projection; Computational geometry (search for similar items in EconPapers)
Date: 2008
References: View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10957-008-9384-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:138:y:2008:i:2:d:10.1007_s10957-008-9384-4

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-008-9384-4

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().