Méthodes de décomposition pour la parallélisation du simplexe en nombres entiers

SPP is an integer linear programming problem that is used to model many industrial problems such as personnel scheduling, logistics and pattern recognition. In the transport industry, it consists of partitioning a set of tasks ( plane flights, bus itinerary segments, ...) into subsets (rotation of navigating personnel) so that the selected subsets have a minimum total cost and each task belongs exactly to one subset. Usually, SPP is solved by the branch and bound method or its variants. These methods are known to be slow in the case of large and difficult problems. However, in industry it is appreciated to have a solution as quickly as possible and to consider available information such as the existence of an initial solution, especially in the re-optimization case. This aspect is easily provided by the primal methods which from an initial solution produce a sequence of decreasing cost solutions that converge towards an optimal or near optimal solution. The Integral Simplex Using Decomposition, ISUD, is a primal method dedicated to solve SPP. At each iteration, it decomposes the original problem into two sub-problems. The first, called the reduced problem (RP), only considers the so-called compatible columns with the current solution. The second, called the complementary problem (CP), deals only with the columns that are incompatible with the current solution. The complementary problem makes it possible to find a descent direction composed of several variables that could be fractional or integer solution. In the case of fractional solutions, a branching often leads to an integer solution. Nowadays, computing science evolves impressively. The transformation of computer hardware into speedy machines is spectacular : a current laptop is equivalent to the 1970s biggest machines. The current trend is to produce multi-core processors and to design and implement parallel computing techniques. The general objective of this thesis is to study and apply parallel computing techniques to ISUD.We propose parallel implementations of ISUD in order to improve its performances and to profit from the contemporary evolution of the computer science. To design these algorithms we have exploited parallelism within ISUD and introduced specific decompositions. At first, we group the columns of the current solution into clusters in order to decompose the initial problem into independent sub-problems. These will be solved in parallel to get an improving solution by combining the sub-problems optimal solutions. To do so, we construct a graph whose nodes are the current solution columns. The edge (i, j) weight is computed by weighting functions that use the information from the original problem such as the number of columns that span two columns Ai and Aj of the current solution. Then, the constructed graph is split into sub graphs and as a result to a set of the current solution clusters. Thus, we add a second dynamic decomposition to the RP-CP one which is intrinsic to ISUD.We obtain a parallel algorithm, The Integral Simplex Using Double Decomposition, called ISU2D. We tested it on instances of bus drivers having up to 1600 constraints and 570000 variables. The ISU2D reduces the computing time of ISUD by a factor of 3, even 4 for some instances. It reaches an optimal or near optimal solution for the majority of these instances in less than 10 min while the commercial solver CPLEX cannot even find a feasible solution with a gap that is less than 10 % after a one-hour time limit. But, ISU2D suffers of the limitation which is the use of a single decomposition of the current solution at a time. In a second step, we improve our algorithm by generalizing the second decomposition concept. Indeed, our goal is to use multiple dynamic decompositions simultaneously. We propose an algorithm, called DISUD, a distributed algorithm based on ISUD and the multi-agent system (MAS). Each agent is an entity that is, at least partially, autonomous and characterized by the dynamic decomposition that it applies. We implemented two variants where agents can be independent or cooperating according to the strategy adopted. Thus, we increase the performance of ISU2D and benefit more from computing hardware evolution. We tested DISUD on airplane flight scheduling problems. The obtained results show that DISUD is better than DCPLEX, the distributed version of the advanced CPLEX commercial solver on our test instances. It achieves better quality solutions than the DCPLEX and reduces the computing time by an average factor of 4 to 5 for some instances. In addition, it solved large instances that the DCPLEX could not improve after a one-hour time limit. In a third work, we integrate the DISUD in a column generation context (GC). This choice is justified by the fact that the coupling of the method of generating columns with enumeration methods such as branch and price is widely used in industry. ISUD has potential to replace the usual enumeration methods to solve the SPP. As a result, there is potential to integrate GC and DISUD to address industry issues. We develop DICG a column generation algorithm which uses DISUD instead of enumeration methods. The results that we obtained during our tests showed that DICG solutions are of good quality (less than 1%). Moreover, it reduces the time of computation by a factor of 2 or even 4 compared to the DRMH, a distributed version of the Restricted Master heuristic. Thus, we have contributed to ISUD evolution. In addition, we improved the performances of ISUD and reduced its computing time. Furthermore, we paved the way for future work to expand the uses of the distributed version of ISUD.