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

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

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

........

r3048 | jwatson | 2010-09-27 09:33:53 -0500 (Mon, 27 Sep 2010) | 3 lines


Modifying PySP CSV solution writer to eliminate leading and trailing parantheses from index names, change embedded commas with colons, and eliminate embedded spaces.

........

r3055 | khunter | 2010-09-30 14:11:13 -0500 (Thu, 30 Sep 2010) | 8 lines


Reorganization of the runph command line options into logical
groups. I might've messed up any intentional ordering within the
groups as I also alphabetized the options, so please to correct as
necessary.


Added -m and -i because Joe commented more than once on the
verbosity of the run(ef|ph) command lines.

........

r3056 | dlwoodr | 2010-09-30 16:41:52 -0500 (Thu, 30 Sep 2010) | 1 line

........

r3057 | dlwoodr | 2010-09-30 16:43:26 -0500 (Thu, 30 Sep 2010) | 1 line


The last check-in simply fixed the missing references problem. This document still needs to be brought up to date with the software (some command line options are not yet documented)

........

r3059 | dlwoodr | 2010-09-30 17:25:25 -0500 (Thu, 30 Sep 2010) | 1 line


Added most of the new command line options and made a few minor edits. Changed the version given as the title to 1.11 (from 1.1).

........

r3060 | dlwoodr | 2010-09-30 17:31:50 -0500 (Thu, 30 Sep 2010) | 1 line


Update the WW Comp Mgt Sci Reference

........

r3065 | jwatson | 2010-10-01 14:46:57 -0500 (Fri, 01 Oct 2010) | 3 lines


Reworked some of the options groups in the runph script, and created some new aliases.

........

r3072 | wehart | 2010-10-04 11:14:32 -0500 (Mon, 04 Oct 2010) | 2 lines


Fixes due to mutability change in coopr.pyomo.

........

r3073 | jwatson | 2010-10-04 20:35:24 -0500 (Mon, 04 Oct 2010) | 3 lines


Complete set of changes to make PySP compatible with latest immutable parameters change.

........

r3074 | jwatson | 2010-10-04 20:45:14 -0500 (Mon, 04 Oct 2010) | 3 lines


Added routines to the PySP scenario tree object to return the stage for a constraint and variable.

........

r3075 | jwatson | 2010-10-04 21:16:58 -0500 (Mon, 04 Oct 2010) | 3 lines


Forgot some debug output in the last commit.

........

r3078 | jwatson | 2010-10-05 09:46:33 -0500 (Tue, 05 Oct 2010) | 3 lines


Fixing long-present bug in network flow model, exposed by Bill's recent commit.

........

r3084 | jwatson | 2010-10-12 22:12:17 -0500 (Tue, 12 Oct 2010) | 3 lines


Fixed bug in constraint stage determination code in PySP - forgot to ignore constant terms, which of course don't have variables!

........

r3088 | jwatson | 2010-10-13 12:52:13 -0500 (Wed, 13 Oct 2010) | 3 lines


Added --traceback option to runph, in order to dump the full stack trace when an exception is thrown.

........

r3089 | jwatson | 2010-10-13 12:57:45 -0500 (Wed, 13 Oct 2010) | 3 lines


Added --traceback option to runef, mirroring recent modification to pysp.

........

r3092 | jwatson | 2010-10-13 14:13:23 -0500 (Wed, 13 Oct 2010) | 3 lines


Update to PySP to suppress canonical expression representations when using ASL. Otherwise, things choke badly.

........

r3093 | jwatson | 2010-10-13 14:38:37 -0500 (Wed, 13 Oct 2010) | 3 lines


More PySP fixes associated with ipopt integration. Nothing wrong with ipopt per se - it was just doing things we didn't expect, but were perfectly reasonable.

........

r3096 | jwatson | 2010-10-13 21:32:35 -0500 (Wed, 13 Oct 2010) | 3 lines


Enhancements to PySP to deal with reporting issues caused by the lack of objective function values in SOL files (in general, and those produced by ipopt in particular).

........

r3100 | khunter | 2010-10-14 15:54:49 -0500 (Thu, 14 Oct 2010) | 2 lines


NFC: remove EOL whitespace

........

r3101 | khunter | 2010-10-14 16:06:40 -0500 (Thu, 14 Oct 2010) | 3 lines


Reorganization of the runef command line options into logical
groups. Also alphabetized the options within the groups.

........

r3102 | khunter | 2010-10-14 16:07:47 -0500 (Thu, 14 Oct 2010) | 2 lines


Add -m and -i because there über common options.

........

r3104 | khunter | 2010-10-15 00:08:51 -0500 (Fri, 15 Oct 2010) | 3 lines


Fix an erroneous exit in the no traceback specified case, if not
exception has occurred.

........

r3105 | khunter | 2010-10-15 01:41:47 -0500 (Fri, 15 Oct 2010) | 2 lines


NFC: EOL whitespace removal

........

r3106 | khunter | 2010-10-15 01:43:00 -0500 (Fri, 15 Oct 2010) | 3 lines


Drive-by mild clean-up of an init function while I researching
another issue.

........

r3107 | jwatson | 2010-10-15 09:27:03 -0500 (Fri, 15 Oct 2010) | 3 lines


Minor touch-ups relating to traceback facilities.

........

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 - 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(value(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 = 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.