Changeset 2413

Timestamp:

Mar 8, 2010 12:20:36 PM (9 years ago)

Author:

jwatson

Message:

PySP EF restructuring / refactoring

Location:

coopr.pysp/trunk/coopr/pysp

Files:

• ef.py (modified) (11 diffs)
• scenariotree.py (modified) (5 diffs)

coopr.pysp/trunk/coopr/pysp/ef.py

@@ -15 +15 @@
 from coopr.pyomo.base.var import _VarValue, _VarBase
 
+#
 # brain-dead utility for determing if there is a binary to write in the 
 # composite model - need to know this, because CPLEX doesn't like empty
 # binary blocks in the LP file.
+#
+
 def binaries_present(master_model, scenario_instances):
 
@@ -34 +37 @@
    return False
 
+#
 # brain-dead utility for determing if there is a binary to write in the 
 # composite model - need to know this, because CPLEX doesn't like empty
 # integer blocks in the LP file.
+#
+
 def integers_present(master_model, scenario_instances):
 
@@ -53 +59 @@
    return False
 
+#
+# a routine to create the extensive form, given an input scenario tree and instances.
+# IMPT: unlike scenario instances, the extensive form instance is *not* self-contained.
+#       in particular, it has binding constraints that cross the binding instance and
+#       the scenario instances. it is up to the caller to keep track of which scenario
+#       instances are associated with the extensive form. this might be something we
+#       encapsulate at some later time.
+#
+
+def create_ef_instance(scenario_tree, scenario_instances, generate_weighted_cvar, verbose_output):
+
+   binding_instance = Model()
+   binding_instance.name = "MASTER"
+
+   # walk the scenario tree - create variables representing the common values for all scenarios
+   # associated with that node. the constraints will be created later. also create expected-cost
+   # variables for each node, to be computed via constraints/objectives defined in a subsequent pass.
+   # master variables are created for all nodes but those in the last stage. expected cost variables
+   # are, for no particularly good reason other than easy coding, created for nodes in all stages.
+   if verbose_output is True:
+      print "Creating variables for master binding instance"
+
+   for stage in scenario_tree._stages:
+
+      for (stage_variable, index_template, stage_variable_indices) in stage._variables:
+
+         if verbose_output is True:
+            print "Creating master variable and blending constraints for decision variable=", stage_variable, ", indices=", index_template
+
+         for tree_node in stage._tree_nodes:
+
+            if stage != scenario_tree._stages[-1]:      
+
+               master_variable_name = tree_node._name + "_" + stage_variable.name
+
+               # because there may be a single stage variable and multiple indices, check
+               # for the existence of the variable at this node - if you don't, you'll
+               # inadvertently over-write what was there previously!
+               master_variable = None
+               try:
+                  master_variable = getattr(binding_instance, master_variable_name)
+               except:
+                  new_master_variable_index = stage_variable._index
+                  new_master_variable = None
+                  if (len(new_master_variable_index) is 1) and (None in new_master_variable_index):
+                     new_master_variable = Var(name=stage_variable.name)
+                  else:
+                     new_master_variable = Var(new_master_variable_index, name=stage_variable.name)
+                  new_master_variable.construct()
+                  new_master_variable._model = binding_instance
+                  setattr(master_binding_instance, master_variable_name, new_master_variable)
+
+                  master_variable = new_master_variable
+
+               for index in stage_variable_indices:
+
+                  is_used = True # until proven otherwise                     
+                  for scenario in tree_node._scenarios:
+                     instance = scenario_instances[scenario._name]
+                     if getattr(instance,stage_variable.name)[index].status == VarStatus.unused:
+                        is_used = False
+
+                  is_fixed = False # until proven otherwise
+                  for scenario in tree_node._scenarios:
+                     instance = scenario_instances[scenario._name]
+                     if getattr(instance,stage_variable.name)[index].fixed is True:
+                        is_fixed = True
+
+                  if (is_used is True) and (is_fixed is False):
+                           
+                     # the following is necessary, specifically to get the name - deepcopy won't reset these attributes.
+                     # and because presolve/simplification is name-based, the names *have* to be different.
+                     master_variable[index].var = master_variable
+                     master_variable[index].name = tree_node._name + "_" + master_variable[index].name
+
+                     for scenario in tree_node._scenarios:
+
+                        scenario_instance = scenario_instances[scenario._name]
+                        scenario_variable = getattr(scenario_instance, stage_variable.name)
+                        new_constraint_name = scenario._name + "_" + master_variable_name + "_" + str(index)
+                        new_constraint = Constraint(name=new_constraint_name)
+                        new_expr = master_variable[index] - scenario_variable[index]
+                        new_constraint.add(None, (0.0, new_expr, 0.0))
+                        new_constraint._model = master_binding_instance
+                        setattr(master_binding_instance, new_constraint_name, new_constraint)
+
+            # create a variable to represent the expected cost at this node -
+            # the constraint to compute this comes later.
+            expected_cost_variable_name = "EXPECTED_COST_" + tree_node._name
+            expected_cost_variable = Var(name=expected_cost_variable_name)
+            expected_cost_variable._model = master_binding_instance
+            setattr(master_binding_instance, expected_cost_variable_name, expected_cost_variable)
+
+   master_binding_instance.preprocess()
+
+   # ditto above for the (non-expected) cost variable.
+   for stage in scenario_tree._stages:
+
+      (cost_variable,cost_variable_index) = stage._cost_variable
+
+      if verbose_output:
+         print "Creating master variable and blending constraints for cost variable=", cost_variable, ", index=", cost_variable_index      
+
+      for tree_node in stage._tree_nodes:
+
+         new_cost_variable_name = tree_node._name + "_" + cost_variable.name
+
+         # TBD - the following is bad - check to see if it's already there (I suspect some of them are!!!)
+
+         # this is undoubtedly wasteful, in that a cost variable
+         # for each tree node is created with *all* indices. 
+         new_cost_variable_name = tree_node._name + "_" + cost_variable.name
+         new_cost_variable_index = cost_variable._index
+         new_cost_variable = None
+         if (len(new_cost_variable_index) is 1) and (None in new_cost_variable_index):
+            new_cost_variable = Var(name=new_cost_variable_name)
+         else:
+            new_cost_variable = Var(new_cost_variable_index, new_cost_variable_name)
+         new_cost_variable.construct()
+         new_cost_variable._model = master_binding_instance
+         setattr(master_binding_instance, new_cost_variable_name, new_cost_variable)                  
+
+         # the following is necessary, specifically to get the name - deepcopy won't reset these attributes.
+         new_cost_variable[cost_variable_index].var = new_cost_variable
+         if cost_variable_index is not None:
+            # if the variable index is None, the variable is derived from a VarValue, so the
+            # name gets updated automagically.
+            new_cost_variable[cost_variable_index].name = tree_node._name + "_" + new_cost_variable[cost_variable_index].name
+
+         for scenario in tree_node._scenarios:
+
+            scenario_instance = scenario_instances[scenario._name]
+            scenario_cost_variable = getattr(scenario_instance, cost_variable.name)
+            new_constraint_name = scenario._name + "_" + new_cost_variable_name + "_" + str(cost_variable_index)
+            new_constraint = Constraint(name=new_constraint_name)
+            new_expr = new_cost_variable[cost_variable_index] - scenario_cost_variable[cost_variable_index]
+            new_constraint.add(None, (0.0, new_expr, 0.0))
+            new_constraint._model = master_binding_instance
+            setattr(master_binding_instance, new_constraint_name, new_constraint)
+
+   # create the constraints for computing the master per-node cost variables,
+   # i.e., the current node cost and the expected cost of the child nodes.
+   # if the root, then the constraint is just the objective.
+
+   for stage in scenario_tree._stages:
+
+      (stage_cost_variable,stage_cost_variable_index) = stage._cost_variable
+
+      for tree_node in stage._tree_nodes:
+
+         node_expected_cost_variable_name = "EXPECTED_COST_" + tree_node._name
+         node_expected_cost_variable = getattr(master_binding_instance, node_expected_cost_variable_name)
+
+         node_cost_variable_name = tree_node._name + "_" + stage_cost_variable.name
+         node_cost_variable = getattr(master_binding_instance, node_cost_variable_name)                        
+            
+         constraint_expr = node_expected_cost_variable - node_cost_variable[stage_cost_variable_index]
+
+         for child_node in tree_node._children:
+
+            child_node_expected_cost_variable_name = "EXPECTED_COST_" + child_node._name
+            child_node_expected_cost_variable = getattr(master_binding_instance, child_node_expected_cost_variable_name)
+            constraint_expr = constraint_expr - (child_node._conditional_probability * child_node_expected_cost_variable)
+
+         new_constraint_name = "COST" + "_" + node_cost_variable_name + "_" + str(cost_variable_index)
+         new_constraint = Constraint(name=new_constraint_name)
+         new_constraint.add(None, (0.0, constraint_expr, 0.0))
+         new_constraint._model = master_binding_instance                     
+         setattr(master_binding_instance, new_constraint_name, new_constraint)
+
+         if tree_node._parent is None:
+
+            an_instance = scenario_instances[scenario_instances.keys()[0]]
+            an_objective = an_instance.active_components(Objective)
+            opt_sense = an_objective[an_objective.keys()[0]].sense
+
+            new_objective = Objective(name="MASTER", sense=opt_sense)
+            new_objective._data[None].expr = node_expected_cost_variable
+            setattr(master_binding_instance, "MASTER", new_objective)
+
+   master_binding_instance.preprocess()
+
+   return master_binding_instance
+
+#
 # the main extensive-form writer routine - including read of scenarios/etc.
