" In the last decade, cloud computing became popular among companies for outsourcing some of their services. Companies use cloud services to store crucial information such as financial and client data. Cloud services are not only cost effective but also easier to manage since the companies avoid maintenance of servers. Although cloud has its advantages, maintaining the security is a big concern. Cloud services might not have any malicious intent, but attacks targeting cloud systems could easily steal vital data belong to the companies. The only protection that assures the security of the information is a strong encryption. However, these schemes only protects the information but prevent you to do any computation on the data. This was an open problem for more than 30 years and it has been solved recently by the introduction of the first fully homomorphic encryption (FHE) scheme by Gentry. The FHE schemes allow you to do arbitrary computation on an encrypted data by still preserving the encryption. Namely, the message is not revealed (decrypted) at any given time while computing the arbitrary circuit. However, the first FHE scheme is not practical for any practical application. Later, numerous research work has been published aiming at making fully homomorphic encryption practical for daily use, but still they were too inefficient to be used in everyday practical applications. In this dissertation we tackle the efficiency problems of fully homomorphic encryption (FHE) schemes. We propose two new FHE schemes that improve the storage requirement and runtime performance. The first scheme (Doröz, Hu and Sunar) reduces the size of the evaluation keys in existing NTRU based FHE schemes. In the second scheme (F-NTRU) we designed an NTRU based FHE scheme which is not only free of costly evaluation keys but also competitive in runtime performance. We further proposed two hardware accelerators to increase the performance of arithmetic operations underlying the schemes. The first accelerator is a custom hardware architecture for realizing the Gentry-Halevi fully homomorphic encryption scheme. This contribution presents the first full realization of FHE in hardware. The architecture features an optimized multi-million bit multiplier based on the Schönhage-Strassen multiplication algorithm. Moreover, a number of optimizations including spectral techniques as well as a precomputation strategy is used to significantly improve the performance of the overall design. The other accelerator is optimized for a class of reconfigurable logic for somewhat homomorphic encryption (SWHE) based schemes. Our design works as a co-processor: the most compute-heavy operations are offloaded to this specialized hardware. The core of our design is an efficient polynomial multiplier as it is the most compute-heavy operation of our target scheme. The presented architecture can compute the product of very-large polynomials more efficiently than software implementations on CPUs. Finally, to assess the performance of proposed schemes and hardware accelerators we homomorphically evaluate the AES and the Prince block ciphers. We introduce various optimizations including a storage-runtime trade-off. Our benchmarking results show significant speedups over other existing instantiations. Also, we present a private information retrieval (PIR) scheme based on a modified version of Doröz, Hu and Sunar’s homomorphic scheme. The scheme is capable of privately retrieving data from a database containing 4 billion entries. We achieve asymptotically lower bandwidth cost compared to other PIR schemes which makes it more practical. "

Counting problems lead naturally to integer sequences. For example if one asks for the number of subsets of an $n$-set, the answer is $2^n$, or the integer sequence $1,~2,~4,~8,~ldots$. Conversely, given an integer sequence, or part of it, one may ask if there is an associated counting problem. There might be several different counting problems that produce the same integer sequence. To illustrate the nature of mathematical research involving integer sequences, we will consider Escher's counting problem and a generalization, as well as counting problems associated with the Catalan numbers, and the Collatz conjecture. We will also discuss the purpose of the On-Line-Encyclopedia of Integer Sequences.

