Volume 2012
http://edoc.hu-berlin.de/18452/369
Thu, 02 Dec 2021 01:36:17 GMT2021-12-02T01:36:17ZConvex hull approximation of TU integer recourse models:Counterexamples, sufficient conditions, and special cases
http://edoc.hu-berlin.de/18452/9082
Convex hull approximation of TU integer recourse models:Counterexamples, sufficient conditions, and special cases
Romeijnders, Ward; Vlerk, Maarten H. van der
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We consider a convex approximation for integer recourse models. In particular, we showthat the claim of Van der Vlerk (2004) that this approximation yields the convex hull of totallyunimodular (TU) integer recourse models is incorrect. We discuss counterexamples, indicate which step of its proof does not hold in general, and identify a class of random variables for which the claim in Van der Vlerk (2004) is not true. At the same time, we derive additional assumptions under which the claim does hold. In particular, if the random variables in the model are independently and uniformly distributed, then these assumptions are satisfied.
Fri, 21 Dec 2012 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90822012-12-21T00:00:00ZThreshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix
http://edoc.hu-berlin.de/18452/9081
Threshold Boolean Form for Joint Probabilistic Constraints with Random Technology Matrix
Kogan, Alexander; Lejeune, Miguel A.
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We develop a new modeling and exact solution method for stochastic programming problems thatinclude a joint probabilistic constraint in which the multi-row random technology matrix is discretely distributed. We binarize the probability distribution of the random variables in such a way that we can extract a threshold partially defined Boolean function (pdBf) representing the probabilistic constraint.We then construct a tight threshold Boolean minorant for the pdBf. Any separating structureof the tight threshold Boolean minorant defines sufficient conditions for the satisfaction of the probabilistic constraint and takes the form of a system of linear constraints. We use the separating structure to derive three new deterministic formulations equivalent to the studied stochastic problem. We derivea set of strengthening valid inequalities for the reformulated problems. A crucial feature ofthe new integer formulations is that the number of integer variables does not depend on the numberof scenarios used to represent uncertainty. The computational study, based on instances of thestochastic capital rationing problem, shows that the MIP reformulations are much easier and ordersof magnitude faster to solve than the MINLP formulation. The method integrating the derived valid inequalities in a branch-and-bound algorithm has the best performance.
Fri, 23 Nov 2012 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90812012-11-23T00:00:00ZOptimizing existing railway timetables by means of stochastic programming
http://edoc.hu-berlin.de/18452/9080
Optimizing existing railway timetables by means of stochastic programming
Vekas, Peter; Vlerk, Maarten H. van der; Haneveld, Willem K. Klein
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
We present some models to find the best allocation of a limited amount of so-called runningtime supplements (extra minutes added to a timetable to reduce delays) on a railway line. Bythe best allocation, we mean the solution under which the sum of expected delays is minimal.Instead of trying to invent a completely new timetable, our aim is to finely adjust an alreadyexisting and well-functioning one. We model this inherently stochastic optimization problemby using two-stage recourse models from stochastic programming, following Vromans [9]. Wepresent an improved formulation, allowing for an efficient solution using a standard algorithmfor recourse models. We include a case study that we managed to solve about 180 times fasterthan it was solved in [9]. By comparing our solution with other, seemingly intuitive solutions,we show that finding the best allocation is not obvious, and implementing it in practicepromises a significant improvement in the punctuality of trains. A technique to estimate themodel parameters from empirical data and an approximating deterministic problem are alsopresented, along with some practical ideas that are meant to enhance the applicability of ourmodels.
Wed, 31 Oct 2012 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90802012-10-31T00:00:00ZIntroduction to convex optimization in financial markets
http://edoc.hu-berlin.de/18452/9079
Introduction to convex optimization in financial markets
Pennanen, Teemu
Higle, Julie L.; Römisch, Werner; Sen, Surrajeet
Convexity arises quite naturally in financial risk management. In riskpreferences concerning random cash-flows, convexity corresponds to thefundamental diversification principle. Convexity is a basic property alsoof budget constraints both in classical linear models as well as in morerealistic models with transaction costs and constraints. Moreover, modern securities markets are based on trading protocols that result in convextrading costs. The first part of this paper gives an introduction to certain basic concepts and principles of financial risk management in simpleoptimization terms. The second part reviews some convex optimizationtechniques used in mathematical and numerical analysis of financial optimization problems.
Fri, 08 Jun 2012 00:00:00 GMThttp://edoc.hu-berlin.de/18452/90792012-06-08T00:00:00Z