Couenne  0.5.8
CouenneExpression.hpp
Go to the documentation of this file.
1 /* $Id: CouenneExpression.hpp 1147 2015-05-04 14:01:51Z stefan $
2  *
3  * Name: expression.hpp
4  * Author: Pietro Belotti
5  * Purpose: definition of the class expression
6  *
7  * (C) Carnegie-Mellon University, 2006-10.
8  * This file is licensed under the Eclipse Public License (EPL)
9  */
10 
11 #ifndef COUENNE_EXPRESSION_HPP
12 #define COUENNE_EXPRESSION_HPP
13 
14 #include <iostream>
15 #include <set>
16 #include <vector>
17 
18 #include "CouennePrecisions.hpp"
19 #include "CouenneTypes.hpp"
20 
22 class OsiSolverInterface;
23 class OsiCuts;
24 
25 namespace Couenne {
26 
27 class CouenneProblem;
28 class CouenneCutGenerator;
29 class CouenneObject;
30 
31 class exprAux;
32 class exprCopy;
33 class exprVar;
34 
35 class DepNode;
36 class DepGraph;
37 
38 class Domain;
39 
40 struct compNode;
41 
47 
48 class expression {
49 
50  public:
51 
56 
58  expression () {}
59 
63  expression (const expression &e, Domain *d = NULL) {}
64 
66  virtual ~expression () {}
67 
69  virtual expression *clone (Domain *d = NULL) const
70  {return NULL;}
71 
73  virtual inline int Index () const
74  {return -1;}
75 
77  virtual inline int nArgs () const
78  {return 0;}
79 
81  virtual inline expression **ArgList () const
82  {return NULL;}
83 
85  virtual inline void ArgList (expression **al) {}
86 
88  virtual inline expression *Argument () const
89  {return NULL;}
90 
92  virtual inline expression **ArgPtr ()
93  {return NULL;}
94 
96  virtual inline enum nodeType Type () const
97  {return EMPTY;}
98 
100  virtual inline expression *Image () const
101  {return NULL;}
102 
105  virtual void Image (expression *image) {}
106 
108  virtual inline CouNumber Value () const
109  {return 0.;}
110 
114  virtual inline const expression *Original () const
115  {return this;}
116 
118  virtual void print (std::ostream &s = std::cout,
119  bool = false) const
120  {s << '?';}
121 
123  virtual CouNumber operator () () = 0;
124 
126  virtual inline CouNumber gradientNorm (const double *x)
127  {return 0.;}
128 
130  virtual expression *differentiate (int);
131 
134  virtual int dependsOn (int *ind, int n, enum dig_type type = STOP_AT_AUX);
135 
137  inline int dependsOn (int singleton, enum dig_type type = STOP_AT_AUX)
138  {return dependsOn (&singleton, 1, type);}
139 
143  virtual inline int DepList (std::set <int> &deplist,
144  enum dig_type type = ORIG_ONLY)
145  {return 0;}
146 
148  virtual inline expression *simplify ()
149  {return NULL;}
150 
152  virtual inline int Linearity ()
153  {return NONLINEAR;}
154 
156  virtual inline bool isDefinedInteger ()
157  {return isInteger ();}
158 
160  virtual inline bool isInteger ()
161  {return false;}
162 
164  virtual void getBounds (expression *&, expression *&);
165 
167  virtual void getBounds (CouNumber &, CouNumber &);
168 
181  virtual inline exprAux *standardize (CouenneProblem *p, bool addAux = true)
182  {return NULL;}
183 
185  virtual void generateCuts (expression *w, //const OsiSolverInterface &si,
186  OsiCuts &cs, const CouenneCutGenerator *cg,
187  t_chg_bounds *chg = NULL, int wind = -1,
189  CouNumber ub = COUENNE_INFINITY) {}
190 
193  virtual enum expr_type code ()
194  {return COU_EXPRESSION;}
195 
197  virtual enum convexity convexity () const
198  {return NONCONVEX;}
199 
201  virtual int compare (expression &);
202 
204  virtual int compare (exprCopy &);
205 
209  virtual int rank ()
210  {return -1;} // return null rank
211 
219  {return false;}
220 
222  virtual inline int Multiplicity ()
223  {return 1;}
224 
228  virtual CouNumber selectBranch (const CouenneObject *obj,
229  const OsiBranchingInformation *info,
230  expression * &var,
231  double * &brpts,
232  double * &brDist, // distance of current LP
233  // point to new convexifications
234  int &way)
235  {var = NULL; return 0.;}
236 
238  virtual void replace (exprVar *, exprVar *) {}
239 
242  virtual void fillDepSet (std::set <DepNode *, compNode> *, DepGraph *) {}
243 
245  virtual void linkDomain (Domain *d) {}
246 
248  virtual void realign (const CouenneProblem *p) {}
249 
251  virtual bool isBijective() const
252  {return false;}
253 
255  virtual CouNumber inverse (expression *vardep) const
256  {return -COUENNE_INFINITY;}
257 
259  virtual void closestFeasible (expression *varind, expression *vardep,
260  CouNumber& left, CouNumber& right) const;
261 
264  virtual bool isCuttable (CouenneProblem *problem, int index) const
265  {return true;}
266 
268  virtual bool isaCopy () const
269  {return false;}
270 
272  virtual expression *Copy () const
273  {return NULL;}
274 };
275 
276 
279 inline bool updateBound (register int sign,
280  register CouNumber *dst,
281  register CouNumber src) {
282 
283  // meaning:
284  //
285  // if (*dst > src) && (sign > 0) --> dst down to src
286  // if (*dst < src) && (sign < 0) --> dst up to src
287  //
288  // that is, sign > 0 means we are tightening an UPPER bound
289  // sign < 0 LOWER
290 
291  register double delta = (sign > 0) ? (*dst - src) : (src - *dst);
292 
293  if (delta > 0.) {
294  //printf ("%.12g --> %.12g\n", *dst, src);
295  *dst = src; // tighten
296  return (delta > COUENNE_EPS); // avoid returning true when improvement is negligible
297  }
298 
299  return false;
300 }
301 
302 
304 inline int compareExpr (const void *e0, const void *e1)
305 {return ((*(expression **) e0) -> compare (**(expression **)e1));}
306 
307 
309 inline bool isInteger (CouNumber x)
310 {return (fabs (COUENNE_round (x) - x) < COUENNE_EPS_INT);}
311 
312 
316 
317  if (e -> isaCopy ()) return getOriginal (e -> Copy ());
318  else return e;
319 }
320 
323 inline expression *Simplified (expression *complicated) {
324 
325  expression *simpler = complicated -> simplify ();
326 
327  if (simpler) {
328  delete complicated;
329  return simpler;
330  } else return complicated;
331 }
332 
333 }
334 
335 #endif
#define COUENNE_EPS
#define COUENNE_INFINITY
#define COUENNE_EPS_INT
#define COUENNE_round(x)
Cut Generator for linear convexifications.
OsiObject for auxiliary variables $w=f(x)$.
Class for MINLP problems with symbolic information.
Dependence graph.
Define a dynamic point+bounds, with a way to save and restore previous points+bounds through a LIFO s...
Auxiliary variable.
variable-type operator
Expression base class.
virtual void closestFeasible(expression *varind, expression *vardep, CouNumber &left, CouNumber &right) const
closest feasible points in function in both directions
virtual void fillDepSet(std::set< DepNode *, compNode > *, DepGraph *)
update dependence set with index of variables on which this expression depends
virtual void getBounds(expression *&, expression *&)
Get lower and upper bound of an expression (if any)
virtual enum expr_type code()
return integer for comparing expressions (used to recognize common expression)
virtual expression ** ArgPtr()
return pointer to argument (when applicable, i.e., with univariate functions)
virtual CouNumber inverse(expression *vardep) const
compute the inverse function
virtual int dependsOn(int *ind, int n, enum dig_type type=STOP_AT_AUX)
dependence on variable set: return cardinality of subset of the set of indices in first argument whic...
virtual bool isInteger()
is this expression integer?
virtual enum nodeType Type() const
node type
expression(const expression &e, Domain *d=NULL)
Copy constructor.
virtual expression * clone(Domain *d=NULL) const
Cloning method.
virtual int Index() const
Return index of variable (only valid for exprVar and exprAux)
virtual void realign(const CouenneProblem *p)
empty function to redirect variables to proper variable vector
virtual expression * Copy() const
return copy of this expression (only makes sense in exprCopy)
virtual CouNumber Value() const
value (empty)
virtual bool isCuttable(CouenneProblem *problem, int index) const
can this expression be further linearized or are we on its concave ("bad") side
virtual CouNumber operator()()=0
null function for evaluating the expression
virtual bool isaCopy() const
return true if this is a copy of something (i.e. an exprCopy)
virtual CouNumber gradientNorm(const double *x)
return l-2 norm of gradient at given point
virtual int compare(exprCopy &)
compare copies of expressions
virtual int compare(expression &)
compare expressions
virtual int Linearity()
get a measure of "how linear" the expression is (see CouenneTypes.h)
virtual void generateCuts(expression *w, OsiCuts &cs, const CouenneCutGenerator *cg, t_chg_bounds *chg=NULL, int wind=-1, CouNumber lb=-COUENNE_INFINITY, CouNumber ub=COUENNE_INFINITY)
generate convexification cut for constraint w = this
virtual void print(std::ostream &s=std::cout, bool=false) const
print expression to iostream
virtual void ArgList(expression **al)
set arglist (used in deleting nodes without deleting children)
virtual bool isBijective() const
indicating if function is monotonically increasing
virtual expression ** ArgList() const
return arglist (when applicable, that is, with N-ary functions)
virtual expression * Argument() const
return argument (when applicable, i.e., with univariate functions)
virtual void Image(expression *image)
set expression associated with this auxiliary variable (for compatibility with exprAux)
virtual expression * simplify()
simplify expression (useful for derivatives)
virtual expression * Image() const
return pointer to corresponding expression (for auxiliary variables only)
virtual enum convexity convexity() const
either CONVEX, CONCAVE, AFFINE, or NONCONVEX
virtual int nArgs() const
return number of arguments (when applicable, that is, with N-ary functions)
virtual int DepList(std::set< int > &deplist, enum dig_type type=ORIG_ONLY)
fill std::set with indices of variables on which this expression depends.
virtual exprAux * standardize(CouenneProblem *p, bool addAux=true)
Create standard form of this expression, by:
virtual void replace(exprVar *, exprVar *)
replace expression with another
virtual void getBounds(CouNumber &, CouNumber &)
Get lower and upper bound of an expression (if any) – real values.
virtual int rank()
used in rank-based branching variable choice: original variables have rank 1; auxiliary w=f(x) has ra...
auxSign
"sign" of the constraint defining an auxiliary.
virtual bool isDefinedInteger()
is this expression defined as an integer?
int dependsOn(int singleton, enum dig_type type=STOP_AT_AUX)
version with one index only
virtual void linkDomain(Domain *d)
empty function to update domain pointer
virtual bool impliedBound(int, CouNumber *, CouNumber *, t_chg_bounds *, enum auxSign=expression::AUX_EQ)
does a backward implied bound processing on every expression, including exprSums although already don...
virtual ~expression()
Destructor.
virtual int Multiplicity()
multiplicity of a variable
virtual const expression * Original() const
If this is an exprClone of a exprClone of an expr???, point to the original expr??...
virtual expression * differentiate(int)
differentiation
virtual CouNumber selectBranch(const CouenneObject *obj, const OsiBranchingInformation *info, expression *&var, double *&brpts, double *&brDist, int &way)
set up branching object by evaluating many branching points for each expression's arguments.
status of lower/upper bound of a variable, to be checked/modified in bound tightening
general include file for different compilers
int compareExpr(const void *e0, const void *e1)
independent comparison
nodeType
type of a node in an expression tree
dig_type
type of digging when filling the dependence list
double CouNumber
main number type in Couenne
bool updateBound(register int sign, register CouNumber *dst, register CouNumber src)
updates maximum violation.
expression * Simplified(expression *complicated)
Macro to return already simplified expression without having to do the if part every time simplify ()...
expr_type
code returned by the method expression::code()
@ COU_EXPRESSION
bool isInteger(CouNumber x)
is this number integer?
expression * getOriginal(expression *e)
get original expression (can't make it an expression method as I need a non-const,...