No description available.

No description available.

No description available.

No description available.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Graph Theory is a widely studied topic. A graph is defined by two important features: nodes and edges. Nodes can represent people, cities, variables, resources, products, while the edges represent a relationship between two nodes. Using graphs to solve problems has played a major role in a diverse set of industries for many years. Integer Programs (IPs) are mathematical models used to optimize a problem. Often this involves maximizing the utilization of resources or minimizing waste. IPs are most notably used when resources must be of integer value, or cannot be split. IPs have been utilized by many companies for resource distribution, scheduling, and conflict management. The node packing or independent set problem is a common combinatorial optimization problem. The objective is to select the maximum nodes in a graph such that no two nodes are adjacent. Node packing has been used in a wide variety of problems, which include routing of vehicles and scheduling machines. This thesis introduces several new graph structures, cliqued hole, odd bipartite hole, and odd k-partite hole, and their corresponding valid inequalities for the node packing polyhedron. These valid inequalities are shown to be new valid inequalities and conditions are provided for when they are facet defining, which are known to be the strongest class of valid inequalities. These new valid inequalities can be used by practitioners to help solve node packing instances and integer programs.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IP) are used in companies and organizations across the world to reach financial and time-related goals most often through optimal resource allocation and scheduling. Unfortunately, integer programs are computationally difficult to solve and in some cases the optimal solutions are unknown even with today’s advanced computing machines. Lifting is a technique that is often used to decrease the time required to solve an IP to optimality. Lifting begins with a valid inequality and strengthens it by changing the coefficients of variables in the inequality. Often times, this technique can result in facet defining inequalities, which are the theoretically strongest inequalities. This thesis introduces a new type of lifting called synchronized simultaneous lifting (SSL). SSL allows for multiple sets of simultaneously lifted variables to be simultaneously lifted which generates a new class of inequalities that previously would have required an oracle to be found. Additionally, this thesis describes an algorithm to perform synchronized simultaneous lifting for a binary knapsack inequality called the Synchronized Simultaneous Lifting Algorithm (SSLA). SSLA is a quadratic time algorithm that will exactly simultaneously lift two sets of simultaneously lifted variables. Short computational studies show SSLA can sometimes solve IPs to optimality that CPLEX, an advanced integer programming solver, alone cannot solve. Specifically, the SSL cuts allowed a 76 percent improvement over CPLEX alone.

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

