Volume 2007
http://edoc.hu-berlin.de/18452/364
2023-12-07T14:05:55ZOn M-stationary points for a stochastic equilibrium problem under equilibrium constraints in electricity spot market modeling
http://edoc.hu-berlin.de/18452/9036
On M-stationary points for a stochastic equilibrium problem under equilibrium constraints in electricity spot market modeling
Henrion, Rene; Römisch, Werner
http://dx.doi.org/10.18452/8384
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Modeling several competitive leaders and followers acting in an electricity marketleads to coupled systems of mathematical programs with equilibrium constraints,called equilibrium problems with equilibrium constraints (EPECs). We consider asimpliﬁed model for competition in electricity markets under uncertainty of demandin an electricity network as a (stochastic) multi-leader-follower game. First ordernecessary conditions are developed for the corresponding stochastic EPEC based ona result of Outrata [17]. For applying the general result an explicit representation ofthe co-derivative of the normal cone mapping to a polyhedron is derived (Proposition3.2). Later the co-derivative formula is used for verifying constraint qualiﬁcationsand for identifying M-stationary solutions of the stochastic EPEC if the demand isrepresented by a ﬁnite number of scenarios.
2007-12-07T00:00:00ZQuantitative stability of fully random mixed-integer two-stage stochastic programs
http://edoc.hu-berlin.de/18452/9035
Quantitative stability of fully random mixed-integer two-stage stochastic programs
Römisch, Werner; Vigerske, Stefan
http://dx.doi.org/10.18452/8383
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Mixed-integer two-stage stochastic programs with ﬁxed recourse matrix, random recourse costs, technology matrix, and right-hand sides areconsidered. Quantitative continuity properties of its optimal value and solution set are derived when the underlying probability distribution is perturbed with respect to an appropriate probability metric.
2007-12-07T00:00:00ZAlgorithms for handling CVaR-constraints in dynamic stochastic programming models with applications to finance
http://edoc.hu-berlin.de/18452/9034
Algorithms for handling CVaR-constraints in dynamic stochastic programming models with applications to finance
Fabian, Csaba I.; Veszpremi, Anna
http://dx.doi.org/10.18452/8382
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We propose dual decomposition and solution schemes for multistage CVaR-constrained problems. These schemes meet the need for handling multiple CVaR-constraints for different time frames and at different confidence levels. Hence they allow shaping distributions according to the decision maker's preference.With minor modifications, the proposed schemes can be used to decompose further types of risk constraints in dynamic portfolio management problems. We consider integrated chance constraints, second-order stochastic dominance constraints, and constraints involving a special value-of-information risk measure. We also suggest application to further financial problems. We propose a dynamic risk-constrained optimization model for option pricing. Moreover we propose special mid-term constraints for use in asset-liability management.
2007-08-10T00:00:00ZDecomposition of Multistage Stochastic Programs with Recombining Scenraio Trees
http://edoc.hu-berlin.de/18452/9033
Decomposition of Multistage Stochastic Programs with Recombining Scenraio Trees
Küchler, Christian; Vigerske, Stefan
http://dx.doi.org/10.18452/8381
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
This paper presents a decomposition approach for linear multistage stochasticprograms, that is based on the concept of recombining scenario trees. The latter, widely applied in Mathematical Finance, may prevent the node number of thescenario tree to grow exponentially with the number of time stages. It is shownhow this property may be exploited within a non-Markovian framework and under time-coupling constraints. Being close to the well-established Nested BendersDecomposition, our approach uses the special structure of recombining trees forsimultaneous cutting plane approximations. Convergence is proved and stoppingcriteria are deduced. Techniques for the generation of suitable scenario trees andsome numerical examples are presented.
2007-08-05T00:00:00ZSelf-concordant Tree and Decomposition Based Interior Point Methods for Stochastic Convex Optimization Problem
http://edoc.hu-berlin.de/18452/9032
Self-concordant Tree and Decomposition Based Interior Point Methods for Stochastic Convex Optimization Problem
Chen, Michael; Mehrotra, Sanjay
http://dx.doi.org/10.18452/8380
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider barrier problems associated with two and multistage stochastic convex optimization problems. We show that the barrier recourse functions at any stage form a self-concordant family with respect to the barrier parameter. We also show that the complexityvalue of the ﬁrst stage problem increases additively with the number of stages and scenarios. Weuse these results to propose a prototype primal interior point decomposition algorithm for thetwo-stage and multistage stochastic convex optimization problems admitting self-concordantbarriers.
2007-07-08T00:00:00ZComputations with Disjunctive Cuts for Two-Stage Stochastic Mixed 0-1 Integer Programs
http://edoc.hu-berlin.de/18452/9031
Computations with Disjunctive Cuts for Two-Stage Stochastic Mixed 0-1 Integer Programs
Ntaimo, Lewis; Tanner, Matthew W.
http://dx.doi.org/10.18452/8379
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a ﬁrst computationalstudy of a disjunctive cutting plane method for stochastic mixed 0-1 programsthat uses lift-and-project cuts based on the extensive form of the two-stage SMIPproblem. An extension of the method based on where the data uncertainty appearsin the problem is made, and it is shown how a valid inequality derived for onescenario can be made valid for other scenarios, potentially reducing solution time.Computational results amply demonstrate the effectiveness of disjunctive cuts insolving several large-scale problem instances from the literature. The results arecompared to the computational results of disjunctive cuts based on the subproblemspace of the formulation and it is shown that the two methods are equivalentlyeffective on the test instances.
2007-07-04T00:00:00ZSecond-Order Stochastic Dominance Constraints Induced by Mixed-Integer Linear Recourse
http://edoc.hu-berlin.de/18452/9030
Second-Order Stochastic Dominance Constraints Induced by Mixed-Integer Linear Recourse
Gollmer, Ralf; Gotzes, Uwe; Schultz, Rüdiger
http://dx.doi.org/10.18452/8378
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We introduce stochastic integer programs with dominance constraints induced by mixed-integer linear recourse. Closedness of the constraint set mapping with respect to perturbations of the underlying probability measure is derived. For discrete probability measures, large-scale, block-structured,mixed-integer linear programming equivalents to the dominance constrained stochastic programs areidentiﬁed. For these models, a decomposition algorithm is proposed. Computational tests withinstances from power optimization and Sudoku puzzling conclude the paper.
2007-06-03T00:00:00ZA Branch-and-Bound Method for Multistage Stochastic Integer Programs with Risk Objectives
http://edoc.hu-berlin.de/18452/9029
A Branch-and-Bound Method for Multistage Stochastic Integer Programs with Risk Objectives
Heinze, Thomas; Schultz, Rüdiger
http://dx.doi.org/10.18452/8377
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We identify multistage stochastic integer programs with risk objectives where the related wait-and-see problems enjoy similar separability as in the risk neutral case. For models belonging to this classwe present a solution method combining branch-and-bound with relaxation of nonanticipativity andconstraint branching along nonanticipativity subspaces.
2007-06-03T00:00:00ZStochastic Programs with First-Order Dominance Constraints Induced by Mixed-Integer Linear Recourse
http://edoc.hu-berlin.de/18452/9028
Stochastic Programs with First-Order Dominance Constraints Induced by Mixed-Integer Linear Recourse
Gollmer, Ralf; Neise, Frederike; Schultz, Rüdiger
http://dx.doi.org/10.18452/8376
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We propose a new class of stochastic integer programs whose special features are dominance constraints induced by mixed-integer linear recourse. For these models, we establish closedness of theconstraint set mapping with the underlying probability measure as parameter. In the case of ﬁniteprobability spaces, the models are shown to be equivalent to large-scale, block-structured, mixed-integer linear programs. We propose a decomposition algorithm for the latter and discuss preliminarycomputational results.
2007-06-03T00:00:00ZA Short Note on the Probabilistic Set Covering Problem
http://edoc.hu-berlin.de/18452/9027
A Short Note on the Probabilistic Set Covering Problem
Saxena, Anureet
http://dx.doi.org/10.18452/8375
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we address the following probabilistic version (PSC) of the set coveringproblem: $ min{cx | P(Ax ≥ ξ) ≥ p, x_j \in {0, 1} j \in N }$ where A is a 0-1 matrix, ξis a random 0-1 vector and $p \in (0, 1]$ is the threshold probability level. In a recentdevelopment Saxena, Goyal and Lejeune proposed a MIP reformulation of (PSC) andreported extensive computational results with small and medium sized (PSC) instances.Their reformulation, however, suffers from the curse of exponentiality − the number ofconstraints in their model can grow exponentially rendering the MIP reformulation intractable for all practical purposes. In this paper, we give a polynomial-time algorithmto separate the (possibly exponential sized) constraint set of their MIP reformulation.Our separation routine is independent of the speciﬁc nature (concave, convex, linear,non-linear etc) of the distribution function of ξ, and can be easily embedded within abranch-and-cut framework yielding a distribution-free algorithm to solve (PSC). The resulting algorithm can solve (PSC) instances of arbitrarily large block sizes by generatingonly a small subset of constraints in the MIP reformulation and verifying the remainingconstraints implicitly. Furthermore, the constraints generated by the separation routineare independent of the coefficient matrix A and cost-vector c thereby facilitating theirapplication in sensitivity analysis, re-optimization and warm-starting (PSC). We givepreliminary computational results to illustrate our ﬁndings on a test-bed of 40 (PSC)instances created from OR-Lib set-covering instance scp41.
2007-05-29T00:00:00ZMIP Reformulations of the Probabilistic Set Covering Problem
http://edoc.hu-berlin.de/18452/9026
MIP Reformulations of the Probabilistic Set Covering Problem
Saxena, Anureet; Goyal, Vineet; Lejeune, Miguel
http://dx.doi.org/10.18452/8374
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper we address the following probabilistic version (PSC) of the set cover-ing problem: $ min{cx | P(Ax ≥ ξ) ≥ p, x_j \in {0, 1}N }$ where A is a 0-1 matrix, ξ is arandom 0-1 vector and $p \in (0, 1]$ is the threshold probability level. We formulate (PSC)as a mixed integer non-linear program (MINLP) and linearize the resulting (MINLP)to obtain a MIP reformulation. We introduce the concepts of p-inefficiency and polaritycuts. While the former is aimed at reducing the number of constraints in our model,the later is used as a strengthening device to obtain stronger formulations. A hierarchy of relaxations for (PSC) is introduced, and fundamental relationships between therelaxations are established culminating with a MIP reformulation of (PSC) with noadditional integer constrained variables. Simpliﬁcations of the MIP model which resultwhen one of the following conditions hold are brieﬂy discussed: A is a balanced matrix,A has the circular ones property, the components of ξ are pairwise independent, thedistribution function of ξ is a stationary distribution or has the so-called disjunctiveshattering property. We corroborate our theoretical ﬁndings by an extensive computational experiment on a test-bed consisting of almost 10,000 probabilistic instances.This test-bed was created using deterministic instances from the literature and consistsof probabilistic variants of the set-covering model and capacitated versions of facilitylocation, warehouse location and k-median models. Our computational results showthat our procedure is orders of magnitude faster than any of the existing approachesto solve (PSC), and in many cases can reduce hours of computing time to fraction ofseconds.
2007-05-29T00:00:00ZAn Exact Solution Approach for Portfolio Optimization Problems under Stochastic and Integer Constraints
http://edoc.hu-berlin.de/18452/9025
An Exact Solution Approach for Portfolio Optimization Problems under Stochastic and Integer Constraints
Bonami, P.; Lejeune, M.A.
http://dx.doi.org/10.18452/8373
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
In this paper, we study extensions of the classical Markowitz’ mean-variance portfolio optimization model. First, we consider that the expected asset returns are stochastic by introducing aprobabilistic constraint imposing that the expected return of the constructed portfolio must exceeda prescribed return level with a high conﬁdence level. We study the deterministic equivalents ofthese models. In particular, we deﬁne under which types of probability distributions the deterministic equivalents are second-order cone programs, and give exact or approximate closed-form formulations. Second, we account for real-world trading constraints, such as the need to diversify theinvestments in a number of industrial sectors, the non-proﬁtability of holding small positions and theconstraint of buying stocks by lots, modeled with integer variables. To solve the resulting problems,we propose an exact solution approach in which the uncertainty in the estimate of the expected returns and the integer trading restrictions are simultaneously considered. The proposed algorithmicapproach rests on a non-linear branch-and-bound algorithm which features two new branching rules.The ﬁrst one is a static rule, called idiosyncratic risk branching, while the second one is dynamic andcalled portfolio risk branching. The proposed branching rules are implemented and tested using theopen-source framework of the solver Bonmin. The comparison of the computational results obtainedwith standard MINLP solvers and with the proposed approach shows the effectiveness of this latterwhich permits to solve to optimality problems with up to 200 assets in a reasonable amount of time.
2007-05-29T00:00:00Z