Finding integer solutions to linear equations has various real world applications. In the thesis, we investigate its application to the reachability analysis of Petri nets. Introduced by Petri in 1962, Petri net has been a powerful mathematical formalism for modeling, analyzing and designing discrete event systems. In the research community of Petri nets, finding a feasible path from the initial state to the target state in Petri net, known as reachability analysis, is probably one of the most important and challenging subjects. The reachability algebraic analysis is equivalent to finding the nonnegative integer solutions to a fundamental equation constructed from the Petri net. We apply our algorithm in this thesis to reachability analysis of Petri net by finding the nonnegative integer solutions to the fundamental equation. / Finding the optimal binary solution to a quadratic object function is known as the Binary Quadratic Programming problem (BQP), which has been studied extensively in the last three decades. In this thesis, by investigating geometric features of the ellipse contour of a concave quadratic function, we derive new upper and lower bounding methods for BQP. Integrating these new bounding schemes into a proposed solution algorithm of a branch-and-bound type, we propose an exact solution method in solving general BQP with promising preliminary computational results. Meanwhile, by investigating some special structures of the second order matrix and linear term in BQP, several polynomial time algorithms are discussed to solve some special cases of BQP. / In the realm of integer programming, finding integer solutions to linear equations is another important research direction. The problem is proved to be NP-Complete, and several algorithms have been proposed such as the algorithm based on linear Diophantine equations as well as the method based on Groebner bases. Unlike the traditional algorithms, the new efficient method we propose in this thesis is based on our results on zero duality gap and the cell enumeration of an arrangement of hyperplanes in discrete geometry. / Integer programming plays an important role in operations research and has a wide range of applications in various fields. There are a lot of research directions in the area of integer programming. In this thesis, two main topics will be investigated in details. One is to find the optimal binary solution to a quadratic object function, and the other is to find integer solutions to linear equations. / Gu, Shenshen. / Adviser: Wang Jun. / Source: Dissertation Abstracts International, Volume: 73-01, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 98-103). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

