![]()
The main topic of this thesis is integer quadratic programming with applications to prob-
lems arising in the areas of automatic control and communication. One of the most
widespread modern control principles is the discrete-time method Model Predictive Con-
trol (MPC). The main advantage with MPC, compared to most other control principles,
is that constraints on control signals and states can easily be handled. In each time step,
MPC requires the solution of a Quadratic Programming (QP) problem. To be able to
use MPC for large systems, and at high sampling rates, optimization routines tailored for
MPC are used. In recent years, the range of application of MPC has been extended from
constrained linear systems to so-called hybrid systems. Hybrid systems are systems where
continuous dynamics interact with logic. When this extension is made, binary variables
are introduced in the problem. As a consequence, the QP problem has to be replaced by
a far more challenging Mixed Integer Quadratic Programming (MIQP) problem. Gener-
ally, for this type of optimization problems, the computational complexity is exponential
in the number of binary optimization variables. In modern communication systems, mul-
tiple users share a so-called multi-access channel, where the information sent by different
users is separated by using almost orthogonal codes. Since the codes are not completely
orthogonal, the decoded information at the receiver is slightly correlated between differ-
ent users. Further, noise is added during the transmission. To estimate the information originally sent, a maximum likelihood problem involving binary variables is solved. The
process of simultaneously estimating the information sent by multiple users is called mul-
tiuser detection. In this thesis, the problem to efficiently solveMIQP problems originating
fromMPC is addressed. Two different algorithms are presented. First, a polynomial com-
plexity preprocessing algorithm for binary quadratic programming problems is presented.
By using the algorithm, some, or all, binary variables can be computed efficiently already
in the preprocessing phase. In simulations, the algorithm is applied to unconstrainedMPC
problems with a mixture of real and binary control signals. It has also been applied to the
multiuser detection problem, where simulations have shown that the bit error rate can
be significantly reduced by using the proposed algorithm as compared to using common
suboptimal algorithms. Second, an MIQP algorithm tailored for MPC is presented. The
algorithm uses a branch and bound method where the relaxed node problems are solved
by a dual active set QP algorithm. In this QP algorithm, the KKT-systems are solved using
Riccati recursions in order to decrease the computational complexity. Simulation results
show that both the QP solver and the MIQP solver proposed have lower computational
complexity than corresponding generic solvers.
