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