Analisis Metode Branch and Bound dalam Masalah Kuadratic Integer Programming

Abstract

This thesis will discuss about integer quadratic programming with applications to problems arising in the areas of automatic control and communication. One of the most widespread modern control principles is the discrete-time method model predictive control (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. Generally, for this type of optimization problems, the computational complexity is exponential in the number of binary optimization variables. Simulation results show that both the qp solver and the miqp solver proposed have lower computational complexity than corresponding generic solver.