We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two al...
详细信息
We consider two-stage pure integer programs with discretely distributed stochastic right-hand sides. We present an equivalent superadditive dual formulation that uses the value functions in both stages. We give two algorithms for finding the value functions. To solve the reformulation after obtaining the value functions, we develop a global branch-and-bound approach and a level-set approach to find an optimal tender. We show that our method can solve randomly generated instances whose extensive forms are several orders of magnitude larger than the extensive forms of those instances found in the literature.
In this paper we derive estimates of the sample size required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented...
详细信息
In this paper we derive estimates of the sample size required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self-contained and is based on a relatively elementary, one-dimensional, Cramer's Large Deviations Theorem. (c) 2005 Elsevier B.V. All rights reserved.
The supervisor and searcher cooperation framework (SSC), introduced in Refs. 1 and 2, provides an effective way to design efficient optimization algorithms combining the desirable features of the two existing ones. Th...
详细信息
The supervisor and searcher cooperation framework (SSC), introduced in Refs. 1 and 2, provides an effective way to design efficient optimization algorithms combining the desirable features of the two existing ones. This work aims to develop efficient algorithms for a wide range of noisy optimization problems including those posed by feedforward neural networks training. It introduces two basic SSC algorithms. The first seems suited for generic problems. The second is motivated by neural networks training problems. It introduces also inexact variants of the two algorithms, which seem to possess desirable properties. It establishes general theoretical results about the convergence and speed of SSC algorithms and illustrates their appealing attributes through numerical tests on deterministic, stochastic, and neural networks training problems.
We introduce the two-stage stochastic maximum-weight matching problem and demonstrate that this problem is NP-complete. We give a factor 1/2 approximation algorithm and prove its correctness. We also provide a tight e...
详细信息
We introduce the two-stage stochastic maximum-weight matching problem and demonstrate that this problem is NP-complete. We give a factor 1/2 approximation algorithm and prove its correctness. We also provide a tight example to show the bound given by the algorithm is exactly 1/2. Computational results on some two-stage stochastic bipartite matching instances indicate that the performance of the approximation algorithm appears to be substantially better than its worst-case performance. (c) 2004 Elsevier B.V. All rights reserved.
We consider optimization problems with second order stochastic dominance constraints formulated as a relation of Lorenz curves. We characterize the relation in terms of rank dependent utility functions, which generali...
详细信息
We consider optimization problems with second order stochastic dominance constraints formulated as a relation of Lorenz curves. We characterize the relation in terms of rank dependent utility functions, which generalize Yaari's utility functions. We develop optimality conditions and duality theory for problems with Lorenz dominance constraints. We prove that Lagrange multipliers associated with these constraints can be identified with rank dependent utility functions. The problem is numerically tractable in the case of discrete distributions with equally probable realizations.
Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criterion. A common approach to addressing risk in decision making problems is to consider a...
详细信息
Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criterion. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk objective, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various mean-risk objective functions in addressing risk in stochastic programming models. We prove that the classical mean-variance criterion leads to computational intractability even in the simplest stochastic programs. On the other hand, a number of alternative mean-risk functions are shown to be computationally tractable using slight variants of existing stochastic programming decomposition algorithms. We propose decomposition-based parametric cutting plane algorithms to generate mean-risk efficient frontiers for two particular classes of mean-risk objectives.
The 'Hungarian inventory control model' was initiated by Prekopa [1965. Reliability equation for an inventory problem and its asymptotic solutions. In: Prekopa, A. (Ed.), Application of the Mathematics to Econ...
详细信息
The 'Hungarian inventory control model' was initiated by Prekopa [1965. Reliability equation for an inventory problem and its asymptotic solutions. In: Prekopa, A. (Ed.), Application of the Mathematics to Economics. Publication House of the Hungarian Academy of Science, pp. 317-327] and Ziermann [1964. Application of Smirnov's theorems for an inventory control problem. Publications of the Mathematical Institute of the Hungarian Academy of Science Series B 8, 509-518 (in Hungarian)], where the ordered amount is delivered in an interval, rather than at a time epoch according to some stochastic process and consumption takes place in the same interval. The problem is to determine the minimum level of initial safety stock that ensures continuous consumption, without disruption, in the whole time interval with a prescribed high probability. Prekopa [2006. On the Hungarian inventory control model. European Journal of Operational Research 171, 894-914] has formulated a two-stage model with such interval type processes and probabilistic constraints. In this paper we modify the assumptions of those models and formulate simpler, numerically more tractable models. We also present numerical examples. (c) 2006 Published by Elsevier B.V.
When electricity prices were regulated, hydropower optimization often considered only the inflow uncertainty. In a deregulated electricity market, price uncertainty must be also considered in addition to inflow uncert...
详细信息
When electricity prices were regulated, hydropower optimization often considered only the inflow uncertainty. In a deregulated electricity market, price uncertainty must be also considered in addition to inflow uncertainty. This makes the operation problem more challenging due to inclusion of the objective of minimizing risk. It also makes the objective function nonlinear while the estimation of risk is problematic. For dealing with uncertainty, a set of finite scenarios of inflow or price sequences may form the evolution of information over the stages that are used in optimization algorithms. Such implicit optimization methods can be seen as an extension of deterministic optimization. A disadvantage is the number of scenarios may grow exponentially in multi-stage optimization problems, even with only a few branches at each stage. An explicit method, denoted as the Fletcher-Ponnambalam model (FP), has been recently developed tor the first and second moments of the storage state distributions in terms of moments of the inflow distributions. This method provides statistical information on the nature of random behaviour of the system state variables without any discretization and hence suitable for multireservoir problems. Also not considering scenarios makes it computationally inexpensive, as there is little growth to the size of the original problem. In this paper, we introduce the price uncertainty into the FP model;our results indicate that the method could achieve optimum policy considering also the reduction of risk, using the second moment information. Our study is for medium term operations of a single reservoir. The results are compared with corresponding results from simulation and where possible, with the well-known Benders' Decomposition method (BD).
In [Euro. J. Operat. Res. 143 (2002) 452;Opt. Meth. Software 17 (2002) 383] a Riccati-based primal interior point method for multistage stochastic programmes was developed. This algorithm has several interesting featu...
详细信息
In [Euro. J. Operat. Res. 143 (2002) 452;Opt. Meth. Software 17 (2002) 383] a Riccati-based primal interior point method for multistage stochastic programmes was developed. This algorithm has several interesting features. It can solve problems with a nonlinear node-sepatable convex objective, local linear constraints and global linear constraints. This paper demonstrates that the algorithm can be efficiently parallelized. The solution procedure in the algorithm allows for a simple but efficient method to distribute the computations. The parallel algorithm has been implemented on a low-budget parallel computer, where we experience almost perfect linear speedup and very good scalability of the algorithm. (C) 2003 Elsevier Science B.V. All rights reserved.
We consider a chance constrained problem, where one seeks to minimize a convex objective over solutions satisfying, with a given close to one probability, a system of randomly perturbed convex constraints. This proble...
详细信息
We consider a chance constrained problem, where one seeks to minimize a convex objective over solutions satisfying, with a given close to one probability, a system of randomly perturbed convex constraints. This problem may happen to be computationally intractable;our goal is to build its computationally tractable approximation, i.e., an efficiently solvable deterministic optimization program with the feasible set contained in the chance constrained problem. We construct a general class of such convex conservative approximations of the corresponding chance constrained problem. Moreover, under the assumptions that the constraints are a. ne in the perturbations and the entries in the perturbation vector are independent-of-each-other random variables, we build a large deviation-type approximation, referred to as "Bernstein approximation," of the chance constrained problem. This approximation is convex and efficiently solvable. We propose a simulation-based scheme for bounding the optimal value in the chance constrained problem and report numerical experiments aimed at comparing the Bernstein and well-known scenario approximation approaches. Finally, we extend our construction to the case of ambiguous chance constrained problems, where the random perturbations are independent with the collection of distributions known to belong to a given convex compact set rather than to be known exactly, while the chance constraint should be satisfied for every distribution given by this set.
暂无评论