source: branches/Couenne/Couenne/src/expression/expression.h @ 534

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

moved include files to make them doxygenable. Introduced three-way branching, with fixed intervals for now. Added check for small bound interval within all generateCuts()

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