Show simple item record

dc.contributor.advisorMahjoub, Ali Ridha
hal.structure.identifier
dc.contributor.authorMartin, Sébastien
HAL ID: 9612
ORCID: 0000-0001-8980-8628
*
dc.date.accessioned2012-07-11T14:55:26Z
dc.date.available2012-07-11T14:55:26Z
dc.date.issued2011-12
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9724
dc.description.abstractfrLes 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.en
dc.language.isofren
dc.subjectseparator problemen
dc.subjectbranch-and-cut algorithmen
dc.subjectseparation problemen
dc.subjectfaceten
dc.subjectcomplexityen
dc.subjectmatchingen
dc.subjectgraphen
dc.subjectdifferential algebraic systemen
dc.subjectstructural analysisen
dc.subjectproblème du séparateuren
dc.subjectalgorithmes de coupes et de branchementsen
dc.subjectséparationen
dc.subjectfacetteen
dc.subjectpolytopeen
dc.subjectcomplexitéen
dc.subjectcouplageen
dc.subjectgrapheen
dc.subjectsystème algébro-différentielen
dc.subjectAnalyse structurelleen
dc.subject.ddc003en
dc.titleAnalyse structurelle des systèmes algébro-différentiels conditionnels : complexité, modèles et polyèdresen
dc.title.alternativeStructural analysis for conditional differential-algebraic systems: complexity, formulation and facetsen
dc.typeThèseen
dc.contributor.editoruniversityUniversité Paris Dauphine
dc.description.abstractenDifferential 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.en
dc.identifier.citationpages188en
dc.identifier.theseid2011PA090078en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record