Chlamydia Trachomatis and Neisseria Gonorrhoeae rank as the two most commonly reported sexually transmitted diseases (STDs) in the United States. Under limited budget, publicly funded clinics are not able to screen and treat the two diseases for all patients. They have to make a decision as to which group of population shall go through the procedure for screening and treating the two diseases. Therefore, we propose a cubic integer programming model on maximizing the number of units of cured diseases. At the same time, a two-step algorithm is established to solve the cubic integer program. We further develop a web-server, which immediately make recommendation on identifying population groups, screening assays and treatment regimens. Running on the empirical data provided by the Centers for Disease Control and Prevention, our program gives more accurate optimal results comparing to MS Excel solver within a very short time.

Knapsack problem has been widely studied in computer science for years. There exist several variants of the problem, with zero-one maximum knapsack in one dimension being the simplest one. In this thesis we study several existing approximation algorithms for the minimization version of the problem and propose a scaling based fully polynomial time approximation scheme for the minimum knapsack problem. We compare the performance of this algorithm with existing algorithms. Our experiments show that, the proposed algorithm runs fast and has a good performance ratio in practice. We also conduct extensive experiments on the data provided by Canadian Pacific Logistics Solutions during the MITACS internship program. We propose a scaling based e-approximation scheme for the multidimensional (d-dimensional) minimum knapsack problem and compare its performance with a generalization of a greedy algorithm for minimum knapsack in d dimensions. Our experiments show that the e- approximation scheme exhibits good performance ratio in practice. / x, 85 leaves ; 29 cm

The release of flammable and toxic chemicals in petrochemical facilities is a major concern when designing modern process safety systems. While the proper selection of the necessary types of gas detectors needed is important, appropriate placement of these detectors is required in order to have a well-functioning gas detection system. However, the uncertainty in leak locations, gas composition, process and weather conditions, and process geometries must all be considered when attempting to determine the appropriate number and placement of the gas detectors. Because traditional approaches are typically based on heuristics, there exists the need to develop more rigorous optimization based approaches to handling this problem. This work presents several mixed-integer programming formulations to address this need. First, a general mixed-integer linear programming problem is presented. This formulation takes advantage of precomputed computational fluid dynamics (CFD) simulations to determine a gas detector placement that minimizes the expected detection time across all scenarios. An extension to this formulation is added that considers the overall coverage in a facility in order to improve the detector placement when enough scenarios may not be available. Additionally, a formulation considering the Conditional-Value-at-Risk is also presented. This formulation provides some control over the shape of the tail of the distribution, not only minimizing the expected detection time across all scenarios, but also improving the tail behavior. In addition to improved formulations, procedures are introduced to determine confidence in the placement generated and to determine if enough scenarios have been used in determining the gas detector placement. First, a procedure is introduced to analyze the performance of the proposed gas detector placement in the face of “unforeseen” scenarios, or scenarios that were not necessarily included in the original formulation. Additionally, a procedure for determine the confidence interval on the optimality gap between a placement generated with a sample of scenarios and its estimated performance on the entire uncertainty space. Finally, a method for determining if enough scenarios have been used and how much additional benefit is expected by adding more scenarios to the optimization is proposed. Results are presented for each of the formulations and methods presented using three data sets from an actual process facility. The use of an off-the-shelf toolkit for the placement of detectors in municipal water networks from the EPA, known as TEVA-SPOT, is explored. Because this toolkit was not designed for placing gas detectors, some adaptation of the files is necessary, and the procedure for doing so is presented.

No description available.

