Good quality management decisions often rely on the evaluation and interpretation of data. One of the most popular ways to investigate possible relationships in a given data set is to follow a process of fitting models to the data. Regression models are often employed to assist with decision making. In addition to decision making, regression models can also be used for the optimization and prediction of data. The success of a regression model, however, relies heavily on assumptions made by the model builder. In addition, the model may also be influenced by the presence of outliers; a more robust model, which is not as easily affected by outliers, is necessary in making more accurate interpretations about the data. In this research study robust techniques for regression models with minimal assumptions are explored. Mathematical programming techniques such as linear programming, mixed integer linear programming, and piecewise linear regression are used to formulate a nonlinear regression model. Outlier detection and smoothing techniques are included to address the robustness of the model and to improve predictive accuracy. The performance of the model is tested by applying it to a variety of data sets and comparing the results to those of other models. The results of the empirical experiments are also presented in this study. / Thesis (M.Sc. (Computer Science))--North-West University, Potchefstroom Campus, 2011.

No description available.

Forest managers throughout Canada must contend with natural disturbance processes that vary over both time and space when developing and implementing forest management plans designed to provide a range of economic, ecological, and social values. In this thesis, I develop a stochastic simulation model with an embedded linear programming (LP) model and use it to evaluate strategies for reducing uncertainty due to forest fires. My results showed that frequent re-planning was sufficient to reduce variability in harvest volume when the burn fraction was low, however, as the burn fraction increased above 0.45%, the best strategy to reduce variability in harvest volume was to account for fire explicitly in the planning process using Model III. A risk analysis tool was also developed to demonstrate a method for managers to improve decision making under uncertainty. The impact of fire on mature and old forest areas was examined and showed that LP forest management planning models reduce the areas of mature and old forest to the minimum required area and fire further reduces the seral area. As the burn fraction increased, the likelihood of the mature and old forest areas satisfying the minimum area requirements decreased. However, if the seral area constraint was strengthened (i.e., the right hand side of the constraint was increased) the likelihood improved. When the planning model was modified to maximize mature and old forest areas, the two fixed harvest volumes (i.e., 2.0 and 8.0 M. m3/decade) had much different impacts on the areas of mature and old forest when the burn fraction was greater than 0.45%. Bootstrapped burn fraction confidence intervals were used to examine the impact of uncertain burn fraction estimates when using Model III to develop harvest schedules. I found that harvest volume bounds were large when the burn fraction was ≥0.45%. I also examined how the uncertainty in natural burn fraction (i.e., estimates of pre-fire suppression average annual area burned) estimates being used for ecosystem management can impact old forest area requirements and the resulting timber supply.

Chemical and biological contaminants can enter a drinking water distribution system through one of the many access points to the network and can spread quickly affecting a very large area. This is of great concern, and water utilities need to consider effective tools and mitigation strategies to improve water network security. This work presents two components that have been integrated into EPA’s Water Security Toolkit, an open-source software package that includes a set of tools to help water utilities protect the public against potential contamination events. The first component is a novel water quality modeling framework referred to as Merlion. The linear system describing contaminant spread through the network at the core of Merlion provides several advantages and potential uses that are aligned with current emerging water security applications. This computational framework is able to efficiently generate an explicit mathematical model that can be easily embedded into larger mathematical system. Merlion can also be used to efficiently simulate a large number of scenarios speeding up current water security tools by an order of magnitude. The last component is a pair of mixed-integer linear programming (MILP) formulations for efficient source inversion and optimal sampling. The contaminant source inversion problem involves determining the source of contamination given a small set of measurements. The source inversion formulation is able to handle discrete positive/negative measurements from manual grab samples taken at different sampling cycles. In addition, sensor/sample placement formulations are extended to determine the optimal locations for the next manual sampling cycle. This approach is enabled by a strategy that significantly reduces the size of the Merlion water quality model, giving rise to a much smaller MILP that is solvable in a real-time setting. The approach is demonstrated on a large-scale water network model with over 12,000 nodes while considering over 100 timesteps. The results show the approach is successful in finding the source of contamination remarkably quickly, requiring a small number of sampling cycles and a small number of sampling teams. These tools are being integrated and tested with a real-time response system.

