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 Ph.D. dissertation research, we lay the mathematical foundations of various fundamental concepts in convex mixed-integer programs (MIPs), that is, optimization problems where all the decision variables belong to a given convex set and, in addition, a subset of them are required to be integer. In particular, we study properties of their feasible region and properties of cutting planes. The main contribution of this work is the extension of several fundamental results from the theory of linear MIPs to the case of convex MIPs. In the first part, we study properties of general closed convex sets that determine the closedness and polyhedrality of their integer hulls. We first present necessary and sufficient conditions for the integer hull of a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the integer hulls of general convex sets to be polyhedra. This result generalizes the well-known result due to Meyer in the case of linear MIPs. Under a simple technical assumption, we show that these sufficient conditions are also necessary for the integer hull of general convex sets to be polyhedra. In the second part, we apply the previous results to mixed-integer second order conic programs (MISOCPs), a special case of nonlinear convex MIPs. We show that there exists a polynomial time algorithm to check the closedness of the mixed integer hulls of simple MISOCPs. Moreover, in the special case of pure integer problems, we present sufficient conditions for verifying the closedness of the integer hull of intersection of simple MISOCPs that can also be checked in polynomial time. In the third part, we present an extension of the duality theory for linear MIPs to the case of conic MIPs. In particular, we construct a subadditive dual to conic MIPs. Under a simple condition on the primal problem, we are able to prove strong duality. In the fourth part, we study properties of maximal S-free convex sets, where S is a subset of integers contained in an arbitrary convex set. An S-free convex set is a convex set not containing any points of S in its interior. In this part, we show that maximal S-free convex sets are polyhedra and discuss some properties of these sets. In the fifth part, we study some generalizations of the split closure in the case of linear MIPs. Split cuts form a well-known class of valid inequalities for linear MIPs. Cook et al. (1990) showed that the split closure of a rational polyhedron - that is, the set of points in the polyhedron satisfying all split cuts - is again a polyhedron. In this thesis, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We also show how this result can be used to prove that some generalizations of split cuts, namely cross cuts, also yield closures that are rational polyhedra.

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.

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.

<p> A solution to an industrial problem of designing a hydrostatic drive system for logging vehicles is presented. A computer program using Land and Doig's method of Branch and Bound Mixed Integer Programming is used to obtain an optimal solution to the problem. A comprehensive users guide to allow the use of the program by unsophisticated users is provided. </p> <p> An attempted alternate method of solution using the Gomory method of Integer Programming is presented and reasons for its failure discussed. </p> / Thesis / Master of Engineering (MEngr)

