Volume 2004
Permanent URI for this collectionhttp://edoc.hu-berlin.de/18452/361
Browse
Recent Submissions
Publication 2004-12-27BuchOn the Fortet-Mourier metric for the stability of Stochastic Optimization Problems, an exampleStrugarek, Cyrille; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe consider the use of the Fortet-Mourier metric between two probability measures to bound the error term made by an approximated solution of a stochastic program. After a short analysis of usual stability arguments, we propose a simple example of stochastic program which enlightens the importance of the information structure. As a conclusion, we underline the need to take into account both the probability measure and the information structure in the discretization of a stochastic program.Publication 2004-10-02BuchTwo-stage integer programs with stochastic right-hand sidesKong, Nan; Schaefer, Andrew J.; Hunsaker, Brady; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe 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 that are several orders of magnitude larger than those found in the literature.Publication 2004-10-02BuchA class of stochastic programs with decision dependent uncertaintyGoel, Vikas; Grossmann, Ignacio E.; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetThe standard approach to formulating stochastic programs is based on the assumption that the stochastic process is independent of the optimization decision. We address a class of problems where the optimization decisions influence the time of information discovery for a subset of the uncertain parameters. We extentd the standard modeling approach by presenting a disjunctive programming formulation that accommodates stochastic programs for this class of ploblems. A set of theoretical properties that lead to reduction in the size of the model is identified. A Lagrange duality based branch and bound algorithm is also presented.Publication 2004-10-02BuchVariance reduction in sample approximations of stochastic programsKoivu, Matti; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetThis paper studies the use of randomized Quasi-Monte Carlo methods (RQMC) in sample approximations of stochastic programs. In high dimensional numerical integration, RQMC methods often substantially reduce the variance of sample approximations compared to MC. It seems thus natural to use RQMC methods in sample approximations of stochastic programs. It is shown, that RQMC methods produce epi-convergent approximations of the original problem. RQMC and MC methods are compared numerically in five different portfolio management models. In the tests, RQMC methods outperform MC sampling substantially reducing the sample variance and bias of optimal values in all the considered problems.Publication 2004-09-13BuchOn deviation measures in stochastic integer programmingMärkert, Andreas; Schultz, Rüdiger; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe propose extensions of traditional expectation-based stochastic integer programs to mean-risk models. Risk is measured by expected deviations of suitable random variables from their means or from preselected targets. We derive structural properties of the resulting stochastic programs and present first algorithmic ideas to achieve problem decomposition.Publication 2004-09-13BuchConditional value-at-risk in stochastic programs with mixed-integer recourseSchultz, Rüdiger; Tiedemann, Stephan; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetIn classical two-stage stochastic programming the expected value of the total costs is minimized. Recently, mean-risk models -- studied in mathematical finance for several decades -- have attracted attention in stochastic programming. We consider Conditional Value-at-Risk as risk measures in the framework of two-stage stochastic integer programming. The paper addresses structure, stability, and algorithms for this class of models. In particular, we study continuity properties of the objective function, both with respect to the first-stage decisions and the integrating probability measure. Further, we present an explicit mixed-integer linear programming formulation of the problem when the probability distribution is discrete and finite. Finally, a solution algorithm based on Lagrangean relaxation of nonanticipativity is proposed.Publication 2004-06-15BuchTreasury management model with foreign exchange exposureVolosov, Konstantin; Mitra, Gautam; Spagnolo, Fabio; Lucas, Cormac; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetIn this paper we formulate a model for foreign exchange exposure management and (international) cash management taking into consideration random fluctuations of exchange rates. A vector error correction model (VECM) is used to predict the random behaviour of the forward as well as spot rates connecting dollar and sterling. A twostage stochastic programming (TWOSP) decision model is formulated using these random parameter values. This model computes currency hedging strategies, which provide rolling decisions of how much forward contracts should be bought and how much should be liquidated. The model decisions are investigated through ex post simulation and backtesting in which value at risk (VaR) for alternative decisions are computed. The investigation (a) shows that there is a considerable improvement to "spot only" strategy, (b) provides insight into how these decisions are made and (c) also validates the performance of this model.Publication 2004-06-05BuchPolyhedral inclusion-exclusionBukszar, Jozsef; Henrion, René; Hujter, Mihaly; Szantai, Tamas; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetMotivated by numerical computations to solve probabilistic constrained stochastic programming problems, we derive a new identity claiming that many terms are cancelled out in the inclusion-exclusion formula expressing the complement of a Euclidean polyhedron.Publication 2004-05-21BuchArbitrage pricing of American contingent claims in incomplete markets - a convex optimization approachPennanen, Teemu; King, Alan J.; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetConvex optimization provides a natural framework for pricing and hedging financial instruments in incomplete market models. Duality theory of convex optimization has been shown to yield elementary proofs of well-known martingale-expressions for prices of European contingent claims. This paper extends the analysis to American contingent claims in incomplete markets. The pricing problems of the seller and the buyer of an American contingent claim are first expressed as convex optimization problems, after which martingale-expressions for the buyer's and seller's prices are obtained by inspecting the dual optimization problems. Besides its simplicity, one of the main advantages of the present approach is that it is computational. Indeed, many algorithms are available for pricing problems as soon as they are set up as convex optimization problems. Also, portfolio constraints and transaction costs can be immediately incorporated to the definitions of the buyer's and seller's prices and into computational approaches based on optimization.Publication 2004-05-17BuchA stochastic programming approach to resource-constrained assignment problemsToktas, Berkin; Yen, Joyce W.; Zabinsky, Zelda B.; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe address the resource-constrained generalizations of the assignment problem with uncertain resource capacities, where the resource capacities have an unknown distribution that can be sampled. We propose three stochastic programming-based formulations that can be used to solve this problem, and provide exact and approximate solution techniques for the resulting models. We also present numerical results for a large set of numerical problems. The results indicate that the solutions obtained using the stochastic programming approaches perform significantly better than those obtained using expected values of capacities in a deterministic solution strategy. In addition, stochastic-programming-based approximations are computationally as efficient as deterministic techniques.Publication 2004-05-17BuchAssessing policy quality in multi-stage stochastic programmingChiralaksanakul, Anukal; Morton, David P.; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetSolving a multi-stage stochastic program with a large number of scenarios and a moderate-to-large number of stages can be computationally challenging. We develop two Monte Carlo-based methods that exploit special structures to generate feasible policies. To establish the quality of a given policy, we employ a Monte Carlo-based lower bound (for minimization problems) and use it to construct a confidence interval on the policy's optimality gap. The confidence interval can be formed in a number of ways depending on how the expected solution value of the policy is estimated and combined with the lower-bound estimator. Computational results suggest that a confidence interval formed by a tree-based gap estimator may be an effective method for assessing policy quality. Variance reduction is achieved by using common random numbers in the gap estimator.Publication 2004-04-20BuchDecomposition-based interior point methods for two-stage stochastic convex quadratic programs with recourseMehrotra, Sanjay; Ozevin, M. Gokhan; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetZhao [28] recently showed that the log barrier associated with the recourse function of two-stage stochastic linear programs behaves as a strongly self-concordant barrier and forms a self concordant family on the first stage solutions. In this paper we show that the recourse function is also strongly self-concordant and forms a self concordant family for the two-stage stochastic convex quadratic programs with recourse. This allows us to develop Benders decomposition based linearly convergent interior point algorithms. An analysis of such an algorithm is given in this paper.[28] G. Zhao: A log-barrier method with Benders decomposition for solving two-stage stochastic linear programs, Mathematical Programming Ser. A 90, (2001) 507-536.Publication 2004-04-16BuchMean-risk objectives in stochastic programmingAhmed, Shabbir; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetTraditional 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 a parametric cutting plane algorithm to generate the entire mean-risk efficient frontier for a particular mean-risk objective.Publication 2004-03-25BuchConditional Risk MappingsRuszczynski, Andrzej; Shapiro, Alexander; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe introduce an axiomatic definition of a conditional convex risk mapping and we derive its properties. In particular, we prove a representation theorem for conditional risk mappings in terms of conditional expectations. We also develop dynamic programming relations for multistage optimization problems involving conditional risk mappings.Publication 2004-03-25BuchOptimization of Convex Risk FunctionsRuszczynski, Andrzej; Shapiro, Alexander; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe consider optimization problems involving convex risk functions. By employing techniques of convex analysis and optimization theory in vector spaces of measurable functions we develop new representation theorems for risk models, and optimality and duality theory for problems involving risk functions.Publication 2004-03-01BuchConvexification of stochastic orderingDentcheva, Darinka; Ruszczynski, Andrzej; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetWe consider sets defined by the usual stochastic ordering relation and by the second order stochastic dominance relation. Under fairy general assumptions we prove that in the space of integrable random variables the closed convex hull of the first set is equal to the second set.Publication 2004-02-21BuchA branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problemGuan, Yongpei; Ahmed, Shabbir; Nemhauser, George L.; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetThis paper addresses a multi-stage stochastic integer programming formulation of the uncapacitated lot-sizing problem under uncertainty. We show that the classical $(\mathcal{l}, S)$ inequalities for the deterministic lot-sizing polytope are also valid for the stochastic lot-sizing polytope. We then extend the $(\mathcal{l}, S)$ inequalities to a general class of valid inequalities, called the $(Q, S_Q)$ inequalities, and we establish necessary and sufficient conditions which guarantee that the $(Q, S_Q)$ inequalities are facet-defining. A separation heuristic for $(Q, S_Q )$ inequalities is developed and incorporated into a branch and cut algorithm. A computational study verifies the usefulness of the $(Q, S_Q)$ inequalities as cuts.Publication 2004-02-19BuchA factor 1/2 approximation algorithm for a class of two-stage stochastic mixed-integer programsKong, Nan; Schaefer, Andrew J.; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetAbstract 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.Publication 2004-02-19BuchThe million-variable "march" for stochastic combinatorial optimizationNtaimo, Lewis; Sen, Suvrajeet; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetCombinatorial optimization problems have applications in a variety of sciences and engineering. In the presence of data uncertainty, these problems lead to stochastic combinatorial optimization problems which result in very large scale combinatorial optimization problems. In this paper, we report on the solution of some of the largest stochastic combinatorial optimization problem consisting of over a million binary variables. While the methodology is quite general, the specific application with which we conduct our experiments arises in stochastic server location problems. The main observation is that stochastic combinatorial optimization problems are comprised of loosely coupled subsystems. By taking advantage of the loosely coupled structure, we show that decomposition-coordination methods provide highly effective algorithms, and surpass the scalability of even the most efficiently implemented backtracking search algorithms.Publication 2004-02-10BuchEpi-convergent discretizations of multistage stochastic programsPennanen, Teemu; Higle, Julie L.; Römisch, Werner; Sen, SurrajeetIn many dynamic stochastic optimization problems in practice, the uncertain factors are best modeled as random variables with an infinite support. This results in infinite-dimensional optimization problems that can rarely be solved directly. Therefore, the random variables (stochastic processes) are often approximated by finitely supported ones (scenario trees), which result in finite-dimensional optimization problems that are more likely to be solvable by available optimization tools. This paper presents conditions under which such finite-dimensional optimization problems can be shown to epi-converge to the original infinite-dimensional problem. Epi-convergence implies the convergence of optimal values and solutions as the discretizations are made finer. Our convergence result applies to a general class of convex problems where neither linearity nor complete recourse are assumed.