Scippy

SCIP

Solving Constraint Integer Programs

scip_expr.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file scip_expr.h
17  * @ingroup PUBLICCOREAPI
18  * @brief public functions to work with algebraic expressions
19  * @author Ksenia Bestuzheva
20  * @author Benjamin Mueller
21  * @author Felipe Serrano
22  * @author Stefan Vigerske
23  */
24 
25 #ifndef SCIP_SCIP_EXPR_H_
26 #define SCIP_SCIP_EXPR_H_
27 
28 #include "scip/type_scip.h"
29 #include "scip/type_expr.h"
30 #include "scip/type_misc.h"
31 
32 #ifdef NDEBUG
33 #include "scip/struct_scip.h"
34 #include "scip/struct_set.h"
35 #include "scip/struct_mem.h"
36 #include "scip/struct_stat.h"
37 #include "scip/set.h"
38 #include "scip/expr.h"
39 #endif
40 
41 #ifdef __cplusplus
42 extern "C" {
43 #endif
44 
45 /**@addtogroup PublicExprHandlerMethods
46  * @{
47  */
48 
49 /** creates the handler for an expression handler and includes it into SCIP */
50 SCIP_EXPORT
52  SCIP* scip, /**< SCIP data structure */
53  SCIP_EXPRHDLR** exprhdlr, /**< buffer where to store created expression handler */
54  const char* name, /**< name of expression handler (must not be NULL) */
55  const char* desc, /**< description of expression handler (can be NULL) */
56  unsigned int precedence, /**< precedence of expression operation (used for printing) */
57  SCIP_DECL_EXPREVAL((*eval)), /**< point evaluation callback (must not be NULL) */
58  SCIP_EXPRHDLRDATA* data /**< data of expression handler (can be NULL) */
59  );
60 
61 /** gives expression handlers */
62 SCIP_EXPORT
64  SCIP* scip /**< SCIP data structure */
65 );
66 
67 /** gives number of expression handlers */
68 SCIP_EXPORT
70  SCIP* scip /**< SCIP data structure */
71 );
72 
73 /** returns an expression handler of a given name (or NULL if not found) */
74 SCIP_EXPORT
76  SCIP* scip, /**< SCIP data structure */
77  const char* name /**< name of expression handler */
78  );
79 
80 /** returns expression handler for variable expressions (or NULL if not included) */
81 SCIP_EXPORT
83  SCIP* scip /**< SCIP data structure */
84  );
85 
86 /** returns expression handler for constant value expressions (or NULL if not included) */
87 SCIP_EXPORT
89  SCIP* scip /**< SCIP data structure */
90  );
91 
92 /** returns expression handler for sum expressions (or NULL if not included) */
93 SCIP_EXPORT
95  SCIP* scip /**< SCIP data structure */
96  );
97 
98 /** returns expression handler for product expressions (or NULL if not included) */
99 SCIP_EXPORT
101  SCIP* scip /**< SCIP data structure */
102  );
103 
104 /** returns expression handler for power expressions (or NULL if not included) */
105 SCIP_EXPORT
107  SCIP* scip /**< SCIP data structure */
108  );
109 
110 #ifdef NDEBUG
111 /* If NDEBUG is defined, the function calls are overwritten by defines to reduce the number of function calls and
112  * speed up the algorithms.
113  */
114 #define SCIPgetExprhdlrs(scip) (scip)->set->exprhdlrs
115 #define SCIPgetNExprhdlrs(scip) (scip)->set->nexprhdlrs
116 #define SCIPfindExprhdlr(scip, name) SCIPsetFindExprhdlr((scip)->set, name)
117 #define SCIPgetExprhdlrVar(scip) (scip)->set->exprhdlrvar
118 #define SCIPgetExprhdlrValue(scip) (scip)->set->exprhdlrval
119 #define SCIPgetExprhdlrSum(scip) (scip)->set->exprhdlrsum
120 #define SCIPgetExprhdlrProduct(scip) (scip)->set->exprhdlrproduct
121 #define SCIPgetExprhdlrPower(scip) (scip)->set->exprhdlrpow
122 #endif
123 
124 /** @} */
125 
126 /**@addtogroup PublicExprMethods
127  * @{
128  */
129 
130 /**@name Expressions */
131 /**@{ */
132 
133 /** creates and captures an expression with given expression data and children */
134 SCIP_EXPORT
136  SCIP* scip, /**< SCIP data structure */
137  SCIP_EXPR** expr, /**< pointer where to store expression */
138  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
139  SCIP_EXPRDATA* exprdata, /**< expression data (expression assumes ownership) */
140  int nchildren, /**< number of children */
141  SCIP_EXPR** children, /**< children (can be NULL if nchildren is 0) */
142  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
143  void* ownercreatedata /**< data to pass to ownercreate */
144  );
145 
146 /** creates and captures an expression with given expression data and up to two children */
147 SCIP_EXPORT
149  SCIP* scip, /**< SCIP data structure */
150  SCIP_EXPR** expr, /**< pointer where to store expression */
151  SCIP_EXPRHDLR* exprhdlr, /**< expression handler */
152  SCIP_EXPRDATA* exprdata, /**< expression data */
153  SCIP_EXPR* child1, /**< first child (can be NULL) */
154  SCIP_EXPR* child2, /**< second child (can be NULL) */
155  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
156  void* ownercreatedata /**< data to pass to ownercreate */
157  );
158 
159 /** creates and captures an expression representing a quadratic function */
160 SCIP_EXPORT
162  SCIP* scip, /**< SCIP data structure */
163  SCIP_EXPR** expr, /**< pointer where to store expression */
164  int nlinvars, /**< number of linear terms */
165  SCIP_VAR** linvars, /**< array with variables in linear part */
166  SCIP_Real* lincoefs, /**< array with coefficients of variables in linear part */
167  int nquadterms, /**< number of quadratic terms */
168  SCIP_VAR** quadvars1, /**< array with first variables in quadratic terms */
169  SCIP_VAR** quadvars2, /**< array with second variables in quadratic terms */
170  SCIP_Real* quadcoefs, /**< array with coefficients of quadratic terms */
171  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
172  void* ownercreatedata /**< data to pass to ownercreate */
173  );
174 
175 /** creates and captures an expression representing a monomial
176  *
177  * @note In deviation from the actual definition of monomials, we also allow for negative and rational exponents.
178  * So this function actually creates an expression for a signomial that has exactly one term.
179  */
180 SCIP_EXPORT
182  SCIP* scip, /**< SCIP data structure */
183  SCIP_EXPR** expr, /**< pointer where to store expression */
184  int nfactors, /**< number of factors in monomial */
185  SCIP_VAR** vars, /**< variables in the monomial */
186  SCIP_Real* exponents, /**< exponent in each factor, or NULL if all 1.0 */
187  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
188  void* ownercreatedata /**< data to pass to ownercreate */
189  );
190 
191 /** appends child to the children list of expr
192  *
193  * @attention Only use if you really know what you are doing. The expression handler of the expression needs to be able to handle an increase in the number of children.
194  */
195 SCIP_EXPORT
197  SCIP* scip, /**< SCIP data structure */
198  SCIP_EXPR* expr, /**< expression */
199  SCIP_EXPR* child /**< expression to be appended */
200  );
201 
202 /** overwrites/replaces a child of an expressions
203  *
204  * The old child is released and the newchild is captured, unless they are the same (=same pointer).
205  */
206 SCIP_EXPORT
208  SCIP* scip, /**< SCIP data structure */
209  SCIP_EXPR* expr, /**< expression which is going to replace a child */
210  int childidx, /**< index of child being replaced */
211  SCIP_EXPR* newchild /**< the new child */
212  );
213 
214 /** remove all children of expr
215  *
216  * @attention Only use if you really know what you are doing. The expression handler of the expression needs to be able to handle the removal of all children.
217  */
218 SCIP_EXPORT
220  SCIP* scip, /**< SCIP data structure */
221  SCIP_EXPR* expr /**< expression */
222  );
223 
224 /** duplicates the given expression and its children */
225 SCIP_EXPORT
227  SCIP* scip, /**< SCIP data structure */
228  SCIP_EXPR* expr, /**< original expression */
229  SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */
230  SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), /**< expression mapping function, or NULL for creating new expressions */
231  void* mapexprdata, /**< data of expression mapping function */
232  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
233  void* ownercreatedata /**< data to pass to ownercreate */
234  );
235 
236 /** duplicates the given expression, but reuses its children */
237 SCIP_EXPORT
239  SCIP* scip, /**< SCIP data structure */
240  SCIP_EXPR* expr, /**< original expression */
241  SCIP_EXPR** copyexpr, /**< buffer to store (shallow) duplicate of expr */
242  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
243  void* ownercreatedata /**< data to pass to ownercreate */
244  );
245 
246 /** copies an expression including children to use in a (possibly different) SCIP instance */
247 SCIP_EXPORT
249  SCIP* sourcescip, /**< source SCIP data structure */
250  SCIP* targetscip, /**< target SCIP data structure */
251  SCIP_EXPR* expr, /**< original expression */
252  SCIP_EXPR** copyexpr, /**< buffer to store duplicate of expr */
253  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call on expression copy to create ownerdata */
254  void* ownercreatedata, /**< data to pass to ownercreate */
255  SCIP_HASHMAP* varmap, /**< a SCIP_HASHMAP mapping variables of the source SCIP to the corresponding
256  * variables of the target SCIP, or NULL */
257  SCIP_HASHMAP* consmap, /**< a hashmap to store the mapping of source constraints to the corresponding
258  * target constraints, or NULL */
259  SCIP_Bool global, /**< create a global or a local copy? */
260  SCIP_Bool* valid /**< pointer to store whether all checked or enforced constraints were validly copied */
261  );
262 
263 /** creates an expression from a string
264  *
265  * We specify the grammar that defines the syntax of an expression.
266  * Loosely speaking, a `Base` will be any "block", a `Factor` is a `Base` to a power,
267  * a `Term` is a product of `Factors` and an `Expression` is a sum of `Terms`.
268  *
269  * The actual definition:
270  * <pre>
271  * Expression -> ["+" | "-"] Term { ("+" | "-" | "number *") ] Term }
272  * Term -> Factor { ("*" | "/" ) Factor }
273  * Factor -> Base [ "^" "number" | "^(" "number" ")" ]
274  * Base -> "number" | "<varname>" | "(" Expression ")" | Op "(" OpExpression ")
275  * </pre>
276  * where `[a|b]` means `a` or `b` or none, `(a|b)` means `a` or `b`, `{a}` means 0 or more `a`.
277  *
278  * Note that `Op` and `OpExpression` are undefined.
279  * `Op` corresponds to the name of an expression handler and `OpExpression` to whatever string the expression handler accepts (through its parse method).
280  */
281 SCIP_EXPORT
283  SCIP* scip, /**< SCIP data structure */
284  SCIP_EXPR** expr, /**< pointer to store the expr parsed */
285  const char* exprstr, /**< string with the expr to parse */
286  const char** finalpos, /**< buffer to store the position of exprstr where we finished reading, or NULL if not of interest */
287  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
288  void* ownercreatedata /**< data to pass to ownercreate */
289  );
290 
291 /** captures an expression (increments usage count) */
292 SCIP_EXPORT
293 void SCIPcaptureExpr(
294  SCIP_EXPR* expr /**< expression to be captured */
295  );
296 
297 /** releases an expression (decrements usage count and possibly frees expression) */
298 SCIP_EXPORT
300  SCIP* scip, /**< SCIP data structure */
301  SCIP_EXPR** expr /**< pointer to expression to be released */
302  );
303 
304 /** returns whether an expression is a variable expression */
305 SCIP_EXPORT
307  SCIP* scip, /**< SCIP data structure */
308  SCIP_EXPR* expr /**< expression */
309  );
310 
311 /** returns whether an expression is a value expression */
312 SCIP_EXPORT
314  SCIP* scip, /**< SCIP data structure */
315  SCIP_EXPR* expr /**< expression */
316  );
317 
318 /** returns whether an expression is a sum expression */
319 SCIP_EXPORT
321  SCIP* scip, /**< SCIP data structure */
322  SCIP_EXPR* expr /**< expression */
323  );
324 
325 /** returns whether an expression is a product expression */
326 SCIP_EXPORT
328  SCIP* scip, /**< SCIP data structure */
329  SCIP_EXPR* expr /**< expression */
330  );
331 
332 /** returns whether an expression is a power expression */
333 SCIP_EXPORT
335  SCIP* scip, /**< SCIP data structure */
336  SCIP_EXPR* expr /**< expression */
337  );
338 
339 /** print an expression as info-message */
340 SCIP_EXPORT
342  SCIP* scip, /**< SCIP data structure */
343  SCIP_EXPR* expr, /**< expression to be printed */
344  FILE* file /**< file to print to, or NULL for stdout */
345  );
346 
347 /** initializes printing of expressions in dot format to a give FILE* pointer */
348 SCIP_EXPORT
350  SCIP* scip, /**< SCIP data structure */
351  SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */
352  FILE* file, /**< file to print to, or NULL for stdout */
353  SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */
354  );
355 
356 /** initializes printing of expressions in dot format to a file with given filename */
357 SCIP_EXPORT
359  SCIP* scip, /**< SCIP data structure */
360  SCIP_EXPRPRINTDATA** printdata, /**< buffer to store dot printing data */
361  const char* filename, /**< name of file to print to */
362  SCIP_EXPRPRINT_WHAT whattoprint /**< info on what to print for each expression */
363  );
364 
365 /** main part of printing an expression in dot format */
366 SCIP_EXPORT
368  SCIP* scip, /**< SCIP data structure */
369  SCIP_EXPRPRINTDATA* printdata, /**< data as initialized by \ref SCIPprintExprDotInit() */
370  SCIP_EXPR* expr /**< expression to be printed */
371  );
372 
373 /** finishes printing of expressions in dot format */
374 SCIP_EXPORT
376  SCIP* scip, /**< SCIP data structure */
377  SCIP_EXPRPRINTDATA** printdata /**< buffer where dot printing data has been stored */
378  );
379 
380 /** shows a single expression by use of dot and gv
381  *
382  * This function is meant for debugging purposes.
383  * It's signature is kept as simple as possible to make it
384  * easily callable from gdb, for example.
385  *
386  * It prints the expression into a temporary file in dot format, then calls dot to create a postscript file, then calls ghostview (gv) to show the file.
387  * SCIP will hold until ghostscript is closed.
388  */
389 SCIP_EXPORT
391  SCIP* scip, /**< SCIP data structure */
392  SCIP_EXPR* expr /**< expression to be printed */
393  );
394 
395 /** prints structure of an expression a la Maple's dismantle */
396 SCIP_EXPORT
398  SCIP* scip, /**< SCIP data structure */
399  FILE* file, /**< file to print to, or NULL for stdout */
400  SCIP_EXPR* expr /**< expression to dismantle */
401  );
402 
403 /** evaluate an expression in a point
404  *
405  * Iterates over expressions to also evaluate children, if necessary.
406  * Value can be received via SCIPexprGetEvalValue().
407  * If an evaluation error (division by zero, ...) occurs, this value will
408  * be set to SCIP_INVALID.
409  *
410  * If a nonzero \p soltag is passed, then only (sub)expressions are
411  * reevaluated that have a different solution tag. If a soltag of 0
412  * is passed, then subexpressions are always reevaluated.
413  * The tag is stored together with the value and can be received via
414  * SCIPexprGetEvalTag().
415  */
416 SCIP_EXPORT
418  SCIP* scip, /**< SCIP data structure */
419  SCIP_EXPR* expr, /**< expression to be evaluated */
420  SCIP_SOL* sol, /**< solution to be evaluated */
421  SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */
422  );
423 
424 /** returns a previously unused solution tag for expression evaluation */
425 SCIP_EXPORT
427  SCIP* scip /**< SCIP data structure */
428  );
429 
430 /**@} */
431 
432 /** @name Differentiation
433  * @anchor SCIP_EXPR_DIFF
434  *
435  * @par Gradients (Automatic differentiation Backward mode)
436  *
437  * Given a function, say, \f$f(s(x,y),t(x,y))\f$ there is a common mnemonic technique to compute its partial derivatives, using a tree diagram.
438  * Suppose we want to compute the partial derivative of \f$f\f$ w.r.t. \f$x\f$.
439  * Write the function as a tree:
440  *
441  * f
442  * |-----|
443  * s t
444  * |--| |--|
445  * x y x y
446  *
447  * The weight of an edge between two nodes represents the partial derivative of the parent w.r.t. the children, e.g.,
448  *
449  * f
450  * |
451  * s
452  *
453  * is \f$ \partial_sf \f$.
454  * The weight of a path is the product of the weight of the edges in the path.
455  * The partial derivative of \f$f\f$ w.r.t. \f$x\f$ is then the sum of the weights of all paths connecting \f$f\f$ with \f$x\f$:
456  * \f[ \frac{\partial f}{\partial x} = \partial_s f \cdot \partial_x s + \partial_t f \cdot \partial_x t. \f]
457  *
458  * We follow this method in order to compute the gradient of an expression (root) at a given point (point).
459  * Note that an expression is a DAG representation of a function, but there is a 1-1 correspondence between paths
460  * in the DAG and path in a tree diagram of a function.
461  * Initially, we set `root->derivative` to 1.0.
462  * Then, traversing the tree in Depth First (see \ref SCIPexpriterInit), for every expr that *has* children,
463  * we store in its i-th child, `child[i]->derivative`, the derivative of expr w.r.t. child evaluated at point multiplied with `expr->derivative`.
464  *
465  * For example:
466  * 1. `f->derivative` = 1.0
467  * 2. `s->derivative` = \f$\partial_s f \,\cdot\f$ `f->derivative` = \f$\partial_s f\f$
468  * 3. `x->derivative` = \f$\partial_x s \,\cdot\f$ `s->derivative` = \f$\partial_x s \cdot \partial_s f\f$
469  *
470  * However, when the child is a variable expressions, we actually need to initialize `child->derivative` to 0.0
471  * and afterwards add, instead of overwrite the computed value.
472  * The complete example would then be:
473  *
474  * 1. `f->derivative` = 1.0, `x->derivative` = 0.0, `y->derivative` = 0.0
475  * 2. `s->derivative` = \f$\partial_s f \,\cdot\f$ `f->derivative` = \f$\partial_s f\f$
476  * 3. `x->derivative` += \f$\partial_x s \,\cdot\f$ `s->derivative` = \f$\partial_x s \cdot \partial_s f\f$
477  * 4. `y->derivative` += \f$\partial_y s \,\cdot\f$ `s->derivative` = \f$\partial_y s \cdot \partial_s f\f$
478  * 5. `t->derivative` = \f$\partial_t f \,\cdot\f$ `f->derivative` = \f$\partial_t f\f$
479  * 6. `x->derivative` += \f$\partial_x t \,\cdot\f$ `t->derivative` = \f$\partial_x t \cdot \partial_t f\f$
480  * 7. `y->derivative` += \f$\partial_y t \,\cdot\f$ `t->derivative` = \f$\partial_y t \cdot \partial_t f\f$
481  *
482  * Note that, to compute this, we only need to know, for each expression, its partial derivatives w.r.t a given child at a point.
483  * This is what the callback `SCIP_DECL_EXPRBWDIFF` should return.
484  * Indeed, from "derivative of expr w.r.t. child evaluated at point multiplied with expr->derivative",
485  * note that at the moment of processing a child, we already know `expr->derivative`, so the only
486  * missing piece of information is "the derivative of expr w.r.t. child evaluated at point".
487  *
488  * An equivalent way of interpreting the procedure is that `expr->derivative` stores the derivative of the root w.r.t. expr.
489  * This way, `x->derivative` and `y->derivative` will contain the partial derivatives of root w.r.t. the variable, that is, the gradient.
490  * Note, however, that this analogy is only correct for leave expressions, since the derivative value of an intermediate expression gets overwritten.
491  *
492  *
493  * \par Hessian (Automatic differentiation Backward on Forward mode)
494  *
495  * Computing the Hessian is more complicated since it is the derivative of the gradient, which is a function with more than one output.
496  * We compute the Hessian by computing "directions" of the Hessian, that is \f$H\cdot u\f$ for different \f$u\f$.
497  * This is easy in general, since it is the gradient of the *scalar* function \f$\nabla f u\f$, that is,
498  * the directional derivative of \f$f\f$ in the direction \f$u\f$: \f$D_u f\f$.
499  *
500  * This is easily computed via the so called forward mode.
501  * Just as `expr->derivative` stores the partial derivative of the root w.r.t. expr,
502  * `expr->dot` stores the directional derivative of expr in the direction \f$u\f$.
503  * Then, by the chain rule, `expr->dot` = \f$\sum_{c:\text{children}} \partial_c \text{expr} \,\cdot\f$ `c->dot`.
504  *
505  * Starting with `x[i]->dot` = \f$u_i\f$, we can compute `expr->dot` for every expression at the same time we evaluate expr.
506  * Computing `expr->dot` is the purpose of the callback `SCIP_DECL_EXPRFWDIFF`.
507  * Obviously, when this callback is called, the "dots" of all children are known
508  * (just like evaluation, where the value of all children are known).
509  *
510  * Once we have this information, we compute the gradient of this function, following the same idea as before.
511  * We define `expr->bardot` to be the directional derivative in direction \f$u\f$ of the partial derivative of the root w.r.t `expr`,
512  * that is \f$D_u (\partial_{\text{expr}} f) = D_u\f$ (`expr->derivative`).
513  *
514  * This way, `x[i]->bardot` = \f$D_u (\partial_{x_i} f) = e_i^T H_f u\f$.
515  * Hence `vars->bardot` contain \f$H_f u\f$.
516  * By the chain rule, product rule, and definition we have
517  * \f{eqnarray*}{
518  * \texttt{expr->bardot} & = & D_u (\partial_{\text{expr}} f) \\
519  * & = & D_u ( \partial_{\text{parent}} f \cdot \partial_{\text{expr}} \text{parent} ) \\
520  * & = & D_u ( \texttt{parent->derivative} \cdot \partial_{\text{expr}} \text{parent} ) \\
521  * & = & \partial_{\text{expr}} \text{parent} \cdot D_u (\texttt{parent->derivative}) + \texttt{parent->derivative} \cdot D_u (\partial_{\text{expr}} \text{parent}) \\
522  * & = & \texttt{parent->bardot} \cdot \partial_{\text{expr}} \text{parent} + \texttt{parent->derivative} \cdot D_u (\partial_{\text{expr}} \text{parent})
523  * \f}
524  *
525  * Note that we have computed `parent->bardot` and `parent->derivative` at this point,
526  * while \f$\partial_{\text{expr}} \text{parent}\f$ is the return of `SCIP_DECL_EXPRBWDIFF`.
527  * Hence the only information we need to compute is \f$D_u (\partial_{\text{expr}} \text{parent})\f$.
528  * This is the purpose of the callback `SCIP_DECL_EXPRBWFWDIFF`.
529  *
530  * @{
531  */
532 
533 /** evaluates gradient of an expression for a given point
534  *
535  * Initiates an expression walk to also evaluate children, if necessary.
536  * Value can be received via SCIPgetExprPartialDiffNonlinear().
537  * If an error (division by zero, ...) occurs, this value will
538  * be set to SCIP_INVALID.
539  */
540 SCIP_EXPORT
542  SCIP* scip, /**< SCIP data structure */
543  SCIP_EXPR* expr, /**< expression to be differentiated */
544  SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */
545  SCIP_Longint soltag /**< tag that uniquely identifies the solution (with its values), or 0. */
546  );
547 
548 /** evaluates Hessian-vector product of an expression for a given point and direction
549  *
550  * Evaluates children, if necessary.
551  * Value can be received via SCIPgetExprPartialDiffGradientDirNonlinear().
552  * If an error (division by zero, ...) occurs, this value will
553  * be set to SCIP_INVALID.
554  */
555 SCIP_EXPORT
557  SCIP* scip, /**< SCIP data structure */
558  SCIP_EXPR* expr, /**< expression to be differentiated */
559  SCIP_SOL* sol, /**< solution to be evaluated (NULL for the current LP solution) */
560  SCIP_Longint soltag, /**< tag that uniquely identifies the solution (with its values), or 0. */
561  SCIP_SOL* direction /**< direction */
562  );
563 
564 /**@} */ /* end of differentiation methods */
565 
566 /**@name Expressions
567  * @{
568  */
569 
570 /** possibly reevaluates and then returns the activity of the expression
571  *
572  * Reevaluate activity if currently stored is no longer uptodate (some bound was changed since last evaluation).
573  *
574  * The owner of the expression may overwrite the methods used to evaluate the activity,
575  * including whether the local or global domain of variables is used.
576  * By default (no owner, or owner doesn't overwrite activity evaluation),
577  * the local domain of variables is used.
578  *
579  * @note If expression is set to be integral, then activities are tightened to integral values.
580  * Thus, ensure that the integrality information is valid (if set to TRUE; the default (FALSE) is always ok).
581  */
582 SCIP_EXPORT
584  SCIP* scip, /**< SCIP data structure */
585  SCIP_EXPR* expr /**< expression */
586  );
587 
588 /** compare expressions
589  * @return -1, 0 or 1 if expr1 <, =, > expr2, respectively
590  * @note The given expressions are assumed to be simplified.
591  */
592 SCIP_EXPORT
593 int SCIPcompareExpr(
594  SCIP* scip, /**< SCIP data structure */
595  SCIP_EXPR* expr1, /**< first expression */
596  SCIP_EXPR* expr2 /**< second expression */
597  );
598 
599 /** compute the hash value of an expression */
600 SCIP_EXPORT
602  SCIP* scip, /**< SCIP data structure */
603  SCIP_EXPR* expr, /**< expression */
604  unsigned int* hashval /**< pointer to store the hash value */
605  );
606 
607 /** simplifies an expression
608  *
609  * This is largely inspired by Joel Cohen's
610  * *Computer algebra and symbolic computation: Mathematical methods*,
611  * in particular Chapter 3.
612  * The other fountain of inspiration are the simplifying methods of expr.c in SCIP 7.
613  *
614  * Note: The things to keep in mind when adding simplification rules are the following.
615  * I will be using the product expressions (see expr_product.c) as an example.
616  * There are mainly 3 parts of the simplification process. You need to decide
617  * at which stage the simplification rule makes sense.
618  * 1. Simplify each factor (simplifyFactor()): At this stage we got the children of the product expression.
619  * At this point, each child is simplified when viewed as a stand-alone expression, but not necessarily when viewed as child of a product expression.
620  * Rules like SP2, SP7, etc are enforced at this point.
621  * 2. Multiply the factors (mergeProductExprlist()): At this point rules like SP4, SP5 and SP14 are enforced.
622  * 3. Build the actual simplified product expression (buildSimplifiedProduct()):
623  * At this point rules like SP10, SP11, etc are enforced.
624  *
625  * During steps 1 and 2 do not forget to set the flag `changed` to TRUE when something actually changes.
626  *
627  * \par Definition of simplified expressions
628  *
629  * An expression is simplified if it
630  * - is a value expression
631  * - is a var expression
632  * - is a product expression such that
633  * - SP1: every child is simplified
634  * - SP2: no child is a product
635  * - SP4: no two children are the same expression (those should be multiplied)
636  * - SP5: the children are sorted [commutative rule]
637  * - SP7: no child is a value
638  * - SP8: its coefficient is 1.0 (otherwise should be written as sum)
639  * - SP10: it has at least two children
640  * - TODO?: at most one child is an `abs`
641  * - SP11: no two children are `expr*log(expr)`
642  * (TODO: we could handle more complicated stuff like \f$xy\log(x) \to - y * \mathrm{entropy}(x)\f$, but I am not sure this should happen at the simplification level;
643  * similar for \f$(xy) \log(xy)\f$, which currently simplifies to \f$xy \log(xy)\f$)
644  * - SP12: if it has two children, then neither of them is a sum (expand sums)
645  * - SP13: no child is a sum with a single term
646  * - SP14: at most one child is an `exp`
647  * - is a power expression such that
648  * - POW1: exponent is not 0
649  * - POW2: exponent is not 1
650  * - POW3: its child is not a value
651  * - POW4: its child is simplified
652  * - POW5: if exponent is integer, its child is not a product
653  * - POW6: if exponent is integer, its child is not a sum with a single term (\f$(2x)^2 \to 4x^2\f$)
654  * - POW7: if exponent is 2, its child is not a sum (expand sums)
655  * - POW8: its child is not a power unless \f$(x^n)^m\f$ with \f$nm\f$ being integer and \f$n\f$ or \f$m\f$ fractional and \f$n\f$ not being even integer
656  * - POW9: its child is not a sum with a single term with a positive coefficient: \f$(25x)^{0.5} \to 5 x^{0.5}\f$
657  * - POW10: its child is not a binary variable: \f$b^e, e > 0 \to b\f$; \f$b^e, e < 0 \to b := 1\f$
658  * - POW11: its child is not an exponential: \f$\exp(\text{expr})^e \to \exp(e\cdot\text{expr})\f$
659  * - is a signedpower expression such that
660  * - SPOW1: exponent is not 0
661  * - SPOW2: exponent is not 1
662  * - SPOW3: its child is not a value
663  * - SPOW4: its child is simplified
664  * - SPOW5: (TODO) do we want to distribute signpowers over products like we do for powers?
665  * - SPOW6: exponent is not an odd integer: (signpow odd expr) -> (pow odd expr)
666  * - SPOW8: if exponent is integer, its child is not a power
667  * - SPOW9: its child is not a sum with a single term: \f$\mathrm{signpow}(25x,0.5) \to 5\mathrm{signpow}(x,0.5)\f$
668  * - SPOW10: its child is not a binary variable: \f$\mathrm{signpow}(b,e), e > 0 \to b\f$; \f$\mathrm{signpow}(b,e), e < 0 \to b := 1\f$
669  * - SPOW11: its child is not an exponential: \f$\mathrm{signpow}(\exp(\text{expr}),e) \to \exp(e\cdot\text{expr})\f$
670  * - TODO: what happens when child is another signed power?
671  * - TODO: if child &ge; 0 -> transform to normal power; if child < 0 -> transform to - normal power
672  *
673  * TODO: Some of these criteria are too restrictive for signed powers; for example, the exponent does not need to be
674  * an integer for signedpower to distribute over a product (SPOW5, SPOW6, SPOW8). Others can also be improved.
675  * - is a sum expression such that
676  * - SS1: every child is simplified
677  * - SS2: no child is a sum
678  * - SS3: no child is a value (values should go in the constant of the sum)
679  * - SS4: no two children are the same expression (those should be summed up)
680  * - SS5: the children are sorted [commutative rule]
681  * - SS6: it has at least one child
682  * - SS7: if it consists of a single child, then either constant is != 0.0 or coef != 1
683  * - SS8: no child has coefficient 0
684  * - SS9: if a child c is a product that has an exponential expression as one of its factors, then the coefficient of c is +/-1.0
685  * - SS10: if a child c is an exponential, then the coefficient of c is +/-1.0
686  * - it is a function with simplified arguments, but not all of them can be values
687  * - TODO? a logarithm doesn't have a product as a child
688  * - TODO? the exponent of an exponential is always 1
689  *
690  * \par Ordering Rules (see SCIPexprCompare())
691  * \anchor EXPR_ORDER
692  * These rules define a total order on *simplified* expressions.
693  * There are two groups of rules, when comparing equal type expressions and different type expressions.
694  *
695  * Equal type expressions:
696  * - OR1: u,v value expressions: u < v &hArr; val(u) < val(v)
697  * - OR2: u,v var expressions: u < v &hArr; `SCIPvarGetIndex(var(u))` < `SCIPvarGetIndex(var(v))`
698  * - OR3: u,v are both sum or product expression: < is a lexicographical order on the terms
699  * - OR4: u,v are both pow: u < v &hArr; base(u) < base(v) or, base(u) = base(v) and expo(u) < expo(v)
700  * - OR5: u,v are \f$u = f(u_1, ..., u_n), v = f(v_1, ..., v_m)\f$: u < v &hArr; For the first k such that \f$u_k \neq v_k\f$, \f$u_k < v_k\f$, or if such a \f$k\f$ doesn't exist, then \f$n < m\f$.
701  *
702  * Different type expressions:
703  * - OR6: u value, v other: u < v always
704  * - OR7: u sum, v var or func: u < v &hArr; u < 0+v;
705  * In other words, if \f$u = \sum_{i=1}^n \alpha_i u_i\f$, then u < v &hArr; \f$u_n\f$ < v or if \f$u_n\f$ = v and \f$\alpha_n\f$ < 1.
706  * - OR8: u product, v pow, sum, var or func: u < v &hArr; u < 1*v;
707  * In other words, if \f$u = \prod_{i=1}^n u_i\f$, then u < v &hArr; \f$u_n\f$ < v.
708  * Note: since this applies only to simplified expressions, the form of the product is correct.
709  * Simplified products do *not* have constant coefficients.
710  * - OR9: u pow, v sum, var or func: u < v &hArr; u < v^1
711  * - OR10: u var, v func: u < v always
712  * - OR11: u func, v other type of func: u < v &hArr; name(type(u)) < name(type(v))
713  * - OR12: none of the rules apply: u < v &hArr; ! v < u
714  *
715  * Examples:
716  * - x < x^2 ?: x is var and x^2 power, so none applies (OR12).
717  * Hence, we try to answer x^2 < x ?: x^2 < x &hArr; x < x or if x = x and 2 < 1 &hArr; 2 < 1 &hArr; False. So x < x^2 is True.
718  * - x < x^-1 --OR12&rarr; ~(x^-1 < x) --OR9&rarr; ~(x^-1 < x^1) --OR4&rarr; ~(x < x or -1 < 1) &rarr; ~True &rarr; False
719  * - x*y < x --OR8&rarr; x*y < 1*x --OR3&rarr; y < x --OR2&rarr; False
720  * - x*y < y --OR8&rarr; x*y < 1*y --OR3&rarr; y < x --OR2&rarr; False
721  *
722  * \par Algorithm
723  *
724  * The recursive version of the algorithm is
725  *
726  * EXPR simplify(expr)
727  * for c in 1..expr->nchildren
728  * expr->children[c] = simplify(expr->children[c])
729  * end
730  * return expr->exprhdlr->simplify(expr)
731  * end
732  *
733  * Important: Whatever is returned by a simplify callback **has** to be simplified.
734  * Also, all children of the given expression **are** already simplified.
735  */
736 SCIP_EXPORT
738  SCIP* scip, /**< SCIP data structure */
739  SCIP_EXPR* rootexpr, /**< expression to be simplified */
740  SCIP_EXPR** simplified, /**< buffer to store simplified expression */
741  SCIP_Bool* changed, /**< buffer to store if rootexpr actually changed */
742  SCIP_Bool* infeasible, /**< buffer to store whether infeasibility has been detected */
743  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
744  void* ownercreatedata /**< data to pass to ownercreate */
745  );
746 
747 /** replaces common sub-expressions in a given expression graph by using a hash key for each expression
748  *
749  * The algorithm consists of two steps:
750  *
751  * 1. traverse through all given expressions and compute for each of them a (not necessarily unique) hash
752  *
753  * 2. initialize an empty hash table and traverse through all expression; check for each of them if we can find a
754  * structural equivalent expression in the hash table; if yes we replace the expression by the expression inside the
755  * hash table, otherwise we add it to the hash table
756  *
757  * @note the hash keys of the expressions are used for the hashing inside the hash table; to compute if two expressions
758  * (with the same hash) are structurally the same we use the function SCIPexprCompare().
759  */
760 SCIP_EXPORT
762  SCIP* scip, /**< SCIP data structure */
763  SCIP_EXPR** exprs, /**< expressions (possibly replaced by equivalent on output) */
764  int nexprs, /**< total number of expressions */
765  SCIP_Bool* replacedroot /**< buffer to store whether any root expression (expression in exprs) was replaced */
766 );
767 
768 /** computes the curvature of a given expression and all its subexpressions
769  *
770  * @note this function also evaluates all subexpressions w.r.t. current variable bounds
771  * @note this function relies on information from the curvature callback of expression handlers only,
772  * consider using function @ref SCIPhasExprCurvature() of the convex-nlhdlr instead, as that uses more information to deduce convexity
773  */
774 SCIP_EXPORT
776  SCIP* scip, /**< SCIP data structure */
777  SCIP_EXPR* expr /**< expression */
778  );
779 
780 /** computes integrality information of a given expression and all its subexpressions
781  *
782  * The integrality information can be accessed via SCIPexprIsIntegral().
783  */
784 SCIP_EXPORT
786  SCIP* scip, /**< SCIP data structure */
787  SCIP_EXPR* expr /**< expression */
788  );
789 
790 /** returns the total number of variable expressions in an expression
791  *
792  * The function counts variable expressions in common sub-expressions only once, but
793  * counts variables appearing in several variable expressions multiple times.
794  */
795 SCIP_EXPORT
797  SCIP* scip, /**< SCIP data structure */
798  SCIP_EXPR* expr, /**< expression */
799  int* nvars /**< buffer to store the total number of variables */
800  );
801 
802 /** returns all variable expressions contained in a given expression
803  *
804  * The array to store all variable expressions needs to be at least of size
805  * the number of unique variable expressions in the expression which is given by SCIPgetExprNVars().
806  *
807  * If every variable is represented by only one variable expression (common subexpression have been removed)
808  * then SCIPgetExprNVars() can be bounded by SCIPgetNTotalVars().
809  * If, in addition, non-active variables have been removed from the expression, e.g., by simplifying,
810  * then SCIPgetExprNVars() can be bounded by SCIPgetNVars().
811  *
812  * @note function captures variable expressions
813  */
814 SCIP_EXPORT
816  SCIP* scip, /**< SCIP data structure */
817  SCIP_EXPR* expr, /**< expression */
818  SCIP_EXPR** varexprs, /**< array to store all variable expressions */
819  int* nvarexprs /**< buffer to store the total number of variable expressions */
820  );
821 
822 /** @} */
823 
824 /**@name Expression Handler Callbacks
825  * @{
826  */
827 
828 /** calls the print callback for an expression
829  *
830  * @see SCIP_DECL_EXPRPRINT
831  */
832 SCIP_EXPORT
833 SCIP_DECL_EXPRPRINT(SCIPcallExprPrint);
834 
835 /** calls the curvature callback for an expression
836  *
837  * @see SCIP_DECL_EXPRCURVATURE
838  *
839  * Returns unknown curvature if callback not implemented.
840  */
841 SCIP_EXPORT
842 SCIP_DECL_EXPRCURVATURE(SCIPcallExprCurvature);
843 
844 /** calls the monotonicity callback for an expression
845  *
846  * @see SCIP_DECL_EXPRMONOTONICITY
847  *
848  * Returns unknown monotonicity if callback not implemented.
849  */
850 SCIP_EXPORT
851 SCIP_DECL_EXPRMONOTONICITY(SCIPcallExprMonotonicity);
852 
853 /** calls the eval callback for an expression with given values for children
854  *
855  * Does not iterates over expressions, but requires values for children to be given.
856  * Value is not stored in expression, but returned in `val`.
857  * If an evaluation error (division by zero, ...) occurs, this value will
858  * be set to `SCIP_INVALID`.
859  */
860 SCIP_EXPORT
862  SCIP* scip, /**< SCIP data structure */
863  SCIP_EXPR* expr, /**< expression to be evaluated */
864  SCIP_Real* childrenvalues, /**< values for children */
865  SCIP_Real* val /**< buffer to store evaluated value */
866  );
867 
868 /** calls the eval and fwdiff callback of an expression with given values for children
869  *
870  * Does not iterates over expressions, but requires values for children and direction to be given.
871  *
872  * Value is not stored in expression, but returned in `val`.
873  * If an evaluation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
874  *
875  * Direction is not stored in expression, but returned in `dot`.
876  * If an differentiation error (division by zero, ...) occurs, this value will be set to `SCIP_INVALID`.
877  */
878 SCIP_EXPORT
880  SCIP* scip, /**< SCIP data structure */
881  SCIP_EXPR* expr, /**< expression to be evaluated */
882  SCIP_Real* childrenvalues, /**< values for children */
883  SCIP_Real* direction, /**< direction in which to differentiate */
884  SCIP_Real* val, /**< buffer to store evaluated value */
885  SCIP_Real* dot /**< buffer to store derivative value */
886  );
887 
888 /** calls the interval evaluation callback for an expression
889  *
890  * @see SCIP_DECL_EXPRINTEVAL
891  *
892  * Returns entire interval if callback not implemented.
893  */
894 SCIP_EXPORT
895 SCIP_DECL_EXPRINTEVAL(SCIPcallExprInteval);
896 
897 /** calls the estimate callback for an expression
898  *
899  * @see SCIP_DECL_EXPRESTIMATE
900  *
901  * Returns without success if callback not implemented.
902  */
903 SCIP_EXPORT
904 SCIP_DECL_EXPRESTIMATE(SCIPcallExprEstimate);
905 
906 /** calls the initial estimators callback for an expression
907  *
908  * @see SCIP_DECL_EXPRINITESTIMATES
909  *
910  * Returns no estimators if callback not implemented.
911  */
912 SCIP_EXPORT
913 SCIP_DECL_EXPRINITESTIMATES(SCIPcallExprInitestimates);
914 
915 /** calls the simplify callback for an expression
916  *
917  * @see SCIP_DECL_EXPRSIMPLIFY
918  *
919  * Returns unmodified expression if simplify callback not implemented.
920  *
921  * Does not simplify descendants (children, etc). Use SCIPsimplifyExpr() for that.
922  */
923 SCIP_EXPORT
924 SCIP_DECL_EXPRSIMPLIFY(SCIPcallExprSimplify);
925 
926 /** calls the reverse propagation callback for an expression
927  *
928  * @see SCIP_DECL_EXPRREVERSEPROP
929  *
930  * Returns unmodified `childrenbounds` if reverseprop callback not implemented.
931  */
932 SCIP_EXPORT
933 SCIP_DECL_EXPRREVERSEPROP(SCIPcallExprReverseprop);
934 
935 #ifdef NDEBUG
936 #define SCIPappendExprChild(scip, expr, child) SCIPexprAppendChild((scip)->set, (scip)->mem->probmem, expr, child)
937 #define SCIPreplaceExprChild(scip, expr, childidx, newchild) SCIPexprReplaceChild((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, childidx, newchild)
938 #define SCIPremoveExprChildren(scip, expr) SCIPexprRemoveChildren((scip)->set, (scip)->stat, (scip)->mem->probmem, expr)
939 #define SCIPduplicateExpr(scip, expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata) SCIPexprCopy((scip)->set, (scip)->stat, (scip)->mem->probmem, (scip)->set, (scip)->stat, (scip)->mem->probmem, expr, copyexpr, mapexpr, mapexprdata, ownercreate, ownercreatedata)
940 #define SCIPduplicateExprShallow(scip, expr, copyexpr, ownercreate, ownercreatedata) SCIPexprDuplicateShallow((scip)->set, (scip)->mem->probmem, expr, copyexpr, ownercreate, ownercreatedata)
941 #define SCIPcaptureExpr(expr) SCIPexprCapture(expr)
942 #define SCIPreleaseExpr(scip, expr) SCIPexprRelease((scip)->set, (scip)->stat, (scip)->mem->probmem, expr)
943 #define SCIPisExprVar(scip, expr) SCIPexprIsVar((scip)->set, expr)
944 #define SCIPisExprValue(scip, expr) SCIPexprIsValue((scip)->set, expr)
945 #define SCIPisExprSum(scip, expr) SCIPexprIsSum((scip)->set, expr)
946 #define SCIPisExprProduct(scip, expr) SCIPexprIsProduct((scip)->set, expr)
947 #define SCIPisExprPower(scip, expr) SCIPexprIsPower((scip)->set, expr)
948 #define SCIPprintExpr(scip, expr, file) SCIPexprPrint((scip)->set, (scip)->stat, (scip)->mem->probmem, (scip)->messagehdlr, file, expr)
949 #define SCIPevalExpr(scip, expr, sol, soltag) SCIPexprEval((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag)
950 #define SCIPgetExprNewSoltag(scip) (++((scip)->stat->exprlastsoltag))
951 #define SCIPevalExprGradient(scip, expr, sol, soltag) SCIPexprEvalGradient((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag)
952 #define SCIPevalExprHessianDir(scip, expr, sol, soltag, direction) SCIPexprEvalHessianDir((scip)->set, (scip)->stat, (scip)->mem->probmem, expr, sol, soltag, direction)
953 #define SCIPevalExprActivity(scip, expr) SCIPexprEvalActivity((scip)->set, (scip)->stat, (scip)->mem->probmem, expr)
954 #define SCIPcompareExpr(scip, expr1, expr2) SCIPexprCompare((scip)->set, expr1, expr2)
955 #define SCIPsimplifyExpr(scip, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata) SCIPexprSimplify((scip)->set, (scip)->stat, (scip)->mem->probmem, rootexpr, simplified, changed, infeasible, ownercreate, ownercreatedata)
956 #define SCIPcallExprCurvature(scip, expr, exprcurvature, success, childcurv) SCIPexprhdlrCurvatureExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, exprcurvature, success, childcurv)
957 #define SCIPcallExprMonotonicity(scip, expr, childidx, result) SCIPexprhdlrMonotonicityExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, childidx, result)
958 #define SCIPcallExprEval(scip, expr, childrenvalues, val) SCIPexprhdlrEvalExpr(SCIPexprGetHdlr(expr), (scip)->set, (scip)->mem->buffer, expr, val, childrenvalues, NULL)
959 #define SCIPcallExprEvalFwdiff(scip, expr, childrenvalues, direction, val, dot) SCIPexprhdlrEvalFwDiffExpr(SCIPexprGetHdlr(expr), (scip)->set, (scip)->mem->buffer, expr, val, dot, childrenvalues, NULL, direction, NULL)
960 #define SCIPcallExprInteval(scip, expr, interval, intevalvar, intevalvardata) SCIPexprhdlrIntEvalExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, interval, intevalvar, intevalvardata)
961 #define SCIPcallExprEstimate(scip, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue, coefs, constant, islocal, success, branchcand) SCIPexprhdlrEstimateExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue, coefs, constant, islocal, success, branchcand)
962 #define SCIPcallExprInitestimates(scip, expr, bounds, overestimate, coefs, constant, nreturned) SCIPexprhdlrInitEstimatesExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, bounds, overestimate, coefs, constant, nreturned)
963 #define SCIPcallExprSimplify(scip, expr, simplifiedexpr, ownercreate, ownercreatedata) SCIPexprhdlrSimplifyExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, simplifiedexpr, ownercreate, ownercreatedata)
964 #define SCIPcallExprReverseprop(scip, expr, bounds, childrenbounds, infeasible) SCIPexprhdlrReversePropExpr(SCIPexprGetHdlr(expr), (scip)->set, expr, bounds, childrenbounds, infeasible)
965 #endif
966 
967 /** @} */
968 
969 
970 /**@name Expression Iterator */
971 /**@{ */
972 
973 /** creates an expression iterator */
974 SCIP_EXPORT
976  SCIP* scip, /**< SCIP data structure */
977  SCIP_EXPRITER** iterator /**< buffer to store expression iterator */
978  );
979 
980 /** frees an expression iterator */
981 SCIP_EXPORT
982 void SCIPfreeExpriter(
983  SCIP_EXPRITER** iterator /**< pointer to the expression iterator */
984  );
985 
986 #ifdef NDEBUG
987 #define SCIPcreateExpriter(scip, iterator) SCIPexpriterCreate((scip)->stat, (scip)->mem->probmem, iterator)
988 #define SCIPfreeExpriter(iterator) SCIPexpriterFree(iterator)
989 #endif
990 
991 /** @} */
992 
993 
994 /**@name Quadratic Expressions */
995 /**@{ */
996 
997 /** checks whether an expression is quadratic
998  *
999  * An expression is quadratic if it is either a square (of some expression), a product (of two expressions),
1000  * or a sum of terms where at least one is a square or a product.
1001  *
1002  * Use SCIPexprGetQuadraticData() to get data about the representation as quadratic.
1003  */
1004 SCIP_EXPORT
1006  SCIP* scip, /**< SCIP data structure */
1007  SCIP_EXPR* expr, /**< expression */
1008  SCIP_Bool* isquadratic /**< buffer to store result */
1009  );
1010 
1011 /** frees information on quadratic representation of an expression
1012  *
1013  * Before doing changes to an expression, it can be useful to call this function.
1014  */
1015 SCIP_EXPORT
1017  SCIP* scip, /**< SCIP data structure */
1018  SCIP_EXPR* expr /**< expression */
1019  );
1020 
1021 /** evaluates quadratic term in a solution
1022  *
1023  * \note This requires that every expressiion used in the quadratic data is a variable expression.
1024  */
1025 SCIP_EXPORT
1027  SCIP* scip, /**< SCIP data structure */
1028  SCIP_EXPR* expr, /**< quadratic expression */
1029  SCIP_SOL* sol /**< solution to evaluate, or NULL for LP solution */
1030  );
1031 
1032 /** prints quadratic expression */
1033 SCIP_EXPORT
1035  SCIP* scip, /**< SCIP data structure */
1036  SCIP_EXPR* expr /**< quadratic expression */
1037  );
1038 
1039 /** checks the curvature of the quadratic expression
1040  *
1041  * For this, it builds the matrix Q of quadratic coefficients and computes its eigenvalues using LAPACK.
1042  * If Q is
1043  * - semidefinite positive -> curv is set to convex,
1044  * - semidefinite negative -> curv is set to concave,
1045  * - otherwise -> curv is set to unknown.
1046  *
1047  * If `assumevarfixed` is given and some expressions in quadratic terms correspond to variables present in
1048  * this hashmap, then the corresponding rows and columns are ignored in the matrix Q.
1049  */
1050 SCIP_EXPORT
1052  SCIP* scip, /**< SCIP data structure */
1053  SCIP_EXPR* expr, /**< quadratic expression */
1054  SCIP_EXPRCURV* curv, /**< pointer to store the curvature of quadratics */
1055  SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */
1056  SCIP_Bool storeeigeninfo /**< whether the eigenvalues and eigenvectors should be stored */
1057  );
1058 
1059 #ifdef NDEBUG
1060 #define SCIPcheckExprQuadratic(scip, expr, isquadratic) SCIPexprCheckQuadratic((scip)->set, (scip)->mem->probmem, expr, isquadratic)
1061 #define SCIPfreeExprQuadratic(scip, expr) SCIPexprFreeQuadratic((scip)->mem->probmem, expr)
1062 #define SCIPcomputeExprQuadraticCurvature(scip, expr, curv, assumevarfixed, storeeigeninfo) SCIPexprComputeQuadraticCurvature((scip)->set, (scip)->mem->probmem, (scip)->mem->buffer, (scip)->messagehdlr, expr, curv, assumevarfixed, storeeigeninfo)
1063 #endif
1064 
1065 /** @} */
1066 
1067 /** @} */
1068 
1069 #ifdef __cplusplus
1070 }
1071 #endif
1072 
1073 #endif /* SCIP_SCIP_EXPR_H_ */
int SCIPgetNExprhdlrs(SCIP *scip)
Definition: scip_expr.c:848
SCIP_Longint SCIPgetExprNewSoltag(SCIP *scip)
Definition: scip_expr.c:1640
static SCIP_RETCODE eval(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRINTDATA *exprintdata, const vector< Type > &x, Type &val)
SCIP_RETCODE SCIPduplicateExprShallow(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1291
#define SCIP_DECL_EXPREVAL(x)
Definition: type_expr.h:414
SCIP_RETCODE SCIPsimplifyExpr(SCIP *scip, SCIP_EXPR *rootexpr, SCIP_EXPR **simplified, SCIP_Bool *changed, SCIP_Bool *infeasible, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1762
SCIP_EXPRHDLR ** SCIPgetExprhdlrs(SCIP *scip)
Definition: scip_expr.c:837
SCIP_EXPRHDLR * SCIPgetExprhdlrVar(SCIP *scip)
Definition: scip_expr.c:871
SCIP_DECL_EXPRINTEVAL(SCIPcallExprInteval)
Definition: scip_expr.c:2211
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1476
type definitions for miscellaneous datastructures
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
Definition: scip_expr.c:2549
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1706
SCIP_DECL_EXPRESTIMATE(SCIPcallExprEstimate)
Definition: scip_expr.c:2227
SCIP_RETCODE SCIPreplaceCommonSubexpressions(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Bool *replacedroot)
Definition: scip_expr.c:1793
SCIP_Real SCIPevalExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol)
Definition: scip_expr.c:2373
SCIP_RETCODE SCIPcheckExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
Definition: scip_expr.c:2340
private functions to work with algebraic expressions
SCIP_RETCODE SCIPduplicateExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_MAPEXPR((*mapexpr)), void *mapexprdata, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1271
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:44
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA
Definition: type_expr.h:716
SCIP_DECL_EXPRMONOTONICITY(SCIPcallExprMonotonicity)
Definition: scip_expr.c:2144
SCIP_RETCODE SCIPcomputeExprCurvature(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1908
SCIP_DECL_EXPRREVERSEPROP(SCIPcallExprReverseprop)
Definition: scip_expr.c:2280
SCIP_EXPRHDLR * SCIPgetExprhdlrProduct(SCIP *scip)
Definition: scip_expr.c:904
SCIP_EXPRHDLR * SCIPgetExprhdlrSum(SCIP *scip)
Definition: scip_expr.c:893
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1399
void SCIPfreeExprQuadratic(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:2358
SCIP_RETCODE SCIPprintExprDot(SCIP *scip, SCIP_EXPRPRINTDATA *printdata, SCIP_EXPR *expr)
Definition: scip_expr.c:1523
SCIP_DECL_EXPRINITESTIMATES(SCIPcallExprInitestimates)
Definition: scip_expr.c:2244
SCIP_EXPRHDLR * SCIPfindExprhdlr(SCIP *scip, const char *name)
Definition: scip_expr.c:859
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1656
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1454
SCIP_RETCODE SCIPevalExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1623
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: scip_expr.c:1723
SCIP_RETCODE SCIPprintExprDotInit2(SCIP *scip, SCIP_EXPRPRINTDATA **printdata, const char *filename, SCIP_EXPRPRINT_WHAT whattoprint)
Definition: scip_expr.c:1507
SCIP_RETCODE SCIPprintExprDotInit(SCIP *scip, SCIP_EXPRPRINTDATA **printdata, FILE *file, SCIP_EXPRPRINT_WHAT whattoprint)
Definition: scip_expr.c:1491
SCIP_RETCODE SCIPcallExprEvalFwdiff(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *direction, SCIP_Real *val, SCIP_Real *dot)
Definition: scip_expr.c:2187
SCIP_RETCODE SCIPcreateExpr(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, int nchildren, SCIP_EXPR **children, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:964
SCIP_RETCODE SCIPcreateExprMonomial(SCIP *scip, SCIP_EXPR **expr, int nfactors, SCIP_VAR **vars, SCIP_Real *exponents, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1131
type definitions for SCIP&#39;s main datastructure
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1432
SCIP_RETCODE SCIPgetExprVarExprs(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **varexprs, int *nvarexprs)
Definition: scip_expr.c:2069
SCIP_RETCODE SCIPreplaceExprChild(SCIP *scip, SCIP_EXPR *expr, int childidx, SCIP_EXPR *newchild)
Definition: scip_expr.c:1238
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1443
internal methods for global SCIP settings
SCIP main data structure.
unsigned int SCIP_EXPRPRINT_WHAT
Definition: type_expr.h:715
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2300
SCIP_EXPRHDLR * SCIPgetExprhdlrValue(SCIP *scip)
Definition: scip_expr.c:882
SCIP_RETCODE SCIPcallExprEval(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *val)
Definition: scip_expr.c:2160
SCIP_RETCODE SCIPprintExprQuadratic(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:2433
SCIP_RETCODE SCIPshowExpr(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1559
#define SCIP_Bool
Definition: def.h:84
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition: type_expr.h:131
SCIP_EXPRCURV
Definition: type_expr.h:48
SCIP_RETCODE SCIPcopyExpr(SCIP *sourcescip, SCIP *targetscip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *valid)
Definition: scip_expr.c:1308
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
SCIP_RETCODE SCIPappendExprChild(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child)
Definition: scip_expr.c:1220
SCIP_RETCODE SCIPparseExpr(SCIP *scip, SCIP_EXPR **expr, const char *exprstr, const char **finalpos, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1370
SCIP_RETCODE SCIPgetExprNVars(SCIP *scip, SCIP_EXPR *expr, int *nvars)
Definition: scip_expr.c:2031
datastructures for block memory pools and memory buffers
SCIP_DECL_EXPRCURVATURE(SCIPcallExprCurvature)
Definition: scip_expr.c:2129
SCIP_RETCODE SCIPcomputeExprIntegrality(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1988
SCIP_RETCODE SCIPcreateExpr2(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, SCIP_EXPR *child1, SCIP_EXPR *child2, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:985
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:183
datastructures for problem statistics
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1465
SCIP_EXPRHDLR * SCIPgetExprhdlrPower(SCIP *scip)
Definition: scip_expr.c:915
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2314
SCIP_DECL_EXPRPRINT(SCIPcallExprPrint)
Definition: scip_expr.c:2113
type and macro definitions related to algebraic expressions
SCIP_RETCODE SCIPevalExprHessianDir(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag, SCIP_SOL *direction)
Definition: scip_expr.c:1678
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
#define SCIP_DECL_EXPR_MAPEXPR(x)
Definition: type_expr.h:170
#define SCIP_Real
Definition: def.h:177
SCIP_DECL_EXPRSIMPLIFY(SCIPcallExprSimplify)
Definition: scip_expr.c:2262
#define SCIP_Longint
Definition: def.h:162
SCIP_RETCODE SCIPprintExprDotFinal(SCIP *scip, SCIP_EXPRPRINTDATA **printdata)
Definition: scip_expr.c:1537
SCIP_RETCODE SCIPdismantleExpr(SCIP *scip, FILE *file, SCIP_EXPR *expr)
Definition: scip_expr.c:1596
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition: scip_expr.c:814
datastructures for global SCIP settings
SCIP_RETCODE SCIPremoveExprChildren(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1257
SCIP_RETCODE SCIPcreateExprQuadratic(SCIP *scip, SCIP_EXPR **expr, int nlinvars, SCIP_VAR **linvars, SCIP_Real *lincoefs, int nquadterms, SCIP_VAR **quadvars1, SCIP_VAR **quadvars2, SCIP_Real *quadcoefs, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1023
SCIP_RETCODE SCIPhashExpr(SCIP *scip, SCIP_EXPR *expr, unsigned int *hashval)
Definition: scip_expr.c:1735