(568f) The Exact Solution of Multiparametric Mixed-Integer Quadratic Programming Problems

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 CR_i, each of which is associated with the
corresponding optimal affine solution x_i(θ), the optimal combination of binary
variables y_i and quadratic objective function z_i(θ).

 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 x_i,j(θ),y_i,j,z_i,j(θ) to one critical region CR_i,
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.

References

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(4?5): p. 715?733.

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. 527?543.

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

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.
147?175.

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. 407?427.