Global Optimization of Multi-Parametric Milp Problems

Multi-parametric programming has recently received considerable attention in the open literature (Pistikopoulos et al, 2007a,b), with important applications to pro-active scheduling and planning under uncertainty problems (Ryu and Pistikopoulos). However, despite these advances, certain important classes of multi-parametric programs have not been fully addressed in the open literature.

In this presentation, we present a global optimisation approach for the general solution of multi-parametric mixed integer linear programs (mp-MILPs), which substantially extends and generalises our earlier work on mp-MILP with only right-hand side (RHS) uncertainty (Dua and Pistikopoulos, 2000). In particular, we describe an optimisation procedure which iterates between a (master) mixed integer non-linear program and a (slave) multi-parametric program. Moreover, we explain how to overcome the presence of bi-linearities, responsible for non-convexity of the multi-parametric program, in two classes of mp-MILPs, with (i) varying parameters in the objective function and (ii) simultaneous presence of varying parameters in the objective function and the right-hand side of the constraints. Planning examples are provided to illustrate the solution steps.

References

Dua, V. and E.N. Pistikopoulos (2000). An algorithm for the solution of multi-parametric mixed integer linear programming problems. Annals of Operations Research 99, pp. 123-139.

Pistikopoulos, E.N., M.C. Georgiadis and V. Dua (2007a). Multiparametric programming: theory, algorithms, and applications, vol 1, Wiley-VCH. Weinheim.

Pistikopoulos, E.N., M.C. Georgiadis and V. Dua (2007b). Multiparametric model-based control: theory and applications, vol 2, Wiley-VCH. Weinheim.

Ryu, JH and E.N. Pistikopoulos (2007). A novel approach to scheduling of zero-wait batch processes under processing time variations. COmputers and Chemical Engineering 31(3), pp. 101-106.