+#
+
 def write_ef_from_scratch(model_directory, instance_directory, output_filename, \
                           generate_weighted_cvar, cvar_weight, risk_alpha):
@@ -605 +798 @@
    print ""
 
-def write_ef(scenario_tree, instances, output_filename):
+def create_and_write_ef(scenario_tree, scenario_instances, output_filename):
 
    start_time = time.time()
 
-   ################################################################################################
-   #### CREATE THE MASTER / BINDING INSTANCE ######################################################
-   ################################################################################################
-
-   master_binding_instance = Model()
-   master_binding_instance.name = "MASTER"
-
-   # walk the scenario tree - create variables representing the common values for all scenarios
-   # associated with that node. the constraints will be created later. also create expected-cost
-   # variables for each node, to be computed via constraints/objectives defined in a subsequent pass.
-   # master variables are created for all nodes but those in the last stage. expected cost variables
-   # are, for no particularly good reason other than easy coding, created for nodes in all stages.
-   print "Creating variables for master binding instance"
-
-   for stage in scenario_tree._stages:
-
-      for (stage_variable, index_template, stage_variable_indices) in stage._variables:
-
-         print "Creating master variable and blending constraints for decision variable=", stage_variable, ", indices=", index_template
-
-         for tree_node in stage._tree_nodes:
-
-            if stage != scenario_tree._stages[-1]:      
-
-               master_variable_name = tree_node._name + "_" + stage_variable.name
-
-               # because there may be a single stage variable and multiple indices, check
-               # for the existence of the variable at this node - if you don't, you'll
-               # inadvertently over-write what was there previously!
-               master_variable = None
-               try:
-                  master_variable = getattr(master_binding_instance, master_variable_name)
-               except:
-                  new_master_variable_index = stage_variable._index
-                  new_master_variable = None
-                  if (len(new_master_variable_index) is 1) and (None in new_master_variable_index):
-                     new_master_variable = Var(name=stage_variable.name)
-                  else:
-                     new_master_variable = Var(new_master_variable_index, name=stage_variable.name)
-                  new_master_variable.construct()
-                  new_master_variable._model = master_binding_instance
-                  setattr(master_binding_instance, master_variable_name, new_master_variable)
-
-                  # TBD - TECHNICALLY, WE NEED TO COPY BOUNDS - BUT WE REALLY DON'T, AS THEY ARE ON THE PER-INSTNACE VARS!
-
-                  master_variable = new_master_variable
-
-               for index in stage_variable_indices:
-
-                  is_used = True # until proven otherwise                     
-                  for scenario in tree_node._scenarios:
-                     instance = instances[scenario._name]
-                     if getattr(instance,stage_variable.name)[index].status == VarStatus.unused:
-                        is_used = False
-
-                  is_fixed = False # until proven otherwise
-                  for scenario in tree_node._scenarios:
-                     instance = instances[scenario._name]
-                     if getattr(instance,stage_variable.name)[index].fixed is True:
-                        is_fixed = True
-
-                  if (is_used is True) and (is_fixed is False):
-                           
-                     # the following is necessary, specifically to get the name - deepcopy won't reset these attributes.
-                     # and because presolve/simplification is name-based, the names *have* to be different.
-                     master_variable[index].var = master_variable
-                     master_variable[index].name = tree_node._name + "_" + master_variable[index].name
-
-                     for scenario in tree_node._scenarios:
-
-                        scenario_instance = instances[scenario._name]
-                        scenario_variable = getattr(scenario_instance, stage_variable.name)
-                        new_constraint_name = scenario._name + "_" + master_variable_name + "_" + str(index)
-                        new_constraint = Constraint(name=new_constraint_name)
-                        new_expr = master_variable[index] - scenario_variable[index]
-                        new_constraint.add(None, (0.0, new_expr, 0.0))
-                        new_constraint._model = master_binding_instance
-                        setattr(master_binding_instance, new_constraint_name, new_constraint)
-
-            # create a variable to represent the expected cost at this node -
-            # the constraint to compute this comes later.
-            expected_cost_variable_name = "EXPECTED_COST_" + tree_node._name
-            expected_cost_variable = Var(name=expected_cost_variable_name)
-            expected_cost_variable._model = master_binding_instance
-            setattr(master_binding_instance, expected_cost_variable_name, expected_cost_variable)
-
-   master_binding_instance.preprocess()
-
-   # ditto above for the (non-expected) cost variable.
-   for stage in scenario_tree._stages:
-
-      (cost_variable,cost_variable_index) = stage._cost_variable
-
-      print "Creating master variable and blending constraints for cost variable=", cost_variable, ", index=", cost_variable_index      
-
-      for tree_node in stage._tree_nodes:
-
-         new_cost_variable_name = tree_node._name + "_" + cost_variable.name
-
-         # TBD - the following is bad - check to see if it's already there (I suspect some of them are!!!)
-
-         # this is undoubtedly wasteful, in that a cost variable
-         # for each tree node is created with *all* indices. 
-         new_cost_variable_name = tree_node._name + "_" + cost_variable.name
-         new_cost_variable_index = cost_variable._index
-         new_cost_variable = None
-         if (len(new_cost_variable_index) is 1) and (None in new_cost_variable_index):
-            new_cost_variable = Var(name=new_cost_variable_name)
-         else:
-            new_cost_variable = Var(new_cost_variable_index, new_cost_variable_name)
-         new_cost_variable.construct()
-         new_cost_variable._model = master_binding_instance
-         setattr(master_binding_instance, new_cost_variable_name, new_cost_variable)                  
-
-         # the following is necessary, specifically to get the name - deepcopy won't reset these attributes.
-         new_cost_variable[cost_variable_index].var = new_cost_variable
-         if cost_variable_index is not None:
-            # if the variable index is None, the variable is derived from a VarValue, so the
-            # name gets updated automagically.
-            new_cost_variable[cost_variable_index].name = tree_node._name + "_" + new_cost_variable[cost_variable_index].name
-
-         for scenario in tree_node._scenarios:
-
-            scenario_instance = instances[scenario._name]
-            scenario_cost_variable = getattr(scenario_instance, cost_variable.name)
-            new_constraint_name = scenario._name + "_" + new_cost_variable_name + "_" + str(cost_variable_index)
-            new_constraint = Constraint(name=new_constraint_name)
-            new_expr = new_cost_variable[cost_variable_index] - scenario_cost_variable[cost_variable_index]
-            new_constraint.add(None, (0.0, new_expr, 0.0))
-            new_constraint._model = master_binding_instance
-            setattr(master_binding_instance, new_constraint_name, new_constraint)
-
-   # create the constraints for computing the master per-node cost variables,
-   # i.e., the current node cost and the expected cost of the child nodes.
-   # if the root, then the constraint is just the objective.
-
-   for stage in scenario_tree._stages:
-
-      (stage_cost_variable,stage_cost_variable_index) = stage._cost_variable
-
-      for tree_node in stage._tree_nodes:
-
-         node_expected_cost_variable_name = "EXPECTED_COST_" + tree_node._name
-         node_expected_cost_variable = getattr(master_binding_instance, node_expected_cost_variable_name)
-
-         node_cost_variable_name = tree_node._name + "_" + stage_cost_variable.name
-         node_cost_variable = getattr(master_binding_instance, node_cost_variable_name)                        
-            
-         constraint_expr = node_expected_cost_variable - node_cost_variable[stage_cost_variable_index]
-
-         for child_node in tree_node._children:
-
-            child_node_expected_cost_variable_name = "EXPECTED_COST_" + child_node._name
-            child_node_expected_cost_variable = getattr(master_binding_instance, child_node_expected_cost_variable_name)
-            constraint_expr = constraint_expr - (child_node._conditional_probability * child_node_expected_cost_variable)
-
-         new_constraint_name = "COST" + "_" + node_cost_variable_name + "_" + str(cost_variable_index)
-         new_constraint = Constraint(name=new_constraint_name)
-         new_constraint.add(None, (0.0, constraint_expr, 0.0))
-         new_constraint._model = master_binding_instance                     
-         setattr(master_binding_instance, new_constraint_name, new_constraint)
-
-         if tree_node._parent is None:
-
-            an_instance = instances[instances.keys()[0]]
-            an_objective = an_instance.active_components(Objective)
-            opt_sense = an_objective[an_objective.keys()[0]].sense
-
-            new_objective = Objective(name="MASTER", sense=opt_sense)
-            new_objective._data[None].expr = node_expected_cost_variable
-            setattr(master_binding_instance, "MASTER", new_objective)
-
-   master_binding_instance.preprocess()
+   binding_instance = create_ef_instance(scenario_tree, scenario_instances, False, True)
 
    ################################################################################################
