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.

Thesis (Ph. D.)--University of Washington, 2001. / Vita. Includes bibliographical references (p. 104-113).

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

Not available / text

published_or_final_version / Electrical and Electronic Engineering / Master / Master of Philosophy

No description available.

As technology becomes ever more pervasive, the challenges of home automation are increasingly apparent. Seamless home control, home monitoring and home programming by the end user have yet to enter the mainstream. This could be attributed to the challenge of developing a fully autonomous and extensible home system that can support devices and technologies of differing protocols and functionalities. In order to offer programming facilities to the user, the underlying rule system must be fully independent, allowing support for current and future devices. Additional challenges arise from the need to detect and handle conflicts that may arise among user rules and yield undesirable results. Non-technical individuals typically struggle when faced with a programming task. It is therefore vital to encourage and ease the process of programming the home. This thesis presents Homer, a home system that has been developed to support three key features of a home system: control, monitoring and programming. Homer supports any third-party hardware or software service that can expose its functionality through Java and conform to the Homer interface. Stand-alone end user interfaces can be written by developers to offer any of Homer's functionality. Where policies (i.e. rules) for the home are concerned, Homer offers a fully independent policy system. The thesis presents a custom policy language, Homeric, that has been designed specifically for writing home rules. The Homer policy system detects overlaps and conflicts among rules using constraint satisfaction and the effect on environment variables. The thesis also introduces the notion of perspectives to ease user interactivity. These have been integrated into Homer to accommodate the range of ways in which a user may think about different aspects and features of their home. These perspectives include location, device type, time and people-oriented points of view. Design guidelines are also discussed to aid end user programming of the home. The work presented in this thesis demonstrates a system that supports control, monitoring and programming of the home. Developers can quickly and easily add functionality to the home through components. Conflicts can be detected amongst rules within the home. Finally, design guidelines and a prototype interface have been developed to allow both technically minded and non-technical people to program their home.

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.

No description available.