No description available.

This study proposed a utility-driven two-stage stochastic mixed-integer linear programming model to understand how the patient preferences impact the additive manufacturing (AM) supply chain design decisions. The goal of the mathematical model is to maximize the utilities derived from the customer preferences by appropriately allocating the AM facilities in the targeted region under customer decision and demand uncertainty. The mathematical model is visualized and validated by developing a real-life case study that utilizes the biomedical implants data for the state of Mississippi. A number of sensitivity analyses are conducted to understand how the patients' behavioral decisions (e.g., price-centric versus time- or quality-centric customers) to purchase biomedical implants impact the AM supply chain design decisions. The results revealed key managerial insights that could be utilized by healthcare service providers and interested stakeholders to provide quality healthcare services by managing patient-centric AM facility siting decisions.

In this thesis, we study three periodic-review, finite-horizon inventory systems in the presence of supply and demand uncertainties. In the first part of the thesis, we study a multi-period single-station problem in which supply uncertainty is modeled by partial supply. Formulating the problem under a robust optimization (RO) framework, we show that solving the robust counterpart is equivalent to solving a nominal problem with a modified deterministic demand sequence. In particular, in the stationary case the optimal robust policy follows the quasi-(s, S) form and the corresponding s and S levels are theoretically computable. In the second part of the thesis, we extend the RO framework to a multi-period multi-echelon problem. We show that for a tree structure network, decomposition applies so that the optimal single-station robust policy remains valid for each echelon in the tree. Furthermore, if there are no setup costs in the network, then the problem can be decomposed into several uncapacitated single-station problems with new cost parameters subject to the deterministic demands. In the last part of the thesis, we consider a periodic-review Assemble-To-Order (ATO) system with multiple components and multiple products, where the inventory replenishment for each component follows an independent base-stock policy and product demands are satisfied according to a First-Come-First-Served (FCFS) rule. We jointly consider the inventory replenishment and component allocation problems in the ATO system under stochastic component replenishment lead times and stochastic product demands. The problems are formulated under the stochastic programming (SP) framework, which are difficult to solve exactly due to a large number of scenarios. We use the sample average approximation (SAA) algorithms to find near-optimal solutions, which accuracy is verified by the numerical experiment results. / Thesis / Doctor of Philosophy (PhD)

We consider two classes of stochastic programming models which are motivated by two applications related to the field of aviation. The first problem we consider is the network capacity planning problem, which arises in capacity planning of systems with network structures, such as transportation terminals, roadways and telecommunication networks. We study this problem in the context of airport terminal capacity planning. In this problem, the objective is to determine the optimal design and expansion capacities for different areas of the terminal in the presence of uncertainty in future demand levels and expansion costs, such that overall passenger delay is minimized. We model this problem as a nonlinear multistage stochastic integer program with a multicommodity network flow structure. The formulation requires the use of time functions for maximum delays in passageways and processing stations, for which we derive approximations that account for the transient behavior of flow. The deterministic equivalent of the developed model is solved via a branch and bound procedure, in which a bounding heuristic is used at the nodes of the branch and bound tree to obtain integer solutions. In the second study, we consider the project portfolio optimization problem. This problem falls in the class of stochastic programs in which times of uncertainty realizations are dependent on the decisions made. The project portfolio optimization problem deals with the selection of research and development (R&D) projects and determination of optimal resource allocations for the current planning period such that the expected total discounted return or a function of this expectation for all projects over an infinite time horizon is maximized, given the uncertainties and resource limitations over a planning horizon. Accounting for endogeneity in some parameters, we propose efficient modeling and solution approaches for the resulting multistage stochastic integer programming model. We first develop a formulation that is amenable to scenario decomposition, and is applicable to the general class of stochastic problems with endogenous uncertainty. We then demonstrate the use of the sample average approximation method in solving large scale problems of this class, where the sample problems are solved through Lagrangian relaxation and lower bounding heuristics.

Práce se zabývá určením pravděpodobnostních rozdělení pro stochastické programování, při kterém jsou optimální hodnoty účelové funkce extrémní (minimální nebo maximální). Rozdělení se určuje pomocí heuristických metod, konkrétně pomocí genetických algoritmů, kde celá populace aproximuje hledané rozdělení. První kapitoly popisují obecně matematické a stochastické programování a dále jsou popsány různé heuristické metody a s důrazem na genetické algoritmy. Těžiště práce je v naprogramování daného algoritmu a otestování na úlohách lineárních a kvadratických stochastických modelů.

Dans cette thèse, nous étudions différents modèles, déterministes et stochastiques, pour les problèmes de dimensionnement de réseaux. Nous examinons également le problème du sac-à-dos stochastique ainsi que, plus généralement, les contraintes de capacité en probabilité.<p>\ / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Při práci s úlohami stochastického programování se často setkáváme s optimalizačními problémy, které jsou příliš rozsáhlé na to, aby byly zpracovány pomocí rutinních metod matematického programování. Nicméně, v některých případech mají tyto problémy vhodnou strukturu, umožňující použití specializovaných dekompozičních metod, které lze použít při řešení rozsáhlých optimalizačních problémů. Tato práce se zabývá dvěma třídami úloh stochastického programování, které mají speciální strukturu, a to dvoustupňovými stochastickými úlohami a úlohami s pravděpodobnostním omezením, a pokročilými dekompozičními metodami, které lze použít k řešení problému v těchto dvou třídách. V práci popisujeme novou metodu pro tvorbu “warm-start” řezů pro metodu zvanou “Generalized Benders Decomposition”, která se používá při řešení dvoustupňových stochastických problémů. Pro třídu úloh s pravděpodobnostním omezením zde uvádíme originální dekompoziční metodu, kterou jsme nazvali “Pool & Discard algoritmus”. Užitečnost popsaných dekompozičních metod je ukázána na několika příkladech a inženýrských aplikacích.

