optimization.tex

由matlab开发的hybrid系统的描述语言

\chapter{Optimization}
\label{optimization_c}


The most important reason to do optimization is to reduce the size
of the \MLD{} system produced. Smaller systems are easier to
handle.

Another reason is to have the output more readable. \hysdel{} now provides symbolic parameters, which should give
insight into the \MLD{} system. But if every matrix element spans multiple lines, this is hardly the
case.\footnote{Since expression simplification is not yet implemented, you should let \matlab{}'s symbolic toolkit
do this. The option \longcmdop{matlab-symbolic} at the command line produces the proper declarations.}

Finally, if the expressions during computation grow too quickly, compiling a \hysdel{} source can take long.
Keeping expressions small by simplifying them saves a lot of memory and CPU time.


\section{Minimizing the CNF}

Enforcing the logic expression
\begin{align}
f=\bigwedge_{i=1}^N (\bigvee_j l_{i,j} )
\end{align}
for literals $l_{i,j}$ requires $N$ \MLD{} inequalities. A CNF should therefore be as small as possible. Finding
the minimal CNF is possible but not yet implemented. The method \method{CNF\_clause}{simplify} first optimizes all
clauses separately. This simplification guarantees that no variable appears twice in a clause. Then we check
whether some clause $A$ implies some other clause $B$. This is the case if all literals of $A$ are also in $B$ ($A
\subseteq B$). If $A \rightarrow B$, $A$ is removed.
\begin{equation}
(A \rightarrow B) \wedge A \Leftrightarrow (\neg A \vee B) \wedge A \Leftrightarrow (A \vee \neg A) \wedge (A \vee
B) \Leftrightarrow A \wedge B
\end{equation}

This does not lead to a minimal CNF, as the following example
shows: The expression $ f = (a_1 \vee a_2) \wedge ( \neg a_1 \vee
a_2 ) $ is not simplified by \hysdel{} (to test it, put it in the
must-section). However, it is equivalent to $ f = a_2 $.


\section{Minimizing Affine functions}
\label{simpl_affine}

\cppclass{Affine\_func} guarantees that no two addends refer to the same variable. Thus, to simplify an affine
function it suffices to simplify each coefficient (which are of type \cppclass{Expr}).


\section{Simplifying Expressions}

Simplification at the expression level is not implemented. The
only simplification done by \method{Expr}{simpl} is to replace the
entire expression by a number, if this is possible, i.e. if the
expression contains no variables and no symbolic parameters. It is
called whenever a new \cppclass{Min\_expr} or \cppclass{Max\_expr}
is created. The reason is that when upper and lower bounds have to
be computed automatically (see chapter~\ref{mme_comp_c}), the
resulting expressions can grow extremely fast.

An hack is implemented in the methods \method{Expr}{to\_matlab} to
print out a almost minimal number of parenthesis.

\section{Other Optimizations}

If the digital part of a DA converter is a negated variable, it is not necessary to unroll it. Instead, we
exchange the `then'- and the `else'-part, which takes care of the negation. Now the logic expression is simply a
variable and the entire DA can be translated directly.

When equalities are used to assign Boolean expressions (in AUTOMATA and logic OUTPUT), the right hand side must be
a simple variable (or the constant `false'). Otherwise the expression is unrolled. If the extended \MLD{} system
is used (\cmdop{5} at the command line), an equality can also assign negated variables and the constant `true'.