A SAT-Based Hybrid Solver for Optimal Control of Hybrid Systems

摘要: Combinatorial optimization over continuous and integer variables was proposed recently as an useful tool for solving complex optimal control problems linear hybrid dynamical systems formulated in discrete-time. Current approaches are based on mixed-integer linear/quadratic programming (MIP), which provides the solution after a sequence of relaxed standard (or quadratic) programs (LP, QP). An MIP formulation has drawback requiring that discrete/logic part problem needs to be converted into inequalities. Although this operation can done automatically, most original discrete structure is lost during conversion. Moreover, efficiency solver only relies upon tightness LP/QP relaxations. In paper we attempt at overcoming such difficulties by combining constraint (CP) techniques "hybrid" solver, taking advantage CP dealing efficiently with satisfiability logic constraints. We detail how model dynamics so solved MIP+CP show case study achieved performance superior one pure solvers.