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

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

Enhancements to PySP to deal with reporting issues caused by the lack of objective function values in SOL files (in general, and those produced by ipopt in particular).

File size: 41.3 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.