@@ -806 +827 @@
 
    print >>output_file, "\\ Begin objective block for master"
-   problem_writer._print_model_LP(master_binding_instance, output_file)
+   problem_writer._print_model_LP(binding_instance, output_file)
    print >>output_file, "\\ End objective block for master"
    print >>output_file, ""
@@ -822 +843 @@
 
    print >>output_file, "\\ Begin constraint block for master"
-   problem_writer._print_model_LP(master_binding_instance, output_file)
+   problem_writer._print_model_LP(binding_instance, output_file)
    print >>output_file, "\\ End constraint block for master",
    print >>output_file, ""
 
-   for scenario_name in instances.keys():
-      instance = instances[scenario_name]
+   for scenario_name in scenario_instances.keys():
+      instance = scenario_instances[scenario_name]
       print >>output_file, "\\ Begin constraint block for scenario",scenario_name       
       problem_writer._print_model_LP(instance, output_file)
@@ -852 +873 @@
 
    print >>output_file, "\\ Begin variable bounds block for master"
-   problem_writer._print_model_LP(master_binding_instance, output_file)
+   problem_writer._print_model_LP(binding_instance, output_file)
    print >>output_file, "\\ End variable bounds block for master"
    print >>output_file, ""
    
-   for scenario_name in instances.keys():
-      instance = instances[scenario_name]
+   for scenario_name in scenario_instances.keys():
+      instance = scenario_instances[scenario_name]
       print >>output_file, "\\ Begin variable bounds block for scenario",scenario_name 
       problem_writer._print_model_LP(instance, output_file)
