There has been in the past ten to fifteen years a surge of activity concerning the cohomology of semi-direct product groups of the form $\mathbb{Z}^{n}\rtimes$G with G finite. A problem first stated by Adem-Ge-Pan-Petrosyan asks for suitable conditions for the Lyndon-Hochschild-Serre Spectral Sequence associated to this group extension to collapse at second page of the Lyndon-Hochschild-Serre spectral sequence. In this thesis we use facts from integer representation theory to reduce this problem to only considering representatives from each genus of representations, and establish techniques for constructing new examples in which the spectral sequence collapses.

Scheduling problem and shift design problems are well known NP-hard problems within the optimization area. Often time, the two problems are studied individually. In this thesis however, we are looking at the combination of both problems. More specifically, the aim of this thesis is to suggest an optimal scheduling policy given that there are no predefined shifts to begin with. The duration of a shift, along with the start and end time may vary. Thus we have proposed to split the problem into two sub-problems: weekly scheduling problem and daily scheduling problem. As there are no exact solution methods that are feasible, two meta-heuristics method has been employed to solve the sub-problems: Simulated Annealing (SA) and Genetic Algorithm (GA). We have provided proofs of concepts for both methods as well as explored the scalability. This is especially important as the number of employee is expected to grow significantly throughout the year. The results obtained has shown to be promising and can be built upon for further capabilities. / Schemaläggning och skiftdesignsproblem är välkända och välstuderade NP-svåra beslutsproblem inom optimeringsområdet. Oftast så studeras dessa problem enskilt, men i detta arbete så studeras en kombination av båda problemen. Mer specifikt är målet med detta arbete att föreslå ett förnuftigt handlingsätt till att skapa ett veckoschema där skift inte är predefinierade för alla veckor. Starttiden, sluttiden och varaktigheten av ett skift kan förändras från vecka till vecka. Därför har problemet delats upp till två delar: Veckoschemaläggnings- och dagsschemaläggningsproblem. Trots uppdelningen så är båda delproblem för komplexa för att lösas exakt. Därför har två metaheuristiska metoder använts som lösningsmetoder: Simulerad Glödgning och Genetisk Algoritm. I detta arbete bevisas båda lösningsmetoderna till att vara bra nog, och dessutom studeras även skalbarheten av modellen. Detta senare är särskilt viktigt eftersom antal anställda som ska schemaläggas förväntas att öka genomåren. De erhållna resultaten har visat sig vara lovande och bevisligen så kan modellen expanderas med er villkor

The Single Instruction Multiple Data (SIMD) paradigm became a core principle for optimizing query processing in columnar database systems. Until now, only the LOAD/STORE instructions are considered to be efficient enough to achieve the expected speedups, while avoiding GATHER/SCATTER is considered almost imperative. However, the GATHER instruction offers a very flexible way to populate SIMD registers with data elements coming from non-consecutive memory locations. As we will discuss within this article, the GATHER instruction can achieve the same performance as the LOAD instruction, if applied properly. To enable the proper usage, we outline a novel access pattern allowing fine-grained, partition-based SIMD implementations. Then, we apply this partition-based SIMD processing to two representative examples from columnar database systems to experimentally demonstrate the applicability and efficiency of our new access pattern.

In this demo, we present MorphStore, an in-memory column store with a novel compression-aware query processing concept. Basically, compression using lightweight integer compression algorithms already plays an important role in existing in-memory column stores, but mainly for base data. The continuous handling of compression from the base data to the intermediate results during query processing has already been discussed, but not investigated in detail since the computational effort for compression as well as decompression is often assumed to exceed the benefits of a reduced transfer cost between CPU and main memory. However, this argument increasingly loses its validity as we are going to show in our demo. Generally, our novel compression-aware query processing concept is characterized by the fact that we are able to speed up the query execution by morphing compressed intermediate results from one scheme to another scheme to dynamically adapt to the changing data characteristics during query processing. Our morphing decisions are made using a cost-based approach.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, 1981 / Vita. / Bibliography: leaves 97-98. / by Dorothy Elliott Sempolinski. / Ph. D. / Ph. D. Massachusetts Institute of Technology, Sloan School of Management

