A Polynomial Algorithm solving a Special Class of Hybrid Optimal Control Problems

Dario Bauso, Raffaele Pesenti

Risultato della ricerca: Otherpeer review


Hybrid optimal control problems are, in general, difficult to solve. A current research goal is to isolate those problems that lead to tractable solutions [5]. In this paper, we identify a special class of hybrid optimal control problems which are easy to solve. We do this by using a paradigm borrowed from the Operations Research field. As main result, we present a solution algorithm that converges to the exact solution in polynomial time. Our approach consists in approximating the hybrid optimal control problem via an integer-linear programming reformulation. The integer-linear programming problem is a Set-covering one with a totally unimodular constraint matrix and therefore solving the Setcovering problem is equivalent to solving its linear relaxation. It turns out that any solution of the linear relaxation is a feasible solution for the hybrid optimal control problem. Then, given the feasible solution, obtained solving the linear relaxation, we find the optimal solution via local search
Lingua originaleEnglish
Numero di pagine6
Stato di pubblicazionePublished - 2006

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2200.2200???


Entra nei temi di ricerca di 'A Polynomial Algorithm solving a Special Class of Hybrid Optimal Control Problems'. Insieme formano una fingerprint unica.

Cita questo