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 2002-2022 Zuse Institute Berlin */
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 
53 typedef struct SCIP_ExprData SCIP_EXPRDATA; /**< expression data, e.g., coefficients */
54 typedef struct SCIP_Expr SCIP_EXPR; /**< expression */
55 
56 /** curvature types */
57 typedef 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 */
63 } SCIP_EXPRCURV;
64 
65 /** monotonicity */
66 typedef 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 */
72 } SCIP_MONOTONE;
73 
74 /**@name Expression Owner */
75 /**@{ */
76 
77 typedef 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 
191 typedef struct SCIP_Exprhdlr SCIP_EXPRHDLR; /**< expression handler */
192 typedef 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 */
683 typedef unsigned int SCIP_EXPRITER_STAGE;
684 
685 /** user data storage type for expression iteration */
686 typedef 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 */
693 } SCIP_EXPRITER_USERDATA;
694 
695 /** mode for expression iterator */
696 typedef enum
697 {
698  SCIP_EXPRITER_RTOPOLOGIC, /**< reverse topological order */
699  SCIP_EXPRITER_BFS, /**< breadth-first search */
700  SCIP_EXPRITER_DFS /**< depth-first search */
701 } SCIP_EXPRITER_TYPE;
702 
703 typedef struct SCIP_ExprIterData SCIP_EXPRITERDATA; /**< expression iterator data of a specific expression */
704 typedef 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 
724 typedef unsigned int SCIP_EXPRPRINT_WHAT; /**< exprprint bitflags */
725 typedef struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA; /**< data when printing an expression */
726 
727 /** @} */
728 
729 
730 #endif /* SCIP_TYPE_EXPR_H_ */
SCIP_MONOTONE
SCIP_MONOTONE
Definition: type_expr.h:66
SCIP_EXPRITER_USERDATA::realval
SCIP_Real realval
Definition: type_expr.h:688
SCIP_MONOTONE_UNKNOWN
Definition: type_expr.h:68
SCIP_EXPRCURV_CONCAVE
Definition: type_expr.h:61
SCIP_EXPRITER_RTOPOLOGIC
Definition: type_expr.h:698
SCIP_Exprhdlr
Definition: struct_expr.h:43
SCIP_EXPRDATA
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:53
SCIP_EXPRITER_TYPE
SCIP_EXPRITER_TYPE
Definition: type_expr.h:696
SCIP_EXPRPRINTDATA
struct SCIP_ExprPrintData SCIP_EXPRPRINTDATA
Definition: type_expr.h:725
SCIP_EXPRCURV_LINEAR
Definition: type_expr.h:62
SCIP_EXPRITER_USERDATA::uintval
unsigned int uintval
Definition: type_expr.h:691
SCIP_MONOTONE_DEC
Definition: type_expr.h:70
SCIP_EXPR_OWNERDATA
struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA
Definition: type_expr.h:77
SCIP_EXPRITER_USERDATA
Definition: type_expr.h:686
SCIP_MONOTONE_CONST
Definition: type_expr.h:71
SCIP_EXPRITER_BFS
Definition: type_expr.h:699
intervalarith.h
interval arithmetics for provable bounds
SCIP_EXPRCURV_CONVEX
Definition: type_expr.h:60
SCIP_EXPRITER_DFS
Definition: type_expr.h:700
type_scip.h
type definitions for SCIP&#39;s main datastructure
SCIP_EXPRCURV_UNKNOWN
Definition: type_expr.h:59
SCIP_EXPRITERDATA
struct SCIP_ExprIterData SCIP_EXPRITERDATA
Definition: type_expr.h:703
type_var.h
type definitions for problem variables
SCIP_ExprIter
Definition: struct_expr.h:202
SCIP_EXPRPRINT_WHAT
unsigned int SCIP_EXPRPRINT_WHAT
Definition: type_expr.h:724
SCIP_Expr
Definition: struct_expr.h:104
SCIP_EXPRITER_USERDATA::intval
int intval
Definition: type_expr.h:689
SCIP_EXPRCURV
SCIP_EXPRCURV
Definition: type_expr.h:57
SCIP_EXPRITER_USERDATA::ptrval
void * ptrval
Definition: type_expr.h:692
type_tree.h
type definitions for branch and bound tree
SCIP_EXPRHDLRDATA
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:192
type_sol.h
type definitions for storing primal CIP solutions
SCIP_MONOTONE_INC
Definition: type_expr.h:69
SCIP_Real
#define SCIP_Real
Definition: def.h:186
SCIP_EXPRITER_STAGE
unsigned int SCIP_EXPRITER_STAGE
Definition: type_expr.h:683
def.h
common defines and data types used in all packages of SCIP