<p>    </p> <p>Programs that use loops to operate over arrays and matrices are generally known as <em>regular programs</em>. These programs appear in critical applications such as image processing, differential equation solvers, and machine learning. Over the past few decades, extensive research has been done on composing, verifying, and applying scheduling transformations like loop interchange and loop tiling for regular programs. As a result, we have general frameworks such as the polyhedral model to handle transformations for loop-based programs. Similarly, programs that use recursion and loops to manipulate pointer-based data structures are known as <em>irregular programs</em>. Irregular programs also appear in essential applications such as scientific simulations, data mining, and graphics rendering. However, there is no analogous framework for recursive programs. In the last decade, although many scheduling transformations have been developed for irregular programs, they are ad-hoc in various aspects, such as being developed for a specific application and lacking portability. This dissertation examines principled ways to handle scheduling transformations for recursive programs through a unified framework resulting in performance enhancement. </p> <p>Finding principled approaches to optimize irregular programs at compile-time is a long-standing problem. We specifically focus on scheduling transformations that reorder a program’s operations to improve performance by enhancing locality and exploiting parallelism. In the first part of this dissertation, we present PolyRec, a unified general framework that can compose and apply scheduling transformations to nested recursive programs and reason about the correctness of composed transformations. PolyRec is a first-of-its-kind unified general transformation framework for irregular programs consisting of nested recursion and loops. It is built on solid theoretical foundations from the world of automata and transducers and provides a fundamentally novel way to think about recursive programs and scheduling transformations for them. The core idea is designing mechanisms to strike a balance between the expressivity in representing the set of dynamic instances of computations, transformations, and dependences and the decidability of checking the correctness of composed transformations. We use <em>multi-tape </em>automata and transducers to represent the set of dynamic instances of computations and transformations, respectively. These machines are similar yet more expressive than their classical single-tape counterparts. While in general decidable properties of classical machines are undecidable for multi-tape machines, we have proven that those properties are decidable for the class of machines we consider, and we present algorithms to verify these properties. Therefore these machines provide the building blocks to compose and verify scheduling transformations for nested recursion and loops. The crux of the PolyRec framework is its regular string-based representation of dynamic instances that allows to lexicographically order instances identically to their execution order. All the transformations considered in PolyRec require different ordering of these strings representable only with <em>additive </em>changes to the strings. </p> <p>Loop transformations such as <em>skewing </em>require performing arithmetic on the representation of dynamic instances. In the second part of this dissertation, we explore this space of transformations by introducing skewing to nested recursion. Skewing plays an essential role in producing easily parallelizable loop nests from seemingly difficult ones due to dependences carried across loops. The inclusion of skewing for nested recursion to PolyRec requires significant extensions to representing dynamic instances and transformations that facilitate <em>performing arithmetic using strings</em>. First, we prove that the machines that represent the transformations are still composable. Then we prove that the representation of dependences and the algorithm that checks the correctness of composed transformations hold with minimal changes. Our new extended framework is known as UniRec, since it resembles the unimodular transformations for perfectly nested loop nests, which consider any combination of the primary transformations interchange, reversal, and skewing. UniRec opens possibilities of producing newly composed transformations for nested recursion and loops and verifying their correctness. We claim that UniRec completely subsumes the unimodular framework for loop transformations since nested recursion is more general than loop nests. </p>

No description available.

