User's Guide to ddsip – A C Package for the Dual Decomposition of
Contents
1. 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 A UV Ne e Time is the total CPU time needed by ddsip 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 e FEV is the solution of the EEV problem according to Birge and Louveaux 1997 e VSS is the value of stochastic programming according to Birge and Lou veaux 1997 e Expectedvalue is the expected value e Riskmeasure is the value of the used risk measure 18 8 3 Other output files The number of additional output files and their content is ruled via the param eters OUTFIL and OUTLEV Values of OUTFIL greater than 1 are intended for debugging purposes e The file more out contains more or less information depending on the pa rameter OUTLEV e g the subproblem solutions the branch and bound tree and the objective function composition e The file solution out contains information on the solution with the optimal first stage solution among them It is not written when OUTFILES is set to 0 e If OUTFILES is greater than 1 then in addition the fol2. ao NID Ot Standard deviation d Table 7 Risk models Positive values of RISKMO implement the model min EX aRX negative ones the risk model min RX These pure risk models are often harder to solve For the mean absolute semideviation model the TARGET has to be set less or equal the optimal expected value when using RISKALG 0 cf Markert 2004 13 4 6 Parameters for the dual method There is no description of ConicBundle available yet We refer to Helmberg 2000 where the used method is described in the context of semidefinite pro gramming Below we only explain the parameters defined in our implementa tion The dual method cannot be used in combination with the algorithm based on the FSD consistency of the risk measure cf Markert 2004 The user has to take care about this detail The use of stochastic cost coefficient in combination with the Lagrangian dual is not supported yet We recommend to reformulate the problem by an additional variable and an additional constraint representing the objective func tion This leads to a stochastic matrix Name Type Range Default Description CBFREQ Int 3 0 Use ConicBundle in every ith node Negative numbers are interpreted as i th node plus preceding one CBITLI Int 0 90 Iteration limit descent steps CBRITLI Int 0 CBITLIM 10 Iteration limit in root node descent steps CBTOTI Int 0 5000 Iteration limit total iterations i e de scent
3. limit CPLEXUB 2058 3 MIP emphasis 2031 10 heuristic frequency 1039 750 Time limit 2009 0 001 Relative Gap CPLEX2UB 2058 4 MIP emphasis 2031 15 heuristic frequency 2061 60 RINS neighbourhood search heuristic frequency 1039 300 Time limit CPLEXDUAL 2009 le 4 Relative gap for Lagrangian Dual 1035 0 Output on screen indicator for Lagrangian dual CPLEXEND Parameters specifying the use of ConicBundle CBFREQ 1000 Conic Bundle in every i th node CBITLIM 20 Limit for number of descent steps in Conic Bundle CBTOTIT 1000 Limit for total number of CB iterations incl nullsteps NONANT 2 Nonanticipativity representation CBPRINT 1 Output level of Conic Bundle CBBUNS 200 Maximal bundle size CBMAXS 10 Maximal number of subgradients CBWEIGHT 5 Conic Bundle initial weight Specification file 22 References Ahmed S M Tawarmalani N V Sahinidis 2000 A Finite Branch and Bound Algorithm for Two Stage Stochastic Integer Programs Stochastic Pro gramming E Print Series http www speps info Beale E M L 1955 On Minimizing a Convex Function Subject to Linear Inequalities Journal of Royal Statistical Society 17 pp 173 184 Birge J R F V Louveaux 1997 Introduction to Stochastic Programming Springer New York Carge C C R Schultz 1999 Dual Decomposition in Stochastic Integer Pro gramming Operations Research Letters 24 pp 37 45 Carge C C R Schultz 1
4. sections beginning with CPLEX2LB CPLEX2UB or CPLEX2DUAL are specified The CPLEX parameter section has to end with the identifier CPLEXEND Parameters not present in the mentioned chapters are set according to their CPLEX default values cf CPLEX 2002 4 3 Parameters for the decomposition procedure The parameters that effect the amount of output and the termination behavior are listed in the table below The first column of the table contains the name of the parameter the second one specifies whether it is an integer or a real Dbl parameter and the last column explains the parameter s meaning The signal SIGTERM as defined on LINUX UNIX environments is han dled by the program other signals are not handled separately SIGTERM causes the termination of ddsip after solving the current subproblem 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 4 6 is essential for the numerical performance cf Carge and Schultz 1998 Parameters that effect the behavior of the branch and bound algorithm are compiled in the Tables 2 and 3 The default values are marked with a star The use of start values is described in Section 7 1 the use of priority order information in Section 7 2 The parameter RELAXL effects the relaxation levels during the eva
5. specifications of the stochastic pro gram some CPLEX and b amp b parameters e Model file a file readable by CPLEX e g lp or mps format possibly in gzipped form that specifies the single scenario model e Priority order file for subproblems optional a CPLEX order file corre sponding to the model file e RHS scenario file a file containing the stochastic right hand sides and the probabilities of the scenarios e Cost scenario file optional a file containing stochastic cost coefficients e Matrix scenario file optional a file containing stochastic matrix entries e Priority order file for master optional a file containing a branching order for the master branch and bound procedure e Start information file optional a file containing start informations such as a feasible solution and or a lower bound A comfortable way to invoke the program on a Unix system is the command ddsip lt files2sip where the file files2sip may contain the lines displayed in Figure 2 sip in model lp model ord rhs sc cost sc matrix sc order dat start in Figure 2 Input file 4 The specification file Comments could be included anywhere in this file An Asterisk identifies the beginning of a comment until the end of the line This way explanations could be included and parameter lines temporarily inactivated the latter could not be used in the CPLEX parameter section Keywords are accepted if their start matches the str
6. stage variable values Gap is the relative gap between Best Value and Bound Wall Time gives the wall time passed since invoking the program CPU Time gives the CPU time passed since invoking the program Father gives the number of the father node 17 The pruning of nodes is indicated by the entry cutoff in the row Objective The row Heuristic may also contain the entries n stop inferiority evaluation stopped at n th scenario or multiple a solution has been evaluated previously When more than one solution is evaluated in a branch and bound step the entry indicates the status of the last solution An asterisk in the first position indicates that a new best value was found In the example a list of heuristics is used in every node the lines beginning with an asterisk indicate which heuristic found a new best solution If the scenario solutions of a node fulfil the nonanticipativiy and yield a new best upper bound in the output line for the node an asterisk is prepended too 8 2 Output in the file szp out All output files will be placed in the subdirectory sipout of the current directory This directory will be created if it does not exist A further run of ddsip overwrites the existing output files The output on screen is also directed to the file more out in case OUTLEV gt 51 In addition this file contains the parameters read and some information on the solution e The value of Status indicates the solution status
7. 4848 188 5 2 7888 Oh 00 10 Oh 00 10 4 6 y 4 44854 2998 infeasible 44854 299 3 2 7888 Oh 00 12 Oh 00 12 4 7 9 5 Heuristic 2 66346 70463 66346 70463 Oh 00 14 Oh 00 13 T 9 5 45712 4035 66346 70463 66346 70463 44854 299 6 2 7888 32 39 Oh 00 14 Oh 00 13 6 8 9 5 Heuristic 2 44864 77749 44864 77749 Oh 00 16 Oh 00 16 8 9 1 44859 2107 44864 77749 44864 77749 44859 210 2 2 7888 0 0124 Oh 00 16 Oh 00 16 6 9 11 1 cutoff 44864 77749 44859 210 0 0124 Oh 00 17 Oh 00 17 8 10 11 1 44863 2847 44865 25242 44864 77749 44863 284 1 2 7888 0 00332 Oh 00 20 Oh 00 19 8 11 13 2 44864 4325 44865 05453 44864 77749 44863 284 1 1 162 0 00332 Oh 00 22 Oh 00 21 10 12 13 2 Heuristic 12 44864 65876 44864 65876 Oh 00 24 Oh 00 23 12 13 2 Heuristic 3 44864 38172 44864 38172 Oh 00 25 Oh 00 24 12 13 1 44863 5109 44864 38172 44864 38172 44863 510 1 1 6268 0 00194 Oh 00 25 Oh 00 24 10 13 15 2 44864 1805 44864 54332 44864 38172 44863 510 1 0 67783 0 00194 Oh 00 27 Oh 00 26 12 straightforward Here is a short explanation Node gives the number of the currently solved node 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 Heuristic is the upper bound returned by the heuristic Best Value is the overall upper bound Bound is the overall lower bound Viol is the number of variables violationg the nonanticipativity Dispersion is the greatest difference of first
8. 998 A two stage stochastic program for unit com mitment under uncertainty in a hydro thermal power system Konrad Zuse Zentrum fiir Informationstechnik Berlin Preprint SC 98 11 Dantzig G B 1955 Linear Programming under Uncertainty Management Science 1 pp 197 206 GNU Project 2004 http www gnu org C Helmberg 2004 http www user tu chemnitz de helmberg C Helmberg 2000 Semidefinite Programming for Combinatorial Optimiza tion ZIB Report ZR 00 34 Konrad Zuse Zentrum Berlin ILOG 2002 ILOG CPLEX 8 0 Reference Manual ILOG Gentilly France Kall P S W Wallace 1994 Stochastic Programming Wiley Chichester Laporte G F V Louveaux 1993 The Integer L Shape Method for Stochastic Integer Programs with Complete Recourse Operations Research Letters 13 pp 133 142 Louveaux F V R Schultz 2003 Stochastic Integer Programming In A Ruszczynski A Shapiro Eds Stochastic Programming Elsevier North Holland A Markert 2004 Deviation Measures in Stochastic Programming with Mixed Integer Recourse Doctoral thesis Institute of Mathematics University Duisburg Essen Campus Duisburg Ogryszak W A Ruszczinsky 1999 From Stochastic Dominance to Mean Risk Models Semideviations as Risk Measures European Journal of Opera tions Research 116 33 50 Prekopa A 1995 Stochastic Programming Kluwer Dordrecht 23 Schultz R S Tiedemann 2003 Risk Aversion via Excess Pr
9. LIER a Lagrangian multiplier Any item of these four different informations may be left out The user has to care for the consistency of the data 16 7 2 The priority order files If indicated by setting the CPLEX parameter CPX_PARAM_MIPORDIND the name of a CPLEX branching order file to be used for the scenario problems has to be specified following the name of the model file named model ord in Figure 2 Its format is described in the CPLEX manual If the parameter PORDER is set a file with branching order information for the master problem has to be given named order dat in Figure 2 The file has two columns whereby the first one contains indices starting with 0 as in the output of siphelp of first stage variables and the second one integer values High values lead to early branching 8 Output 8 1 Output on screen The following shows typical lines of output as produced by ddsip accuracy of the values cut due to line length The meaning of the single entries is rather Node Nodes Left Objective Heuristic Best Value Bound Viol Dispersion Gap Wall Time CPU Time Father 0 aL 1 44841 3565 infeasible 44841 356 5 3 Oh 00 03 Oh 00 03 1 T 3 2 47944 6273 infeasible 44841 356 7 2 7888 Oh 00 06 Oh 00 06 0 2 3 2 44844 5722 infeasible 44844 572 5 2 7888 Oh 00 07 Oh 00 07 0O 3 5 3 44953 0125 infeasible 44844 572 7 2 7888 Oh 00 09 Oh 00 08 2 4 5 3 44848 1886 multiple 44848 188 4 2 7888 Oh 00 09 Oh 00 09 2 5 7 4 45549 6459 infeasible 4
10. Markert 2004 T W Ts Ws H Figure 1 Constraints of 6 Assume we are given a finite number of scenarios j 1 S with corresponding probabilities 7 Then problem 4 turns into S min Aca TjqjYj Tjx Wiyj hj Vi 5 rex yjEZ XR j l cf Birge and Louveaux 1997 Kall and Wallace 1994 and Prekopa 1995 The so called expected recourse function Qg reads S Qrla cj min mgu Tie Wiyj hji Vj yjEZ xR j for all x R The program 5 is a large scale deterministic mixed integer linear program MILP with a block angular structure A recent and compre hensive overview of existing algorithms for problem 5 is provided in Louveaux and Schultz 2003 To mention some of the algorithmic approaches we refer to van der Vlerk 1995 for simple recourse models W I I to Laporte and Louveaux 1993 for two stage models with a binary first stage and to Ahmed et al 2000 for models with an integer second stage and a fixed technology matrix T An algorithm for problem 5 in its general form has been proposed in Carge and Schultz 1999 It works on the expense of a branching on con tinuous first stage variables The latter algorithm is implemented in ddsip and described in what follows By introducing copies of the first stage variables an equivalent formulation of 5 is given by s min 15 CjXj qjyj x1 28 j yj E
11. Mj Vi 6 J133 5 j l where M y5 Tj j Wjyj hj xj E X yj ek lyas Considering the constraint matrix of 6 cf Figure 1 we can identify S single scenario subproblems solely coupled by the equality nonanticipativity constraints on the copies of the first stage variables and written as y Hyjx 0 where H H1 Hj The problem decomposes when we relax the non anticipativity constraints Upper bounds on the optimal value can be obtained by heuristics based on the solutions for the subproblems We get a lower bound by solving the Lagrangian dual which is a nonlinear concave maximization S S ZLD max min cia ore qjyj AS Hir j Yj Mj Vi 7 iYi E j 1 j l In general the involved integrality restrictions lead to an optimality gap If we are not satisfied with the bounds given by the above method we can elaborate a branch and bound algorithm that successively reestablishes the equality of the components of the first stage vector Let P denote a list of problems Algorithm SD Scenario decomposition Carge and Schultz 1999 STEP 1 Initialization Set z oo and let P consist of problem 5 STEP 2 Termination If P then x with z Qg a is optimal STEP 3 Node selection Select and delete a problem P from P and solve its Lagrangian dual If the associated optimal value z p P equals infinity infeasibility of a subproblem go to STEP 2 STEP 4 Bounding If z p P
12. OQ0 determines the pe riod of bounding steps with changing tolerances for sufficiently small TOLSMA Int 1 PERIOD 16 for BOUSTRAT gt 0 determines the number of steps in each period with a small tolerance continued on next page 10 continued from previous page Name Type Range Default Description ACCURA Dbl 5e 16 1 le 14 Accuracy real values are considered equal if the absolute value of their dif ference is less than accuracy EPSILO Dbl 0 le 14 Specifies disjoint subdomains if continu ous components are branched NULLDI Dbl 0 le 14 Branch nodes only if their dispersion norm is greater than NULLDI KAPPA Int 0 2 0 No gathering of kappa values by CPLEX Int 1 sample gathering of kappa values by CPLEX and reporting Int 2 full gathering of kappa values by CPLEX and reporting RELAXL Int 0 2 0 No integrality relaxation 1 Relax first stage variables 2 Relax first and second stage variables QUANTI Int 0 10 Number of Quantiles to be displayed at the end MAXINH Int 0 5 maximal level of inheritance of solutions in lower bounding HEURIS Int 0 13 99 3 choice of heuristics cf Table 5 Table 3 Branch and bound parameters The MAXINHERIT parameter specifies a maximal level of passing on solu tions and bounds in the B amp B tree for the lower bound step This facility is in terrupted by an invocation of the conic bundle algorithm which will change the Lagrangian multipliers I
13. R amp x RS is defined on the probability space Q IP A The set X C x R Ax b contains all deterministic constraints on Inequality constraints can be handled in 1 by the introduction of appropriate slack variables The model 1 is also referred to as two stage model We note that the problem 1 is not yet well defined As the constraints include random parameters the meaning of feasibility and thus of optimality is not clear We complete the recourse model by adding an objective function criterion Before we do so we rewrite problem 1 as inf c w x z w 2 where o w dey T w x W w y hw 3 We note that provided R x Q is measurable we can regard Z c w x o a w a X as a family of random variables Now each function R Z gt R e g the expected value some measure of risk or a weighted sum of both can serve as objective criterion inf Ri c w a a w 4 rex Our focus is on integer models i e in addition to the constraints employed in problem 1 we may have integrality requirements on the variables x and y Note that models with a linear second stage should be dealt with a version of the L shaped algorithm see Birge and Louveaux 1997 We briefly discuss the implemented algorithm for the expected value case i e Ric w x a w Ele w x o x w ewe 2 w IPdw Further algorithms suitable for the treatment of mean risk models are described in
14. RISKMOD TARGET WEIGHT RISKBM BRAETA 5 1 0 0 90 800 99 3 4 1 0 0 001 1 le 3 le 0 le 4 Print info to more out Print files models and output Use start solution bound Sort scenarios ddsip node limit ddsip time limit Heuristic to produce a feasible solution Solve EEV cf Birge and Louveaux 1997 Absolute duality gap Relative duality gap Use branching priority order Branching direction Branching strategy Bounding strategy Epsilon used for branching on real variables Relaxation level 1 relax first stage variables in scenario problems Output log frequency Branching on integers first Accuracy used to compare real values Tolerance level for null dispersion used together with ACCURACY Number of Quantiles Risk model Target for target measures Weight of the risk term Big M used in modeling risk models 2 and 5 Branch on auxiliary variable eta models 4 and 5 21 CPLEX Parameters See CPLEX manual CPLEX 2002 CPLEXBEGIN 1035 1 Output on screen indicator 2009 le 7 Relative gap CPLEXEEV 2009 0 1 Relative gap for EEV CPLEXLB 2058 3 MIP emphasis 2031 10 heuristic frequency 2009 0 002 Relative Gap 1039 900 Time limit CPLEX2LB 2058 4 MIP emphasis 2031 5 heuristic frequency 2061 20 RINS neighbourhood search heuristic frequency 2009 le 6 Relative Gap 1039 350 Time
15. Ruszczynski 1999 here expected shortfall below target ex cess probabilities as investigated in Schultz and Tiedemann 2003 absolute semideviation worst case costs tail value at risk value at risk and standard deviation The code is of research quality i e no production quality should be expected with respect to stability and efficiency We kindly ask the user to support us fixing bugs by reporting them to us as they occur We did not include support for the SMPS format but a rather basic input format is implemented which is not very handy with stochastic matrix entries Any contributions in this respect are welcome Our code only supports the scenario formulation This manual describes the format of the input files and the data contained in the output files of ddsip We try to provide all necessary information on the input parameters 2 Stochastic programs with mixed integer recourse This implementation is appropriate to solve recourse models Such problems were first investigated by Dantzig 1955 and Beale 1955 The conceptual idea behind recourse models is the following assume the decisions are two stage in the sense that some of them say x have to be taken immediately whilst others say y may be delayed to a time when uncertainty has revealed We can write a random linear program of this type as sex ean Ole ale ule Toet Wolo O The random parameter c q T W h Q gt R x R x R x
16. User s Guide to ddsip A C Package for the Dual Decomposition of Two Stage Stochastic Programs with Mixed Integer Recourse A Markert R Gollmer Department of Mathematics University Duisburg Essen Campus Essen Thea Leymann Stra se 9 D 45127 Essen Germany ralf gollmer uni due de August 3 2015 1 Introduction ddsip is a C implementation of a number of scenario decomposition algorithms for two stage stochastic linear programs with mixed integer recourse It expects a MIP stochastic LPs are not supported The program is based on a previous Fortran 90 implementation of C C Car e Main idea of the decomposition algorithms is the Lagrangian relaxation of the nonanticipativity constraints and a branch and bound algorithm to reestablish nonanticipativity The original scenarios decomposition algorithm has been de veloped in Carge and Schultz 1999 Extensions including the treatment of mean risk models have been made in Markert 2004 For the dual optimization we use ConicBundle a C implementation kindly provided by C Helmberg see Helmberg 2004 We use the CPLEX callable library to solve the mixed integer subproblems in the branch and bound tree see CPLEX 2002 The current version of ddsip is ready for on CPLEX 12 6 2 and requires at least version 11 2 The implementation features risk minimization too This version supports mean risk models involving the risk measure expected excess of a target see Ogryczak and
17. and null steps CBPREC Dbl 0 le 14 Precision of bundle method CBPRIN Int 0 0 ConicBundle output level NONANT Int 1 3 The identity of the first stage vectors is represented by 1 1 29 01 3 L1 E En 2 U1 T2 T2 V3 Un 1 Tn 3 Piti ja j i Pir 5 Vi CBBUNS Int Less 50 Bundle size CBWEIG Dbl 0 1 Initial weight cf CB manual CBFACT Dbl 0 1 0 8 Initial weight in the next node is final 1 CBFACTOR weight in the father CBFACTOR initial weight CBINHE Int 0 1 0 Should the solutions of the father node be inherited in the initial evaluation CBCHAN Int 0 1 0 Should the tolerances and time limits be changed after a number of unsuccessful step CBSTEP Int 1 8 Maximal number of steps within a de scent step 14 Table 8 ConicBundle parameters 5 The model file The model file contains the single scenario model Its format can be one of the formats readable by CPLEX as e g the lp or mps format The gzipped forms of these files with extensions lp gz or mps gz can be used for the sake of saving disk space This is especially advisable in case OUTFIL gt 3 The first stage variables have to be identified by a prefix or a postfix ap pended to their names as specified in the specs file Variables with stochastic cost coefficients have to be placed at the beginning and according to the order in which the stochastic cost coefficients are provided in the scenario file In the presence of stochastic rig
18. d Integer components are rounded down 2 The average of the solutions is used Integer components are rounded up 3 The average of the solutions is used Integer components are rounded to the next integer 4 The solution occurring most frequently is used 5 Use the solution of a scenario that is closest J norm to average 6 The first stage solution with highest probability is chosen adding probabilities in case of identical first stage scenario solutions 7 Solution with best objective value 8 Solution with worst objective value 9 Solution with minimal sum of first stage variables 10 Solution with maximal sum of first stage variables 12 Try solutions of all scenarios 13 Apply heuristic 3 and 5 alternating 199 Indicates that a list of heuristics is given in the sequel See the example in the Appendix Table 5 Values of parameter HEURIS In order to save time the order of evaluation of the scenario problems is changed if an infeasible one is encountered Since often the same scenarios gives infeasi bility these ones are evaluated first in the sequel 4 5 Parameters for the risk model The parameters for the risk models are displayed below Some parameter set tings lead to ill posed models cf Markert 2004 ddsip provides only limited consistency checks with this respect The same holds true for the choice of an algorithm Algorithms similar to the scenario decomposition as outlined above only apply to mean
19. he weighted av erage of the scenario solutions for the chosen variable and the mean between maximal and minimal value for that variable as branching value continued on next page continued from previous page Name Type Range Default Description BRAEQU Int 0 1 1 equal distribution Among the vari ables with maximal dispersion value choose one for branching which most equally divides feasibility of scenario so lutions among both new nodes 0 unequally in 2 3 of the iterations choose a variable such that most of the scenario solutions remain feasible for one of the new nodes INTFIR Int 0 1 0 Branching exclusively according to branching rules 1 Branching on integers first BOUSTR Int 0 9 0 choose node with best bound as next node 1 heuristic among nodes with sufficiently small bound choose node with biggest dispersion norm unsolved nodes first 2 heuristic among nodes with sufficiently small bound choose node with biggest dispersion norm 3 heuristic among nodes with sufficiently small bound choose node with least number of violations unsolved nodes first 4 heuristic among nodes with sufficiently small bound choose node with least number of violations 5 9 heuristic depth first until a incumbent is found then switch to BOUSTRAT 4 10 heuristic among last four generated nodes choose node with best bound un solved nodes first PERIOD Int l 32 for BOUSTRAT gt
20. ht hand sides the constraints require a cer tain order too First stage constraint have to be followed by the constraints with stochastic right hand sides Second stage constraints without stochastic right hand sides have to be placed at the end The placing of first stage con straints in the beginning is mandatory for the construction of the deterministic equivalent too 6 The scenario files Unfortunately the program ddsip is not conform to the SMPS data format yet The proprietary data format of the scenario files is described below The identifier sce indicates the begin of the entries for the next scenario Figure 3 displays the different scenario files right hand sides cost coefficients matrix entries scenariol scenariol position 0 1 23 200 23 34 186 34 scenarioN scenarioN scenariol 0 1 30 23 30 41 34 41 scenarioN 30 41 Figure 3 Format of the scenario files In the right hand side scenario file the first number after the identifier is 15 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 con straints have to be grouped in the model file cf Section 3 The constraint section begins with the first stage constraints followed by the stochastic con straints ordered corresponding to the entries in the scenario file and closes with the second stage co
21. ings given in the tables Unknown keywords are simply ignored Lines with the first occurrence of each keyword are evaluated A sample specification file is given in Appendix A 4 1 Parameters for the two stage model Hopefully the identifiers in the first part of the file are self explaining Other wise they should become clear when consulting the two stage chapter of one of the standard text books on stochastic programming see Birge and Louveaux 1997 Kall and Wallace 1994 Prekopa 1995 Some of the identifiers as e g FIRSTVAR are redundant They serve to check consistency with the model file Either a prefix or a postfix of the variable names for identifying the first stage variables can be specified The default behaviour is to expect a postfix of the form 01 in their names Name Type Default Description FIRSTC Int 0 Number of First stage constraints FIRSTV Int 0 Number of First stage variables SECCON Int 0 Number of Second stage constraints SECVAR Int 0 Number of Second stage variables POSTFIX String none postfix for first stage variables PREFIX String none prefix for first stage variables SCENAR Int 0 Number of scenarios STOCRHS Int 0 Number of stochastic rhs elements STOCCOST Int 0 Number of stochastic cost coefficients STOCMAT Int 0 Number of stochastic matrix entries Table 1 Problem specification parameters 4 2 CPLEX parameters CPLEX parameters to be set different from their defaults have t
22. is greater than z go to STEP 2 Otherwise pro ceed as follows if the first stage solutions xj j 1 S of the subproblems are identical then set 2 min z Qp a delete all P P with z n P gt 2 and go to STEP 2 not identical then compute a suggestion Heu x1 s using some heuristic Set z min z Qg and delete all P P with zp P gt z STEP 5 Branching Select a component x of x and add two new problems to P that differ from P by the additional constraint x lt a and Lk 1 respectively if x x is integer or k lt Tik E and Tk Lak respectively if x is continuous gt 0 has to be chosen such that the two new problems have disjoint subdomains Go to STEP 3 The algorithm is finite if X is bounded and if some stopping criterion is em ployed that prevents the algorithm from endless branching on the continuous components of x see Carge and Schultz 1999 The function Qg is evaluated at x by fixing the first stage to x solving the scenario many subproblems and calculating the expected value of the corre sponding optimal values Thus infeasible suggestion are identified immediately We remark that problems related to random recourse have to be cared about by the users cf Walkup and Wets 1967 3 Input files ddsip requires 3 input files a number of other files are optional e Specification file a file containing the
23. lowing files are written to sipout The files rhs out cost out matriz out and model lp gz offer a check for a correct reading of the scenario files and the model file respec tively The files risk lp gz and eev lp gz document the changes made dur ing defining the risk model and solving the expected value problem respectively e If OUTFILES equals 3 then in addition the following files are written to sipout The single scenario files lb_sc_ _n0_gc lp gz and ub_sc_ _n0_gc lp gz solved in the root node for lower and upper bounds respectively e If OUTFILES equals 4 then in addition the following files are written to sipout The single scenario files 1b_sc_ _n _gc lp gz and ub_sc_ _n _gc lp gz solved in all nodes for lower and upper bounds e If OUTFILES equals 5 then the files Ib_sc_ _n _gc lp gz and ub_sc_ _n _gc lp gz are not written but instead The single scenario files b_sc_ _n sav gz solved in all nodes for lower bounds plus the used MIP starts as b_sc_ _n mst gz and the CPLEX settings as Ib_sc_ _n _l prm and Ib_sc_ _n _2 prm In the case of conic bundle use these are overwritten in every dual step just the ones of the final dual step of each node or the one causing a program crash remain e If OUTFILES equals 6 as in the case 5 the single scenario problem files are not written as lp gz but instead The single scenario files lb_sc_ _n _gc sav gz solved in all nodes for lower bou
24. luation of lower bounds It relates to the scenario subproblems Name Type Range Default Description OUTLEV Int 0 100 0 Amount of output to more out Caution The file more out may become large for high values of OUTLEV OUTFIL Int 0 5 1 Amount of output files see chapter 8 Caution If OUTFIL is greater than 3 lp or sav 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 Db 0 100 The total time limit CPU time includ ing the time needed to solve the EEV problem ABSOLU Dbl 0 0 The absolute duality gap RELATI Db 0 0 The relative duality gap EEVPRO Int 0 1 0 If the parameter is 1 then solve the EEV problem and report the VSS cf Birge and Louveaux 1997 DETEQU Int 0 1 0 If the parameter is 1 then produce a deterministic equivalent as det_equ lp gz Only for expectation based problems and it takes quite a while Table 2 Output and termination parameters The branching value is used to create two new subproblems as described in STEP 5 of the decomposition algorithm For continuous components it depends on the parameter EPSILON The dispersion norm of a node is calculated as max max i min x where zj j 1 S are the first stage part of the solutions of the S subproblems and xij i 1 n are their i th components Nodes
25. nds plus the used MIP starts as 1b_sc_ _n _gc mst gz and 19 the CPLEX settings as b_sc_ _n _1 prm and Ib_sc_ _n _2 prm This is the same amount of output files as with the setting 5 in case no conic bundle is used In the case of conic bundle use these are written in every dual step increasing the value after gc global counter with each step 9 License and bugs 9 1 License The program is free software It is distributed under the GNU General Public License as published by the Free Software Foundation see GNU Project 2004 9 2 Bug report Please report all bugs via email to ralf gollmer Quni due de If possible provide the input files to facilitate reproduction of the error 20 A Sample specs file Parameters to specify the two stage model FIRSTCON FIRSTVAR SECCON SECVAR STOCRHS SCENARIOS STOCCOST STOCMAT 9 30 280 326 70 5 0 0 First stage constraints First stage variables Second stage constraints Second stage variables Number of stochastic rhs elements Number of scenarios Number of stochastic cost coefficients stoch obj doesn t work in combination with risk Number of stochastic matrix entries Parameters for dual decomposition procedure OUTLEVEL OUTFILES STARTINFO PREPRO NODELIM TIMELIM HEURISTIC EEVPROB ABSOLUTE RELATIVE PORDER BRADIR BRASTRAT BOUSTRAT EPSILON RELAXL LOGFREQ INTFIRST ACCURACY NULLDISP QUANTILES Risk model
26. nstraints without stochastic right hand sides In the cost coefficient scenario file the probability entries are left out Oth erwise the entries are the same as those in the right hand side scenario file cf Figure 3 The number of stochastic cost coefficients c has to be specified in the specification file The first c variables occurring in the objective function of the model file are assumed to have stochastic cost coefficients The matrix scenario file requires additionally a row and column index for each stochastic matrix coefficient see Figure 3 The identifier for this index is pos If m is the number of stochastic matrix entries the 2 x i 1 th number 1 lt i lt m following pos is treated as row index and the 2 x i th number as column index of the i th entry of the individual scenarios Indices start with 0 for the first column row To facilitate the identification of the indices a simple program siphelp is included in the sources which reads a model file and produces a gzipped text file with a list of indices and names of rows and columns named rows cols gz and optionally an lp file of the model 7 Optional files 7 1 Start information file Start information can be provided as displayed in Figure 4 Hereby BEST BEST 2345 BOUND 2000 SOLUTION 1 2 MULTIPLIER 3 4 Figure 4 File with start values should be an upper bound BOUND a lower bound SOLUTION a feasible first stage solution and MULTIP
27. o be specified following a line with the indicator CPLEX BEGIN The contained lines have to start with the CPLEX parameter number followed by the parameter value This can be followed by a comment starting with an asterisk The parameter numbers are specified in the CPLEX callable library documentation section parameter table The settings following directly the line with CPLEXBEGIN are applied to all problems solved Special settings for CPLEX parameters can be specified for the different stages of the program For the calculation of the EEV parameter values can be overwritten after the identifier CPLEXEEV for the evaluation of lower bounds after the identifier CPLEXLB for a continuation of the evaluation of lower bounds with different settings after the identifier CPLEX2UB for the evaluation of upper bounds after the identifier CPLEX UB for a continuation of the evaluation of upper bounds with different settings after the identifier CPLEX2UB for the subproblems of the Lagrangian dual after the identifier CPLEXDUAL for a continuation of the subproblems of the Lagrangian dual after the identifier CPLEX2DUAL For some problems it is beneficial to use two optimization calls with different parameter setings e g mip emphasis heuristic frequency sequentially the sec ond one starting with the B amp B tree and solutions obtained in the first call This is enabled for lower and upper bound calculations and the Lagrangean dual if the
28. obabilities in Stochastic Programs with Mixed Integer Recourse SIAM Journal on Opti mization 14 pp 115 138 van der Vlerk M H 1995 Stochastic Programming with Integer Recourse PhD thesis University of Groningen The Netherlands Walkup D R J B Wets 1967 Stochastic Programs with Recourse SIAM Journal on Applied Mathematics 15 pp 1299 1314 24
29. risk models with decomposable linear risk measures The algorithm FSD can be used with any risk measure that is consistent with first order stochastic dominance The weakest 12 algorithm NFSD allows the minimization of any nonlinear risk measure A detailed description of the different algorithms can be found in Markert 2004 Name Type Range Default Description RISKMO Int 7 7 0 Risk model WEIGHT Dbl 0 1 Weight on risk term in objective TARGET Dbl Pe 0 Target for target measures PROBLE Dbl 0 1 0 Probability level for T VaR RISKAL Int 0 2 0 Scenario decomposition 1 FSD algorithm advised for TVaR also for pure risk models except 4 worst case costs and 7 stadard deviation 2 NFSD algorithm BRAETA Int 0 1 1 Branch order of additional first stage variable in models 4 and 5 A value of 0 means that this vari able will not be branched and its dispersion ignored RISKBM Dbl _ le 10 Big M for risk model 2 also used as bound for 7 with risk model 5 Table 6 Parameters for the risk model The program offers 7 different mean risk models and the associated risk models in which the expected value is not minimized In the following table we have compiled the possible settings Name Value Description RISKMO 1 1 Expected excess above target 2 2 Excess probabilities 3 3 Absolute semideviation 4 Worst case costs d 4 5 Tail value at risk 6 Value at risk
30. t saves half of the solutions of scenario problems but in case these problems are not solved to optimality the lower bound might be infe rior to the one possibly obtained for the descendants with the addtional bounds on the variables branched on For this reason the level of inheritance can be bounded to the number of branching steps specified with the MAXINHERIT keyword After the first node the scenarios are sorted descending wrt their contribu tion to the expected value This serves earlier detection of inferiority and allows stopping of evaluation of scenarios If conic bundle is used the lower bound for each scenario is not reliable in upper bounding which is done without Lagrangean parameters Thus the additional parameter PREMATURE to allow disallow premature stopping in upper bounding is set according to the use of conic bundle 4 4 Heuristic The decomposition algorithm uses a heuristic to guess feasible first stage so lutions based on the solutions of the subproblems in the current node The 11 heuristic is set by means of the parameter HEURIS The possible values of HEURIS are listed in the following table More than one of the heuristics could be used sequentially in every node when specifying the value 99 followed by a list of heuristics to be used the specs file line could look like this HEURISTIC 99 2 3 12 heuristics 2 3 and 12 are specified Value Description 1 The average of the solutions is use
31. with a dispersion norm smaller than NULLDISP are considered as leaves of the B amp B tree i e no further branching on them Name Type Range Default Description PORDER Int 0 1 0 Use priority order for branching If this parameter is 1 a priority order file has to be specified STARTI Int 0 1 0 Use start information If this is 1 a file containing the start values and or lower bound has to be specified MAXINH Int 0 5 Maximal level of inheritance of scen solutions in the B amp B tree HOTSTA Int 0 6 0 No warm starts during B amp B 1 Use solution pool of previous scenario and integer values of the same scenario in father as initial solutions 2 Use solution pool of previous scenario and lower bound from father node not applicable for risk models 3 Use solutions of all previous scenarios in the same node 4 Use solutions of all previous scenarios of the same node as well as solutions of all scenarios in father node 5 _ Uses solution info as in 3 together with the lower bound from father node 6 Uses solution info as in 4 together with the lower bound from father node BRADIR Int 1 1 1 Branching down is done first 1 Branching up is done first BRASTR Int 0 2 0 Use the middle between maximal and minimal value for the chosen variable as branching value 1 Use the expected value weighted aver age of the scenario solutions for the cho sen variable as branching value 2 Use a point in between t
Download Pdf Manuals
Related Search