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
Couenne::t_chg_bounds
status of lower/upper bound of a variable, to be checked/modified in bound tightening
Definition: CouenneTypes.hpp:66
Couenne::expression::Copy
virtual expression * Copy() const
return copy of this expression (only makes sense in exprCopy)
Definition: CouenneExpression.hpp:272
Couenne::expression::~expression
virtual ~expression()
Destructor.
Definition: CouenneExpression.hpp:66
Couenne::getOriginal
expression * getOriginal(expression *e)
get original expression (can't make it an expression method as I need a non-const,...
Definition: CouenneExpression.hpp:315
Couenne::expression::code
virtual enum expr_type code()
return integer for comparing expressions (used to recognize common expression)
Definition: CouenneExpression.hpp:193
Couenne::expr_type
expr_type
code returned by the method expression::code()
Definition: CouenneTypes.hpp:40
CouennePrecisions.hpp
Couenne::expression::replace
virtual void replace(exprVar *, exprVar *)
replace expression with another
Definition: CouenneExpression.hpp:238
Couenne::isInteger
bool isInteger(CouNumber x)
is this number integer?
Definition: CouenneExpression.hpp:309
Couenne::expression::print
virtual void print(std::ostream &s=std::cout, bool=false) const
print expression to iostream
Definition: CouenneExpression.hpp:118
Couenne::expression::ArgList
virtual void ArgList(expression **al)
set arglist (used in deleting nodes without deleting children)
Definition: CouenneExpression.hpp:85
COUENNE_INFINITY
#define COUENNE_INFINITY
Definition: CouennePrecisions.hpp:32
Couenne::NONCONVEX
@ NONCONVEX
Definition: CouenneTypes.hpp:56
Couenne::expression::selectBranch
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.
Definition: CouenneExpression.hpp:228
Couenne::expression::Argument
virtual expression * Argument() const
return argument (when applicable, i.e., with univariate functions)
Definition: CouenneExpression.hpp:88
Couenne::expression::AUX_LEQ
@ AUX_LEQ
Definition: CouenneExpression.hpp:55
Couenne::COU_EXPRESSION
@ COU_EXPRESSION
Definition: CouenneTypes.hpp:41
Couenne::expression::rank
virtual int rank()
used in rank-based branching variable choice: original variables have rank 1; auxiliary w=f(x) has ra...
Definition: CouenneExpression.hpp:209
Couenne::expression::AUX_EQ
@ AUX_EQ
Definition: CouenneExpression.hpp:55
Couenne::expression::gradientNorm
virtual CouNumber gradientNorm(const double *x)
return l-2 norm of gradient at given point
Definition: CouenneExpression.hpp:126
Couenne::expression::DepList
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.
Definition: CouenneExpression.hpp:143
Couenne::CouenneCutGenerator
Cut Generator for linear convexifications.
Definition: CouenneCutGenerator.hpp:49
Couenne::expression::dependsOn
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...
Couenne::expression::Type
virtual enum nodeType Type() const
node type
Definition: CouenneExpression.hpp:96
Couenne
general include file for different compilers
Definition: CouenneAggrProbing.hpp:24
Couenne::EMPTY
@ EMPTY
Definition: CouenneTypes.hpp:20
Couenne::expression::Image
virtual expression * Image() const
return pointer to corresponding expression (for auxiliary variables only)
Definition: CouenneExpression.hpp:100
Couenne::expression::isInteger
virtual bool isInteger()
is this expression integer?
Definition: CouenneExpression.hpp:160
Couenne::expression::realign
virtual void realign(const CouenneProblem *p)
empty function to redirect variables to proper variable vector
Definition: CouenneExpression.hpp:248
Couenne::STOP_AT_AUX
@ STOP_AT_AUX
Definition: CouenneTypes.hpp:62
Couenne::dig_type
dig_type
type of digging when filling the dependence list
Definition: CouenneTypes.hpp:62
Couenne::expression::AUX_UNDEF
@ AUX_UNDEF
Definition: CouenneExpression.hpp:55
Couenne::compareExpr
int compareExpr(const void *e0, const void *e1)
independent comparison
Definition: CouenneExpression.hpp:304
Couenne::CouenneObject
OsiObject for auxiliary variables $w=f(x)$.
Definition: CouenneObject.hpp:57
COUENNE_EPS
#define COUENNE_EPS
Definition: CouennePrecisions.hpp:19
Couenne::expression::simplify
virtual expression * simplify()
simplify expression (useful for derivatives)
Definition: CouenneExpression.hpp:148
Couenne::DepGraph
Dependence graph.
Definition: CouenneDepGraph.hpp:115
Couenne::expression::isaCopy
virtual bool isaCopy() const
return true if this is a copy of something (i.e. an exprCopy)
Definition: CouenneExpression.hpp:268
Couenne::convexity
convexity
convexity type of an expression
Definition: CouenneTypes.hpp:56
Couenne::expression::differentiate
virtual expression * differentiate(int)
differentiation
Couenne::expression::linkDomain
virtual void linkDomain(Domain *d)
empty function to update domain pointer
Definition: CouenneExpression.hpp:245
Couenne::CouNumber
double CouNumber
main number type in Couenne
Definition: CouenneTypes.hpp:100
Couenne::expression::fillDepSet
virtual void fillDepSet(std::set< DepNode *, compNode > *, DepGraph *)
update dependence set with index of variables on which this expression depends
Definition: CouenneExpression.hpp:242
Couenne::expression::Image
virtual void Image(expression *image)
set expression associated with this auxiliary variable (for compatibility with exprAux)
Definition: CouenneExpression.hpp:105
OsiCuts
Couenne::expression::ArgList
virtual expression ** ArgList() const
return arglist (when applicable, that is, with N-ary functions)
Definition: CouenneExpression.hpp:81
Couenne::expression::auxSign
auxSign
"sign" of the constraint defining an auxiliary.
Definition: CouenneExpression.hpp:55
Couenne::exprVar
variable-type operator
Definition: CouenneExprVar.hpp:45
OsiSolverInterface
Couenne::expression::compare
virtual int compare(expression &)
compare expressions
CouenneTypes.hpp
Couenne::expression::dependsOn
int dependsOn(int singleton, enum dig_type type=STOP_AT_AUX)
version with one index only
Definition: CouenneExpression.hpp:137
Couenne::expression::clone
virtual expression * clone(Domain *d=NULL) const
Cloning method.
Definition: CouenneExpression.hpp:69
COUENNE_EPS_INT
#define COUENNE_EPS_INT
Definition: CouennePrecisions.hpp:25
Couenne::expression::operator()
virtual CouNumber operator()()=0
null function for evaluating the expression
Couenne::expression::isBijective
virtual bool isBijective() const
indicating if function is monotonically increasing
Definition: CouenneExpression.hpp:251
OsiBranchingInformation
Couenne::exprCopy
Definition: CouenneExprCopy.hpp:25
Couenne::nodeType
nodeType
type of a node in an expression tree
Definition: CouenneTypes.hpp:20
Couenne::Simplified
expression * Simplified(expression *complicated)
Macro to return already simplified expression without having to do the if part every time simplify ()...
Definition: CouenneExpression.hpp:323
Couenne::expression::generateCuts
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
Definition: CouenneExpression.hpp:185
Couenne::expression::convexity
virtual enum convexity convexity() const
either CONVEX, CONCAVE, AFFINE, or NONCONVEX
Definition: CouenneExpression.hpp:197
Couenne::expression::Original
virtual const expression * Original() const
If this is an exprClone of a exprClone of an expr???, point to the original expr??...
Definition: CouenneExpression.hpp:114
Couenne::expression::getBounds
virtual void getBounds(expression *&, expression *&)
Get lower and upper bound of an expression (if any)
Couenne::expression::inverse
virtual CouNumber inverse(expression *vardep) const
compute the inverse function
Definition: CouenneExpression.hpp:255
Couenne::NONLINEAR
@ NONLINEAR
Definition: CouenneTypes.hpp:23
Couenne::expression::expression
expression(const expression &e, Domain *d=NULL)
Copy constructor.
Definition: CouenneExpression.hpp:63
Couenne::expression::expression
expression()
Constructor.
Definition: CouenneExpression.hpp:58
Couenne::expression::closestFeasible
virtual void closestFeasible(expression *varind, expression *vardep, CouNumber &left, CouNumber &right) const
closest feasible points in function in both directions
Couenne::updateBound
bool updateBound(register int sign, register CouNumber *dst, register CouNumber src)
updates maximum violation.
Definition: CouenneExpression.hpp:279
Couenne::expression::Linearity
virtual int Linearity()
get a measure of "how linear" the expression is (see CouenneTypes.h)
Definition: CouenneExpression.hpp:152
COUENNE_round
#define COUENNE_round(x)
Definition: CouennePrecisions.hpp:42
Couenne::ORIG_ONLY
@ ORIG_ONLY
Definition: CouenneTypes.hpp:62
Couenne::CouenneProblem
Class for MINLP problems with symbolic information.
Definition: CouenneProblem.hpp:169
Couenne::expression::isDefinedInteger
virtual bool isDefinedInteger()
is this expression defined as an integer?
Definition: CouenneExpression.hpp:156
Couenne::expression::ArgPtr
virtual expression ** ArgPtr()
return pointer to argument (when applicable, i.e., with univariate functions)
Definition: CouenneExpression.hpp:92
Couenne::expression::Multiplicity
virtual int Multiplicity()
multiplicity of a variable
Definition: CouenneExpression.hpp:222
Couenne::exprAux
Auxiliary variable.
Definition: CouenneExprAux.hpp:32
Couenne::expression::nArgs
virtual int nArgs() const
return number of arguments (when applicable, that is, with N-ary functions)
Definition: CouenneExpression.hpp:77
Couenne::expression
Expression base class.
Definition: CouenneExpression.hpp:48
Couenne::expression::Value
virtual CouNumber Value() const
value (empty)
Definition: CouenneExpression.hpp:108
Couenne::expression::Index
virtual int Index() const
Return index of variable (only valid for exprVar and exprAux)
Definition: CouenneExpression.hpp:73
Couenne::expression::isCuttable
virtual bool isCuttable(CouenneProblem *problem, int index) const
can this expression be further linearized or are we on its concave ("bad") side
Definition: CouenneExpression.hpp:264
Couenne::expression::impliedBound
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...
Definition: CouenneExpression.hpp:218
Couenne::Domain
Define a dynamic point+bounds, with a way to save and restore previous points+bounds through a LIFO s...
Definition: CouenneDomain.hpp:104
Couenne::expression::standardize
virtual exprAux * standardize(CouenneProblem *p, bool addAux=true)
Create standard form of this expression, by:
Definition: CouenneExpression.hpp:181
Couenne::expression::AUX_GEQ
@ AUX_GEQ
Definition: CouenneExpression.hpp:55