(200e) Advances In Multi-Parametric Mixed Integer Linear Programming

The presence of uncertainty in mixed integer linear programming (MILP) models employed in widespread application fields, including planning/scheduling, process synthesis and hybrid control, significantly increases the complexity and computational effort in retrieving optimal solutions. A particular difficulty arises when uncertainty is simultaneously present in the coefficients of the objective function (OFC), the constraint matrix (LHS) and the constraint vector (RHS), which transforms the original linear model into a nonlinear and non-convex one with respect to both the optimization variables and the parameters.

Here, we discuss two novel methods for the solution of the general multi-parametric (mp) MILP problem with OFC-, RHS- and LHS-uncertainty. The first approach is a two-stage method, [1], which efficiently obtains approximate solutions by combining suitable robust optimization and multi-parametric programming techniques yielding a tight upper bound on the optimal objective function value. In the first step a partial immunization of the model against LHS-uncertainty is performed, whereas in the second step explicit solutions of the partially robust counterpart are derived using a recently proposed mp-MILP algorithm [2].

The second approach deals with the global solution of the general mp-MILP problem. Extending the ideas of [3] to our framework, we outline the steps of a parametric branch and bound algorithm for the global solution of mp-LP problems with LHS-uncertainty, which play a key role in the overall global solution of mp-MILP problems.We exploit the special structure of the mp-MILP problem to construct competitive multi-parametric under- and overestimating problems employing McCormick-type relaxations of bilinear terms. Furthermore, we discuss the alternative of embedding novel piecewise affine relaxations of bilinear terms [4,5] in the proposed procedure. The optimal solution of the general mp-MILP problem is approximated by piecewise affine functions.

References

[1].	Wittmann-Hohlbein, M., Pistikopoulos, E.N.  A robust optimization based approach to the general solution of mp-MILP problems. Accepted for publication in Proceedings of 21st European Symposium on Computer Aided Process Engineering.
[2].	Faísca, N.P., Kosmidis, V.D., Rustem, B., Pistikopoulos, E.N. Global optimization of multi-parametric MILP problems. Journal of Global Optimization 45, 131–151 (2009).
[3].	Dua, V., Papalexandri, K.P., Pistikopoulos, E.N. Global optimization issues in multiparametric continuous and mixed-integer optimization problems. Journal of Global Optimization 30, 59-89 (2004).
[4].	Wicaksono, D.S., Karimi, I.A. Piecewise MILP under- and overestimators for global optimization of bilinear programs. AIChE Journal 54, 991-1008 (2008).
[5].	Gounaris, C.E., Misener, R., Floudas, C.A. Computational comparison of piecewise−linear relaxations for pooling problems. Industrial & Engineering Chemical Research 48, 5742-5766 (2009).