Air transportation offers both passenger and freight services that are essential for economic growth and development. In a highly competitive environment, airline companies have to control their operating costs by managing their flights, aircraft, and crews effectively. This motivates the extensive use of analytical techniques to solve complex problems related to airline operations planning, which includes schedule design, fleet assignment, aircraft routing, and crew scheduling. The initial problem addressed by airlines is that of schedule design, whereby a set of flights having specific origin and destination cities as well as departure and arrival times is determined. Then, a fleet assignment problem is solved to assign an aircraft type to each flight so as to maximize anticipated profits. This enables a decomposition of subsequent problems according to the different aircraft types belonging to a common family, for each of which an aircraft routing problem and a crew scheduling or pairing problem are solved. Here, in the aircraft routing problem, a flight sequence or route is built for each individual aircraft so as to cover each flight exactly once at a minimum cost while satisfying maintenance requirements. Finally, in the crew scheduling or pairing optimization problem, a minimum cost set of crew rotations or pairings is constructed such that every flight is assigned a qualified crew and that work rules and collective agreements are satisfied. In practice, most airline companies solve these problems in a sequential manner to plan their operations, although recently, an increasing effort is being made to develop novel approaches for integrating some of the airline operations planning problems while retaining tractability. This dissertation formulates and analyzes three different models, each of which examines a composition of certain pertinent airline operational planning problems. A comprehensive fourth model is also proposed, but is relegated for future research. In the first model, we integrate fleet assignment and schedule design by simultaneously considering optional flight legs to select along with the assignment of aircraft types to all scheduled legs. In addition, we consider itinerary-based demands pertaining to multiple fare-classes. A polyhedral analysis of the proposed mixed-integer programming model is used to derive several classes of valid inequalities for tightening its representation. Solution approaches are developed by applying Benders decomposition method to the resulting lifted model, and computational experiments are conducted using real data obtained from a major U.S. airline (United Airlines) to demonstrate the efficacy of the proposed procedures as well as the benefits of integration. A comparison of the experimental results obtained for the basic integrated model and for its different enhanced representations reveals that the best modeling strategy among those tested is the one that utilizes a variety of five types of valid inequalities for moderately sized problems, and further implements a Benders decomposition approach for relatively larger problems. In addition, when a heuristic sequential fixing step is incorporated within the algorithm for even larger sized problems, the computational results demonstrate a less than 2% deterioration in solution quality, while reducing the effort by about 21%. We also performed an experiment to assess the impact of integration by comparing the proposed integrated model with a sequential implementation in which the schedule design is implemented separately before the fleet assignment stage based on two alternative profit maximizing submodels. The results obtained demonstrate a clear advantage of utilizing the integrated model, yielding an 11.4% and 5.5% increase in profits in comparison with using the latter two sequential models, which translates to an increase in annual profits by about $28.3 million and $13.7 million, respectively. The second proposed model augments the first model with additional features such as flexible flight times (i.e., departure time-windows), schedule balance, and demand recapture considerations. Optional flight legs are incorporated to facilitate the construction of a profitable schedule by optimally selecting among such alternatives in concert with assigning the available aircraft fleet to all the scheduled legs. Moreover, network effects and realistic demand patterns are effectively represented by examining itinerary-based demands as well as multiple fare-classes. Allowing flexibility on the departure times of scheduled flight legs within the framework of an integrated model increases connection opportunities for passengers, hence yielding robust schedules while saving fleet assignment costs. A provision is also made for airlines to capture an adequate market share by balancing flight schedules throughout the day. Furthermore, demand recapture considerations are modeled to more realistically represent revenue realizations. For this proposed mixed-integer programming model, which integrates the schedule design and fleet assignment processes while considering flexible flight times, schedule balance, and recapture issues, along with optional legs, itinerary-based demands, and multiple fare-classes, we perform a polyhedral analysis and utilize the Reformulation-Linearization Technique in concert with suitable separation routines to generate valid inequalities for tightening the model representation. Effective solution approaches are designed by applying Benders decomposition method to the resulting tightened model, and computational results are presented to demonstrate the efficacy of the proposed procedures. Using real data obtained from United Airlines, when flight times were permitted to shift by up to 10 minutes, the estimated increase in profits was about $14.9M/year over the baseline case where only original flight legs were used. Also, the computational results indicated a 1.52% and 0.49% increase in profits, respectively, over the baseline case, while considering two levels of schedule balance restrictions, which can evidently also enhance market shares. In addition, we measured the effect of recaptured demand with respect to the parameter that penalizes switches in itineraries. Using values of the parameter that reflect 1, 50, 100, or 200 dollars per switched passenger, this yielded increases in recaptured demand that induced additional profits of 2.10%, 2.09%, 2.02%, and 1.92%, respectively, over the baseline case. Overall, the results obtained from the two schedule balance variants of the proposed integrated model that accommodate all the features of flight retiming, schedule balance, and demand recapture simultaneously, demonstrated a clear advantage by way of $35.1 and $31.8 million increases in annual profits, respectively, over the baseline case in which none of these additional features is considered. In the third model, we integrate the schedule design, fleet assignment, and aircraft maintenance routing decisions, while considering optional legs, itinerary-based demands, flexible flight retimings, recapture, and multiple fare-classes. Instead of utilizing the traditional time-space network (TSN), we formulate this model based on a flight network (FN) that provides greater flexibility in accommodating integrated operational considerations. In order to consider through-flights (i.e., a sequence of flight legs served by the same aircraft), we append a set of constraints that matches aircraft assignments on certain inbound legs into a station with that on appropriate outbound legs at the same station. Through-flights can generate greater revenue because passengers are willing to pay a premium for not having to change aircraft on connecting flights, thereby reducing the possibility of delays and missed baggage. In order to tighten the model representation and reduce its complexity, we apply the Reformulation-Linearization Technique (RLT) and also generate other classes of valid inequalities. In addition, since the model possesses many equivalent feasible solutions that can be obtained by simply reindexing the aircraft of the same type that depart from the same station, we introduce a set of suitable hierarchical symmetry-breaking constraints to enhance the model solvability by distinguishing among aircraft of the same type. For the resulting large-scale augmented model formulation, we design a Benders decomposition-based solution methodology and present extensive computational results to demonstrate the efficacy of the proposed approach. We explored four different algorithmic variants, among which the best performing procedure (Algorithm A1) adopted two sequential levels of Benders partitioning method. We then applied Algorithm A1 to perform several experiments to study the effects of different modeling features and algorithmic strategies. A summary of the results obtained is as follows. First, the case that accommodated both mandatory and optional through-flight leg pairs in the model based on their relative effects on demands and enhanced revenues achieved the most profitable strategy, with an estimated increase in expected annual profits of $2.4 million over the baseline case. Second, utilizing symmetry-breaking constraints in concert with compatible objective perturbation terms greatly enhanced problem solvability and thus promoted the detection of improved solutions, resulting in a $5.8 million increase in estimated annual profits over the baseline case. Third, in the experiment that considers recapture of spilled demand from primary itineraries to other compatible itineraries, the different penalty parameter values (100, 50, and 1 dollars per re-routed passenger) induced average respective proportions of 3.2%, 3.4%, and 3.7% in recaptured demand, resulting in additional estimated annual profits of $3.7 million, $3.8 million, and $4.0 million over the baseline case. Finally, incorporating the proposed valid inequalities within the model to tighten its representation helped reduce the computational effort by 11% on average, while achieving better solutions that yielded on average an increase in estimated annual profits of $1.4 million. In closing, we propose a fourth more comprehensive model in which the crew scheduling problem is additionally integrated with fleet assignment and aircraft routing. This integration is important for airlines because crew costs are the second largest component of airline operating expenses (after fuel costs), and the assignment and routing of aircraft plus the assignment of crews are two closely interacting components of the planning process. Since crews are qualified to typically serve a single aircraft family that is comprised of aircraft types having a common cockpit configuration and crew rating, the aircraft fleeting and routing decisions significantly impact the ensuing assignment of cockpit crews to flights. Therefore it is worthwhile to investigate new models and solution approaches for the integrated fleeting, aircraft routing, and crew scheduling problem, where all of these important inter-dependent processes are handled simultaneously, and where the model can directly accommodate various work rules such as imposing a specified minimum and maximum number of flying hours for crews on any given pairing, and a minimum number of departures at a given crew base for each fleet group. However, given that the crew scheduling problem itself is highly complex because of the restrictive work rules that must be heeded while constructing viable duties and pairings, the formulated integrated model would require further manipulation and enhancements along with the design of sophisticated algorithms to render it solvable. We therefore recommend this study for future research, and we hope that the modeling, analysis, and algorithmic development and implementation work performed in this dissertation will lend methodological insights into achieving further advances along these lines. / Ph. D.

