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

BAUSO D, R PESENTI (2006). A Polynomial Algorithm solving a Special Class of Hybrid Optimal Control Problems. In Proceedings of the IEEE International Conference on Control Applications (pp.349-354) [10.1109/CACSD-CCA-ISIC.2006.4776671].

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

BAUSO, Dario;PESENTI, Raffaele
2006-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
Settore MAT/09 - Ricerca Operativa
IEEE Conference on Control Applications
Munich, Germany
Oct. 4-6, 2006.
2006
6
BAUSO D, R PESENTI (2006). A Polynomial Algorithm solving a Special Class of Hybrid Optimal Control Problems. In Proceedings of the IEEE International Conference on Control Applications (pp.349-354) [10.1109/CACSD-CCA-ISIC.2006.4776671].
Proceedings (atti dei congressi)
BAUSO D; R PESENTI
File in questo prodotto:
File Dimensione Formato  
04776671.pdf

Solo gestori archvio

Descrizione: pdf
Dimensione 157.48 kB
Formato Adobe PDF
157.48 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/10456
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact