Cette thèse développe les deux approches locales et globales basées sur la programmation DC et DCA pour l'optimisation combinatoire en variables mixtes 0-1 et leurs applications à la résolution de nombreux problèmes en planification opérationnelle. Plus particulièrement, cette thèse adresse à: l'amélioration de l'algorithme d'approximation extérieure basée sur DCA (appelé DCACUT) introduit par Nguyen V.V. et Le Thi pour la programmation linéaire en variables mixtes 0-1, les combinaisons des algorithmes globaux et DCA et l'étude numérique comparative de ces approches pour la programmation linéaire en variables mixtes 0-1, l'utilisation de DCA à la résolution de la programmation DC en variables mixtes 0-1 en utilisant la pénalité exacte, la mise en œuvre des algorithmes développés à la résolution des problèmes de grande taille en planification opérationnelle comme les problèmes dans le réseau de télécommunication sans fils, les problèmes d’ordonnancement ainsi que le problème d'affectation de tâches des véhicules aériens non pilotés ou bien le problème des tournées de véhicules dans une chaîne d'approvisionnement / This thesis develops two local and global approaches based on DC programming and DCA for mixed 0-1 combinatorial optimization and their applications to many problems in operational planning. More particularly, this thesis consists of: the improvement of the outer approximation algorithm based on DCA (called DCACUT) introduced by Nguyen V.V and Le Thi for mixed 0-1 linear programming, the combinations of global algorithms and DCA and the comparative numerical study of these approaches for mixed 0-1 linear programming, the use of DCA for solving mixed 0-1 programming via an exact penalty technique, the implementation of the algorithms developed for solving large scale problems in operational planning: two problems in wireless telecommunication network, two scheduling problems, an UAV task assignment problem and an inventory routing problem in supply chains

L'algorithme Branch-and-Bound (B&B) est une méthode de recherche arborescente fréquemment utilisé pour la résolution exacte de problèmes d'optimisation combinatoire (POC). Néanmoins, seules des petites instances peuvent être effectivement résolues sur une machine séquentielle, le nombre de sous-problèmes à évaluer étant souvent très grand. Visant la resolution de POC de grande taille, nous réexaminons la conception et l'implémentation d'algorithmes B&B massivement parallèles sur de larges plateformes hétérogènes de calcul, intégrant des processeurs multi-coeurs, many-cores et et processeurs graphiques (GPUs). Pour une représentation compacte en mémoire des sous-problèmes une structure de données originale (IVM), dédiée aux problèmes de permutation est utilisée. En raison de la forte irrégularité de l'arbre de recherche, l'équilibrage de charge dynamique entre processus d'exploration parallèles occupe une place centrale dans cette thèse. Basés sur un encodage compact de l'espace de recherche sous forme d'intervalles, des stratégies de vol de tâches sont proposées pour processeurs multi-core et GPU, ainsi une approche hiérarchique pour l'équilibrage de charge dans les systèmes multi-GPU et multi-CPU à mémoire distribuée. Trois problèmes d'optimisation définis sur l'ensemble des permutations, le problème d'ordonnancement Flow-Shop (FSP), d'affectation quadratique (QAP) et le problème des n-dames sont utilisés comme cas d'étude. La resolution en 9 heures d'une instance du FSP dont le temps de résolution séquentiel est estimé à 22 ans demontre la capacité de passage à l'échelle des algorithmes proposés sur une grappe de calcul composé de 36 GPUs. / Branch-and-Bound (B&B) is a frequently used tree-search exploratory method for the exact resolution of combinatorial optimization problems (COPs). However, in practice, only small problem instances can be solved on a sequential computer, as B&B generates often generates a huge amount of subproblems to be evaluated. In order to solve large COPs, we revisit the design and implementation of massively parallel B&B on top of large heterogeneous clusters, integrating multi-core CPUs, many-core processors and GPUs. For the efficient storage and management of subproblems an original data structure (IVM) dedicated to permutation problems is used. Because of the highly irregular and unpredictable shape of the B&B tree, dynamic load balancing between parallel exploration processes is one of the main issues addressed in this thesis. Based on a compact encoding of the search space in the form of intervals, work stealing strategies for multi-core and GPU are proposed, as well as hierarchical approaches for load balancing in distributed memory multi-CPU/multi-GPU systems. Three permutation problems, the Flowshop Scheduling Problem (FSP), the Quadratic Assignment Problem (QAP) and the n-Queens puzzle problem are used as test-cases. The resolution, in 9 hours, of a FSP instance with an estimated sequential execution time of 22 years demonstrates the scalability of the proposed algorithms on a cluster composed of 36 GPUs.

