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.
A Polynomial algorithm solving a special class of hybrid optimal control problems
PESENTI, Raffaele
2007-01-01
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
04776671.pdf
non disponibili
Tipologia:
Documento in Post-print
Licenza:
Accesso chiuso-personale
Dimensione
159.33 kB
Formato
Adobe PDF
|
159.33 kB | Adobe PDF | Visualizza/Apri |
I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.