Solving a mixed-integer programming formulation of a classification model with misclassification limitsBrooks, J. Paul 25 August 2005 (has links)
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.
Gandonou, Jean-Marc A.
01 January 2005
Precision agriculture (PA) can be defined as a set of technologies that have helped propel agriculture into the computerized information-based world, and is designed to help farmers get greater control over the management of farm operations. Because of its potential to spatially reduce yield variability within the field through variable rate application of nutrients it is thought to be a production risk management instrument. Subsurface drip irrigation (SDI) is another production risk management technology that is generating interest from the farming community as a result of new technological improvements that facilitate equipment maintenance and reduces water consumption.In the first article the production risk management potential of these two technologies was investigated both for each technology and for a combination of the two. Simulated yield data for corn, wheat and soybeans were obtained using EPIC, a crop growth simulation model. Mathematical programming techniques were used in a standard E-V framework to reproduce the production environment of a Kentucky commercial grain farmer in Henderson County. Results show that for risk averse farmers, the lowest yield variability was obtained with the SDI technology. The highest profit level was obtained when the two technologies were combined.Investment in two sets of equipments (PA and SDI) to maximize profitability and reduce risk could however expose many farm operations to financial risk. In the second article, a discrete stochastic sequential programming (DSSP) model was used to analyze the impact of PA and/or SDI equipment investment on the farm's liquidity and debt to asset ratio.In the last article, the cotton sector in Benin, West Africa, was utilized to study the transferability of PA technology to a developing country. Properly introduced, precision agriculture (PA) technology could help farmers increase profitability, improve management practices, and reduce soil depletion. An improved production system could also help farmers better cope with the policy risk related to cotton production. Results from the two models show that PA is less profitable for the risk neutral farmer but more profitable for the risk averse one when compared to conventional production practices. The adoption of the new technology also has very little impact on the choice of crop rotation made by the farmer.
Wheatley, David Michael
This thesis studies an inventory-location problem faced by a large manufacturer and supplier of small to medium sized aircraft and their spare parts. The sale of after market spare parts is a major source of revenue for the company, but it is a complex industry with many unique challenges. The original problem is a multi-echelon network design problem, which is decomposed into a facility location problem with consolidated shipping challenges, and a spare parts inventory problem. The facility location problem is solved a number of times under different scenarios to give the company's leadership team access to a wide range of feasible solutions. The model itself is an important contribution to industry, allowing the company to solve a spare parts network problem that will guide strategic decision-making for years. The chapter serves as case-study on how to accurately model a large and complicated service parts supply chain through the use of mathematical programming, part aggregation and scenarios. The company used the scenario results to redesign its spare parts distribution network, opening new hubs and consolidating existing service centres. The costs savings associated with this project are estimated to be $4.4 Million USD annually. The proposed solution does increase the burden of customer freight charges on the company's customers compared to the current network, but the operational savings are expected to more than outweigh the increase in customer shipments costs. The project team thus recommended that the company consider subsidizing customer freight costs to offset the expected cost increase the customers face, resulting in lower costs for both the company and their customers. This solution could set a new standard for aircraft spare parts suppliers to follow. Considered next is an integrated inventory-location problem with service requirements based on the first problem. Customer demand is Poisson distributed and the service levels are time-based, leading to highly non-linear, stochastic service constraints and a nonlinear, mixed-integer optimization problem. Unlike previous works in the literature that propose approximations for the nonlinear constraints, this thesis presents an exact solution methodology using logic-based Benders decomposition. The problem is decomposed to separate the location decisions in the master problem from the inventory decisions in the subproblem. A new family of valid cuts is proposed and the algorithm is shown to converge to optimality. This is the first attempt to solve this type of problem exactly. Then, this thesis presents a new restrict-and-decompose scheme to further decompose the Benders master problem by part. The approach is tested on industry instances as well as random instances. The second algorithm is able to solve industry instances with up to 60 parts within two hours of computation time, while the maximum number of parts attempted in the literature is currently five. Finally, this thesis studies a second integrated inventory-location problem under different assumptions. While the previous model uses the backorder assumption for unfilled demand and a strict time window, the third model uses the lost-sales assumption and a soft time window for satisfying time sensitive customer demand. The restrict-and-decompose scheme is applied with little modification, the main difference being the calculation of the Benders cut coefficients. The algorithm is again guaranteed to converge to optimality. The results are compared against previous work under the same assumptions. The results deliver better solutions and certificates of optimality to a large set of test problems.
In this thesis some problems in mathematical programming have been studied. Chapter 1 contains a brief review of the problems studied and the motivation for choosing these problems for further investigation. The development of two algorithms for finding all the vertices of a convex polyhedron and their applications are reported in Chapter 2. The linear complementary problem is studied in Chapter 3 and an algorithm to solve this problem is outlined. Chapter 4 contains a description of the plant location problem (uncapacited). This problem has been studied in some depth and an algorithm to solve this problem is presented. By using the Chinese representation of integers a new algorithm has been developed for transforming a nonsingular integer matrix into its Smith Normal Form; this work is discussed in Chapter 5. A hybrid algorithm involving the gradient method and the simplex method has also been developed to solve the linear programming problem. Chapter 6 contains a description of this method. The computer programs written in FORTRAN IV for these algorithms are set out in Appendices Rl to R5. A report on study of the group theory and its application in mathematical programming is presented as supplementary material. The algorithms in Chapter 2 are new. Part one of Chapter 3 is a collection of published material on the solution of the linear complementary problem; however the algorithm in Part two of this Chapter is original. The formulation of the plant location problem (uncapacited) together with some simplifications are claimed to be original. The use of Chinese representation of integers to transform an integer matrix into its Smith Normal Form is a new technique. The algorithm in Chapter 6 illustrates a new approach to solve the linear programming problem by a mixture of gradient and simplex method.
A number of researchers have proposed several Bayesian methods for portfolio selection, which combine statistical information from financial time series with the prior beliefs of the portfolio manager, in an attempt to reduce the impact of estimation errors in distribution parameters on the portfolio selection process and the effect of these errors on the performance of 'optimal' portfolios in out-of-sample-data. This thesis seeks to reverse the direction of this process, inferring portfolio managers’ probabilistic beliefs about future distributions based on the portfolios that they hold. We refer to the process of portfolio selection as the forward problem and the process of retrieving the implied probabilities, given an optimal portfolio, as the inverse problem. We attempt to solve the inverse problem in a general setting by using a finite set of scenarios. Using a discrete time framework, we can retrieve probabilities associated with each of the scenarios, which tells us the views of the portfolio manager implicit in the choice of a portfolio considered optimal. We conduct the implied views analysis for portfolios selected using expected utility maximization, where the investor's utility function is a globally non-optimal concave function, and in the mean-variance setting with the covariance matrix assumed to be given. We then use the models developed for inverse problem on empirical data to retrieve the implied views implicit in a given portfolio, and attempt to determine whether incorporating these views in portfolio selection improves portfolio performance out of sample.
Campos, José Renato.
Orientador: Geraldo Nunes Silva / Banca: Vilma Alves de Oliveira / Banca: Heloisa Helena Marino Silva / Resumo: Métodos de Runge-Kutta para problemas de controle ótimo contínuo são estudados seguindo os trabalhos de Hager ,  e . O problema de controle ótimo é discretizado transformando-se num problema de programação matemática. Um estudo sobre as condições necessárias de otimalidade para a solução do problema e conexões com o problema adjunto é realizado para obtenção das condições de ordem na discretização. Estuda-se também a convergência da solução do problema discretizado para a solução ótima do problema contínuo (ver Hager ). Nesta análise Hager obtêm uma cota para o erro entre a solução numérica e a solução contínua o qual depende do tamanho do passo. Por fim, o trabalho apresenta alguns exemplos com o intuito de ilustrar a teoria apresentada. / Abstract: Runge-Kutta methods for continuous optimal control problems are studied following the papers of Hager ,  and . The control problem is discretized and transformed into a mathematical programming problem. A study about necessary conditions of optimality for the solution of the problem and connections with an adjoint problem are done to provide order conditions for the method of discretization. It is also studied the convergence of the optimal solution of the discrete problem for the solution of the continuous time control problem (see Hager ). In this convergence analysis Hager obtains an error bound comparing the numerical and the continuous solution. The error bound is dependent of the size of the step of the method. Finally, some examples are presented aiming at illustrating the discussed theory. / Mestre
With an increasing proportion of elderly and an increasing demand for healthcare, managerial efforts are needed in order make the best use of resources and to keep cost under control. One of the most critical and expensive resources in a hospital is the operating theatre. This thesis aims to investigate the potential of computer-based modelling for supporting healthcare decision makers to improve management policies related to the hospital operating theatre. In a study conducted at a medium sized Swedish hospital we identify important prioritisations and decisions made in relation to patient scheduling and resource allocation when planning for surgery. Patient scheduling and operating room planning are complex tasks with a number of influencing factors to consider like, e.g., uncertainty in patient arrival, uncertainty in surgery procedure time and medical prioritisations and diagnosis. Further, several intersected dependencies, e.g. pre- and post operative care, have to be considered as to prevent occlusion and obtain a maximum patient through-put. With an optimisation-based approach we demonstrate how different criteria in patient scheduling and resource allocations can affect various objectives in terms of patient perspectives, staff perspectives and costs. For instance, we show that the current policy for resource allocation does not handle the variability generated by the patient diagnosis very well. In Sweden a law has recently been introduced, which advocates restrictions in elective patient waiting times. We extend the optimisation-based approach to include post-operative care and simulate a scenario based on patient data from a Swedish hospital to be able to predict the possible impact of the new law. The results indicate that the law causes an unsuitable increase in the waiting times for medium prioritised patients. Furthermore, we propose a combination of discreteevent simulation and optimisation to examine what impact different resource allocations of emergency and elective resources have on both utilisation rate and disturbance consequences, i.e. surgery cancellation and overtime work, due to emergency cases and other unexpected events. We show that both utilisation rate and cancellation frequencies can be improved significantly by the application of some minor changes in the resource allocation. Finally, we explore some future possibilities of using agent technology for modelling health care management decisions.
14 June 2022
Optimized Routing and Scheduling (RS) for mobile caregivers is essential for the efficient management of Home Health Care services. Unexpected events, such as traffic jams and visits lasting longer or shorter than expected, may affect the initial caregiver’s schedule by delaying or accelerating visits. Therefore, the RS should be continuously updated to deliver services that respect the problem constraints, e.g., patients’ and caregivers’ availability, caregivers’ breaks, etc., while minimizing the total costs of services. The services costs include travel, overtime, time exceeding patient time windows, and working time differences among caregivers. In this research, we formulate and solve a mixed-integer linear programming RS model that considers delays and earliness throughout the day. Once delays or earliness arise, we propose a rescheduling approach capable of updating the current schedule to consider the time difference and instantly provide a new optimal outcome. Results show a decrease in total costs in 48% of the cases, with an average saving of 349$ per day when rescheduling patients. 15% of the cases present an increase in total costs by an average of 143$ per day. No change is observed in 37% of the cases. Finally, when applying the rescheduling approach, results show that larger time windows provide more significant savings when delays are observed throughout the day.
Policies Affecting Production Practices and Adoption of Integrated Pest Management for Jamaican Farmers in Ebony Park, ClarendonOgrodowczyk, Joseph Daniel 07 April 1999 (has links)
Farmers' decisions to adopt Integrated Pest Management (IPM) technologies depend on the profitability of IPM systems relative to the traditional production methods. Government policies may affect the profitability of the IPM technologies. A linear programming model was developed and used to evaluate the economic incentives for adoption of Integrated Pest Mangement (IPM) practices by Jamaican farmers in Ebony Park, Clarendon. Further analysis was completed to determine the affect of policy changes on the profitability of the IPM systems. The objective function of the model was to maximize net returns above variable costs for the farm and included: ten cropping systems, resource constraints, relative prices, and government policies facing the farm. Resource constraints included risk constraints limiting the maximum acreage planted for each crop. Potential crops grown by the farm included: IPM and conventional hot pepper, IPM and conventional sweet potato, IPM and conventional callaloo, corn, pumpkin, cassava, and sugar cane. The trade and domestic policies incorporated into the model were: preclearance (farm level inspections of exportable harvest), elimination of the concessionary water rates to farmers, lowering the duty concession rate to farmers, lowering the Common External Tariff, appreciation of the real exchange rate, elimination of the credit subsidy and a fall in the real interest rate. The results of the model showed four major conclusions. First, the IPM systems for hot pepper, sweet potato and callaloo were more profitable than the conventional systems. Second, within the framework of risk constraints and preclearance, the IPM systems continued to be more profitable than the conventional practices. Third, the elimination of either the water or credit subsidies currently available to the farmers did not greatly affect the profitability of the IPM systems compared with the profitability of conventional production. Fourth, with a lower real interest rate, the elimination of the duty concession, a lowering of the Common External Tariff (CET) or an appreciation of the real exchange rate, the IPM systems were more profitable than the conventional technologies. Four implications arose from the conclusions. First, extension efforts towards farmers should emphasize the increase in profits from the IPM technologies. Second, policy steps designed to liberalize the domestic economy will not require offsetting policies supporting the adoption of IPM by farmers in Clarendon. Further research is needed on the effects of water availability on IPM adoption and the potential barriers to IPM adoption by female-headed households. Finally, further research is on the economic returns of incorporating preclearance education with IPM. / Master of Science
Reeves, Laurence H.
01 May 1991
Agroforestry as a sustainable production system has been recognized as a land use system with the potential to slow encroachment of agriculture onto forested lands in developing countries. However, the acceptance of nontraditional agroforestry systems has been hampered in some areas due to the risk-averse nature of rural agriculturalists. By explicitly recognizing risk in agroforestry planning, a wider acceptance of agroforestry is possible. This thesis consists of a collection of three papers that explore the potential of modern stock portfolio theory to reduce financial risk in agroforestry planning. The first paper presents a theoretical framework that incorporates modern stock portfolio theory through mathematical programming. This framework allows for the explicit recognition of financial risk by using a knowledge of past net revenue trends and fluctuations for various cropping systems, with the assumption that past trend behavior is indicative of future behavior. The paper demonstrates how financial risk can be reduced by selecting cropping systems with stable and/or negatively correlated net revenues, thereby reducing the variance of future net revenues. Agroforestry systems generally entail growing simultaneously some combination of plant and/or animal species. As a result, interactions between crops usually cause crop yields within systems to deviate from what would be observed under monocultural conditions, thus requiring some means of incorporating these interactions into mathematical models. The second paper presents two approaches to modeling such interactions, depending on the nature of the interaction. The continuous system approach is appropriate under conditions where yield interactions are linear between crops and allows for a continuous range of crop mixtures. The discrete system approach should be used where nonlinear interactions occur. Under this second approach, decision variables are defined as fixed crop mixtures with known yields. In the third paper, the techniques presented above were applied to a case study site in Costa Rica. Using MOTAD programming and a discrete system approach, a set of minimum-risk farm plans were derived for a hypothetical farm. For the region studied, results indicate that reductions in risk require substantial reductions in expected net revenue.
Page generated in 0.2005 seconds