Throughout the study of polymeric Langmuir monolayers at the air/water (A/W) interface, the Wilhelmy plate and Langmuir-Blodgett (LB) techniques along with Brewster angle microscopy (BAM) have been identified as key methods for acquiring structural, thermodynamic, rheological and morphological information. These techniques along with surface light scattering (SLS), a method for probing a monolayer's dynamic dilational rheological properties, will be used to characterize homopolymers, poly(ethylene oxide) (PEO) and poly(ethylene glycol) (PEG), and a new class of novel polymeric surfactants, telechelic (POSS-PEG-POSS) and hemi-telechelic (POSS-PEG) polyhedral oligomeric silsesquioxane (POSS) derivatives of PEG. PEO with number average molar mass, Mn > ~ 18 kg·mol-1 form stable spread Langmuir films at the A/W interface, while oligomeric PEG have ï -A isotherms that deviate from high molar mass PEO. Nonetheless, SLS reveals that the dynamic dilational viscoelastic properties of any Mn PEG(PEO) only depend on ï and not Mn. Likewise, POSS-PEG-POSS telechelics exhibit molar mass dependent ï -A isotherms, where low ï regimes (ï < 1 mN·m-1) have PEG-like behavior, but high ï regimes were dominated by POSS-POSS interactions. SLS studies reveal that the dynamic dilational moduli of POSS-PEG-POSS are greater than either PEO or an analogous POSS compound, trisilanolcyclohexyl-POSS. The ability to control rheological properties and the hydrophilic-lipophilic balance even allows one POSS-PEG-POSS (PEG Mn = 1 kg·mol-1) to form Y-type LB-multilayer films. For POSS-PEG systems, comparisons at comparable POSS:PEG ratios reveal short PEG chains (PEG Mn ~ 0.5 kg·mol-1) yield similar viscoelastic properties as POSS-PEG-POSS (PEG Mn ~ 1 kg·mol-1), while longer PEG chains (PEG Mn ~ 2 kg·mol-1) yield lower modulus films than comparable POSS-PEG-POSS. These differences are attributed to brush-like PEG conformations in short POSS-PEG versus mushroom-like PEG conformations in long POSS-PEG at the A/W interface. These results provide insight for designing PEG-based amphiphilic nanoparticles with controlled interfacial rheology. / Ph. D.