Norrmejerier står inför förändringar vad gäller både mjölkkonsumtion och flytt av produktionen från Luleå mejeri till Umeå mejeri inom en snar framtid. Det har gett behov av ett verktyg för att snabbt kunna fatta beslut om systemet kan hantera en ökad mängd volym och antal produktkategorier. För att ta fram ett sådant verktyg skapades en matematisk optimeringsmodell uppbyggd i programvaran Python som gör det möjligt att köra programmet för olika scenarion. Modellen använder optimeringslösaren Pulp för att hitta en lösning på problemet. Den matematiska modellen baseras på Multi Commodity Flow Problem med tidsvariabel i kombination med Flow-shop scheduling och har modifierats efter systemet på Umeå mejeri. Det är en pessimistisk modell baserat på de antaganden som gjorts i rapporten. Programmet baseras på ett dygns produktion och avgör, genom att minimera den totala tiden det tar för flödet genom processen, om det finns kapacitet för en ökad produktion. Systemet i projektet är uppdelat i två subnätverk på grund av tidskomplexiteten och resultaten visar att implementering av en ytterligare produktkategori kan hanteras av båda subnätverken. En ökad volym med 10% av den befintliga kan endast hanteras av den första delen av nätverket. Det betyder att det finns tekniska begränsningar i det andra subnätverket. Genom tillägg av extra noder som kan användas till en viss straffkostnad kunde flaskhalsar identifieras och det visade sig att pastör 2P1 är en uppenbar flaskhals i systemet. Om man ökar produktionen ytterligare kan även silosarna behöva utökas för att hantera flödet. / Norrmejerier is facing changes in terms of both milk consumption and a move of the production from Luleå dairy to Umeå dairy in the near future. This has given rise to the need of a tool that quickly can make descisions about whether the system can handle an increased amount of volume and number of product categories. To produce such a tool a mathematical optimization model was created in Python which makes it possible to run the program for different scenarios. The model uses the optimization solver Pulp. The mathematical model is based on Multi Commodity Flow Problem with time variable combined with Flow-shop scheduling and has been modified according to the system at Umeå dairy. Based on the assumptions made in the report it is a pessimistic model. The program is based on one day's production and determines by minimizing the total time it takes for the flow to pass through the system, to see if there is enough capacity for increased production. The system in the project is divided into two subnetworks due to the time complexity and the results show that implementation of an additional product category can be handled by both subnetworks. An increased volume of 10% of the existing volume can only be handled by the first part of the network. This means that there are technical limitations in the second subnetwork. By adding extra nodes that can be used for a certain penalty cost, bottlenecks could be identified and it turned out that Pasteur 2P1 is an obvious bottleneck in the system. If the production increases further the silos may also need to be expanded to handle the flow in the system.

