We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsa...
详细信息
We consider stochastic programming problems with probabilistic constraints involving random variables with discrete distributions. They can be reformulated as large scale mixed integer programming problems with knapsack constraints. Using specific properties of stochastic programming problems and bounds on the probability of the union of events we develop new valid inequalities for these mixed integer programming problems. We also develop methods for lifting these inequalities. These procedures are used in a general iterative algorithm for solving probabilistically constrained problems. The results are illustrated with a numerical example.
作者：
Liu, BDTsinghua Univ
Dept Math Sci State Key Lab Intelligent Technol & Syst Beijing 100084 Peoples R China
A fuzzy random variable is a measurable function from a probability space to a collection of fuzzy sets, while a random fuzzy variable is a function from a collection of random variables to [0, 1]. This paper provides...
详细信息
A fuzzy random variable is a measurable function from a probability space to a collection of fuzzy sets, while a random fuzzy variable is a function from a collection of random variables to [0, 1]. This paper provides a spectrum of random fuzzy dependent-chance programming in which the underlying philosophy is based on selecting the decision with maximal chance to meet the event. In order to speed up the solution process, we train a neural network to approximate chance functions based on the training data generated by the random fuzzy simulation. Finally, we integrate random fuzzy simulation, neural network and genetic algorithm to produce a more powerful and effective hybrid intelligent algorithm for solving random fuzzy dependent-chance programming models, and illustrate its effectiveness by some numerical examples. (C) 2002 Elsevier Science Inc. All rights reserved.
We consider stochastic integer programming problems with probabilistic constraints. The concept of p-efficient points of a probability distribution is used to derive various equivalent problem formulations. Next we in...
详细信息
We consider stochastic integer programming problems with probabilistic constraints. The concept of p-efficient points of a probability distribution is used to derive various equivalent problem formulations. Next we introduce new methods for constructing lower and upper bounds for probabilistically constrained integer programs. We also show how limited information about the distribution can be used to construct such bounds. The concepts and methods are illustrated on an example of a vehicle routing problem. (C) 2002 Published by Elsevier Science B.V.
stochastic dynamic programming (SDP) models are widely used to predict optimal behavioural and life history strategies. We discuss a diversity of ways to test SDP models empirically, taking as our main illustration a ...
详细信息
stochastic dynamic programming (SDP) models are widely used to predict optimal behavioural and life history strategies. We discuss a diversity of ways to test SDP models empirically, taking as our main illustration a model of the daily singing routine of birds. One approach to verification is to quantify model parameters, but most SDP models are schematic. Because predictions are therefore qualitative, testing several predictions is desirable. How state determines behaviour (the policy) is a central prediction that should be examined directly if both state and behaviour are measurable. Complementary predictions concern how behaviour and state change through time, but information is discarded by considering behaviour rather than state, by looking only at average state rather than its distribution, and by not following individuals. We identify the various circumstances in which an individual's state/behaviour at one time is correlated with its state/behaviour at a later time. When there are several state variables,the relationships between them may be informative. Often model parameters represent environmental conditions that can also be viewed as state variables. Experimental manipulation of the environment has several advantages as a test, but a problem is uncertainty over how much the organism's policy will adjust. As an example we allow birds to use different assumptions about how well past weather predicts future weather. We advocate mirroring planned empirical investigations oh the computer to investigate which manipulations and predictions will best test a model. (C) 2000 The Association for the Study of Animal Behaviour.
This work addresses the problem of determining the optimal operating schedule that minimizes the operating cost in an energy-intensive air separation plant. The difficulty arises from the fact that the rate at which t...
详细信息
This work addresses the problem of determining the optimal operating schedule that minimizes the operating cost in an energy-intensive air separation plant. The difficulty arises from the fact that the rate at which the utility company supplies electricity to the plant is subject to high fluctuations. This creates a potential opportunity to reduce average operating costs by changing the operating mode and production rates depending on the power costs, However, constraints occur due to product distribution requirements and plant capabilities, The scheduling optimization problem is made more challenging because the power prices are only known for a portion of the desired optimization horizon. These challenges were addressed by developing an efficient two-stage stochastic programming approach. Extensive analysis was done which resulted in a MILP problem formulation that uses an ARIMA model to generate the necessary scenarios for future power prices. The proposed problem was solved by utilizing commercial software and has been successfully tested on real data.
This paper presents a multistage stochastic programming model for strategic capacity planning at a major US semiconductor manufacturer. Main sources of uncertainty in this multi-year planning problem include demand of...
详细信息
This paper presents a multistage stochastic programming model for strategic capacity planning at a major US semiconductor manufacturer. Main sources of uncertainty in this multi-year planning problem include demand of different technologies and capacity estimations for each fabrication (fab) facility. We test the model using real-world scenarios requiring the determination of capacity planning for 29 technology categories among five fab facilities. The objective of the model is to minimize the gaps between product demands and the capacity allocated to the technology specified by each product. We consider two different scenario-analysis constructs: first, an independent scenario structure where we assume no prior information and the model systematically enumerates possible states in each period. The states from one period to another are independent from each other. Second, we consider an arbitrary scenario construct, which allows the planner to sample/evaluate arbitrary multi-period scenarios that captures the dependency between periods. In both cases, a scenario is defined as a multi-period path from the root to a leaf in the scenario tree. We conduct intensive computational experiments on these models using real data supplied by the semiconductor manufacturer. The purpose of our experiments is two-fold: first to examine different degree of scenario aggregation and its effects on the independent model to achieve high-quality solution. Using this as a benchmark, we then compare the results from the arbitrary model and illustrate the different uses of the two scenario constructs. We show that the independent model allows a varying degree of scenario aggregation without significant prior information, while the arbitrary model allows planners to play out specific scenarios given prior information.
The rate of change in technology in the semiconductor industry has made the demand supply planning process extremely challenging for manufacturers. This problem is further exacerbated for tool procurement because the ...
详细信息
The rate of change in technology in the semiconductor industry has made the demand supply planning process extremely challenging for manufacturers. This problem is further exacerbated for tool procurement because the tools are made to order, very expensive and have a long lead time for delivery. In this paper, we present a scenario-based stochastic planning approach for tool procurement under uncertainty in demand and formulate the problem as a mixed integer program. Our results based on the data from a manufacturing line indicate that the heuristics for stochastic planning can significantly outperform deterministic planning.
In this paper, we modify Benders' decomposition method by using concepts from the Reformulation-Linearization Technique (RLT) and lift-and-project cuts in order to develop an approch for solving discrete optimizat...
详细信息
In this paper, we modify Benders' decomposition method by using concepts from the Reformulation-Linearization Technique (RLT) and lift-and-project cuts in order to develop an approch for solving discrete optimization problems that yield integral subproblems, such as those that arise in the case of two-stage stochastic programs with integer recourse. We first demonstrate that if a particular convex hull representation of the problem's constrained region is available when binariness is enforced on only the second-stage (or recourse) variables, then the regular Benders' algorithm is applicable. The proposed procedure is based on sequentially generating a suitable partial description of this convex hull representation as needed in the process of deriving valid Benders' cuts. The key idea is to solve the subproblems using an RLT or lift-and-project cutting plane scheme, but to generate and store the cuts as functions of the first-stage variables. Hence, we are able to re-use these cutting planes from one subproblem solution to the next simply by updating the values of the first-stage decisions. The proposed Benders' cuts also recognize these RLT or lift-and-project cuts as functions of the first-stage variables, and are hence shown to be globally valid, thereby leading to an overall finitely convergent solution procedure. Some illustrative examples are provided to elucidate the proposed approach. The focus of this paper is on developing such a finitely convergent Benders' approach for problems having 0-1 mixed-integer subproblems as in the aforementioned context of two-stage stochastic programs with integer recourse. A second part of this paper will deal with related computational experiments.
The purpose of this paper is to demonstrate how to evaluate stochastic programming models, and more specifically to compare two different approaches to asset liability management. The first uses multistage stochastic ...
详细信息
The purpose of this paper is to demonstrate how to evaluate stochastic programming models, and more specifically to compare two different approaches to asset liability management. The first uses multistage stochastic programming, while the other is a static approach based on the so-called constant rebalancing or fixed mix. Particular attention is paid to the methodology used for the comparison. The two alternatives are tested over a large number of realistic scenarios created by means of simulation. We find that due to the ability of the stochastic programming model to adapt to the information in the scenario tree, it dominates the fixed mix approach. (C) 2002 Elsevier Science B.V. All rights reserved.
This article constructs a foundation for warfare at the individual level, where agents in two groups fire and absorb shots according to a non-stationary Poisson process. We determine for generalized forms of warfare t...
详细信息
This article constructs a foundation for warfare at the individual level, where agents in two groups fire and absorb shots according to a non-stationary Poisson process. We determine for generalized forms of warfare the conditional and unconditional point probabilities of a certain number of agents in each group through time, and the conditional and unconditional expected sizes and variances. Conditional variables are especially useful in modern warfare since these allow for updated intelligence. We determine the conditions for discrepancies between the stochastic version and the associated Lanchester model. Correspondence is demonstrated for square warfare for large groups where the probability that a group goes extinct is negligible. For linear warfare equivalence occurs for the conditional case, whereas for the unconditional case correspondence arises at the limit where the covariance of the group sizes approaches zero. Finally the stochastic model is tested against newly released empirics for the Ardennes Campaign during World War II. (C) 2002 Elsevier Science B.V. All rights reserved.
暂无评论