source: coopr.pysp/trunk/coopr/pysp/scenariotree.py @ 3105

Last change on this file since 3105 was 3105, checked in by khunter, 11 years ago

NFC: EOL whitespace removal

File size: 41.2 KB
Line 
1#  _________________________________________________________________________
2#
3#  Coopr: A COmmon Optimization Python Repository
4#  Copyright (c) 2008 Sandia Corporation.
5#  This software is distributed under the BSD License.
6#  Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
7#  the U.S. Government retains certain rights in this software.
8#  For more information, see the Coopr README.txt file.
9#  _________________________________________________________________________
10
11import sys
12import types
13import copy
14import os.path
15import traceback
16
17from math import fabs
18
19from coopr.pyomo import *
20from phutils import *
21
22class ScenarioTreeNode(object):
23
24   #
25   # update the _solutions attribute of a tree node, given a specific
26   # variable/match-template/variable-index triple.
27   #
28   def _update_solution_map(self, variable, match_template, variable_indices):
29
30      # don't bother copying bounds for variables, as the values stored
31      # here are computed elsewhere - and that entity is responsible for
32      # ensuring feasibility. this also leaves room for specifying infeasible
33      # or partial solutions.
34      new_variable_index = variable._index
35      new_variable_name = variable.name
36      new_variable = None
37      if (len(new_variable_index) is 1) and (None in new_variable_index):
38         new_variable = Var(name=new_variable_name)
39      else:
40         new_variable = Var(new_variable_index, name=new_variable_name)
41      new_variable.construct()
42
43      # by default, deactive all variable values - we're copying the
44      # full index set of a variable, which is necessarily wasteful and
45      # incorrect. then, do a second pass and activate those indicies
46      # that are actually associated with this tree node.
47      for index in new_variable_index:
48         new_variable[index].deactivate()
49
50      for index in variable_indices:
51         new_variable[index].activate()
52
53      self._solutions[new_variable_name] = new_variable
54
55   #
56   # initialize the _solutions attribute of a tree node, from scratch.
57   #
58
59   def _initialize_solution_map(self):
60
61      # clear whatever was there before.
62      self._solutions = {}
63
64      # NOTE: Given the expense, this should really be optional - don't
65      #       construct unless we're actually going to use!
66      # for each variable referenced in the stage, clone the variable
67      # for purposes of storing solutions. we are being wasteful in
68      # terms copying indices that may not be referenced in the stage.
69      # this is something that we might revisit if space/performance
70      # is an issue (space is the most likely issue)
71      for variable, match_template, variable_indices in self._stage._variables:
72         self._update_solution_map(variable, match_template, variable_indices)
73
74      self._solution_map_initialized = True
75
76
77   """ Constructor
78   """
79   def __init__(self, name, conditional_probability, stage, initialize_solution=False):
80
81      self._name = name
82      self._stage = stage
83      self._parent = None
84      self._children = [] # a collection of ScenarioTreeNodes
85      self._conditional_probability = conditional_probability # conditional on parent
86      self._scenarios = [] # a collection of all Scenarios passing through this node in the tree
87
88      # general use statistics for the variables at each node.
89      # each attribute is a map between the variable name and a
90      # parameter (over the same index set) encoding the corresponding
91      # statistic computed over all scenarios for that node. the
92      # parameters are named as the source variable name suffixed
93      # by one of: "NODEMIN", "NODEAVG", and "NODEMAX".
94      # NOTE: the averages are probability_weighted - the min/max
95      #       values are not.
96      # NOTE: the parameter names are basically irrelevant, and the
97      #       convention is assumed to be enforced by whoever populates
98      #       these parameters.
99      self._averages = {}
100      self._minimums = {}
101      self._maximums = {}
102
103      # a flag indicating whether the _solutions attribute has been properly initialized.
104      self._solution_map_initialized = False
105
106      # solution (variable) values for this node. assumed to be distinct
107      # from self._averages, as the latter are not necessarily feasible.
108      # objects in the map are actual pyomo Var instances; keys are
109      # variable names.
110      self._solutions = {}
111
112      if initialize_solution is True:
113         self._initialize_solution_map()
114
115   #
116   # copies the parameter values values from the _averages attribute
117   # into the _solutions attribute - only for active variable values.
118   #
119
120   def snapshotSolutionFromAverages(self):
121
122      if self._solution_map_initialized is False:
123         self._initialize_solution_map()
124
125      for variable_name, variable in self._solutions.items():
126
127         # try and grab the corresponding averages parameter - if it
128         # doesn't exist, throw an exception.
129         average_parameter = None
130         try:
131            average_parameter = self._averages[variable_name]
132         except:
133            raise RuntimeError, "No averages parameter present on tree node="+self._name+" for variable="+variable_name
134
135         for index in variable._index:
136            if variable[index].active is True:
137               variable[index] = value(average_parameter[index])
138
139   #
140   # computes the solution values from the composite scenario instances at this tree node.
141   # the input scenario_instance_map is a map from scenario name to instance objects.
142   #
143
144   def snapshotSolutionFromInstances(self, scenario_instance_map):
145
146      if self._solution_map_initialized is False:
147         self._initialize_solution_map()
148
149      for variable_name, variable in self._solutions.items():
150         for index in variable._index:
151            if variable[index].active is True:
152               node_probability = 0.0
153               avg = 0.0
154               num_scenarios_with_index = 0
155               for scenario in self._scenarios:
156                  scenario_instance = scenario_instance_map[scenario._name]
157                  node_probability += scenario._probability
158                  scenario_variable = getattr(scenario_instance, variable.name)
159                  if index in scenario_variable:
160                     num_scenarios_with_index = num_scenarios_with_index + 1
161                     var_value = value(getattr(scenario_instance, variable.name)[index])
162                     avg += (scenario._probability * var_value)
163               if num_scenarios_with_index > 0:
164                  variable[index] = avg / node_probability
165
166   #
167   # a utility to compute the cost of the current node plus the expected costs of child nodes.
168   #
169
170   def computeExpectedNodeCost(self, scenario_instance_map):
171
172      # IMPT: This implicitly assumes convergence across the scenarios - if not, garbage results.
173      instance = scenario_instance_map[self._scenarios[0]._name]
174      stage_cost_variable = instance.active_components(Var)[self._stage._cost_variable[0].name][self._stage._cost_variable[1]]
175      if stage_cost_variable.value is not None:
176         my_cost = stage_cost_variable.value
177      else:
178         # depending on the situation (and the model), the stage cost variables might not have values.
179         my_cost = 0.0
180      child_cost = 0.0
181      for child in self._children:
182         child_cost += (child._conditional_probability * child.computeExpectedNodeCost(scenario_instance_map))
183      return my_cost + child_cost
184
185
186class Stage(object):
187
188   """ Constructor
189   """
190   def __init__(self, *args, **kwds):
191
192      self._name = ""
193
194      # a collection of ScenarioTreeNode objects.
195      self._tree_nodes = []
196
197      # a collection of triples consisting of (1) a reference to a Pyomo model Var object, (2) the original match
198      # template string (for output purposes), and (3) a *list* of the corresponding indices. the variables are
199      # references to those objects belonging to the Pyomo reference scenario instance associated with the parent
200      # ScenarioTree of this Stage.
201      # NOTE: if the variable index is none, it is assumed that the entire variable is blended.
202      self._variables = []
203
204      # a tuple consisting of (1) a reference to a pyomo model Var that computes the stage-specific cost and (2) the corresponding
205      # index. the index *is* the sole index in the cost variable, as the cost variable refers to a single variable index.
206      self._cost_variable = (None, None)
207
208   #
209   # add a new variable to the stage, which will include updating the solution maps for each associated ScenarioTreeNode.
210   #
211   def add_variable(self, variable, match_template, indices):
212
213      self._variables.append((variable, match_template, indices))
214
215      for tree_node in self._tree_nodes:
216         tree_node._update_solution_map(variable, match_template, indices)
217
218class Scenario(object):
219
220   """ Constructor
221   """
222   def __init__(self, *args, **kwds):
223
224      self._name = None
225      self._leaf_node = None  # allows for construction of node list
226      self._node_list = []    # sequence from parent to leaf of ScenarioTreeNodes
227      self._probability = 0.0 # the unconditional probability for this scenario, computed from the node list
228
229class ScenarioTree(object):
230
231   # a utility to construct the stage objects for this scenario tree.
232   # operates strictly by side effects, initializing the self
233   # _stages and _stage_map attributes.
234   def _construct_stages(self, stage_ids, stage_variable_ids, stage_cost_variable_ids):
235
236      # construct the stage objects, which will leave them
237      # largely uninitialized - no variable information, in particular.
238      for stage_name in stage_ids:
239         new_stage = Stage()
240         new_stage._name = stage_name
241         self._stages.append(new_stage)
242         self._stage_map[stage_name] = new_stage
243
244      # initialize the variable collections (blended and cost) for each stage.
245      # these are references, not copies.
246      for stage_id in stage_variable_ids.keys():
247
248         if stage_id not in self._stage_map.keys():
249            raise ValueError, "Unknown stage=" + stage_id + " specified in scenario tree constructor (stage->variable map)"
250
251         stage = self._stage_map[stage_id]
252         variable_ids = stage_variable_ids[stage_id]
253
254         for variable_string in variable_ids:
255
256            if isVariableNameIndexed(variable_string) is True:
257
258               variable_name, index_template = extractVariableNameAndIndex(variable_string)
259
260               # validate that the variable exists and extract the reference.
261               if variable_name not in self._reference_instance.active_components(Var):
262                  raise ValueError, "Variable=" + variable_name + " associated with stage=" + stage_id + " is not present in model=" + self._reference_instance.name
263               variable = self._reference_instance.active_components(Var)[variable_name]
264
265               # extract all "real", i.e., fully specified, indices matching the index template.
266               match_indices = extractVariableIndices(variable, index_template)
267
268               # there is a possibility that no indices match the input template.
269               # if so, let the user know about it.
270               if len(match_indices) == 0:
271                  raise RuntimeError, "No indices match template="+str(index_template)+" for variable="+variable_name+" ; encountered in scenario tree specification for model="+self._reference_instance.name
272
273               stage._variables.append((variable, index_template, match_indices))
274
275            else:
276
277               # verify that the variable exists.
278               if variable_string not in self._reference_instance.active_components(Var).keys():
279                  raise RuntimeError, "Unknown variable=" + variable_string + " associated with stage=" + stage_id + " is not present in model=" + self._reference_instance.name
280
281               variable = self._reference_instance.active_components(Var)[variable_string]
282
283               # 9/14/2009 - now forcing the user to explicit specify the full
284               # match template (e.g., "foo[*,*]") instead of just the variable
285               # name (e.g., "foo") to represent the set of all indices.
286
287               # if the variable is a singleton - that is, non-indexed - no brackets is fine.
288               # we'll just tag the var[None] variable value with the (suffix,value) pair.
289               if None not in variable._index:
290                  raise RuntimeError, "Variable="+variable_string+" is an indexed variable, and templates must specify an index match; encountered in scenario tree specification for model="+self._reference_instance.name
291
292               match_indices = []
293               match_indices.append(None)
294
295               stage._variables.append((variable, "", match_indices))
296
297      for stage_id in stage_cost_variable_ids.keys():
298
299         if stage_id not in self._stage_map.keys():
300            raise ValueError, "Unknown stage=" + stage_id + " specified in scenario tree constructor (stage->cost variable map)"
301         stage = self._stage_map[stage_id]
302
303         cost_variable_string = value(stage_cost_variable_ids[stage_id]) # de-reference is required to access the parameter value
304
305         # to be extracted from the string.
306         cost_variable_name = None
307         cost_variable = None
308         cost_variable_index = None
309
310         # do the extraction.
311         if isVariableNameIndexed(cost_variable_string) is True:
312
313            cost_variable_name, index_template = extractVariableNameAndIndex(cost_variable_string)
314
315            # validate that the variable exists and extract the reference.
316            if cost_variable_name not in self._reference_instance.active_components(Var):
317               raise ValueError, "Variable=" + cost_variable_name + " associated with stage=" + stage_id + " is not present in model=" + self._reference_instance.name
318            cost_variable = self._reference_instance.active_components(Var)[cost_variable_name]
319
320            # extract all "real", i.e., fully specified, indices matching the index template.
321            match_indices = extractVariableIndices(cost_variable, index_template)
322
323            # only one index can be supplied for a stage cost variable.
324            if len(match_indices) > 1:
325                msg = 'Only one index can be specified for a stage cost '     \
326                      'variable - %s match template "%s" for variable "%s" ;' \
327                      ' encountered in scenario tree specification for model' \
328                      ' "%s"'
329                raise RuntimeError, msg % (
330                  len(match_indices),
331                  index_template,
332                  cost_variable_name,
333                  self._reference_instance.name
334                )
335            elif len(match_indices) == 0:
336                msg = 'Stage cost index not found: %s[%s]\n'                  \
337                      'Do you have an off-by-one miscalculation, or did you ' \
338                      'forget to specify it in ReferenceModel.dat?'
339                raise RuntimeError, msg % ( cost_variable_name, index_template )
340
341            cost_variable_index = match_indices[0]
342
343         else:
344
345            cost_variable_name = cost_variable_string
346
347            # validate that the variable exists and extract the reference
348            if cost_variable_name not in self._reference_instance.active_components(Var):
349               raise ValueError, "Cost variable=" + cost_variable_name + " associated with stage=" + stage_id + " is not present in model=" + self._reference_instance.name
350            cost_variable = self._reference_instance.active_components(Var)[cost_variable_name]
351
352         # store the validated info.
353         stage._cost_variable = (cost_variable, cost_variable_index)
354
355   """ Constructor
356       Arguments:
357           scenarioinstance     - the reference (deterministic) scenario instance.
358           scenariotreeinstance - the pyomo model specifying all scenario tree (text) data.
359           scenariobundlelist   - a list of scenario names to retain, i.e., cull the rest to create a reduced tree!
360   """
361   def __init__(self, *args, **kwds):
362
363      self._name = None # some arbitrary identifier
364      self._reference_instance = None # the reference (deterministic) base model
365
366      # the core objects defining the scenario tree.
367      self._tree_nodes = [] # collection of ScenarioTreeNodes
368      self._stages = [] # collection of Stages - assumed to be in time-order. the set (provided by the user) itself *must* be ordered.
369      self._scenarios = [] # collection of Scenarios
370
371      # dictionaries for the above.
372      self._tree_node_map = {}
373      self._stage_map = {}
374      self._scenario_map = {}
375
376      # a boolean indicating how data for scenario instances is specified.
377      # possibly belongs elsewhere, e.g., in the PH algorithm.
378      self._scenario_based_data = None
379
380      scenario_tree_instance = None
381      scenario_bundle_list = None
382
383      # process the keyword options
384      for key in kwds.keys():
385         if key == "scenarioinstance":
386            self._reference_instance = kwds[key]
387         elif key == "scenariotreeinstance":
388            scenario_tree_instance = kwds[key]
389         elif key == "scenariobundlelist":
390            scenario_bundle_list = kwds[key]
391         else:
392            print "Unknown option=" + key + " specified in call to ScenarioTree constructor"
393
394      if self._reference_instance is None:
395         raise ValueError, "A reference scenario instance must be supplied in the ScenarioTree constructor"
396
397      if scenario_tree_instance is None:
398         raise ValueError, "A scenario tree instance must be supplied in the ScenarioTree constructor"
399
400      node_ids = scenario_tree_instance.Nodes
401      node_child_ids = scenario_tree_instance.Children
402      node_stage_ids = scenario_tree_instance.NodeStage
403      node_probability_map = scenario_tree_instance.ConditionalProbability
404      stage_ids = scenario_tree_instance.Stages
405      stage_variable_ids = scenario_tree_instance.StageVariables
406      stage_cost_variable_ids = scenario_tree_instance.StageCostVariable
407      scenario_ids = scenario_tree_instance.Scenarios
408      scenario_leaf_ids = scenario_tree_instance.ScenarioLeafNode
409      scenario_based_data = scenario_tree_instance.ScenarioBasedData
410
411      # save the method for instance data storage.
412      self._scenario_based_data = scenario_based_data()
413
414      # the input stages must be ordered, for both output purposes and knowledge of the final stage.
415      if stage_ids.ordered is False:
416         raise ValueError, "An ordered set of stage IDs must be supplied in the ScenarioTree constructor"
417
418      #
419      # construct the actual tree objects
420      #
421
422      # construct the stage objects w/o any linkages first; link them up
423      # with tree nodes after these have been fully constructed.
424      self._construct_stages(stage_ids, stage_variable_ids, stage_cost_variable_ids)
425
426      # construct the tree node objects themselves in a first pass,
427      # and then link them up in a second pass to form the tree.
428      # can't do a single pass because the objects may not exist.
429      for tree_node_name in node_ids:
430
431         if tree_node_name not in node_stage_ids:
432            raise ValueError, "No stage is assigned to tree node=" + tree_node._name
433
434         stage_name = value(node_stage_ids[tree_node_name])
435         if stage_name not in self._stage_map.keys():
436            raise ValueError, "Unknown stage=" + stage_name + " assigned to tree node=" + tree_node._name
437
438         new_tree_node = ScenarioTreeNode(tree_node_name,
439                                          value(node_probability_map[tree_node_name]),
440                                          self._stage_map[stage_name],
441                                          self._reference_instance)
442
443         self._tree_nodes.append(new_tree_node)
444         self._tree_node_map[tree_node_name] = new_tree_node
445         self._stage_map[stage_name]._tree_nodes.append(new_tree_node)
446
447      # link up the tree nodes objects based on the child id sets.
448      for this_node in self._tree_nodes:
449         this_node._children = []
450         if this_node._name in node_child_ids: # otherwise, you're at a leaf and all is well.
451            child_ids = node_child_ids[this_node._name]
452            for child_id in child_ids:
453               if child_id in self._tree_node_map.keys():
454                  child_node = self._tree_node_map[child_id]
455                  this_node._children.append(self._tree_node_map[child_id])
456                  if child_node._parent is None:
457                     child_node._parent = this_node
458                  else:
459                     raise ValueError, "Multiple parents specified for tree node="+child_id+"; existing parent node="+child_node._parent._name+"; conflicting parent node="+this_node._name
460               else:
461                  raise ValueError, "Unknown child tree node=" + child_id + " specified for tree node=" + this_node._name
462
463      # at this point, the scenario tree nodes and the stages are set - no
464      # two-pass logic necessary when constructing scenarios.
465      for scenario_name in scenario_ids:
466
467         # IMPT: the name of the scenario is assumed to have no '_' (underscore) characters in the identifier.
468         #       this is required when writing the extensive form, e.g., the scenario is used in the extensive
469         #       form as a prefix on variable and constraint names. this convention simplifies parsing on the
470         #       back end; if the underscore isn't used as a reserved character, then some other separator
471         #       symbol would be required, or we would have to engage in some complex prefix matching with
472         #       all possible scenario names.
473         if string.find(scenario_name, "_") != -1:
474            raise ValueError, "By convention, scenario names in PySP cannot contain underscore (_) characters; the scenario in violation="+scenario_name
475
476         new_scenario = Scenario()
477         new_scenario._name=scenario_name
478
479         if scenario_name not in scenario_leaf_ids.keys():
480            raise ValueError, "No leaf tree node specified for scenario=" + scenario_name
481         else:
482            scenario_leaf_node_name = value(scenario_leaf_ids[scenario_name])
483            if scenario_leaf_node_name not in self._tree_node_map.keys():
484               raise ValueError, "Uknown tree node=" + scenario_leaf_node_name + " specified as leaf of scenario=" + scenario_name
485            else:
486               new_scenario._leaf_node = self._tree_node_map[scenario_leaf_node_name]
487
488         current_node = new_scenario._leaf_node
489         probability = 1.0
490         while current_node is not None:
491            new_scenario._node_list.append(current_node)
492            current_node._scenarios.append(new_scenario) # links the scenarios to the nodes to enforce necessary non-anticipativity
493            probability *= current_node._conditional_probability
494            current_node = current_node._parent
495         new_scenario._node_list.reverse()
496         new_scenario._probability = probability
497
498         self._scenarios.append(new_scenario)
499         self._scenario_map[scenario_name] = new_scenario
500
501      # for output purposes, it is useful to known the maximal length of identifiers
502      # in the scenario tree for any particular category. I'm building these up
503      # incrementally, as they are needed. 0 indicates unassigned.
504      self._max_scenario_id_length = 0
505
506      # does the actual traversal to populate the members.
507      self.computeIdentifierMaxLengths()
508
509      # if a sub-bundle of scenarios has been specified, mark the
510      # active scenario tree components and compress the tree.
511      if scenario_bundle_list is not None:
512         self.compress(scenario_bundle_list)
513
514   #
515   # is the indicated scenario in the tree?
516   #
517
518   def contains_scenario(self, name):
519      return name in self._scenario_map.keys()
520
521   #
522   # get the scenario object from the tree.
523   #
524
525   def get_scenario(self, name):
526      return self._scenario_map[name]
527
528   #
529   # compute the scenario cost for the input instance, i.e.,
530   # the sum of all stage cost variables.
531   #
532
533   def compute_scenario_cost(self, instance):
534      aggregate_cost = 0.0
535      for stage in self._stages:
536            instance_cost_variable = instance.active_components(Var)[stage._cost_variable[0].name][stage._cost_variable[1]]
537            if instance_cost_variable.value is not None:
538                # depending on the situation (and the model), the stage cost variables might not have values.
539               aggregate_cost += instance_cost_variable
540      return aggregate_cost
541
542   #
543   # utility for compressing or culling a scenario tree based on
544   # a provided list of scenarios (specified by name) to retain -
545   # all non-referenced components are eliminated. this particular
546   # method compresses *in-place*, i.e., via direct modification
547   # of the scenario tree structure.
548   #
549
550   def compress(self, scenario_bundle_list):
551
552      # scan for and mark all referenced scenarios and
553      # tree nodes in the bundle list - all stages will
554      # obviously remain.
555      for scenario_name in scenario_bundle_list:
556         if scenario_name not in self._scenario_map:
557            raise ValueError, "Scenario="+scenario_name+" selected for bundling not present in scenario tree"
558         scenario = self._scenario_map[scenario_name]
559         scenario.retain = True
560
561         # chase all nodes comprising this scenario,
562         # marking them for retention.
563         for node in scenario._node_list:
564            node.retain = True
565
566      # scan for any non-retained scenarios and tree nodes.
567      scenarios_to_delete = []
568      tree_nodes_to_delete = []
569      for scenario in self._scenarios:
570         if hasattr(scenario, "retain") is True:
571            delattr(scenario, "retain")
572            pass
573         else:
574            scenarios_to_delete.append(scenario)
575            del self._scenario_map[scenario._name]
576
577      for tree_node in self._tree_nodes:
578         if hasattr(tree_node, "retain") is True:
579            delattr(tree_node, "retain")
580            pass
581         else:
582            tree_nodes_to_delete.append(tree_node)
583            del self._tree_node_map[tree_node._name]
584
585      # JPW does not claim the following routines are
586      # the most efficient. rather, they get the job
587      # done while avoiding serious issues with
588      # attempting to remove elements from a list that
589      # you are iterating over.
590
591      # delete all references to unmarked scenarios
592      # and child tree nodes in the scenario tree node
593      # structures.
594      for tree_node in self._tree_nodes:
595         for scenario in scenarios_to_delete:
596            if scenario in tree_node._scenarios:
597               tree_node._scenarios.remove(scenario)
598         for node_to_delete in tree_nodes_to_delete:
599            if node_to_delete in tree_node._children:
600               tree_node._children.remove(node_to_delete)
601
602      # delete all references to unmarked tree nodes
603      # in the scenario tree stage structures.
604      for stage in self._stages:
605         for tree_node in tree_nodes_to_delete:
606            if tree_node in stage._tree_nodes:
607               stage._tree_nodes.remove(tree_node)
608
609      # delete all unreferenced entries from the core scenario
610      # tree data structures.
611      for scenario in scenarios_to_delete:
612         self._scenarios.remove(scenario)
613      for tree_node in tree_nodes_to_delete:
614         self._tree_nodes.remove(tree_node)
615
616
617      # re-normalize the conditional probabilities of the
618      # children at each tree node.
619      for tree_node in self._tree_nodes:
620         sum_child_probabilities = 0.0
621         for child_node in tree_node._children:
622            sum_child_probabilities += child_node._conditional_probability
623         for child_node in tree_node._children:
624            child_node._conditional_probability = child_node._conditional_probability / sum_child_probabilities
625
626      # re-compute the absolute scenario probabilities based
627      # on the re-normalized conditional node probabilities.
628      for scenario in self._scenarios:
629         probability = 1.0
630         for tree_node in scenario._node_list:
631            probability = probability * tree_node._conditional_probability
632         scenario._probability = probability
633
634   #
635   # returns the root node of the scenario tree
636   #
637
638   def findRootNode(self):
639
640      for tree_node in self._tree_nodes:
641         if tree_node._parent is None:
642            return tree_node
643      return None
644
645   #
646   # a utility function to compute, based on the current scenario tree content,
647   # the maximal length of identifiers in various categories.
648   #
649
650   def computeIdentifierMaxLengths(self):
651
652      self._max_scenario_id_length = 0
653      for scenario in self._scenarios:
654         if len(scenario._name) > self._max_scenario_id_length:
655            self._max_scenario_id_length = len(scenario._name)
656
657   #
658   # a utility function to (partially, at the moment) validate a scenario tree
659   #
660
661   def validate(self):
662
663      # for any node, the sum of conditional probabilities of the children should sum to 1.
664      for tree_node in self._tree_nodes:
665         sum_probabilities = 0.0
666         if len(tree_node._children) > 0:
667            for child in tree_node._children:
668               sum_probabilities += child._conditional_probability
669            if abs(1.0 - sum_probabilities) > 0.000001:
670               print "The child conditional probabilities for tree node=" + tree_node._name + " sum to " + `sum_probabilities`
671               return False
672
673      # ensure that there is only one root node in the tree
674      num_roots = 0
675      root_ids = []
676      for tree_node in self._tree_nodes:
677         if tree_node._parent is None:
678            num_roots += 1
679            root_ids.append(tree_node._name)
680
681      if num_roots != 1:
682         print "Illegal set of root nodes detected: " + `root_ids`
683         return False
684
685      # there must be at least one scenario passing through each tree node.
686      for tree_node in self._tree_nodes:
687         if len(tree_node._scenarios) == 0:
688            print "There are no scenarios associated with tree node=" + tree_node._name
689            return False
690
691      return True
692
693   #
694   # copies the parameter values stored in any tree node _averages attribute
695   # into any tree node _solutions attribute - only for active variable values.
696   #
697
698   def snapshotSolutionFromAverages(self):
699
700      for tree_node in self._tree_nodes:
701
702         tree_node.snapshotSolutionFromAverages()
703
704   #
705   # computes the variable values at each tree node from the input scenario instances.
706   #
707
708   def snapshotSolutionFromInstances(self, scenario_instance_map):
709
710      for tree_node in self._tree_nodes:
711
712         tree_node.snapshotSolutionFromInstances(scenario_instance_map)
713
714   #
715   # a utility to determine the stage to which the input variable belongs.
716   # this is horribly inefficient, lacking an inverse map. fortunately,
717   # it isn't really called that often (yet). stage membership is determined
718   # by comparing the input variable name with the reference instance
719   # variable name (which is what the scenario tree refers to) and the
720   # associated indices.
721   #
722
723   def variableStage(self, variable, index):
724
725      for stage in self._stages:
726         # stage_var is a VarValue - the rest are strings and list of indices, respectively.
727         for (stage_var, match_template, match_indices) in stage._variables:
728            if (variable.name == stage_var.name) and (index in match_indices):
729               return stage
730
731         # IMPT: this is a temporary hack - the real fix is to force users to
732         # have every variable assigned to some stage in the model, either
733         # automatically or explicitly.
734         if (variable.name == stage._cost_variable[0].name):
735            return stage
736
737      raise RuntimeError, "The variable="+str(variable.name)+", index="+str(index)+" does not belong to any stage in the scenario tree"
738
739   #
740   # a utility to determine the stage to which the input constraint "belongs".
741   # a constraint belongs to the latest stage in which referenced variables
742   # in the constraint appears in that stage.
743   # input is a constraint is of type "Constraint", and an index of that
744   # constraint - which might be None in the case of singleton constraints.
745   # currently doesn't deal with SOS constraints, for no real good reason.
746   # returns an instance of a Stage object.
747   # IMPT: this method works on the canonical representation ("repn" attribute)
748   #       of a constraint. this implies that pre-processing of the instance
749   #       has been performed.
750   # NOTE: there is still the issue of whether the contained variables really
751   #       belong to the same model, but that is a different issue we won't
752   #       address right now (e.g., what does it mean for a constraint in an
753   #       extensive form binding instance to belong to a stage?).
754   #
755
756   def constraintStage(self, constraint, index):
757
758      largest_stage_index = -1
759      largest_stage = None
760
761      canonical_repn = constraint[index].repn
762      for degree, terms in canonical_repn.items():
763         if (degree != -1) and (degree != 0): # ignore constant terms and the variable definitions themselves.
764            for var_key, coefficient in terms.items():
765               var_value = canonical_repn[-1][var_key.keys()[0]]
766               var_stage = self.variableStage(var_value.var, var_value.index)
767               var_stage_index = self._stages.index(var_stage)
768
769               if var_stage_index > largest_stage_index:
770                  largest_stage_index = var_stage_index
771                  largest_stage = var_stage
772
773      return largest_stage
774
775   #
776   # a utility function to pretty-print the static/non-cost information associated with a scenario tree
777   #
778
779   def pprint(self):
780
781      print "Scenario Tree Detail"
782
783      print "----------------------------------------------------"
784      if self._reference_instance is not None:
785         print "Model=" + self._reference_instance.name
786      else:
787         print "Model=" + "Unassigned"
788      print "----------------------------------------------------"
789      print "Tree Nodes:"
790      print ""
791      for tree_node_name in sorted(self._tree_node_map.keys()):
792         tree_node = self._tree_node_map[tree_node_name]
793         print "\tName=" + tree_node_name
794         if tree_node._stage is not None:
795            print "\tStage=" + str(tree_node._stage._name)
796         else:
797            print "\t Stage=None"
798         if tree_node._parent is not None:
799            print "\tParent=" + tree_node._parent._name
800         else:
801            print "\tParent=" + "None"
802         if tree_node._conditional_probability is not None:
803            print "\tConditional probability=%4.4f" % tree_node._conditional_probability
804         else:
805            print "\tConditional probability=" + "***Undefined***"
806         print "\tChildren:"
807         if len(tree_node._children) > 0:
808            for child_node in sorted(tree_node._children, cmp=lambda x,y: cmp(x._name, y._name)):
809               print "\t\t" + child_node._name
810         else:
811            print "\t\tNone"
812         print "\tScenarios:"
813         if len(tree_node._scenarios) == 0:
814            print "\t\tNone"
815         else:
816            for scenario in sorted(tree_node._scenarios, cmp=lambda x,y: cmp(x._name, y._name)):
817               print "\t\t" + scenario._name
818         print ""
819      print "----------------------------------------------------"
820      print "Stages:"
821      for stage_name in sorted(self._stage_map.keys()):
822         stage = self._stage_map[stage_name]
823         print "\tName=" + str(stage_name)
824         print "\tTree Nodes: "
825         for tree_node in sorted(stage._tree_nodes, cmp=lambda x,y: cmp(x._name, y._name)):
826            print "\t\t" + tree_node._name
827         print "\tVariables: "
828         for (variable, index_template, indices) in stage._variables:
829            if (len(indices) == 1) and (indices[0] == None):
830               print "\t\t" + variable.name
831            else:
832               print "\t\t",variable.name,":",index_template
833         print "\tCost Variable: "
834         if stage._cost_variable[1] is None:
835            print "\t\t" + stage._cost_variable[0].name
836         else:
837            print "\t\t" + stage._cost_variable[0].name + indexToString(stage._cost_variable[1])
838         print ""
839      print "----------------------------------------------------"
840      print "Scenarios:"
841      for scenario_name in sorted(self._scenario_map.keys()):
842         scenario = self._scenario_map[scenario_name]
843         print "\tName=" + scenario_name
844         print "\tProbability=%4.4f" % scenario._probability
845         if scenario._leaf_node is None:
846            print "\tLeaf node=None"
847         else:
848            print "\tLeaf node=" + scenario._leaf_node._name
849         print "\tTree node sequence:"
850         for tree_node in scenario._node_list:
851            print "\t\t" + tree_node._name
852         print ""
853      print "----------------------------------------------------"
854
855   #
856   # a utility function to pretty-print the solution associated with a scenario tree
857   #
858
859   def pprintSolution(self, epsilon=1.0e-5):
860
861      print "----------------------------------------------------"
862      print "Tree Nodes:"
863      print ""
864      for tree_node_name in sorted(self._tree_node_map.keys()):
865         tree_node = self._tree_node_map[tree_node_name]
866         print "\tName=" + tree_node_name
867         if tree_node._stage is not None:
868            print "\tStage=" + tree_node._stage._name
869         else:
870            print "\t Stage=None"
871         if tree_node._parent is not None:
872            print "\tParent=" + tree_node._parent._name
873         else:
874            print "\tParent=" + "None"
875         print "\tVariables: "
876         for (variable, index_template, indices) in tree_node._stage._variables:
877            solution_variable = tree_node._solutions[variable.name]
878            if (len(indices) == 1) and (indices[0] == None):
879               # if this is a singleton variable, then it should necessarily be active -
880               # otherwise, it wouldn't be referenced in the stage!!!
881               value = solution_variable[None].value
882               if fabs(value) > epsilon:
883                  print "\t\t"+variable.name+"="+str(value)
884            else:
885               for index in indices:
886                  if (solution_variable[index].active is True) and (index in solution_variable):
887                     value = solution_variable[index].value
888                     if (value is not None) and (fabs(value) > epsilon):
889                        print "\t\t"+variable.name+indexToString(index)+"="+str(value)
890         print ""
891
892   #
893   # a utility function to pretty-print the cost information associated with a scenario tree
894   #
895
896   def pprintCosts(self, scenario_instance_map):
897
898      print "Scenario Tree Costs"
899      print "***WARNING***: Assumes full (or nearly so) convergence of scenario solutions at each node in the scenario tree - computed costs are invalid otherwise"
900
901      print "----------------------------------------------------"
902      if self._reference_instance is not None:
903         print "Model=" + self._reference_instance.name
904      else:
905         print "Model=" + "Unassigned"
906
907      print "----------------------------------------------------"
908      print "Tree Nodes:"
909      print ""
910      for tree_node_name in sorted(self._tree_node_map.keys()):
911         tree_node = self._tree_node_map[tree_node_name]
912         print "\tName=" + tree_node_name
913         if tree_node._stage is not None:
914            print "\tStage=" + tree_node._stage._name
915         else:
916            print "\t Stage=None"
917         if tree_node._parent is not None:
918            print "\tParent=" + tree_node._parent._name
919         else:
920            print "\tParent=" + "None"
921         if tree_node._conditional_probability is not None:
922            print "\tConditional probability=%4.4f" % tree_node._conditional_probability
923         else:
924            print "\tConditional probability=" + "***Undefined***"
925         print "\tChildren:"
926         if len(tree_node._children) > 0:
927            for child_node in sorted(tree_node._children, cmp=lambda x,y: cmp(x._name, y._name)):
928               print "\t\t" + child_node._name
929         else:
930            print "\t\tNone"
931         print "\tScenarios:"
932         if len(tree_node._scenarios) == 0:
933            print "\t\tNone"
934         else:
935            for scenario in sorted(tree_node._scenarios, cmp=lambda x,y: cmp(x._name, y._name)):
936               print "\t\t" + scenario._name
937         print "\tExpected node cost=%10.4f" % tree_node.computeExpectedNodeCost(scenario_instance_map)
938         print ""
939
940      print "----------------------------------------------------"
941      print "Scenarios:"
942      print ""
943      for scenario_name, scenario in sorted(self._scenario_map.iteritems()):
944         instance = scenario_instance_map[scenario_name]
945
946         print "\tName=" + scenario_name
947         print "\tProbability=%4.4f" % scenario._probability
948
949         if scenario._leaf_node is None:
950            print "\tLeaf Node=None"
951         else:
952            print "\tLeaf Node=" + scenario._leaf_node._name
953
954         print "\tTree node sequence:"
955         for tree_node in scenario._node_list:
956            print "\t\t" + tree_node._name
957
958         aggregate_cost = 0.0
959         for stage in self._stages:
960            instance_cost_variable = instance.active_components(Var)[stage._cost_variable[0].name][stage._cost_variable[1]]
961            if instance_cost_variable.value is not None:
962               print "\tStage=%20s     Cost=%10.4f" % (stage._name, instance_cost_variable.value)
963               cost = instance_cost_variable.value
964            else:
965               print "\tStage=%20s     Cost=%10s" % (stage._name, "Not Rprted.")
966               cost = 0.0
967            aggregate_cost += cost
968         print "\tTotal scenario cost=%10.4f" % aggregate_cost
969         print ""
970      print "----------------------------------------------------"
971
Note: See TracBrowser for help on using the repository browser.