Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming is a useful tool for modeling and optimizing real world problems. Unfortunately, the time required to solve integer programs is exponential, so real world problems often cannot be solved. The knapsack problem is a form of integer programming that has only one constraint and can be used to strengthen cutting planes for general integer programs. These facts make finding new classes of facet-defining inequalities for the knapsack problem an extremely important area of research. This thesis introduces three set inequalities (TSI) and an algorithm for finding them. Theoretical results show that these inequalities will be of dimension at least 2, and can be facet defining for the knapsack problem under certain conditions. Another interesting aspect of these inequalities is that TSIs are some of the first facet-defining inequalities for knapsack problems that are not based on covers. Furthermore, the algorithm can be extended to generate multiple inequalities by implementing an enumerative branching tree. A small computational study is provided to demonstrate the effectiveness of three set inequalities. The study compares running times of solving integer programs with and without three set inequalities, and is inconclusive.

No description available.

No description available.

Solving real world problems with mixed integer programming (MIP) involves efforts in modeling and efficient algorithms. To solve a minimization MIP problem, a lower bound is needed in a branch-and-bound algorithm to evaluate the quality of a feasible solution and to improve the efficiency of the algorithm. This thesis develops a new MIP model and studies algorithms for obtaining lower bounds for MIP. The first part of the thesis is dedicated to a new production planning model with pricing decisions. To increase profit, a company can use pricing to influence its demand to increase revenue, decrease cost, or both. We present a model that uses pricing discounts to increase production and delivery flexibility, which helps to decrease costs. Although the revenue can be hurt by introducing pricing discounts, the total profit can be increased by properly choosing the discounts and production and delivery decisions. We further explore the idea with variations of the model and present the advantages of using flexibility to increase profit. The second part of the thesis focuses on solving integer programming(IP) problems by improving lower bounds. Specifically, we consider obtaining lower bounds for the multi- dimensional knapsack problem (MKP). Because MKP lacks special structures, it allows us to consider general methods for obtaining lower bounds for IP, which includes various relaxation algorithms. A problem relaxation is achieved by either enlarging the feasible region, or decreasing the value of the objective function on the feasible region. In addition, dual algorithms can also be used to obtain lower bounds, which work directly on solving the dual problems. We first present some characteristics of the value function of MKP and extend some properties from the knapsack problem to MKP. The properties of MKP allow some large scale problems to be reduced to smaller ones. In addition, the quality of corner relaxation bounds of MKP is considered. We explore conditions under which the corner relaxation is tight for MKP, such that relaxing some of the constraints does not affect the quality of the lower bounds. To evaluate the overall tightness of the corner relaxation, we also show the worst-case gap of the corner relaxation for MKP. To identify parameters that contribute the most to the hardness of MKP and further evaluate the quality of lower bounds obtained from various algorithms, we analyze the characteristics that impact the hardness of MKP with a series of computational tests and establish a testbed of instances for computational experiments in the thesis. Next, we examine the lower bounds obtained from various relaxation algorithms com- putationally. We study methods of choosing constraints for relaxations that produce high- quality lower bounds. We use information obtained from linear relaxations to choose con- straints to relax. However, for many hard instances, choosing the right constraints can be challenging, due to the inaccuracy of the LP information. We thus develop a dual heuristic algorithm that explores various constraints to be used in relaxations in the Branch-and- Bound algorithm. The algorithm uses lower bounds obtained from surrogate relaxations to improve the LP bounds, where the relaxed constraints may vary for different nodes. We also examine adaptively controlling the parameters of the algorithm to improve the performance. Finally, the thesis presents two problem-specific algorithms to obtain lower bounds for MKP: A subadditive lifting method is developed to construct subadditive dual solutions, which always provide valid lower bounds. In addition, since MKP can be reformulated as a shortest path problem, we present a shortest path algorithm that uses estimated distances by solving relaxations problems. The recursive structure of the graph is used to accelerate the algorithm. Computational results of the shortest path algorithm are given on the testbed instances.

