Linking mathematical programming formalism with combinatorial optimization formalism, through the study of generic scheduling and network synthesis problems – LMCO

This project is a three year project which puts together people who used to respectively work on Discrete Mathematics, Combinatorial Optimization, Mathematical Programming, and embedded systems. Those people are located in three laboratories: - LIP6 Laboratory in PARIS VI, team animated by Philippe CHRETIENNE and mainly dedicated to Scheduling; - HEUDYASIC Laboratory, U.T Compiègne, team animated by Jacques CARLIER, dedicated to Combinatorial Optimization and applications; - LIMOS Laboratory in Clermont-Ferrand, UMR CNRS 6158: this laboratory may prevail itself with a good ability in the field of network synthesis and mathematical programming. It contains pluridisciplinarity in the sense that those people have most often been using very distinct formalisms and have also been applying them in very different contexts. It also contains pluridisciplinarity in the sense that, by focusing on the “time dimension” in the management of Operations Research problem, it makes people working in this field to get closer to people working on embedded systems, until defining a kind of “Embedded Operations Research” problems. Thus this project first aims at unifying, or at least at getting closer, several kinds of formalisms which prevail in Operations Research, namely the Combinatorial Optimization formalism (partially ordered sets, task sets, temporal constraints, disjunctive constraints, constraint propagation, heuristics scheme…) associated with planning and scheduling, and the Mathematical Programming formalism associated with network synthesis models (flow and multicommodity flow, linear and convex optimization machinery, decomposition scheme, duality, polyhedral methods…). It also aims at linking routing and scheduling algorithmic approaches which are implemented in order to deal with static data, without any kind of real time constraint, to the way decision rules must be designed in order to handle dynamic data, that means in order to deal with the kind of reactivity constraints and communication devices which one must take into account when driving real dynamic systems (for instance transportation or production systems). It includes a theoretical part, dedicated to models and algorithms, and a practical part, which focuses on software test and development and on the way some applied scheduling, routing and resource management problems may be cast into our distinct theoretical framework. The first working package of this project will be made of an analysis of the way the classical network synthesis formalism, which is usually dedicated to long term decision problems related to telecommunication and production systems may be extended in order to capture the “Time” dimension. It will lead us to introduce a notion of Timed Flow, together with a generic scheduling problem P-SCH with extended disjunctive constraints and a non standard optimization criterion. We shall use them in order to match classical combinatorial optimization (constraint propagation, greedy list scheme…) approaches with approaches inherited from the mathematical programming machinery (duality, subdifferentiality…), and in order to compare them both from a formal point of view and from an experimental point of view. While performing experiments, focus on the notion of “a posteriori complexity”, with the purpose clearly identifying what are the difficult instances of a problem, and what are the true causes for the different behaviour of several algorithmic scheme. A second working package will be made of a study of the way classical CFA (Capacitated Flow Assignment) models, which are commonly used in order to manage long term telecommunication network design problems, may be extended in order to include a scheduling dimension. This study will in turn allow us to model a middle term and short term routing and load assignment transportation reference problem P-ROUT. Most routing/scheduling problems usually admit a static version (all data are known in advance, and the computer deals only one time with them), and a dynamic version (data are “on line”, and the computer handles them in a reactive way). It will be specially the case of the P-ROUT problem, which may arise as a control problem for highly mobile distributed systems. Therefore, a third working package will be dedicated to the study of the way the results of a static case algorithmic analysis may be formally used in order to make easier the design of reactive algorithmic patterns (Embedded Operations Research problems). A last working package will be dedicated to an identification of emerging practical applications of timed flows and of the scheduling and routing problems P-SCH and P-ROUT.