SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
type_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 type_expr.h
26 * @ingroup TYPEDEFINITIONS
27 * @brief type and macro definitions related to algebraic expressions
28 * @author Ksenia Bestuzheva
29 * @author Benjamin Mueller
30 * @author Felipe Serrano
31 * @author Stefan Vigerske
32 *
33 * This file defines the interface for expression handlers.
34 *
35 * - \ref EXPRHDLRS "List of available expression handlers"
36 */
37
38/** @defgroup DEFPLUGINS_EXPR Default expression handlers
39 * @ingroup DEFPLUGINS
40 * @brief implementation files (.c files) of the default expression handlers of SCIP
41 */
42
43#ifndef SCIP_TYPE_EXPR_H_
44#define SCIP_TYPE_EXPR_H_
45
46#include "scip/def.h"
47#include "scip/intervalarith.h"
48#include "scip/type_scip.h"
49#include "scip/type_sol.h"
50#include "scip/type_var.h"
51#include "scip/type_tree.h"
52
53typedef struct SCIP_ExprData SCIP_EXPRDATA; /**< expression data, e.g., coefficients */
54typedef struct SCIP_Expr SCIP_EXPR; /**< expression */
55
56/** curvature types */
57typedef enum
58{
59 SCIP_EXPRCURV_UNKNOWN = 0, /**< unknown or indefinite curvature */
60 SCIP_EXPRCURV_CONVEX = 1, /**< convex */
61 SCIP_EXPRCURV_CONCAVE = 2, /**< concave */
62 SCIP_EXPRCURV_LINEAR = SCIP_EXPRCURV_CONVEX | SCIP_EXPRCURV_CONCAVE/**< linear = convex and concave */
64
65/** monotonicity */
66typedef enum
67{
68 SCIP_MONOTONE_UNKNOWN = 0, /**< unknown or non-monotone */
69 SCIP_MONOTONE_INC = 1, /**< increasing */
70 SCIP_MONOTONE_DEC = 2, /**< decreasing */
71 SCIP_MONOTONE_CONST = SCIP_MONOTONE_INC | SCIP_MONOTONE_DEC /**< constant = increasing and decreasing */
73
74/**@name Expression Owner */
75/**@{ */
76
77typedef struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA; /**< data stored by expression owner (e.g., conshdlr, nlp) in expression */
78
79/** callback for freeing ownerdata of expression
80 *
81 * This callback is called while an expression is freed.
82 * The callback shall free the ownerdata, if any.
83 * That is, the callback is also called on expressions that only store this callback, but no ownerdata.
84 *
85 * Note, that the children of the expression have already been released when this callback is called.
86 * The callback must not try to access the expressions children.
87 *
88 * \param[in] scip SCIP main data structure
89 * \param[in] expr the expression which is freed
90 * \param[in] ownerdata the ownerdata stored in the expression
91 */
92#define SCIP_DECL_EXPR_OWNERFREE(x) SCIP_RETCODE x(\
93 SCIP* scip, \
94 SCIP_EXPR* expr, \
95 SCIP_EXPR_OWNERDATA** ownerdata)
96
97/** callback for printing ownerdata of expression
98 *
99 * This callback is called when printing details on an expression, e.g., SCIPdismantleExpr().
100 *
101 * \param[in] scip SCIP main data structure
102 * \param[in] expr the expression which is printed
103 * \param[in] file file to print to, or NULL for stdout
104 * \param[in] ownerdata the ownerdata stored in the expression
105 */
106#define SCIP_DECL_EXPR_OWNERPRINT(x) SCIP_RETCODE x(\
107 SCIP* scip, \
108 FILE* file, \
109 SCIP_EXPR* expr, \
110 SCIP_EXPR_OWNERDATA* ownerdata)
111
112/** callback for owner-specific activity evaluation
113 *
114 * This callback is called when evaluating the activity of an expression, e.g., SCIPevalActivity().
115 * The callback should ensure that activity is updated, if required, by calling SCIPsetActivity().
116 * The callback can use the activitytag in the expression to recognize whether it needs to become active.
117 *
118 * \param[in] scip SCIP main data structure
119 * \param[in] expr the expression for which activity should be updated
120 * \param[in] ownerdata the ownerdata stored in the expression
121 */
122#define SCIP_DECL_EXPR_OWNEREVALACTIVITY(x) SCIP_RETCODE x(\
123 SCIP* scip, \
124 SCIP_EXPR* expr, \
125 SCIP_EXPR_OWNERDATA* ownerdata)
126
127/** callback for creating ownerdata of expression
128 *
129 * This callback is called when an expression has been created.
130 * It can create data which is then stored in the expression.
131 *
132 * \param[in] scip SCIP main data structure
133 * \param[in] expr the expression that has been created
134 * \param[out] ownerdata buffer to store ownerdata that shall be stored in expression (can be NULL, initialized to NULL)
135 * \param[out] ownerfree buffer to store function to be called to free ownerdata when expression is freed (can be NULL, initialized to NULL)
136 * \param[out] ownerprint buffer to store function to be called to print ownerdata (can be NULL, initialized to NULL)
137 * \param[out] ownerevalactivity buffer to store function to be called to evaluate activity (can be NULL, initialized to NULL)
138 * \param[in] ownercreatedata data that has been passed on by future owner of expression that can be used to create ownerdata
139 */
140#define SCIP_DECL_EXPR_OWNERCREATE(x) SCIP_RETCODE x(\
141 SCIP* scip, \
142 SCIP_EXPR* expr, \
143 SCIP_EXPR_OWNERDATA** ownerdata, \
144 SCIP_DECL_EXPR_OWNERFREE((**ownerfree)), \
145 SCIP_DECL_EXPR_OWNERPRINT((**ownerprint)), \
146 SCIP_DECL_EXPR_OWNEREVALACTIVITY((**ownerevalactivity)), \
147 void* ownercreatedata)
148
149/** @} */ /* expression owner */
150
151/** callback that returns bounds for a given variable as used in interval evaluation
152 *
153 * Implements a relaxation scheme for variable bounds and translates between different infinity values.
154 * Returns an interval that contains the current variable bounds, but might be (slightly) larger.
155 *
156 * \param[in] scip SCIP main data structure
157 * \param[in] var variable for which to obtain bounds
158 * \param[in] intevalvardata data that belongs to this callback
159 */
160#define SCIP_DECL_EXPR_INTEVALVAR(x) SCIP_INTERVAL x (\
161 SCIP* scip, \
162 SCIP_VAR* var, \
163 void* intevalvardata \
164 )
165
166/** expression mapping callback for expression copy callback
167 *
168 * The method maps an expression (in a source SCIP instance) to an expression
169 * (in a target SCIP instance) and captures the target expression.
170 *
171 * \param[in] targetscip target SCIP main data structure
172 * \param[out] targetexpr pointer to store the mapped expression, or NULL if expression shall be copied; initialized to NULL
173 * \param[in] sourcescip source SCIP main data structure
174 * \param[in] sourceexpr expression to be mapped
175 * \param[in] ownercreate callback to call when creating a new expression
176 * \param[in] ownercreatedata data for ownercreate callback
177 * \param[in] mapexprdata data of mapexpr callback
178 */
179#define SCIP_DECL_EXPR_MAPEXPR(x) SCIP_RETCODE x (\
180 SCIP* targetscip, \
181 SCIP_EXPR** targetexpr, \
182 SCIP* sourcescip, \
183 SCIP_EXPR* sourceexpr, \
184 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \
185 void* ownercreatedata, \
186 void* mapexprdata)
187
188/**@name Expression Handler */
189/**@{ */
190
191typedef struct SCIP_Exprhdlr SCIP_EXPRHDLR; /**< expression handler */
192typedef struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA; /**< expression handler data, e.g., SCIP parameter values */
193
194/** the maximal number of estimates an expression handler can return in the INITESTIMATES callback */
195#define SCIP_EXPR_MAXINITESTIMATES 10
196
197/** expression handler copy callback
198 *
199 * The method should include the expression handler into a given SCIP instance.
200 * It is usually called when doing a copy of SCIP.
201 *
202 * \param[in] scip target SCIP main data structure where to include expression handler
203 * \param[in] sourceexprhdlr expression handler in source SCIP
204 *
205 * See also \ref EXPRCOPYHDLR.
206 */
207#define SCIP_DECL_EXPRCOPYHDLR(x) SCIP_RETCODE x (\
208 SCIP* scip, \
209 SCIP_EXPRHDLR* sourceexprhdlr)
210
211/** expression handler free callback
212 *
213 * Frees the data of an expression handler.
214 *
215 * \param[in] scip SCIP main data structure
216 * \param[in] exprhdlr expression handler
217 * \param[in] exprhdlrdata expression handler data to be freed
218 *
219 * See also \ref EXPRFREEHDLR.
220 */
221#define SCIP_DECL_EXPRFREEHDLR(x) SCIP_RETCODE x (\
222 SCIP* scip, \
223 SCIP_EXPRHDLR* exprhdlr, \
224 SCIP_EXPRHDLRDATA** exprhdlrdata)
225
226/** expression data copy callback
227 *
228 * Copies the data of an expression.
229 *
230 * This method is called when creating copies of an expression within
231 * the same or between different SCIP instances. It is given the
232 * source expression, which data shall be copied. It expects
233 * that *targetexprdata will be set. This data will then be used
234 * to create a new expression.
235 *
236 * This callback must be implemented for expressions that have data.
237 *
238 * \param[in] targetscip target SCIP main data structure
239 * \param[in] targetexprhdlr expression handler in target SCIP
240 * \param[out] targetexprdata pointer to store the copied expression data
241 * \param[in] sourcescip source SCIP main data structure
242 * \param[in] sourceexpr expression in source SCIP which data is to be copied
243 *
244 * See also \ref EXPRCOPYDATA.
245 */
246#define SCIP_DECL_EXPRCOPYDATA(x) SCIP_RETCODE x (\
247 SCIP* targetscip, \
248 SCIP_EXPRHDLR* targetexprhdlr, \
249 SCIP_EXPRDATA** targetexprdata, \
250 SCIP* sourcescip, \
251 SCIP_EXPR* sourceexpr)
252
253/** expression data free callback
254 *
255 * Frees the data of an expression.
256 * Shall call SCIPexprSetData(expr, NULL).
257 *
258 * This callback must be implemented for expressions that have data.
259 *
260 * \param[in] scip SCIP main data structure
261 * \param[in] expr the expression which data to be freed
262 *
263 * See also \ref EXPRFREEDATA.
264 */
265#define SCIP_DECL_EXPRFREEDATA(x) SCIP_RETCODE x (\
266 SCIP* scip, \
267 SCIP_EXPR* expr)
268
269/** expression print callback
270 *
271 * Prints an expression.
272 * It is called while DFS-iterating over the expression at different stages, that is,
273 * when the expression is visited the first time, before each child of the expression is visited,
274 * after each child of the expression has been visited, and when the iterator leaves the expression
275 * for its parent. See also \ref SCIP_EXPRITER_DFS "expression iteration docu".
276 *
277 * \param[in] scip SCIP main data structure
278 * \param[in] expr expression which data is to be printed
279 * \param[in] stage stage of expression iteration
280 * \param[in] currentchild index of current child if in stage visitingchild or visitedchild
281 * \param[in] parentprecedence precedence of parent
282 * \param[in] file the file to print to
283 *
284 * See also \ref EXPRPRINT.
285 */
286#define SCIP_DECL_EXPRPRINT(x) SCIP_RETCODE x (\
287 SCIP* scip, \
288 SCIP_EXPR* expr, \
289 SCIP_EXPRITER_STAGE stage, \
290 int currentchild, \
291 unsigned int parentprecedence, \
292 FILE* file)
293
294/** expression parse callback
295 *
296 * Parses an expression.
297 * It is called when parsing an expression and an operator with the expr handler name is found.
298 *
299 * \param[in] scip SCIP main data structure
300 * \param[in] string string containing expression to be parse
301 * \param[in] ownercreate function to call to create ownerdata
302 * \param[in] ownercreatedata data to pass to ownercreate
303 * \param[out] endstring buffer to store the position of string after parsing
304 * \param[out] expr buffer to store the parsed expression
305 * \param[out] success buffer to store whether the parsing was successful or not
306 *
307 * See also \ref EXPRPARSE.
308 */
309#define SCIP_DECL_EXPRPARSE(x) SCIP_RETCODE x (\
310 SCIP* scip, \
311 SCIP_EXPRHDLR* exprhdlr, \
312 const char* string, \
313 const char** endstring, \
314 SCIP_EXPR** expr, \
315 SCIP_Bool* success, \
316 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \
317 void* ownercreatedata)
318
319/** expression curvature detection callback
320 *
321 * The method returns whether an expression can have a desired curvature under conditions on the
322 * curvature of the children.
323 * That is, the method shall return TRUE in success and requirements on the curvature for each child
324 * which will suffice for this expression to be convex (or concave, or linear, as specified by caller)
325 * w.r.t. the current activities of all children.
326 * It can return "unknown" for a child's curvature if its curvature does not matter (though that's
327 * rarely the case).
328 *
329 * \param[in] scip SCIP main data structure
330 * \param[in] expr expression to check the curvature for
331 * \param[in] exprcurvature desired curvature of this expression
332 * \param[out] success buffer to store whether the desired curvature was obtained
333 * \param[out] childcurv array to store required curvature for each child
334 *
335 * See also \ref EXPRCURVATURE.
336 */
337#define SCIP_DECL_EXPRCURVATURE(x) SCIP_RETCODE x (\
338 SCIP* scip, \
339 SCIP_EXPR* expr, \
340 SCIP_EXPRCURV exprcurvature, \
341 SCIP_Bool* success, \
342 SCIP_EXPRCURV* childcurv)
343
344/** expression monotonicity detection callback
345 *
346 * The method computes the monotonicity of an expression with respect to a given child.
347 *
348 * \param[in] scip SCIP main data structure
349 * \param[in] expr expression to check the monotonicity for
350 * \param[in] childidx index of the considered child expression
351 * \param[out] result buffer to store the monotonicity
352 *
353 * See also \ref EXPRMONOTONICITY.
354 */
355#define SCIP_DECL_EXPRMONOTONICITY(x) SCIP_RETCODE x (\
356 SCIP* scip, \
357 SCIP_EXPR* expr, \
358 int childidx, \
359 SCIP_MONOTONE* result)
360
361/** expression integrality detection callback
362 *
363 * The method checks whether an expression evaluates always to an integral value in a feasible solution.
364 * Usually uses SCIPexprIsIntegral() to check whether children evaluate to an integral value.
365 *
366 * \param[in] scip SCIP main data structure
367 * \param[in] expr expression to check the integrality for
368 * \param[out] isintegral buffer to store whether expr is integral
369 *
370 * See also \ref EXPRINTEGRALITY.
371 */
372#define SCIP_DECL_EXPRINTEGRALITY(x) SCIP_RETCODE x (\
373 SCIP* scip, \
374 SCIP_EXPR* expr, \
375 SCIP_Bool* isintegral)
376
377/** expression hash callback
378 *
379 * The method hashes an expression by taking the hashes of its children into account.
380 *
381 * \param[in] scip SCIP main data structure
382 * \param[in] expr expression to be hashed
383 * \param[out] hashkey buffer to store the hash value
384 * \param[in] childrenhashes array with hash values of children
385 *
386 * See also \ref EXPRHASH.
387 */
388#define SCIP_DECL_EXPRHASH(x) SCIP_RETCODE x (\
389 SCIP* scip, \
390 SCIP_EXPR* expr, \
391 unsigned int* hashkey, \
392 unsigned int* childrenhashes)
393
394/** expression compare callback
395 *
396 * the method receives two expressions, expr1 and expr2. Must return
397 * -1 if expr1 < expr2, or
398 * 0 if expr1 = expr2, or
399 * 1 if expr1 > expr2.
400 *
401 * \param[in] scip SCIP main data structure
402 * \param[in] expr1 first expression in comparison
403 * \param[in] expr2 second expression in comparison
404 *
405 * See also \ref EXPRCOMPARE.
406 */
407#define SCIP_DECL_EXPRCOMPARE(x) int x (\
408 SCIP* scip, \
409 SCIP_EXPR* expr1, \
410 SCIP_EXPR* expr2)
411
412/** expression (point-) evaluation callback
413 *
414 * The method evaluates an expression by taking the values of its children into account.
415 *
416 * \param[in] scip SCIP main data structure
417 * \param[in] expr expression to be evaluated
418 * \param[out] val buffer where to store value
419 * \param[in] sol solution that is evaluated (can be NULL)
420 *
421 * See also \ref EXPREVAL.
422 */
423#define SCIP_DECL_EXPREVAL(x) SCIP_RETCODE x (\
424 SCIP* scip, \
425 SCIP_EXPR* expr, \
426 SCIP_Real* val, \
427 SCIP_SOL* sol)
428
429/** backward derivative evaluation callback
430 *
431 * The method should compute the partial derivative of expr w.r.t. its child at childidx.
432 * That is, it should return
433 * \f[
434 * \frac{\partial \text{expr}}{\partial \text{child}_{\text{childidx}}}
435 * \f]
436 *
437 * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details.
438 *
439 * \param[in] scip SCIP main data structure
440 * \param[in] expr expression to be differentiated
441 * \param[in] childidx index of the child
442 * \param[out] val buffer to store the partial derivative w.r.t. the childidx-th children
443 *
444 * See also \ref EXPRBWDIFF.
445 */
446#define SCIP_DECL_EXPRBWDIFF(x) SCIP_RETCODE x (\
447 SCIP* scip, \
448 SCIP_EXPR* expr, \
449 int childidx, \
450 SCIP_Real* val)
451
452/** forward derivative evaluation callback
453 *
454 * The method should evaluate the directional derivative of expr.
455 * The expr should be interpreted as an operator \f$ \text{expr}(c_1, \ldots, c_n) \f$, where \f$ c_1, \ldots, c_n \f$
456 * are the children of the expr.
457 * The directional derivative is evaluated at the point
458 * SCIPexprGetEvalValue\f$(c_1)\f$, ..., SCIPexprGetEvalValue\f$(c_n)\f$
459 * in the direction given by direction.
460 *
461 * This method should return
462 * \f[
463 * \sum_{i = 1}^n \frac{\partial \text{expr}}{\partial c_i} D_u c_i,
464 * \f]
465 * where \f$ u \f$ is the direction and \f$ D_u c_i \f$ is the directional derivative of the i-th child,
466 * which can be accessed via SCIPexprGetDot().
467 *
468 * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details.
469 *
470 * \param[in] scip SCIP main data structure
471 * \param[in] expr expression to be differentiated
472 * \param[out] dot buffer to store derivative value
473 * \param[in] direction direction of the derivative (useful only for var expressions)
474 *
475 * See also \ref EXPRFWDIFF.
476 */
477#define SCIP_DECL_EXPRFWDIFF(x) SCIP_RETCODE x (\
478 SCIP* scip, \
479 SCIP_EXPR* expr, \
480 SCIP_Real* dot, \
481 SCIP_SOL* direction)
482
483/** derivative evaluation callback for Hessian directions (backward over forward)
484 *
485 * The method computes the total derivative, w.r.t. its children, of the partial derivative of expr w.r.t. childidx.
486 * Equivalently, it computes the partial derivative w.r.t. childidx of the total derivative.
487 *
488 * The expr should be interpreted as an operator \f$ \text{expr}(c_1, \ldots, c_n) \f$, where \f$ c_1, \ldots, c_n \f$
489 * are the children of the expr.
490 * The directional derivative is evaluated at the point
491 * SCIPexprGetEvalValue\f$(c_1)\f$, ..., SCIPexprGetEvalValue\f$(c_n)\f$
492 * in the direction given by direction.
493 *
494 * This method should return
495 * \f[
496 * \sum_{i = 1}^n \frac{\partial^2 \text{expr}}{\partial c_i} \partial c_{\text{childidx}} D_u c_i,
497 * \f]
498 *
499 * where \f$ u \f$ is the direction and \f$ D_u c_i \f$ is the directional derivative of the i-th child,
500 * which can be accessed via SCIPexprGetDot().
501 *
502 * Thus, if \f$ n = 1 \f$ (i.e. if expr represents an univariate operator), the method should return
503 * \f[
504 * \text{expr}^{\prime \prime}(\text{SCIPexprGetEvalValue}(c)) D_u c.
505 * \f]
506 *
507 * See \ref SCIP_EXPR_DIFF "Differentiation methods in scip_expr.h" for more details.
508 *
509 * \param[in] scip SCIP main data structure
510 * \param[in] expr expression to be evaluated
511 * \param[in] childidx index of the child
512 * \param[out] bardot buffer to store derivative value
513 * \param[in] direction direction of the derivative (useful only for var expressions)
514 *
515 * See also \ref EXPRBWFWDIFF.
516 */
517#define SCIP_DECL_EXPRBWFWDIFF(x) SCIP_RETCODE x (\
518 SCIP* scip, \
519 SCIP_EXPR* expr, \
520 int childidx, \
521 SCIP_Real* bardot, \
522 SCIP_SOL* direction)
523
524/** expression (interval-) evaluation callback
525 *
526 * The method evaluates an expression by taking the intervals of its children into account.
527 *
528 * \param[in] scip SCIP main data structure
529 * \param[in] expr expression to be evaluated
530 * \param[out] interval buffer where to store interval
531 * \param[in] intevalvar callback to be called when interval evaluating a variable
532 * \param[in] intevalvardata data to be passed to intevalvar callback
533 *
534 * See also \ref EXPRINTEVAL.
535 */
536#define SCIP_DECL_EXPRINTEVAL(x) SCIP_RETCODE x (\
537 SCIP* scip, \
538 SCIP_EXPR* expr, \
539 SCIP_INTERVAL* interval, \
540 SCIP_DECL_EXPR_INTEVALVAR((*intevalvar)), \
541 void* intevalvardata)
542
543/** expression under/overestimation callback
544 *
545 * The method tries to compute a linear under- or overestimator that is as tight as possible
546 * at a given point. The estimator must be valid w.r.t. the bounds given by localbounds.
547 * If the value of the estimator in the reference point is smaller (larger) than targetvalue
548 * when underestimating (overestimating), then no estimator needs to be computed.
549 * Note, that targetvalue can be infinite if any estimator will be accepted.
550 * If successful, it shall store the coefficient of the i-th child in entry coefs[i] and
551 * the constant part in constant.
552 * If the estimator is also valid w.r.t. the bounds given by globalbounds, then *islocal shall
553 * be set to FALSE.
554 * The callback shall indicate in branchcand[i] whether branching on the i-th child would improve
555 * the estimator. It can be assumed that branchcand[i] has been initialized to TRUE for all children.
556 *
557 * \param[in] scip SCIP main data structure
558 * \param[in] expr expression
559 * \param[in] localbounds current bounds for children
560 * \param[in] globalbounds global bounds for children
561 * \param[in] refpoint values for children in the reference point where to estimate
562 * \param[in] overestimate whether the expression needs to be over- or underestimated
563 * \param[in] targetvalue a value that the estimator shall exceed, can be +/-infinity
564 * \param[out] coefs array to store coefficients of estimator
565 * \param[out] constant buffer to store constant part of estimator
566 * \param[out] islocal buffer to store whether estimator is valid locally only
567 * \param[out] success buffer to indicate whether an estimator could be computed
568 * \param[out] branchcand array to indicate which children to consider for branching
569 *
570 * See also \ref EXPRESTIMATE.
571 */
572#define SCIP_DECL_EXPRESTIMATE(x) SCIP_RETCODE x (\
573 SCIP* scip, \
574 SCIP_EXPR* expr, \
575 SCIP_INTERVAL* localbounds, \
576 SCIP_INTERVAL* globalbounds, \
577 SCIP_Real* refpoint, \
578 SCIP_Bool overestimate, \
579 SCIP_Real targetvalue, \
580 SCIP_Real* coefs, \
581 SCIP_Real* constant, \
582 SCIP_Bool* islocal, \
583 SCIP_Bool* success, \
584 SCIP_Bool* branchcand)
585
586/** expression initial under/overestimation callback
587 *
588 * The method tries to compute a few linear under- or overestimator that approximate the
589 * behavior of the expression. The estimator must be valid w.r.t. the bounds given by bounds.
590 * These estimators may be used to initialize a linear relaxation.
591 * The callback shall return the number of computed estimators in nreturned,
592 * store the coefficient of the i-th child for the j-th estimator in entry coefs[j][i],
593 * and store the constant part for the j-th estimator in constant[j].
594 *
595 * \param[in] scip SCIP main data structure
596 * \param[in] expr expression
597 * \param[in] bounds bounds for children
598 * \param[in] overestimate whether the expression shall be overestimated or underestimated
599 * \param[out] coefs buffer to store coefficients of computed estimators
600 * \param[out] constant buffer to store constant of computed estimators
601 * \param[out] nreturned buffer to store number of estimators that have been computed
602 *
603 * See also \ref EXPRINITESTIMATES.
604 */
605#define SCIP_DECL_EXPRINITESTIMATES(x) SCIP_RETCODE x ( \
606 SCIP* scip, \
607 SCIP_EXPR* expr, \
608 SCIP_INTERVAL* bounds, \
609 SCIP_Bool overestimate, \
610 SCIP_Real* coefs[SCIP_EXPR_MAXINITESTIMATES], \
611 SCIP_Real constant[SCIP_EXPR_MAXINITESTIMATES], \
612 int* nreturned)
613
614/** expression simplify callback
615 *
616 * The method shall try to simplify an expression by applying algebraic transformations
617 * and return the simplified expression.
618 * It can assume that children have been simplified.
619 * If no simplification is possible, then shall set *simplifiedexpr to expr and capture *simplifiedexpr.
620 *
621 * \param[in] scip SCIP main data structure
622 * \param[in] expr expression to simplify
623 * \param[in] ownercreate function to call to create ownerdata
624 * \param[in] ownercreatedata data to pass to ownercreate
625 * \param[out] simplifiedexpr buffer to store the simplified expression
626 *
627 * See also \ref EXPRSIMPLIFY and SCIPsimplifyExpr().
628 */
629#define SCIP_DECL_EXPRSIMPLIFY(x) SCIP_RETCODE x (\
630 SCIP* scip, \
631 SCIP_EXPR* expr, \
632 SCIP_EXPR** simplifiedexpr, \
633 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), \
634 void* ownercreatedata)
635
636/** expression callback for reverse propagation
637 *
638 * The method propagates given bounds over the children of an expression.
639 * Shall compute an interval overestimate on
640 * \f[
641 * \{ x_i : \text{expr}(c_1,\ldots,c_{i-1},x_i,c_{i+1},\ldots,c_n) \in \text{bounds} \}
642 * \f]
643 * for each child i and store it in childrenbounds[i].
644 * The initial intervals \f$c_i, i=1,\ldots,n,\f$ are given by childrenbounds, too.
645 *
646 * \param[in] scip SCIP main data structure
647 * \param[in] expr expression
648 * \param[in] bounds the bounds on the expression that should be propagated
649 * \param[in,out] childrenbounds array to store computed bounds for children, initialized with current activity
650 * \param[out] infeasible buffer to store whether a children bounds were propagated to an empty interval
651 *
652 * See also \ref EXPRREVERSEPROP.
653 */
654#define SCIP_DECL_EXPRREVERSEPROP(x) SCIP_RETCODE x (\
655 SCIP* scip, \
656 SCIP_EXPR* expr, \
657 SCIP_INTERVAL bounds, \
658 SCIP_INTERVAL* childrenbounds, \
659 SCIP_Bool* infeasible)
660
661/** @} */ /* expression handler */
662
663
664
665/** @name Expression iterator
666 * @{
667 */
668
669/** maximal number of iterators that can be active on an expression graph concurrently
670 *
671 * How often an expression graph iteration can be started within an active iteration, plus one.
672 */
673#define SCIP_EXPRITER_MAXNACTIVE 5
674
675/* stages of expression DFS iteration */
676#define SCIP_EXPRITER_ENTEREXPR 1u /**< an expression is visited the first time (before any of its children are visited) */
677#define SCIP_EXPRITER_VISITINGCHILD 2u /**< a child of an expression is to be visited */
678#define SCIP_EXPRITER_VISITEDCHILD 4u /**< a child of an expression has been visited */
679#define SCIP_EXPRITER_LEAVEEXPR 8u /**< an expression is to be left (all of its children have been processed) */
680#define SCIP_EXPRITER_ALLSTAGES (SCIP_EXPRITER_ENTEREXPR | SCIP_EXPRITER_VISITINGCHILD | SCIP_EXPRITER_VISITEDCHILD | SCIP_EXPRITER_LEAVEEXPR)
681
682/** stage of DFS iterator */
683typedef unsigned int SCIP_EXPRITER_STAGE;
684
685/** user data storage type for expression iteration */
686typedef union
687{
688 SCIP_Real realval; /**< a floating-point value */
689 int intval; /**< an integer value */
690 int intvals[2]; /**< two integer values */
691 unsigned int uintval; /**< an unsigned integer value */
692 void* ptrval; /**< a pointer */
694
695/** mode for expression iterator */
696typedef enum
697{
698 SCIP_EXPRITER_RTOPOLOGIC, /**< reverse topological order */
699 SCIP_EXPRITER_BFS, /**< breadth-first search */
700 SCIP_EXPRITER_DFS /**< depth-first search */
702
703typedef struct SCIP_ExprIterData SCIP_EXPRITERDATA; /**< expression iterator data of a specific expression */
704typedef struct SCIP_ExprIter SCIP_EXPRITER; /**< expression iterator */
705
706/** @} */ /* expression iterator */
707
708/** @name Expression printing
709 * @{
710 */
711
712#define SCIP_EXPRPRINT_EXPRSTRING 0x1u /**< print the math. function that the expression represents (e.g., "c0+c1") */
713#define SCIP_EXPRPRINT_EXPRHDLR 0x2u /**< print expression handler name */
714#define SCIP_EXPRPRINT_NUSES 0x4u /**< print number of uses (reference counting) */
715#define SCIP_EXPRPRINT_EVALVALUE 0x8u /**< print evaluation value */
716#define SCIP_EXPRPRINT_EVALTAG 0x18u /**< print evaluation value and tag */
717#define SCIP_EXPRPRINT_ACTIVITY 0x20u /**< print activity value */
718#define SCIP_EXPRPRINT_ACTIVITYTAG 0x60u /**< print activity value and corresponding tag */
719#define SCIP_EXPRPRINT_OWNER 0x80u /**< print ownerdata */
720
721/** print everything */
722#define SCIP_EXPRPRINT_ALL SCIP_EXPRPRINT_EXPRSTRING | SCIP_EXPRPRINT_EXPRHDLR | SCIP_EXPRPRINT_NUSES | SCIP_EXPRPRINT_EVALTAG | SCIP_EXPRPRINT_ACTIVITYTAG | SCIP_EXPRPRINT_OWNER
723
724typedef unsigned int SCIP_EXPRPRINT_WHAT; /**< exprprint bitflags */
725typedef struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA; /**< data when printing an expression */
726
727/** @} */
728
729
730#endif /* SCIP_TYPE_EXPR_H_ */
common defines and data types used in all packages of SCIP
interval arithmetics for provable bounds
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition type_expr.h:192
struct SCIP_ExprData SCIP_EXPRDATA
Definition type_expr.h:53
struct SCIP_ExprIterData SCIP_EXPRITERDATA
Definition type_expr.h:703
SCIP_EXPRCURV
Definition type_expr.h:58
@ SCIP_EXPRCURV_CONVEX
Definition type_expr.h:60
@ SCIP_EXPRCURV_LINEAR
Definition type_expr.h:62
@ SCIP_EXPRCURV_UNKNOWN
Definition type_expr.h:59
@ SCIP_EXPRCURV_CONCAVE
Definition type_expr.h:61
struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA
Definition type_expr.h:77
SCIP_MONOTONE
Definition type_expr.h:67
@ SCIP_MONOTONE_CONST
Definition type_expr.h:71
@ SCIP_MONOTONE_UNKNOWN
Definition type_expr.h:68
@ SCIP_MONOTONE_INC
Definition type_expr.h:69
@ SCIP_MONOTONE_DEC
Definition type_expr.h:70
unsigned int SCIP_EXPRPRINT_WHAT
Definition type_expr.h:724
SCIP_EXPRITER_TYPE
Definition type_expr.h:697
@ SCIP_EXPRITER_BFS
Definition type_expr.h:699
@ SCIP_EXPRITER_DFS
Definition type_expr.h:700
@ SCIP_EXPRITER_RTOPOLOGIC
Definition type_expr.h:698
struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA
Definition type_expr.h:725
unsigned int SCIP_EXPRITER_STAGE
Definition type_expr.h:683
type definitions for SCIP's main datastructure
type definitions for storing primal CIP solutions
type definitions for branch and bound tree
type definitions for problem variables
unsigned int uintval
Definition type_expr.h:691