Changeset 3038

Timestamp:

Sep 22, 2010 5:12:01 PM (11 years ago)

Author:

jwatson

Message:

Fairly extensive re-work and simplification of the PySP extensive form writer, focusing on a cleaner implementation of the cvar term generation.

Location:

coopr.pysp/trunk/coopr/pysp

Files:

• ef.py (modified) (8 diffs)
• scenariotree.py (modified) (10 diffs)

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

@@ -69 +69 @@
 #       instances are associated with the extensive form. this might be something we
 #       encapsulate at some later time.
+# NOTE: if cvar terms are generated, then the input scenario tree is modified accordingly,
+#       i.e., with the addition of the "eta" variable at the root node and the excess
+#       variables at (for lack of a better place - they are per-scenario, but are not
+#       blended) the second stage.
 #
 
@@ -89 +93 @@
          print "CVaR alpha="+str(risk_alpha)
          print ""
+
+      # update the scenario tree with cvar-specific variable names, so
+      # they will get cloned accordingly in the master instance.
+      first_stage = scenario_tree._stages[0]
+      second_stage = scenario_tree._stages[1]
+      root_node = first_stage._tree_nodes[0]
+
+      # NOTE: because we currently don't have access to the reference
+      #       instance in this method, temporarily (and largely orphaned)
+      #       variables are constructed to supply to the scenario tree.
+      #       this decision should be ultimately revisited.
+      cvar_eta_variable_name = "CVAR_ETA"
+      cvar_eta_variable = Var(name=cvar_eta_variable_name)
+      cvar_eta_variable.construct()               
+
+      first_stage.add_variable(cvar_eta_variable, "*", [None])
+
+      cvar_excess_variable_name = "CVAR_EXCESS"
+      cvar_excess_variable = Var(name=cvar_excess_variable_name)
+      cvar_excess_variable.construct()
+
+      second_stage.add_variable(cvar_excess_variable, "*", [None])
+
+      # create the eta and excess variable on a per-scenario basis,
+      # in addition to the constraint relating to the two.
+      for scenario_name, scenario_instance in scenario_instances.items():
+
+         cvar_excess_variable_name = "CVAR_EXCESS"
+         cvar_excess_variable = Var(name=cvar_excess_variable_name, domain=NonNegativeReals)
+         cvar_excess_variable.construct()         
+         setattr(scenario_instance, cvar_excess_variable_name, cvar_excess_variable)
+
+         cvar_eta_variable_name = "CVAR_ETA"
+         cvar_eta_variable = Var(name=cvar_eta_variable_name)
+         cvar_eta_variable.construct()         
+         setattr(scenario_instance, cvar_eta_variable_name, cvar_eta_variable)
+
+         compute_excess_constraint_name = "COMPUTE_SCENARIO_EXCESS"
+         compute_excess_constraint = Constraint(name=compute_excess_constraint_name)
+         compute_excess_expression = cvar_excess_variable
+         for node in scenario_tree._scenario_map[scenario_name]._node_list:
+            (cost_variable, cost_variable_idx) = node._stage._cost_variable
+            compute_excess_expression -= getattr(scenario_instance, cost_variable.name)[cost_variable_idx]
+         compute_excess_expression += cvar_eta_variable
+         compute_excess_constraint.add(None, (0.0, compute_excess_expression, None))
+         compute_excess_constraint._model = scenario_instance
+         setattr(scenario_instance, compute_excess_constraint_name, compute_excess_constraint)
+
+         # re-process the scenario instance due to the newly added constraints/variables associated
+         # with CVaR. a complete preprocess is overkill, of course - the correct approach would be
+         # to just preprocess those newly added variables and constraints.
+         scenario_instance.preprocess()
 
    #
@@ -118 +174 @@
             if stage != scenario_tree._stages[-1]:      
 
-               master_variable_name = tree_node._name + "_" + stage_variable.name
+               master_variable_name = stage_variable.name               
 
                # because there may be a single stage variable and multiple indices, check
@@ -156 +212 @@
                   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]
@@ -181 +232 @@
          setattr(binding_instance, expected_cost_variable_name, expected_cost_variable)
 
-   # if we're generating the weighted CVaR objective term, create the
-   # corresponding variable and the master CVaR eta variable.
    if generate_weighted_cvar is True:
 
-      root_node = scenario_tree._stages[0]._tree_nodes[0]
-      
       cvar_cost_variable_name = "CVAR_COST_" + root_node._name
       cvar_cost_variable = Var(name=cvar_cost_variable_name)
+      cvar_cost_variable.construct()            
       setattr(binding_instance, cvar_cost_variable_name, cvar_cost_variable)
-      cvar_cost_variable.construct()
-
-      cvar_eta_variable_name = "CVAR_ETA_" + root_node._name
-      cvar_eta_variable = Var(name=cvar_eta_variable_name)
-      setattr(binding_instance, cvar_eta_variable_name, cvar_eta_variable)      
-      cvar_eta_variable.construct()
 
    binding_instance.preprocess()
