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.

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.

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.

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 [11], [15] e [17]. 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 [17]). 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 [11], [15] and [17]. 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 [17]). 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.

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.

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.

Cette thèse est consacrée à l’étude et à la discussion de deux questions importantes qui se posent dans le domaine de la Programmation Mathématique: les symétries et les distances. En arrière-plan, nous examinons la Programmation Semidéfinie (PSD) et sa pertinence comme l’un des principaux outils employés aujourd’hui pour résoudre les Programmes Mathématiques (PM) durs. Après le chapitre introductif, nous discutons des symétries au Chapitre 2 et des distances au Chapitre 5. Entre ces deux chapitres, nous présentons deux courts chapitres que nous préférons en fait appeler entr’actes: leur contenu ne mérite pas d’être publié pour le moment, mais ils fournissent un lien entre les deux Chapitres 2 et 5 apparemment distincts, qui contiennent les principales contributions de cette thèse. Il est bien connu que les PMs symétriques sont plus difficiles à résoudre pour l’optimalité globale en utilisant des algorithmes du type Branch-and-Bound (B&B). Il est également bien connu que certaines des symétries de solution sont évidentes dans la formulation, ce qui permet d’essayer de traiter les symétries en tant qu’étape de prétraitement. L’une des approches les plus simples consiste à rompre les symétries en associant les Contraintes de Rupture de Symétrie (CRS) à la formulation, en supprimant ainsi des optima globaux symétriques, puis à résoudre la reformulation avec un solveur générique. Ces contraintes peuvent être générés à partir de chaque orbite de l’action des symétries sur l’ensemble des indices des variables. Cependant, il est difficile de savoir si et comment il est possible de choisir deux ou plus orbites distinctes pour générer des CRSs qui sont compatibles les unes avec les autres (elles ne rendent pas tous les optima globaux infaisables). Dans le Chapitre 2, nous discutons et testons un nouveau concept d’Indépendance Orbitale (IO) qui clarifie cette question. Les expériences numériques réalisées à l’aide de PLMEs et de PNLMEs soulignent l’exactitude et l’utilité de la théorie de l’IO. Programmation Quadratique Binaire (PQB) est utilisée pour étudier les symétries et SDP dans Entr'acte 3. Programmes quadratiques binaires symétriques ayant une certaine structure de symétrie sont générés et utilisés pour illustrer les conditions dans lesquelles l'utilisation de CRSs est avantageuse. Une discussion préliminaire sur l'impact des symétries et des CRSs dans la performance des solveurs PSD est également réalisée. Le Problème Euclidien de l'Arbre de Steiner est étudié dans Entr'acte 4. Deux modèles sont dérivés, ainsi que des relaxations SDP. Un algorithme heuristique basé à la fois sur les modèles mathématiques et sur les principes d'IO présentés au Chapitre 2 est également proposé. Concernant ces méthodes, des résultats préliminaires sur un petit ensemble d'exemples bien connus sont fournis. Finalement, dans le Chapitre 5, nous abordons le problème fondamental qui se pose dans le domaine de la Géométrie de Distance: il s’agit de trouver une réalisation d’un graphe pondéré non orienté dans RK pour un certain K donné, de sorte que les positions pour les sommets adjacents respectent la distance donnée par le poids de l’arête correspondante. Le Problème de la Géométrie de Distance Euclidienne (PGDE) est d’une grande importance car il a de nombreuses applications en science et en ingénierie. Il est difficile de calculer numériquement des solutions, et la plupart des méthodes proposées jusqu’à présent ne sont pas adaptées à des tailles utiles ou sont peu susceptibles d’identifier de bonnes solutions. La nécessité de contraindre le rang de la matrice représentant des solutions réalisables du PGDE rend le problème si difficile. Nous proposons un algorithme heuristique en deux étapes basé sur la PSD (en fait basé sur le paradigme de la PDD) et la modélisation explicite de Contraintes de Rang. Nous fournissons tests informatiques comprenant des instances générées de façon aléatoire ainsi que des exemples réalistes de conformation de protéines. / This thesis is mostly dedicated to study and discuss two important challenges existing not only in the field of Mathematical Programming: symmetries and distances. In the background we take a look into Semidefinite Programming (SDP) and its pertinency as one of the major tools employed nowadays to solve hard Mathematical Programs (MP). After the introductory Chapter 1, we discuss about symmetries in Chapter 2 and about distances in Chapter 5. In between them we present two short chapters that we actually prefer to call as entr’actes: their content is not necessarily worthy of publication yet, but they do provide a connection between the two seemingly separate Chapters 2 and 5, which are the ones containing the main contributions of this thesis. It is widely known that symmetric MPs are harder to solve to global optimality using Branch-and-Bound (B&B) type algorithms, given that the solution symmetry is reflected in the size of the B&B tree. It is also well-known that some of the solution symmetries are usually evident in the formulation, which makes it possible to attempt to deal with symmetries as a preprocessing step. Implementation-wise, one of the simplest approaches is to break symmetries by adjoining Symmetry-Breaking Constraints (SBC) to the formulation, thereby removing some symmetric global optima, then solve the reformulation with a generic solver. Sets of such constraints can be generated from each orbit of the action of the symmetries on the variable index set. It is unclear, however, whether and how it is possible to choose two or more separate orbits to generate SBCs which are compatible with each other (in the sense that they do not make all global optima infeasible). In Chapter 2 we discuss and test a new concept of Orbital Independence (OI) that clarifies this issue. The numerical experiences conducted using public MILPs and MINLPs emphasize the correctness and usefulness of the OI theory. Binary Quadratic Programming (BQP) is used to investigate symmetries and SDP in Entr'acte 3. Symmetric Binary Quadratic Programs having a certain symmetry structure are generated and used to exemplify the conditions under which the usage of SBCs is majoritarily advantageous. A preliminary discussion about the impact of symmetries and SBCs in the performance of SDP solvers is also carried out. The Euclidean Steiner Tree Problem is studied in Entr'acte 4. Two models (which are exact reformulations of an existing formulation) are derived, as well as SDP relaxations. A heuristic algorithm based on both the mathematical models and the OI principles presented in Chapter 2 is also proposed. As concerns these methods, preliminary results on a small set of well-known instances are provided. Finally and following up the Distance Geometry subject, in Chapter 5 we cope with the most fundamental problem arising in the field of Distance Geometry, the one of realizing graphs in Euclidean spaces: it asks to find a realization of an edge-weighted undirected graph in RK for some given K such that the positions for adjacent vertices respect the distance given by the corresponding edge weight. The Euclidean Distance Geometry Problem (EDGP) is of great importance since it has many applications to science and engineering. It is notoriously difficult to solve computationally, and most of the methods proposed so far either do not scale up to useful sizes, or unlikely identify good solutions. In fact, the need to constrain the rank of the matrix representing feasible solutions of the EDGP is what makes the problem so hard. Intending to overcome these issues, we propose a two-steps heuristic algorithm based on SDP (or more precisely based on the very recent Diagonally Dominant Programming paradigm) and the explicitly modeling of Rank Constraints. We provide extensive computational testing against randomly generated instances as well as against feasible realistic protein conformation instances taken from the Protein Data Bank to analyze our method.