Academic literature on the topic 'Two-stage stochastic programming problems'

Stochastic Programming is an asset for the next world researchers due to its uncertainty calculations, which has been skipped in deterministic world experiments as it includes complicated calculations. Two-stage stochastic programming concerns two time period decisions based on some random parameters obtained from past experience or some sort of survey. The objective function for formulating two-stage stochastic programming with fixed recourse includes two parts: first-stage forecast and second-stage fixed decisions based on the experiment results. The constraints are similar to the normal optimization techniques rather some adjustments of requirements and technology assets. The fixed recourse decisions are sort of decisions from the deterministic world. Formulation techniques of two-stage stochastic programming with fixed recourse may be used for further complications arises in stochastic programming like complete recourse problems, multi-stage problems, etc. And that’s why Two-stage stochastic programming with fixed recourse is called the primary model for stochastic programming.

Most of the real-life decision-making problems have more than one conflicting and incommensurable objective functions. In this paper, we present a multiobjective two-stage stochastic linear programming problem considering some parameters of the linear constraints as interval type discrete random variables with known probability distribution. Randomness of the discrete intervals are considered for the model parameters. Further, the concepts of best optimum and worst optimum solution are analyzed in two-stage stochastic programming. To solve the stated problem, first we remove the randomness of the problem and formulate an equivalent deterministic linear programming model with multiobjective interval coefficients. Then the deterministic multiobjective model is solved using weighting method, where we apply the solution procedure of interval linear programming technique. We obtain the upper and lower bound of the objective function as the best and the worst value, respectively. It highlights the possible risk involved in the decision-making tool. A numerical example is presented to demonstrate the proposed solution procedure.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>PROGRAMA DE SUPORTE À PÓS-GRADUAÇÃO DE INSTS. DE ENSINO<br>A parte mais difícil de modelar os problemas de tomada de decisão do mundo real, é a incerteza associada a realização de eventos futuros. A programação estocástica se encarrega desse assunto; o objetivo é achar soluções que sejam factíveis para todas as possíveis realizações dos dados, otimizando o valor esperado de algumas funções das variáveis de decisão e de incerteza. A abordagem mais estudada está baseada em simulação de Monte Carlo e o método SAA (Sample Average Appmwimation) o qual é uma formulação do problema verdadeiro para cada realização da data incerta, que pertence a um conjunto finito de cenários uniformemente distribuídos. É possível provar que o valor ótimo e a solução ótima do problema SAA converge a seus homólogos do problema verdadeiro quando o número de cenários é suficientemente grande.Embora essa abordagem seja útil ali existem fatores limitantes sobre o custo computacional para obter soluções mais precisas aumentando o número de cenários; no entanto o fato mais importante é que o problema SAA é função de cada amostra gerada e por essa razão é aleatório, o qual significa que a sua solução também é incerta, e para medir essa incerteza e necessário considerar o número de replicações do problema SAA afim de estimar a dispersão da solução, aumentando assim o custo computacional. O propósito deste trabalho é apresentar uma abordagem alternativa baseada em um método de partição que permite obter cotas para estimar deterministicamente a solução do problema original, com aplicação da desigualdade de Jensen e de técnicas de otimização robusta. No final se analisa a convergência dos algoritmos de solução propostos.<br>The hardest part of modelling decision-making problems in the real world, is the uncertainty associated to realizations of futures events. The stochastic programming is responsible about this subject; the target is finding solutions that are feasible for all possible realizations of the unknown data, optimizing the expected value of some functions of decision variables and random variables. The approach most studied is based on Monte Carlo simulation and the Sample Average Approximation (SAA) method which is a kind of discretization of expected value, considering a nite set of realizations or scenarios uniformly distributed. It is possible to prove that the optimal value and the optimal solution of the SAA problem converge to their counterparts of the true problem when the number of scenarios is sufficiently big. Although that approach is useful, there exist limiting factors about the computational cost to increase the scenarios number to obtain a better solution; but the most important fact is that SAA problem is function of each sample generated, and for that reason is random, which means that the solution is also uncertain, and to measure its uncertainty it is necessary consider the replications of SAA problem to estimate the dispersion of the estimated solution, increasing even more the computational cost. The purpose of this work is presenting an alternative approach based on robust optimization techniques and applications of Jensen s inequality, to obtain bounds for the optimal solution, partitioning the support of distribution (without scenarios creation) of unknown data, and taking advantage of the convexity. At the end of this work the convergence of the bounding problem and the proposed solution algorithms are analyzed.

