User's guide to ddsip.vSD - Universität Duisburg
Contents
1. 69 95 GNU Project http www gnu org Gollmer R Gotzes U Schultz R Second Order Stochastic Dominance Constraints Induced by Mixed Integer Linear Recourse Preprint 644 2007 Department of Mathe matics University of Duisburg essen 2007 Gollmer R Neise F Schultz R Stochastic Programs with First Order Dominance Constraints Induced by Mixed Integer Linear Recourse Preprint 641 2006 Department of Mathematics University of Duisburg essen 2006 Helmberg C http www user tu chemnitz de helmberg Conic Bundle Manual 2005 http www ilog com products optimization ILOG CPLEX 9 0 Manuals http www iro umontreal ca gendron IFT6551 CPLEX HTML http www graphviz org Kall P Wallace S W Stochastic Programming Wiley Chichester 1994 Louveaux F V Schultz R Stochastic Integer Programming In A Ruszczynski A Shapiro Eds Stochastic Programming Elsevier North Holland 2003 Miiller A Scarsini M Stochastic Order Relations and Lattices of Probability Mea sures Siam Journal on Optimization 16 2006 pp 1024 1043 Markert A Deviation Measures in Stochastic Programming with Mixed Integer Re course Doctoral thesis Institute of Mathematics University Duisburg Essen Campus Duisburg 2004 Markert A ddsip http www uni duisburg de FB11 disma ddsip shtml Mann H B Whitney D R On a test of whether one of two random variables is stochas tically larger than the ot2. a lower bound prp P and apply a feasibility heuristics to find a feasible point x of P STEP 4 PRUNING If yrp P 00 infeasibility of a subproblem or prB P gt inferiority of P then go to Step 2 If pLg P g z optimality for P then check whether g lt If yes then g z Go to Step 2 If g lt then g z STEP 5 BRANCHING Create two new subproblems by partitioning the set X P by means of linear inequali ties Add these subproblems to P and go to Step 2 3 Input files ddsip vSD requires 4 input files a number of other files are optional The file formats will be described in the following sections Mandatory Specification file a file containing the specifications of the stochastic program some CPLEX and Branch amp Bound parameters Model file a mps file readable by CPLEX that specifies the single scenario model Scenario file a file containing the scenario probabilities and stochastic right hand sides if there are any A Reference file a file containing the specifications of the benchmark random variable d Optional Priority order file for subproblems a CPLEX order file 14 corresponding to the model file Matrix scenario file a file containing stochastic matrix entries Priority order file for master a file containing a branching order for the master branch and bound procedure Start information file a file containing start informations such as a feasible solu
3. output on screen is also directed to the file sip out In addition this file contains the read parameters and some information on the solution e The value of Status indicates the solution status 1 the process was terminated by the user the node limit has been reached the gap absolute or relative has been reached the time limit has been reached the maximal dispersion i e the maximal difference of the first stage components within all remaining front nodes was less then the parameter NULLDISP null dispersion 5 the whole branching tree was backtracked Ae UUNe e Time is the total time needed by ddsip vSD e Upper bounds is the number of evaluated upper bounds e Tree depth is the depth of the branch and bound tree e Nodes is the total number of nodes 8 3 Other output files The number of additional output files and their content is ruled via the parameters OUTFIL and OUTLEV 15 e The files rhs out matriz out and model mps offer a check for a correct reading of the scenario files and the model file respectively e The files solution out contains information on the solution with the optimal first stage solution among them e The file more out contains more or less information depending on the parameter OUT LEV e g the subproblem solutions the branch and bound tree and the objective function composition e det_equ FSD SSD mps gz test lp gz Deterministic equivalent of the current problem and deterministic
4. stochastic integer programs see 6 below that we address with our software Stochastic dominance an established concept in decision theory 22 provides a possibil ity to formalize the above mentioned acceptability We deal with first and second order stochastic dominance in the case where the involved random variables have only finitely many realizations Let Y a random variable on some probability space and Y Q y1 yx When preferring small outcomes to big ones a random variable X is said to dominate a random variable Y to first order X gt Y iff P X lt yx gt P Y lt yz Vk 1 K Second order dominance X 2 yx holds iff E X yk lt E Y yk Vk 1 K i e iff the expected excess of X above each outcome of Y is less than or equal to the expected excess of Y above its realizations 4 max 0 Coming back to our two stage random optimization problem 1 and the related family 4 we assume some random benchmark cost profile i e a random variable d be given We consider only those x X acceptable for which the corresponding fr dominates the benchmark profile d stochastically to first or second order respectively Over all acceptable x X we optimize some function g X R This leads to the following stochastic program with dominance constraint induced by mixed integer linear recourse min g x fe zi d eX t 1 2 6 Note that t
5. the table below The first column of the table contains the name of the parameter the second column specifies whether it is an integer or a real Dbl parameter Then the parameter s range and it s default value is given The last column explains the parameter s meaning Name Type Range Default Description OUTLEV Int 0 30 0 Print output to more out Caution The file more out may become large for high values of OUTLEV OUTFIL Int 0 9 0 Print output files see chapter Cau tion If OUTFIL is greater than 8 lp files are written at each node and for each scenario LOGFRE Int 0 1 A line of output is printed every i th iter ation NODELI Int 0 1 The node limit for the branch and bound procedure TIMELI Dbl 0 100 The total time limit CPU time ABSOLU Dbl 0 0 The absolute duality gap Should be greater than RELATI RELATI Dbl 0 0 The relative duality gap OBJISINT Int 0 1 0 Indicates whether the objective function attains only integer values If yes lower bounds are rounded up DOMINANCE Int 1 2 Indicates which if first or second order stochastic dominance is used DETEQU Int 0 1 0 Indicates whether a deterministic equiva lent to the current problem is written out to sipout TEST Int 0 1 0 Indicates whether a deterministic equiv alent with fixed variables is written out after a problem was solved TRIVIALUB Dbl a oo Value that is interpreted as infinity by the dual method dual method in the cu
6. User s guide to ddsip vSD A C Package for the Dual Decomposition of Stochastic Programs with Dominance Constraints Induced by Mixed Integer Linear Recourse U Gotzes F Neise Department of Mathematics University of Duisburg Essen Campus Duisburg Lotharstr 65 D 47048 Germany gotzesQmath uni duisburg de neiseQ math uni dusburg de March 12 2008 1 Introduction ddsip vSD is a C implementation of a number of scenario decomposition algorithms for stochastic linear programs with first or second order stochastic dominance constraints in duced by mixed integer linear recourse The program is based on a previous implementation of scenario decomposition algorithms for mean risk models of A Markert 20 Main idea of the decomposition algorithms is the Lagrangean relaxation of unavoidable scenario coupling second stage constraints and of some nonanticipativity constraints A branch and bound algorithm to reestablish nonanticipativity is employed The original scenario decomposition algorithm for stochastic linear programs with mixed integer recourse has been developed in 5 Extensions including the treatment of mean risk models have been made in 19 The algorithms focussing stochastic dominance have been elaborated in TI For the dual optimization we use ConicBundle a C implementation provided by C Helmberg see 12 We use the CPLEX callable library to solve the mixed integer subprob lems in the branch and bound tree se
7. e 14 The current version of ddsip vSD relies on CPLEX 9 1 3 Unfortunately we did not yet have the chance to debug and optimize the code in a sufficient way We ask the user to support fixing bugs by reporting them to us as they occur This manual describes the format of the input files and the data contained in the output files of ddsip vSD We try to provide all necessary information on the input parameters 2 Stochastic programs with dominance constraints induced by mixed integer linear recourse ddsip vSD is appropriate to solve stochastic programs with first or second order dominance constraints induced by mixed integer linear recourse Such problems were first investigated by 11 T0 Two stage stochastic programming models are derived from random optimization problems with information constraints We start out from the following random mixed integer linear program min c a q y Te Wy 2z w rE X y Y 1 together with the information constraint that x must be selected without anticipation of z w This leads to a two stage scheme of alternating decision and observation The decision on x is followed by observing z w and then y is taken thus depending on x and z w Accordingly x and y are called first and second stage decisions respectively X and Y are polyhedra possibly involving integer requirements to some vector components z is a random vector on some probability space Note that also c q T and W may have stochast
8. e uses To use a multiplier file the parameter INITMULT has to occur in the specification file followed by the path of the file 8 Output 8 1 Output on screen F igure 5 shows two typical lines of output as produced by ddsip vSD Hopefully the meaning of the single entries is rather straight forward Here is a short explanation 14 Nodes Left Objective Strategy Heuristic Best Value Bound Gap Time 11 5 25 2384 CB 25 9449 25 8430 24 9897 3 3 0 25 Figure 5 Output lines Nodes counts the number of nodes generated in the tree Left counts the number of nodes in the front tree Objective is the lower bound of the current node Strategy is the information which lower bounding strategy was used Heuristic is the upper bound returned by the heuristic Best Value is the overall upper bound Bound is the overall lower bound Gap is the relative gap between Best Value and Bound Time is the CPU time passed since invoking the program The pruning of nodes is indicated by the entry cutoff in the row Objective The row Heuris tic may also contain the entries n stop inferiority evaluation stopped at n th scenario or multiple a solution has been evaluated previously 8 2 Output in the file szp out All output files will be placed in the subdirectories sipout and debug of the current directory These directories will be created if they do not exist A further run of ddsip vSD overwrites the existing output files The
9. equivalent with fixed variables if the decomposition algorithm exited normally and if DETEQU TEST were set to 1 9 Licence and bug 9 1 Licence The program is free software It is distributed under the GNU General Public License as published by the Free Software Foundation see D 9 2 Bug report Please report bugs via email to gotzes math uni duisburg de and neiseQ math uni duisburg de If possible include the input files to make the error reproducible 16 A Sample specs file Parameters to specify the model FIRSTCON FIRSTVAR SECCON SECVAR SCENARIOS STOCRHS STOCMAT 9 30 280 326 5 70 0 First stage constraints First stage variables Second stage constraints Second stage variables Number of scenarios Number of stochastic rhs elements Number of stochastic matrix entries Parameters for dual decomposition procedure OUTLEVEL OUTFILES STARTINFO NODELIM TIMELIM HEURISTIC ABSOLUTE RELATIVE PORDER BRADIR BRASTRAT BOUSTRAT EPSILON LOGFREQ INTFIRST ACCURACY NULLDISP QUANTILES NLB VIS TEST DETEQU DOMINANCE REFERENCE SCALEREF MREFSCALE 5 1 0 90 800 0 001 2 test ref 0 Print info to more out Print files models and output Use start solution bounds Node limit for the outer b amp b ddsip vSD time limit Heuristic to produce a feasible solution Absolute duality gap Relative duality gap Use branching priority order Bra
10. gTa gt clat q y UIk lt dk Vl Vk Trz Wy 2 V1 7 Xi TVk lt E d d Vk LEX yEY VIE gt O VI Vk The program is a large scale deterministic mixed integer linear program with a block angular structured constraint matrix Note that the K multiplicity of the second stage vari ables and of the second stage constraints as in is not necessary since if the problems there are solved chose y arg min KAiC yik and is also solved And if 7 is solved choose yik yi Vk 1 K in the deterministic equivalents in TIl By introducing scenario many copies x l 1 L of the first stage variables an equivalent formulation of 7 is given by EE mv lt E d dg 8 x1 y1 Mi VL Wk r1 EX T wr tw E X T we 2 2 cre X T wy Nonanticipativity Ekim vr lt E d d Yk Figure 1 Structure of the constraint matrix where for l 1 L M i m EXxY Avy 20 such that cla qly vik lt dk VIVE 9 T Wy 2 Vl Vk Considering the constraint matrix of 8 we can identify L single scenario subproblems solely coupled by the equality constraints nonanticipativity on the copies of the first stage variables and the dominance modelling constraint xx including second stage variables be longing to different scenarios The problem decomposes when we relax t
11. ge variables have to be placed at the beginning of the COLUMNS section of the mps file and their names have to end with the identifier 01 They are followed by all second stage variables e The last variable in the COLUMNS section has to be a nonnegative continuous variable which is interpreted as the variable v e For first order stochastic dominance the constraint c a q y v lt d has to be modified according to c a q y M 60 lt d M has to be appropriately chosen by the user and the last variable in the COLUMNS section has to be a binary variable instead of a nonnegative continuous variable cf 11 Below there is a small example model file with 1 first stage constraint gt 2 first stage variables 2 nonnegative continuous variables 3 second stage constraints gt lt lt 1 with stochastic right hand side and 1 with stochastic matrix entries and 3 second stage variables 1 binary variable and 2 nonnegative continuous variables We recommend to built up the model file with some modelling language interpreter as ILOG OPL Studio free trial on 13 or the free software Zimpl by Thorsten Koch 26 To postprocess the mps file pick a text editor of your choice For instance vi has nice functions to easily achieve the special format that is needed by our software and can be found on any Unix Linux distribution e Note that the constraint m i Vik lt does not occur in the model It is added during the algori
12. he case of multiple dominance constraints is also covered Multiple first order constraints fre 1 di i 1 N can be expressed through a single dominance constraint fz 1 d by choosing d equal the random variable whose distribution function is the pointwise maximum of the distribution functions of the d For the case of multiple second order constraints we refer the reader to Theorem 3 2 in 18 In and the authors have shown that 6 can be approximated through discrete approximations of fy and d if their range is not a finite set by nature On the other hand 6 can be shown to be equivalent to deterministic block structured large scale mixed integer linear programs in the case of finitely many realizations of f and d cf 11 However these so called deterministic equivalents quickly become extraordinary large and can often not be tackled with standard solvers alone such that the application of the described scenario decomposition method might be useful Note that there exists a more efficient algorithm for the treatment of first order models with a linear second stage This method uses duality theory and is described in 7 We briefly discuss the implemented algorithm for the second order case The treatment of first order instances is basically the same Assume a finite number of scenarios i e z Q z1 2z with corresponding probabilities 7 is given and that g in 6 is linear Then cf 10 problem 6 turns into min f
13. he nonanticipativity some most are omitted some can be treated with Lagrangean relaxation and the K con straints L X mwg lt E d dx 1 1 The structure of the constraint matrix is sloppily pictured in Figure I Here stochastic matrix entries are considered Stochastic cost coefficients are also present since the constraints cla q y vm lt dk and the matrices T and W are condensed in T and W now with scenario index and hence possibly changing from scenario to scenario We get a lower bound by solving the Lagrangean dual which is a nonlinear concave maximization carried out with Helmberg s bundle method I2 n Dies mg at Diba Zea A T vie m E d de 5 pea Uml 1 71 Tim1 Til xy E Mi VI ZLD max AER weRM 2 1 10 4 L Yommint g max 7 min g XI AER weRM L 1 YL Arlu E d de 11 sy Vml Liml x y E M where i J v Mml 1 au for t 1 m HUml 1 forl gt 2 The number M of first stage variables whose nonanticipativity constraints are treated with Lagrangean Relaxation has to be specified after the identifier RELNA in the specification file In the current node the M L 1 nonanticipativity constraints of the M variables 7 with the biggest dispersion in the father of the current node are treated with Lagrangean Relaxation Another rather simple method to obtain a lower bound is to s
14. her Annals of Mathematical Statistics 18 1947 50 60 M ller A Stoyan D Comparison Methods for Stochastic Models and Risks Wiley Chichester 2002 Prekopa A Stochastic Programming Kluwer Dordrecht 1995 Schultz R Tiedemann S Conditional value at risk in stochastic programs with mixed integer recourse Mathematical Programming 105 2006 pp 365 386 19 25 Schultz R Tiedemann S Risk Aversion via Excess Probabilities in Stochastic Pro grams with Mixed Integer Recourse SIAM Journal on Optimization 14 2003 pp 115 138 26 http www zib de koch zimp1 20
15. i 1 th number 1 lt i lt r following pos is treated as row index and the 27 th number as column index of the i th entry of the individual scenarios 13 The program siphelp makes things a lot easier and can be obtained from our workgroup The file containing the information what the benchmark distribution looks like plays a promi nent role It should consist of two columns e First Column contains the probabilities that d attains d fork 1 K e Second Column contains the corresponding realizations d for k 1 K These pairs do not have to be sorted but the probabilities should sum up to 1 7 Optional files 7 1 Start information file Start information can be provided as displayed in Figure 4 Hereby BEST should be an upper BEST 2345 BOUND 2000 SOLUTION 1 2 Figure 4 File with start values bound BOUND a lower bound and SOLUTION a feasible first stage solution The user has to care about the consistency of the data 7 2 The priority order file The priority order for the branching in the master problem is specified by passing a file to ddsip vSD The file has two columns where the first contains indices of first stage variables and the second integer values High values lead to early branching 7 3 The multiplier file The multiplier file has one column with as many nonnegative values as the benchmark profile has realizations It specifies the initial multipliers that Conic Bundl
16. ic entries and that this case is also covered by our implementation Furthermore besides other implicit regularity assumptions 17 all objects in may have conformal dimensions The mentioned two stage dynamics becomes explicit by the following reformulation of min ez min q y Wy z w Tr yE EY x x x y min c z w Tx cE xX 2 where S t min q y Wy t y Y 3 The function called the value function of the mixed integer linear program min g y Wy t yE Y has been studied in parametric optimization 2 4 In view of 2 the random optimization problem gives rise to the family of random variables 4 Thus every first stage decision x X induces a random variable f w c z w Tz Traditional two stage stochastic programming aims at optimizing nonanticipative decisions i e finding a best x or in other words a best member in the family of random variables For the specification of best statistical parameters reflecting mean and or risk are used Employing the weighted sum of E and some risk measure R leads to mean risk models cf 1 B 8 16 23 24 25 ca z w Ta min E f p R fre LEX p gt 0 fixed 5 Here we take an alternative view Rather than heading for best members of 4 we want to identify acceptable members and optimize over them This leads to the new class of
17. ing up is preferred BOUSTR Int 0 2 0 In order to improve bounds the node with the worst lower bound is chosen 1 Width first strategy Node with smallest index is chosen 2 Depth first strategy Node with largest fa ther index is chosen BRASTR Int 0 1 0 Use the average of lower and upper bound in father node as branching value 1 Use the weighted average of the scenario solutions of the component as branching value INTFIR Int 0 1 1 Branch first on integer variables despite of smaller DISPNORM EPSILO Dbl 0 0 Specifies disjoint subdomains if continuous components are branched NULLDI Dbl 1 0 Branch nodes only if their dispersion norm is greater than NULLDI VIS Int 0 2 1 Visualization of the Branch amp Bound tree of the subdivision of X 0 no visualization 1 pdf file sipout bbtree pdf is written just before termination 2 visualization is done on the fly This might be very time consuming espe To be continued on the next page Name Type Default Description NLB 4 4 Heuristics Int cially when the nodes are solved very quickly It is interesting to watch Use gv watch bbtree ps in the direc tory sipout during the computation Note that it is necessary to have the Graphviz package installed See I5 for more information Yellow nodes multiple Red nodes cutoff Green nodes otimallity 0 Specifies the use of the simple lower bound ing procedure ta
18. ke maximum of the sub solutions all Lagrangean multipliers equal to 0 described before 3 use the simple procedure and CB only in every i th node where i is the specified number 2 use only the simple procedure 1 use the simple procedure only in node 0 and CB in all nodes 0 use only CB 1 use CB and the simple procedure in every i th node where 7 is the speci fied number Table 2 Branch and bound parameters The decomposition algorithm uses a heuristic to guess feasible first stage solutions based on the solutions of the subproblems in the current node The heuristic is set by means of the parameter HEURIS The possible values of HEURIS are listed in the following table Value Description 1 3 The average of the subsolutions is used Integer components are rounded down The average of the subsolutions is used Integer components are rounded up The average of the subsolutions is used Integer components are rounded to the next integer The subsolution occurring most frequently is used To be continued on the next page 10 Value Description 5 Oo ao N QOQ 12 13 14 99 The solution of a subscenario that is closest l norm to average is used Apply heuristic 3 and 5 alternating Solution with best objective value Solution with worst objective value Solution with minimal sum of first stage variables Solution with maximal sum of first stage variables Try a
19. ll subsolutions Solve a randomly selected scenario with high precision the remain ing ones with low Use solution of the first scenario Special heuristic sipheurchanged c has to be changed and recom piled for special requirements Table 3 Values of parameter HEURIS 4 5 Parameters for the dual method Name Type Range Default Description CBITLI Int 0 oo Iteration limit descent steps CBTOTI Int 0 oo Iteration limit descent and null steps CBPREC Dbl 0 le 7 Precision of bundle method INITMULT String Path of file with multipliers initially used by Conic Bundle RELNA String Number of first stage variables whose nonanticipativity constraints are treated with Lagrangean Relaxation Table 4 ConicBundle parameters 5 The model file The model file contains the single scenario model in the mps format 14 e The sense and names of the first stage constraints constraints only involving first stage variables have to be placed after N obj the objective function at the beginning of the ROWS section of the mps file 11 e The names of the first stage constraints have to be followed by the names of the second stage constraint with a stochastic right hand side e Then all other second stage constraints follow e At the end of the ROWS section the name of the constraint c a q y v lt dhas to be put Here d is an arbitrary value since it is adjusted by the decomposition method e The first sta
20. nching direction Branching strategy Bounding strategy Epsilon used for branching on real variables Output log frequency Branch on integers first Accuracy used to compare real values Tolerance level for null dispersion used together with ACCURACY Number of Quantiles printed out at the end Node interval for simple lower bound procedure Visualization of the b amp b procedure Write out deterministic equivalent with fixed variables Write out the deterministic equivalent Dominance model Path of the file that specifies the benchmark SCALEREF is added to every outcome of d It can be made easier or harder to be fulfilled by this value every outcome of d is multiplied by MREFSCALE It can be made easier or harder to be fulfilled by this value 17 INITMULT mult Path of the file that specifies initial multipliers TRIVIALUB 10000 Value that is interpreted as infinity by the dual method dual method in the current node stops when lower bound exceeds TRIVIALUB and the lower bound is set to infinity OBJISINT 0 Ifthe objective value is integral the dual method rounds its solutions up to the next integer RELNA 0 Number of variables that are treated with Lagrangean Relaxation CPLEX Parameters See CPLEX manual 14 CPLEXBEGIN 1035 0 Output on screen indicator 2009 0 31 Relative gap CPLEXUB 1035 1 Output on screen indicator for upper bounds CPLEXEND Pa
21. olve each subproblem with all multipliers equal to zero and to pick the maximal objective value of the subproblems as a lower bound This works since all subproblems are relaxations of the full problem Upper bounds on the optimal value can be obtained by heuristics based on the solutions for the subproblems from the lower bounding procedure Let a promising candidate received by some heuristic cf Section We check the feasibility of z and push down the sik simultaneously to fulfill 12 with the L auxiliary problems K min 2 Sik cl q y siz lt dk k 1 Tz Wyi i yi E Y sip 2 gt 0 k 1 K If they are feasible for alli 1 L we still have to check whether S X Ti sip lt E d di Yk 1 K 12 i l If these constraints are fulfilled we compute the upper bound g z We elaborate a branch and bound algorithm that uses the described bounding procedures and successively reestablishes the equality of the components of the first stage vector By P we denote a list of problems and pzg P is a lower bound for the optimal value of P P Moreover denotes the currently best upper bound to the optimal value of 7 and X P is the element in the partition of X belonging to P Algorithm 2 1 STEP 1 INITIALIZATION Let P 7 and 00 STEP 2 TERMINATION If P 0 then the T that yielded g z is optimal STEP 3 BOUNDING Select and delete a problem P from P Compute
22. r rent node stops when lower bound ex ceeds TRIVIALUB and the lower bound is set to infinity SCALEREF Dbl 3 0 SCALEREF is added to every outcome of d It can be made easier or harder to be fulfilled by this value Table 1 Output and termination parameters So far all termination parameters are static in the sense that they cannot be changed during the branch and bound algorithm Therefore a careful trade off between these parameters and the termination parameters of the bundle method see Section is essential for the numerical performance cf 6 Parameters that effect the behavior of the branch and bound algorithm are compiled in Ta ble 2 When confusion is possible the default values are marked with a star The use of start values is described in Section the use of priority order information in Section The dispersion norm of a node is calculated as max max xij min xij where x denotes the i th component of the firststage part of the solution of the j th scenario Nodes with a dispersion norm smaller than NULLDI are considered as leaves of the complete enumeration tree Name Type Range Default Description PORDER Int 0 1 0 Use priority order for branching If this parameter is 1 then the priority order file needs to be specified STARTI Int 0 1 0 Use start information If this parameter is 1 a file containing the start values needs to be specified BRADIR Int 1 1 1 Branching down is preferred 1 Branch
23. rameters specifying the use of ConicBundle CBITLIM 20 Limit for number of descent steps in Conic Bundle CBTOTIT 1000 Limit for the total number of Conic Bundle iterations incl nullsteps Specification file References 1 Ahmed S Convexity and decomposition of mean risk stochastic programs Mathemat ical Programming 106 2006 433 446 2 Bank B Mandel R Parametric Integer Optimization Akademie Verlag Berlin 1988 3 Birge J R Louveaux F V Introduction to Stochastic Programming Springer New York 2000 4 Blair C E Jeroslow R G The value function of a mixed integer program I Discrete Mathematics 19 1977 121 138 5 Car e C C Schultz R Dual Decomposition in Stochastic Integer Programming Op erations Research Letters 24 pp 37 45 1999 6 Car e C C Schultz R A two stage stochastic program for unit commitment under uncertainty in a hydro thermal power system Konrad Zuse Zentrum ftir Information stechnik Berlin Preprint SC 98 11 1998 18 7 Drapkin D Schultz R A Decomposition Algorithm for Stochastic Programs with 12 13 14 15 16 17 18 19 20 21 22 23 24 First Order Dominance Constraints Induced by Linear Recourse Preprint 653 2007 Department of Mathematics University of Duisburg essen 2007 Eichhorn A R misch W Polyhedral risk measures in stochastic programming SIAM Journal on Optimization 16 2005 pp
24. thm e The constraint c a q y v lt d has to occur only once independently on the number of reference outcomes N obj G FirCon G StocRhsSecCon L StocMatSecCon L cx_qy COLUMNS x1_01 obj 1 x1_01 FirCon 1 x1_01 StocMatSecCon 1 x1_01 cx_qy 1 x2_01 FirCon 1 MARKOOOO MARKER gt INTORG 12 y StocRhsSecCon 1 y StocMatSecCon 1 y cx_qy 1 MARKOOO1 MARKER gt INTEND Zz StocRhsSecCon 1 Zz StocMatSecCon 1 v cx_qy 1 RHS rhs FirCon rhs StocRhsSecCon 1 rhs StocMatSecCon 30 rhs cx_qy 100 BOUNDS UP bnd y 1 ENDATA 6 The scenario files and the benchmark file Figure 3 displays the different scenario files right hand sides matrix entries benchmark distribution scenariol position 0 1 200 0 05 1 23 186 0 15 34 0 25 4 scenarioL scenariol 0 1 15 0 1 23 30 34 Al scenarioL 30 Al Figure 3 Format of the scenario files In the right hand side scenario file the first number after the identifier sce is the scenario probability For problems without stochastic right hand sides this file contains only the probabilities of the individual scenarios In order to assign the stochastic right hand sides to constraints the constraints have to be grouped in the model file cf Section The matrix scenario file requires additionally a row and column index for each stochastic matrix coefficient see Figure The identifier for this index is pos If r is the number of stochastic matrix entries the 2
25. tion or a lower bound A comfortable way to invoke the program on a Unix system is the command ddsip vSD lt files2sip where the file files2sip may contain the lines displayed in Figure sip in model mps model ord rhs sc matrix sc order dat start in Figure 2 Input file 4 The specification file 4 1 Parameters for the dominance constrained model A sample specification file is given in Appendix A Hopefully the identifiers in the first part of this file are self explaining Otherwise they should become clear when consulting the two stage chapter of one of the standard text books on stochastic programming see 23 Some of the identifiers as e g FIRSTVAR are redundant They serve to check consistency with the model file 4 2 CPLEX parameters The CPLEX parameters have to be specified behind the indicator CPLEXBEGIN The lines have to start with the CPLEX parameter number followed by the parameter value cf Ap pendix A The parameter number corresponds to the values defined in the CPLEX callable library For the evaluation of upper bounds the parameter values can be overwritten after the identifier CPLEXUB The CPLEX parameter section has to end with the identifier CPLEX END Parameters not present in this chapter are set according to their CPLEX default values cf 14 4 3 Parameters for the decomposition procedure The parameters that effect the amount of output and the termination behavior are listed in
Download Pdf Manuals
Related Search