Continuous casting is by far the most widely used casting method for steel production all over the world. The Swedish steel industry has specialized in niche products with high quality. To obtain high-quality steel, flow control is crucial when operating the caster. Computational fluid dynamics is used in the research and development of steel production to gain knowledge and optimize flow control, with meshing being a crucial step. One challenge with meshing is finding the balance between computational cost (time and storage) and accuracy. This study investigated whether polyhedral mesh elements would be suffcient for modeling turbulent flow in continuous casting. Firstly, Ansys Fluent's polyhedral converter was used on an existing mesh containing tetrahedral and hexahedral elements. The mesh quality in terms of skewness, orthogonality, and aspect ratio was studied. The results showed that the polyhedral converter lowered the cell count and slightly improved the quality compared to the original mesh. However, more research is needed with other meshes and actual simulations to determine if it is suffcient for modeling turbulent flow in continuous casting. Following that, two new meshes were generated: one polyhedral and one poly-hexcore mesh, both using Ansys Fluent Meshing, and their mesh quality was analyzed as in the first case. These meshes were then simulated with the Large Eddy Simulation model for steel, slag, and air for 60 seconds. They were compared and evaluated using production data in the form of steel layer fluctuations and nail board measurements. The results from the polyhedral and poly-hexcore meshes showed that both meshes had good, equal quality and cell count. Even so, due to the construction of the poly-hexcore, switching between polyhedral and hexahedral elements, and the occurrence of hanging nodes, the simulation showed signs of discretization errors. This might have also contributed to the lower flow velocities at the steel layer compared to the nail boards for the poly-hexcore mesh. The polyhedral mesh showed more stable simulation results with closer velocity trends compared to the nailboard measurements. The steel layer fluctuations for both meshes were somewhat similar to the production data, but further FFT analysis concluded that fluid flow simulations alone are not enough for an FFT comparison to production data since many factors are missing from the simulations, such as mould oscillations and regulations from the stopper. The computational cost varied between time and storage, with the polyhedral mesh requiring 13 % less simulation time but 32.7 % more storage. In summary, it can be concluded that polyhedral mesh elements can be successfully implemented for modeling turbulent flow in continuous castingwith a reasonable computational cost. / Stränggjutning är den främsta metoden använt för stålproduktion över hela världen. Den svenska stålindustrin har specialiserat sig på nischade produkter med hög kvalitet. För att uppnå högkvalitativt stål är flödeskontroll avgörande vid drift av gjutmaskinen. Numeriska strömningsberäkningar används i forskningen och utvecklingen av stålproduktion för att skaffa kunskap och optimera flödeskontrollen, där meshing är ett avgörande steg. En utmaning med meshing är att hitta balansen mellan beräkningskostnad (tid och lagring) och noggrannhet. Denna studie undersökte om polyhedrala mesh-element skulle vara tillräckliga för att modellera turbulent flöde i stränggjutning. Först användes Ansys Fluents polyhedrala konverterare på en befintlig mesh, innehållande tetrahedrala och hexahedrala element. Meshkvalitén i termer av skevhet, ortogonalitet och aspektförhållande studerades. Resultaten visade att den polyhedrala konverteraren sänkte cellantalet och förbättrade kvaliteten något jämfört med den ursprungliga meshen. Dock behövs mer forskning med andra mesher, och faktiska simuleringar, för att avgöra om den är tillräcklig för att modellera turbulent flöde i stränggjutning. Därefter genererades två nya mesher: ett polyhedralt och en poly-hexcore, båda med hjälp av Ansys Fluent Meshing, och precis som i det första fallet, studerades deras meshkvalitet. Dessa två meshes simulerades sedan med Large Eddy Simulation-modellen för stål, slagg och luft i 60 sekunder. De jämfördes och utvärderades med hjälp av produktionsdata i form av stålnivå, fluktuationer och 'nail board'-mätningar. Resultaten från det polyhedrala och poly-hexcore meshen visade att båda mesherna hade god och likvärdiga kvalitéer samt cellantal. Trots detta, på grund av uppbyggnaden av poly-hexcore meshen, alltså växlingen mellan polyhedrala och hexahedrala element och förekomsten av hängande noder, visade simuleringen tecken på diskretiseringsfel. Detta kan också ha bidragit till de lägre flödeshastigheterna vid stålnivån jämfört med 'nail board'-mätningarna för poly-hexcore meshen. Den polyhedrala meshen visade mer stabila simuleringsresultat med hastighetstrender närmare 'nail board'-mätningarna. Amplituden för stålnivåfluktuationerna för båda näten var något lika produktionsdatan, men en vidare FFT-analys visade att endast flödesimuleringar inte är tillräckliga för en FFT-jämförelse med produktionsdata eftersom många faktorer saknas i simuleringarna, såsom svängningar av gjutformen och reglering av inloppashastigheten. Beräkningskostnaden varierade mellan tid och lagring, där den polyhedrala meshen krävde 13 % mindre simuleringstid men 32,7 % mer lagring. Sammanfattningsvis kan det konstateras att polyhedrala mesh-element framgångsrikt kan implementeras för att modellera turbulent flöde i stränggjutning med en rimlig beräkningskostnad.