Stochastic programming is an optimization technique that incorporates random variables as parameters. Because it better reflects the uncertain real world than its traditional deterministic counterpart, stochastic programming has drawn increasingly more attention among decision-makers, and its applications span many fields including financial engineering, health care, communication systems, and supply chain management. On the flip side, stochastic programs are usually very difficult to solve, which is further compounded by the fact that in many of the aforementioned applications, we also have discrete decisions, thereby rendering these problems even more challenging. In this dissertation, we study the class of two-stage stochastic mixed-integer programs (SMIP), which, as its name suggests, lies at the confluence of two formidable classes of problems. We design a novel algorithm for this class of problems, and also explore specialized approaches for two related real-world applications. Although a number of algorithms have been developed to solve two-stage SMIPs, most of them deal with problems containing purely integer or continuous variables in either or both of the two stages, and frequently require the technology and/or recourse matrices to be deterministic. As a ground-breaking effort, in this work, we address the challenging class of two-stage SMIPs that involve 0-1 mixed-integer variables in both stages. The only earlier work on solving such problems (Carøe and Schultz (1999)) requires the optimization of several non-smooth Lagrangian dual problems using subgradient methods in the bounding process, which turns out to be computationally very expensive. We begin with proposing a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having 0-1 mixed-integer variables in both stages. Since the second-stage problems contain binary variables, their value functions are in general nonconvex and discontinuous; hence, the classical Benders' decomposition approach (or the L-shaped method) for solving two-stage stochastic programs, which requires convex subproblem value functions, cannot be directly applied. This motivates us to relax the second-stage problems and accompany this relaxation with a convexification process. To make this process computationally efficient, we propose to construct a certain partial convex hull representation of the two-stage solution space, using the relaxed second-stage constraints and the restrictions confining the first-stage variables to lie within some hyperrectangle. This partial convex hull is sequentially generated using a convexification scheme, such as the Reformulation-Linearization Technique (RLT), which yields valid inequalities that are functions of the first-stage variables and, of noteworthy importance, are reusable in the subsequent subproblems by updating the values of the first-stage variables. Meanwhile, since the first stage contains continuous variables, whenever we tentatively fix these variables at some given feasible values, the resulting constraints may not be facial with respect to the associated bounding constraints that are used to construct the partial convex hull. As a result, the constructed Benders' subproblems define lower bounds for the second-stage value functions, and likewise, the resulting Benders' master problem provides a lower bound for the original stochastic program defined over the same hyperrectangle. Another difficulty resulting from continuous first-stage variables is that when the given first-stage solution is not extremal with respect to its bounds, the second-stage solution obtained for a Benders' subproblem defined with respect to a partial convex hull representation in the two-stage space may not satisfy the model's binary restrictions. We thus need to be able to detect whether or not a Benders' subproblem is solved by a given fractional second-stage solution. We design a novel procedure to check this situation in the overall algorithmic scheme. A key property established, which ensures global convergence, is that these lower bounds become exact if the given first-stage solution is a vertex of the defining hyperrectangle, or if the second-stage solution satisfies the binary restrictions. Based on these algorithmic constructs, we design a branch-and-bound procedure where the branching process performs a hyperrectangular partitioning of the projected space of the first-stage variables, and lower bounds for the nodal problems are computed by applying the proposed modified Benders' decomposition method. We prove that, when using the least-lower-bound node-selection rule, this algorithm converges to a global optimal solution. We also show that the derived RLT cuts are not only reusable in subsequent Benders iterations at the same node, but are also inheritable by the subproblems of the children nodes. Likewise, the Benders' cuts derived for a given sub-hyperrectangle can also be inherited by the lower bounding master programs solved for its children nodes. Using these cut inheritance properties results in significant savings in the overall computational effort. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach. The sizes of the deterministic equivalent of our test problems range from having 386 continuous variables, 386 binary variables, and 386 constraints, up to 1795 continuous variables, 1539 binary variables, and 1028 constraints. The results reveal an average savings in computational effort by a factor of 9.5 in comparison with using a commercial mixed-integer programming package (CPLEX 8.1) on a deterministic equivalent formulation. We then explore an important application of SMIP to enhance the traditional airline fleet assignment models (FAM). Given a flight schedule network, the fleet assignment problem solved by airline companies is concerned with assigning aircraft to flight legs in order to maximize profit with respect to captured path- or itinerary-based demand. Because certain related crew scheduling regulations require early information regarding the type of aircraft serving each flight leg, the current practice adopted by airlines is to solve the fleet assignment problem using estimated demand data 10-12 weeks in advance of departure. Given the level of uncertainty, deterministic models at this early stage are inadequate to obtain a good match of aircraft capacity with passenger demands, and revisions to the initial fleet assignment become naturally pertinent when the observed demand differs considerably from the assigned aircraft capacities. From this viewpoint, the initial decision should embrace various market scenarios so that it incorporates a sufficient look-ahead feature and provides sufficient flexibility for the subsequent re-fleeting processes to accommodate the inevitable demand fluctuations. With this motivation, we propose a two-stage stochastic programming approach in which the first stage is concerned with the initial fleet assignment decisions and, unlike the traditional deterministic methodology, focuses on making only a family-level assignment to each flight leg. The second stage subsequently performs the detailed assignments of fleet types within the allotted family to each leg under each of the multiple potential scenarios that address corresponding path- or itinerary-based demands. In this fashion, the initial decision of what aircraft family should serve each flight leg accomplishes the purpose of facilitating the necessary crew scheduling decisions, while judiciously examining the outcome of future re-fleeting actions based on different possible demand scenarios. Hence, when the actual re-fleeting process is enacted several weeks later, this anticipatory initial family-level assignment will hopefully provide an improved overall fleet type re-allocation that better matches demand. This two-stage stochastic model is complemented with a secondary model that performs adjustments within each family, if necessary, to provide a consistent fleet type-assignment information for accompanying decision processes, such as yield management. We also propose several enhanced fleet assignment models, including a robust optimization model that controls decision variation among scenarios and a stochastic programming model that considers the recapture effect of spilled demand. In addition to the above modeling concepts and framework, we also contribute in developing effective solution approaches for the proposed model, which is a large-scale two-stage stochastic 0-1 mixed-integer program. Because the most pertinent information needed from the initial fleet assignment is at the family level, and the type-level assignment is subject to change at the re-fleeting stage according to future demand realizations, our solution approach focuses on assigning aircraft families to the different legs in the flight network at the first stage, while finding relaxed second-stage solutions under different demand scenarios. Based on a polyhedral study of a subsystem extracted from the original model, we derive certain higher-dimensional convex hull as well as partial convex hull representations for this subsystem. Accordingly, we propose two variants for the primary model, both of which relax the binary restrictions on the second-stage variables, but where the second variant then also accommodates the partial convex hull representations, yielding a tighter, albeit larger, relaxation. For each variant, we design a suitable solution approach predicated on Benders' decomposition methodology. Using certain realistic large-scale flight network test problems having 900 flight legs and 1,814 paths, as obtained from United Airlines, the proposed stochastic modeling approach was demonstrated to increase daily expected profits by about 3% (which translates to about $160 million per year) in comparison with the traditional deterministic model in present usage, which considers only the expected demand. Only 1.6% of the second-stage binary variables turn out to be fractional in the first variant, and this number is further reduced to 1.2% by using the tighter variant. Furthermore, when attempting to solve the deterministic equivalent formulation for these two variants using a commercial mixed-integer programming package (CPLEX 8.1), both the corresponding runs were terminated after reaching a 25-hour cpu time limit. At termination, the software was still processing the initial LP relaxation at the root node for each of these runs, and no feasible basis was found. Using the proposed algorithms, on the other hand, the solution times were significantly reduced to 5 and 19 hours for the two variants, respectively. Considering that the fleet assignment models are solved around three months in advance of departure, this solution time is well acceptable at this early planning stage, and the improved quality in the solution produced by considering the stochasticity in the system is indeed highly desirable. Finally, we address another practical workforce planning problem encountered by a global financial firm that seeks to manage multi-category workforce for functional areas located at different service centers, each having office-space and recruitment-capacity constraints. The workforce demand fluctuates over time due to market uncertainty and dynamic project requirements. To hedge against the demand fluctuations and the inherent uncertainty, we propose a two-stage stochastic programming model where the first stage makes personnel recruiting and allocation decisions, while the second stage, based on the given personnel decision and realized workforce demand, decides on the project implementation assignment. The second stage of the proposed model contains binary variables that are used to compute and also limit the number of changes to the original plan. Since these variables are concerned with only one quality aspect of the resulting workforce plan and do not affect feasibility issues, we replace these binary variables with certain conservative policies regarding workforce assignment change restrictions in order to obtain more manageable subproblems that contain purely continuous variables. Numerical experiments reveal that the stochastic programming approach results in significantly fewer alterations to the original workforce plan. When using a commercial linear programming package CPLEX 9.0 to solve the deterministic equivalent form directly, except for a few small-sized problems, this software failed to produce solutions due to memory limitations, while the proposed Benders' decomposition-based solution approach consistently solved all the practical-sized test problems with reasonable effort. To summarize, this dissertation provides a significant advancement in the algorithmic development for solving two-stage stochastic mixed-integer programs having 0-1 mixed-integer variables in both stages, as well as in its application to two important contemporary real-world applications. The framework for the proposed solution approaches is to formulate tighter relaxations via partial convex hull representations and to exploit the resulting structure using suitable decomposition methods. As decision robustness is becoming increasingly relevant from an economic viewpoint, and as computer technological advances provide decision-makers the ability to explore a wide variety of scenarios, we hope that the proposed algorithms will have a notable positive impact on solving stochastic mixed-integer programs. In particular, the proposed stochastic programming airline fleet assignment and the workforce planning approaches studied herein are well-poised to enhance the profitability and robustness of decisions made in the related industries, and we hope that similar improvements are adapted by more industries where decisions need to be made in the light of data that is shrouded by uncertainty. / Ph. D.

Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase.   Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature.   The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.

