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
TypeCommunication / Conférence
Conference titleISCO International Symposium on Combinatorial Optimization
Journal nameElectronic Notes in Discrete Mathematics
MetadataShow full item record
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 / Keywordsstructural analysis; Differential algebraic system; facet; polytope; matching; bipartite graph
Showing items related by title and author.
Combinatorial optimization model and MIP formulation for the structural analysis of conditional differential-algebraic systems. Martin, Sébastien; Mahjoub, Ali Ridha; Lacroix, Mathieu (2011) Article accepté pour publication ou publié
Cornaz, Denis; Furini, Fabio; Lacroix, Mathieu; Malaguti, Enrico; Mahjoub, Ali Ridha; Martin, Sébastien (2014) Communication / Conférence