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