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.

This thesis concerns the application of mixed-integer programming techniques to solve special classes of network flow problems and stochastic integer programs. We draw tools from complexity and polyhedral theory to analyze these problems and propose improved solution methods. In the first part, we consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are required to take values above a prespecified minimum threshold whenever they are not zero. These problems find applications in management and supply chain models where orders in small quantities are undesirable. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We also consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems. In the second part, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of optimizing a linear function on the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem and finds applications in stochastic integer programming. We observe that the complexity of the problem depends on how P and X are specified. For instance, P can be explicitly given by its linear description, or implicitly by an oracle. Similarly, X can be explicitly given as a list of vectors, or implicitly as a face of P. While removing vertices turns to be hard in general, it is tractable for tractable 0-1 polytopes, and compact extended formulations can be obtained. Some extensions to integral polytopes are also presented. The third part is devoted to the integer L-shaped method for two-stage stochastic integer programs. A widely used model assumes that decisions are made in a two-step fashion, where first-stage decisions are followed by second-stage recourse actions after the uncertain parameters are observed, and we seek to minimize the expected overall cost. In the case of finitely many possible outcomes or scenarios, the integer L-shaped method proposes a decomposition scheme akin to Benders' decomposition for linear problems, but where a series of mixed-integer subproblems have to be solved at each iteration. To improve the performance of the method, we devise a simple modification that alternates between linear and mixed-integer subproblems, yielding significant time savings in instances from the literature. We also present a general framework to generate optimality cuts via a cut-generating problem. Using an extended formulation of the forbidden-vertices problem, we recast our cut-generating problem as a linear problem and embed it within the integer L-shaped method. Our numerical experiments suggest that this approach can prove beneficial when the first-stage set is relatively complicated.