by Lui Oi Lun Irene. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2001. / Includes bibliographical references (leaves 128-132). / Abstracts in English and Chinese. / List of Figures --- p.vii / List of Tables --- p.viii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Satisfiability Problem --- p.1 / Chapter 1.2 --- Motivation of the Research --- p.1 / Chapter 1.3 --- Overview of the Thesis --- p.2 / Chapter 2 --- Constraint Satisfaction Problem and Satisfiability Problem --- p.4 / Chapter 2.1 --- Constraint Programming --- p.4 / Chapter 2.2 --- Satisfiability Problem --- p.6 / Chapter 2.3 --- Methods in Solving SAT problem --- p.7 / Chapter 2.3.1 --- Davis-Putnam-Loveland Procedure --- p.7 / Chapter 2.3.2 --- SATZ by Chu-Min Li --- p.8 / Chapter 2.3.3 --- Local Search for SAT --- p.11 / Chapter 2.3.4 --- Integer Linear Programming Method for SAT --- p.12 / Chapter 2.3.5 --- Semidefinite Programming Method --- p.13 / Chapter 2.4 --- Softwares for SAT --- p.15 / Chapter 2.4.1 --- SAT01 --- p.15 / Chapter 2.4.2 --- "SATZ and SATZ213, contributed by Chu-Min Li" --- p.15 / Chapter 2.4.3 --- Others --- p.15 / Chapter 3 --- Integer Programming --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.1.1 --- Formulation of IPs and BIPs --- p.18 / Chapter 3.1.2 --- Binary Search Tree --- p.19 / Chapter 3.2 --- Methods in Solving IP problem --- p.19 / Chapter 3.2.1 --- Branch-and-Bound Method --- p.20 / Chapter 3.2.2 --- Cutting-Plane Method --- p.23 / Chapter 3.2.3 --- Duality in Integer Programming --- p.26 / Chapter 3.2.4 --- Heuristic Algorithm --- p.28 / Chapter 3.3 --- Zero-one Optimization and Continuous Relaxation --- p.29 / Chapter 3.3.1 --- Introduction --- p.29 / Chapter 3.3.2 --- The Roof Dual expressed in terms of Lagrangian Relaxation --- p.30 / Chapter 3.3.3 --- Determining the Existence of a Duality Gap --- p.31 / Chapter 3.4 --- Software for solving Integer Programs --- p.33 / Chapter 4 --- Integer Programming Formulation for SAT Problem --- p.35 / Chapter 4.1 --- From 3-CNF SAT Clauses to Zero-One IP Constraints --- p.35 / Chapter 4.2 --- From m-Constrained IP Problem to Singly-Constrained IP Problem --- p.38 / Chapter 4.2.1 --- Example --- p.39 / Chapter 5 --- A Basic Branch-and-Bound Algorithm for the Zero-One Polynomial Maximization Problem --- p.42 / Chapter 5.1 --- Reason for choosing Branch-and-Bound Method --- p.42 / Chapter 5.2 --- Searching Algorithm --- p.43 / Chapter 5.2.1 --- Branch Rule --- p.44 / Chapter 5.2.2 --- Bounding Rule --- p.46 / Chapter 5.2.3 --- Fathoming Test --- p.46 / Chapter 5.2.4 --- Example --- p.47 / Chapter 6 --- Revised Bound Rule for Branch-and-Bound Algorithm --- p.55 / Chapter 6.1 --- Revised Bound Rule --- p.55 / Chapter 6.1.1 --- CPLEX --- p.57 / Chapter 6.2 --- Example --- p.57 / Chapter 6.3 --- Conclusion --- p.65 / Chapter 7 --- Revised Branch Rule for Branch-and-Bound Algorithm --- p.67 / Chapter 7.1 --- Revised Branch Rule --- p.67 / Chapter 7.2 --- Comparison between Branch Rule and Revised Branch Rule --- p.69 / Chapter 7.3 --- Example --- p.72 / Chapter 7.4 --- Conclusion --- p.73 / Chapter 8 --- Experimental Results and Analysis --- p.80 / Chapter 8.1 --- Experimental Results --- p.80 / Chapter 8.2 --- Statistical Analysis --- p.33 / Chapter 8.2.1 --- Analysis of Search Techniques --- p.83 / Chapter 8.2.2 --- Discussion of the Performance of SATZ --- p.85 / Chapter 9 --- Concluding Remarks --- p.87 / Chapter 9.1 --- Conclusion --- p.87 / Chapter 9.2 --- Suggestions for Future Research --- p.88 / Chapter A --- Searching Procedures for Solving Constraint Satisfaction Problem (CSP) --- p.91 / Chapter A.1 --- Notation --- p.91 / Chapter A.2 --- Procedures for Solving CSP --- p.92 / Chapter A.2.1 --- Generate and Test --- p.92 / Chapter A.2.2 --- Standard Backtracking --- p.93 / Chapter A.2.3 --- Forward Checking --- p.94 / Chapter A.2.4 --- Looking Ahead --- p.95 / Chapter B --- Complete Results for Experiments --- p.96 / Chapter B.1 --- Complete Result for SATZ --- p.96 / Chapter B.1.1 --- n =5 --- p.95 / Chapter B.1.2 --- n = 10 --- p.98 / Chapter B.1.3 --- n = 30 --- p.99 / Chapter B.2 --- Complete Result for Basic Branch-and-Bound Algorithm --- p.101 / Chapter B.2.1 --- n二5 --- p.101 / Chapter B.2.2 --- n = 10 --- p.104 / Chapter B.2.3 --- n = 30 --- p.107 / Chapter B.3 --- Complete Result for Revised Bound Rule --- p.109 / Chapter B.3.1 --- n = 5 --- p.109 / Chapter B.3.2 --- n = 10 --- p.112 / Chapter B.3.3 --- n = 30 --- p.115 / Chapter B.4 --- Complete Result for Revised Branch-and-Bound Algorithm --- p.118 / Chapter B.4.1 --- n = 5 --- p.118 / Chapter B.4.2 --- n = 10 --- p.121 / Chapter B.4.3 --- n = 30 --- p.124 / Bibliography --- p.128