Particle Image Velocimetry (PIV) based pressure field calculation is becoming increasingly popular in experimental fluid dynamics due to its non-intrusive nature. Errors propagated from PIV results to pressure field calculations are unavoidable, and in most cases, non-negligible. However, the specific dynamics of this error propagation process have not been unveiled. This dissertation examines both why and how errors in the experimental data are propagated to the pressure field by direct analysis of the pressure Poisson equation. Error in the pressure calculations are bounded with the error level of the experimental data. The error bounds quantitatively explain why and how many factors (i.e., geometry and length scale of the flow domain, type of boundary conditions) determine the resulting error propagation. The reason that the type of flow and profile of the error matter to the error propagation is also qualitatively illustrated. Numerical and experimental validations are conducted to verify these results. The results and framework introduced in this research can be used to guide the optimization of the experimental design, and potentially estimate the error in the reconstructed pressure field before performing PIV experiments.

Previous investigators have indicated that low socio-economic students have difficulty experiencing success on tests heavily loaded with verbal material. Differences in personality characteristics between students of high and low creativity have also been found. The purpose of the present study was to investigate the influence of manifest needs and anxiety on creative thinking. The Taylor Manifest Anxiety Scale, which determines anxiety level, the Edwards Personal Preference Schedule, which measures manifest needs, and the Torrance Tests of Creative Thinking, which provides an index of creativity were administered to Spanish-American, Anglo-American, Negro, and Navaho high school students, who constituted the 1967 Upward Bound population at Utah State University. The total sample, composed of the four ethnic backgrounds, was administered the Torrance Tests of Creative Thinking. The students were ranked on the basis of their total creativity score, and high and low creativity groups were extracted at the median. The results indicate that Upward Bound students are significantly higher in figural than in verbal creativity. No significant differences between high and low creativity students were found on anxiety or manifest needs, although a negative trend between anxiety and creativity was suggested.

This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.

In the paper, we minimize the holding cost of the safety stock held in a supply chain modeled as a general network. By our assumption, the demand is bounded by a concave function. This fact allows us to formulate the problem as a deterministic optimization. We minimize a concave function over a discrete polyhedron. The main goal of the paper is to describe an algorithm to solve the problem without assuming any particular structure of the underlying supply chain. The algorithm is a branch and bound algorithm. / Singapore-MIT Alliance (SMA)

This thesis studies Production Scheduling in a multistage hybrid flowshop facility. It first states the general Production Planning and Scheduling problem and highlights some drawbacks of classical solutions. A theoretical decomposition-based approach is introduced whose main issue is to overcome non-efficient capacity utilization. By using Branch and Bound methods, an in-depth analysis of the scheduling part of the system is then carried out throughout the study and development of upper and lower bounds as well as branching schemes. Already-existing and new heuristics are presented and compared on different shop floor configurations. Five different heuristic approaches are studied. By scheduling the HFS one stage at a time the first approach uses different stage sequencing orders. The second and third approaches are mainly list heuristics. The second approach uses ideas derived from the multistage classical flowshop with a single machine per stage, while the third approach uses classical dispatching priority rules. The fourth and fifth approaches, respectively, use random scheduling and local search techniques. Statistical analysis is carried out in order to compare the heuristics and to select the best of them for each shop configuration. Already-existing and new lower bounds on the single stage subproblem are also presented and compared. Three new lower bounds are developed: a dual heuristic based bound, a partially preemptive bound and a heuristic for the so-called subset bound. Some of these lower bounds use a network flow algorithm. A new version of the “Preflow Push” algorithm which runs faster than the original one is presented. The best lower bounds are selected based on numerical tests. Two branch and bound algorithms are presented, an improved version of the sequence enumeration method and a generalization of the so-called interval branching method, along with several bounding strategies. Based on the upper and lower bound studies, several branch and bound algorithms are presented and compared using numerical tests on different shop floor configurations. Eventually, an Object Model for Scheduling Algorithm Implementations (OMSAI), that has been used for the computer implementation of the developed algorithms, is presented.

