Primal-Dual Enumeration for Multiparametric Linear Programming

Optimal control problems for constrained linear systems with a linear cost can be posed as multiparametric linear programs (pLPs) and solved explicitly offline. Several algorithms have recently been proposed in the literature that solve these pLPs in a fairly efficient manner, all of which have as a base operation the computation and removal of redundant constraints. For many problems, it is this redundancy elimination that requires the vast majority of the computation time. This paper introduces a new solution technique for multiparametric linear programs based on the primal–dual paradigm. The proposed approach reposes the problem as the vertex enumeration of a linearly transformed polytope and then simultaneously computes both its vertex and halfspace representations. Exploitation of the halfspace representation allows, for smaller problems, a very significant reduction in the number of redundancy elimination operations required, resulting in many cases in a much faster algorithm.


Editor(s):
Iglesias, Andrés
Takayama, Nobuki
Published in:
Mathematical Software - ICMS 2006, 248-259
Year:
2006
Publisher:
Berlin, Heidelberg, Springer Berlin Heidelberg
ISBN:
978-3-540-38084-9
Laboratories:


Note: The status of this file is: EPFL only


 Record created 2011-10-24, last modified 2018-01-28

Rate this document:

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