The purpose of this dissertation is to synthesize a methodology to prescribe a strategic design of a surveillance system to provide the required level of surveillance for ports and waterways. The method of approach to this problem is to formulate a linear integer programming model to prescribe a strategic surveillance system design (SSD) for ports or waterways, to devise branch-and-price decomposition (B

When integer programming (IP) models are used in operational situations there is a need to consider the tradeoff between the conflicting goals of solution quality and solution time, since for many problems solving realistic-size instances to a tight tolerance is still beyond the capability of state-of-the-art solvers. However, by appropriately defining small instances, good primal solutions frequently can be found quickly. We explore this approach in this thesis by studying the design of algorithms that produce solutions to an integer program by solving restrictions of the problem via integer programming technology. We refer to this type of algorithm as IP-based search and present algorithms for network design problems of both real-world and academic interest. Along with algorithms that exploit the structure of the problem studied we also present a general integer programming algorithm that uses column generation to choose the restrictions to solve.

Branch-price-and-cut algorithms are among the most successful exact optimization approaches for solving many routing and scheduling problems. This is due, in part, to the availability of extremely efficient and effective dynamic programming algorithms for solving the pricing problem, and the availability of efficient and effective branching schemes and cutting planes that drive integrality. In terms of branch-price-and-cut, two obstacles we face today are (1) being able to solve harder and larger pricing problems, and (2) solving mixed-integer column generation formulations that suffer from relatively weak LP bounds compared to the more traditional 0-1 set partitioning type. As part of the work presented in this thesis, we encounter column generation formulations motivated by real life problems that require overcoming both types of challenges. The first part of this thesis is dedicated to solving the resource constrained shortest path problem (RCSPP) arising in column generation pricing problems for formulations involving extremely large networks and a huge number of local resource constraints. We present a relaxation-based dynamic programming algorithm that alternates between a forward and a backward search. Each search employs bounds derived in the previous search to prune the search, and between consecutive searches, the relaxation is tightened over a set of critical resources and arcs. The second part of this thesis focuses in the fixed charge shortest path problem (FCSPP) in which the amount of resource consumed is itself a continuous bounded variable. By exploiting the structure of optimal solutions to FCSPP, we design and implement a solution approach that relies on solving multiple RCSPPs, and therefore can again make use of extremely efficient and effective dynamic programming algorithms. In the third and final part of this thesis, we present a branch-price-and-cut algorithm for the inventory routing problem (IRP). We extend a class of cuts known for the vehicle routing problem, and develop a new class of cuts specifically for IRP to tighten the formulation. Both the branching schemes and cuts preserve the structure of the pricing problem making them efficiently implementable within a branch-price-and-cut algorithm.

In 2003, Gomory and Johnson gave two different three-slope T-space facet constructions, both of which shared a slope with the corresponding Gomory mixed-integer cut. We give a new three-slope facet which is independent of the GMIC and also give a four-slope T-space facet construction, which to our knowledge, is the first four-slope construction. We describe an enumerative framework for the discovery of T-space facets. Using an algorithm by Harvey for computing integer hulls in the plane, we give a heuristic for quickly computing lattice-free triangles. Given two rows of the tableau, we derive how to exactly calculate lattice-free triangles and quadrilaterals in the plane which can be used to derive facet-defining inequalities of the integer hull. We then present computational results using these derivations where non-basic integer variables are strengthened using Balas-Jeroslow lifting.

In this dissertation we examine several discrete optimization problems through the perspectives of modeling, complexity and algorithms. We first provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables in terms of cut coefficients and volume cutoff. Under a specific probabilistic model of the problem parameters, we show that for the above measure, the probability that a split cut is better than a type 1 triangle cut is higher than the probability that a type 1 triangle cut is better than a split cut. The analysis also suggests some guidelines on when type 1 triangle cuts are likely to be more effective than split cuts and vice versa. We next study a minimum concave cost network flow problem over a grid network. We give a polytime algorithm to solve this problem when the number of echelons is fixed. We show that the problem is NP-hard when the number of echelons is an input parameter. We also extend our result to grid networks with backward and upward arcs. Our result unifies the complexity results for several models in production planning and green recycling including the lot-sizing model, and gives the first polytime algorithm for some problems whose complexities were not known before. Finally, we examine how much complexity randomness will bring to a simple combinatorial optimization problem. We study a problem called the sell or hold problem (SHP). SHP is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. Although the deterministic version of SHP is trivial to solve, we show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SHP is polynomially solvable when the number of scenarios in the second stage is constant. A max{1/2,k/n}-approximation algorithm is presented for the scenario-based SHP.

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.

Draw management is a critical part of the successful recovery of mineral reserves by cave mining. This thesis presents a draw control model that indirectly increases resource value by controlling production based on geotechnical constraints. The mixed integer linear programming (MILP) model is formulated as a goal programming model that includes seven general constraint types. These constraints model the mining system and drive the operation towards the dual strategic targets of total monthly production tonnage and cave shape. This approach increases value by ensuring that reserves are not lost due to poor draw practice. The model also allows any number of processing plants to feed from multiple sources (caves, stockpiles, and dumps). The ability to blend material allows the model to be included in strategic level studies that target corporate objectives while emphasising production control within each cave. There are three main production control constraints in the MILP. The first of these, the draw maturity rules, is designed to balance drawpoint production with cave propagation rates. The maturity rules are modelled using disjunctive constraints. The constraint regulates production based on drawpoint depletion. Drawpoint production increases from 100 mm/d to 404 mm/d once the drawpoint reaches 6.5% depletion. Draw can continue at this maximum rate until drawpoint ramp-down begins as 93.5% depletion. The maximum draw rate decreases to 100 mm/d at drawpoint closure in the three maturity rule systems included in the thesis. The maturity rule constraints combine with the minimum draw rate constraint to limit production based on the difference between the actual and ideal drawpoint depletion. Drawpoints which lag behind their ideal depletion are restricted by the maturity rules while those that exceeded the ideal depletion were forced to mine at their minimum rate to ensure that cave porosity was maintained. The third production control constraint, relative draw rate (RDR), prohibits isolated draw by ensuring that extraction is uniform across the cave. It does this by controlling the relative draw difference between adjacent drawpoints. It is apparent in this thesis that production from a drawpoint can have an indirect effect on remote drawpoints because the relative draw rate constraints pass from one neighbour to the next within the cave. Tightening the RDR constraint increases production variation during cave ramp-up. This variation occurs because the maturity rules dictate that new drawpoints must produce at a lower draw rate than mature drawpoints. As a result, newly opened drawpoints limit production from the mature drawpoints within their region of the cave (not just their immediate neighbours). The MILP is also used to quantify production changes caused by varying geotechnical constraints, limiting haulage capacity, and reversing mining direction. It has been shown that tightening the RDR constraint decreases total cave production. The ramp-up duration also increased by eighteen months compared to the control RDR scenario. Tighter relative draw also made it difficult to maintain cave shape during ramp-up. However, once ramp-up was complete, the tighter control produced a better depletion surface. The trial with limited haulage capacity identified bottlenecks in the materials handling system. The main bottlenecks occur in the production drives with the greatest tonnage associated with their drawpoints. There also appears to be an average haulage capacity threshold for the extraction drives of 2000 tonnes per drawpoint. Only one drive with a capacity below this threshold achieves its target production in each period. Reversing the cave advance to initiate in the South-East shows the greatest potential for achieving total production and cave shape targets. The greater number of drawpoints available early in the schedule provides more production capacity. This ability to distribute production over a greater number of drawpoints reduces the total production lag during ramp-up. In addition to its role in feasibility studies, the MILP is well suited for use as a production guidance tool. It has been shown in three case studies that the model can be used to evaluate production performance and to establish long term production targets. The first of the studies shows the analysis of historical production data by comparison to the MILP optimised schedule. The second shows that the model produces an optimised production plan irrespective of the current cave state. The final case study emulates the draw control cycle used by the Premier Diamond Mine. The series of optimised production schedules mirror that of the life-of-mine schedule generated at the start of the iterative process. The results illustrate how the MILP can be used by a draw control engineer to analyse production data and to develop long term production targets both before and after a cave is brought into full production.

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.