Single-row mixed-integer programming (MIP) problems have been studied thoroughly under many different perspectives over the years. While not many practical applications can be modeled as a single-row MIP, their importance lies in the fact that they are simple, natural and very useful relaxations of generic MIPs. This thesis will focus on such MIPs and present theoretical and computational advances in their study. Chapter 1 presents an introduction to single-row MIPs, a historical overview of results and a motivation of why we will be studying them. It will also contain a brief review of the topics studied in this thesis as well as our contribution to them. In Chapter 2, we introduce a generalization of a very important structured single-row MIP: Gomory's master cyclic group polyhedron (MCGP). We will show a structural result for the generalization, characterizing all facet-defining inequalities for it. This structural result allows us to develop relationships with MCGP, extend it to the mixed-integer case and show how it can be used to generate new valid inequalities for MIPs. Chapter 3 presents research on an algorithmic view on how to maximally lift continuous and integer variables. Connections to tilting and fractional programming will also be presented. Even though lifting is not particular to single-row MIPs, we envision that the general use of the techniques presented should be on easily solvable MIP relaxations such as single-row MIPs. In fact, Chapter 4 uses the lifting algorithm presented. Chapter 4 presents an extension to the work of Goycoolea (2006) which attempts to evaluate the effectiveness of Mixed Integer Rounding (MIR) and Gomory mixed-integer (GMI) inequalities. By extending his work, natural benchmarks arise, against which any class of cuts derived from single-row MIPs can be compared. Finally, Chapter 5 is dedicated to dealing with an important computational problem when developing any computer code for solving MIPs, namely the problem of numerical accuracy. This problem arises due to the intrinsic arithmetic errors in computer floating-point arithmetic. We propose a simple approach to deal with this issue in the context of generating MIR/GMI inequalities.

Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd Easton / Integer programs (IPs) are mathematical models that can provide an optimal solution to a variety of different problems. They have the ability to maximize profitability and decrease wasteful spending, but IPs are NP-complete resulting in many IPs that cannot be solved in reasonable periods of time. Cutting planes or valid inequalities have been used to decrease the time required to solve IPs. These valid inequalities are commonly created using a procedure called lifting. Lifting is a technique that strengthens existing valid inequalities without cutting off feasible solutions. Lifting inequalities can result in facet defining inequalities, the theoretically strongest valid inequalities. Because of these properties, lifting procedures are used in software to reduce the time required to solve an IP. This thesis introduces a new algorithm for synchronized simultaneous approximate lifting for multiple knapsack problems. Synchronized Simultaneous Approximate Lifting (SSAL) requires O(|E1|SLP_|E1|+|E2|,m + |E1|2) effort, where |E1| and |E2| are the sizes of sets used in the algorithm and SLP is the time to solve a linear program. It approximately uplifts two sets simultaneously to creates multiple inequalities of a particular form. These new valid inequalities generated by SSAL can be facet defining. A small computational study shows that SSAL is quick to execute, requiring fractions of a second. Additionally, applying SSAL inequalities to large knapsack problem enabled commercial software to solve faster and also eliminate off the initial linear relaxation point.

We propose a generic algorithm based on branch-and-bound to generate all efficient solutions of multiobjective combinatorial optimization (MOCO) problems. We present an algorithm specific to multiobjective 0-1 Knapsack Problem based on the generic algorithm. We test the performance of our algorithm on randomly generated sample problems against IBM ILOG CPLEX and we obtain better performance using a problem specific algorithm. We develop a heuristic algorithm by incorporating memory limitations at the expense of solution quality to overcome memory issues of the exact algorithm.

We propose a resource allocation model for the management of the fund for the screening and treatment of women infected by Chlamydia trachomatis and Neisseria gonorrhoeae. The goal is to maximize the number of infected women cured of Chlamydia trachomatis and Neisseria gonorrhoeae infections. The population going for screening is divided into groups by ages and races. The group number is dynamic. Dierent groups have dierent infection rates. There are four possible test assays and four possible treatments. We employed a two-phase algorithm to solve the problem. The first phase is small so an exhaustive method is applied, while the second phase is transformed to a knapsack problem and a dynamic programming method is applied.

Nowadays all existing public key cryptosystems are classified into three categories relied on different mathematical foundations. The first one is based on the difficulty of factoring the product of two big prime numbers. The representatives are the RSA and the Rabin cryptosystems. The second one such as the ElGamal cryptosystem is based on the discrete logarithm problem. The last one is based on the NP-completeness of the knapsack problem. The first two categories survived crypto attacks, whereas the last one was broken and there has been no attempt to use such a cryptosystem. In order to save the last category, Kiriyama proposed a new public key cryptosystem based on the non-linear knapsack problem, which is an NP-complete problem. Due to the non-linear property of the non-linear knapsack problem, this system resists all known attacks to the linear knapsack problem. Based on his work, we extend our research in several ways. Firstly, we propose an encrypted secret sharing scheme. We improve the security of shares by our method over other existing secret sharing schemes. Simply speaking, in our scheme, it would be hard for outsiders to recover a secret even if somehow they could collect all shares, because each share is already encrypted when it is generated. Moreover, our scheme is efficient. Then we propose a multiple identities authentication scheme, developed on the basis of the non-linear knapsack scheme. It verifies the ownership of an entity's several identities in only one execution of our scheme. More importantly, it protects the privacy of the entities from outsiders. Furthermore, it can be used in resource-constrained devices due to low computational complexity. We implement the above schemes in the C language under the Linux system. The experimental results show the high efficiency of our schemes, due to low computational complexity of the non-linear knapsack problem, which works as the mathematical foundation of our research.

Thesis (PhD)--University of Stellenbosch, 2007. / Bibliography. Also availabe via the Internet.