Internal audit departments strive to control risk within an organization. To do this they choose specific audit areas to include in an audit plan. In order to select areas, they usually focus on those areas with the highest risk. Even though high risk areas are considered, there are various other restrictions such as resource constraints (in terms of funds, manpower and hours) that must also be considered. In some cases, management might also have special requirements. Traditionally this area selection process is conducted using manual processes and requires significant decision maker experience. This makes it difficult to take all possibilities into consideration while also catering for all resource constraints and special management requirements. In this study, mathematical techniques used in capital budgeting problems are explored to solve the IT audit area selection problem. A DSS is developed which implements some of these mathematical techniques such as a linear programming model, greedy heuristic, improved greedy heuristic and evolutionary heuristic. The DSS also implements extensions to the standard capital budgeting model to make provision for special management requirements. The performance of the mathematical techniques in the DSS is tested by applying different decision rules to each of the techniques and comparing those results. The DSS, empirical experiments and results are also presented in this research study. Results have shown that in most cases a binary 0-1 model outperformed the other techniques. Internal audit management should therefore consider this model to assist with the construction of an IT internal audit plan. / MSc (Computer Science), North-West University, Potchefstroom Campus, 2015

Internal audit departments strive to control risk within an organization. To do this they choose specific audit areas to include in an audit plan. In order to select areas, they usually focus on those areas with the highest risk. Even though high risk areas are considered, there are various other restrictions such as resource constraints (in terms of funds, manpower and hours) that must also be considered. In some cases, management might also have special requirements. Traditionally this area selection process is conducted using manual processes and requires significant decision maker experience. This makes it difficult to take all possibilities into consideration while also catering for all resource constraints and special management requirements. In this study, mathematical techniques used in capital budgeting problems are explored to solve the IT audit area selection problem. A DSS is developed which implements some of these mathematical techniques such as a linear programming model, greedy heuristic, improved greedy heuristic and evolutionary heuristic. The DSS also implements extensions to the standard capital budgeting model to make provision for special management requirements. The performance of the mathematical techniques in the DSS is tested by applying different decision rules to each of the techniques and comparing those results. The DSS, empirical experiments and results are also presented in this research study. Results have shown that in most cases a binary 0-1 model outperformed the other techniques. Internal audit management should therefore consider this model to assist with the construction of an IT internal audit plan. / MSc (Computer Science), North-West University, Potchefstroom Campus, 2015