Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.

  

A Geometric Algorithm for Multi-Parametric Linear Programming

Author(s):

F. Borrelli, A. Bemporad, M. Morari
Conference/Journal:

vol. AUT00-06
Abstract:

We propose a novel algorithm for solving multi-parametric linear programming (mp-LP) problems. Rather than visiting different bases of the associated LP tableau, we follow a geometric approach based on the direct exploration of the parameter space. The resulting algorithm has computational advantages, namely the simplicity of its implementation in a recursive form, and the possibility to look for parametric solutions within a given polyhedral region of the parameter-space without solving the problem globally. Other features include: an initial step which computes the minimal affine subspace containing all feasible parameters, primal and dual degeneracy handling, and the possibility of using a polynomial time LP solver. Illustrative examples will describe the approach throughout the paper.

Year:

2000
Type of Publication:

(04)Technical Report
Supervisor:



No Files for download available.
% Autogenerated BibTeX entry
@TechReport { BorBem:2000:IFA_1805,
    author={F. Borrelli and A. Bemporad and M. Morari},
    title={{A Geometric Algorithm for Multi-Parametric Linear
	  Programming}},
    institution={},
    year={2000},
    number={},
    address={},
    month=mar,
    url={http://control.ee.ethz.ch/index.cgi?page=publications;action=details;id=1805}
}
Permanent link