With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows probabilistic data parameters in mixed integer programming, a well-known tool for optimization modeling with deterministic input data. However, akin to the mixed integer programs, these stochastic models are theoretically intractable and computationally challenging to solve because of the presence of integer variables. This dissertation focuses on theory, algorithms and applications of two-stage stochastic mixed integer (non)linear programs and it has three-pronged plan. In the first direction, we study two-stage stochastic p-order conic mixed integer programs (TSS-CMIPs) with p-order conic terms in the second-stage objectives. We develop so called scenario-based (non)linear cuts which are added to the deterministic equivalent of TSS-CMIPs (a large-scale deterministic conic mixed integer program). We provide conditions under which these cuts are sufficient to relax the integrality restrictions on the second-stage integer variables without impacting the integrality of the optimal solution of the TSS-CMIP. We also introduce a multi-module capacitated stochastic facility location problem and TSS-CMIPs with structured CMIPs in the second stage to demonstrate the significance of the foregoing results for solving these problems. In the second direction, we propose risk-neutral and risk-averse two-stage stochastic mixed integer linear programs for load shed recovery with uncertain renewable generation and demand. The models are implemented using a scenario-based approach where the objective is to maximize load shed recovery in the bulk transmission network by switching transmission lines and performing other corrective actions (e.g. generator re-dispatch) after the topology is modified. Experiments highlight how the proposed approach can serve as an offline contingency analysis tool, and how this method aids self-healing by recovering more load shedding. In the third direction, we develop a dual decomposition approach for solving two-stage stochastic quadratically constrained quadratic mixed integer programs. We also create a new module for an open-source package DSP (Decomposition for Structured Programming) to solve this problem. We evaluate the effectiveness of this module and our approach by solving a stochastic quadratic facility location problem. / Doctor of Philosophy / With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows two-stages of decision making where the first-stage strategic decisions (such as deciding the locations of facilities or topology of a power transmission network) are taken before the realization of uncertainty, and the second-stage operational decisions (such as transportation decisions between customers and facilities or power flow in the transmission network) are taken in response to the first-stage decision and a realization of the uncertain (demand) data. This modeling tool is gaining wide acceptance because of its applications in healthcare, power systems, wildfire planning, logistics, and chemical industries, among others. Though intriguing, two-stage stochastic programs are computationally challenging. Therefore, it is crucial to develop theoretical results and computationally efficient algorithms, so that these models for real-world applied problems can be solved in a realistic time frame. In this dissertation, we consider two-stage stochastic mixed integer (non)linear programs, provide theoretical and algorithmic results for them, and introduce their applications in logistics and power systems. First, we consider a two-stage stochastic mixed integer program with p-order conic terms in the objective that has applications in facility location problem, power system, portfolio optimization, and many more. We provide a so-called second-stage convexification technique which greatly reduces the computational time to solve a facility location problem, in comparison to solving it directly with a state-of-the-art solver, CPLEX, with its default settings. Second, we introduce risk-averse and risk-neutral two-stage stochastic models to deal with uncertainties in power systems, as well as the risk preference of decision makers. We leverage the inherent flexibility of the bulk transmission network through the systematic switching of transmission lines in/out of service while accounting for uncertainty in generation and demand during an emergency. We provide abundant computational experiments to quantify our proposed models, and justify how the proposed approach can serve as an offline contingency analysis tool. Third, we develop a new solution approach for two-stage stochastic mixed integer programs with quadratic terms in the objective function and constraints and implement it as a new module for an open-source package DSP We perform computational experiments on a stochastic quadratic facility location problem to evaluate the performance of this module.

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.

Call number: LD2668 .T4 1978 L445 / Master of Science

The factors limiting the performance of computer software periodically undergo sudden shifts, resulting from technological progress, and these shifts can have profound implications for the design of high performance codes. At the present time, the speed with which hardware can execute a single stream of instructions has reached a plateau. It is now the number of instruction streams that may be executed concurrently which underpins estimates of compute power, and with this change, a critical limitation on the performance of software has come to be the degree to which it can be parallelised. The research in this thesis is concerned with the means by which codes for linear programming may be adapted to this new hardware. For the most part, it is codes implementing the simplex method which will be discussed, though these have typically lower performance for single solves than those implementing interior point methods. However, the ability of the simplex method to rapidly re-solve a problem makes it at present indispensable as a subroutine for mixed integer programming. The long history of the simplex method as a practical technique, with applications in many industries and government, has led to such codes reaching a great level of sophistication. It would be unexpected in a research project such as this one to match the performance of top commercial codes with many years of development behind them. The simplex codes described in this thesis are, however, able to solve real problems of small to moderate size, rather than being confined to random or otherwise artificially generated instances. The remainder of this thesis is structured as follows. The rest of this chapter gives a brief overview of the essential elements of modern parallel hardware and of the linear programming problem. Both the simplex method and interior point methods are discussed, along with some of the key algorithmic enhancements required for such systems to solve real-world problems. Some background on the parallelisation of both types of code is given. The next chapter describes two standard simplex codes designed to exploit the current generation of hardware. i6 is a parallel standard simplex solver capable of being applied to a range of real problems, and showing exceptional performance for dense, square programs. i8 is also a parallel, standard simplex solver, but now implemented for graphics processing units (GPUs).

This thesis is devoted to investigating some properties of the sequence (Wn) of the denominators. This is a divisibility sequence; that is, Wm | Wn whenever m | n. Our task here is to examine a conjecture on the number of prime terms in (Wn), well known as the Primality conjecture. We will prove that there is a uniform lower bound on n beyond such that all terms Wn have at least two distinct prime factors. In some cases, the bound is as low as n = 2.