Scippy

SCIP

Solving Constraint Integer Programs

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"
40 #include "blockmemshell/memory.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 */
90 struct 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 */
99 typedef struct SCIP_QuadExpr SCIP_QUADEXPR; /**< representation of expression as quadratic */
100 typedef struct SCIP_QuadExpr_QuadTerm SCIP_QUADEXPR_QUADTERM; /**< a single term associated to a quadratic variable */
101 typedef struct SCIP_QuadExpr_BilinTerm SCIP_QUADEXPR_BILINTERM; /**< a single bilinear term */
102 
103 /** an algebraic expression */
104 struct SCIP_Expr
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)
SCIP_Bool initialized
Definition: struct_expr.h:207
SCIP_Bool allexprsarevars
Definition: struct_expr.h:162
SCIP_EXPRCURV curvature
Definition: struct_expr.h:164
SCIP_DECL_EXPRINITESTIMATES((*initestimates))
SCIP_EXPR_OWNERDATA * ownerdata
Definition: struct_expr.h:117
SCIP_EXPR ** linexprs
Definition: struct_expr.h:153
unsigned int ncreated
Definition: struct_expr.h:73
SCIP_Longint evaltag
Definition: struct_expr.h:127
SCIP_Real constant
Definition: struct_expr.h:150
SCIP_EXPRCURV curvature
Definition: struct_expr.h:137
SCIP_DECL_EXPRFWDIFF((*fwdiff))
BMS_BLKMEM * blkmem
Definition: struct_expr.h:204
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:53
SCIP_Longint nsimplifycalls
Definition: struct_expr.h:79
SCIP_DECL_EXPRINTEVAL((*inteval))
SCIP_EXPRITER_TYPE
Definition: type_expr.h:696
SCIP_Longint nintevalcalls
Definition: struct_expr.h:75
SCIP_DECL_EXPRINTEGRALITY((*integrality))
struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA
Definition: type_expr.h:77
type definitions for problem statistics
unsigned int precedence
Definition: struct_expr.h:48
int nchildren
Definition: struct_expr.h:109
SCIP_DECL_EXPRFREEHDLR((*freehdlr))
SCIP_Bool isintegral
Definition: struct_expr.h:140
#define SCIP_DECL_EXPR_OWNERFREE(x)
Definition: type_expr.h:92
SCIP_DECL_EXPREVAL((*eval))
SCIP_QUADEXPR_QUADTERM * quadexprterms
Definition: struct_expr.h:157
SCIP_DECL_EXPRPARSE((*parse))
int * dfsnvisited
Definition: struct_expr.h:215
SCIP_DECL_EXPRESTIMATE((*estimate))
SCIP_Longint visitedtag
Definition: struct_expr.h:211
SCIP_CLOCK * estimatetime
Definition: struct_expr.h:83
SCIP_DECL_EXPRREVERSEPROP((*reverseprop))
SCIP_CLOCK * simplifytime
Definition: struct_expr.h:86
SCIP_DECL_EXPRPRINT((*print))
SCIP_CLOCK * intevaltime
Definition: struct_expr.h:84
SCIP_INTERVAL activity
Definition: struct_expr.h:133
SCIP_EXPRDATA * exprdata
Definition: struct_expr.h:107
SCIP_Longint npropcalls
Definition: struct_expr.h:76
struct SCIP_ExprIterData SCIP_EXPRITERDATA
Definition: type_expr.h:703
SCIP_Real * lincoefs
Definition: struct_expr.h:154
SCIP_CLOCK * proptime
Definition: struct_expr.h:85
SCIP_EXPRITER_TYPE itertype
Definition: struct_expr.h:208
SCIP_EXPR ** dfsexprs
Definition: struct_expr.h:214
SCIP_Bool eigeninfostored
Definition: struct_expr.h:168
SCIP_DECL_EXPRHASH((*hash))
int childrensize
Definition: struct_expr.h:110
#define SCIP_Bool
Definition: def.h:93
SCIP_Longint nbranchscores
Definition: struct_expr.h:81
SCIP_EXPRCURV
Definition: type_expr.h:57
#define SCIP_DECL_EXPR_OWNEREVALACTIVITY(x)
Definition: type_expr.h:122
SCIP_QUEUE * queue
Definition: struct_expr.h:220
SCIP_Longint nestimatecalls
Definition: struct_expr.h:74
SCIP_EXPRITER_STAGE dfsstage
Definition: struct_expr.h:223
SCIP_EXPR ** children
Definition: struct_expr.h:111
SCIP_EXPR * curr
Definition: struct_expr.h:209
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:192
SCIP_Bool curvaturechecked
Definition: struct_expr.h:165
type definitions for clocks and timing issues
SCIP_Longint difftag
Definition: struct_expr.h:128
SCIP_DECL_EXPRCOPYDATA((*copydata))
SCIP_Longint nsimplified
Definition: struct_expr.h:80
SCIP_Real * eigenvectors
Definition: struct_expr.h:170
#define SCIP_EXPRITER_MAXNACTIVE
Definition: type_expr.h:673
SCIP_DECL_EXPRCURVATURE((*curvature))
#define SCIP_DECL_EXPR_OWNERPRINT(x)
Definition: type_expr.h:106
SCIP_Longint ncutoffs
Definition: struct_expr.h:77
SCIP_DECL_EXPRCOMPARE((*compare))
SCIP_EXPRHDLR * exprhdlr
Definition: struct_expr.h:106
SCIP_DECL_EXPRCOPYHDLR((*copyhdlr))
SCIP_QUADEXPR_BILINTERM * bilinexprterms
Definition: struct_expr.h:160
type and macro definitions related to algebraic expressions
SCIP_Real * eigenvalues
Definition: struct_expr.h:169
SCIP_STAT * stat
Definition: struct_expr.h:205
#define SCIP_Real
Definition: def.h:186
SCIP_DECL_EXPRFREEDATA((*freedata))
SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff))
SCIP_Real derivative
Definition: struct_expr.h:124
#define SCIP_Longint
Definition: def.h:171
SCIP_DECL_EXPRMONOTONICITY((*monotonicity))
SCIP_Longint ndomreds
Definition: struct_expr.h:78
unsigned int stopstages
Definition: struct_expr.h:224
SCIP_Real evalvalue
Definition: struct_expr.h:123
SCIP_Real bardot
Definition: struct_expr.h:126
SCIP_QUADEXPR * quaddata
Definition: struct_expr.h:143
SCIP_DECL_EXPRBWDIFF((*bwdiff))
unsigned int SCIP_EXPRITER_STAGE
Definition: type_expr.h:683
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:439
SCIP_EXPRHDLRDATA * data
Definition: struct_expr.h:47
SCIP_DECL_EXPRSIMPLIFY((*simplify))
SCIP_Real dot
Definition: struct_expr.h:125
SCIP_Bool quadchecked
Definition: struct_expr.h:144
memory allocation routines
SCIP_Longint activitytag
Definition: struct_expr.h:134