source: trunk/coopr/pyomo/presolve/collect_linear_terms.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.5 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 FAST README.txt file.
9#  _________________________________________________________________________
10
11
12import pyutilib.plugin.core
13from coopr.pyomo.base import expr, _VarBase, Constraint, Objective
14from coopr.pyomo.base.numvalue import NumericConstant
15from coopr.pyomo.base.var import _VarValue
16from coopr.pyomo.base import IPyomoPresolver, IPyomoPresolveAction
17
18import string
19import StringIO
20
21
22class CollectLinearTerms(pyutilib.plugin.core.SingletonPlugin):
23    """
24    This plugin processes a Pyomo Model instance to collect
25    linear terms.
26    """
27
28    pyutilib.plugin.core.implements(IPyomoPresolveAction)
29
30    def __init__(self, **kwds):
31        kwds['name'] = "collect_linear_terms"
32        pyutilib.plugin.core.Plugin.__init__(self, **kwds)
33
34    def rank(self):
35        return 10000
36
37    #
38    # Identify variables and confirm that the expression is linear
39    #
40    def _Collect2(self, exp, x, scale=1.0):
41        #
42        # Ignore identity expressions
43        #
44        while isinstance(exp,expr._IdentityExpression):
45            exp = exp._args[0]
46        #
47        # Expression
48        #
49        if isinstance(exp,expr.Expression):
50           #
51           # Sum
52           #
53           if isinstance(exp,expr._SumExpression):
54              for i in xrange(len(exp._args)):
55                x = self._Collect2(exp._args[i], x, scale*exp._coef[i])
56              c = exp._const * scale
57              if "0" in x:
58                   xv = x["0"]
59                   x["0"] = (xv[0]+c,xv[1])
60              else:
61                   x["0"] = (c,"0")
62           #
63           # Product
64           #
65           elif isinstance(exp,expr._ProductExpression):
66              c = scale * exp.coef
67              ve = v = "0"
68              for e in exp._numerator:
69                 if e.fixed_value():
70                     # at this point, we have checked that the expression has a fixed value.
71                     # however, that check isn't particularly strong, as the "fixedness" of
72                     # something is typically a function of the class, e.g., numeric values or
73                     # parameter values. it is currently possible to specify expressions for
74                     # parameter values, which is something to warn on and completely chokes
75                     # the presolve.
76                     if isinstance(e.value, expr.Expression):
77                        value_as_string = StringIO.StringIO()
78                        e.value.pprint(ostream=value_as_string)
79                        raise AttributeError, "Expression encountered where fixed value (probably a parameter) was expected - offending subexpression="+string.strip(value_as_string.getvalue())
80                     c *= e.value
81                 else:
82                     if not v is "0":
83                         raise ValueError, "Nonlinear expression: found two non-fixed variables in ProductExpression"
84                     if hasattr(e, "label") is False:
85                        expression_string = StringIO.StringIO()
86                        e.pprint(ostream=expression_string)
87                        msg = "No label for expression object="+string.strip(expression_string.getvalue())+" of type="+str(type(e))
88                        raise AttributeError, msg
89                     v = e.label
90                     ve = e
91              for e in exp._denominator:
92                   if e.fixed_value():
93                       c /= e.value
94                   else:
95                           raise ValueError, "Nonlinear expression: found variable in denominator"
96              if v in x:
97                 xv = x[v]
98                 x[v] = (xv[0]+c,xv[1])
99              else:
100                 x[v] = (c,ve)
101           #
102           # ERROR
103           #
104           else:
105              raise ValueError, "Unsupported expression type: "+str(exp)
106        #
107        # Constant
108        #
109        elif exp.fixed_value():
110           c = exp.value * scale
111           if "0" in x:
112              xv = x["0"]
113              x["0"] = (xv[0]+c,xv[1])
114           else:
115              x["0"] = (c,"0")
116        #
117        # Variable
118        #
119        elif isinstance(exp,_VarValue):
120          v = exp.label
121          if v in x:
122               xv = x[v]
123               x[v] = (xv[0] + scale, xv[1])
124          else:
125               x[v] = (scale, exp)
126        #
127        # ERROR
128        #
129        else:
130           raise ValueError, "Unexpected expression type in _Collect2:"+str(exp)
131        return x
132
133    def _Collect3(self, exp):
134        """
135        The highest-level linear term collection process for an expression.
136        Pretty much just a simple filter over _Collect2.
137        """
138        # the 'x' is just a dictonary mapping variable names to (coefficient, VarValue) pairs.
139        x = self._Collect2(exp,{})
140        # the 'y' is just a reduction of 'x' that eliminates entries with coefficients = 0.0.
141        y = {}
142        for i in x:
143           if x[i][0] != 0.:
144              y[i] = x[i]
145        return y
146
147    def presolve(self,model):
148        """
149        The main routine to perform the presolve
150        """
151        Vars = model._component[_VarBase]
152        Con = model._component[Constraint]
153        Obj = model._component[Objective]
154        #
155        # Collect the linear terms
156        #
157        # Objectives
158        #
159        Obj1 = []
160        for key in Obj.keys():
161            obj = Obj[key]
162            obj._linterm = {}
163            Onz = []
164            nt = 0
165            for ondx in obj._data:
166                if obj._data[ondx].expr is None:
167                    raise ValueError, "No expression has been defined for objective %s" % str(key)
168                t = obj._linterm[ondx] = self._Collect3(obj._data[ondx].expr)
169                lt = len(t)
170                if lt > 0:
171                    Onz.append(ondx)
172                    nt += 1
173            if nt > 0:
174                Obj1.append(key)
175            obj._Onz = Onz
176        model.Onontriv = Obj1
177        #
178        # Constraints
179        #
180
181        # there are currently expressions within pyomo that the collect routines
182        # have issues with - most notably, _SumExpression objects not having labels
183        # (which of course they don't). we are working to fix this issue, but in
184        # the meantime, we are providing a bit more context regarding which specific
185        # constraint is causing the issue.
186
187        # a model maintains a list of constraints with at least one non-empty expression index.
188        # attribute is "Cnontriv" - see set below.
189        Con1 = [] 
190        for key in Con.keys():
191           C = Con[key]
192           # for each constraint, a map between each index and the associated linear term construct.             
193           C._linterm = {}
194           # each constraint tracks a list of the indices with non-empty expressions.
195           # attribute is _Cnz - see set below.             
196           Cnz = [] 
197           nt = 0 # track number of constraint indicies with non-trivial bodies
198           for cndx in C.keys():
199                 
200#              print "Collecting linear terms for constraint="+key+"["+str(cndx)+"]"
201#              junk = StringIO.StringIO()
202#              C._data[cndx].body.pprint(ostream=junk)                 
203#              print "CONSTRAINT BODY:"+string.strip(junk.getvalue())
204
205              try:                 
206                 t = C._linterm[cndx] = self._Collect3(C._data[cndx].body)
207              except AttributeError, msg:
208                 print "***Error encountered in class CollectLinearTerms, method=presolve, encountered when invoking _Collect3 on constraint="+key+"["+str(cndx)+"]"
209                 constraint_as_string = StringIO.StringIO()
210                 C._data[cndx].body.pprint(ostream=constraint_as_string)                                 
211                 print "***Constraint body:"+string.strip(constraint_as_string.getvalue())
212                 print "***Problem: "+str(msg)
213                 raise RuntimeError
214                 
215              if len(t) > 0:
216                 Cnz.append(cndx)
217                 nt += 1
218                   
219           if nt > 0:
220              Con1.append(key)
221           C._Cnz = Cnz
222        model.Cnontriv = Con1
223
224        #
225        # Return modified instance
226        #
227        return model
228
Note: See TracBrowser for help on using the repository browser.