source: trunk/coopr/pyomo/presolve/collect_linear_terms.py @ 1750

Last change on this file since 1750 was 1750, checked in by jwatson, 11 years ago

Added diagnostics to collect_linear_terms.py presolver to handle cases where a parameter value is specified as an expression. This currently yields illegal files when writing models for solution (e.g., in the CPXLP format), as the value of the expressions is the name of the operation of the expression tree.

Expressions might be OK in this context (I have initiated an e-mail thread), but it will require some discussion and subsequent modification of collect_linear_terms.py.

File size: 8.4 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
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.SingletonPlugin):
23    """
24    This plugin processes a Pyomo Model instance to collect
25    linear terms.
26    """
27
28    pyutilib.plugin.implements(IPyomoPresolveAction)
29
30    def __init__(self, **kwds):
31        kwds['name'] = "collect_linear_terms"
32        pyutilib.plugin.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.