source: coopr.pysp/trunk/coopr/pysp/convergence.py @ 3261

Last change on this file since 3261 was 3217, checked in by jwatson, 10 years ago

Various updates to support heteogeneous index sets in PH for different nodes in the scenario tree - more work / testing remains.

File size: 8.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
13from coopr.pyomo import *
14import copy
15import os.path
16import traceback
17
18from math import fabs
19
20from scenariotree import *
21
22#
23# This module contains a hierarchy of convergence "computers" for PH (or any
24# other scenario-based decomposition strategy). Their basic function is to
25# compute some measure of convergence among disparate scenario solutions,
26# and to track the corresponding history of the metric. the sole inputs
27# are a scenario tree and a (time-varying) set of instances (with solutions).
28#
29
30class ConvergenceBase(object):
31
32   """ Constructor   
33       Arguments:
34          convergence_threshold          numeric threshold at-or-below which a set of scenario solutions is considered converged. must be >= 0.0.
35   """
36   def __init__(self, *args, **kwds):
37
38      # key is the iteration number, passed in via the update() method.
39      self._metric_history = {}
40
41      # the largest iteration key thus far - we assume continugous values from 0.
42      self._largest_iteration_key = 0
43
44      # at what point do I consider the scenario solution pool converged?
45      self._convergence_threshold = 0.0
46
47      for key in kwds.keys():
48         if key == "convergence_threshold":
49            self._convergence_threshold = kwds[key]
50         else:
51            print "Unknown option=" + key + " specified in call to ConvergenceBase constructor"
52
53   def reset(self):
54
55      self._metric_history.clear()
56
57   def lastMetric(self):
58
59      if len(self._metric_history) == 0:
60         raise RuntimeError, "ConvergenceBase::lastMetric() invoked with 0-length history"
61
62      last_key = self._metric_history.keys()[-1]
63      return self._metric_history[last_key]
64
65   def update(self, iteration_id, ph, scenario_tree, instances):
66
67      current_value = self.computeMetric(ph, scenario_tree, instances)
68      self._metric_history[iteration_id] = current_value
69      self._largest_iteration_key = max(self._largest_iteration_key, iteration_id)
70
71   def computeMetric(self, ph, scenario_tree, solutions):
72
73      raise RuntimeError, "ConvergenceBase::computeMetric() is an abstract method"
74
75   def isConverged(self, ph):
76
77      if (ph._total_discrete_vars > 0) and (ph._total_discrete_vars == ph._total_fixed_discrete_vars):
78         return True
79      else:
80         return self.lastMetric() <= self._convergence_threshold
81
82   def isImproving(self, iteration_lag):
83
84      last_iteration = self._largest_iteration_key
85      reference_iteration = min(0,self._largest_iteration_key - iteration_lag)
86      return self._metric_history[last_iteration] < self._metric_history[reference_iteration]
87
88   def pprint(self):
89
90      print "Iteration    Metric Value"
91      for key in self._metric_history.keys():
92         print ' %5d       %12.4f' % (key, self._metric_history[key])
93
94#
95# Implements the baseline "term-diff" metric from our submitted CMS paper.
96# For each variable, take the fabs of the difference from the mean at that
97# node, and weight by scenario probability.
98#
99
100class TermDiffConvergence(ConvergenceBase):
101
102   """ Constructor
103       Arguments: None beyond those in the base class.
104
105   """
106   def __init__(self, *args, **kwds):
107
108      ConvergenceBase.__init__(self, *args, **kwds)
109
110   def computeMetric(self, ph, scenario_tree, instances):
111
112      term_diff = 0.0
113
114      for stage in scenario_tree._stages:
115         
116         # we don't blend in the last stage, so we don't current care about printing the associated information.
117         if stage != scenario_tree._stages[-1]:
118
119            for (reference_variable, index_template) in stage._variables:
120               
121               reference_variable_name = reference_variable.name
122               
123               for tree_node in stage._tree_nodes:
124
125                  variable_indices = tree_node._variable_indices[reference_variable_name]
126
127                  node_variable_average = tree_node._averages[reference_variable_name]
128                 
129                  for index in variable_indices:
130                     
131                     is_used = True # until proven otherwise
132                     
133                     for scenario in tree_node._scenarios:
134                       
135                        instance = instances[scenario._name]
136                       
137                        if getattr(instance, reference_variable_name)[index].status == VarStatus.unused:
138                           is_used = False
139
140                     if is_used is True:
141                       
142                        for scenario in tree_node._scenarios:
143                           
144                           instance = instances[scenario._name]
145                           this_value = getattr(instance, reference_variable_name)[index].value
146                           term_diff += scenario._probability * fabs(this_value - value(node_variable_average[index]))
147
148      return term_diff
149
150
151#
152# Implements the normalized "term-diff" metric from our submitted CMS paper.
153# For each variable, take the fabs of the difference from the mean at that
154# node, and weight by scenario probability - but normalize by the mean.
155# If I wasn't being lazy, this could be derived from the TermDiffConvergence
156# class to avoid code replication :)
157#
158
159class NormalizedTermDiffConvergence(ConvergenceBase):
160
161   """ Constructor
162       Arguments: None beyond those in the base class.
163
164   """
165   def __init__(self, *args, **kwds):
166
167      ConvergenceBase.__init__(self, *args, **kwds)
168
169   def computeMetric(self, ph, scenario_tree, instances):
170
171      normalized_term_diff = 0.0
172
173      for stage in scenario_tree._stages:
174         
175         # we don't blend in the last stage, so we don't current care about printing the associated information.
176         if stage != scenario_tree._stages[-1]:
177
178            for (reference_variable, index_template) in stage._variables:
179               
180               reference_variable_name = reference_variable.name
181               
182               for tree_node in stage._tree_nodes:
183
184                  node_variable_average = tree_node._averages[reference_variable_name]
185
186                  variable_indices = tree_node._variable_indices[reference_variable_name]                 
187                 
188                  for index in variable_indices:
189
190                     # should think about nixing the magic constant below (not sure how to best pararamterize it).
191                     if fabs(value(node_variable_average[index])) > 0.0001: 
192                     
193                        is_used = True # until proven otherwise
194                     
195                        for scenario in tree_node._scenarios:
196                       
197                           instance = instances[scenario._name]
198                       
199                           if getattr(instance, reference_variable_name)[index].status == VarStatus.unused:
200                              is_used = False
201
202                        if is_used is True:
203
204                           average_value = value(node_variable_average[index])
205                         
206                           for scenario in tree_node._scenarios:
207                           
208                              instance = instances[scenario._name]
209                              this_value = getattr(instance, reference_variable_name)[index].value
210                              normalized_term_diff += scenario._probability * fabs((this_value - average_value)/average_value)
211
212      return normalized_term_diff
213
214#
215# Implements a super-simple convergence criterion based on when a particular number of
216# discrete variables are free (e.g., 20 or fewer).
217#
218
219class NumFixedDiscreteVarConvergence(ConvergenceBase):
220
221   """ Constructor
222       Arguments: None beyond those in the base class.
223
224   """
225   def __init__(self, *args, **kwds):
226
227      ConvergenceBase.__init__(self, *args, **kwds)
228
229   def computeMetric(self, ph, scenario_tree, instances):
230
231      # the metric is brain-dead; just look at PH to see how many free discrete variables there are!
232      return ph._total_discrete_vars - ph._total_fixed_discrete_vars
233   
234                     
Note: See TracBrowser for help on using the repository browser.