Stochastic programming is an optimization technique that incorporates random variables as parameters. Because it better reflects the uncertain real world than its traditional deterministic counterpart, stochastic programming has drawn increasingly more attention among decision-makers, and its applications span many fields including financial engineering, health care, communication systems, and supply chain management. On the flip side, stochastic programs are usually very difficult to solve, which is further compounded by the fact that in many of the aforementioned applications, we also have discrete decisions, thereby rendering these problems even more challenging. In this dissertation, we study the class of two-stage stochastic mixed-integer programs (SMIP), which, as its name suggests, lies at the confluence of two formidable classes of problems. We design a novel algorithm for this class of problems, and also explore specialized approaches for two related real-world applications. Although a number of algorithms have been developed to solve two-stage SMIPs, most of them deal with problems containing purely integer or continuous variables in either or both of the two stages, and frequently require the technology and/or recourse matrices to be deterministic. As a ground-breaking effort, in this work, we address the challenging class of two-stage SMIPs that involve 0-1 mixed-integer variables in both stages. The only earlier work on solving such problems (Car&#248;e and Schultz (1999)) requires the optimization of several non-smooth Lagrangian dual problems using subgradient methods in the bounding process, which turns out to be computationally very expensive. We begin with proposing a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having 0-1 mixed-integer variables in both stages. Since the second-stage problems contain binary variables, their value functions are in general nonconvex and discontinuous; hence, the classical Benders' decomposition approach (or the L-shaped method) for solving two-stage stochastic programs, which requires convex subproblem value functions, cannot be directly applied. This motivates us to relax the second-stage problems and accompany this relaxation with a convexification process. To make this process computationally efficient, we propose to construct a certain partial convex hull representation of the two-stage solution space, using the relaxed second-stage constraints and the restrictions confining the first-stage variables to lie within some hyperrectangle. This partial convex hull is sequentially generated using a convexification scheme, such as the Reformulation-Linearization Technique (RLT), which yields valid inequalities that are functions of the first-stage variables and, of noteworthy importance, are reusable in the subsequent subproblems by updating the values of the first-stage variables. Meanwhile, since the first stage contains continuous variables, whenever we tentatively fix these variables at some given feasible values, the resulting constraints may not be facial with respect to the associated bounding constraints that are used to construct the partial convex hull. As a result, the constructed Benders' subproblems define lower bounds for the second-stage value functions, and likewise, the resulting Benders' master problem provides a lower bound for the original stochastic program defined over the same hyperrectangle. Another difficulty resulting from continuous first-stage variables is that when the given first-stage solution is not extremal with respect to its bounds, the second-stage solution obtained for a Benders' subproblem defined with respect to a partial convex hull representation in the two-stage space may not satisfy the model's binary restrictions. We thus need to be able to detect whether or not a Benders' subproblem is solved by a given fractional second-stage solution. We design a novel procedure to check this situation in the overall algorithmic scheme. A key property established, which ensures global convergence, is that these lower bounds become exact if the given first-stage solution is a vertex of the defining hyperrectangle, or if the second-stage solution satisfies the binary restrictions. Based on these algorithmic constructs, we design a branch-and-bound procedure where the branching process performs a hyperrectangular partitioning of the projected space of the first-stage variables, and lower bounds for the nodal problems are computed by applying the proposed modified Benders' decomposition method. We prove that, when using the least-lower-bound node-selection rule, this algorithm converges to a global optimal solution. We also show that the derived RLT cuts are not only reusable in subsequent Benders iterations at the same node, but are also inheritable by the subproblems of the children nodes. Likewise, the Benders' cuts derived for a given sub-hyperrectangle can also be inherited by the lower bounding master programs solved for its children nodes. Using these cut inheritance properties results in significant savings in the overall computational effort. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach. The sizes of the deterministic equivalent of our test problems range from having 386 continuous variables, 386 binary variables, and 386 constraints, up to 1795 continuous variables, 1539 binary variables, and 1028 constraints. The results reveal an average savings in computational effort by a factor of 9.5 in comparison with using a commercial mixed-integer programming package (CPLEX 8.1) on a deterministic equivalent formulation. We then explore an important application of SMIP to enhance the traditional airline fleet assignment models (FAM). Given a flight schedule network, the fleet assignment problem solved by airline companies is concerned with assigning aircraft to flight legs in order to maximize profit with respect to captured path- or itinerary-based demand. Because certain related crew scheduling regulations require early information regarding the type of aircraft serving each flight leg, the current practice adopted by airlines is to solve the fleet assignment problem using estimated demand data 10-12 weeks in advance of departure. Given the level of uncertainty, deterministic models at this early stage are inadequate to obtain a good match of aircraft capacity with passenger demands, and revisions to the initial fleet assignment become naturally pertinent when the observed demand differs considerably from the assigned aircraft capacities. From this viewpoint, the initial decision should embrace various market scenarios so that it incorporates a sufficient look-ahead feature and provides sufficient flexibility for the subsequent re-fleeting processes to accommodate the inevitable demand fluctuations. With this motivation, we propose a two-stage stochastic programming approach in which the first stage is concerned with the initial fleet assignment decisions and, unlike the traditional deterministic methodology, focuses on making only a family-level assignment to each flight leg. The second stage subsequently performs the detailed assignments of fleet types within the allotted family to each leg under each of the multiple potential scenarios that address corresponding path- or itinerary-based demands. In this fashion, the initial decision of what aircraft family should serve each flight leg accomplishes the purpose of facilitating the necessary crew scheduling decisions, while judiciously examining the outcome of future re-fleeting actions based on different possible demand scenarios. Hence, when the actual re-fleeting process is enacted several weeks later, this anticipatory initial family-level assignment will hopefully provide an improved overall fleet type re-allocation that better matches demand. This two-stage stochastic model is complemented with a secondary model that performs adjustments within each family, if necessary, to provide a consistent fleet type-assignment information for accompanying decision processes, such as yield management. We also propose several enhanced fleet assignment models, including a robust optimization model that controls decision variation among scenarios and a stochastic programming model that considers the recapture effect of spilled demand. In addition to the above modeling concepts and framework, we also contribute in developing effective solution approaches for the proposed model, which is a large-scale two-stage stochastic 0-1 mixed-integer program. Because the most pertinent information needed from the initial fleet assignment is at the family level, and the type-level assignment is subject to change at the re-fleeting stage according to future demand realizations, our solution approach focuses on assigning aircraft families to the different legs in the flight network at the first stage, while finding relaxed second-stage solutions under different demand scenarios. Based on a polyhedral study of a subsystem extracted from the original model, we derive certain higher-dimensional convex hull as well as partial convex hull representations for this subsystem. Accordingly, we propose two variants for the primary model, both of which relax the binary restrictions on the second-stage variables, but where the second variant then also accommodates the partial convex hull representations, yielding a tighter, albeit larger, relaxation. For each variant, we design a suitable solution approach predicated on Benders' decomposition methodology. Using certain realistic large-scale flight network test problems having 900 flight legs and 1,814 paths, as obtained from United Airlines, the proposed stochastic modeling approach was demonstrated to increase daily expected profits by about 3% (which translates to about $160 million per year) in comparison with the traditional deterministic model in present usage, which considers only the expected demand. Only 1.6% of the second-stage binary variables turn out to be fractional in the first variant, and this number is further reduced to 1.2% by using the tighter variant. Furthermore, when attempting to solve the deterministic equivalent formulation for these two variants using a commercial mixed-integer programming package (CPLEX 8.1), both the corresponding runs were terminated after reaching a 25-hour cpu time limit. At termination, the software was still processing the initial LP relaxation at the root node for each of these runs, and no feasible basis was found. Using the proposed algorithms, on the other hand, the solution times were significantly reduced to 5 and 19 hours for the two variants, respectively. Considering that the fleet assignment models are solved around three months in advance of departure, this solution time is well acceptable at this early planning stage, and the improved quality in the solution produced by considering the stochasticity in the system is indeed highly desirable. Finally, we address another practical workforce planning problem encountered by a global financial firm that seeks to manage multi-category workforce for functional areas located at different service centers, each having office-space and recruitment-capacity constraints. The workforce demand fluctuates over time due to market uncertainty and dynamic project requirements. To hedge against the demand fluctuations and the inherent uncertainty, we propose a two-stage stochastic programming model where the first stage makes personnel recruiting and allocation decisions, while the second stage, based on the given personnel decision and realized workforce demand, decides on the project implementation assignment. The second stage of the proposed model contains binary variables that are used to compute and also limit the number of changes to the original plan. Since these variables are concerned with only one quality aspect of the resulting workforce plan and do not affect feasibility issues, we replace these binary variables with certain conservative policies regarding workforce assignment change restrictions in order to obtain more manageable subproblems that contain purely continuous variables. Numerical experiments reveal that the stochastic programming approach results in significantly fewer alterations to the original workforce plan. When using a commercial linear programming package CPLEX 9.0 to solve the deterministic equivalent form directly, except for a few small-sized problems, this software failed to produce solutions due to memory limitations, while the proposed Benders' decomposition-based solution approach consistently solved all the practical-sized test problems with reasonable effort. To summarize, this dissertation provides a significant advancement in the algorithmic development for solving two-stage stochastic mixed-integer programs having 0-1 mixed-integer variables in both stages, as well as in its application to two important contemporary real-world applications. The framework for the proposed solution approaches is to formulate tighter relaxations via partial convex hull representations and to exploit the resulting structure using suitable decomposition methods. As decision robustness is becoming increasingly relevant from an economic viewpoint, and as computer technological advances provide decision-makers the ability to explore a wide variety of scenarios, we hope that the proposed algorithms will have a notable positive impact on solving stochastic mixed-integer programs. In particular, the proposed stochastic programming airline fleet assignment and the workforce planning approaches studied herein are well-poised to enhance the profitability and robustness of decisions made in the related industries, and we hope that similar improvements are adapted by more industries where decisions need to be made in the light of data that is shrouded by uncertainty.<br>Ph. D.

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.

Algorithmic Framework for Improving Heuristics in Stochastic, Stage-Wise Optimization Problems Jaein Choi 172 Pages Directed by Dr. Jay H. Lee and Dr. Matthew J. Realff The goal of this thesis is the development of a computationally tractable solution method for stochastic, stage-wise optimization problems. In order to achieve the goal, we have developed a novel algorithmic framework based on Dynamic Programming (DP) for improving heuristics. The propose method represents a systematic way to take a family of solutions and patch them together as an improved solution. However, patching is accomplished in state space, rather than in solution space. Since the proposed approach utilizes simulation with heuristics to circumvent the curse of dimensionality of the DP, it is named as Dynamic Programming in Heuristically Restricted State Space. The proposed algorithmic framework is applied to stochastic Resource Constrained Project Scheduling problems, a real-world optimization problem with a high dimensional state space and significant uncertainty equivalent to billions of scenarios. The real-time decision making policy obtained by the proposed approach outperforms the best heuristic applied in simulation stage to form the policy. The proposed approach is extended with the idea of Q-Learning technique, which enables us to build empirical state transition rules through simulation, for stochastic optimization problems with complicated state transition rules. Furthermore, the proposed framework is applied to a stochastic supply chain management problem, which has high dimensional action space as well as high dimensional state space, with a novel concept of implicit sub-action space that efficiently restricts action space for each state in the restricted state space. The resulting real-time policy responds to the time varying demand for products by stitching together decisions made by the heuristics and improves overall performance of the supply chain. The proposed approach can be applied to any problem formulated as a stochastic DP, provided that there are reasonable heuristics available for simulation.

Optimalizace toku v síti je klasickou aplikací matematického programování. Tyto modely mají, mimo jiné, široké uplatnění také v logistice, kde se tak snažíme docílit optimálního rozdělení dopravy, např. vzhledem k maximalizaci zisku, či minimalizaci nákladů. Toto pojetí ovšem často problém idealizuje, poněvadž předpokládá existenci jediného rozhodovatele. Takový přístup je možný ve striktně organizovaných sítích jako např. v logistických sítích přepravních společností, železničních sítích či armádním zásobování. Úloha ''Traffic Assignment Problem'' (TAP) se zaměřuje na dopady teorie her na optimalizaci toku, tj. zkoumá vliv více rozhodovatelů na celkové využití sítě. V práci se zaobíráme úlohou TAP s působením náhodných vlivů, k čemuž využíváme metod stochastické a vícestupňové optimalizace. Dále zkoumáme možnosti zlepšení stávajícího využití sítě za rozhodnutí autoritativního rozhodovatele, kterému je umožněn zásah do samotné struktury sítě, k čemuž využíváme víceúrovňové programování.

Stochastic linear programming problems are linear programming problems for which one or more data elements are described by random variables. Two-stage stochastic linear programming problems are problems in which a first stage decision is made before the random variables are observed. A second stage, or recourse decision, which varies with these observations compensates for any deficiencies which result from the earlier decision. Many applications areas including water resources, industrial management, economics and finance lead to two-stage stochastic linear programs with recourse. In this dissertation, two algorithms for solving stochastic linear programming problems with recourse are developed and tested. The first is referred to as Quadratic Stochastic Decomposition (QSD). This algorithm is an enhanced version of the Stochastic Decomposition (SD) algorithm of Higle and Sen (1988). The enhancements were designed to increase the computational efficiency of the SD algorithm by introducing a quadratic proximal term in the master program objective function and altering the manner in which the recourse function approximations are updated. We show that every accumulation point of an easily identifiable subsequence of points generated by the algorithm are optimal solutions to the stochastic program with probability 1. The various combinations of the enhancements are empirically investigated in a computational experiment using operations research problems from the literature. The second algorithm is an SD based algorithm for solving a stochastic linear program in which the recourse problem appears in the constraint set. This algorithm involves the use of an exact penalty function in the master program. We find that under certain conditions every accumulation point of a sequence of points generated by the algorithm is an optimal solution to the recourse constrained stochastic program, with probability 1. This algorithm is tested on several operations research problems.

The master’s thesis focuses on the optimization models in logistics with emphasis on the network interdiction problem. The brief introduction is followed by two overview chapters - graph theory and mathematical programming. Important definitions strongly related to network interdiction problems are introduced in the chapter named Basic concepts of graph theory. Necessary theorems used for solving problems are following the definitions. Next chapter named Introduction to mathematical programming firstly contains concepts from linear programming. Definitions and theorems are chosen with respect to the following maximum flow problem and the derived dual problem. Concepts of stochastic optimization follow. In the fifth chapter, we discuss deterministic models of the network interdiction. Stochastic models of the network interdiction follow in the next chapter. All models are implemented in programmes written in the programming language GAMS, the codes are attached.

Two-stage stochastic programming problem with PDE constraint, specially elliptic equation is formulated. The computational scheme is proposed, whereas the emphasis is put on approximation techniques. We introduce method of approximation of random variables of stochastic problem and utilize suitable numerical methods, finite difference method first, then finite element method. There is also formulated a mathematical programming problem describing a membrane deflection with random load. It is followed by determination of the acceptableness of using stochastic optimization rather than deterministic problem and assess the quality of approximations based on Monte Carlo simulation method and the theory of interval estimates. The resulting mathematical models are implemented and solved in the general algebraic modeling system GAMS. Graphical and numerical results are presented.

We present a rigorous but understandable introduction to the field of sampling theory for ecologists and natural resource scientists. Sampling theory concerns itself with development of procedures for random selection of a subset of units, a sample, from a larger finite population, and with how to best use sample data to make scientifically and statistically sound inferences about the population as a whole. The inferences fall into two broad categories: (a) estimation of simple descriptive population parameters, such as means, totals, or proportions, for variables of interest, and (b) estimation of uncertainty associated with estimated parameter values. Although the targets of estimation are few and simple, estimates of means, totals, or proportions see important and often controversial uses in management of natural resources and in fundamental ecological research, but few ecologists or natural resource scientists have formal training in sampling theory. We emphasize the classical design-based approach to sampling in which variable values associated with units are regarded as fixed and uncertainty of estimation arises via various randomization strategies that may be used to select samples. In addition to covering standard topics such as simple random, systematic, cluster, unequal probability (stressing the generality of Horvitz–Thompson estimation), multi-stage, and multi-phase sampling, we also consider adaptive sampling, spatially balanced sampling, and sampling through time, three areas of special importance for ecologists and natural resource scientists. The text is directed to undergraduate seniors, graduate students, and practicing professionals. Problems emphasize application of the theory and R programming in ecological and natural resource settings.

Multistage stochastic programs, which involve sequences of decisions over time, are usually hard to solve in realistically sized problems. Providing bounds for their optimal solution may help in evaluating whether it is worth the additional computations for the stochastic program versus simplified approaches. In this paper we present a summary of the results in [22] where we generalize the value of information gained from deterministic, pair solution and rolling-horizon approximation in the two-stage case to the multistage stochastic formulation. Numerical results on a case study related to a simple transportation problem illustrate the described relationships.

Complex multi-stage decision making problems often involve uncertainty, for example, regarding demand or processing times. Stochastic constraint programming was proposed as a way to formulate and solve such decision problems, involving arbitrary constraints over both decision and random variables. What stochastic constraint programming still lacks is support for the use of factorized probabilistic models that are popular in the graphical model community. We show how a state-of-the-art probabilistic inference engine can be integrated into standard constraint solvers. The resulting approach searches over the And-Or search tree directly, and we investigate tight bounds on the expected utility objective. This significantly improves search efficiency and outperforms scenario-based methods that ground out the possible worlds.

Abstract In a competitive and volatile market, the price is needed to make in consideration of the uncertain demands of the customers and the limited capacities of enterprises. This requires the coordination decisions on pricing, delivery and resource allocation to increase profit and guarantee service quality for firms. The joint decision on pricing and resource allocation with demand and processing time uncertainty is becoming an issue for a profit-maximizing firm that produces various products. We propose a two-stage model based on stochastic programming to address this joint problem, aiming to maximize profit of products. We present a scenario-simulation approach to describe the stochastic variables; then the deterministic two-stage mixed integer linear programming model is formulated depending on those scenarios. We develop an algorithm by ant colony algorithm to obtain the near-optimal solutions of the models above. The numerical experiments were conducted to validate the proposed models. The results show that the stochastic approach outperforms the deterministic model in the different problem scales and yield the better values of compared metrics. The outcomes also imply that this joint pricing model can provide managerial inspiration for enterprises in the customization environment.