Integer Programming (IP) is a powerful and widely-used formulation for combinatorial problems. The study of IP over the past several decades has led to fascinating theoretical developments, and has improved our ability to solve discrete optimization problems arising in practice. This thesis makes progress on algorithmic solutions for IP by building on combinatorial, geometric and Linear Programming (LP) approaches. We use a combinatorial approach to give an approximation algorithm for the feedback vertex set problem (FVS) in a recently developed Implicit Hitting Set framework. Our algorithm is a simple online algorithm which finds a nearly optimal FVS in random graphs. We also propose a planted model for FVS and show that an optimal hitting set for a polynomial number of subsets is sufficient to recover the planted subset. Next, we present an unexplored geometric connection between integer feasibility and the classical notion of discrepancy of matrices. We exploit this connection to show a phase transition from infeasibility to feasibility in random IP instances. A recent algorithm for small discrepancy solutions leads to an efficient algorithm to find an integer point for random IP instances that are feasible with high probability. Finally, we give a provably efficient implementation of a cutting-plane algorithm for perfect matchings. In our algorithm, cuts separating the current optimum are easy to derive while a small LP is solved to identify the cuts that are to be retained for later iterations. Our result gives a rigorous theoretical explanation for the practical efficiency of the cutting plane approach for perfect matching evident from implementations. In summary, this thesis contributes to new models and connections, new algorithms and rigorous analysis of well-known approaches for IP.

In this thesis, we use integer programming techniques to solve the resource constrained shortest path problem (RCSPP) which seeks a minimum cost path between two nodes in a directed graph subject to a finite set of resource constraints. Although NP-hard, the RCSPP is extremely useful in practice and often appears as a subproblem in many decomposition schemes for difficult optimization problems. We begin with a study of the RCSPP polytope for the single resource case and obtain several new valid inequality classes. Separation routines are provided, along with a polynomial time algorithm for constructing an auxiliary conflict graph which can be used to separate well known valid inequalities for the node packing polytope. We establish some facet defining conditions when the underlying graph is acyclic and develop a polynomial time sequential lifting algorithm which can be used to strengthen one of the inequality classes. Next, we outline a branch-and-cut algorithm for the RCSPP. We present preprocessing techniques and branching schemes which lead to strengthened linear programming relaxations and balanced search trees, and the majority of the new inequality classes are generalized to consider multiple resources. We describe a primal heuristic scheme that uses fractional solutions, along with the current incumbent, to search for new feasible solutions throughout the branch-and-bound tree. A computational study is conducted to evaluate several implementation choices, and the results demonstrate that our algorithm outperforms the default branch-and-cut algorithm of a leading integer programming software package. Finally, we consider the dial-a-flight problem (DAFP), a new vehicle routing problem that arises in the context of on-demand air transportation and is concerned with the scheduling of a set of travel requests for a single day of operations. The DAFP can be formulated as an integer multicommodity network flow model consisting of several RCSPPs linked together by set partitioning constraints which guarantee that all travel requests are satisfied. Therefore, we extend our branch-and-cut algorithm for the RCSPP to solve the DAFP. Computational experiments with practical instances provided by the DayJet Corporation verify that the extended algorithm also outperforms the default branch-and-cut algorithm of a leading integer programming software package.