The distinct element method (DEM) is a useful tool in rock engineering to model jointed rock masses. To simulate a jointed rock mass realistically, the main challenge is to be able to capture its complex geometry which consists of blocks with various shapes and sizes, and to model the interactions between these blocks. The main contribution of this thesis is the development of novel algorithms in the DEM to model jointed rock masses, namely rock slicing procedures for block generation, and algorithms for contact detection between polygonal blocks in 2-D or polyhedral blocks in 3-D. These algorithms make use of convex optimisation techniques, for which there exist efficient solution procedures. They do not rely on conventional vertex-edge-face hierarchical data structures and tedious housekeeping algorithms. The algorithms have been verified against analytical and numerical solutions, as well as validated against experimental results published in the literature. Among those, the results of DEM simulations were compared against the experimental model tests and numerical simulations of jointed beams carried out by Talesnick et al. (2007) and Tsesarsky & Talesnick (2007) respectively. Emphasis was placed on modelling the stiffness of the block interfaces accurately, and this was accomplished by reinterpreting the laboratory data published by the investigators. The capabilities of the numerical tools are also examined and demonstrated in areas for which the DEM has found practical application. A substantial fraction of this thesis is devoted to illustrating how these tools can assist the engineer in designing support systems; for example, designing the length and spacing of rock bolts and the lining thickness for a tunnel. Algorithms to model rock bolt and lining support were implemented for this purpose. Interesting comparisons with elastic solutions for supported openings were obtained. Further, it is shown that the relative benefit of introducing more rock bolts or thicker lining can be evaluated using the numerical tools with the aid of an interaction diagram. In the final part of this thesis, the case history of the 1963 Vaiont rock slide in Italy is studied. The 2-D analyses led to useful insights concerning the influence of the reservoir water level, the rock mass strength and deformability, and the slide surface shear stiffness. 3-D analyses were undertaken to investigate the influence of the eastern boundary of the slope, and interesting insights were obtained concerning the slope kinematics. Overall, the case study shows that the tools are capable of modelling problems with specific physical and geometrical detail in both 2-D and 3-D.

