On Polyhedral Projection and Parametric Programming |
| |
Authors: | C N Jones E C Kerrigan J M Maciejowski |
| |
Institution: | (1) Automatic Control Laboratory, ETH Zurich, Physikstrasse 3, Zurich, Switzerland;(2) Department of Aeronautics and Department of Electrical and Electronic Engineering, Imperial College London, Exhibition Road, London, SW7 2AZ, UK;(3) Department of Engineering, University of Cambridge, Trumpington Street, Cambridge, CB2 1PZ, UK |
| |
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.
E.C. Kerrigan’s research was supported in part by the Royal Academy of Engineering, UK. |
| |
Keywords: | Parametric programming Polyhedral projection Computational geometry |
本文献已被 SpringerLink 等数据库收录! |
|