Modern problems arising in many domains are driving a need for more capable, state-of-the-art optimization tools. A sharp focus on performance and accuracy has appeared, for example, in science and engineering applications. In particular, we have seen a growth in studies related to Polynomial Optimization: a field with beautiful and deep theory, offering flexibility for modeling and high impact in diverse areas. The understanding of structural aspects of the feasible sets in Polynomial Optimization, mainly studied in Real Algebraic Geometry, has a long tradition in Mathematics and it has recently acquired increased computational maturity, opening the gate for new Optimization methodologies to be developed. The celebrated hierarchies due to Lasserre, for example, emerged as good algorithmic templates. They allow the representation of semi-algebraic sets, possibly non-convex, through convex sets in lifted spaces, thus enabling the use of long-studied Convex Optimization methods. Nonetheless, there are some computational drawbacks for these approaches: they often rely on possibly large semidefinite programs, and due to scalability and numerical issues associated with SDPs, alternatives and complements are arising. In this dissertation, we will explore theoretical and practical Integer-Programming-based techniques for Polynomial Optimization problems. We first present a Linear Programming relaxation for the AC-OPF problem in Power Systems, a non-convex quadratic problem, and show how such relaxation can be used to develop a tractable MIP-based algorithm for the AC Transmission Switching problem. From a more theoretical perspective, and motivated by the AC-OPF problem, we study how sparsity can be exploited as a tool for analysis of the fundamental complexity of a Polynomial Optimization problem, by showing LP formulations that can efficiently approximate sparse polynomial problems. Finally, we show a computationally practical approach for constructing strong LP approximations on-the-fly, using cutting plane approaches. We will show two different frameworks that can generate cutting planes, which are based on classical methods used in Mixed-Integer Programming. Our methods mainly rely on the maturity of current MIP technology; we believe these contributions are important for the development of manageable approaches to general Polynomial Optimization problems.

Sugar mills represent significant capital investments. To maintain appropriate returns on their investment, sugar companies seek to run the mills at capacity over the sugarcane harvest season. Because the sugar content of cane degrades considerably once it is cut, maintaining inventories of cut cane is undesirable. Instead, mills want to coordinate the arrival of cut cane with production. We present exact solution approaches exploiting special structure of the sugarcane harvest logistics problem in Brazil and the United States.

Automated theorem proving is a method to establish or disprove logical theorems. While these can be theorems in the classical mathematical sense, we are more concerned with logical encodings of properties of algorithms, hardware and software. Especially in the area of hardware verification, propositional logic is used widely in industry. Satisfiability Module Theories (SMT) is a set of logics which extend propositional logic with theories relevant for specific application domains. In particular, software verification has received much attention, and efficient algorithms have been devised for reasoning over arithmetic and data types. Built-in support for theories by decision procedures is often significantly more efficient than reductions to propositional logic (SAT). Most efficient SAT solvers are based on the DPLL architecture, which is also the basis for most efficient SMT solvers. The main shortcoming of both kinds of logics is the weak support for non-ground reasoning, which noticeably limits the applicability to real world systems. The Model Evolution Calculus (ME) was devised as a lifting of the DPLL architecture from the propositional setting to full first-order logic. In previous work, we created the solver Darwin as an implementation of ME, and showed how to adapt improvements from the DPLL setting. The first half of this thesis is concerned with ME and Darwin. First, we lift a further crucial ingredient of SAT and SMT solvers, lemma-learning, to Darwin and evaluate its benefits. Then, we show how to use Darwin for finite model finding, and how this application benefits from lemma-learning. In the second half of the thesis we present Model Evolution with Linear Integer Arithmetic (MELIA), a calculus combining function-free first-order logic with linear integer arithmetic (LIA). MELIA is based on ME and supports similar inference rules and redundancy criteria. We prove the correctness of the calculus, and show how to obtain complete proof procedures and decision procedures for some interesting classes of MELIA's logic. Finally, we explain in detail how MELIA can be implemented efficiently based on the techniques employed in SMT solvers and Darwin.

