Séminaire du GERAD : Structural analysis for conditional-algebraic systems: Polyhedra and branch-and-cut

Structural analysis for conditional-algebraic systems: Polyhedra and branch-and-cut

A. Ridha Mahjoub – LAMSADE, Université Paris-Dauphine, France

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 changment. 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.

-----

Entrée gratuite.
Bienvenue à tous!