We study two data structuring problems under the bit probe model: the dynamic predecessor problem and integer representation in a manner supporting basic updates in as few bit operations as possible. The model of computation considered in this paper is the bit probe model. In this model, the complexity measure counts only the bitwise accesses to the data structure. The model ignores the cost of computation. As a result, the bit probe complexity of a data structuring problem can be considered as a fundamental measure of the problem. Lower bounds derived by this model are valid as lower bounds for any realistic, sequential model of computation. Furthermore, some of the problems are more suitable for study in this model as they can be solved using less than $w$ bit probes where $w$ is the size of a computer word. The predecessor problem is one of the fundamental problems in computer science with numerous applications and has been studied for several decades. We study the colored predecessor problem, a variation of the predecessor problem, in which each element is associated with a symbol from a finite alphabet or color. The problem is to store a subset $S$ of size $n,$ from a finite universe $U$ so that to support efficient insertion, deletion and queries to determine the color of the largest value in $S$ which is not larger than $x,$ for a given $x \in U.$ We present a data structure for the problem that requires $O(k \sqrt[k]{{\log U} \over {\log \log U}})$ bit probes for the query and $O(k^2 {{\log U} \over {\log \log U}})$ bit probes for the update operations, where $U$ is the universe size and $k$ is positive constant. We also show that the results on the colored predecessor problem can be used to solve some other related problems such as existential range query, dynamic prefix sum, segment representative, connectivity problems, etc. The second structure considered is for integer representation. We examine the problem of integer representation in a nearly minimal number of bits so that increment and decrement (and indeed addition and subtraction) can be performed using few bit inspections and fewer bit changes. In particular, we prove a new lower bound of $\Omega(\sqrt{n})$ for the increment and decrement operation, where $n$ is the minimum number of bits required to represent the number. We present several efficient data structures to represent integers that use a logarithmic number of bit inspections and a constant number of bit changes per operation.

Racial equality in the United States educational system has long been and continues to be a source of debate. Specifically, the disparities between whites and other minority groups have been increasingly more critical. Blacks and Latinos consistently score lower than whites on standardized tests and academic course work. There have been several explanations given for poorer school performance by certain minority groups than whites. In this dissertation, I explore the black white achievement gap through the examination of one widely known explanation, oppositional culture theory. This research investigates the major tenets of oppositional culture theory and the contemporary multicultural navigator concept. Using a grounded theory method of analysis, I examine the connections between suppositions of the theory and black students in the Upward Bound academic achievement program.

This thesis is about solving the manpower planning problem concerning stangand transitioning of pilots. The objective of the planning is to have enoughpilots to satisfy the demand while minimizing the cost. The main decisions totake are how many pilots to hire, which pilots to train and which courses toschedule. The planning problems that arise are both large and dicult whichmakes it important to use ecient solution methods. Seniority rules betweenpairs of pilots are the most complicating factor.A major part in the solution process is the solving of mixed integer programs.The emphasis in the thesis is to develop and test adaptations of the branch andbound algorithm to solve mixed integer programs faster. One of these is abranching principle that takes a problem specic structure into account. Agraph of implications is constructed from the seniority rules and this graph isthen used to estimate the impact of each branching candidate. The implementedmethods outperform the software XPRESS on some instances, while for mostinstances the performance is comparable.