@@ -245 +287 @@
    # 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:
 
@@ -284 +325 @@
                cvar_cost_variable = getattr(binding_instance, cvar_cost_variable_name)
                if cvar_weight == 0.0:
+                  # if the cvar weight is 0, then we're only doing cvar - no mean.
                   opt_expression = cvar_cost_variable                              
                else:
@@ -298 +340 @@
    if generate_weighted_cvar is True:
       
-      root_node = scenario_tree._stages[0]._tree_nodes[0]
-
-      master_cvar_eta_variable_name = "CVAR_ETA_" + root_node._name
-      master_cvar_eta_variable = getattr(binding_instance, master_cvar_eta_variable_name)
-      
-      for scenario_name in scenario_instances.keys():
-         scenario_instance = scenario_instances[scenario_name]
-
-         # unique names are required because the presolve isn't
-         # aware of the "owning" models for variables.
-         cvar_excess_variable_name = "CVAR_EXCESS_"+scenario_name
-         cvar_excess_variable = Var(name=cvar_excess_variable_name, domain=NonNegativeReals)
-         setattr(scenario_instance, cvar_excess_variable_name, cvar_excess_variable)
-         cvar_excess_variable.construct()
-
-         cvar_eta_variable_name = "CVAR_ETA"
-         cvar_eta_variable = Var(name=cvar_eta_variable_name)
-         setattr(scenario_instance, cvar_eta_variable_name, cvar_eta_variable)
-         cvar_eta_variable.construct()
-
-         compute_excess_constraint_name = "COMPUTE_SCENARIO_EXCESS"
-         compute_excess_constraint = Constraint(name=compute_excess_constraint_name)
-         compute_excess_expression = cvar_excess_variable
-         for node in scenario_tree._scenario_map[scenario_name]._node_list:
-            (cost_variable, cost_variable_idx) = node._stage._cost_variable
-            compute_excess_expression -= getattr(scenario_instance, cost_variable.name)[cost_variable_idx]
-         compute_excess_expression += cvar_eta_variable
-         compute_excess_constraint.add(None, (0.0, compute_excess_expression, None))
-         compute_excess_constraint._model = scenario_instance
-         setattr(scenario_instance, compute_excess_constraint_name, compute_excess_constraint)
-
-         eta_equality_constraint_name = "MASTER_ETA_EQUALITY_WITH_" + scenario_instance.name
-         eta_equality_constraint = Constraint(name=eta_equality_constraint_name)
-         eta_equality_expr = master_cvar_eta_variable - cvar_eta_variable
-         eta_equality_constraint.add(None, (0.0, eta_equality_expr, 0.0))
-         eta_equality_constraint._model = binding_instance
-         setattr(binding_instance, eta_equality_constraint_name, eta_equality_constraint)
-
-         # re-process the scenario instance due to the newly added constraints/variables associated
-         # with CVaR. a complete preprocess is overkill, of course - the correct approach would be
-         # to just preprocess those newly added variables and constraints.
-         scenario_instance.preprocess()
-
       # add the constraint to compute the master CVaR variable value. iterate
       # over scenario instances to create the expected excess component first.
       cvar_cost_variable_name = "CVAR_COST_" + root_node._name
       cvar_cost_variable = getattr(binding_instance, cvar_cost_variable_name)
-      cvar_eta_variable_name = "CVAR_ETA_" + root_node._name
+      cvar_eta_variable_name = "CVAR_ETA"
       cvar_eta_variable = getattr(binding_instance, cvar_eta_variable_name)
       
       cvar_cost_expression = cvar_cost_variable - cvar_eta_variable
       
-      for scenario_name in scenario_instances.keys():
-         scenario_instance = scenario_instances[scenario_name]
+      for scenario_name, scenario_instance in scenario_instances.items():
+
          scenario_probability = scenario_tree._scenario_map[scenario_name]._probability
 
-         scenario_excess_variable_name = "CVAR_EXCESS_"+scenario_name
+         scenario_excess_variable_name = "CVAR_EXCESS"
          scenario_excess_variable = getattr(scenario_instance, scenario_excess_variable_name)
 

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

@@ -23 +23 @@
 
    #
-   # initialize the _solutions attribute of a tree node.
-   #
-
-   def _initialize_solutions(self):
+   # update the _solutions attribute of a tree node, given a specific
+   # variable/match-template/variable-index triple. 
+   #
+   def _update_solution_map(self, variable, match_template, variable_indices):
+
+      # 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)
+      new_variable.construct()
+
+      # by default, deactive all variable values - we're copying the
+      # full index set of a variable, which is necessarily wasteful and
+      # incorrect. then, do a second pass and activate those indicies
+      # that are actually associated with this tree node.
+      for index in new_variable_index:
+         new_variable[index].deactivate()
+
+      for index in variable_indices:
+         new_variable[index].activate()
+
+      self._solutions[new_variable_name] = new_variable      
+
+   #
+   # initialize the _solutions attribute of a tree node, from scratch.
+   #
+
+   def _initialize_solution_map(self):
+
+      # clear whatever was there before.
+      self._solutions = {}
 
       # NOTE: Given the expense, this should really be optional - don't