Liées de façon covalente à des chaînes polymères, les nanoparticules POSS (polysilses-quioxanes polyédriques) permettent l’obtention de matériaux nanocomposites hybrides orga-nique/inorganique. Ces nanoparticules présentent deux intérêts majeurs: des dimensions bien définies (cœur inorganique: 0.5 nm), ainsi que leur caractère hybride ( groupements organiques entourant les cages inorganiques). Les nanocomposites polymère/POSS peuvent présenter un renfort important des propriétés mécaniques et de la stabilité thermique de la matrice polymère. Cependant, l’origine moléculaire de ce renfort reste mal comprise. Aussi, afin de mieux comprendre le renfort des propriétés mécaniques de la matrice, nous avons étudié l’effet des particules POSS sur l’organisation à l’état solide et la dynamique des chaînes po-lymères au sein d’une matrice semi-cristalline. Pour cela, nous avons considéré une série de copolymères polyéthylène-POSS, caractérisés par une large gamme de concentration en POSS. Le polyéthylène et le POSS ayant intrinsèquement tendance à cristalliser, les copolymères présentent des organisations à l’état solide complexes que nous avons caractérisés par l’utilisation combinée de la calorimétrie différentielle à balayage (DSC), de la diffraction des rayons X aux grands angles (DRX) et de la résonance magnétique nucléaire en phase solide (RMN). Dans un second volet de cette étude, nous nous sommes intéressés à la dynamique des chaînes de polyéthylène en phase amorphe et à l’évolution de celle-ci avec le taux de charge des nanocomposites. Enfin, nous avons également étudié, de façon sélective, la dynamique des segments de chaînes de polyéthylène situés au voisinage de la charge / Grafting polyhedral oligomeric silsesquioxanes (POSS) to polymer chains offers a novel avenue to prepare hybrid organic/inorganic nanocomposites. The great advantage of such an approach holds in the very well-defined dimensions of the filler particles(inorganic core: 0.5 nm), in contrast with polymer/clay systems. Polymer/POSS nanocomposites display attractive properties such as significant mechanical reinforcement and increased thermal stability. However, the molecular origins of these enhancements are still an open question. The aim of this work is to describe both bulk organization and molecular motions of the polymer chains within these materials: these molecular properties should lead to a deeper knowledge of the enhancement of the polymer-POSS mechanical properties. The systems investigated are polyethylene (PE)-POSS copolymers with various POSS contents. The (semi-)crystalline behaviour of both PE and POSS particles induces complex bulk organization of these hybrid materials. The combined use of NMR, DSC and X-ray scattering experiments enabled to monitor the variation of the solid-state organization with the filler loading. In the second part of this work, the PE chain dynamics was investigated in the amorphous phase and its variation with the filler content was considered. Lastly, selective NMR experiments were used to probe the PE chain segment mobility close to the POSS nanoparticles

Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.

Nous proposons dans ce mémoire de thèse une méthodologie permettant la résolution du problème de la décomposition de Hodge-Helmholtz discrète sur maillages polyédriques. Le défi de ce travail consiste à respecter les propriétés de la décomposition au niveau discret. Pour répondre à cet objectif, nous menons une étude bibliographique nous permettant d'identifier la nécessité de la mise en oeuvre de schémas numériques mimétiques. La description ainsi que la validation de la mise en oeuvre de ces schémas sont présentées dans ce mémoire. Nous revisitons et améliorons les méthodes de décomposition que nous étudions ensuite au travers d'expériences numériques. En particulier, nous détaillons le choix d'un solveur linéaire ainsi que la convergence des quantités extraites sur un ensemble varié de maillages polyédriques et de conditions aux limites. Nous appliquons finalement la décomposition de Hodge-Helmholtz à l'étude de deux écoulements turbulents : un écoulement en canal plan et un écoulement turbulent homogène isotrope. / We propose in this thesis a methodology to compute the Helmholtz-Hodge decomposition on discrete polyhedral meshes. The challenge of this work isto preserve the properties of the decomposition at the discrete level. In our literature survey, we have identified the need of mimetic schemes to achieve our goal. The description and validation of our implementation of these schemes are presented inthis document. We revisit and improve the methods of decomposition we then study through numerical experiments. In particular, we detail our choice of linear solvers and the convergence of extracted quantities on various series of polyhedral meshes and boundary conditions. Finally, we apply the Helmholtz-Hodge decomposition to the study of two turbulent flows: a turbulent channel flow and a homogeneous isotropic turbulent flow.