(130b) A Novel Geometric Based Algorithm to Solve Multiparametric Programming Problems

Multiparametric programming (mpP) is a technique that develops explicit maps of solutions to optimization problems comprising unrealized and bounded parameters. Advancements in mpP have led to “MPC-on-a-chip” technology [1], global solutions to certain classes of bi-level optimization problems [2], and a procedure for integrated multi-scale decision making in process systems engineering [3], amongst others. However, multiparametric programming for large scale applications is still prohibitive due to the combinatorial nature of the active constraints. Current algorithms suffer from the curse of dimensionality arising from an increase in the number of optimization variables, constraints, and parameters. Improving the performance of mpP problems, primarily linear (mpLP), mixed integer linear (mpMILP), and quadratic (mpQP) is still an open question in the literature [4,5].

In this work, we propose a parametric space exploration based algorithm to address mpP limitations with increasing number of optimization variables and constraints. The algorithm exploits key properties of mpP problems where (i) critical regions are convex, (ii) active sets within a critical region remain identical, and (iii) optimization variables are affine functions of the parameters. Exploring the parametric space follows an iterative procedure of vertex identification based on properties (i) and (ii), followed by identifying critical region boundaries based on (i), and determining the exact expressions of the optimization variables as a function of the parameters based on (iii). The proposed algorithm effectively handles mpP problems with a larger number of optimization variables and constraints, while still scaling exponentially with the number of parameters. The applicability of the algorithm is demonstrated through a computational study of various mpP problem sizes and classes (mpLP, mpMILP, and mpQP), and compared against existing software [6,7].

References

[1] Pistikopoulos, E. N. Perspectives in multiparametric programming and explicit model predictive control. AIChE Journal 2009, 55 (8), 1918-1925.

[2] Avraamidou, S.; Pistikopoulos, E. N. A novel algorithm for the global solution of mixed-integer bi-level multi-follower problems - Application on the problem of Planning and Scheduling integration. European Control Conference (ECC 2018); 2018; Accepted manuscript.

[3] Burnak, B.; Katz, J.; Diangelakis, N. A.; Pistikopoulos, E. N. Simultaneous Process Scheduling and Control: A Multiparametric Programming Based Approach. Industrial & Engineering Chemistry Research 2018, 57 (11), 3963-3976.

[4] Oberdieck, R.; Diangelakis, N. A.; Pistikopoulos, E. N. Explicit Model Predictive Control: A connected-graph approach. Automatica 2017, 76, 103-112.

[5] Ahmadi-Moshkenani, P.; Johanses, T.A.; Olaru, S. Combinatorial Approach towards Multi-Parametric Quadratic Programming based on Characterizing Adjacent Critical Regions. IEEE Transactions on Automatic Control, Institute of Electrical and Electronics Engineers, In press.

[6] Oberdieck, R.; Diangelakis, N. A.; Papathanasiou, M. M.; Nascu, I.; Pistikopoulos, E. N. POP - Parametric Optimization Toolbox. Industrial & Engineering Chemistry Research 2016, 55 (33), 8979-8991.

[7] M. Herceg, M. Kvasnica, C.N. Jones, and M. Morari. Multi-Parametric Toolbox 3.0. In Proc. of the European Control Conference, pages 502–510, Zurich, Switzerland, July 17–19 2013.