Abstract
Optimal impulse control problems are, in general, difficult to solve. A current research goal is to isolate those problems that lead to tractable solutions. In this paper, we identify a special class of optimal impulse control problems which are easy to solve. Easy to solve means that solution algorithms are polynomial in time and therefore suitable to the on-line implementation in real-time problems. 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 optimal impulse control problem via a binary linear programming problem with a totally unimodular constraint matrix. Hence, solving the binary linear programming problem is equivalent to solving its linear relaxation. It turns out that any solution of the linear relaxation is a feasible solution for the optimal impulse control problem. Then, given the feasible solution, obtained solving the linear relaxation, we find the optimal solution via local search.
Lingua originale | English |
---|---|
Numero di pagine | 5 |
Stato di pubblicazione | Published - 2009 |
All Science Journal Classification (ASJC) codes
- ???subjectarea.asjc.2200.2207???
- ???subjectarea.asjc.2600.2611???
- ???subjectarea.asjc.2600.2606???