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

Last change on this file since 1768 was 1768, checked in by wehart, 11 years ago

Rework of Coopr to use the new PyUtilib? package decomposition.

NOTE: to use Coopr with this update, we need to work with a new version of coopr_install.

File size: 8.2 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, reference_variable_indices) in stage._variables:
120               
121               reference_variable_name = reference_variable.name
122               
123               for tree_node in stage._tree_nodes:
124
125                  node_variable_average = tree_node._averages[reference_variable_name]
126                 
127                  for index in reference_variable_indices:
128                     
129                     is_used = True # until proven otherwise
130                     
131                     for scenario in tree_node._scenarios:
132                       
133                        instance = instances[scenario._name]
134                       
135                        if getattr(instance, reference_variable_name)[index].status == VarStatus.unused:
136                           is_used = False
137
138                     if is_used is True:
139                       
140                        for scenario in tree_node._scenarios:
141                           
142                           instance = instances[scenario._name]
143                           this_value = getattr(instance, reference_variable_name)[index].value
144                           term_diff += scenario._probability * fabs(this_value - node_variable_average[index]())
145
146      return term_diff
147
148
149#
150# Implements the normalized "term-diff" metric from our submitted CMS paper.
151# For each variable, take the fabs of the difference from the mean at that
152# node, and weight by scenario probability - but normalize by the mean.
153# If I wasn't being lazy, this could be derived from the TermDiffConvergence
154# class to avoid code replication :)
155#
156
157class NormalizedTermDiffConvergence(ConvergenceBase):
158
159   """ Constructor
160       Arguments: None beyond those in the base class.
161
162   """
163   def __init__(self, *args, **kwds):
164
165      ConvergenceBase.__init__(self, *args, **kwds)
166
167   def computeMetric(self, ph, scenario_tree, instances):
168
169      normalized_term_diff = 0.0
170
171      for stage in scenario_tree._stages:
172         
173         # we don't blend in the last stage, so we don't current care about printing the associated information.
174         if stage != scenario_tree._stages[-1]:
175
176            for (reference_variable, index_template, reference_variable_indices) in stage._variables:
177               
178               reference_variable_name = reference_variable.name
179               
180               for tree_node in stage._tree_nodes:
181
182                  node_variable_average = tree_node._averages[reference_variable_name]
183                 
184                  for index in reference_variable_indices:
185
186                     # should think about nixing the magic constant below (not sure how to best pararamterize it).
187                     if fabs(node_variable_average[index]()) > 0.0001: 
188                     
189                        is_used = True # until proven otherwise
190                     
191                        for scenario in tree_node._scenarios:
192                       
193                           instance = instances[scenario._name]
194                       
195                           if getattr(instance, reference_variable_name)[index].status == VarStatus.unused:
196                              is_used = False
197
198                        if is_used is True:
199
200                           average_value = node_variable_average[index]()
201                         
202                           for scenario in tree_node._scenarios:
203                           
204                              instance = instances[scenario._name]
205                              this_value = getattr(instance, reference_variable_name)[index].value
206                              normalized_term_diff += scenario._probability * fabs((this_value - average_value)/average_value)
207
208      return normalized_term_diff
209
210#
211# Implements a super-simple convergence criterion based on when a particular number of
212# discrete variables are free (e.g., 20 or fewer).
213#
214
215class NumFixedDiscreteVarConvergence(ConvergenceBase):
216
217   """ Constructor
218       Arguments: None beyond those in the base class.
219
220   """
221   def __init__(self, *args, **kwds):
222
223      ConvergenceBase.__init__(self, *args, **kwds)
224
225   def computeMetric(self, ph, scenario_tree, instances):
226
227      # the metric is brain-dead; just look at PH to see how many free discrete variables there are!
228      return ph._total_discrete_vars - ph._total_fixed_discrete_vars
229   
230                     
Note: See TracBrowser for help on using the repository browser.