source: branches/Couenne/Couenne/src/include/expression.h @ 497

Last change on this file since 497 was 497, checked in by pbelotti, 13 years ago

testing new conv-expr{Sin,Cos}. Added tool for deepest cut in exprPow

File size: 8.3 KB
Line 
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
18class CouenneProblem;
19class CouenneCutGenerator;
20class exprAux;
21class OsiSolverInterface;
22class OsiCuts;
23class exprUnary;
24class exprOp;
25class exprCopy;
26
27// expression base class
28
29class 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
226inline 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
251inline int compareExpr (const void *e0, const void *e1) {
252  return ((*(expression **) e0) -> compare (**(expression **)e1));
253}
254
255/// maximum
256inline CouNumber mymin (register CouNumber a, register CouNumber b) 
257{return ((a<b) ? a : b);} 
258
259/// minimum
260inline CouNumber mymax (register CouNumber a, register CouNumber b) 
261{return ((a>b) ? a : b);} 
262
263#endif
Note: See TracBrowser for help on using the repository browser.