A basic issue for translational genomics is to model gene interactions via gene regulatory networks (GRNs) and thereby provide an informatics environment to derive and study effective interventions eradicating the tumor. In this dissertation, we present two different approaches to intervention methods in cancer-related GRNs. Decisions regarding possible interventions are assumed to be made at every state transition of the network. To account for dosing constraints, a model for the sequence of treatment windows is considered, where treatments are allowed only at the beginning of each treatment cycle followed by a recovery phase. Due to biological variabilities within tumor cells, the action period of an antitumor drug can vary among a population of patients. That is, a treatment typically has a random duration of action. We propose a unified approach to such intervention models for any Markovian GRN governing the tumor. To accomplish this, we place the problem in the general framework of partially controlled decision intervals with infinite horizon discounting cost. We present a methodology to devise optimal intervention policies for synthetically generated gene regulatory networks as well as a mutated mammalian cell-cycle network. As a different approach, we view the phenotype as a characterization of the long- run behavior of the Markovian GRN and desire interventions that optimally move the probability mass from undesirable to desirable states. We employ a linear programming approach to formulate the maximal shift problem, that is, optimization is directly based on the amount of shift. Moreover, the same basic linear programming structure is used for a constrained optimization, where there is a limit on the amount of mass that may be shifted to states that are not directly undesirable relative to the pathology of interest, but which bear some perceived risk. We demonstrate the performance of optimal policies on synthetic networks as well as two real GRNs derived from the metastatic melanoma and mammalian cell cycle. These methods, as any effective cancer treatment must, aim to carry out their actions rapidly and with high efficiency such that a very large percentage of tumor cells die or shift into a state where they stop proliferating.

A workforce plan states the number of workers required at any point in time. Efficient workforce plans can help companies achieve their organizational goals while keeping costs low. In ever increasing globalized work market, companies need a competitive edge over their competitors. A competitive edge can be achieved by lowering costs. Labour costs can be one of the significant costs faced by the companies. Efficient workforce plans can provide companies with a competitive edge by finding low cost options to meet customer demand. This thesis studies the problem of determining the required number of workers when there are two categories of workers. Workers belonging to the first category are trained to work on one type of task (called Specialized Workers); whereas, workers in the second category are trained to work in all the tasks (called Flexible Workers). This thesis makes the following three main contributions. First, it addresses this problem when the demand is deterministic and stochastic. Two different models for deterministic demand cases have been proposed. To study the effects of uncertain demand, techniques of Robust Optimization and Robust Mathemat- ical Programming were used. The thesis also investigates methods to solve large instances of this problem; some of the instances we considered have more than 600,000 variables and constraints. As most of the variables are integer, and objective function is nonlinear, a commercial solver was not able to solve the problem in one day. Initially, we tried to solve the problem by using Lagrangian relaxation and Outer approximation techniques but these approaches were not successful. Although effective in solving small problems, these tools were not able to generate a bound within run time limit for the large data set. A number of heuristics were proposed using projection techniques. Finally this thesis develops a genetic algorithm to solve large instances of this prob- lem. For the tested population, the genetic algorithm delivered results within 2-3% of optimal solution.

線性規劃的求解方法依幾何觀點可區分為單體法(Simplex Method)和起源於Karmarkar的內點法(Interior Point Method)，無論在理論上或應用上這兩者的許多變體仍然不斷地在改進中。Dantzig的單體法和它變體的演算法是從邊上角點走到另一角點直至到達最佳點，內點法則是透過這個可行地區的內部的可行點走到可行點的方法。眾所週知，當遭遇最壞案例時單體法求解速度的函數表示成指數形式；而內點法卻成多項式形式。就一般案例而言，實驗證據提議，當問題大小為小型時，以單體法求解速度較佳。而內點法僅僅在很大規模的線性規劃時，其解法優於以單體法為基礎的方法。 儘管內點法求解速度較單體法為快，但大多數運用內點法求得最佳解的原理，都使用一個可行解區域內部的點作為起點(或稱為中心)，然而就原始線性規劃問題而言，求得一可行解其複雜度和求得最佳解的複雜度是相同的。倘若能以單體法製造起始點的方法，搭配內點法的優點，產生一不同於過去單體法和內點法之新演算法，能降低求解速度，則是吸引人的課題。是故作者希望能以線性規劃問題的搜尋方向為主題加以整理，探討如何結合單體法及內點法的特性，深入研究搜尋方向在邊界上可能會發生的問題，並以一演算法為例，設計程式，作數據實驗，實際觀察問題發生的原因及提供解決的方法。

