Master of Science / Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programming is a field of mathematical optimization that has applications across a wide variety of industries and fields including business, government, health care and military. A commonly studied integer program is the knapsack problem, which has applications including project and portfolio selection, production planning, inventory problems, profit maximization applications and machine scheduling. Integer programs are computationally difficult and currently require exponential effort to solve. Adding cutting planes is a way of reducing the solving time of integer programs. These cutting planes eliminate linear relaxation space. The theoretically strongest cutting planes are facet defining inequalities. This thesis introduces a new class of cutting planes called multiple variable merging cover inequalities (MVMCI). The thesis presents the multiple variable merging cover algorithm (MVMCA), which runs in linear time and produces a valid MVMCI. Under certain conditions, an MVMCI can be shown to be a facet defining inequality. An example demonstrates these advancements and is used to prove that MVMCIs could not be identified by any existing techniques. A small computational study compares the computational impact of including MVMCIs. The study shows that finding an MVMCI is extremely fast, less than .01 seconds. Furthermore, including an MVMCI improved the solution time required by CPLEX, a commercial integer programming solver, by 6.3% on average.

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.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IPs) are a commonly researched class of decision problems. These problems are used in various applications to help companies, governments, or individuals make better decisions by determining optimal resource allocations. While IPs are practical tools, they require an exponential amount of effort to solve, unless P = NP. This fact has led to much research focused on reducing the time required to solve IPs. Cutting planes are a commonly used tool for reducing IP solving time. Lifting, a process of changing the coefficients in an inequality, is often employed to strengthen cutting planes. When lifting, the goal is often to create a facet defining inequality, which is theoretically the strongest cutting plane. This thesis introduces two new lifting procedures for the Node Packing problem. The Node Packing problem seeks to select the maximum number of nodes in a graph such that no two nodes are adjacent. The first lifting method, the Simultaneous Lifting Expansion, takes two inequalities and combines them to make a stronger cut. It works for any two general classes of inequalities, as long as the requisite graph structures are met. The second method, the Cliques On Odd-holes Lifting (COOL) procedure, lifts from an odd-hole inequality to a facet defining inequality. COOL makes use of the Odd Gap Lifting procedure, an efficient method for finding lifting coefficients on odd holes. A computational study shows COOL to be effective in creating cuts in graphs with low edge densities.

Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd Easton / Graph theory is a widely researched topic. A graph contains a set of nodes and a set of edges. The nodes often represent resources such as machines, employees, or plant locations. Each edge represents the relationship between a pair of nodes such as time, distance, or cost. Integer programs are frequently used to solve graphical problems. Unfortunately, IPs are NP-hard unless P = NP, which implies that it requires exponential effort to solve them. Much research has been focused on reducing the amount of time required to solve IPs through the use of valid inequalities or cutting planes. The theoretically strongest cutting planes are facet defining cutting planes. This research focuses on the node packing problem or independent set problem, which is a combinatorial optimization problem. The node packing problem involves coloring the maximum number of nodes such that no two nodes are adjacent. Node packings have been applied to airline traffic and radio frequencies. This thesis introduces a new class of graphical structures called suns. Suns produce previously undiscovered valid inequalities for the node packing polyhedron. Conditions are provided for when these valid inequalities are proven to be facet defining. Sun valid inequalities have the potential to more quickly solve node packing problems and could even be extended to general integer programs through conflict graphs.

Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd W. Easton / Integer programming is an important discipline in operation research that positively impacts society. Unfortunately, no algorithm currently exists to solve IP's in polynomial time. Researchers are constantly developing new techniques, such as cutting planes, to help solve IPs faster. For example, DeLissa discovered the existence of equality cuts limited to zero and one coefficients for the multiple knapsack equality problem (MKEP). An equality cut is an improper cut because every feasible point satisfies the equality. However, such a cut always reduces the dimension of the linear relaxation space by at least one. This thesis introduces lifted equality cuts, which can have coefficients greater than or equal to two. Two main theorems provide the conditions for the existence of lifted equalities. These theorems provide the foundation for The Algorithm of Lifted Equality Cuts (ALEC), which finds lifted equality cuts in quadratic time. The computational study verifies the benefit of lifted equality cuts in random MKEP instances. ALEC generated millions of lifted equality cuts and reduced the solution time by an average of 15%. To the best of the author's knowledge, ALEC is the first algorithm that has found over 30.7 million cuts on a single problem, while reducing the solving time by 18%.

No description available.

