| Attributes | Values |
|---|
| type
| |
| Thesis advisor
| |
| Author
| |
| alternative label
| - Structural analysis for conditional differential-algebraic systems : complexity, formulation and facets
|
| dc:subject
| - Théorie des graphes
- Thèses et écrits académiques
- Complexité de calcul (informatique)
- Polyèdres
- Couplage, Théorie du
- Polytopes convexes
|
| preferred label
| - Analyse structurelle des systèmes algébro-différentiels conditionnels, complexité, modèles et polyèdres
|
| Language
| |
| Subject
| |
| dc:title
| - Analyse structurelle des systèmes algébro-différentiels conditionnels, complexité, modèles et polyèdres
|
| Degree granting institution
| |
| note
| - Differential algebraic systems are used for modeling complex physical systems as electrical networks and dynamic movements. They are often large and difficult to solve. The structural analysis for differential algebraic systems permits to verify if these systems can not be solved with numerical methods. It consists to solve an underlying matching problem in graphs. In this thesis, we consider the structural analysis problem for differential algebraic systems with conditional equations. We show that the structural analysis problem for differential algebraic systems with conditional equations reduces to which we call the perfect matching free subgraph problem. We show the NP-completeness of this latter problem. We propose a formulation in terms of graphs and two integer programming formulations. We study the polytope associated to this problem and describe several classes of valid inequalities. We give necessary and sufficient conditions for these inequalities to be facet defining. We also discuss separation algorithms for these constraints. We develop a branch-and-cut algorithm based on these results. We also study an extension of this problem to differential algebraic systems with conditional embedded equations. We generalize the results obtained for the first variant and give new valid inequalities for this more general problem. In a second part, we study the parallelization problem for differential algebraic systems. This problem reduces to which is called the separator problem. We give several integer programming formulations, and for one of them we study the associated polytope. We give a few experimental results associated to this polyhedral study.
- Les systèmes algébro-différentiels permettent de modéliser des systèmes physiques complexes comme les circuits électriques et les mouvements dynamiques. Ils sont souvent de grande taille et difficiles à résoudre. L'analyse structurelle des systèmes algébro-différentiels permet de vérifier si un tel système ne pourra pas être résolu par des méthodes numériques. Elle consiste à résoudre un problème sous-jacent de couplage dans les graphes. Dans cette thèse, nous étudions ce problème dans le cas des systèmes algébro-différentiels conditionnels. Nous montrons que ce problème est équivalent au problème du sous-graphe sans couplage parfait. Nous montrons que ce dernier est NP-difficile. Nous proposons une formulation en termes de graphes et deux formulations en nombres entiers pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires et suffisantes pour que ces contraintes définissent des facettes. Nous discutons également d'algorithmes de séparation pour ces contraintes et en utilisant ces résultats, nous développons un algorithme de coupes et branchements. Nous étudions aussi une extension de ce problème pour les systèmes algébro-différentiels conditionnels imbriqués. Nous étendons la plupart des résultats précédents à ce cas. Nous identifions de nouvelles contraintes valides pour cette variante du problème. Dans une deuxième partie, nous nous intéressons au problème de parallélisation des systèmes algébro-différentiels. Ce problème se ramène au problème du séparateur. Nous proposons plusieurs formulations en nombres entiers du modèle et pour l'une d'entre elle, nous étudions le polyèdre associé. Nous proposons quelques résultats expérimentaux obtenus suite à cette étude
|
| dc:type
| |
| http://iflastandar...bd/elements/P1001
| |
| rdaw:P10219
| |
| has content type
| |
| is primary topic
of | |
| is rdam:P30135
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