This report aimed to develop algorithms for solving the optimization problem of matchingbuy and sell orders in call auctions while minimizing the number of transactions. The developed algorithms were evaluated based on their execution time and solution accuracy.The study found that the problem was more difficult to solve than initially anticipated, and commercial solvers were inadequate for the task. The data’s characteristics werecritical to the algorithms’ performance, and the lack of specifications for instruments andexchange posed a challenge. The algorithms were tested on a broad range of datasets with different characteristics, as well as real trades of stocks from the Stockholm Stock Exchange. Evaluating the best-performing algorithm became a trade-off between time and accuracy, where the quickest algorithm did not have the highest solution accuracy. Therefore, the importance of these factors should be considered before deciding which algorithm to implement. Eight algorithms were evaluated: four greedy algorithms and four clusteralgorithms capable of identifying 2-1 and 3-1 matches. If execution time is the single most crucial factor, the Unsorted Greedy Algorithm should be considered. However, if accuracyi s a priority, the Cluster 3-1 & 1-3 Algorithm should be considered, even though it takes longer to find a solution. Ultimately, the report concluded that while no single algorithm can be definitively la-beled as the best, the Cluster 2-1 Algorithm strikes the most effective balance between execution time and solution accuracy, while also remaining relatively stable in perfor-mance for all test cases. The recommendation was based on the fact that the Cluster 2-1 Algorithm proved to be the quickest of the developed cluster algorithms, and that cluster algorithms were able to find the best solutions for all tested data sets. This study successfully addressed its purpose by developing eight algorithms that solved the given problem and suggested an appropriate algorithm that strikes a balance between execution time and solution quality.

