Some of the most important and challenging problems in computer science and operations research are stochastic combinatorial optimization (SCO) problems. SCO deals with a class of combinatorial optimization models and algorithms in which some of the data are subject to significant uncertainty and evolve over time, and often discrete decisions need to be made before observing complete future data. Therefore, under such circumstances it becomes necessary to develop models and algorithms in which plans are evaluated against possible future scenarios that represent alternative outcomes of data. Consequently, SCO models are characterized by a large number of scenarios, discrete decision variables and constraints. This dissertation focuses on the development of practical decomposition algorithms for large-scale SCO. Stochastic mixed-integer programming (SMIP), the optimization branch concerned with models containing discrete decision variables and random parameters, provides one way for dealing with such decision-making problems under uncertainty. This dissertation studies decomposition algorithms, models and applications for large-scale two-stage SMIP. The theoretical underpinnings of the method are derived from the disjunctive decomposition (D 2) method. We study this class of methods through applications, computations and extensions. With regard to applications, we first present a stochastic server location problem (SSLP) which arises in a variety of applications. These models give rise to SMIP problems in which all integer variables are binary. We study the performance of the D2 method with these problems. In order to carry out a more comprehensive study of SSLP problems, we also present certain other valid inequalities for SMIP problems. Following our study with SSLP, we also discuss the implementation of the D2 method, and also study its performance on problems in which the second-stage is mixed-integer (binary). The models for which we carry out this experimental study have appeared in the literature as stochastic matching problems, and stochastic strategic supply chain planning problems. Finally, in terms of extensions of the D 2 method, we also present a new procedure in which the first-stage model is allowed to include continuous variables. We conclude this dissertation with several ideas for future research.

The main objective of this study was to describe the relationship between rangeland condition and land tenure system. Other management and biophysical variables were also analyzed. The data for this study were obtained from range condition studies done during the period of 1973 to 1993 in the State of Sonora, Mexico. The sample of 480 cases, included ejidos and private properties and covering an area of 1,774,479 hectares. The information was analyzed using simple tabulation, contingency analysis, correlation analysis, and multiple regression, using range condition as the dependent variable and the land tenure and management and biophysical variables as the independent variables. No direct linear relationship between rangeland condition and land tenure system was observed, but the chi-square result showed different rangeland condition distribution for both land tenure systems. The only variables linearly related to range condition were infrastructure condition and precipitation. Rangeland condition was most strongly related to precipitation in the year of survey, where higher condition ratings were observed in wetter years. Rangeland condition ratings for ejido holdings were higher than private holdings because the surveys on ejidos were performed in wetter years than private lands. Variables like precipitation are almost impossible to modify, but they should be taken into consideration in cattle management. People can modify some variables. For example, improving the infrastructure condition and attaining a better grazing distribution could help both types of properties to improve rangeland condition. Because precipitation level is so strongly related to rangeland condition in any one year, it is important that land managers, administrators, lenders, and policy makers demand many years of rangeland condition surveys, that include wet and dry years to evaluate all rangeland management practices, including the land tenure system.

Three time domain system identification (SI) approaches, i.e., Modified Iterative Least Square with Unknown Input (ILS-UI), Localized Structural Identification, and Modified Iterative Least Square--Extended Kalman Filter with Unknown Input (ILS-EKF-UI), are proposed to identify defects at the element level of structures. In all these methods, structures are modeled using the finite element method (FEM) and the structural parameters (stiffness and damping) are identified using only output response measurements without using any information on input excitation. Excitations are identified as a byproduct of the SI procedures. If damping is considered to be proportional or Rayleigh-type, the time domain SI technique becomes nonlinear even though the dynamic system remains linear. The Modified ILS-UI approach is essentially a nonlinear SI algorithm. The Localized Structural Identification combines a time domain SI technique and FEM formulation representing a part of the structure. The time domain responses at each time instance represent an equilibrium status of the system which is reflected in the nodal equilibrium in the FEM. Using the Localized Structural Model, only dynamic responses at the local region closely connected to the part of the structure to be identified are required. This dramatically reduces the measurement requirements, and makes it possible to identify the parameters of the whole structure by identifying only part of it. This study discusses how to select elements of the local structure and how to determine the locations and number of the output measurements. The Modified ILS-EKF-UI approach was developed by combining the Modified ILS-UI and the Localized Structural Identification. Using the Modified ILS-EKF-UI approach, the system can be identified using responses at a reduced number of dynamic degrees of freedom. This method allows the finite element mesh to be refined further for more localized parameter identification without additional response information. All three methods are verified using numerical examples. They identify the structures very well. They are found to be more accurate than other methods currently reported in the literature even when input excitation information is used to identify structures. Various types of structures are examined, including shear buildings, plane frames, and plane trusses. The proposed methods are found to be robust even when the responses are contaminated with noise.

