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 | |
---|
12 | import pyutilib.plugin |
---|
13 | from coopr.pyomo.base import expr, _VarBase, Constraint, Objective |
---|
14 | from coopr.pyomo.base.numvalue import NumericConstant |
---|
15 | from coopr.pyomo.base.var import _VarValue |
---|
16 | from coopr.pyomo.base import IPyomoPresolver, IPyomoPresolveAction |
---|
17 | |
---|
18 | import string |
---|
19 | import StringIO |
---|
20 | |
---|
21 | |
---|
22 | class 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 | |
---|