1 | /* |
---|
2 | * Name: expression.h |
---|
3 | * Author: Pietro Belotti |
---|
4 | * Purpose: definition of the class expression |
---|
5 | * |
---|
6 | * (C) Pietro Belotti. This file is licensed under the Common Public License (CPL) |
---|
7 | */ |
---|
8 | |
---|
9 | #ifndef COUENNE_EXPRESSION_H |
---|
10 | #define COUENNE_EXPRESSION_H |
---|
11 | |
---|
12 | #define STACK_SIZE 100000 |
---|
13 | |
---|
14 | #include <iostream> |
---|
15 | #include <CouennePrecisions.h> |
---|
16 | #include <CouenneTypes.h> |
---|
17 | |
---|
18 | class CouenneProblem; |
---|
19 | class CouenneCutGenerator; |
---|
20 | class exprAux; |
---|
21 | class OsiSolverInterface; |
---|
22 | class OsiCuts; |
---|
23 | class exprUnary; |
---|
24 | class exprOp; |
---|
25 | class exprCopy; |
---|
26 | |
---|
27 | // expression base class |
---|
28 | |
---|
29 | class expression { |
---|
30 | |
---|
31 | protected: |
---|
32 | |
---|
33 | /// Static members to be used "globally" by an expression upon |
---|
34 | /// evaluation with a given value of the variables' or the bounds' |
---|
35 | /// vectors. |
---|
36 | /// |
---|
37 | /// stack is used in evaluation as a LIFO structure where all |
---|
38 | /// arguments of an expression (which are expressions themselves) are |
---|
39 | /// stored (with a PUSH-like operation) after being evaluated, for |
---|
40 | /// the current node to process them with a POP operation. PUSH and |
---|
41 | /// POP operations are the *++sp and *sp-- instructions, |
---|
42 | /// respectively, on the Stack Pointer variable sp. |
---|
43 | /// |
---|
44 | /// STACK_SIZE should be enough for expressions where at each node of |
---|
45 | /// the evaluation tree, DEPTH + #ARGUMENTS is at most STACK_SIZE, |
---|
46 | /// where DEPTH is the depth of the evaluation node and #ARGUMENTS is |
---|
47 | /// the number of arguments of the function in the node. |
---|
48 | /// |
---|
49 | /// UPDATE (04/12/07): no longer used, keep for possible new |
---|
50 | /// operators |
---|
51 | |
---|
52 | static CouNumber stack [STACK_SIZE]; |
---|
53 | static CouNumber *sp; |
---|
54 | |
---|
55 | /// these "global" variables, static members of expression, contain |
---|
56 | /// the current value of the variables' and bounds' vectors. The |
---|
57 | /// former vector is used to compute the value of the expression, for |
---|
58 | /// instance when using a non-linear solver that requires evaluation |
---|
59 | /// of all expressions in the problem. The latter is used when |
---|
60 | /// updating the problem after a change in the variables' bounds. |
---|
61 | /// |
---|
62 | /// CAUTION: every time an expression (or a set) is evaluated, the |
---|
63 | /// user can (SHOULD) tell the program to synchronize with her/his |
---|
64 | /// own vectors by calling the method expression::update (myvars, |
---|
65 | /// mylbounds, myubounds) below. |
---|
66 | |
---|
67 | static CouNumber *variables_; |
---|
68 | static CouNumber *lbounds_; |
---|
69 | static CouNumber *ubounds_; |
---|
70 | |
---|
71 | /// current value of the expression, used when accessing a copy of |
---|
72 | /// the expression created for a node that is evaluated after the |
---|
73 | /// original (saves some time). |
---|
74 | |
---|
75 | CouNumber currValue_; |
---|
76 | |
---|
77 | public: |
---|
78 | |
---|
79 | /// update the value of "external" vectors (if the addresses have not |
---|
80 | /// changed, it is not needed) |
---|
81 | static inline void update (CouNumber *variables = NULL, |
---|
82 | CouNumber *lbounds = NULL, |
---|
83 | CouNumber *ubounds = NULL) { |
---|
84 | |
---|
85 | if (variables) variables_ = variables; |
---|
86 | if (lbounds) lbounds_ = lbounds; |
---|
87 | if (ubounds) ubounds_ = ubounds; |
---|
88 | } |
---|
89 | |
---|
90 | /// return current values of variables and bounds |
---|
91 | static CouNumber Lbound (int i) {return lbounds_ [i];} |
---|
92 | static CouNumber Ubound (int i) {return ubounds_ [i];} |
---|
93 | static CouNumber Variable (int i) {return variables_ [i];} // allow to set it |
---|
94 | |
---|
95 | /// Constructor, destructor |
---|
96 | expression () {} |
---|
97 | expression (const expression &e) {} |
---|
98 | virtual ~expression () {} |
---|
99 | |
---|
100 | /// cloning method |
---|
101 | virtual expression *clone () const |
---|
102 | {return new expression (*this);} |
---|
103 | |
---|
104 | /// return index of variable (only valid for exprVar and exprAux) |
---|
105 | virtual inline int Index () const |
---|
106 | {return -1;} |
---|
107 | |
---|
108 | /// return number of arguments (when applicable, that is, with N-ary functions) |
---|
109 | virtual inline int nArgs () const |
---|
110 | {return 0;} |
---|
111 | |
---|
112 | /// return arglist (when applicable, that is, with N-ary functions) |
---|
113 | virtual inline expression **ArgList () const |
---|
114 | {return NULL;} |
---|
115 | |
---|
116 | /// return argument (when applicable, i.e., with univariate functions) |
---|
117 | virtual inline expression *Argument () const |
---|
118 | {return NULL;} |
---|
119 | |
---|
120 | /// return pointer to argument (when applicable, i.e., with univariate functions) |
---|
121 | virtual inline expression **ArgPtr () |
---|
122 | {return NULL;} |
---|
123 | |
---|
124 | /// node type |
---|
125 | virtual inline enum nodeType Type () |
---|
126 | {return EMPTY;} |
---|
127 | |
---|
128 | /// value (empty) |
---|
129 | virtual inline CouNumber Value () const |
---|
130 | {return currValue_;} |
---|
131 | |
---|
132 | /// If this is an exprClone of a exprClone of an expr???, point to |
---|
133 | /// the original expr??? instead of an exprClone -- improve computing |
---|
134 | /// efficiency. Only overloaded for exprClones/exprCopy, of course. |
---|
135 | virtual inline const expression *Original () const |
---|
136 | {return this;} |
---|
137 | |
---|
138 | /// I/O |
---|
139 | virtual void print (std::ostream &s) const {s << '?';} |
---|
140 | |
---|
141 | /// null function for evaluating the expression |
---|
142 | virtual inline CouNumber operator () () |
---|
143 | {return 0;} |
---|
144 | |
---|
145 | /// differentiation |
---|
146 | virtual inline expression *differentiate (int) |
---|
147 | {return NULL;} |
---|
148 | |
---|
149 | /// dependence on variable set |
---|
150 | virtual inline bool dependsOn (int *, int) |
---|
151 | {return false;} |
---|
152 | |
---|
153 | /// simplify expression (useful for derivatives) |
---|
154 | virtual inline expression *simplify () |
---|
155 | {return NULL;} |
---|
156 | |
---|
157 | /// get a measure of "how linear" the expression is (see CouenneTypes.h) |
---|
158 | virtual inline int Linearity () |
---|
159 | {return NONLINEAR;} |
---|
160 | |
---|
161 | /// is this expression integer? |
---|
162 | virtual bool isInteger () |
---|
163 | {return false;} |
---|
164 | |
---|
165 | /// Get lower and upper bound of an expression (if any) |
---|
166 | virtual void getBounds (expression *&, expression *&); |
---|
167 | |
---|
168 | /// Create standard form of this expression, by: |
---|
169 | /// |
---|
170 | /// - creating auxiliary w variables and corresponding expressions |
---|
171 | /// - returning linear counterpart as new constraint (to replace |
---|
172 | /// current one) |
---|
173 | /// |
---|
174 | /// For the base exprOp class we only do the first part (for argument |
---|
175 | /// list components only), and the calling class (Sum, Sub, Mul, Pow, |
---|
176 | /// and the like) will do the part for its own object |
---|
177 | virtual inline exprAux *standardize (CouenneProblem *) |
---|
178 | {return NULL;} |
---|
179 | |
---|
180 | /// generate convexification cut for constraint w = this |
---|
181 | virtual void generateCuts (exprAux *, const OsiSolverInterface &, |
---|
182 | OsiCuts &, const CouenneCutGenerator *) {} |
---|
183 | |
---|
184 | /// return an index to the variable's argument that is better fixed |
---|
185 | /// in a branching rule for solving a nonconvexity gap |
---|
186 | virtual expression *getFixVar () |
---|
187 | {printf ("Warning: expression::getFixIndex()\n"); return NULL;} |
---|
188 | |
---|
189 | /// return integer for comparing expressions (used to recognize |
---|
190 | /// common expression) |
---|
191 | virtual enum expr_type code () |
---|
192 | {return COU_EXPRESSION;} |
---|
193 | |
---|
194 | /// either CONVEX, CONCAVE, AFFINE, or NONCONVEX |
---|
195 | virtual enum convexity convexity () |
---|
196 | {return NONCONVEX;} |
---|
197 | |
---|
198 | /// compare expressions |
---|
199 | virtual int compare (expression &); |
---|
200 | virtual int compare (exprCopy &); |
---|
201 | |
---|
202 | /// used in rank-based branching variable choice: original variables |
---|
203 | /// have rank 1; auxiliary w=f(x) has rank r(w) = r(x)+1; finally, |
---|
204 | /// auxiliary w=f(x1,x2...,xk) has rank r(w) = 1+max{r(xi):i=1..k}. |
---|
205 | virtual int rank (CouenneProblem *p = NULL) |
---|
206 | {return -1;} // return null rank |
---|
207 | |
---|
208 | /// does a backward implied bound processing on every expression, |
---|
209 | /// including exprSums although already done by Clp (useful when |
---|
210 | /// repeated within Couenne). Parameters are the index of the |
---|
211 | /// (auxiliary) variable in question and the current lower/upper |
---|
212 | /// bound. The method returns the best bound improvement obtained on |
---|
213 | /// all variables of the expression. |
---|
214 | virtual bool impliedBound (int, CouNumber *, CouNumber *, char *) |
---|
215 | {return false;} |
---|
216 | |
---|
217 | /// multiplicity of a variable |
---|
218 | virtual int Multiplicity () |
---|
219 | {return 1;} |
---|
220 | }; |
---|
221 | |
---|
222 | |
---|
223 | /// updates maximum violation. Used with all impliedBound. Returns 1 |
---|
224 | /// if a bound has been modified, 0 otherwise |
---|
225 | |
---|
226 | inline bool updateBound (int sign, CouNumber *dst, CouNumber src) { |
---|
227 | |
---|
228 | register CouNumber delta = src - *dst; |
---|
229 | |
---|
230 | if (sign > 0) |
---|
231 | delta = - delta; |
---|
232 | |
---|
233 | // meaning: |
---|
234 | // |
---|
235 | // if (*dst > src) && (sign > 0) --> dst down to src |
---|
236 | // if (*dst < src) && (sign < 0) --> dst up to src |
---|
237 | // |
---|
238 | // that is, sign > 0 means we are tightening an UPPER bound |
---|
239 | // sign < 0 LOWER |
---|
240 | |
---|
241 | if (delta > COUENNE_EPS) { |
---|
242 | //printf ("%.9f --> %.9f\n", *dst, src); |
---|
243 | *dst = src; // tighten |
---|
244 | return true; |
---|
245 | } |
---|
246 | |
---|
247 | return false; |
---|
248 | } |
---|
249 | |
---|
250 | /// independent comparison |
---|
251 | inline int compareExpr (const void *e0, const void *e1) { |
---|
252 | return ((*(expression **) e0) -> compare (**(expression **)e1)); |
---|
253 | } |
---|
254 | |
---|
255 | /// maximum |
---|
256 | inline CouNumber mymin (register CouNumber a, register CouNumber b) |
---|
257 | {return ((a<b) ? a : b);} |
---|
258 | |
---|
259 | /// minimum |
---|
260 | inline CouNumber mymax (register CouNumber a, register CouNumber b) |
---|
261 | {return ((a>b) ? a : b);} |
---|
262 | |
---|
263 | #endif |
---|