Based on the recent successes in stochastic linear programming and mixed integer programming, in this thesis we combine these two important areas of mathematical programming; specifically we study stochastic integer programming. We first study a simple and important stochastic integer programming problem, called stochastic uncapacitated lot-sizing (SLS), which is motivated by production planning under uncertainty. We describe a multi-stage stochastic integer programming formulation of the problem and develop a family of valid inequalities, called the (Q, S) inequalities. We establish facet-defining conditions and show that these inequalities are sufficient to describe the convex hull of integral solutions for two-period instances. A separation heuristic for (Q, S) inequalities is developed and incorporated into a branch-and-cut algorithm. A computational study verifies the usefulness of the inequalities as cuts. Then, motivated by the polyhedral study of (Q, S) inequalities for SLS, we analyze the underlying integer programming scheme for general stochastic integer programming problems. We present a scheme for generating new valid inequalities for mixed integer programs by taking pair-wise combinations of existing valid inequalities. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some special cases, we identify combination sequences that lead to a manageable set of all non-dominated inequalities. For the general scenario tree case, we identify combination sequences that lead to non-dominated inequalities. We also analyze the conditions such that the inequalities generated by our approach are facet-defining and describe the convex hull of integral solutions. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results which show the efficiency of adding the new generated inequalities as cuts.

Classification, the development of rules for the allocation of observations to one or more groups, is a fundamental problem in machine learning and has been applied to many problems in medicine and business. We consider aspects of a classification model developed by Gallagher, Lee, and Patterson that is based on a result by Anderson. The model seeks to maximize the probability of correct G-group classification, subject to limits on misclassification probabilities. The mixed-integer programming formulation of the model is an empirical method for estimating the parameters of an optimal classification rule, which are identified as coefficients of linear functions by Anderson. The model is shown to be a consistent method for estimating the parameters of the optimal solution to the problem of maximizing the probability of correct classification subject to limits on inter-group misclassification probabilities. A polynomial time algorithm is described for two-group instances. The method is NP-complete for a general number of groups, and an approximation is formulated as a mixed-integer program (MIP). The MIP is difficult to solve due to the formulation of constraints wherein certain variables are equal to the maximum of a set of linear functions. These constraints are conducive to an ill-conditioned coefficient matrix. Methods for generating edges of the conflict graph and conflict hypergraphs are discussed. The conflict graph is employed for finding cuts in a branch-and-bound framework. This technique and others lead to improvement in solution time over industry-standard software on instances generated by real-world data. The classification accuracy of the model in relation to standard classification methods on real-world and simulated data is also noted.

The purpose of this study was to develop and test an optimization model that will provide a deployment plan of emission reduction technologies to reduce emissions from non-road equipment. The focus of the study was on the counties of Texas that have nonattainment (NA) and near-nonattainment (NNA) status. The objective of this research was to develop methodologies that will help to deploy emission reduction technologies for non-road equipment of TxDOT to reduce emissions in a cost effective and optimal manner. Three technologies were considered for deployment in this research, (1) hydrogen enrichment (HE), (2) selective catalytic reduction (SCR) and (3) fuel additive (FA). Combinations of technologies were also considered in the study, i.e. HE with FA, and SCR with FA. Two approaches were investigated in this research. The first approach was "Method 1" in which all the technologies, i.e. FA, HE and SCR were deployed in the NA counties at the first stage. In the second stage the same technologies were deployed in the NNA counties with the remaining budget, if any. The second approach was called "Method 2" in which all the technologies, i.e. FA, HE and SCR were deployed in the NA counties along with deploying only FA in the NNA counties at the first stage. Then with the remaining budget, SCR and HE were deployed in the NNA counties in the second stage. In each of these methods, 2 options were considered, i.e. maximizing NOx reduction with and without fuel economy consideration in the objective function. Thus, the four options investigated each having different mixes of emission reduction technologies include Case 1A: Method 1 with fuel economy consideration; Case 1B: Method 1 without fuel economy consideration; Case 2A: Method 2 with fuel economy consideration; and Case 2B: Method 2 without fuel economy consideration and were programmed with Visual C++ and ILOG CPLEX. These four options were tested for budget amounts ranging from $500 to $1,183,000 and the results obtained show that for a given budget one option representing a mix of technologies often performed better than others. This is conceivable because for a given budget the optimization model selects an affordable option considering the cost of technologies involved while at the same time maximum emission reduction, with and without fuel economy consideration, is achieved. Thus the alternative options described in this study will assist the decision makers to decide about the deployment preference of technologies. For a given budget, the decision maker can obtain the results for total NOx reduction, combined diesel economy and total combined benefit using the four models mentioned above. Based on their requirements and priorities, they can select the desired model and subsequently obtain the required deployment plan for deploying the emission reduction technologies in the NA and NNA counties.

Modern system-on-chip consists of an increasing number of highly complex modules. The quality of the interfaces and throughput of communication connections between these components are crucial to the performance of the system, since communication is often the main bottleneck in modern application domains like multimedia. In this thesis, a bus-based communication architecture synthesis approach is proposed. Given the result of hardware/software partitioning and pipelined scheduling, the proposed approach constructs a communication topology which meets the constraints. We begin with the minimum number of AHB and an APB, each time we add an AHB and do some transformation such as merging or setting local buses. Our goal is to find the bus architecture which has minimum area. We use integer programming to construct a bus architecture each time, until the bus architecture with the minimum area are found. By this approach, we can save a lot of time required to design the communication architecture manually.

