Advances in multi-parametric mixed-integer programming and its applications

Abstract

At many stages of process engineering we are confronted with data that have not yet revealed their true values. Uncertainty in the underlying mathematical model of real processes is common and poses an additional challenge on its solution. Multi-parametric programming is a powerful tool to account for the presence of uncertainty in mathematical models. It provides a complete map of the optimal solution of the perturbed problem in the parameter space. Mixed integer linear programming has widespread application in process engineering such as process design, planning and scheduling, and the control of hybrid systems. A particular difficulty arises, significantly increasing the complexity and computational effort in retrieving the optimal solution of the problem, when uncertainty is simultaneously present in the coefficients of the objective function and the constraints, yielding a general multi-parametric (mp)-MILP problem. In this thesis, we present novel solution strategies for this class of problems. A global optimization procedure for mp-MILP problems, which adapts techniques from the deterministic case to the multi-parametric framework, has been developed. One of the challenges in multi-parametric global optimization is that parametric profiles, and not scalar values as in the deterministic case, need to be compared. To overcome the computational burden to derive a globally optimal solution, two-stage methods for the approximate solution of mp-MILP problems are proposed. The first approach combines robust optimization and multi-parametric programming; whereas in the second approach suitable relaxations of bilinear terms are employed to linearize the constraints during the approximation stage. The choice of approximation techniques used in the two-stage method has impact on the conservatism of the solution estimate that is generated. Lastly, multi-parametric programming based two-stage methods are applied in pro-active short-term scheduling of batch processes when faced with varied sources of uncertainty, such of price, demand and operational level uncertainty.