In the last two decades, the western world witnessed a continuous rise in the health expenditure. Meanwhile, complaints from patients on excessive waiting times are also increasing. In the past, many researchers have tried to devise appointment scheduling rules to provide trade-offs between maximizing patients’ satisfaction and minimizing the costs of the health providers. For instance, this challenge appears appointment scheduling problems (ASP). Commonly used methods in ASP include analytical methods, simulation studies, and combination of simulation with heuristic approaches. Analytical methods (e.g., queuing theory and mathematical programming) face challenges of fully capturing the complexities of systems and usually make strong assumptions for tractability of problems. These methods simplify the whole system to a single-stage unit and ignore the actual system factors such as the presence of multiple stages and/or resource constraints. Simulation studies, conversely, are able to model most complexities of the actual system, but they typically lack an optimization strategy to deliver optimal appointment schedules. Also, heuristic approaches normally are based on intuitive rules and do not perform well as standalone methods. In order to reach an optimal schedule while considering complexities in actual health care systems, this thesis proposes efficient and effective methods that yield (near) optimal appointment schedules by integrating mathematical programming, a tabu search optimization algorithm and discrete event simulation. The proposed methodologies address the challenges and complexities of scheduling in real world multistage healthcare units in the presence of stochastic service durations, a mix of patient types, patients with heterogeneous service sequence, and resource constraints. Moreover, the proposed methodology is capable of finding the optimum considering simultaneously multiple performance criteria. A Pareto front (a set of optimal solutions) for the performance criteria can be obtained using the proposed methods. Healthcare management can use the Pareto front to choose the appropriate policy based on different conditions and priorities. In addition, the proposed method has been applied to two case studies of Operating Rooms departments in two major Canadian hospitals. The comparison of actual schedules and the ones yielded by the proposed method indicates that proposed method can improve the appointment scheduling in realistic clinical settings.

In this Ph.D. dissertation research, we lay the mathematical foundations of various fundamental concepts in convex mixed-integer programs (MIPs), that is, optimization problems where all the decision variables belong to a given convex set and, in addition, a subset of them are required to be integer. In particular, we study properties of their feasible region and properties of cutting planes. The main contribution of this work is the extension of several fundamental results from the theory of linear MIPs to the case of convex MIPs. In the first part, we study properties of general closed convex sets that determine the closedness and polyhedrality of their integer hulls. We first present necessary and sufficient conditions for the integer hull of a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the integer hulls of general convex sets to be polyhedra. This result generalizes the well-known result due to Meyer in the case of linear MIPs. Under a simple technical assumption, we show that these sufficient conditions are also necessary for the integer hull of general convex sets to be polyhedra. In the second part, we apply the previous results to mixed-integer second order conic programs (MISOCPs), a special case of nonlinear convex MIPs. We show that there exists a polynomial time algorithm to check the closedness of the mixed integer hulls of simple MISOCPs. Moreover, in the special case of pure integer problems, we present sufficient conditions for verifying the closedness of the integer hull of intersection of simple MISOCPs that can also be checked in polynomial time. In the third part, we present an extension of the duality theory for linear MIPs to the case of conic MIPs. In particular, we construct a subadditive dual to conic MIPs. Under a simple condition on the primal problem, we are able to prove strong duality. In the fourth part, we study properties of maximal S-free convex sets, where S is a subset of integers contained in an arbitrary convex set. An S-free convex set is a convex set not containing any points of S in its interior. In this part, we show that maximal S-free convex sets are polyhedra and discuss some properties of these sets. In the fifth part, we study some generalizations of the split closure in the case of linear MIPs. Split cuts form a well-known class of valid inequalities for linear MIPs. Cook et al. (1990) showed that the split closure of a rational polyhedron - that is, the set of points in the polyhedron satisfying all split cuts - is again a polyhedron. In this thesis, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We also show how this result can be used to prove that some generalizations of split cuts, namely cross cuts, also yield closures that are rational polyhedra.