Most combinatorial optimization problems are NP -hard, which imply that under well- believed complexity assumptions, there exist no polynomial time algorithms to solve them. To cope with the NP-hardness, approximation algorithms which return solutions close to the optimal, have become a rich field of study. One successful method for designing approx- imation algorithms has been to model the optimization problem as an integer program and then using its polynomial time solvable linear programming relaxation for the design and analysis of such algorithms. Such a technique is called the LP-based technique. In this thesis, we study the algorithmic aspects of three classes of combinatorial optimization problems using LP-based techniques as our main tool. Connectivity Problems: We study the Steiner tree problem and devise new linear pro- gramming relaxations for the problem. We show an equivalence of our relaxation with the well studied bidirected cut relaxation for the Steiner tree problem. Furthermore, for a class of graphs called quasi-bipartite graphs, we improve the best known upper bound on the integrality gap from 3/2 to 4/3. Algorithmically, we obtain fast and simple approximation algorithms for the Steiner tree problem on quasi-bipartite graphs. Allocation Problems: We study the budgeted al location problem of allocating a set of indivisible items to a set of agents who bid on it but possess a hard budget constraint more than which they are unwilling to pay. This problem is a special case of submodular welfare maximization. We use a natural LP relaxation for the problem and improve the best known approximation factor for the problem from ~ 0.632 to 3/4. We also improve the inapprox- imability factor of the problem to 15/16 and use our techniques to show inapproximability results for many other allocation problems. We also study online allocation problems where the set of items are unknown and appear one at a time. Under some necessary assumptions we provide online algorithms for many problems which attain the (almost) optimal competitive ratio. Both these works have applications in the area of budgeted auctions, the most famous of which are the sponsored search auctions hosted by search engines on the Internet. Design Problems: We formally define and study design problems which asks how the weights of an input instance can be designed, so that the minimum (or maximum) of a certain function of the input can be maximized (respectively, minimized). We show if the function can be approximated to any factor $alpha$, then the optimum design can be approximated to the same factor. We also show that (max-min) design problems are dual to packing problems. We use the framework developed by our study of design problems to obtain results about fraction- ally packing Steiner trees in a "black-box" fashion. Finally, we study integral packing of spanning trees and provide an alternate proof of a theorem of Nash-Williams and Tutte about packing spanning trees.

This thesis presents new results on a few problems involving maximum flows. The first topic we explore is maximum flow network interdiction. The second topic we explore is reoptimization heuristics for rapidly solving an entire sequence of Maximum Flow Problems. In the Cardinality Maximum Flow Network Interdiction Problem (CMFNIP), an interdictor chooses R arcs to delete from an s-t flow network so as to minimize the maximum flow on the network induced on the undeleted arcs. This is an intensively studied problem that has nontrivial applications in military strategy, intercepting contraband and flood control. CMFNIP is a strongly NP-hard special case of the Maximum Flow Network Interdiction Problem (MFNIP), where each arc has an interdiction cost and the interdictor is constrained by an interdiction budget. Although there are several papers on MFNIP, very few theoretical results have been documented. In this talk, we introduce two exponentially large classes of valid inequalities for CMFNIP and prove that they can be separated in polynomial time. Second, we prove that the integrality gap of the commonly used integer linear programming formulation for CMFNIP is contained in the set Omega(|V| ^(1 e)) where |V| is the number of nodes in the network and e is in the interval (0,1). We prove that this result holds even when the linear programming relaxation is strengthened with our two classes of valid inequalities and we note that this result immediately extends to MFNIP. In the second part of this defense, we explore incremental algorithms for solving an online sequence of Maximum Flow Problems (MFPs). Sequences of MFPs arise in a diverse collection of settings including computational biology, finger biometry, constraint programming and real-time scheduling. To initiate this study, we develop an algorithm for solving a sequence of MFPs when the ith MFP differs from the (i-1)st MFP, for each possible i, in that the underlying networks differ by exactly one arc. Second, we develop maximum flow reoptimization heuristics to rapidly compute a robust minimum capacity s-t cut in light of uncertain arc capacities. Third, we develop heuristics to efficiently compute a maximum expected maximum flow in the context of two-stage stochastic programming. We present computational results illustrating the practical performance of our algorithms.

Agricultural economics report 81. / Cover title. / "This manual supplements 'An iterative linear programming procedure for estimating patterns of agricultural land use,' by the present authors." / 28 p. tables