Volume 2004
http://edoc.hu-berlin.de/18452/361
2023-10-03T06:54:10ZOn the Fortet-Mourier metric for the stability of Stochastic Optimization Problems, an example
http://edoc.hu-berlin.de/18452/8981
On the Fortet-Mourier metric for the stability of Stochastic Optimization Problems, an example
Strugarek, Cyrille
http://dx.doi.org/10.18452/8329
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We 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.
2004-12-27T00:00:00ZTwo-stage integer programs with stochastic right-hand sides
http://edoc.hu-berlin.de/18452/8980
Two-stage integer programs with stochastic right-hand sides
Kong, Nan; Schaefer, Andrew J.; Hunsaker, Brady
http://dx.doi.org/10.18452/8328
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
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 that are several orders of magnitude larger than those found in the literature.
2004-10-02T00:00:00ZA class of stochastic programs with decision dependent uncertainty
http://edoc.hu-berlin.de/18452/8979
A class of stochastic programs with decision dependent uncertainty
Goel, Vikas; Grossmann, Ignacio E.
http://dx.doi.org/10.18452/8327
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
The 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.
2004-10-02T00:00:00ZVariance reduction in sample approximations of stochastic programs
http://edoc.hu-berlin.de/18452/8978
Variance reduction in sample approximations of stochastic programs
Koivu, Matti
http://dx.doi.org/10.18452/8326
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This 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.
2004-10-02T00:00:00ZOn deviation measures in stochastic integer programming
http://edoc.hu-berlin.de/18452/8977
On deviation measures in stochastic integer programming
Märkert, Andreas; Schultz, Rüdiger
http://dx.doi.org/10.18452/8325
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We 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.
2004-09-13T00:00:00ZConditional value-at-risk in stochastic programs with mixed-integer recourse
http://edoc.hu-berlin.de/18452/8976
Conditional value-at-risk in stochastic programs with mixed-integer recourse
Schultz, Rüdiger; Tiedemann, Stephan
http://dx.doi.org/10.18452/8324
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In 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.
2004-09-13T00:00:00ZTreasury management model with foreign exchange exposure
http://edoc.hu-berlin.de/18452/8975
Treasury management model with foreign exchange exposure
Volosov, Konstantin; Mitra, Gautam; Spagnolo, Fabio; Lucas, Cormac
http://dx.doi.org/10.18452/8323
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In 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.
2004-06-15T00:00:00ZPolyhedral inclusion-exclusion
http://edoc.hu-berlin.de/18452/8974
Polyhedral inclusion-exclusion
Bukszar, Jozsef; Henrion, René; Hujter, Mihaly; Szantai, Tamas
http://dx.doi.org/10.18452/8322
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Motivated 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.
2004-06-05T00:00:00ZArbitrage pricing of American contingent claims in incomplete markets - a convex optimization approach
http://edoc.hu-berlin.de/18452/8973
Arbitrage pricing of American contingent claims in incomplete markets - a convex optimization approach
Pennanen, Teemu; King, Alan J.
http://dx.doi.org/10.18452/8321
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Convex 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.
2004-05-21T00:00:00ZA stochastic programming approach to resource-constrained assignment problems
http://edoc.hu-berlin.de/18452/8972
A stochastic programming approach to resource-constrained assignment problems
Toktas, Berkin; Yen, Joyce W.; Zabinsky, Zelda B.
http://dx.doi.org/10.18452/8320
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We 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.
2004-05-17T00:00:00ZAssessing policy quality in multi-stage stochastic programming
http://edoc.hu-berlin.de/18452/8971
Assessing policy quality in multi-stage stochastic programming
Chiralaksanakul, Anukal; Morton, David P.
http://dx.doi.org/10.18452/8319
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Solving 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.
2004-05-17T00:00:00ZDecomposition-based interior point methods for two-stage stochastic convex quadratic programs with recourse
http://edoc.hu-berlin.de/18452/8970
Decomposition-based interior point methods for two-stage stochastic convex quadratic programs with recourse
Mehrotra, Sanjay; Ozevin, M. Gokhan
http://dx.doi.org/10.18452/8318
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Zhao [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.
2004-04-20T00:00:00ZMean-risk objectives in stochastic programming
http://edoc.hu-berlin.de/18452/8969
Mean-risk objectives in stochastic programming
Ahmed, Shabbir
http://dx.doi.org/10.18452/8317
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
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 a parametric cutting plane algorithm to generate the entire mean-risk efficient frontier for a particular mean-risk objective.
2004-04-16T00:00:00ZConditional Risk Mappings
http://edoc.hu-berlin.de/18452/8968
Conditional Risk Mappings
Ruszczynski, Andrzej; Shapiro, Alexander
http://dx.doi.org/10.18452/8316
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We 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.
2004-03-25T00:00:00ZOptimization of Convex Risk Functions
http://edoc.hu-berlin.de/18452/8967
Optimization of Convex Risk Functions
Ruszczynski, Andrzej; Shapiro, Alexander
http://dx.doi.org/10.18452/8315
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We 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.
2004-03-25T00:00:00ZConvexification of stochastic ordering
http://edoc.hu-berlin.de/18452/8966
Convexification of stochastic ordering
Dentcheva, Darinka; Ruszczynski, Andrzej
http://dx.doi.org/10.18452/8314
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We 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.
2004-03-01T00:00:00ZA branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem
http://edoc.hu-berlin.de/18452/8965
A branch-and-cut algorithm for the stochastic uncapacitated lot-sizing problem
Guan, Yongpei; Ahmed, Shabbir; Nemhauser, George L.
http://dx.doi.org/10.18452/8313
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This 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.
2004-02-21T00:00:00ZA factor 1/2 approximation algorithm for a class of two-stage stochastic mixed-integer programs
http://edoc.hu-berlin.de/18452/8964
A factor 1/2 approximation algorithm for a class of two-stage stochastic mixed-integer programs
Kong, Nan; Schaefer, Andrew J.
http://dx.doi.org/10.18452/8312
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Abstract 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.
2004-02-19T00:00:00ZThe million-variable "march" for stochastic combinatorial optimization
http://edoc.hu-berlin.de/18452/8963
The million-variable "march" for stochastic combinatorial optimization
Ntaimo, Lewis; Sen, Suvrajeet
http://dx.doi.org/10.18452/8311
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Combinatorial 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.
2004-02-19T00:00:00ZEpi-convergent discretizations of multistage stochastic programs
http://edoc.hu-berlin.de/18452/8962
Epi-convergent discretizations of multistage stochastic programs
Pennanen, Teemu
http://dx.doi.org/10.18452/8310
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In 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.
2004-02-10T00:00:00ZMelt control
http://edoc.hu-berlin.de/18452/8961
Melt control
Dupacová, Jitka; Popela, Pavel
http://dx.doi.org/10.18452/8309
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper introduces melt control as a good case for application of two- and multistage stochastic programming models. Sources of uncertainties are described and several methods of input generation are presented. The implementation based on real data compares decisions and costs obtained by solving stochastic programs with different numbers of stages and a different structure of the scenario tree. The results give a clear evidence in favor of the proposed stochastic programming methodology.
2004-01-14T00:00:00ZAsset-liability management for Czech pension funds using stochastic programming
http://edoc.hu-berlin.de/18452/8960
Asset-liability management for Czech pension funds using stochastic programming
Dupacová, Jitka; Polivka, Jan
http://dx.doi.org/10.18452/8308
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
It is possible to model a wide range of portfolio management problems using stochastic programming. This approach requires the generation of input scenarios and probabilities, which represent the evolution of the return on investment, the stream of liabilities and other random phenomena of the problem and respect the no-arbitrage properties. The quality of the recommended capital allocation depends on the quality of the input scenarios and a validation of results is necessary. We propose scenario generation techniques and for output analysis in the context of defined contribution pension fund management. The application to the specific case of a Czech pension fund indicates the components that influence the recommended investment decisions and the fund's results. The initial position of the pension fund is important because of the accounting rules in the model and tracking both the market and purchasing valuation of assets.
2004-01-14T00:00:00Z