This work extends recent research in the development of a number of direct search methods in nonlinear integer programming. The various algorithms use an extension of the well-known FORTRAN MINOS code of Murtagh and Saunders as a starting point. MINOS is capable of solving quite large problems in which the objective function is nonlinear and the constraints linear. The original MINOS code has been extended in various ways by Murtagh, Saunders and co-workers since the original 1978 landmark paper. Extensions have dealt with methods to handle both nonlinear constraints, most notably MINOS/AUGMENTED and integer requirements on a subset of the variables(MINTO). The starting point for the present thesis is the MINTO code of Murtagh. MINTO is a direct descendant of MINOS in that it extends the capabilities to general nonlinear constraints and integer restrictions. The overriding goal for the work described in this thesis is to obtain a good integer-feasible or near-integer-feasible solution to the general NLIP problem while trying to avoid or at least minimize the use of the ubiquitous branch-and-bound techniques. In general, we assume a small number of nonlinearities and a small number of integer variables.Some initial ideas motivating the present work are summarised in an invited paper presented by Murtagh at the 1989 CTAC (Computational Techniques and Applications) conference in Brisbane, Australia. The approach discussed there was to start a direct search procedure at the solution of the continuous relaxation of a nonlinear mixed-integer problem by first removing integer variables from the simplex basis, then adjusting integer-infeasible superbasic variables, and finally checking for local optimality by trial unit steps in the integers. This may be followed by a reoptimization with the latest point as the starting point, but integer variables held fixed. We describe ideas for the further development of Murtagh’s direct search method. Both the old and new approaches aim to attain an integer-feasible solution from an initially relaxed (continuous) solution. Techniques such as branch-and-bound or Scarf’s neighbourhood search [84] may then be used to obtain a locally optimal solution. The present range of direct search methods differs significantly to that described by Murtagh, both in heuristics used and major and minor steps of the procedures. Chapter 5 summarizes Murtagh’s original approach while Chapter 6 describes the new methods in detail.Afeature of the new approach is that some degree of user-interaction (MINTO/INTERACTIVE) has been provided, so that a skilled user can "drive" the solution towards optimality if this is desired. Alternatively the code can still be run in "automatic" mode, where one of five available direct search methods may be specified in the customary SPECS file. A selection of nonlinear integer programming problems taken from the literature has been solved and the results are presented here in the latter chapters. Further, anewcommunications network topology and allocation model devised by Berry and Sugden has been successfully solved by the direct search methods presented herein. The results are discussed in Chapter 14, where the approach is compared with the branch-and-bound heuristic.

Thesis (M.S.)--University of Missouri--Rolla, 2007. / Vita. The entire thesis text is included in file. Title from title screen of thesis/dissertation PDF file (viewed December 7, 2007) Includes bibliographical references (p. 28).

In this thesis we consider four topics all related to using problem reformulations in order to solve integer programs, i.e. optimization problems in which the decision variables must be integer. We first consider the polyhedral approach. We start by addressing the question of lifting valid inequalities, i.e. finding a valid inequality for a set Y from the knowledge of a valid inequality for a lower-dimensional restriction X of Y. We simplify and clarify the presentation of the procedure. This allows us to derive conditions under which the computation of the lifting is tractable. The second topic is the study of valid inequalities for the single node flow set. The single node flow set is the problem obtained by considering one node of a fixed charge network flow problem. We derive valid inequalities for this set and various generalizations. Our approach is a systematic procedure using only basic tools of integer programming: fixing and complementing variables, mixed-integer rounding and lifting. The method allows us to explain and generate a large range of inequalities describing the convex hull of such sets. The last two topics are based on non-standard approaches for integer programming. We first show how the group relaxation approach can be used to provide reformulations for the integral basis method. This is based on a study of extended formulations for the group problem. We present four extended formulations and show that the projections of three of these formulations provide the convex hull of the original group problem. Initial computational tests of the approach are also reported. Finally we consider a problem that is difficult for the standard branch-and-bound approach even for small instances. A reformulation based on lattice basis reduction is known to be more effective. However the step to compute the reduced basis is O(n^4) and becomes a bottleneck for small to medium instances. By using the structure of the problem, we show that we can decompose the problem and obtain the basis by taking the kronecker product of two smaller bases easier to compute. Furthermore, if the two small bases are reduced, the kronecker product is also reduced up to a reordering of the vectors. Computational results show the gain from such an approach.