Master of Science / Department of Industrial & Manufacturing Systems Engineering / Todd W. Easton / Integer programs (IPs) are mathematical models that can provide an optimal solution to a variety of different problems. They have been used to reduce costs and optimize organizations. Additionally, IPs are NP-complete resulting in many IPs that cannot be solved. Cutting planes or valid inequalities have been used to decrease the time required to solve IPs. Lifting is a technique that strengthens existing valid inequalities. Lifting inequalities can result in facet defining inequalities, which are the theoretically strongest valid inequalities. Because of these properties, lifting procedures are used in software to reduce the time required to solve an IP. The thesis introduces a new algorithm for exact synchronized simultaneous uplifting over an arbitrary initial inequality for knapsack problems. Synchronized Simultaneous Lifting (SSL) is a pseudopolynomial time algorithm requiring O(nb+n[superscript]3) effort to solve. It exactly uplifts two sets simultaneously into an initial arbitrary valid inequality and creates multiple inequalities of a particular form. This previously undiscovered class of inequalities generated by SSL can be facet defining. A small computational study shows that SSL is quick to execute, requiring on average less than a quarter of a second. Additionally, applying SSL inequalities to a knapsack problem enabled commercial software to solve problems that it could not solve without them.

Master of Science / Department of Industrial and Manufacturing Systems Engineering / Todd Easton / Integer Programming is used to solve numerous optimization problems. This class of mathematical models aims to maximize or minimize a cost function restricted to some constraints and the solution must be integer. One class of widely studied Integer Program (IP) is the Multiple Knapsack Problem (MKP). Unfortunately, both IPs and MKPs are NP-hard, potentially requiring an exponential time to solve these problems. Utilization of cutting planes is one common method to improve the solution time of IPs. A cutting plane is a valid inequality that cuts off a portion of the linear relaxation space. This thesis presents a new class of cutting planes referred to as merged knapsack cover inequalities (MKCI). These valid inequalities combine information from a cover inequality with a knapsack constraint to generate stronger inequalities. Merged knapsack cover inequalities are generated by the Merging Knapsack Cover Algorithm (MKCA), which runs in linear time. These inequalities may be improved by the Exact Improvement Through Dynamic Programming Algorithm (EITDPA) in order to make them stronger inequalities. Theoretical results have demonstrated that this new class of cutting planes may cut off some space of the linear relaxation region. A computational study was performed to determine whether implementation of merged knapsack cover inequalities is computationally effective. Results demonstrated that MKCIs decrease solution time an average of 8% and decrease the number of ticks in CPLEX, a commercial IP solver, approximately 4% when implemented in appropriate instances.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / O problema de coloraÃÃo de vÃrtices à considerado um dos modelos mais estudados em teoria dos grafos pela sua relevÃncia em campos prÃticos e teÃricos. Do ponto de vista teÃrico, o problema de coloraÃÃo à NP - DifÃcil. AlÃm disto, foi classificado entre os problemas mais difÃceis de NP, no sentido de que achar uma aproximaÃÃo para o nÃmero cromÃtico tambÃm à NP - DifÃcil. A importÃncia do problema de coloraÃÃo tem incentivado a investigar mÃtodos para encontrar limitantes inferiores prÃximos do nÃmero cromÃtico. Historicamente, os primeiros limitantes inferiores utilizados para resolvÃ-lo lidavam com cliques maximais. Mais recentemente, popularizou-se a utilizaÃÃo de relaxaÃÃes lineares de formulaÃÃes de programaÃÃo inteira. Uma formulaÃÃo que mostrou bons limitantes inferiores foi a formulaÃÃo por conjuntos independentes, cujo valor de relaxaÃÃo equivale ao nÃmero cromÃtico fracionÃrio. No presente trabalho, fazemos uma comparaÃÃo entre as formulaÃÃes de programaÃÃo inteira conhecidas para indicar a escolha pela formulaÃÃo dos representantes. Revisamos a formulaÃÃo para remover simetrias existentes e apresentamos um estudo parcial do politopo associado ao fecho convexo de suas soluÃÃes inteiras. Discutimos como à possÃvel utilizar a formulaÃÃo dos representantes para gerar limites inferiores para o nÃmero cromÃtico fracionÃrio. Realizamos a implementaÃÃo de um mÃtodo de planos de corte para aproximar o nÃmero cromÃtico fracionÃrio e mostramos que podemos gerar limitantes inferiores que normalmente nÃo diferem em mais de uma unidade. / The vertex coloring problem is one of the most studied problems in graph theory for its relevance in practical and theoretical fields. From a theoretical point of view, it is a NP-Hard problem. Moreover, it is classified among the most difficult problems of NP- Hard in the sense that finding an approximation to the chromatic number is also NP-Hard. The importance of the coloring problem motivates searching for methods to find lower bounds close to the chromatic number. Historically, the first lower bounds used were obtained from the size of maximal cliques. More recently, relaxed integer programming formulations gained more attention. A formulation which found good lower bounds was the coloring problem through stable sets whose relaxed lower bound equals the fractional chromatic number. In this work, we make a comparison between the known integer programming formulations to motivate our choice for the Representatives formulation. We revise this formulation to remove symmetry and present a partial study of the polytope associated with the convex hull of its integer solutions. We discuss how to se the Representatives formulation to get lower bounds for the fractional chromatic number and we show how to get such lower bounds that differ at most by one unit to its exact value.