Structural Analysis for Conditional-Algebraic Systems, and Combinatorial Optimization
Seminar by
A. Ridha Mahjoub
Université Paris-Dauphine
Abstract:
Differential-Algebraic Systems (DAS) are used for modeling complex physical systems such as electrical networks and dynamic movements. Such a system can be given as F(x,x’,t)=0 where x is the variable vector, t the time and x’ the derivative vector associated to x with respect to time. In many practical situations, physical systems may have different states generated by some technical conditions. These may be, for instance, related to temperature change. Such systems generally yield conditional DASs which may have different states depending on the assignment of the true and false values to the conditions. Each assignment yields a non-conditional system called a state of the system. A main problem, which arises in the analysis of DASs, is to know whether or not the system may have a solution in each state, and if not to determine a state in which the system has no solution. This is called the Structural Analysis Problem. In this talk, we consider this problem. We give an integer programming formulation for the problem. This is based on a transformation of the problem into a matching problem in an auxiliary graph. We show that the linear relaxation can be solved in polynomial time. We also describe some valid inequalities. Using this, we will discuss a Branch-and-Cut algorithm for the problem along with some experimental results.
Bio:
A. Ridha Mahjoub is Professeur Classe Exceptionnelle of Operations Research and Combinatorial Optimization at Université Paris-Dauphine, Paris, France. He is also member of the LAMSADE laboratory, CNRS. Previous positions include full professor at the University of Brest, France, from 1991 to 1998 and the University of Clermont-Ferrand, France, from 1998 to 2007. Dr. Mahjoub holds an undergraduate degree in Mathematics from University of Tunis, Tunisia and a Ph.D. and a Doctorat d’Etat in Operations Research and Combinatorial Optimization from the University of Grenoble, France. His research areas include the theory and applications of polyhedral approaches for modeling, analyzing and solving large NP-hard combinatorial optimization problems, mixed integer programming as well as complexity and graph theory. A part of his research has recently focused on the design of cutting plane algorithms for network design problems. Dr. Mahjoub is author and co-author of several papers that have appeared in leading journals such as Mathematical Programming, Mathematics of Operations Research, SIAM Journal on Discrete Mathematics, Discrete Mathematics, Discrete Applied Mathematics, Discrete Optimization, Informs Journal on Computing and Networks. He served as Co-Director of the Mathematics and Computer Science Department at Université Paris-Dauphine between 2008 and 2013. Dr. Mahjoub edited and co-edited books and several special issues of journals. He currently serves as Editor-in-Chief of the international journal RAIRO-Operations Research and Area Editor of the journal Computers and Industrial Engineering.
