Читать книгу Multi-parametric Optimization and Control - Efstratios N. Pistikopoulos - Страница 77

The idea to consider the variation of a parameter in an LP problem was reportedly first put forth in the unpublished master thesis by William Orchard‐Hays in 1952, as reported in [14], where the variation of the right‐hand side of the constraints was considered:

(2.21)

Subsequently, several researchers proposed algorithms for the treatment of the single parameter case [15–20], but it was not until 1972 when the seminal paper by Gal and Nedoma described for the first time a rigorous strategy for the general solution of mp‐LP problems of type (2.2) based on the connected‐graph theorem [2]. All these developments were captured in the excellent textbook by Gal and Davis from 1979 [21], for which a second edition appeared in 1995 [22].

The algorithm from [2] remained the state‐of‐the‐art for over 25 years (see, e.g. [23,24]), until geometrical algorithms for general mp‐LP problems were developed starting in 2000,5 with the application of multi‐parametric programming to model‐predictive control [26,27]. Although the initial focus was put on mp‐QP problems, quickly publications concerning combination of model predictive control and mp‐LP problems were put forth [28–31], many of which were captured in this excellent review [32]. This new string of developments resulted in a deeper interest in the theoretical properties of mp‐LP problems, specifically in the case of degeneracy (see section 2.2), as well as the question of the presence of parameters in the left‐hand side of the constraints, i.e.

(2.22a)

(2.22b)

where algorithms based on McCormick relaxations [33,34], as well as exact algorithms for the single parameter case [35] have been presented.⁶