This thesis concerns the application of mixed-integer programming techniques to solve special classes of network flow problems and stochastic integer programs. We draw tools from complexity and polyhedral theory to analyze these problems and propose improved solution methods. In the first part, we consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are required to take values above a prespecified minimum threshold whenever they are not zero. These problems find applications in management and supply chain models where orders in small quantities are undesirable. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present complete descriptions of the convex hull in terms of linear inequalities and extended formulations. We also consider a class of semi-continuous transportation problems where inflow systems arise as substructures, for which we investigate complexity questions. Finally, we study the computational efficacy of the developed polyhedral results in solving randomly generated instances of semi-continuous transportation problems. In the second part, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of optimizing a linear function on the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem and finds applications in stochastic integer programming. We observe that the complexity of the problem depends on how P and X are specified. For instance, P can be explicitly given by its linear description, or implicitly by an oracle. Similarly, X can be explicitly given as a list of vectors, or implicitly as a face of P. While removing vertices turns to be hard in general, it is tractable for tractable 0-1 polytopes, and compact extended formulations can be obtained. Some extensions to integral polytopes are also presented. The third part is devoted to the integer L-shaped method for two-stage stochastic integer programs. A widely used model assumes that decisions are made in a two-step fashion, where first-stage decisions are followed by second-stage recourse actions after the uncertain parameters are observed, and we seek to minimize the expected overall cost. In the case of finitely many possible outcomes or scenarios, the integer L-shaped method proposes a decomposition scheme akin to Benders' decomposition for linear problems, but where a series of mixed-integer subproblems have to be solved at each iteration. To improve the performance of the method, we devise a simple modification that alternates between linear and mixed-integer subproblems, yielding significant time savings in instances from the literature. We also present a general framework to generate optimality cuts via a cut-generating problem. Using an extended formulation of the forbidden-vertices problem, we recast our cut-generating problem as a linear problem and embed it within the integer L-shaped method. Our numerical experiments suggest that this approach can prove beneficial when the first-stage set is relatively complicated.

Some oil and gas companies are drilling and developing fields in the Arctic Ocean, which has an environment with sea ice called ice floes. These companies must protect their platforms from ice floe collisions. One proposal is to use a system that consists of autonomous underwater vehicles (AUVs) and docking stations. The AUVs measure the under-water topography of the ice floes, while the docking stations launch the AUVs and recharge their batteries. Given resource constraints, we optimize quantities and locations for the docking stations and the AUVs, as well as the AUV scheduling policies, in order to provide the maximum protection level for the platform. We first use an queueing approach to model the problem as a queueing system with abandonments, with the objective to minimize the abandonment probability. Both M/M/k+M and M/G/k+G queueing approximations are applied and we also develop a detailed simulation model based on the queueing approximation. In a complementary approach, we model the system using a multi-stage stochastic facility location problem in order to optimize the docking station locations, the AUV allocations, and the scheduling policies of the AUVs. A two-stage stochastic facility location problem and several efficient online scheduling heuristics are developed to provide lower bounds and upper bounds for the multi-stage model, and also to solve large-scale instances of the optimization model. Even though the model is motivated by an oil industry project, most of the modeling and optimization methods apply more broadly to any radial detection problems with queueing dynamics. / text

Monte Carlo sampling-based methods are frequently used in stochastic programming when exact solution is not possible. In this dissertation, we develop two sets of Monte Carlo sampling-based algorithms to solve classes of two-stage stochastic programs. These algorithms follow a sequential framework such that a candidate solution is generated and evaluated at each step. If the solution is of desired quality, then the algorithm stops and outputs the candidate solution along with an approximate (1 - α) confidence interval on its optimality gap. The first set of algorithms proposed, which we refer to as the fixed-width sequential sampling methods, generate a candidate solution by solving a sampling approximation of the original problem. Using an independent sample, a confidence interval is built on the optimality gap of the candidate solution. The procedures stop when the confidence interval width plus an inflation factor falls below a pre-specified tolerance epsilon. We present two variants. The fully sequential procedures use deterministic, non-decreasing sample size schedules, whereas in another variant, the sample size at the next iteration is determined using current statistical estimates. We establish desired asymptotic properties and present computational results. In another set of sequential algorithms, we combine deterministically valid and sampling-based bounds. These algorithms, labeled sampling-based sequential approximation methods, take advantage of certain characteristics of the models such as convexity to generate candidate solutions and deterministic lower bounds through Jensen's inequality. A point estimate on the optimality gap is calculated by generating an upper bound through sampling. The procedure stops when the point estimate on the optimality gap falls below a fraction of its sample standard deviation. We show asymptotically that this algorithm finds a solution with a desired quality tolerance. We present variance reduction techniques and show their effectiveness through an empirical study.