Algorithms for the solution of multiparametric mixed-integer nonlinear optimization problems

In this paper we present novel theoretical and algorithmic developments for the solution of mixed-integer optimization problems involving uncertainty, which can be posed as multiparametric mixed-integer optimization models, w here uncertainty is described by a set of parameters bounded between lower and upper bounds. In particular, we address convex nonlinear formulations i nvolving (i) 0-1 integer variables and (ii) uncertain parameters appearing linearly and separately and present on the right-hand side of the constrain ts. The developments reported in this work are based upon decomposition pri nciples where the problem is decomposed into two iteratively converging sub problems: (i) a primal and (ii) a master subproblem, representing valid par ametric upper and lower bounds on the final solution, respectively. The pri mal subproblem is formulated by fixing the integer variables which results in a multiparametric nonlinear programming (mp-NLP) problem, which is solve d by outer-approximating the nonlinear functions at a number of points in t he space of uncertain parameters to derive linear profiles. The aim of the master subproblem is then to propose another set of integer solutions which are better than the integer solutions that have already been analyzed in t he primal subproblem. This can be achieved by (i) introducing cuts, (ii) em ploying outer-approximation (OA) principles, or (iii) using generalized ben ders decomposition (GBD) fundamentals. The algorithm terminates when the ma ster problem cannot identify a better integer solution.