@@ -868 +889 @@
    problem_writer._output_integer_variables = True
 
-   if integers_present(master_binding_instance, instances) is True:
+   if integers_present(binding_instance, scenario_instances) is True:
 
       print >>output_file, "integer"
@@ -874 +895 @@
 
       print >>output_file, "\\ Begin integer variable block for master"
-      problem_writer._print_model_LP(master_binding_instance, output_file)
+      problem_writer._print_model_LP(binding_instance, output_file)
       print >>output_file, "\\ End integer variable block for master"
       print >>output_file, ""
    
-      for scenario_name in instances.keys():
-         instance = instances[scenario_name]
+      for scenario_name in scenario_instances.keys():
+         instance = scenario_instances[scenario_name]
          print >>output_file, "\\ Begin integer variable block for scenario",scenario_name 
          problem_writer._print_model_LP(instance, output_file)
@@ -890 +911 @@
    problem_writer._output_binary_variables = True
 
-   if binaries_present(master_binding_instance, instances) is True:
+   if binaries_present(binding_instance, scenario_instances) is True:
 
       print >>output_file, "binary"
@@ -896 +917 @@
 
       print >>output_file, "\\ Begin binary variable block for master"
-      problem_writer._print_model_LP(master_binding_instance, output_file)
+      problem_writer._print_model_LP(binding_instance, output_file)
       print >>output_file, "\\ End binary variable block for master"
       print >>output_file, ""
    
