New results
Handling Multimode Models and Mode Changes in Modelica
Since version 3.3, the Modelica language offers the possibility of specifying multimode dynamics, by describing state machines with different DAE dynamics in each different state 59. This feature enables describing large complex cyber-physical systems with different behaviors in different modes.
While being undoubtedly valuable, multimode modeling has been the source of serious difficulties for non-expert users of the current generation of Modelica tools. Indeed, while many large-scale Modelica models are properly handled, some physically meaningful models do not result in correct simulations with most Modelica tools. As such problematic models are actually easy to construct, the likelihood of such bad cases occurring in large models is significant.
It is unfortunately unclear which multimode Modelica models will be properly handled, and which ones will fail. As a consequence, quite often, end users have to ask Modelica experts, or even tool developers themselves, to tweak their models in order to make them work as expected. While it is accepted that physical modeling itself requires expertise, requiring expertise in how to get around tool idiosyncrasies is not desirable. This situation hinders the dissemination of Modelica tools among a larger class of users, such as Simulink-trained engineers.
Several examples, presented in 7 reveal that this problem is due to an inadequate structural analysis, performed during compilation. As far as we know, no industrial-strength Modelica tool implements a mode-dependent structural analysis. Worse, it is not even understood what kind of structural analysis should be associated with mode change events.
Some years ago, we started a project aiming at addressing all the above issues 25, 24, 30. In 7, we cast our approach in the context of the Modelica language, by illustrating it on two simple yet physically meaningful examples that current Modelica tools fail to properly simulate. The use of nonstandard analysis allows us to perform the analysis of both modes and mode changes in a unified framework, including the handling of transient modes and that of impulsive mode changes. Standardization techniques are then used in order to generate effective code for restarts at mode changes.
As an efficient implementation of such methods in Modelica compilers would greatly expand the class of multimode models amenable to reliable numerical simulation, multimode DAE structural analysis algorithms are also detailed in 7. This extends previous work presented in 44: mode enumeration is avoided thanks to the use of an implicit, BDD-based symbolic representations of the structure of a multimode DAE system. However, the scalability of the algorithm is greatly improved thanks to the use of CoSTreD 14, a message-passing technique, that allows to decompose the resolution of the primal problem of the multimode Pryce method into a set of smaller parametric optimization problems —more details in Section 8.2.
A compile-time calculus that evaluates the impulse order of algebraic variables is also detailed in 7. Finite impulse orders can be used to renormalize impulsive variables when implementing a numerical scheme that approximates the restart values for each state variable of the system. We also detail in this paper, a systematic way of rewriting a multimode Modelica model, based on the results of a multimode structural analysis. The rewritten Modelica model is guaranteed to have a reduced index and a mode-independent structure. This suffices to guarantee correctly compiled by state-of-the-art Modelica tools. Simulation results are presented on a simple, yet meaningful, physical system whose original Modelica model is not correctly handled by state-of-the-art Modelica tools.
We demonstrate how the results of this multimode structural analysis can be used for transforming a multimode Modelica model into its RIMIS (Reduced Index Mode-Independent Structure) form, which is guaranteed to yield correct execution on state-of-the-art Modelica tools.
Constraint System Decomposition
Various classical problems in computer science can be formulated as Constraint Solving Problems (CSP), consisting in a query on a conjunction of constraints. Typical instances of such queries are satisfiability problems, optimization under constraints, model enumeration, model counting and normalization. Constraint systems can be Conjunctive Normal Form (CNF) formulas, as well as Integer Linear Programs (ILP), and, in its most generic form, Constraint Programs (CP). In both industrial and academic contexts, instances are generally structured and, in most cases, sparse: each constraint involves only a small set of variables, and variables are only involved in a small set of constraints. Moreover, large practical instances tend to have a tree-like structure, which can efficiently be captured by the notion of treewidth, as commonly considered in the fixed-parameter tractability community. Using dynamic programming to solve problems for which a “good” tree decomposition is available is well known, and has been rediscovered many times in the history of computer science, under various names: message passing in factor graphs, belief propagation in belief networks, arc consistency in constraint networks, etc. In 14, we introduce the CoSTreD (Constraint System Tree Decomposition) method, based on symbolic representations and operators on them to improve the scalability of CSP solving. CoSTreD is based upon two operators: a projection operator which allows to deal with satisfiability and canonicalization locally on the tree decomposition, and a co-projection operator, extending the method to optimization queries. We establish sufficient conditions under which these operators preserve the semantics of the CSP. Finally, CoSTreD is extended to deal with parameter (or mode) variables, mostly by (i) adapting the notion of tree decomposition to deal with parameter variables, (ii) using symbolic representations to avoid the combinatorial explosion of mode enumeration, and (iii) mitigating the contamination of constraints by parameter variables during message passing.
Characterizing Q-matrices
In 13, we provide a geometric equivalent reformulation of a relatively old, yet unsolved, problem that originated in the optimization community: under which conditions on the
Characterizing Positively Invariant Sets: Inductive and Topological Methods
In 8, we present two characterizations of positive invariance of sets for systems of ordinary differential equations. The first characterization uses inward sets which intuitively collect those points from which the flow evolves within the set for a short period of time, whereas the second characterization uses the notion of exit sets, which intuitively collect those points from which the flow immediately leaves the set. Our proofs emphasize the use of the real induction principle as a generic and unifying proof technique that captures the essence of the formal reasoning justifying our results and provides cleaner alternative proofs of known results. The two characterizations presented in this article, while essentially equivalent, lead to two rather different decision procedures (termed respectively LZZ and ESE) for checking whether a given semi-algebraic set is positively invariant under the flow of a system of polynomial ordinary differential equations. The procedure LZZ improves upon the original work by Liu, Zhan and Zhao 72. The procedure ESE, introduced in this article, works by splitting the problem, in a principled way, into simpler sub-problems that are easier to check, and is shown to exhibit substantially better performance compared to LZZ on problems featuring semi-algebraic sets described by formulas with non-trivial Boolean structure.
