Structures within very large displacement, mature fault zones, such as the North Branch San Gabriel Fault (NBSGF), are the product of a complex combination of processes. Off-fault damage within a damage zone and first-order geometric asperities, such as bends and steps, are thought to affect earthquake rupture propagation and energy radiation, but the effects are not completely understood. We hypothesize that the rate of accumulation of new damage decreases as fault maturity increases, and damage magnitude saturates in very large displacement faults. Nonetheless, geometric irregularities in the fault surface may modify damage zone characteristics. Accordingly, we seek to investigate the orientation, kinematics, and density of features at a range of scales within the damage zone adjacent to an abrupt 13 degree bend over 425 m in the NBSGF in order to constrain the relative role of the initiation of new damage versus the reactivation of preexisting damage adjacent to a bend. Field investigation and microstructural study focused on structural domains before, within, and after the fault bend on both sides of the fault. Subsidiary fault fabrics are similar in all domains outside the bend, which suggests a steady state fracture density and orientation distribution is established on the straight segments before and after the bend. The density of fractures within and outside the bend is similar; however, subsidiary fault orientations and kinematics are different within the bend relative to the straight segments. These observations are best explained by relatively low rates of damage generation relative to rates of fault reactivation during the later stages of faulting on the NBSGF, and that damage zone kinematics is reset as the host rock moves into the bend and again upon exiting the bend. Consequently, significant energy released during earthquake unloading can be dissipated by reactivation and slip on existing fractures in the damage zone, particularly adjacent to mesoscale faults. Thus, areas of heightened reactivation of damage, such as adjacent to geometric irregularities in the fault surface, could affect earthquake rupture dynamics.

Populus tremuloides Michx. (trembling aspen) is a tree species native to much of North America, characterized by an excurrent crown with horizontal to ascending branches and a dominant terminal leader. An unusual clone of trembling aspen was discovered in the 1940s near Hafford, Saskatchewan. This clone demonstrates abnormal crown morphology, in which vigorous shoots bend down, ultimately leading to an overall twisted or crooked appearance. The objectives of the present study were to investigate the mechanism of shoot bending by (1) characterizing the process and timing of bending, (2) evaluating structural aspects of developing wild-type and crooked aspen shoots, and (3) comparing anatomical features of bending shoots with wild-type shoots. L-system reconstruction models of 3-D digitized shoot development revealed dramatic bending midway through the growing season. Morphological analyses revealed that crooked aspen shoots had greater taper compared to the wild-type, typically known to create shoots resist deflection and bending. However, preliminary strength analyses indicated that crooked aspen shoots were less rigid, with smaller values of Young’s modulus compared to wild-type shoots. Anatomical investigations revealed differences in several structural tissues between developing wild-type and crooked aspen shoots, and differences within crooked aspen shoots. Primary phloem fibres on the upper side of bending shoots maintained relatively large lumens while those on the lower side were fully lignified, similar to those of mature vertically oriented wild-type leader shoots. These differences may result in differential extension growth early in development, and/or uneven mechanical support later on, ultimately resulting in bending due to self-weight. Gelatinous fibres (G-fibres), characteristic of tension wood (TW), were found throughout older wild-type and vertically oriented crooked aspen shoots; however, G-fibres were only found on the lower side of crooked aspen shoots. These lateral differences could have contributed to shoot bending by actively bending shoots downwards, or lack of TW on the upper side may not have prevented biomechanical bending from self weight. Nevertheless, shoot bending stops at the end of the growing season, suggesting that the mechanisms involved in creating bent shoots are only functional during the first growing season. / February 2006

Dans le domaine de l'Optimisation Combinatoire, la résolution de manière optimale de problèmes de grande taille par le biais d'algorithmes Branch-and-Bound requiert un nombre très élevé de ressources de calcul. De nos jours, de telles ressources sont accessibles grâce aux grilles de calcul, composées de grappes de clusters réparties sur différents sites géographiques. Ces environnements parallèles posent de nombreux défis scientifiques, notamment en termes de passage à l'échelle, de la prise en compte de l'hétérogénéité des ressources ainsi qu'en termes de tolérance aux pannes. La plupart des approaches existantes pour l'algorithme Branch-and-Bound parallèle sont basées sur une architecture de type Maître-Esclave, où un processus maître répartit les tâches à accomplir auprès de processus esclaves en charge de les traîter. L'utilisation d'une telle entité centrale constitue un obstacle majeur en ce qui concerne le passage à l'échelle. Dans cette thèse, nous proposons de relever ces défis ainsi que de surmonter cet obstacle grâce à une approche innovante et complètement distribuée, basée sur une architecture Pair-à-Pair (P2P). Celle-ci repose sur un seul type de processus (le pair), qui a pour mission d'explorer son propre ensemble de tâches, de le partager avec d'autres pairs et de diffuser l'information globale. Nous définissons des mécanismes adaptés en lien avec l'algorithme Branch-and-Bound, qui traitent de la répartition de la charge, de la diffusion de la meilleure solution trouvée et de la détection de la terminaison des calculs. En plus de multiples expérimentations sur le problème d'ordonnancement du Flow-Shop sur la grille de calcul Grid'5000, nous proposons une preuve formelle de la correction de notre approche. Par ailleurs, nous traîtons une problématique souvent ignorés dans les travaux relatifs au calcul P2P, qui est l'importance de la topologie du réseau P2P. Généralement, une topologie très simple est utilisée. Les résultats obtenus montrent que notre approche permet le déploiement de réseaux de calculs à de très grandes échelles, constitués potentiellement de centaines de milliers de coeurs de calcul. Notre dernière contribution consiste en une approche Pair-à-Pair tolérante aux pannes afin de prendre en compte la nature généralement très volatile des ressources de calcul. Les résultats obtenus prouvent la robustesse de l'approche dans des environnements à la fois réalistes et sujets à de nombreux dysfinctionnements