There are several reasons to research the effects of axial twist exposures and the resulting loading on the spine. The lack of consensus from the limited work that has previously examined the role of axial twist moments and motions in the development of spine injuries or generation of low back pain is the primary reason. From recently published works, axial twist moments appear to represent an increased risk for injury development when it acts in concert with loading about other physiological axes (i.e. flexion, extension, and compression). However, there is a large body of epidemiologic data identifying axial twist moments and/or motion as risk factors for low back disorders and pain, demonstrating the need for this series of investigations. It is likely that these combined exposures increase risk through altering the spine’s load distribution (passive resistance) by modifying the mechanics, but this deduction and related causal mechanism need to be researched. The global objective of this research was focused on determining whether there is evidence to support altered load distribution in the spine, specifically between the intervertebral disc and facets, in response to applied axial twist moments (when added in combination with one and two axes of additional loading). Also included was whether these modes of loading can modify spine mechanics and contribute and/or alter the development of damage and pain. This objective was addressed through one in-vivo (Drake and Callaghan, 2008a– Chapter #2) and three in-vitro (Drake et al., 2008– Chapter #4; Drake and Callaghan, 2008b– Chapter #5; Drake and Callaghan, 2008c– Chapter #6) studies that: (1) Quantified the amount of passive twist motion in the lumbar spine when coupled with various flexion-extension postures; (2) Documented the effects of flexion-extension postures and loading history on the distance between the facet articular surfaces; (3) Evaluated the result of axial twist rotation rates on acute failure of the spine in a neutral flexion posture; and (4) Explored whether repetitive combined loading has the ability to cause enough deformation to the spine to generate pain. Through the combination of findings previously reported in the literature and the outcomes of Drake and Callaghan (2008a– Chapter #2) and Drake et al. (2008– Chapter #4), a postural mediated mechanism was hypothesized to be responsible for governing the load distribution between the facet joints and other structures of the spine (i.e. disc, ligaments). Increased flexed postures were found to decrease the rotational stiffness by resulting in larger twist angles for the same applied twist moment in-vivo relative to a neutral flexion posture (Drake and Callaghan, 2008a– Chapter #2). This suggested there might be an increased load on the disc due to a change in facet coupling in these combined postures. Similarly, increased angles were observed in flexed and twisted postures for in-vitro specimens relative to a neutral flexion posture. These observed differences were found to correspond with altered facet joint mechanics. Specifically that flexed twisted postures increased the inter-facet spacing relative to the initial state of facet articulation (Drake et al., 2008– Chapter #4). These finding supported the postulated postural mechanism. Therefore, in a neutral posture the facet joints likely resisted the majority of any applied twist moment based on the limited range of motion and higher axial rotational stiffness responses observed. It was suspected that the changes in mechanics would likely cause a change in the load distribution however the magnitude of change in load distribution remains to be quantified. Further support for this postulated postural mechanism comes from the mode of failure for specimens that were exposed to 10,000 cycles of 5° axial twist rotation while in a static flexed posture (Drake and Callaghan, 2008c– Chapter #6), and neutrally flexed specimens exposed to 1.5° of rotation for 10,000 cycles reported in the literature. Without flexion, the failure patterns were reported to occur in the endplates, facets, laminae and capsular ligaments, but not the disc. However, with flexion the repetitive axial twist rotational displacements caused damage primarily to the disc. If the load distribution was unchanged, the higher axial rotation angle should have caused the specimen to fail in less cycles of loading, and the failure pattern should not have changed. Modulators of this hypothesized mechanism include the velocity of the applied twist moment and the effects these have on the failure parameters and injury outcomes. The three physiologic loading rates investigated in this work were not shown to affect the ultimate axial twist rotational failure angle or moment in a neutral flexion/extension posture, but were shown to modify flexion-extension stiffness (Drake and Callaghan, 2008b– Chapter #5). All of the flexion-extension stiffness values post failure, from a one-time axial twist exposure, was less than those from a repetitive combined loading exposure that has been established to damage the intervertebral disc but not the facets. Therefore, it is likely that the facet joint provides the primary resistance to acute axial twist moments when the spine is in a neutral flexion posture, but there appears to be a redistribution of the applied load from the facets to the disc in repetitive exposures. The aforementioned studies determined there are changes in load distribution and load response caused by altered mechanics resulting from twist loading, but whether the exposures could possibly produce pain needed to be addressed. Previous research has determined that the disc has relatively low innervation in comparison to the richly innervated facet capsule and vertebra, with only the outer regions being innervated. Likewise, it is assumed that pain could be directly generated as the nucleus pulposus disrupted the innervated outer annular fibres in the process of herniation. Also, direct compression of the spinal cord or nerve roots has been shown to occur from the extruded nucleus and result in the generation of pain responses. Additionally, the nucleus pulposus has been shown to be a noxious stimulus that damages the function and structure of nerves on contact. The other source of nerve root compression commonly recognized is a decrease in intervertebral foramina space, which was previously believed to only be caused through losses in disc height. However, decreased intervertebral foramina space due to repetitive motions appears to be a viable pain generating pathway that may not directly correspond to simply a loss of specimen or disc height (Drake and Callaghan, 2008c– Chapter #6). This is new evidence for combined loading to generate pain through spinal deformation. The objective of many traditional treatments for nerve root compression focus on restoring lost disc height to remove the nerve root compression. Unfortunately, nerve root compression caused by repetitive loading may not be alleviated through this approach. This collection of studies was focused on determining whether altered load distribution in the spine, specifically between the intervertebral disc and facets, in response to applied axial twist loading (when added in combination with one and two axes of additional loading) was occurring, and examining how these modes of loading can contribute and/or alter the development of injury and pain. Therefore, findings generated from this thesis may have important implications for clinicians, researchers, and ergonomists.

There are several reasons to research the effects of axial twist exposures and the resulting loading on the spine. The lack of consensus from the limited work that has previously examined the role of axial twist moments and motions in the development of spine injuries or generation of low back pain is the primary reason. From recently published works, axial twist moments appear to represent an increased risk for injury development when it acts in concert with loading about other physiological axes (i.e. flexion, extension, and compression). However, there is a large body of epidemiologic data identifying axial twist moments and/or motion as risk factors for low back disorders and pain, demonstrating the need for this series of investigations. It is likely that these combined exposures increase risk through altering the spine’s load distribution (passive resistance) by modifying the mechanics, but this deduction and related causal mechanism need to be researched. The global objective of this research was focused on determining whether there is evidence to support altered load distribution in the spine, specifically between the intervertebral disc and facets, in response to applied axial twist moments (when added in combination with one and two axes of additional loading). Also included was whether these modes of loading can modify spine mechanics and contribute and/or alter the development of damage and pain. This objective was addressed through one in-vivo (Drake and Callaghan, 2008a– Chapter #2) and three in-vitro (Drake et al., 2008– Chapter #4; Drake and Callaghan, 2008b– Chapter #5; Drake and Callaghan, 2008c– Chapter #6) studies that: (1) Quantified the amount of passive twist motion in the lumbar spine when coupled with various flexion-extension postures; (2) Documented the effects of flexion-extension postures and loading history on the distance between the facet articular surfaces; (3) Evaluated the result of axial twist rotation rates on acute failure of the spine in a neutral flexion posture; and (4) Explored whether repetitive combined loading has the ability to cause enough deformation to the spine to generate pain. Through the combination of findings previously reported in the literature and the outcomes of Drake and Callaghan (2008a– Chapter #2) and Drake et al. (2008– Chapter #4), a postural mediated mechanism was hypothesized to be responsible for governing the load distribution between the facet joints and other structures of the spine (i.e. disc, ligaments). Increased flexed postures were found to decrease the rotational stiffness by resulting in larger twist angles for the same applied twist moment in-vivo relative to a neutral flexion posture (Drake and Callaghan, 2008a– Chapter #2). This suggested there might be an increased load on the disc due to a change in facet coupling in these combined postures. Similarly, increased angles were observed in flexed and twisted postures for in-vitro specimens relative to a neutral flexion posture. These observed differences were found to correspond with altered facet joint mechanics. Specifically that flexed twisted postures increased the inter-facet spacing relative to the initial state of facet articulation (Drake et al., 2008– Chapter #4). These finding supported the postulated postural mechanism. Therefore, in a neutral posture the facet joints likely resisted the majority of any applied twist moment based on the limited range of motion and higher axial rotational stiffness responses observed. It was suspected that the changes in mechanics would likely cause a change in the load distribution however the magnitude of change in load distribution remains to be quantified. Further support for this postulated postural mechanism comes from the mode of failure for specimens that were exposed to 10,000 cycles of 5° axial twist rotation while in a static flexed posture (Drake and Callaghan, 2008c– Chapter #6), and neutrally flexed specimens exposed to 1.5° of rotation for 10,000 cycles reported in the literature. Without flexion, the failure patterns were reported to occur in the endplates, facets, laminae and capsular ligaments, but not the disc. However, with flexion the repetitive axial twist rotational displacements caused damage primarily to the disc. If the load distribution was unchanged, the higher axial rotation angle should have caused the specimen to fail in less cycles of loading, and the failure pattern should not have changed. Modulators of this hypothesized mechanism include the velocity of the applied twist moment and the effects these have on the failure parameters and injury outcomes. The three physiologic loading rates investigated in this work were not shown to affect the ultimate axial twist rotational failure angle or moment in a neutral flexion/extension posture, but were shown to modify flexion-extension stiffness (Drake and Callaghan, 2008b– Chapter #5). All of the flexion-extension stiffness values post failure, from a one-time axial twist exposure, was less than those from a repetitive combined loading exposure that has been established to damage the intervertebral disc but not the facets. Therefore, it is likely that the facet joint provides the primary resistance to acute axial twist moments when the spine is in a neutral flexion posture, but there appears to be a redistribution of the applied load from the facets to the disc in repetitive exposures. The aforementioned studies determined there are changes in load distribution and load response caused by altered mechanics resulting from twist loading, but whether the exposures could possibly produce pain needed to be addressed. Previous research has determined that the disc has relatively low innervation in comparison to the richly innervated facet capsule and vertebra, with only the outer regions being innervated. Likewise, it is assumed that pain could be directly generated as the nucleus pulposus disrupted the innervated outer annular fibres in the process of herniation. Also, direct compression of the spinal cord or nerve roots has been shown to occur from the extruded nucleus and result in the generation of pain responses. Additionally, the nucleus pulposus has been shown to be a noxious stimulus that damages the function and structure of nerves on contact. The other source of nerve root compression commonly recognized is a decrease in intervertebral foramina space, which was previously believed to only be caused through losses in disc height. However, decreased intervertebral foramina space due to repetitive motions appears to be a viable pain generating pathway that may not directly correspond to simply a loss of specimen or disc height (Drake and Callaghan, 2008c– Chapter #6). This is new evidence for combined loading to generate pain through spinal deformation. The objective of many traditional treatments for nerve root compression focus on restoring lost disc height to remove the nerve root compression. Unfortunately, nerve root compression caused by repetitive loading may not be alleviated through this approach. This collection of studies was focused on determining whether altered load distribution in the spine, specifically between the intervertebral disc and facets, in response to applied axial twist loading (when added in combination with one and two axes of additional loading) was occurring, and examining how these modes of loading can contribute and/or alter the development of injury and pain. Therefore, findings generated from this thesis may have important implications for clinicians, researchers, and ergonomists.

Cette thèse présente quelques avancées sur la représentation efficace de l’apparence matérielle dans une simulation de l’éclairage. Nous présentons deux contributions : un algorithme pratique de simulation interactive pour rendre la réflectance mesurée avec une géométrie dynamique en utilisant une analyse fréquentielle du transport de l’énergie lumineuse et le shading hiérarchique et sur-échantillonnage dans un contexte deferred shading, et une nouvelle fonction de distribution pour le modèle de BRDF de Cook-Torrance. Dans la première partie, nous présentons une analyse fréquentielle de transport de l’éclairage en temps réel. La bande passante et la variance sont fonction de l’éclairage incident, de la distance parcourue par la lumière, de la BRDF et de la texture, et de la configuration de la géométrie (la courbure). Nous utilisons ces informations pour sous-échantillonner l’image en utilisant un nombre adaptatif d’échantillons. Nous calculons l’éclairage de façon hiérarchique, en un seul passage. Notre algorithme est implémenté dans un cadre de deferred shading, et fonctionne avec des fonctions de réflectance quelconques, y compris mesurées. Nous proposons deux extensions : pré-convolution de l’éclairage incident pour plus d’efficacité, et anti-aliasing utilisant l’information de fréquence. Dans la deuxième partie, nous nous intéressons aux fonction de réflectance a base de micro-facette, comme le modèle de Cook-Torrance. En nous basant sur les réflectances mesurées, nous proposons une nouvelle distribution des micro-facettes. Cette distribution, Shifted Gamma Distribution, s’adapte aux donnée avec plus de précision. Nous montrons également comment calculer la fonction d’ombrage et de masquage pour cette distribution. Dans un deuxième temps, nous observons que pour certains matériaux, le coefficient de Fresnel ne suit pas l’approximation de Schlick. Nous proposons une généralisation de cette approximation qui correspond mieux aux données mesurées. Nous proposons par ailleurs une nouvelle technique d’optimisation, canal par canal, en deux étapes. Notre modèle est plus précis que les modèles existants, du diffus au spéculaire. / This thesis presents some advances in efficient representation of material appearance in a lighting simulation. The scope of this thesis is two-fold: an interactive shading algorithm to render measured reflectance with dynamic geometry using frequency analysis of light transport and hierarchical shading and up-sampling in deferred shading context, and a new normal distribution function for the Cook-Torrance micro-facet BRDF model, along with a new shadowing and masking function and a generalization of Schlick’s approximation of the Fresnel term. In the first part, we introduce a real-time frequency analysis of light transport framework that allows us to estimate the bandwidth and variance of the shading integrand. The bandwidth and variance are a function of frequencies in the illumination, distance traveled by light, BRDF and texture, and the geometry configuration (curvature). We use this information to under-sample the image, and also use an adaptive number of samples for shading. We devise a single-pass hierarchical shading and up-sampling scheme to assemble an image out of the sparsely shaded image pixels. We extend our interactive technique to use pre-convolved shading for real-time performance. We also take advantage of the bandwidth information to perform multi-sample anti-aliasing in deferred shading by subsampling only a small portion of image pixels whose bandwidth is smaller than 1 pixel^-1. In the second part, we propose a new distribution function for the Cook-Torrance micro-facet BRDF, based on our observations on the reflectance measurements. We isolate the distribution components of the reflectance data and directly observe that existing distribution functions are insufficient. Then we devise the Shifted Gamma Distribution (SGD) fitting more accurately to the data. We derive the shadowing and masking function from the distribution. We observe that not all materials have the Fresnel behavior expected by Schlick’s approximation. Hence, we generalize the Schlick’s approximation to more accurately fit the model to the measurements. We introduce a two-step fitting approach, that fits each RGB channel separately — accounting for wave-length dependent effects. We show that our shading model outperforms existing models and accurately represents a wider range of materials from diffuse to glossy and highly specular materials.