1 /* $Id$
2 *
3 * Name: exprOp.cpp
4 * Author: Pietro Belotti
5 * Purpose: methods for multivariate function class
6 *
7 * (C) Carnegie-Mellon University, 2006-08.
8 * This file is licensed under the Eclipse Public License (EPL)
9 */
10
11 #include "CouenneExpression.hpp"
12 #include "CouenneExprAux.hpp"
13 #include "CouenneExprClone.hpp"
14 #include "CouenneExprOp.hpp"
15 #include "CouenneExprGroup.hpp"
16 #include "CouenneExprQuad.hpp"
17 #include "CouenneExprConst.hpp"
18 #include "CouennePrecisions.hpp"
19
20 #include <cstdio>
21
22 using namespace Couenne;
23
24 namespace Couenne {
25 class CouenneProblem;
26 class Domain;
27 }
28
29 // General N-ary function destructor
~exprOp()30 exprOp::~exprOp () {
31
32 if (arglist_) {
33 for (expression **alist = arglist_; nargs_--; alist++)
34 if (*alist) delete (*alist);
35 delete [] arglist_;
36 }
37 }
38
39
40 // print expression
41
print(std::ostream & out,bool descend) const42 void exprOp::print (std::ostream &out,
43 bool descend) const {
44
45 if (printPos () == PRE)
46 out << printOp ();
47
48 if (nargs_ > 1)
49 {out << "("; fflush (stdout);}
50 for (int i=0; i<nargs_; i++) {
51 if (arglist_ [i])
52 arglist_ [i] -> print (out, descend);
53 fflush (stdout);
54 if (i < nargs_ - 1) {
55 if (printPos () == INSIDE) out << printOp ();
56 else out << ",";
57 }
58 if (!((i + 1) % MAX_ARG_LINE))
59 out << std::endl;
60 fflush (stdout);
61 }
62 if (nargs_ > 1) {
63 out << ")";
64 fflush (stdout);
65 }
66 }
67
68
69 /// compare general n-ary expressions
70
compare(exprOp & e1)71 int exprOp::compare (exprOp &e1) {
72
73 int c0 = code (),
74 c1 = e1. code ();
75
76 if (c0 < c1) return -1;
77 if (c0 > c1) return 1;
78
79 // have to compare arguments one by one
80 if (nargs_ < e1.nargs_) return -1;
81 if (nargs_ > e1.nargs_) return 1;
82
83 // not an exprGroup, compare arguments
84 for (register int i = nargs_; i--;) {
85
86 int res = arglist_ [i] -> compare (*(e1. ArgList () [i]));
87 if (res) return res;
88 }
89
90 // last chance, this might be an exprGroup or derived
91 if ((c0 == COU_EXPRGROUP) ||
92 (c0 == COU_EXPRQUAD)) {
93
94 exprGroup *ne0 = dynamic_cast <exprGroup *> (this),
95 *ne1 = dynamic_cast <exprGroup *> (&e1);
96
97 int cg = ne0 -> compare (*ne1);
98
99 if (cg) return cg; // exprGroup
100
101 // last chance, the two are quadratic forms
102
103 if (c0 == COU_EXPRQUAD) {
104
105 exprQuad *ne0 = dynamic_cast <exprQuad *> (this),
106 *ne1 = dynamic_cast <exprQuad *> (&e1);
107
108 return ne0 -> compare (*ne1);
109 }
110 }
111
112 return 0;
113 }
114
115
116 /// used in rank-based branching variable choice
117
rank()118 int exprOp::rank () {
119
120 int maxrank = -1;
121
122 for (expression **al = arglist_ + nargs_;
123 al-- > arglist_;) {
124 int r = (*al) -> rank ();
125 if (r > maxrank) maxrank = r;
126 }
127
128 return (maxrank);
129 }
130
131
132 // Create standard formulation of this expression, by:
133 //
134 // - creating auxiliary w variables and corresponding expressions
135 // - returning linear counterpart as new constraint (to replace
136 // current one)
137 //
138 // For the base exprOp class we only do the first part (for argument
139 // list components only), and the calling class (Sum, Sub, Mul, Pow,
140 // and the like) will do the part for its own object
141
standardize(CouenneProblem * p,bool addAux)142 exprAux *exprOp::standardize (CouenneProblem *p, bool addAux) {
143
144 exprVar *subst;
145
146 for (int i = 0; i < nargs_; ++i)
147 if ((subst = arglist_ [i] -> standardize (p))) {
148
149 if ((subst -> Type () == VAR) ||
150 (subst -> Type () == AUX))
151 arglist_ [i] = new exprClone (subst);
152 else arglist_ [i] = subst; // possibly a constant, should be nothing else
153 }
154 return NULL;
155 }
156
157
158 /// replace variable x with new (aux) w
replace(exprVar * x,exprVar * w)159 void exprOp::replace (exprVar *x, exprVar *w) {
160
161 expression **al = arglist_;
162 int index = x -> Index ();
163
164 for (register int i = nargs_; i--; al++)
165
166 switch ((*al) -> Type ()) {
167
168 case AUX:
169 case VAR:
170 if ((*al) -> Index () == index) {
171 delete *al;
172 *al = new exprClone (w);
173 }
174 break;
175
176 case UNARY:
177 case N_ARY:
178 (*al) -> replace (x, w);
179 break;
180
181 default:
182 break;
183 }
184 }
185
186
187 /// is this expression integer?
isInteger()188 bool exprOp::isInteger () {
189
190 for (int i = nargs_; i--;)
191
192 if (!(arglist_ [i] -> isInteger ())) {
193
194 // this argument is not integer: check if constant and integer
195
196 CouNumber lb, ub;
197 arglist_ [i] -> getBounds (lb, ub);
198
199 if ((fabs (lb - ub) > COUENNE_EPS) ||
200 !::isInteger (lb))
201 return false;
202 }
203
204 return true;
205 }
206
207
208 /// fill in the set with all indices of variables appearing in the
209 /// expression
DepList(std::set<int> & deplist,enum dig_type type)210 int exprOp::DepList (std::set <int> &deplist,
211 enum dig_type type) {
212 int tot = 0;
213
214 //printf (" exprop::deplist of %x: ", Original ()); print (); printf ("\n");
215
216 for (int i = nargs_; i--;) {
217
218 /*printf (" ");
219 arglist_ [i] -> print (); printf (": {");
220 for (std::set <int>::iterator j=deplist.begin(); j != deplist.end(); ++j)
221 printf ("%d ", *j);
222 printf ("} -> {");*/
223
224 tot += arglist_ [i] -> DepList (deplist, type);
225
226 /*for (std::set <int>::iterator j=deplist.begin(); j != deplist.end(); ++j)
227 printf ("%d ", *j);
228 printf ("}\n");*/
229 }
230
231 return tot;
232 }
233
234 /// empty function to redirect variables to proper variable vector
realign(const CouenneProblem * p)235 void exprOp::realign (const CouenneProblem *p) {
236
237 for (int i=0; i<nargs_; i++)
238 arglist_ [i] -> realign (p);
239 }
240
241
242 // simplify n-ary expression f (g_1(x), g_2(x)... g_n(x))
simplify()243 expression *exprOp:: simplify () {
244
245 // Simplify arguments g_1(x), g_2(x)... g_n(x) first
246 for (int i=0; i<nargs_; i++) {
247
248 expression *subst;
249
250 if ((subst = arglist_ [i] -> simplify ())) {
251
252 delete arglist_ [i];
253 arglist_ [i] = subst;
254 }
255 }
256
257 return NULL;
258 }
259
260
261 //
262 // shrink argument list
263 //
264 // used by + and * (for now), accepts a constant resulting from
265 // applying an operator to the constants in the list of (pointers to)
266 // function arguments contained in el. The constant is inserted in the
267 // list if the result is not equal to null_element or if there are
268 // other non-constant terms in the arglist.
269 //
270 // Example: f(x) + 3 + g(x) + 2 + 4
271 //
272 // el = {pf, NULL, pg, NULL, NULL}
273 // nargs = 5
274 // c = 3 + 2 + 4 = 9
275 // null_element = 0 (for sums)
276 //
277 // where pf and pg are pointers to expression containing f and g,
278 // resp.
279 //
280 // Result: el and nargs are changed to
281 //
282 // el = {pf, p9, pg}
283 // nargs = 3
284 //
285 // Another example: f(x) + 2 + g(x) + (-4) + 2
286 // Result:
287 // el = {pf, pg}
288 // nargs = 2
289 //
290 // Another example: f(x) * 3 * g(x) * 2
291 //
292 // el = {pf, NULL, pg, NULL}
293 // nargs = 4
294 // c = 3 * 2 = 6 != null_element = 1 (for multiplications)
295 // Result:
296 // el = {pf, p6, pg}
297 // nargs = 3
298 //
299
shrink_arglist(CouNumber c,CouNumber null_element)300 int exprOp::shrink_arglist (CouNumber c, CouNumber null_element) {
301
302 register int i=0, j=0;
303
304 bool one_fun = false;
305
306 // find first NULL spot (left by some constant)
307 while ((i < nargs_) && (arglist_ [i]))
308 i++;
309
310 // no spots, leave
311 if (i==nargs_)
312 return 0;
313
314 // check if there is at least one non-constant expression
315 for (register int k=nargs_; k--;)
316 if (arglist_ [k]) {
317 one_fun = true;
318 break;
319 }
320
321 // add constant term if c is not null w.r.t. the operation or if it
322 // would be an empty operand list otherwise
323 if ((fabs (c - null_element) > COUENNE_EPS) || !one_fun)
324 arglist_ [i++] = new exprConst (c);
325
326 j = i;
327
328 // now shift back all operands to compress argument list
329 while (i < nargs_) {
330
331 while ((i < nargs_) && !(arglist_ [i]))
332 i++;
333
334 if (i < nargs_)
335 one_fun = true;
336
337 while ((i < nargs_) && (arglist_ [i]))
338 arglist_ [j++] = arglist_ [i++];
339 }
340
341 nargs_ = j;
342
343 // only say shrinking simplified arg list if there is just the
344 // constant
345 return (nargs_ == 1);// && ((fabs (c - null_element) > COUENNE_EPS) || !one_fun));
346 }
347