(635f) Multi-Parametric Linear Programming with Global Uncertainty

Multi-parametric programming (mp-P) has proven to be an invaluable tool for optimisation problems liable to uncertainty ^[1]. Uncertainty is an inherent feature in all mathematical models either because of fluctuations in extrinsic data such as demand of products, prices, availability of raw material etc. or intrinsic parameters such as stoichiometric coefficients, transition times in a scheduling problem etc.^[2] While the first type of uncertainty typically results in variations either in the objective functionâ??s coefficients (OFC) or on the right hand side (RHS) of the constraints of the problem the latter mostly appears as left hand side (LHS) uncertainty as varying parameters in the technology matrix. When uncertain parameters are present in the entries of the technology matrix the resulting multi-parametric programming problem is in general non-convex and hard to solve. To address this issue, hybrid and/or approximate solution strategies^[3,4] and inversion of perturbed matrices based approaches^[6] have been proposed. Recently, symbolic manipulation software has gained a considerable amount of attention and platforms like Mathematica^© have created their own environments that allow users to efficiently perform symbolic calculations to provide exact solutions for certain classes of problems. The use of symbolic manipulation software for the solution of optimization problems was studied by Dua (2015) ^[5] where an algorithm for Mixed Integer Polynomial problems was proposed.

In this work, a new general framework is introduced for the exact solution of multi-parametric linear programming (mp-LP) problems with varying uncertain parameters in the OFC, the RHS and the LHS simultaneously. The proposed methodology is based on the analytical solution of the system of equations derived from the Karush-Kuhn-Tucker (KKT) conditions for general linear programming (LP) problems using symbolic manipulation software. Key contribution of this work is the ability of the proposed methodology to efficiently handle the LHS uncertainty by computing exactly the corresponding non-convex critical regions (CRs). The algorithm has been tested for a number of case studies which further underlines its advantages when compared with existing approaches.

References

1. Pistikopoulos, E. N., Georgiadis, M. C., & Dua, V. (2007). Multi-parametric programming. Volume I. Weinheim: WileyVCH.
2. Grossmann, I. E., Apap, R. M., Calfa, B. A., Garcia-Herreros, P., & Zhang, Q. (2015) â??Recent Advances in Mathematical Programming Techniques for the Optimization of Process Systems under Uncertaintyâ?. 12^th International Symposium on Process Systems Engineering and 25^th European Symposium on Computer Aided Process Engineering (Vol. 37, p. 1). Elsevier.
3. Li, Z., & Ierapetritou, M. G. (2007). A new methodology for the general multiparametric mixed-integer linear programming (MILP) problems. Industrial & engineering chemistry research, 46(15), 5141-5151.
4. Wittmann-Hohlbein, M., & Pistikopoulos, E. N. (2013). On the global solution of multi-parametric mixed integer linear programming problems. Journal of Global Optimization, 57(1), 51-73.
5. Dua, V. (2015). Mixed integer polynomial programming. Computers & Chemical Engineering, 72, 387-394.
6. Khalilpour, R., & Karimi, I. A. (2014). Parametric optimization with uncertainty on the left hand side of linear programs. Computers & Chemical Engineering, 60, 31-40.