The minimum k-partition (MkP) problem is a well-known optimization problem encountered in various applications most notably in telecommunication and physics. Formulated in the early 1990s by Chopra and Rao, the MkP problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in different partitions. In this thesis, we design and implement a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. We describe and study the properties of two relaxations of the MkP problem, the linear programming and the semidefinite programming relaxations. We then derive a new strengthened relaxation based on semidefinite programming. This new relaxation provides tighter bounds compared to the other two discussed relaxations but suffers in term of computational time. We further devise an iterative clustering heuristic (ICH), a novel heuristic that finds feasible solution to the MkP problem and we compare it to the hyperplane rounding techniques of Goemans and Williamson and Frieze and Jerrum for k=2 and for k=3 respectively. Our computational results support the conclusion that ICH provides a better feasible solution for the MkP. Furthermore, unlike the hyperplane rounding, ICH remains very effective in the presence of negative edge weights. Next we describe in detail the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) to find optimal solution for the MkP problem. The ICH heuristic is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-cut tree. Finally, we present computational results for the SBC algorithm on several classes of test instances with k=3, 5, and 7. Complete graphs with up to 60 vertices and sparse graphs with up to 100 vertices arising from a physics application were considered.

The multiprocessor task graph scheduling problem has been extensively studied asacademic optimization problem which occurs in optimizing the execution time of parallelalgorithm with parallel computer. The problem is already being known as one of the NPhardproblems. There are many good approaches made with many optimizing algorithmto find out the optimum solution for this problem with less computational time. One ofthem is branch and bound algorithm.In this paper, we propose a branch and bound algorithm for the multiprocessor schedulingproblem. We investigate the algorithm by comparing two different lower bounds withtheir computational costs and the size of the pruned tree.Several experiments are made with small set of problems and results are compared indifferent sections.

The minimum k-partition (MkP) problem is a well-known optimization problem encountered in various applications most notably in telecommunication and physics. Formulated in the early 1990s by Chopra and Rao, the MkP problem is the problem of partitioning the set of vertices of a graph into k disjoint subsets so as to minimize the total weight of the edges joining vertices in different partitions. In this thesis, we design and implement a branch-and-cut algorithm based on semidefinite programming (SBC) for the MkP problem. We describe and study the properties of two relaxations of the MkP problem, the linear programming and the semidefinite programming relaxations. We then derive a new strengthened relaxation based on semidefinite programming. This new relaxation provides tighter bounds compared to the other two discussed relaxations but suffers in term of computational time. We further devise an iterative clustering heuristic (ICH), a novel heuristic that finds feasible solution to the MkP problem and we compare it to the hyperplane rounding techniques of Goemans and Williamson and Frieze and Jerrum for k=2 and for k=3 respectively. Our computational results support the conclusion that ICH provides a better feasible solution for the MkP. Furthermore, unlike the hyperplane rounding, ICH remains very effective in the presence of negative edge weights. Next we describe in detail the design and implementation of a branch-and-cut algorithm based on semidefinite programming (SBC) to find optimal solution for the MkP problem. The ICH heuristic is used in our SBC algorithm to provide feasible solutions at each node of the branch-and-cut tree. Finally, we present computational results for the SBC algorithm on several classes of test instances with k=3, 5, and 7. Complete graphs with up to 60 vertices and sparse graphs with up to 100 vertices arising from a physics application were considered.