@@ -36 +70 @@
       # 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)
-         new_variable.construct()
-
-         # by default, deactive all variable values - we're copying the
-         # full index set of a variable, which is necessarily wasteful and
-         # incorrect. then, do a second pass and activate those indicies
-         # that are actually associated with this tree node.
-         for index in new_variable_index:
-            new_variable[index].deactivate()
-
-         for index in variable_indices:
-            new_variable[index].activate()
-
-         self._solutions[new_variable_name] = new_variable
-
-      self._solutions_initialized = True
+         self._update_solution_map(variable, match_template, variable_indices)
+
+      self._solution_map_initialized = True
 
 
@@ -92 +102 @@
 
       # a flag indicating whether the _solutions attribute has been properly initialized.
-      self._solutions_initialized = False
+      self._solution_map_initialized = False
 
       # solution (variable) values for this node. assumed to be distinct
@@ -101 +111 @@
 
       if initialize_solution is True:
-         self._initialize_solutions()
+         self._initialize_solution_map()
 
    #
@@ -110 +120 @@
    def snapshotSolutionFromAverages(self):
 
-      if self._solutions_initialized is False:
-         self._initialize_solutions()
+      if self._solution_map_initialized is False:
+         self._initialize_solution_map()
 
       for variable_name, variable in self._solutions.items():
@@ -134 +144 @@
    def snapshotSolutionFromInstances(self, scenario_instance_map):
 
-      if self._solutions_initialized is False:
-         self._initialize_solutions()
+      if self._solution_map_initialized is False:
+         self._initialize_solution_map()
 
       for variable_name, variable in self._solutions.items():
@@ -174 +184 @@
    """
    def __init__(self, *args, **kwds):
+
       self._name = ""
-      self._tree_nodes = []      # a collection of ScenarioTreeNodes
-      # a collection of pairs consisting of (1) references to pyomo model Vars, (2) the original match template string (for output purposes),
-      # and (3) a *list* of the corresponding indices.
-      # the variables are references to those objects belonging to the instance in the parent ScenarioTree.
+      
+      # a collection of ScenarioTreeNode objects.
+      self._tree_nodes = []      
+      
+      # a collection of triples consisting of (1) a reference to a Pyomo model Var object, (2) the original match
+      # template string (for output purposes), and (3) a *list* of the corresponding indices. the variables are
+      # references to those objects belonging to the Pyomo reference scenario instance associated with the parent
+      # ScenarioTree of this Stage.
       # NOTE: if the variable index is none, it is assumed that the entire variable is blended.
       self._variables = []
-      # a tuple consisting of (1) a reference to a pyomo model Var that computes the stage-specific cost and (2) the corresponding index.
-      # the index *is* the sole index in the cost variable, as the cost variable refers to a single variable index.
+      
+      # a tuple consisting of (1) a reference to a pyomo model Var that computes the stage-specific cost and (2) the corresponding
+      # index. the index *is* the sole index in the cost variable, as the cost variable refers to a single variable index.
       self._cost_variable = (None, None)
+
+   #
+   # add a new variable to the stage, which will include updating the solution maps for each associated ScenarioTreeNode.
+   #
+   def add_variable(self, variable, match_template, indices):
+
+      self._variables.append((variable, match_template, indices))
+
+      for tree_node in self._tree_nodes:
+         tree_node._update_solution_map(variable, match_template, indices)
 
 class Scenario(object):
@@ -190 +216 @@
    """
    def __init__(self, *args, **kwds):
+      
       self._name = None
       self._leaf_node = None  # allows for construction of node list
@@ -328 +355 @@
    """
    def __init__(self, *args, **kwds):
-      self._name = None # TBD - some arbitrary identifier
-      self._reference_instance = None # TBD - the reference (deterministic) base model
+      
+      self._name = None # some arbitrary identifier
+      self._reference_instance = None # the reference (deterministic) base model
 
       # the core objects defining the scenario tree.
@@ -341 +369 @@
       self._scenario_map = {}
 
-      # mapping of stages to sets of variables which belong in the corresponding stage.
-      self._stage_variables = {}
-
       # a boolean indicating how data for scenario instances is specified.
       # possibly belongs elsewhere, e.g., in the PH algorithm.
       self._scenario_based_data = None
-
-      # every stage has a cost variable - this is a variable/index pair.
-      self._cost_variable = None
 
       scenario_tree_instance = None