On Polyhedral Projection and Parametric Programming

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 timethis implies that algorithms for computing projections or methods for solving parametric linear programs can be applied to either problem class


Published in:
Journal of Optimization Theory and Applications, 138, 2, 207-220
Year:
2008
ISSN:
1573-2878
Keywords:
Laboratories:


Note: The status of this file is: EPFL only


 Record created 2011-03-14, last modified 2018-01-28

External link:
Download fulltext
n/a
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)