  Many problems in optimization theory are strongly nonlinear in the
traditional sense but possess a hidden linear structure over suitable
idempotent semirings. After an overview of `Idempotent Mathematics' with an
emphasis on matrix theory, interval analysis over idempotent semirings is
developed. The theory is applied to construction of exact interval solutions to
the interval discrete stationary Bellman equation. Solution of an interval
system is typically NP-hard in the traditional interval linear algebra; in the
idempotent case it is polynomial. A generalization to the case of positive
semirings is outlined.