-      for scenario_name in instances.keys():
-         instance = instances[scenario_name]
+      for scenario_name in scenario_instances.keys():
+         instance = scenario_instances[scenario_name]
          print >>output_file, "\\ Begin binary variable block for scenario",scenario_name 
          problem_writer._print_model_LP(instance, output_file)

coopr.pysp/trunk/coopr/pysp/scenariotree.py

@@ -11 +11 @@
 import sys
 import types
-from coopr.pyomo import *
 import copy
 import os.path
 import traceback
 
+from coopr.pyomo import *
 from phutils import *
 
@@ -23 +23 @@
 
    """
-   def __init__(self, *args, **kwds):
-
-      self._name = ""
-      self._stage = None
+   def __init__(self, name, conditional_probability, stage, reference_instance):
+
+      self._name = name
+      self._stage = stage
       self._parent = None
       self._children = [] # a collection of ScenarioTreeNodes
-      self._conditional_probability = None # conditional on parent
+      self._conditional_probability = conditional_probability # conditional on parent
       self._scenarios = [] # a collection of all Scenarios passing through this node in the tree
 
@@ -43 +43 @@
       self._minimums = {}
       self._maximums = {}
+
+      # solution (variable) values for this node. assumed to be distinct
+      # from self._averages, as the latter are not necessarily feasible.
+      # objects in the map are actual variables. 
+      self._solution = {}
+
+      # for each variable referenced in the stage, clone the variable
+      # for purposes of storing solutions. we are being wasteful in 
+      # terms copying indices that may not be referenced in the stage.
+      # this is something that we might revisit if space/performance
+      # is an issue (space is the most likely issue)
+      for variable, match_template, variable_indices in self._stage._variables:
+
+         # don't bother copying bounds for variables, as the values stored
+         # here are computed elsewhere - and that entity is responsible for
+         # ensuring feasibility. this also leaves room for specifying infeasible
+         # or partial solutions.       
+
+         new_variable_index = variable._index
+         new_variable_name = variable._name
+         new_variable = None
+         if (len(new_variable_index) is 1) and (None in new_variable_index):
+            new_variable = Var(name=new_variable_name)
+         else:
+            new_variable = Var(new_variable_index, name=new_variable_name)
+
+         self._solution[new_variable_name] = new_variable
 
    #
@@ -91 +118 @@
    """ Constructor
        Arguments:
