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**

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

**Extended Abstract:**File Not Uploaded

See more of this Group/Topical: Computing and Systems Technology Division