Volume 2002
http://edoc.hu-berlin.de/18452/359
2024-03-01T01:06:12ZLearning algorithms for separable approximations of stochastic optimization problems
http://edoc.hu-berlin.de/18452/8934
Learning algorithms for separable approximations of stochastic optimization problems
Powell, Warren; Ruszczynski, Andrzej; Topaloglu, Huseyin
http://dx.doi.org/10.18452/8282
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We propose the use of sequences of separable, piecewise linear approximations for solving classes of nondiffferential stochastic optimization problems. The approximations are estimated adaptively using a combination of stochastic gradient information and possibly sample information on the objective function itself. We prove the convergence of several versions of such methods when the objective function is separable and illustrate their behavior on numerical examples. We then demonstrate the preformance on nonseparable problems that arise in the context of two-stage stochastic programming problems, and demonstrate that these techniques provide near optimal solutions with a very fast rate of convergence compared to other solution techniques.
2002-11-05T00:00:00ZA branch-and-price algorithm for multi-stage stochastic integer programming with application to stochastic batch-sizing problems
http://edoc.hu-berlin.de/18452/8933
A branch-and-price algorithm for multi-stage stochastic integer programming with application to stochastic batch-sizing problems
Lulli, Guglielmo; Sen, Suvrajeet
http://dx.doi.org/10.18452/8281
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we present a branch-and-price method to solve special structured multi-stage stochastic integer programming problems. We validate our method on two different versions of a multi-stage stochastic batch-sizing problem. One version adopts a recourse formulation, and the other is based on probabilistic constraints. Our algorithmic approach is applicable to both formulations. Our computational results suggest that both classes of problems can be solved using relatively few nodes of a branch-and-price tree. The success of our approach calls for extensions in methodology as well as applications.
2002-10-24T00:00:00ZFrontiers of stochastically nondominated portfolios
http://edoc.hu-berlin.de/18452/8932
Frontiers of stochastically nondominated portfolios
Ruszczynski, Andrzej; Vanderbei, Robert J.
http://dx.doi.org/10.18452/8280
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider the problem of constructing a portfolio of finitely many assets whose returns are described by a discrete joint distribution. We propose mean-risk models which are solvable by linear programming and generate portfolios whose returns are nondominated in the sense of second-order stochastic dominance. Next, we develop a specialized parametric method for recovering the entire mean-risk efficient frontiers of these models and we illustrate its operation on a large data set involving thousands of assets and realizations.
2002-10-24T00:00:00ZRisk aversion via excess probabilities in stochastic programs with mixed-integer recourse
http://edoc.hu-berlin.de/18452/8931
Risk aversion via excess probabilities in stochastic programs with mixed-integer recourse
Schultz, Rüdiger; Tiedemann, Stephan
http://dx.doi.org/10.18452/8279
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider linear two-stage stochastic programs with mixed-integer recourse. Instead of basing the selection of an optimal first-stage solution on expected costs alone, we include into the objective a risk term reflecting the probability that a preselected cost threshold is exceeded. After we have put the resulting mean-risk model into perspective with stochastic dominance, we study further structural properties of the model and derive some basic stability results. In the algorithmic part of the paper, we propose a scenario decomposition method and report initial computational experience.
2002-08-16T00:00:00ZIntegrated chance constraints
http://edoc.hu-berlin.de/18452/8930
Integrated chance constraints
Haneveld, Willem K. Klein; Vlerk, Maarten H. van der
http://dx.doi.org/10.18452/8278
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider integrated chance constraints (ICC), which provide quantitative alternatives for traditional chance constraints. We derive explicit polyhedral descriptions for the convex feasible sets induced by ICCs, for the case that the underlying distribution is discrete. Based on these reduced forms, we propose an efficient algorithm for this problem class.The relation to conditional value-at-risk models and (simple) recourse models is discussed, leading to a special purpose algorithm for simple recourse models with discretely distributed technology matrix. For both algorithms, numerical results are presented.
2002-07-29T00:00:00ZDuality gaps in nonconvex stochastic optimization
http://edoc.hu-berlin.de/18452/8929
Duality gaps in nonconvex stochastic optimization
Dentcheva, Darinka; Römisch, Werner
http://dx.doi.org/10.18452/8277
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider multistage stochastic optimization models. Logical or integrality constraints, frequently present in optimization models, limit the application of powerful convex analysis tools. Different Lagrangian relaxation schemes and the resulting decomposition approaches provide estimates of the optimal value. We formulate convex optimization models equivalent to the dual problems of the Lagrangian relaxations. Our main results compare the resulting duality gap for these decomposition schemes. Attention is paid also to programs that model large systems with loosely coupled components.
2002-07-07T00:00:00ZApplying the minimax criterion in stochastic recourse programs
http://edoc.hu-berlin.de/18452/8928
Applying the minimax criterion in stochastic recourse programs
Riis, Morten; Andersen, Kim Allan
http://dx.doi.org/10.18452/8276
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider an optimization problem in which some uncertain parmeters are replaced by random variables. The minimax approach to stochastic programming concerns the problem of minimizing the worst expected value of the objective function with respect to the set of probability measures that are consistent with the available information on random data. Only very few practicable solution procedures have been proposed for this problem and the existing ones rely on simplifying assumptions. In this paper, we establish a number of stability results for the minimax stochastic program, justifying in particular the approach of restricting attention to probability measures with support in some unknown finite set. Following this approach, we elaborate solution procedures for the minimax problem in the setting of two-stage stochastic recourse models, considering the linear recourse case as well as the integer recourse case. Since the solution procedures are modifications of well-known algorithms, their efficacy is immediate from the computational testing of these procedures and we do not report results of any computational experiments.
2002-07-05T00:00:00ZIntegration quadratures in discretization of stochastic programs
http://edoc.hu-berlin.de/18452/8927
Integration quadratures in discretization of stochastic programs
Pennanen, Teemu; Koivu, Matti
http://dx.doi.org/10.18452/8275
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Because of its simplicity, conditional sampling is the most popular method for generating scenario trees in stochastic programming. It is based on approximating probability measures by empirical ones generated by random samples. Because of computational restrictions, these samples cannot be very large, so the empirical measures can be poor approximations of the original ones. This paper shows that modern integration quadratures provide a simple and an attractive alternative to random sampling. These quadratures are designed to give good approximations of given (probability) measures by a small number of quadrature points. The performance of the resulting scenario generation methods is demonstrated by numerical examples.
2002-06-04T00:00:00ZConvex approximations for complete integer recourse models
http://edoc.hu-berlin.de/18452/8926
Convex approximations for complete integer recourse models
Vlerk, Maarten H. van der
http://dx.doi.org/10.18452/8274
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider convex approximations of the expected value function of a two-stage integer recourse problem. The convex approximations are obtained by perturbing the distribution of the random right-hand side vector. It is shown that the approximation is optimal for the class of problems with totally unimodular recourse matrices. For problems not in this class, the result is a convex lower bound that is strictly better than the one obtained from the LP relaxation.
2002-05-26T00:00:00ZOptimization of simultaneous power production and trading by stochastic integer programming
http://edoc.hu-berlin.de/18452/8925
Optimization of simultaneous power production and trading by stochastic integer programming
Nowak, Matthias Peter; Schultz, Rüdiger; Westphalen, Markus
http://dx.doi.org/10.18452/8273
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We develop a two-stage stochastic integer programming model for the simultaneous optimization of power production and day-ahead power trading. The model rests on mixed-integer linear formulations for the unit commitment problem and for the price clearing mechanism at the power exchange. Foreign bids enter as random components into the model. We solve the stochastic integer program by a decomposition method combining Lagrangian relaxation of nonanticipativity with branch-and-bound in the spirit of global optimization. Fianlly, we report some first computational experiences.
2002-05-23T00:00:00ZHigher-Order Upper Bounds on the Expectation of a Convex Function
http://edoc.hu-berlin.de/18452/8924
Higher-Order Upper Bounds on the Expectation of a Convex Function
Dokov, Steftcho P.; Morton, David P.
http://dx.doi.org/10.18452/8272
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We develop a decreasing sequence of upper bounds on the expectation of a convex function. The n-th term in the sequence uses moments and cross-moments of up to degree n from the underlying random vector. Our work has application to a class of two-stage stochastic programs with recourse. The objective function of such a model can defy computation when: (i) the underlying distribution is assumed to be known only through a limited number of moments or (ii) the function is computationally intractable, even though the distribution is known. A tractable approximating model arises by replacing the objective function by one of our bounding elements. We justify this approach by showing that as n grows, solutions of the order-n approximation solve the true stochastic program.
2002-05-03T00:00:00ZOn Multiple Simple Recourse models
http://edoc.hu-berlin.de/18452/8923
On Multiple Simple Recourse models
Vlerk, Maarten H. van der
http://dx.doi.org/10.18452/8271
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider multiple simple recourse (MSR) models, both continuous and integer versions, which generalize the corresponding simple recourse (SR) models by allowing for a refined penalty cost structure for individual shortages and surpluses. It will be shown that (convex approximations of) such MSR models can be repre-sented as explicitly specified continuous SR models, and thus can be solved efficiently by existing algorithms.
2002-05-02T00:00:00ZCapital growth with security
http://edoc.hu-berlin.de/18452/8922
Capital growth with security
MacLean, Leonard C.; Sanegre, Rafael; Zhao, Yonggan; Ziemba, William T.
http://dx.doi.org/10.18452/8270
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper discusses the allocation of capital over time with several risky assets. The capital growth log utility approach is used with conditions requiring that specific goals are achieved with high probability. The stochastic optimization model uses a disjunctive form for the probabilistic constraints, which identifies an outer problem of choosing an optimal set of scenarios, and an inner (conditional) problem of finding the optimal investment decisions for a given scenarios set. The multiperiod inner problem is composed of a sequence of conditional one period problems. The theory is illustrated for the dynamic allocation of wealth in stocks, bonds and cash equivalents.
2002-01-29T00:00:00ZA stochastic intra-ring synchronous optimal network design problem
http://edoc.hu-berlin.de/18452/8921
A stochastic intra-ring synchronous optimal network design problem
Cole, J.; Schaefer, Andrew J.; Yen, Joyce W.
http://dx.doi.org/10.18452/8269
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We develop a stochastic programming approach to solving an intra-ring Synchronous Optical Network (SONET) design problem. This research differs from pioneering SONET design studies in two fundamental ways. First, while traditional approaches to solving this problem assume that all data are deterministic, we observe that for practical planning situations, network demand levels are stochastic. Second, while most models disallow demand shortages and focus only on the minimization of capital Add-Drop Multiplexer (ADM) equipment expenditure, our model minimizes a mix of ADM installations and expected penalties arising from the failure to satisfy some or all of the actual telecommunication demand. We propose an L-shaped algorithm to solve this design problem, and demonstrate how a nonlinear reformulation of the problem may improve the strength of the generated optimality cuts. We next enhance the ba-sic algorithm by implementing powerful lower and upper bounding techniques via an assortment of modeling, valid inequality, and heuristic strategies. Our computational results conclusively demonstrate the efficacy of our proposed algorithm as opposed to standard L-shaped and extensive form approaches to solving the problem.
2002-04-23T00:00:00ZExact solutions to a class of stochastic generalized assignment problems
http://edoc.hu-berlin.de/18452/8920
Exact solutions to a class of stochastic generalized assignment problems
Albareda-Sambola, Maria; Vlerk, Maarten H. van der; Fernandez, Elena
http://dx.doi.org/10.18452/8268
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper deals with a stochastic Generalized Assignment Problem with recourse. Only a random subset of the given set of jobs will require to be actually processed. An assignment of each job to an agent is decided a priori, and once the demands are known, reassignments can be performed if there are overloaded agents. We construct a convex approximation of the objective function that is sharp at all feasible solutions. We then present three versions of an exact algorithm to solve this problem, based on branch and bound techniques, optimality cuts, and a special purpose lower bound. Numerical results are reported.
2002-04-22T00:00:00ZA splitting method for stochastic programs
http://edoc.hu-berlin.de/18452/8919
A splitting method for stochastic programs
Pennanen, Teemu; Kallio, Markku
http://dx.doi.org/10.18452/8267
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper derives a new splitting-based decomposition algorithm for convex stochastic programs. It combines certain attractive features of the progressive hedging algorithm of Rockafellar and Wets, the dynamic splitting algorithm of Salinger and Rockafellar and an algorithm of Korf. We give two derivations of our algorithm. The first one is very simple, and the second one yields a preconditioner that can be used to speed up the convergence.
2002-03-14T00:00:00ZMultistage stochastic convex programs
http://edoc.hu-berlin.de/18452/8918
Multistage stochastic convex programs
Higle, Julia L.; Sen, Suvrajeet
http://dx.doi.org/10.18452/8266
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper, we study alternative primal and dual formulations of multistage stochastic convex programs (SP). The alternative dual problems which can be traced to the alterna-tive primal representations, lead to stochastic analogs of standard deterministic constructs such as conjugate functions and Lagrangians. One of the by-products of this approach is that the development does not depend on dynamic programming (DP) type recursive arguments, and is therefore applicable to problems in which the objective function is non-separable (in the DP sense). Moreover, the treatment allows us to handle both continuous and discrete random variables with equal ease. We also investigate properties of the ex-pected value of perfect information (EVPI) within the context of SP, and the connection between EVPI and nonanticipativity of optimal multipliers. Our study reveals that there exist optimal multipliers that are nonanticipative if, and only if, the EVPI is zero. Finally, we provide interpretations of the retroactive nature of the dual multipliers.
2002-02-21T00:00:00ZThe stochastic single node service provision problem
http://edoc.hu-berlin.de/18452/8917
The stochastic single node service provision problem
Dye, Shane; Stougie, Leen; Tomasgard, Asgeir
http://dx.doi.org/10.18452/8265
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
The service provision problem described in this paper comes from an application of distributed processing in telecommunications networks. The objective is to maximize a service provider's profit from offering computational based services to customers. The service provider has limited capacity and must choose from a set of software applications those he would like to offer. This can be done dynamically taking into consideration that demand for the different services is uncertain. The problem is examined in the framework of stochastic integer programming. Approximations and complexity are examined for the case when demand is described by a discrete probability distribution. For the deterministic counterpart a fully polynomial approximation scheme is known. We show that introduction of stochasticity makes the problem stongly NP-hard, implying that the existence of such a scheme for the stochastic problem is highly unlikely. For the general case a heuristic with a worst-case performance ratio that increases in the number of scenarios is presented. Restricting the class of problem instances in a way that many reasonable practical problem instances will satisfy, allows for the derivation of a heuristic with a constant worst-case performance ratio. These worst-case results are the first results for stochastic programming problems that the authors are aware of in a direction that is classical in the field of combinatorial optimization.
2002-02-13T00:00:00Z