SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
struct_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 struct_expr.h
26 * @ingroup INTERNALAPI
27 * @brief structure definitions related to algebraic expressions
28 * @author Ksenia Bestuzheva
29 * @author Benjamin Mueller
30 * @author Felipe Serrano
31 * @author Stefan Vigerske
32 */
33
34#ifndef SCIP_STRUCT_EXPR_H_
35#define SCIP_STRUCT_EXPR_H_
36
37#include "scip/type_expr.h"
38#include "scip/type_clock.h"
39#include "scip/type_stat.h"
41
42/** generic data and callback methods of an expression handler */
44{
45 char* name; /**< expression handler name */
46 char* desc; /**< expression handler description (can be NULL) */
47 SCIP_EXPRHDLRDATA* data; /**< data of handler */
48 unsigned int precedence; /**< precedence of expression operation relative to other expression (used for printing) */
49
50 /* callbacks */
51 SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)); /**< handler copy callback (can be NULL) */
52 SCIP_DECL_EXPRFREEHDLR((*freehdlr)); /**< handler free callback (can be NULL) */
53 SCIP_DECL_EXPRCOPYDATA((*copydata)); /**< data copy callback, or NULL for expressions that have no data */
54 SCIP_DECL_EXPRFREEDATA((*freedata)); /**< data free callback, or NULL for expressions that have no data or which data does not need to be freed */
55 SCIP_DECL_EXPRSIMPLIFY((*simplify)); /**< simplify callback (can be NULL) */
56 SCIP_DECL_EXPRCOMPARE((*compare)); /**< compare callback (can be NULL) */
57 SCIP_DECL_EXPRPRINT((*print)); /**< print callback (can be NULL) */
58 SCIP_DECL_EXPRPARSE((*parse)); /**< parse callback (can be NULL) */
59 SCIP_DECL_EXPREVAL((*eval)); /**< point evaluation callback (can never be NULL) */
60 SCIP_DECL_EXPRBWDIFF((*bwdiff)); /**< backward derivative evaluation callback (can be NULL) */
61 SCIP_DECL_EXPRFWDIFF((*fwdiff)); /**< forward derivative evaluation callback (can be NULL) */
62 SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)); /**< backward over forward derivative evaluation callback (can be NULL) */
63 SCIP_DECL_EXPRINTEVAL((*inteval)); /**< interval evaluation callback (can be NULL) */
64 SCIP_DECL_EXPRESTIMATE((*estimate)); /**< estimation callback (can be NULL) */
65 SCIP_DECL_EXPRINITESTIMATES((*initestimates)); /**< initial estimators callback (can be NULL) */
66 SCIP_DECL_EXPRREVERSEPROP((*reverseprop));/**< reverse propagation callback (can be NULL) */
67 SCIP_DECL_EXPRHASH((*hash)); /**< hash callback (can be NULL) */
68 SCIP_DECL_EXPRCURVATURE((*curvature)); /**< curvature detection callback (can be NULL) */
69 SCIP_DECL_EXPRMONOTONICITY((*monotonicity)); /**< monotonicity detection callback (can be NULL) */
70 SCIP_DECL_EXPRINTEGRALITY((*integrality));/**< integrality detection callback (can be NULL) */
71
72 /* statistics */
73 unsigned int ncreated; /**< number of times expression has been created */
74 SCIP_Longint nestimatecalls; /**< number of times the estimation callback was called */
75 SCIP_Longint nintevalcalls; /**< number of times the interval evaluation callback was called */
76 SCIP_Longint npropcalls; /**< number of times the propagation callback was called */
77 SCIP_Longint ncutoffs; /**< number of cutoffs found so far by this expression handler */
78 SCIP_Longint ndomreds; /**< number of domain reductions found so far by this expression handler */
79 SCIP_Longint nsimplifycalls; /**< number of times the simplification callback was called */
80 SCIP_Longint nsimplified; /**< number of times the simplification callback simplified */
81 SCIP_Longint nbranchscores; /**< number of times branching scores were added by (or for) this expression handler */
82
83 SCIP_CLOCK* estimatetime; /**< time used for estimation */
84 SCIP_CLOCK* intevaltime; /**< time used for interval evaluation */
85 SCIP_CLOCK* proptime; /**< time used for propagation */
86 SCIP_CLOCK* simplifytime; /**< time used for expression simplification */
87};
88
89/** expression iteration data stored in an expression */
90struct SCIP_ExprIterData
91{
92 SCIP_EXPR* parent; /**< parent expression in DFS iteration */
93 int currentchild; /**< child that is currently visited (or will be visited next) by DFS iteration */
94 SCIP_Longint visitedtag; /**< tag to identify whether an expression has been visited already */
95 SCIP_EXPRITER_USERDATA userdata; /**< space for iterator user to store some (temporary) data */
96};
97
98/* private types */
99typedef struct SCIP_QuadExpr SCIP_QUADEXPR; /**< representation of expression as quadratic */
100typedef struct SCIP_QuadExpr_QuadTerm SCIP_QUADEXPR_QUADTERM; /**< a single term associated to a quadratic variable */
101typedef struct SCIP_QuadExpr_BilinTerm SCIP_QUADEXPR_BILINTERM; /**< a single bilinear term */
102
103/** an algebraic expression */
105{
106 SCIP_EXPRHDLR* exprhdlr; /**< expression type (as pointer to its handler) */
107 SCIP_EXPRDATA* exprdata; /**< expression data */
108
109 int nchildren; /**< number of children */
110 int childrensize; /**< length of children array */
111 SCIP_EXPR** children; /**< children expressions */
112
113 int nuses; /**< reference counter */
114 SCIP_EXPRITERDATA iterdata[SCIP_EXPRITER_MAXNACTIVE]; /**< data for expression iterators */
115
116 /* owner data */
117 SCIP_EXPR_OWNERDATA* ownerdata; /**< data stored by owner of expression */
118 SCIP_DECL_EXPR_OWNERFREE((*ownerfree)); /**< callback for freeing ownerdata */
119 SCIP_DECL_EXPR_OWNERPRINT((*ownerprint)); /**< callback for printing ownerdata */
120 SCIP_DECL_EXPR_OWNEREVALACTIVITY((*ownerevalactivity)); /**< callback for evaluating activity */
121
122 /* point-evaluation and differentiation*/
123 SCIP_Real evalvalue; /**< value of expression from last evaluation (corresponding to evaltag) */
124 SCIP_Real derivative; /**< partial derivative of a "root path" w.r.t. this expression (see \ref SCIP_EXPR_DIFF "Differentiation methods") */
125 SCIP_Real dot; /**< directional derivative of this expr (see \ref SCIP_EXPR_DIFF "Differentiation methods") */
126 SCIP_Real bardot; /**< directional derivative of derivative of root (strictly speaking, a path) w.r.t this expr (see \ref SCIP_EXPR_DIFF "Differentiation methods") */
127 SCIP_Longint evaltag; /**< tag of point for which the expression has been evaluated last, or 0 */
128 SCIP_Longint difftag; /**< when computing partial derivatives of an expression w.r.t. a variable,
129 * the tag allows us to decide whether the expression depends on the variable;
130 * the tag will be checked in SCIPgetExprPartialDiff() */
131
132 /* interval-evaluation (activity) */
133 SCIP_INTERVAL activity; /**< activity of expression with respect to variable bounds */
134 SCIP_Longint activitytag; /**< tag of variable bounds for which activity is valid */
135
136 /* curvature information */
137 SCIP_EXPRCURV curvature; /**< curvature of the expression w.r.t. bounds that have been used in the last curvature detection */
138
139 /* integrality information */
140 SCIP_Bool isintegral; /**< whether expression value is integral in feasible solutions */
141
142 /* view expression as quadratic */
143 SCIP_QUADEXPR* quaddata; /**< representation of expression as a quadratic, if checked and being quadratic */
144 SCIP_Bool quadchecked; /**< whether it has been checked whether the expression is quadratic */
145};
146
147/** representation of an expression as quadratic */
149{
150 SCIP_Real constant; /**< a constant term */
151
152 int nlinexprs; /**< number of linear terms */
153 SCIP_EXPR** linexprs; /**< expressions of linear terms */
154 SCIP_Real* lincoefs; /**< coefficients of linear terms */
155
156 int nquadexprs; /**< number of expressions in quadratic terms */
157 SCIP_QUADEXPR_QUADTERM* quadexprterms; /**< array with quadratic expression terms */
158
159 int nbilinexprterms; /**< number of bilinear expressions terms */
160 SCIP_QUADEXPR_BILINTERM* bilinexprterms; /**< bilinear expression terms array */
161
162 SCIP_Bool allexprsarevars; /**< whether all arguments (linexprs, quadexprterms[.].expr) are variable expressions */
163
164 SCIP_EXPRCURV curvature; /**< curvature of the quadratic representation of the expression */
165 SCIP_Bool curvaturechecked; /**< whether curvature has been checked */
166
167 /* eigen decomposition information */
168 SCIP_Bool eigeninfostored; /**< whether the eigen information is stored */
169 SCIP_Real* eigenvalues; /**< eigenvalues of the Q matrix: size of nquadexprs */
170 SCIP_Real* eigenvectors; /**< eigenvalues of the Q matrix: size of nquadexprs^2 */
171};
172
173/** a quadratic term associated to an expression */
175{
176 SCIP_EXPR* expr; /**< expression of quadratic term */
177 SCIP_Real lincoef; /**< linear coefficient of expression */
178 SCIP_Real sqrcoef; /**< square coefficient of expression */
179
180 int nadjbilin; /**< number of bilinear terms this expression is involved in */
181 int adjbilinsize; /**< size of adjacent bilinear terms array */
182 int* adjbilin; /**< indices of associated bilinear terms */
183
184 SCIP_EXPR* sqrexpr; /**< expression that was found to be the square of expr, or NULL if no square term (sqrcoef==0) */
185};
186
187/** a single bilinear term coef * expr1 * expr2
188 *
189 * except for temporary reasons, we assume that the index of var1 is smaller than the index of var2
190 */
192{
193 SCIP_EXPR* expr1; /**< first factor of bilinear term */
194 SCIP_EXPR* expr2; /**< second factor of bilinear term */
195 SCIP_Real coef; /**< coefficient of bilinear term */
196 int pos2; /**< position of expr2's quadexprterm in quadexprterms */
197
198 SCIP_EXPR* prodexpr; /**< expression that was found to be the product of expr1 and expr2 */
199};
200
201/** expression iterator */
203{
204 BMS_BLKMEM* blkmem; /**< block memory */
205 SCIP_STAT* stat; /**< dynamic problem statistics */
206
207 SCIP_Bool initialized; /**< whether the iterator has been initialized, that is, is in use */
208 SCIP_EXPRITER_TYPE itertype; /**< type of expression iterator */
209 SCIP_EXPR* curr; /**< current expression of the iterator */
210 int iterindex; /**< index of iterator data in expressions, or -1 if not using iterator data in expressions */
211 SCIP_Longint visitedtag; /**< tag to mark and recognize an expression as visited, or 0 if not avoiding multiple visits */
212
213 /* data for rtopological mode */
214 SCIP_EXPR** dfsexprs; /**< DFS stack */
215 int* dfsnvisited; /**< number of visited children for each expression in the stack */
216 int dfsnexprs; /**< total number of expression in stack */
217 int dfssize; /**< size of DFS stack */
218
219 /* data for BFS mode */
220 SCIP_QUEUE* queue; /**< BFS queue */
221
222 /* data for DFS mode */
223 SCIP_EXPRITER_STAGE dfsstage; /**< current stage */
224 unsigned int stopstages; /**< stages in which to interrupt iterator */
225};
226
227#endif /* SCIP_STRUCT_EXPR_H_ */
static SCIP_RETCODE eval(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRINTDATA *exprintdata, const vector< Type > &x, Type &val)
memory allocation routines
struct BMS_BlkMem BMS_BLKMEM
Definition memory.h:439
SCIP_EXPRITER_TYPE itertype
SCIP_EXPRITER_STAGE dfsstage
SCIP_QUEUE * queue
BMS_BLKMEM * blkmem
SCIP_Bool initialized
SCIP_EXPR ** dfsexprs
SCIP_STAT * stat
SCIP_Longint visitedtag
SCIP_EXPR * curr
unsigned int stopstages
SCIP_Real dot
SCIP_EXPRCURV curvature
SCIP_EXPRDATA * exprdata
SCIP_Real evalvalue
SCIP_DECL_EXPR_OWNERPRINT((*ownerprint))
SCIP_INTERVAL activity
SCIP_EXPRITERDATA iterdata[SCIP_EXPRITER_MAXNACTIVE]
SCIP_Longint difftag
SCIP_EXPRHDLR * exprhdlr
SCIP_EXPR_OWNERDATA * ownerdata
SCIP_DECL_EXPR_OWNEREVALACTIVITY((*ownerevalactivity))
SCIP_Bool quadchecked
SCIP_Longint evaltag
SCIP_Longint activitytag
int childrensize
SCIP_Real derivative
SCIP_EXPR ** children
SCIP_Real bardot
SCIP_QUADEXPR * quaddata
SCIP_DECL_EXPR_OWNERFREE((*ownerfree))
SCIP_Bool isintegral
SCIP_DECL_EXPRESTIMATE((*estimate))
SCIP_DECL_EXPRSIMPLIFY((*simplify))
SCIP_DECL_EXPRCURVATURE((*curvature))
SCIP_Longint nsimplifycalls
Definition struct_expr.h:79
SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff))
SCIP_CLOCK * intevaltime
Definition struct_expr.h:84
SCIP_Longint npropcalls
Definition struct_expr.h:76
SCIP_DECL_EXPRINTEVAL((*inteval))
SCIP_DECL_EXPRFWDIFF((*fwdiff))
SCIP_Longint nestimatecalls
Definition struct_expr.h:74
SCIP_CLOCK * simplifytime
Definition struct_expr.h:86
unsigned int precedence
Definition struct_expr.h:48
SCIP_DECL_EXPRPARSE((*parse))
SCIP_DECL_EXPREVAL((*eval))
SCIP_Longint ncutoffs
Definition struct_expr.h:77
SCIP_DECL_EXPRMONOTONICITY((*monotonicity))
SCIP_DECL_EXPRCOMPARE((*compare))
SCIP_DECL_EXPRPRINT((*print))
unsigned int ncreated
Definition struct_expr.h:73
SCIP_DECL_EXPRCOPYHDLR((*copyhdlr))
SCIP_DECL_EXPRREVERSEPROP((*reverseprop))
SCIP_Longint nsimplified
Definition struct_expr.h:80
SCIP_CLOCK * proptime
Definition struct_expr.h:85
SCIP_Longint ndomreds
Definition struct_expr.h:78
SCIP_DECL_EXPRFREEDATA((*freedata))
SCIP_DECL_EXPRCOPYDATA((*copydata))
SCIP_CLOCK * estimatetime
Definition struct_expr.h:83
SCIP_DECL_EXPRINTEGRALITY((*integrality))
SCIP_Longint nintevalcalls
Definition struct_expr.h:75
SCIP_Longint nbranchscores
Definition struct_expr.h:81
SCIP_DECL_EXPRFREEHDLR((*freehdlr))
SCIP_DECL_EXPRHASH((*hash))
SCIP_DECL_EXPRINITESTIMATES((*initestimates))
SCIP_DECL_EXPRBWDIFF((*bwdiff))
SCIP_EXPRHDLRDATA * data
Definition struct_expr.h:47
SCIP_Bool curvaturechecked
SCIP_QUADEXPR_QUADTERM * quadexprterms
SCIP_Bool eigeninfostored
SCIP_Real * lincoefs
SCIP_EXPR ** linexprs
SCIP_Bool allexprsarevars
SCIP_Real constant
SCIP_EXPRCURV curvature
SCIP_QUADEXPR_BILINTERM * bilinexprterms
SCIP_Real * eigenvalues
SCIP_Real * eigenvectors
type definitions for clocks and timing issues
type and macro definitions related to algebraic expressions
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition type_expr.h:192
struct SCIP_ExprData SCIP_EXPRDATA
Definition type_expr.h:53
#define SCIP_EXPRITER_MAXNACTIVE
Definition type_expr.h:673
struct SCIP_ExprIterData SCIP_EXPRITERDATA
Definition type_expr.h:703
SCIP_EXPRCURV
Definition type_expr.h:58
struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA
Definition type_expr.h:77
SCIP_EXPRITER_TYPE
Definition type_expr.h:697
unsigned int SCIP_EXPRITER_STAGE
Definition type_expr.h:683
type definitions for problem statistics