424392 The Exact Solution of Multiparametric Mixed-Integer Quadratic Programming Problems

Wednesday, November 11, 2015: 5:00 PM
Salon F (Salt Lake Marriott Downtown at City Creek)
Richard Oberdieck1,2 and Efstratios N. Pistikopoulos1, (1)Artie McFerrin Department of Chemical Engineering, Texas A&M University, College Station, TX, (2)Dept. of Chemical Engineering, Centre for Process Systems Engineering, Imperial College London, London, United Kingdom

In recent years, multiparametric programming in general and multiparametric mixed-integer quadratic programming (mp-MIQP) in particular has received a growing interest due to its applicability in areas such as explicit optimal control and reactive scheduling [1]. In general, mp-MIQP problems consist of a quadratic objective function z(θ) subject to linear constraints and a polytopic parameter space. The corresponding solution is a partitioning of the feasible parameter space into a number of so-called critical regions CRi, each of which is associated with the corresponding optimal affine solution xi(θ), the optimal combination of binary variables yi and quadratic objective function zi(θ).

However, obtaining this solution is very challenging due to two key difficulties:

-       The presence of the binary variables: This has been approached via (a) global optimization [2], (b) branch-and-bound algorithms [3, 4] and (c) exhaustive enumeration [5].

-       The comparison of the parametric profiles for each feasible combination of binary variables: Such a comparison procedure is necessary in order to obtain a single, optimal parametric profile for the solution of the mp-MIQP. Due to the quadratic nature of the objective function z(θ), the transition from the one solution being optimal to another might be quadratic, resulting in non-polytopic partitions. Earlier approaches have avoided the formation of such regions by assigning multiple solutions xi,j(θ),yi,j,zi,j(θ) to one critical region CRi, which is referred to as an envelope of solutions. The presence such envelopes requires the online comparison of all solutions assigned to a specific critical region, a procedure which conceptually undermines the idea of explicit MPC as it introduces online computational burden.

In this work, we present a novel mp-MIQP algorithm which circumvents the generation of envelopes of solutions by enabling the seamless handling of non-polytopic critical regions [6]. This strategy can be decomposed into a series of steps:

1.    Determination of a candidate combination of binary variables considering the non-polytopic critical region CR.

2.    Calculation of a polytope Ξ such that CRΞ via McCormick relaxations [7].

3.    The candidate combination of binary variables is fixed in the original mp-MIQP problem and the resulting multiparametric quadratic programming (mp-QP) problem is solved for θΞ using existing solvers [8].

4.    Given the problem is feasible, the resulting, polytopic parametric profile is compared with the parametric profile of the upper bound. This comparison can be decomposed into two steps:

a.    Determination whether one of the solutions is optimal over the entire range of the critical region considered

b.    If this is not the case, partition the considered critical region using the difference of the optimal objective function of the mp-QP subproblem in the critical region considered and the objective function of the current best upper bound. Due to the quadratic nature of these functions this might result in quadratically constrained critical region.

5.    As the comparison procedure was performed in Ξ, it is necessary to perform a post-processing step by re-introducing the quadratic constraints of CR. As this might result in empty regions, a quadratically constrained quadratic programming (QCQP) feasibility problem is solved for each newly formed region.

6.    The next iteration of the algorithm begins.

This newly developed approach towards the solution of mp-MIQP problems is applied to several numerical examples, where its computational performance is compared against existing approaches. In particular, it is shown that despite the necessity of solving a QCQP feasibility problem, the computational effort remains manageable as each critical region is only associated with one objective function value.

Additionally, we apply the proposed procedure to explicit hybrid control problems, which can be formulated as mixed-integer quadratic programming (MIQP) problems [9]. In particular, we consider the well-known hybrid control problem posed in [9], and show how the proposed procedure yields the exact partitioning of the state-space, hence reducing the online computational effort for this system to a point location and a function evaluations.


1. Pistikopoulos, E.N., et al., PAROC - an Integrated Framework and Software Platform for the Optimization and Advanced Model-Based Control of Process Systems. Chemical Engineering Science, 2015, in print.

2. Dua, V., N.A. Bozinis, and E.N. Pistikopoulos, A multiparametric programming approach for mixed-integer quadratic engineering problems. Computers & Chemical Engineering, 2002. 26(45): p. 715733.

3. Oberdieck, R., M. Wittmann-Hohlbein, and E.N. Pistikopoulos, A branch and bound method for the solution of multiparametric mixed integer linear programming problems. Journal of Global Optimization, 2014. 59(2-3): p. 527543.

4. Axehill, D., et al., A parametric branch and bound approach to suboptimal explicit hybrid MPC. Automatica, 2014. 50(1): p. 240246.

5. Borrelli, F., Constrained optimal control of linear and hybrid systems. Lecture Notes in Control and Information Sciences. 2003, Berlin; New York: Springer. 1 online resource (xvii, 206.

6. Oberdieck, R. and E.N. Pistikopoulos, Explicit Hybrid Model-Predictive Control: The exact solution. Automatica, 2015. Accepted for publication.

7. McCormick, G.P., Computability of global solutions to factorable nonconvex programs: Part I Convex underestimating problems. Mathematical Programming, 1976. 10(1): p. 147175.

8. ParOs, Parametric Optimization Programming (POP). 2004, ParOS.

9. Bemporad, A. and M. Morari, Control of systems integrating logic, dynamics, and constraints. Automatica, 1999. 35(3): p. 407427.

Extended Abstract: File Not Uploaded
See more of this Session: Advances in Optimization III
See more of this Group/Topical: Computing and Systems Technology Division