-           scenarioinstance             - the reference scenario instance.
+           scenarioinstance     - the reference (deterministic) scenario instance.
            scenariotreeinstance - the pyomo model specifying all scenario tree (text) data.
            scenariobundlelist   - a list of scenario names to retain, i.e., cull the rest to create a reduced tree!
@@ -173 +200 @@
       # can't do a single pass because the objects may not exist.
       for tree_node_name in node_ids:
-         new_tree_node = ScenarioTreeNode()
-         new_tree_node._name = tree_node_name
+
+         if tree_node_name not in node_stage_ids:
+            raise ValueError, "No stage is assigned to tree node=" + tree_node._name
+
+         stage_name = node_stage_ids[tree_node_name].value
+         if stage_name not in self._stage_map.keys():
+            raise ValueError, "Unknown stage=" + stage_name + " assigned to tree node=" + tree_node._name
+
+         new_tree_node = ScenarioTreeNode(tree_node_name, 
+                                          node_probability_map[tree_node_name].value, 
+                                          self._stage_map[stage_name],
+                                          self._reference_instance)
 
          self._tree_nodes.append(new_tree_node)
          self._tree_node_map[tree_node_name] = new_tree_node
-
-         new_tree_node._conditional_probability = node_probability_map[tree_node_name].value
-
-         if tree_node_name not in node_stage_ids:
-            raise ValueError, "No stage is assigned to tree node=" + tree_node._name
-         else:
-            stage_name = node_stage_ids[new_tree_node._name].value
-            if stage_name not in self._stage_map.keys():
-               raise ValueError, "Unknown stage=" + stage_name + " assigned to tree node=" + tree_node._name
-            else:
-               new_tree_node._stage = self._stage_map[stage_name]
-               self._stage_map[stage_name]._tree_nodes.append(new_tree_node)
+         self._stage_map[stage_name]._tree_nodes.append(new_tree_node)
 
       # link up the tree nodes objects based on the child id sets.