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.
fulltext.pdf
Publisher's version
restricted
443.88 KB
Adobe PDF
1d57444cbdb3e2c95431bffbc48ef1fb
publication_2450.pdf
Preprint
openaccess
175.03 KB
Adobe PDF
7cd66cb8d167ca6f8222bda7337fd149