Thesis (Ph. D.)--University of Washington, 2002. / Vita. Includes bibliographical references (leaves 71-75).

Integer multicommodity network flow (MCNF) models have applications in various areas like logistics, freight transportation, telecommunication and manufacturing. In this thesis we study an extension of the integer MCNF problem (MCNF-FIFO) where commodities are handled (processed) in a first-in-first-out (FIFO) order at each transshipment location and resource capacities are shared across arcs in the network. The objective of the MCNF-FIFO model is to find feasible routes for all commodities from their origins to destinations while minimizing the total transportation and holding cost or the sum of delivery times. We formulate the MCNF-FIFO problem on a time-space network and develop three different integer-programming (IP) formulations for the FIFO constraints, and two IP formulations for the flow conservations requirements. Since these formulations have a very large number of variables and constraints, we develop various algorithmic strategies to obtain good quality solutions quickly. The first strategy is to reduce the problem size by using properties of the optimal solution. We develop novel problem reduction and decomposition techniques that eliminate variables and constraints, and decompose the problem into smaller components. To further reduce the problem size, we classify the FIFO constraints into different categories by utilizing the relationships between different commodities, and provide specialized formulations for each of these categories so as to reduce the number of FIFO constraints significantly. The second strategy is to develop heuristic algorithms that provide near-optimal solutions to the MCNF-FIFO problem. Our first algorithm is an optimization-based heuristic that solves a relaxed MCNF-FIFO model with a limited number of FIFO constraints. Then, it removes the remaining infeasibilities in the solution of the relaxed MCNF-FIFO model using a repair heuristic to obtain a feasible solution. We develop two other heuristic algorithms that are stand-alone construction heuristics that build a feasible solution from scratch. To assess the effectiveness of the modeling and algorithmic enhancements, we implement the methods and apply them to three real life test instances. Our tests show that the problem reduction techniques are very effective in reducing the solution times. Among the heuristic algorithms, the optimization-based heuristic performs the best to find near-optimal solutions quickly. / text

Not available / text

We consider a scheduling problem where each job requires multiple classes of resources, which we refer to as the multiple resource constrained scheduling problem(MRCSP). Potential applications include team scheduling problems that arise in service industries such as consulting and operating room scheduling. We focus on two general cases of the problem. The first case considers uncertainty of processing times, due dates, and resource availabilities consumption, which we denote as the stochastic MRCSP with uncertain parameters (SMRCSP-U). The second case considers uncertainty in the number of jobs to schedule, which arises in consulting and defense contracting when companies bid on future contracts but may or may not win the bid. We call this problem the stochastic MRCSP with job bidding (SMRCSP-JB).We first provide formulations of each problem under the framework of two-stage stochastic programming with recourse. We then develop solution methodologies for both problems. For the SMRCSP-U, we develop an exact solution method based on the L-shaped method for problems with a moderate number of scenarios. Several algorithmic enhancements are added to improve efficiency. Then, we embed the L-shaped method within a sampling-based solution method for problems with a large number of scenarios. We modify a sequential sampling procedure to allowfor approximate solution of integer programs and prove desired properties. The sampling-based method is applicable to two-stage stochastic integer programs with integer first-stage variables. Finally, we compare the solution methodologies on a set of test problems.For SMRCSP-JB, we utilize the disjunctive decomposition (D2 ) algorithm for stochastic integer programs with mixed-binary subproblems. We develop several enhancements to the D2 algorithm. First, we explore the use of a cut generation problem restricted to a subspace of the variables, which yields significant computational savings. Then, we examine generating alternative disjunctive cuts based on the generalized upper bound (GUB) constraints that appear in the second-stage of the SMRCSP-JB. We establish convergence of all D2 variants and present computational results on a set of instances of SMRCSP-JB.

We consider a problem of placing route-based filters in a communication network to limit the number of forged address attacks to a prescribed level. Nodes in the network communicate by exchanging packets along arcs, and the originating node embeds the origin and destination addresses within each packet that it sends. In the absence of a validation mechanism, one node can send packets to another node using a forged origin address to launch an attack against that node. Route-based filters can be established at various nodes on the communication network to protect against these attacks. A route-based filter examines each packet arriving at a node, and determines whether or not the origin address could be legitimate, based on the arc on which the packet arrives, the routing information, and possibly the destination. The problem we consider seeks to find a minimum cardinality subset of nodes to filter so that the prescribed level of security is achieved.The primary contributions of this dissertation are as follows. We formulate and discuss the modeling of this filter placement problem as a mixed-integer program. We then show the sensitivity of the optimal number of deployed filters as the required level of security changes, and demonstrate that current vertex cover-based heuristics are ineffective for problems with relaxed security levels. We identify a set of special network topologies on which the filter placement problem is solvable in polynomial time, focusing our attention on the development of a dynamic programming algorithm for solving this problem on tree networks. These results can then in turn be used to derive valid inequalities for an integer programming model of the filter placement problem. Finally, we present heuristic algorithms based on the insights gained from our overall study for solving the problem, and evaluate their performance against the optimal solution provided by our integer programming model.

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.