Download Free Etude Et Conception Dalgorithmes Paralleles Doptimisation Combinatoire Discrete Book in PDF and EPUB Free Download. You can read online Etude Et Conception Dalgorithmes Paralleles Doptimisation Combinatoire Discrete and write the review.

LES METAHEURISTIQUES DE TYPE RECUIT SIMULE OU METHODE TABOU SONT DES OUTILS PUISSANTS ET RECONNUS POUR OBTENIR DES SOLUTIONS APPROCHEES AUX PROBLEMES D'OPTIMISATION COMBINATOIRE DE GRANDE TAILLE. SI ELLES SONT RELATIVEMENT FACILES A METTRE EN UVRE, ELLES NECESSITENT UN CERTAIN SAVOIR-FAIRE POUR REGLER LES DIFFERENTS PARAMETRES AFIN D'AJUSTER LEUR CONVERGENCE ET, PAR LA MEME, ACCELERER L'OBTENTION D'UNE BONNE SOLUTION. PLUSIEURS PARALLELISATIONS ONT DEJA ETE PROPOSEES POUR AMELIORER LEUR RAPIDITE MAIS, POUR CHAQUE PROBLEME A RESOUDRE, SE POSENT A NOUVEAU LES QUESTIONS: QUELLE HEURISTIQUE CHOISIR ? QUELLE STRATEGIE DE PARALLELISATION ? DE PLUS, IL EST NECESSAIRE D'ECRIRE UN NOUVEAU PROGRAMME POUR CHAQUE NOUVELLE IMPLANTATION SUR UNE MACHINE PARALLELE. FACE A CES DIFFICULTES, NOTRE APPROCHE CONSISTE EN LA CONCEPTION D'UNE BIBLIOTHEQUE DE FONCTIONS PARALLELES (LOREST), PERMETTANT D'EXPERIMENTER PLUSIEURS PARALLELISATIONS DES METAHEURISTIQUES A PARTIR D'UN MEME PROGRAMME SEQUENTIEL. LA BIBLIOTHEQUE LOREST PRESENTE UNE ARCHITECTURE EN COUCHES. ELLE PERMET UNE IMPLANTATION INDEPENDANTE DE LA MACHINE CIBLE ET CONSTITUE, POUR L'ESSENTIEL, UNE MACHINE VIRTUELLE DE COMMUNICATION. NOUS PRESENTONS DEUX IMPLANTATIONS DE LOREST REALISEES, L'UNE SUR UNE MACHINE TNODE DE TELMAT EQUIPEE DE 16 TRANSPUTERS ET, L'AUTRE, SUR UN RESEAU DE STATIONS DE TRAVAIL, AU DESSUS DE LA BIBLIOTHEQUE DE COMMUNICATION PARALLEL VIRTUAL MACHINE (PVM). LE TRAVAIL EXPERIMENTAL A CONSISTE A TESTER DIFFERENTES STRATEGIES DE PARALLELISATION SUR DEUX PROBLEMES CLASSIQUES (AFFECTATION QUADRATIQUE ET VOYAGEUR DE COMMERCE), AINSI QUE SUR UN PROBLEME DE RECHERCHE DE CHEMIN HAMILTONIEN DANS LES GRAPHES CUBIQUES. CE DERNIER TRAVAIL A DONNE LIEU A LA MISE AU POINT D'UNE METHODE DE DISTORSION DE LA FONCTION DE COUT TELLE QUE LA MOYENNE DES SAUTS D'ENERGIE RESTE APPROXIMATIVEMENT CONSTANTE AU COURS DU CALCUL. CETTE METHODE S'EST AVEREE TRES EFFICACE AVEC LE RECUIT SIMULE
ETUDE DE LA TERMINAISON DISTRIBUEE. RECHERCHE DES PLUS COURTS CHEMINS DANS UN GRAPHE VALUE, RECHERCHE D'UN ARBRE COUVRANT, ENUMERATION IMPLICITE PARALLELE SONT 3 PROBLEMES COMBINATOIRES POUR LESQUELS EST DONNEE LA PARTICULARISATION A UN ENVIRONNEMENT PARALLELE TYPE PRAM
This book contains papers presented at the Workshop on Parallel Processing of Discrete Optimization Problems held at DIMACS in April 1994. The contents cover a wide spectrum of the most recent algorithms and applications in parallel processing of discrete optimization and related problems. Topics include parallel branch and bound algorithms, scalability, load balancing, parallelism and irregular data structures and scheduling task graphs on parallel machines. Applications include parallel algorithms for solving satisfiability problems, location problems, linear programming, quadratic and linear assignment problems. This book would be suitable as a textbook in advanced courses on parallel algorithms and combinatorial optimization.
Cette thèse est divisée en trois parties : la première partie, précédée d'un chapitre 0 qui précise et justifie vocabulaire et notations, est composée de deux chapitres I et II, qui traitent du problème de la terminaison distribuée, apprentissage et détection, l'idée maîtresse étant celle de "mot circulant" qui généralise le concept de jeton circulant. Le mot circulant permettant un apprentissage de propriétés de l'algorithme distribué étudié. Le chapitre II fournit de plus un algorithme distribué d'identification des circuits élémentaires d'un graphe. La deuxième partie est consacrée à l'étude de trois grands problèmes combinatoires tels que : La recherche des plus courts chemins dans un graphe valué, pour la résolution duquel nous réutilisons des concepts du chapitre II et pour lequel l'algorithme distribué que nous construisons se distingue des autres algorithmes connus par sa totale asynchronicité. (Chapitre III). La recherche d'un arbre couvrant (chapitre IV) pour laquelle, en allant à contrario de quelques idées établies sur la question, on donne un algorithme distribué totalement asynchrone, minimisant le nombre de messages échangés, et ce, malgré des hypothèses moins restrictives (en particulier, nous admettons la possibilité d'arêtes équipondérées) que les autres algorithmes distribués élaborés pour ce faire. L'énumération implicite parallèle (chapitre V) pour laquelle on fait apparaître, en environnement parallèle, des phénomènes nouveaux, en particulier à propos des gains de performance en temps, qui tranchent avec quelques idées largement répandues. Pour ces trois chapitres, nous donnons la particularisation à un environnement parallèle type machine à mémoire partagée (PRAM), et pour les chapitres III et V, nous donnons, en annexe, les programmes, jeux d'essais et résultats de tests sur CRAY. La troisième partie, tirant les enseignements théoriques des deux précédentes, essaie de donner une définition du concept d'algorithme parallèle et distribuée qui soit cohérente avec ce qui se fait en séquentiel, et qui permette une évaluation et une comparaison des algorithmes parallèles ou distribués (chapitre VI). Le, tri, fusion, et le problème de l'arbre couvrant minimum du chapitre VII est une application du modèle du chapitre VI à quatre problèmes; recherche du maximum IV
LE BUT DE CETTE THESE EST D'ETUDIER LA PARALLELISATION DES ALGORITHMES DES FAMILLES A* ET MINIMAX, ISSUES DE L'INTELLIGENCE ARTIFICIELLE, POUR LES PROBLEMES D'OPTIMISATION COMBINATOIRE. DANS LES DEUX PREMIERS CHAPITRES, NOUS MONTRONS QUE CES METHODES UTILISENT LE MEME PARADIGME D'EXPLORATION D'ESPACES DE RECHERCHE QUE LES ALGORITHMES BRANCH AND BOUND ET DEGAGEONS LES PARTIES SUSCEPTIBLES A ETRE PARALLELISEES. LE TROISIEME CHAPITRE FAIT LE POINT SUR L'EVOLUTION DES MACHINES PARALLELES, LES DIFFERENTS TYPES DE PARALLELISME POSSIBLES DANS UNE EXPLORATION D'ESPACE DE RECHERCHE ET LES TRAVAUX ANTERIEURES DES FAMILLES A* ET MINIMAX. NOUS PROPOSONS, AU CHAPITRE QUATRE, UNE NOUVELLE STRUCTURE DE DONNEES APPELEE CONCURRENT TREAP, A DOUBLE CRITERE (PRIORITE ET CLE) ET ACCES CONCURRENT POUR UNE IMPLANTATION PARALLELE EFFICACE DE A* (CAS). CETTE STRUCTURE PERMET D'EVITER LE PROBLEME D'INTERBLOCAGE DES STRUCTURES COMBINEES CLASSIQUES. LE CHAPITRE CINQ PRESENTE UN MODELE THEORIQUE POUR LA FAMILLE MINIMAX, PERMETTANT LE CALCUL DES BORNES D'ACCELERATION ET D'EFFICACITE POUR UN ARBRE UNIFORME DONNE. DEUX PARALLELISATIONS DE L'ALGORITHME ALPHA-BETA SONT PROPOSEES DANS LE DERNIER CHAPITRE. L'UNE (SABA), POUR MACHINES SIMD A PARALLELISME MASSIF, PERMET LA VALIDATION DU MODELE THEORIQUE. L'AUTRE (CABP), POUR MACHINES MIMD A MEMOIRE PARTAGEE, EST FONDEE SUR L'EXPLORATION D'UN ARBRE CRITIQUE ET L'INTRODUCTION D'UN DEGRE D'ELAGAGES CONCURRENT K. CE PARAMETRE AUTORISE UN CONTROLE DYNAMIQUE DU SURCOUT D'EXPLORATION EN COURS DE RECHERCHE
LE TRAVAIL DE CETTE THESE PORTE SUR LA CONCEPTION D'ALGORITHMES PARALLELES POUR LA RESOLUTION DE DEUX CLASSES DE PROBLEMES D'OPTIMISATION DANS LES GRAPHES : LES PROBLEMES DE FLOT DE COUT MINIMUM A CRITERE CONVEXE ET LES PROBLEMES DE TYPE FLOT MAXIMUM/COUPE MINIMALE. IL CONCERNE EGALEMENT LA MISE EN UVRE DE CES ALGORITHMES SUR DES MACHINES PARALLELES A MEMOIRE DISTRIBUEE ET A MEMOIRE PARTAGEE. DANS LA PREMIERE PARTIE DU DOCUMENT, NOUS NOUS INTERESSONS AU PROBLEME DE FLOT DE COUT MINIMUM A CRITERE CONVEXE. LES METHODES DE GRADIENT ET DE RELAXATION PERMETTANT DE RESOUDRE CETTE CLASSE DE PROBLEME SONT PERFORMANTES ET BIEN ADAPTEES A UNE MISE EN UVRE PARALLELE. NOUS NOUS CONCENTRONS PRINCIPALEMENT SUR LES METHODES ITERATIVES PARALLELES DEPOURVUES D'UN CONTROLE DES ITERATIONS, APPELEES ITERATIONS ASYNCHRONES. APRES UN RAPPEL DE LEUR FORMULATION ET DE RESULTATS DE CONVERGENCE, NOUS PRESENTONS UNE EXTENSION OFFRANT UNE PLUS GRANDE SOUPLESSE DANS LA COMMUNICATION DES ITERES PARTIELS ENTRE LES PROCESSEURS : LES ITERATIONS ASYNCHRONES AVEC COMMUNICATION FLEXIBLE. NOUS VALIDONS CETTE NOUVELLE APPROCHE PAR L'EXPERIMENTATION SUR DEUX ARCHITECTURES PARALLELES : LE T-NODE (MEMOIRE DISTRIBUEE) AINSI QU'UN MULTIPROCESSEUR SUN SMP (MEMOIRE PARTAGEE). LA SECONDE PARTIE DU MEMOIRE EST CONSACREE AU PROBLEME DE FLOT MAXIMUM/COUPE MINIMALE, QUI EST UN CAS PARTICULIER DU PROBLEME DE FLOT DE COUT MINIMUM A CRITERE LINEAIRE. DANS UN PREMIER TEMPS, NOUS PRESENTONS LE PROBLEME AINSI QUE LES DEUX PRINCIPALES CLASSES D'ALGORITHMES SEQUENTIELS PERMETTANT DE LE RESOUDRE : LES ALGORITHMES BASES SUR UNE CHAINE AMELIORANTE ET CEUX BASES SUR LA NOTION DE PREFLOT. DANS UN SECOND TEMPS, NOUS COMPARONS LES PERFORMANCES DE CES ALGORITHMES POUR DES PROBLEMES DE TOPOLOGIE DIFFERENTE A PARTIR D'EXPERIMENTATIONS NUMERIQUES. NOUS PROPOSONS ENFIN UNE STRATEGIE DE PARALLELISATION DU PREFLOT PAR L'UTILISATION DE THREADS SUR ARCHITECTURE FAIBLEMENT PARALLELE.
L'OPTIMISATION DISCRETE EST LE NOYAU FEDERATEUR DE LA THESE. POUR RESOUDRE LES PROBLEMES NP-COMPLETS DU DOMAINE, LES TROIS DIRECTIONS SUIVANTES SONT EXPLOREES : (I) LA CONCEPTION D'ALGORITHMES EFFICACES PAR LA VOIE D'HYBRIDATION DES TECHNIQUES CLASSIQUES DE RESOLUTION, AINSI QUE PAR L'EXPLOITATION DES PROPRIETES FONDAMENTALES DU PROBLEME ; (II) L'ELABORATION DE METHODES HEURISTIQUES POUR TRAITER DES INSTANCES INACCESSIBLES PAR LES METHODES EXACTES ; (III) L'UTILISATION PERFORMANTE DU PARALLELISME POUR LA RESOLUTION DES PROBLEMES COMBINATOIRES. L'APPLICATION D'OPTIMISATION DISCRETE DANS LE PARALLELISME EST AUSSI ABORDEE DANS LA THESE. LA PARALLELISATION EFFICACE D'UN ALGORITHME ENGENDRE DE NOMBREUX PROBLEMES D'OPTIMISATION DISCRETE, LIES A L'EQUILIBRAGE DE CHARGE ENTRE PROCESSEURS, A LA GRANULARITE OPTIMALE DU CALCUL ET A LA REDUCTION DU SURCOUT DE COMMUNICATION. THEMES PRINCIPAUX : (I) PROBLEME DE CLASSIFICATION (PROBLEME D'ANALYSE DISCRIMINANTE LINEAIRE) - CONCEPTION D'ALGORITHMES EFFICACES SEQUENTIELS ET PARALLELES ; (II) PROBLEME DE SAC-A-DOS MULTIDIMENSIONNEL EN VARIABLES 0-1 - HYBRIDATION DE PROGRAMMATION DYNAMIQUE ET UN SYSTEME DE BORNES ; (III) ORDONNANCEMENT DE SYSTEMES D'EQUATIONS RECURRENTES AFFINES - UTILISATION DE PROGRAMMATION LINEAIRE ET COMPARAISON DES METHODES DIFFERENTES ; (IV) PROBLEME DE PAVAGE OPTIMAL DE L'ESPACE D'ITERATIONS POUR PARALLELISATION DE NIDS DE BOUCLES - DETERMINATION DE PARAMETRES OPTIMAUX DU PAVAGE ET APPLICATION DE L'APPROCHE POUR COMPARAISON DE SEQUENCES GENOMIQUES.
Solving combinatorial optimization problems can often lead to runtime growing exponentially as a function of the input size. But important real-world problems, industrial applications, and academic research challenges, may demand exact optimal solutions. In such situations, parallel processing can reduce the runtime from days or months, typical when one workstation is used, to a few minutes or even seconds. Partners of the CEC-sponsored SCOOP Project (Solving Combinatorial Optimization Problems in Parallel) contributed, on invitation, to this book; much attention was paid to competent coverage of the topic and the style of writing. Readers will include students, scientists, engineers, and professionals interested in the design and implementation of parallel algorithms for solving combinatorial optimization problems.