source: coopr.pysp/stable/coopr/pysp/convergence.py @ 3286

Last change on this file since 3286 was 3286, checked in by wehart, 10 years ago

Merged revisions 3187-3285 via svnmerge from
https://software.sandia.gov/svn/public/coopr/coopr.pysp/trunk

........

r3201 | jwatson | 2010-10-29 13:18:17 -0600 (Fri, 29 Oct 2010) | 3 lines


Inverting order of .dat files in PySP when loading from a node representation - now root-to-leaf, instead of leaf-to-root. This allows for deeper-in-the-tree nodes to over-write parameter values defined higher in the tree, which is a more "expected" behavior than the converse. The real answer is to throw an exception if a parameter is re-defined, but we're not there yet.

........

r3217 | jwatson | 2010-11-05 11:29:42 -0600 (Fri, 05 Nov 2010) | 3 lines


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

........

r3218 | jwatson | 2010-11-05 12:35:51 -0600 (Fri, 05 Nov 2010) | 3 lines


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

........

r3220 | jwatson | 2010-11-05 20:28:29 -0600 (Fri, 05 Nov 2010) | 3 lines


Various fixes to the WW PH extension, bringing it in compliance to previous commit changes.

........

r3221 | jwatson | 2010-11-05 20:43:40 -0600 (Fri, 05 Nov 2010) | 1 line


Removing some older PySP test problems from the repository

........

r3222 | jwatson | 2010-11-05 20:55:15 -0600 (Fri, 05 Nov 2010) | 1 line


Moving PySP forestry example to local sandbox, to streamline distribution.

........

r3261 | jwatson | 2010-11-29 15:26:46 -0700 (Mon, 29 Nov 2010) | 9 lines


Adding two options to the runef and runph pysp scripts, to facilitate scenario downsampling - the case where you have a big tree, but you don't want to use it all.


The options are:
--scenario-tree-downsample-fraction=X
--scenario-tree-random-seed


The options are fairly self-explanatory - the only possible nuance is that the downsample fraction is the fraction of scenarios retained.

........

r3263 | jwatson | 2010-12-01 10:47:21 -0700 (Wed, 01 Dec 2010) | 3 lines


Corrected issue with cvar generation introduced a while back.

........

r3264 | jwatson | 2010-12-01 11:16:01 -0700 (Wed, 01 Dec 2010) | 3 lines


Adding PySP extensive form tests.

........

r3265 | wehart | 2010-12-01 13:19:56 -0700 (Wed, 01 Dec 2010) | 2 lines


Auxmenting the filter

........

r3266 | wehart | 2010-12-01 13:58:59 -0700 (Wed, 01 Dec 2010) | 2 lines


Adding further diagnostics to the filter.

........

r3267 | wehart | 2010-12-01 14:12:15 -0700 (Wed, 01 Dec 2010) | 2 lines


Another attempt to fix this filter...

........

r3271 | wehart | 2010-12-01 15:51:23 -0700 (Wed, 01 Dec 2010) | 4 lines


Simplifying filter.


The error was really a Python 2.5 portability issue in EF. :(

........

r3275 | jwatson | 2010-12-02 19:35:52 -0700 (Thu, 02 Dec 2010) | 3 lines


Fixing Python 2.5-related issue with string.translate in phutils.py - using None as the translation table is not allowed in Python 2.5.

........

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.