6533b857fe1ef96bd12b45d7
RESEARCH PRODUCT
A polynomial algorithm solving a special class of hybrid optimal control problems
W.j. BookHaihong Zhusubject
EngineeringMathematical optimizationForce densityComputational complexity theoryLinear programmingbusiness.industrySpecial classOptimal controlPolynomial algorithmControllabilityHybrid optimal controlAlgorithmsHybrid computersInteger programmingLinear control systemsUnimodular matrixControl theoryHuman machine interactionLocal search (optimization)Relaxation (approximation)Settore MAT/09 - Ricerca OperativabusinessInteger programmingTime complexityMathematicsdescription
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 Set-covering 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2006-10-01 | 2006 IEEE Conference on Computer Aided Control System Design, 2006 IEEE International Conference on Control Applications, 2006 IEEE International Symposium on Intelligent Control |