Programmation dynamique | EPFL Graph Search

En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman. À l'époque, le terme « programmation » signifie planification et ordonnancement. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires. Elle a d'emblée connu un grand succès, car de nombreuses fonctions économiques de l'industrie étaient de ce type, comme la conduite et l'optimisation de procédés chimiques, ou la gestion de stocks. Principe vignette|149x149px|Le graphe de dépendance des sous-problèmes pour le calcul de F5, le 5ème terme de la suite de Fibonacci. Illustrons la programmation dynamique sur le calcul du nème terme de la suite de Fibonacci, parfois utilisé comme exemple introduct

Efficient Data Structures for Decision Diagrams

Nacereddine Ouaret

Dynamic Programming OPtimization (DPOP) is an algorithm proposed for solving distributed constraint optimization problems. In this algorithm, Hypercubes are used as the format of the messages exchanged between the agents. Then, Hybrid-DPOP (H-DPOP), a hybrid algorithm based on DPOP was proposed as an improved solution. Its main advantage over DPOP lies under the use of Multi-valued Decision Diagrams (MDDs) instead of Hypercubes. Furthermore, MDDs give a more compact representation of the messages. The MDDs were implemented and presented in by Kumar even though it was presented as Constrained Decision Diagrams (CDD) which is a generalization of MDDs. The first part of this project aims at implementing Hypercubes. An Implementation already exists. Therefore, the goal is to propose an implementation which is more efficient in term of speed and memory usage for the already implemented functions (join, project and slice). The solution implemented during this project should also provide new functions (split and re-order) and the possibility of saving Hypercubes in the XML format. The second part of the project consists in proposing and implementing a data structure that is more efficient than the MDDs implemented in H-DPOP. This data structure should also provide more functions, and also provide the possibility of saving data in the XML format.

2008

Extension d'algorithmes d'ordre zéro pour l'optimisation stochastique

Pierre Huguenin

The electrical discharge machining process (EDM) was discovered in the 1950s, and was then used essentially to destroy unrecoverable damaged screws. Since then, huge progress has been achieved in making this process reliable and able to perform the most complex machining operations on the most sophisticated materials. Two main processes use electrical discharge machining. First, Die Sinking EDM (DSEDM) in which an electrode, moved along a usually vertical axis, makes an imprint into a mechanical element ; second, Wire EDM (WEDM), uses a wire as an electrode and makes it possible to perform cut operations. Two specific aspects of the EDM process make it particularly challenging for optimization. First, the process evolves with the machining position. In the DSEDM process, where the electrode sinks deeply into the material, the fragments spawn by erosion (contamination) are trapped, thus modifying the sparking conditions. In the WEDM process, the main factors that drive the evolution of the process are the machining operations. Second, the measurements are very noisy, which is due to underlying, mainly random, physical phenomenon ; this is particularly true to spark triggering. The process evolution influences the single criterion to be minimized : total machining time. However, the latter is only known once the operations are completed. As a result, the whole history of manipulated variables influences the final criterion to minimize in this case of dynamic optimization. A major contribution of this work is a proof that a first-order model of the DSEDM process, with the machining position as a state variable, makes it possible to transform a dynamic optimization problem into a static optimization problem. The tools used in this demonstration are Pontryagin's Minimum Principle as well as Parametric Programming. The conclusion is that in order to achieve minimum machining time, maximum speed must be sought all along the trajectory. The online search for maximum speed is another important contribution of this thesis. Noisy efficiency functions are, indeed, known to be a significant challenge to the reliability of optimization algorithms. To address this issue the Golden Ratio Search and the Nelder-Mead Simplex algorithms were chosen as the starting point, as they do not rely explicitly on the gradient of the efficiency function. The addition of a further dilation condition makes these algorithms more effective in stochastic mode. This condition is based on the detection of contradictory measurement samples as compared to the shape of the efficiency function, which is assumed to be unimodal. As a result of this modification, the density of the final optimization points is well centred relative to the theoretical optimum, and dispersion is small. Moreover, the size of the search region for both algorithms never approaches zero. Consequently, as the machining conditions evolve, the optimizer can target a new optimum. This adaptability proves to be a significant improvement over existing algorithms. In the case of the DSEDM process, a simple model of the efficiency surface as a function of the control variables, which has been calibrated on sample measures, has allowed for a validation of the static optimization. For the WEDM process, conclusive results for the modified algorithms have been obtained both by simulation and during machine-based tests.

EPFL2005

Efficient Data Structures For Decision Diagrams

Stéphane Rabie

Dynamic Programming Optimization (DPOP) is an algorithm proposed to solve distributed constraint optimization problems. In order to represent the multi-values functions manipulated in this algorithm, a data structure called Hypercube was implemented. A more efficient data structure, the Utility Diagram, was then proposed as an alternative to the Hypercube. DPOP also required the implementation of several operations (such as join, project, slice, split and reorder) on these two data structures. This project is a follow-up of Nacereddine Ouaret’s master thesis, which consisted in implementing all of these data structures and theirs associated operations. As DPOP may have to work on very large decision diagrams, and perform a lot of successive operations on them, having implementations which are efficient in term of speed and memory is critical. The aim of this project was therefore to seek for new ways to improve the already implemented functions for hypercubes and utility diagrams, both in term of execution time and memory consumption. This report will thus first present a quick overview of hypercubes, utility diagrams, and their associated operations (a more complete description of these objects, as well as the details about their original implementation, can be found in Nacereddine Ouaret’s report on Efficient Data Structures for Decision Diagrams). The second part will then cover various improvements made to their implementation during the course of this project. Finally, a variant for the methods used by hypercube, more economical in term of memory as it reuses existing hypercubes rather than creating new ones, will be presented.

2009

Extension d'algorithmes d'ordre zéro pour l'optimisation stochastique

Pierre Huguenin

EPFL2005