Le calcul du nombre chromatique et la détermination d'une colo- ration optimale des sommets d'un graphe sont des problèmes NP- difficiles en général. Ils peuvent cependant être résolus en temps po- lynomial dans les graphes parfaits. Par ailleurs, la perfection d'un graphe peut être décidée efficacement. Les graphes parfaits sont caractérisés par la structure de leur poly- tope des stables : les facettes non-triviales sont définies exclusivement par des inégalités de cliques. Réciproquement, une structure similaire des facettes du polytope des stables détermine-t-elle des propriétés combinatoires et algorithmiques intéressantes? Un graphe est h-parfait si les facettes non-triviales de son polytope des stables sont définies par des inégalités de cliques et de circuits impairs. On ne connaît que peu de résultats analogues au cas des graphes parfaits pour la h-perfection, et on ne sait pas si les problèmes sont NP-difficiles. Par exemple, les complexités algorithmiques de la re- connaissance des graphes h-parfaits et du calcul de leur nombre chro- matique sont toujours ouvertes. Par ailleurs, on ne dispose pas de borne sur la différence entre le nombre chromatique et la taille maxi- mum d'une clique d'un graphe h-parfait. Dans cette thèse, nous montrons tout d'abord que les opérations de t-mineurs conservent la h-perfection (ce qui fournit une extension non triviale d'un résultat de Gerards et Shepherd pour la t-perfection). De plus, nous prouvons qu'elles préservent la propriété de décompo- sition entière du polytope des stables. Nous utilisons ce résultat pour répondre négativement à une question de Shepherd sur les graphes h-parfaits 3-colorables. L'étude des graphes minimalement h-imparfaits (relativement aux t-mineurs) est liée à la recherche d'une caractérisation co-NP com- binatoire de la h-perfection. Nous faisons l'inventaire des exemples connus de tels graphes, donnons une description de leur polytope des stables et énonçons plusieurs conjectures à leur propos. D'autre part, nous montrons que le nombre chromatique (pondéré) de certains graphes h-parfaits peut être obtenu efficacement en ar- rondissant sa relaxation fractionnaire à l'entier supérieur. Ce résultat implique notamment un nouveau cas d'une conjecture de Goldberg et Seymour sur la coloration d'arêtes. Enfin, nous présentons un nouveau paramètre de graphe associé aux facettes du polytope des couplages et l'utilisons pour donner un algorithme simple et efficace de reconnaissance des graphes h- parfaits dans la classe des graphes adjoints. / Computing the chromatic number and finding an optimal coloring of a perfect graph can be done efficiently, whereas it is an NP-hard problem in general. Furthermore, testing perfection can be carried- out in polynomial-time. Perfect graphs are characterized by a minimal structure of their sta- ble set polytope: the non-trivial facets are defined by clique-inequalities only. Conversely, does a similar facet-structure for the stable set polytope imply nice combinatorial and algorithmic properties of the graph ? A graph is h-perfect if its stable set polytope is completely de- scribed by non-negativity, clique and odd-circuit inequalities. Statements analogous to the results on perfection are far from being understood for h-perfection, and negative results are missing. For ex- ample, testing h-perfection and determining the chromatic number of an h-perfect graph are unsolved. Besides, no upper bound is known on the gap between the chromatic and clique numbers of an h-perfect graph. Our first main result states that the operations of t-minors keep h- perfection (this is a non-trivial extension of a result of Gerards and Shepherd on t-perfect graphs). We show that it also keeps the Integer Decomposition Property of the stable set polytope, and use this to answer a question of Shepherd on 3-colorable h-perfect graphs in the negative. The study of minimally h-imperfect graphs with respect to t-minors may yield a combinatorial co-NP characterization of h-perfection. We review the currently known examples of such graphs, study their stable set polytope and state several conjectures on their structure. On the other hand, we show that the (weighted) chromatic number of certain h-perfect graphs can be obtained efficiently by rounding-up its fractional relaxation. This is related to conjectures of Goldberg and Seymour on edge-colorings. Finally, we introduce a new parameter on the complexity of the matching polytope and use it to give an efficient and elementary al- gorithm for testing h-perfection in line-graphs.

Approved for public release, distribution is unlimited / This thesis develops an integer linear program called MSAMT (Model to Schedule Army Maneuver Training) to schedule an Army installation's maneuver training. We demonstrate MSAMT using a data set containing 261 platoon-level, 67 company-level and 18 battalion-level units, and 7 major training areas located at Fort Hood, Texas. Using a typical near-term planning horizon from 6 to 8 weeks, MSAMT schedules daily training for a randomly selected set of the stationed units and training requirements. For a 6-week time period and almost 65% (63 platoons 16 companies and 5 battalions) of the units there are 151 platoon-level, 51 company-level and 11 battalion-level required tasks of which MSAMT can schedule 93%. When the subset of units is increased to 80% (75 platoons, 20 companies, 6 battalions), there are 187 platoon-level, 62 company-level and 11 battalion-level tasks of which MSAMT can schedule only 85%. Maintaining the 80% unit level but having an 8 weekperiod increases required training achieved to 94%. Such results can help determine the ability of an Army installation to satisfy training requirements of its stationed units as well as identify a shortage or excess in available training land. It can show the training impact of changing the quantity of units at an installation and thereby aid in base realignment and closure decisions. / First Lieutenant, Turkish Army

Muitos problemas de otimização envolvem tanto variáveis inteiras quanto contínuas e podem ser modelados como problemas de programação não-linear inteira mista. Problemas dessa natureza aparecem com freqüência em engenharia química e incluem, por exemplo, síntese de processos, projeto de colunas de destilação, síntese de rede de trocadores de calor e produção de óleo e gás. Neste trabalho, apresentamos algoritmos baseados em Lagrangianos Aumentados e branch and bound para resolver problemas de programação não-linear inteira mista. Duas abordagens são consideradas. Na primeira delas, um algoritmo do tipo Lagrangianos Aumentados é usado como método para resolver os problemas de programação não-linear que aparecem em cada um dos nós do método branch and bound. Na segunda abordagem, usamos o branch and bound para resolver os problemas de minimização em caixas com variáveis inteiras que aparecem como subproblemas do método de Lagrangianos Aumentados. Ambos os algoritmos garantem encontrar a solução ótima de problemas convexos e oferecem recursos apropriados para serem usados na resolução de problemas não convexos, apesar de não haver garantia de otimalidade nesse caso. Apresentamos um problema de empacotamento de retângulos em regiões convexas arbitrárias e propomos modelos para esse problema que resultam em programas não-lineares com variáveis inteiras e contínuas. Realizamos alguns experimentos numéricos e comparamos os resultados obtidos pelo método descrito neste trabalho com os resultados alcançados por outros métodos. Também realizamos experimentos com problemas de programação não-linear inteira mista encontrados na literatura e comparamos o desempenho do nosso método ao de outro disponível publicamente. / Many optimization problems contain both integer and continuous variables and can be modeled as mixed-integer nonlinear programming problems. Problems of this nature appear frequently in chemical engineering and include, for instance, process synthesis, design of distillation columns, heat exchanger network synthesis and oil and gas production. In this work, we present algorithms based on Augmented Lagrangians and branch and bound for solving mixed-integer nonlinear programming problems. Two approaches are considered. In the first one, an Augmented Lagrangian algorithm is used for solving nonlinear programming problems that appear at each node in the branch and bound method. In the second approach, we use a branch and bound method for solving box-constrained problems with integer variables that appear as subproblems of the Augmented Lagrangian algorithm. Both algorithms guarantee to find an optimal solution for convex problems and have appropriate strategies to deal with non-convex problems, although there is no guarantee of optimality in this case. We present a problem of packing rectangles within an arbitrary convex region and propose models for this problem that result in nonlinear programs with integer and continuous variables. We have performed some numerical experiments and compared the results reached by the method described in this work and the results obtained by other methods. We have also performed experiments with mixed-integer nonlinear programming problems found in the literature and compared the performance of our method to that of other method publicly available.

In this thesis we develop integer programming approaches for solving network flow problems with equal-split restrictions. Such problems arise in traffic engineering of internet protocol networks. Equal-split structure is used in protocols like OSPF and IS-IS that allow flow to be split among the multiple shortest paths. Equal-split assumptions also arise in peer-to-peer networks and road optimization problems. All the previous work on this problem has been focused on developing heuristic methods for the specific applications. We are the first ones to study the problem as a general network flow problem and provide a polyhedral study. First we consider a general multi-commodity network flow problem with equal split restrictions. This problem is NP-hard in general. We perform a polyhedral study on mixed integer linear programming formulation for this problem. Valid inequalities are obtained, and are incorporated within a branch-and-cut framework to solve the problem. We provide fast separation schemes for most of the families of valid inequalities. Computational results are presented to show the effectiveness of cutting plane families. Next, we consider the OSPF weight setting problem. We propose an integer programming formulation for this problem. A decomposition based approach to solve the problem is presented next. Valid inequalities, exploiting the structure, are obtained for this problem. We also propose heuristic methods to get good starting solutions for the problem. The proposed cutting planes and heuristic methods are integrated within a branch-and-cut framework to solve the problem. We present computational experiments that demonstrate the effectiveness of our approach to obtain solutions with tight optimality gaps as compared with default CPLEX. Finally, we consider an equal split flow problem on bipartite graphs. We present an integer programming formulation for this problem that models the equal-split in a different way than the multi-commodity network flow problem discussed before. Valid inequalities and heuristic methods for this problem are proposed, and are integrated within the branch-and-cut framework. We present computational experiments demonstrating the effectiveness of our solution strategy. We present an alternate formulation for the problem with some favorable polyhedral properties. Lastly, a computational comparison between the two formulations is presented.

Avec l’apparition du véhicule électrique, le besoin électrique est en progression constante. La taille des batteries étant contrainte et leurs performances étant limitées, il est devenu indispensable de disposer d’une Gestion de l’Energie Electrique (GEE) performante. Il est donc nécessaire de maitriser l’énergie et la puissance disponibles de l’accumulateur grâce à des estimateurs d’états internes. Ce travail de thèse présente une étude détaillée de la modélisation des accumulateurs lithium-ion à partir de la théorie des électrodes poreuses ainsi que des méthodes de paramétrisation de ces modèles. Sur la base de cette étude, des structures d’observation de l’état de charge d’un accumulateur lithium-ion ont été créées. Ces structures permettent d’estimer l’état de charge de manière fiable tout en prenant en compte des erreurs de mesures des courants et tensions mises en jeu. / In electric cars, electrical need increases continuously. Since, the battery size is limited and its performances do not improve any more, it is essential to have a high-performance electrical energy management. It is thus necessary to control the battery resources, in terms of available energy and power, thanks to an ageing-integrated state estimator. This thesis work presents a detailed study of the modeling of the lithium-ion battery thanks to the porous electrodes theory and parameterization methods of these models. Following this study, structures of observation of the SOC of lithium-ion batteries has been made. Those structures allow us to estimate the Soc in a reliable way taking into account of currents and voltages errors involved.

Muitos problemas de otimização envolvem tanto variáveis inteiras quanto contínuas e podem ser modelados como problemas de programação não-linear inteira mista. Problemas dessa natureza aparecem com freqüência em engenharia química e incluem, por exemplo, síntese de processos, projeto de colunas de destilação, síntese de rede de trocadores de calor e produção de óleo e gás. Neste trabalho, apresentamos algoritmos baseados em Lagrangianos Aumentados e branch and bound para resolver problemas de programação não-linear inteira mista. Duas abordagens são consideradas. Na primeira delas, um algoritmo do tipo Lagrangianos Aumentados é usado como método para resolver os problemas de programação não-linear que aparecem em cada um dos nós do método branch and bound. Na segunda abordagem, usamos o branch and bound para resolver os problemas de minimização em caixas com variáveis inteiras que aparecem como subproblemas do método de Lagrangianos Aumentados. Ambos os algoritmos garantem encontrar a solução ótima de problemas convexos e oferecem recursos apropriados para serem usados na resolução de problemas não convexos, apesar de não haver garantia de otimalidade nesse caso. Apresentamos um problema de empacotamento de retângulos em regiões convexas arbitrárias e propomos modelos para esse problema que resultam em programas não-lineares com variáveis inteiras e contínuas. Realizamos alguns experimentos numéricos e comparamos os resultados obtidos pelo método descrito neste trabalho com os resultados alcançados por outros métodos. Também realizamos experimentos com problemas de programação não-linear inteira mista encontrados na literatura e comparamos o desempenho do nosso método ao de outro disponível publicamente. / Many optimization problems contain both integer and continuous variables and can be modeled as mixed-integer nonlinear programming problems. Problems of this nature appear frequently in chemical engineering and include, for instance, process synthesis, design of distillation columns, heat exchanger network synthesis and oil and gas production. In this work, we present algorithms based on Augmented Lagrangians and branch and bound for solving mixed-integer nonlinear programming problems. Two approaches are considered. In the first one, an Augmented Lagrangian algorithm is used for solving nonlinear programming problems that appear at each node in the branch and bound method. In the second approach, we use a branch and bound method for solving box-constrained problems with integer variables that appear as subproblems of the Augmented Lagrangian algorithm. Both algorithms guarantee to find an optimal solution for convex problems and have appropriate strategies to deal with non-convex problems, although there is no guarantee of optimality in this case. We present a problem of packing rectangles within an arbitrary convex region and propose models for this problem that result in nonlinear programs with integer and continuous variables. We have performed some numerical experiments and compared the results reached by the method described in this work and the results obtained by other methods. We have also performed experiments with mixed-integer nonlinear programming problems found in the literature and compared the performance of our method to that of other method publicly available.

With an increasingly large amount of data being collected in numerous application areas, the importance of online analytical processing (OLAP) workloads increases constantly. OLAP queries typically access only a small number of columns but a high number of rows and are, thus, most efficiently executed by column-stores. With the significant developments in the main memory domain even large datasets can be entirely held in the main memory. Thus, main memory column-stores have been established as state-of-the-art for OLAP scenarios. In these systems, all values of every column are encoded as a sequence of integer values and, thus, query processing is completely done on these integer sequences. To improve query processing, vectorization based the Single Instruction Multiple Data (SIMD) parallel paradigm is a state-of-the-art technique. Aside from vectorization, lightweight integer compression algorithms also play an important role to reduce the necessary memory space. Unfortunately, there is no single-best lightweight integer compression algorithm, and the algorithm selection decision depends most importantly on the data characteristics. Nevertheless, vectorization and integer compression complement each other, and the combined usage improves the query performance. Unfortunately, the benefits of vectorization are limited on modern x86-processors due to predefined and fixed SIMD instruction set extensions. Nowadays, the Field Programmable Gate Array (FPGA) offers a novel opportunity with regard to hardware reconfigurable capability. For example, we can use an arbitrary length of processor word in FPGA leading to a higher performance, we can prepare proper pipeline-based custom-made database accelerators, and we can develop embedded systems through utilizing such accelerators. Moreover, modern hybrid CPU-FPGA systems have a direct data communication channel between the main memory and FPGA which is useful for throughput acceleration. Based on these advantages, this thesis examines the utilization of FPGA for main memory column-stores. This examination is two-fold. First, we investigate the column scan on compressed data as important operation and second, we systematically look at lightweight integer compression. These two aspects are considered from the hardware perspective to guarantee a certain level of query performance acceleration. In particular, this thesis explores different embedded design options and proposes an adaptive lightweight integer compression system. Based on a comprehensive evaluation, we find out the optimal design constraint as per implementation mechanism for column scan and lightweight integer compression. Finally, we conclude this thesis by mentioning our upcoming research activities.:CONTENTS PAGE 1 INTRODUCTION 1 1.1 Analytical Data Systems 2 1.2 Query Acceleration 3 1.3 Thesis Contributions 5 2 BACKGROUND AND PROBLEM DEFINITION 7 2.1 Main Memory Column-Store Database Systems 8 2.2 State-of-the-art Optimization of Query Processing 11 2.2.1 Optimization using SIMD-Vectorization 11 2.2.2 Optimization using GPU-Accelerator 13 2.2.3 Summary 14 2.3 Opportunities and Challenges of FPGA-based Acceleration 15 2.3.1 Hybrid CPU-FPGA Architecture 15 2.3.2 Related Works on FPGA-based Acceleration 17 2.3.3 Research Challenges 19 3 COLUMN SCAN ON COMPRESSED DATA 21 3.1 Column Scan 22 3.1.1 Naïve 22 3.1.2 BitWeaving 24 3.1.3 SIMD Implementation 26 3.2 FPGA Implementation 29 3.2.1 Processing Element 30 3.2.2 Basic Architecture 31 3.2.3 Hybrid Architecture 31 3.3 Comparative Evaluation 32 3.3.1 SIMD Evaluation 33 3.3.2 FPGA Evaluation 36 3.4 Lessons Learned and Summary 38 4 ADAPTIVE LIGHTWEIGHT COMPRESSION SYSTEM 40 4.1 Lightweight Integer Compression 41 4.1.1 Overview and Classification 41 4.1.2 State-of-the-art Implementation Concepts 43 4.1.3 Discussion 46 4.2 FPGA-based Implementation of Lightweight Integer Compression Algorithms 46 4.2.1 Recap FPGA-based Architecture 47 4.2.2 Custom-made Compression HW Implementation 47 4.2.3 Lightweight Integer Compression System Implementation 56 4.2.4 Discussion 57 4.3 Adaptive Compression Systems 57 4.3.1 User-Specified Adaptive System 58 4.3.2 HW-Specified Adaptive Systems 59 4.4 Experimental Evaluation 63 4.4.1 Data Properties Definition 64 4.4.2 Physical-Level Compression 65 4.4.3 Logical-Level Compression 67 4.4.4 Cascaded Compression 69 4.4.5 Adaptive Compression 74 4.5 Lessons Learned and Summary 78 5 CONCLUSION AND FUTURE WORK 81 5.1 Conclusion 82 5.2 Future Work 84 BIBLIOGRAPHY 86 LIST OF FIGURES 91 LIST OF TABLES 94 CONTENTS