Irrigation scheduling using the soil water balance approach has been recommended to irrigators for many years. Reasonably good results are normally obtained by researchers using carefully quantified inputs. Irrigators in production agriculture may estimate inputs and then question the validity of the method when the irrigation recommendations conflict with present irrigation schedules. By associating each input with an interval representing possible bias based on the way the input was estimated, and solving the irrigation scheduling model using the intervals as inputs, the output was associated with an interval representing possible bias. This method was also used to evaluate possible bias associated with growing degree day based crop coefficient curves developed from Arizona crop consumptive use measurements. For comparison purposes, roughly estimated inputs based on irrigation system type, soil type, area weather data and available crop coefficient curves were used as default intervals. Improved input intervals consisted of observed irrigation system performance, soil property measurements, local weather data and theoretical improvements in crop coefficient curves. For surface irrigation, field observation of plant stress and soil water content showed the greatest potential to improve irrigation date predictions. For buried drip under a row crop, accuracy of the predicted daily irrigation rate was most improved by a better estimate of irrigation efficacy.

This dissertation is intended to study the stochastic optimization of a dynamical currency option hedging process and presents a sampling-based scenario aggregation algorithm which can be used to solve the optimal currency option hedging model. First, we review various financial applications of stochastic programming modeling techniques in the literature and examine traditional option hedging and valuation methods in finance. Next, we analyze the uncertain factors in currency exchange and discuss how to generate scenarios and scenario tree for financial optimization methods. We examine the advantages of using short-term derivative securities in portfolio hedging and give valuation models for the short term derivative securities traded in the exchange market. We provide three types of optimal currency option hedging models to satisfy various hedging environment and risk management needs. To solve the currency option hedging model, we propose a sampling-based stochastic programming algorithm which is based on its corresponding deterministic algorithm. The sample frequencies and a sampled scenario tree will be used to approximate the scenario probabilities and the true scenario tree respectively in the algorithm. We prove that the iteration points will converge with probability one to the true optimal solution asymptotically and show that the accuracy and speed of the algorithm depend on the sample size and error tolerance for each sampled problem in the iterations. Finally, we present the results of numerical experiments of our option hedging models and sampling-based scenario aggregation algorithm. The computational results for the option hedging models show that our optimal hedging method generates better cost-profit hedging performance compared with traditional hedging methods. The experiments of the sampling algorithm shows that the algorithm can generate good solutions effectively, especially for extremely large-scale stochastic programming problems.

Dynamic programming (DP) is one of the most important mathematical programming methods. However, a major limitation in the practical application of DP methods to stochastic decision and control problems has been the explosive computational burden. Significant amounts of research have been focused on improving the speed of convergence and allowing for larger state and action spaces. The principal methods and algorithms of DP are surveyed in this dissertation. The rank-one correction method for value iteration (ROC) recently proposed by Bertsekas was designed to increase the speed of convergence. In this dissertation we have extended the ROC method proposed by Bertsekas to problems with multiple policies. This method is particularly well-suited to systems with substochastic matrices, e.g., those arising in shortest path problems. In order to test, verify, and compare different computational methods we developed a FORTRAN software laboratory for Stochastic s (YS)tems (CO)ntrol and (DE)cision algorithms for discrete time, finite Markov decision processes (SYSCODE). This is a user-friendly, interactive software laboratory. SYSCODE provides the user with a choice of 39 combinations of DP algorithms for testing and 1 comparison. SYSCODE has also been endowed with sophisticated capabilities for random problem data generation. We present a comprehensive computational comparison of many of the algorithms provided by SYSCODE using well-known test problems as well as randomly generated problem data.

Both static and dynamic aspects of oligopoly are discussed in the beginning of this thesis and four expectation schemes of dynamic oligopolies have been investigated and tested. Some modifications have also been added to an earlier computer program developed originally by Wu (1991) to improve the stability of the models. Computer simulation results are reported at the end of this thesis.

The Markovian Arrival Process (MAP) is a tractable, versatile class of Markov renewal processes which has been extensively used to model arrival (or service) processes in queues. This thesis mainly deals with the first two moment matrices of the counts for the MAP. We derive asymptotic expansions for these two moment matrices and also derive efficient and stable algorithms to compute these matrices numerically. Simpler expressions for some of the classical mathematical descriptors of the superposition of independent MAPs also are derived.

The Modified Covering Problem (MCP) is introduced and theory is developed for solving it on paths and trees. First, the Modified Covering Problem is defined as a subset of the Conditional Covering Problem, and motivations are proposed for its study. Next, a literature review examines relevant, published material. The MCP is then formulated as a binary integer program, followed by an examination of the characteristics of its feasible solutions, optimality, and overall complexity. A polynomial algorithm is developed for the solving the MCP on paths with uniform link distances, and solving within 20% of optimality on paths with non-uniform link distances. Next, an exponential algorithm is developed to solve non-uniform link distance problems to optimality. The theory is then further expanded to construct an algorithm to develop strong upper and lower bounds for the optimal solution on trees with non-uniform link distances.

The Tricotyledon Theory of System Design is applied to large scale complex systems. This implies a large staff and budget to accomplish the system design. Elements of the theory can be applied to smaller system with severe constraints on the Technology Requirement. These include requirement definition, concept exploration, functional analysis, and physical synthesis. In addition, system terminology will be modified where necessary to more easily convey the meaning of the theory to the novice systems engineer. An implementation using hypertext techniques and object oriented programming was done to guide an engineer through the development of the systems engineering plans. The ability to create and modify performance, resource and tradeoff indexes and figures of merit is provided to allow full comparison of differing system designs.