Polynomial programming, a class of non-linear programming where the objective and the constraints are multivariate polynomials, has attracted the attention of many researchers in the past decade. Polynomial programming is a powerful modeling tool that captures various optimization models. Due to the wide range of applications, a research topic of high interest is the development of computationally efficient algorithms for solving polynomial programs. Even though some solution methodologies are already available and have been studied in the literature, these approaches are often either problem specific or are inapplicable for large-scale polynomial programs. Most of the available methods are based on using hierarchies of convex relaxations to solve polynomial programs; these schemes grow exponentially in size becoming rapidly computationally expensive. The present work proposes methods and implementations that are capable of solving polynomial programs of large sizes. First we propose a general framework to construct conic relaxations for binary polynomial programs, this framework allows us to re-derive previous relaxation schemes and provide new ones. In particular, three new relaxations for binary quadratic polynomial programs are presented. The first two relaxations, based on second-order cone and semidefinite programming, represent a significant improvement over previous practical relaxations for several classes of non-convex binary quadratic polynomial problems. The third relaxation is based purely on second-order cone programming, it outperforms the semidefinite-based relaxations that are proposed in the literature in terms of computational efficiency while being comparable in terms of bounds. To strengthen the relaxations further, a dynamic inequality generation scheme to generate valid polynomial inequalities for general polynomial programs is presented. When used iteratively, this scheme improves the bounds without incurring an exponential growth in the size of the relaxation. The scheme can be used on any initial relaxation of the polynomial program whether it is second-order cone based or semidefinite based relaxations. The proposed scheme is specialized for binary polynomial programs and is in principle scalable to large general combinatorial optimization problems. In the case of binary polynomial programs, the proposed scheme converges to the global optimal solution under mild assumptions on the initial approximation of the binary polynomial program. Finally, for binary polynomial programs the proposed relaxations are integrated with the dynamic scheme in a branch-and-bound algorithm to find global optimal solutions.

Typically, design is approached as a sequence of decisions in which designers select what they believe to be the best alternative in each decision. While this approach can be used to arrive at a final solution quickly, it is unlikely to result in the most-preferred solution. The reason for this is that all the decisions in the design process are coupled. To determine the most preferred alternative in the current decision, the designer would need to know the outcomes of all future decisions, information that is currently unavailable or indeterminate. Since the designer cannot select a single alternative because of this indeterminate (interval-based) uncertainty, a set-based design approach is introduced. The approach is motivated by the engineering practices at Toyota and is based on the structure of the Branch and Bound Algorithm. Instead of selecting a single design alternative that is perceived as being the most preferred at the time of the decision, the proposed set-based design approach eliminates dominated design alternatives: rather than selecting the best, eliminate the worst. Starting from a large initial design space, the approach sequentially reduces the set of non-dominated design alternatives until no further reduction is possible ??e remaining set cannot be rationally differentiated based on the available information. A single alternative is then selected from the remaining set of non-dominated designs. In this thesis, the focus is on the elimination step of the set-based design method: A criterion for rational elimination under interval-based uncertainty is derived. To be efficient, the criterion takes into account shared uncertainty ??certainty shared between design alternatives. In taking this uncertainty into account, one is able to eliminate significantly more design alternatives, improving the efficiency of the set-based design approach. Additionally, the criterion uses a detailed reference design to allow more elimination of inferior design sets without evaluating each alternative in that set. The effectiveness of this elimination is demonstrated in two examples: a beam design and a gearbox design.

The effects of coupling parameters of active-passive and passive-passive coupling components on the coupling efficiency and signal mixed proportion for polymer optical fiber (POF) communication are investigated. A high sensitivity and easy fabricated POF displacement sensor is proposed by using cycling bending POF. Also, light sources for both Laser diode (LD) and light emitting diode (LED) are employed in this study. Experimental approaches and numerical analysis of rays tracing method and finite element method are performed to investigate the effects of coupling scheme and bent deformation on the optical power attenuation. Experimental results also illustrate the feasibility of using numerical analysis in coupling components and POF displacement sensor design. The effect of V-grooved array¡¦s POF on the coupling efficiency and signal mixed proportion are presented in active-passive components. The results indicate that the effect of the V-groove¡¦s shape and size on the coupling efficiency is very significant for all designed parameters of V-grooved array¡¦s POF. Compared with the parallel V-grooved array, the skew V-grooved array reduces the length of the coupling component and increases the output power between light source and POF. In the Y-branch POF coupler for passive-passive components, both the excess loss and the output power ratio of the Y-branch couplers are very sensitive to the couple angle, the coupling distance and the refractive index of the filling medium between the emitting-end and receiving-end of fibers. The results also show that the proposed model can be used to analyze the coupling efficiencies in the asymmetrical Y-branch or axial symmetrical couplers with acceptable accuracy. In the POF displacement sensor using by cycling bending loss, the results show that the effect of roller¡¦s number, interval and wavelength on light power attenuation is very significant. Based on the experimental data, a linear equation is derived to estimate the relationship between the power loss and the relative displacement. The difference between the estimated results and the experimental results is less than 8%.

The purpose of this dissertation is to synthesize a methodology to prescribe a strategic design of a surveillance system to provide the required level of surveillance for ports and waterways. The method of approach to this problem is to formulate a linear integer programming model to prescribe a strategic surveillance system design (SSD) for ports or waterways, to devise branch-and-price decomposition (B