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