Scippy

SCIP

Solving Constraint Integer Programs

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