The genetic structure of an intra-host viral population has an effect on many clinically important phenotypic traits such as escape from vaccine induced immunity, virulence, and response to antiviral therapies. Next-generation sequencing provides read-coverage sufficient for genomic reconstruction of a heterogeneous, yet highly similar, viral population; and more specifically, for the detection of rare variants. Admittedly, while depth is less of an issue for modern sequencers, the short length of generated reads complicates viral population assembly. This task is worsened by the presence of both random and systematic sequencing errors in huge amounts of data. In this dissertation I present completed work for reconstructing a viral population given next-generation sequencing data. Several algorithms are described for solving this problem under the error-free amplicon (or sliding-window) model. In order for these methods to handle actual real-world data, an error-correction method is proposed. A formal derivation of its likelihood model along with optimization steps for an EM algorithm are presented. Although these methods perform well, they cannot take into account paired-end sequencing data. In order to address this, a new method is detailed that works under the error-free paired-end case along with maximum a-posteriori estimation of the model parameters.

In any supply chain, the location of facilities and the routing of material are important decisions that contribute a significant amount of costs, lowering a corporation's overall profits. These choices become more important when dealing with a global supply chain, whose players span multiple countries and continents. International factors, such as tax rates and transfer prices, must be carefully considered, while the advantages of timely delivery versus cost-effective transportation must be carefully weighed to ensure that customer demands are met at the best possible price. We examine an international supply chain with plants, distribution centers (DCs), and customers in the North American Free Trade Agreement (NAFTA) and the European Union (EU) regions. The company in question manufactures two sub-assemblies at its plant in Mexico, and then assembles them into a final product at DCs in North America and Europe. To better serve its European customers, the company wishes to locate a new plant in the EU, as well as determine the modes of transportation used to distribute products between nodes, while maximizing overall profit. The problem is formulated as a mixed integer linear program and is solved in two stages using a Strategic Model (SM) and an Operational Model (OM). In SM, each time period represents one month and we determine the optimal facility locations over a 12-month time horizon. With transportation lead times expressed in days, we can be certain that demand will be fulfilled within a single period, and for this reason, lead times are not considered in SM. At the operational level, however, each time period represents one day, and so lead times must be included as they will affect the choice of mode for a given route. The location results from SM are used as input for OM, which then gives the optimal modal and routing decisions for the network. A number of cases are tested to determine how the optimal network is affected by changes in fixed and variable costs of facilities, transfer prices charged by plants to DCs, and the differing tax rates of each country.

In the last two decades, the western world witnessed a continuous rise in the health expenditure. Meanwhile, complaints from patients on excessive waiting times are also increasing. In the past, many researchers have tried to devise appointment scheduling rules to provide trade-offs between maximizing patients’ satisfaction and minimizing the costs of the health providers. For instance, this challenge appears appointment scheduling problems (ASP). Commonly used methods in ASP include analytical methods, simulation studies, and combination of simulation with heuristic approaches. Analytical methods (e.g., queuing theory and mathematical programming) face challenges of fully capturing the complexities of systems and usually make strong assumptions for tractability of problems. These methods simplify the whole system to a single-stage unit and ignore the actual system factors such as the presence of multiple stages and/or resource constraints. Simulation studies, conversely, are able to model most complexities of the actual system, but they typically lack an optimization strategy to deliver optimal appointment schedules. Also, heuristic approaches normally are based on intuitive rules and do not perform well as standalone methods. In order to reach an optimal schedule while considering complexities in actual health care systems, this thesis proposes efficient and effective methods that yield (near) optimal appointment schedules by integrating mathematical programming, a tabu search optimization algorithm and discrete event simulation. The proposed methodologies address the challenges and complexities of scheduling in real world multistage healthcare units in the presence of stochastic service durations, a mix of patient types, patients with heterogeneous service sequence, and resource constraints. Moreover, the proposed methodology is capable of finding the optimum considering simultaneously multiple performance criteria. A Pareto front (a set of optimal solutions) for the performance criteria can be obtained using the proposed methods. Healthcare management can use the Pareto front to choose the appropriate policy based on different conditions and priorities. In addition, the proposed method has been applied to two case studies of Operating Rooms departments in two major Canadian hospitals. The comparison of actual schedules and the ones yielded by the proposed method indicates that proposed method can improve the appointment scheduling in realistic clinical settings.

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.