Thumbnail - Request a copy

Structural Analysis for Differential-Algebraic Systems : Complexity, formulation and facets

Mahjoub, Ali Ridha; Lacroix, Mathieu; Martin, Sébastien (2010), Structural Analysis for Differential-Algebraic Systems : Complexity, formulation and facets, ISCO International Symposium on Combinatorial Optimization, 2010-03, Hammamet, Tunisie

Type
Communication / Conférence
Date
2010
Conference title
ISCO International Symposium on Combinatorial Optimization
Conference date
2010-03
Conference city
Hammamet
Conference country
Tunisie
Journal name
Electronic Notes in Discrete Mathematics
Volume
36
Publisher
Elsevier
Pages
1073-1080
Publication identifier
Metadata
Show full item record
Author(s)
Mahjoub, Ali Ridha
Lacroix, Mathieu cc
Martin, Sébastien cc
Abstract (EN)
In this paper we consider the structural analysis problem for differential-algebraic systems with conditional equations. This consists, given a conditional differential algebraic system, in verifying if the system is wellconstrained for every state and if not in finding a state for which the system is bad-constrained. We first show that the problem reduces to the perfect matching free subgraph problem in a bipartite graph. We then show the NP-completeness of this problem and give a formulation as an integer linear program.We also discuss the polytope of the solutions of this problem and propose a Branch-and-Cut algorithm.
Subjects / Keywords
structural analysis; Differential algebraic system; facet; polytope; matching; bipartite graph