Optimization methods for the integrated study of complex decisional problems – ATHENA

Let A and B two decision problems considered.
• Assume that the decisions for both A and B are taken by the same decision maker (centralized context) and that the environment is static (known and reliable data). The integration of A and B can be tackled by decomposition methods induced by linear programming (Benders decomposition, Lagrangian decomposition, ...). This is the purpose of the task «Decomposition Approaches«.
• Suppose activities A and B are assigned to two agents denoted by A and B. Agent A can have an objective to realize or to minimize, which is not related to the purpose of agent B. However, the decisions taken by agent A may have an impact on the performances of agent B and vice versa. The problem is to build a solution to the integrated problem that is a compromise acceptable by both agent A and B. The task «multi-agent approaches« is placed in this context.
• Again, assuming that problems are assigned to agents, we now consider that the decision is distributed. In other words, agents A and B are autonomous in their own decisions. The objective is to develop cooperation mechanisms necessary for both agents to make decisions that are generally suitable for all, that is to say, decisions that lead to a balance. The task «cooperative approaches« is devoted to this case and makes a link with traditional issues of cooperative game theory.
• Finally, we assume that the context is centralized and dynamic and subject to many uncertainties such as the arrival of new tasks to be processed, uncertainties on parameters, hazards, etc. In this context, the main issue is robustness. This is the purpose of the task «robust and flexible approaches - dynamic environment.«

The project's development strategy is based primarily on partner publications. All members of the project (with the exception of young people) are researchers who are used to produce articles in the best journals of the field, and some have a great editorial experience. The research topic is quite relevant and the work can - if the results are there - provide good results. The journals where project members are used to publish are European Journal of Operational Research, Computers and Operations Research, International Journal of Production Economics, International Journal of Production Research, etc.

The project will also contribute to the formation of several Master students, through 5 stages funded by the project (3 at Heudiasyc and 2 at LAAS), plus engineering student projects and internships of our students (UTC - Compiegne ISIMA - Clermont-Ferrand, Polytech'Tours, INSA Toulouse, ENSEEIHT - Toulouse), which will also contribute to the progress of work, but for which no specific budget has been requested. The engineers in the end of their curriculum have also projects that can be either in relation to private partners or on research topics. The project will provide naturally beautiful research projects for engineering students.

As part of the proposed collaborations, the one concerning the preparation of chemotherapy and distribution with the Tours University Hospital may have implications that go beyond the Operational Research community. Collaborations in the past with this unit have led to publications in the pharmaceutical sector [Aubert et al., 2009] and communications in professional journals.

There are many research perspectives because there are many problems covered by the field of the project, because the approaches are multiple and because for each approach, many resolution methods can be used. There are necessarily numerous research perspectives on each addressed problem.
There will be some interesting perspectives in the field of transfer and valorisation. Real case identification and their resolution remains a difficult challenge, but important in an operational researcher approach. A first real case application exists at Tours University Hospital for the production and distribution of chemotherapy, and this real context may well lead to the implementation of this research, of course with additional work (algorithms are not sufficient, an industrial partnership is also required, equipment, specific development, etc.).

Moukrim A., Quilliot A., Toussaint H., An effective branch-and-price algorithm for the Preemptive Resource Constrained Project Scheduling Problem based on minimal Interval Order Enumeration, EJOR (2015).
A. CHEREF, J-C. BILLAUT, C. ARTIGUES, Une approche robuste pour un problème d'ordonnancement et de VRP intégrés, 15ème congrès de la Société de la Société Française de Recherche Opérationnelle et d'Aide à la Décision Roadef’2014, Bordeaux, février 2014.
A. CHEREF, T. BOUCHARD, J-C. BILLAUT, C. ARTIGUES, Un algorithme tabou pour résoudre, grâce aux groupes d’opérations permutables, un problème d’ordonnancement et de routing robuste, 10ème Conférence Internationale de MOdélisation, Optimisation et SIMulation - MOSIM’14 - 5 au 7 Novembre 2014 – Nancy
Azeddine Cheref, Alessandro Agnetis, Christian Artigues, Jean-Charles Billaut, Problème d’ordonnancement et de distribution intégrés, in ROADEF 2015
Afifi, S. and Guibadj, R.-N. and Moukrim, A. New Lower Bounds on the Number of Vehicles for the Vehicle Routing Problem with Time Windows 11th International Conference, CPAIOR 2014, Cork, Ireland, May 19-23, 2014., Cork, Irlande, vol. 8451, pp. 422-437, series: LNCS, 2014
N. Chaabane Fakhfakh, C. Briand and M-J. Huguet. A Multi-Agent Min-Cost Flow problem with Controllable Capacities - Complexity of Finding a Maximum-Nash Equilibrium. Proceedings of International Conference on Operations Research and Enterprise Systems (ICORES 2014), pp. 27-34 (2014) – Best paper award
Leticia Vargas, Nicolas Jozefowiez, Sandra Ulrich Ngueveu: A Selector Operator Based Adaptative Large Neighborhood Search for the Covering Tour Problem, in LION 9 to appear in LNCS
N. Chaabane, C. Briand and M-J. Huguet. Finding Stable flows in multi-agent Networks under an equal-sharing policy. International Network Optimization Conference, INOC 2015 (accepté)

The optimization of complex decision-making process is the subject of studies in operations research and mathematical optimization for many years. Generally, the origin of the problems comes from an implicit cutting of the problematic, which was made taking into account the nature of the problems and of the obvious complexity of trying to treat them jointly. These problems are addressed in a very precise way and the difficulty lies in how to make them communicate. For example, in the context of the supply chain, production decisions are strongly related to inventory management decisions as well as distribution policy. However, the problems are most often discussed separately. Recently, thanks to the advances in optimization techniques, thanks to performing software available for researchers and to advanced technology, it is now possible to tackle problems of great complexity. For example, addressing some decisional problems in an integrated manner rather than separately is possible and it is established that it provides solutions of a great interest. The goal of the project is to address complex optimization problems at an operational level (for instance production scheduling and vehicle routing problems). So that the study is complete, multiple contexts are considered. First, we consider that the decision environment is centralized and static, it means that the data are known with certainty and do not vary in time. The techniques of combinatorial optimization based on decomposition are then preferred to seek optimal or near optimal solutions. Secondly, we consider that the environment is centralized and static but that the integrated decision problems have distinct objective functions, possibly conflicting. So, multi-agent approaches (n the sense of “competing agents”) are preferred and compromise solutions are searched. Thirdly, still in a static environment, we consider now that the decision is distributed and that each of the integrated problems is under the responsibility of an autonomous decision-maker. We have to consider the cooperation mechanisms between decision-makers and find balanced solutions. Finally, in a last part, we consider that the environment is dynamic; it means that the problem parameters may change over time. The proposed solution is disturbed and the problem is to find, according to the definition of uncertainties, to develop methods that find robust solutions.
Four partners are involved in the project: the “Laboratoire d’Informatique” of the University of Tours, the laboratory called Heudiasyc of the Université de Technologie de Compiègne, the LAAS-CNRS of Toulouse and the LIMOS of the University of Clermont-Ferrand. The project will last 48 months and the main funding request is composed of two co-supervised thesis (LI-LAAS and LIMOS-Heudiasyc).