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

Last change on this file since 3218 was 3218, checked in by jwatson, 11 years ago

More changes associated with generalizing the PySP index structures from per-stage to per-node.

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