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-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 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 SCIP_DECL_EXPRGETSYMDATA((*getsymdata)); /**< symmetry information callback (can be NULL) */
72
73 /* statistics */
74 unsigned int ncreated; /**< number of times expression has been created */
75 SCIP_Longint nestimatecalls; /**< number of times the estimation callback was called */
76 SCIP_Longint nintevalcalls; /**< number of times the interval evaluation callback was called */
77 SCIP_Longint npropcalls; /**< number of times the propagation callback was called */
78 SCIP_Longint ncutoffs; /**< number of cutoffs found so far by this expression handler */
79 SCIP_Longint ndomreds; /**< number of domain reductions found so far by this expression handler */
80 SCIP_Longint nsimplifycalls; /**< number of times the simplification callback was called */
81 SCIP_Longint nsimplified; /**< number of times the simplification callback simplified */
82 SCIP_Longint nbranchscores; /**< number of times branching scores were added by (or for) this expression handler */
83
84 SCIP_CLOCK* estimatetime; /**< time used for estimation */
85 SCIP_CLOCK* intevaltime; /**< time used for interval evaluation */
86 SCIP_CLOCK* proptime; /**< time used for propagation */
87 SCIP_CLOCK* simplifytime; /**< time used for expression simplification */
88};
89
90/** expression iteration data stored in an expression */
91struct SCIP_ExprIterData
92{
93 SCIP_EXPR* parent; /**< parent expression in DFS iteration */
94 int currentchild; /**< child that is currently visited (or will be visited next) by DFS iteration */
95 SCIP_Longint visitedtag; /**< tag to identify whether an expression has been visited already */
96 SCIP_EXPRITER_USERDATA userdata; /**< space for iterator user to store some (temporary) data */
97};
98
99/* private types */
100typedef struct SCIP_QuadExpr SCIP_QUADEXPR; /**< representation of expression as quadratic */
101typedef struct SCIP_QuadExpr_QuadTerm SCIP_QUADEXPR_QUADTERM; /**< a single term associated to a quadratic variable */
102typedef struct SCIP_QuadExpr_BilinTerm SCIP_QUADEXPR_BILINTERM; /**< a single bilinear term */
103
104/** an algebraic expression */
106{
107 SCIP_EXPRHDLR* exprhdlr; /**< expression type (as pointer to its handler) */
108 SCIP_EXPRDATA* exprdata; /**< expression data */
109
110 int nchildren; /**< number of children */
111 int childrensize; /**< length of children array */
112 SCIP_EXPR** children; /**< children expressions */
113
114 int nuses; /**< reference counter */
115 SCIP_EXPRITERDATA iterdata[SCIP_EXPRITER_MAXNACTIVE]; /**< data for expression iterators */
116
117 /* owner data */
118 SCIP_EXPR_OWNERDATA* ownerdata; /**< data stored by owner of expression */
119 SCIP_DECL_EXPR_OWNERFREE((*ownerfree)); /**< callback for freeing ownerdata */
120 SCIP_DECL_EXPR_OWNERPRINT((*ownerprint)); /**< callback for printing ownerdata */
121 SCIP_DECL_EXPR_OWNEREVALACTIVITY((*ownerevalactivity)); /**< callback for evaluating activity */
122
123 /* point-evaluation and differentiation*/
124 SCIP_Real evalvalue; /**< value of expression from last evaluation (corresponding to evaltag) */
125 SCIP_Real derivative; /**< partial derivative of a "root path" w.r.t. this expression (see \ref SCIP_EXPR_DIFF "Differentiation methods") */
126 SCIP_Real dot; /**< directional derivative of this expr (see \ref SCIP_EXPR_DIFF "Differentiation methods") */
127 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") */
128 SCIP_Longint evaltag; /**< tag of point for which the expression has been evaluated last, or 0 */
129 SCIP_Longint difftag; /**< when computing partial derivatives of an expression w.r.t. a variable,
130 * the tag allows us to decide whether the expression depends on the variable;
131 * the tag will be checked in SCIPgetExprPartialDiff() */
132
133 /* interval-evaluation (activity) */
134 SCIP_INTERVAL activity; /**< activity of expression with respect to variable bounds */
135 SCIP_Longint activitytag; /**< tag of variable bounds for which activity is valid */
136
137 /* curvature information */
138 SCIP_EXPRCURV curvature; /**< curvature of the expression w.r.t. bounds that have been used in the last curvature detection */
139
140 /* integrality information */
141 SCIP_Bool isintegral; /**< whether expression value is integral in feasible solutions */
142
143 /* view expression as quadratic */
144 SCIP_QUADEXPR* quaddata; /**< representation of expression as a quadratic, if checked and being quadratic */
145 SCIP_Bool quadchecked; /**< whether it has been checked whether the expression is quadratic */
146};
147
148/** representation of an expression as quadratic */
150{
151 SCIP_Real constant; /**< a constant term */
152
153 int nlinexprs; /**< number of linear terms */
154 SCIP_EXPR** linexprs; /**< expressions of linear terms */
155 SCIP_Real* lincoefs; /**< coefficients of linear terms */
156
157 int nquadexprs; /**< number of expressions in quadratic terms */
158 SCIP_QUADEXPR_QUADTERM* quadexprterms; /**< array with quadratic expression terms */
159
160 int nbilinexprterms; /**< number of bilinear expressions terms */
161 SCIP_QUADEXPR_BILINTERM* bilinexprterms; /**< bilinear expression terms array */
162
163 SCIP_Bool allexprsarevars; /**< whether all arguments (linexprs, quadexprterms[.].expr) are variable expressions */
164
165 SCIP_EXPRCURV curvature; /**< curvature of the quadratic representation of the expression */
166 SCIP_Bool curvaturechecked; /**< whether curvature has been checked */
167
168 /* eigen decomposition information */
169 SCIP_Bool eigeninfostored; /**< whether the eigen information is stored */
170 SCIP_Real* eigenvalues; /**< eigenvalues of the Q matrix: size of nquadexprs */
171 SCIP_Real* eigenvectors; /**< eigenvalues of the Q matrix: size of nquadexprs^2 */
172};
173
174/** a quadratic term associated to an expression */
176{
177 SCIP_EXPR* expr; /**< expression of quadratic term */
178 SCIP_Real lincoef; /**< linear coefficient of expression */
179 SCIP_Real sqrcoef; /**< square coefficient of expression */
180
181 int nadjbilin; /**< number of bilinear terms this expression is involved in */
182 int adjbilinsize; /**< size of adjacent bilinear terms array */
183 int* adjbilin; /**< indices of associated bilinear terms */
184
185 SCIP_EXPR* sqrexpr; /**< expression that was found to be the square of expr, or NULL if no square term (sqrcoef==0) */
186};
187
188/** a single bilinear term coef * expr1 * expr2
189 *
190 * except for temporary reasons, we assume that the index of var1 is smaller than the index of var2
191 */
193{
194 SCIP_EXPR* expr1; /**< first factor of bilinear term */
195 SCIP_EXPR* expr2; /**< second factor of bilinear term */
196 SCIP_Real coef; /**< coefficient of bilinear term */
197 int pos2; /**< position of expr2's quadexprterm in quadexprterms */
198
199 SCIP_EXPR* prodexpr; /**< expression that was found to be the product of expr1 and expr2 */
200};
201
202/** expression iterator */
204{
205 BMS_BLKMEM* blkmem; /**< block memory */
206 SCIP_STAT* stat; /**< dynamic problem statistics */
207
208 SCIP_Bool initialized; /**< whether the iterator has been initialized, that is, is in use */
209 SCIP_EXPRITER_TYPE itertype; /**< type of expression iterator */
210 SCIP_EXPR* curr; /**< current expression of the iterator */
211 int iterindex; /**< index of iterator data in expressions, or -1 if not using iterator data in expressions */
212 SCIP_Longint visitedtag; /**< tag to mark and recognize an expression as visited, or 0 if not avoiding multiple visits */
213
214 /* data for rtopological mode */
215 SCIP_EXPR** dfsexprs; /**< DFS stack */
216 int* dfsnvisited; /**< number of visited children for each expression in the stack */
217 int dfsnexprs; /**< total number of expression in stack */
218 int dfssize; /**< size of DFS stack */
219
220 /* data for BFS mode */
221 SCIP_QUEUE* queue; /**< BFS queue */
222
223 /* data for DFS mode */
224 SCIP_EXPRITER_STAGE dfsstage; /**< current stage */
225 unsigned int stopstages; /**< stages in which to interrupt iterator */
226};
227
228#endif /* SCIP_STRUCT_EXPR_H_ */
#define SCIP_Longint
Definition: def.h:158
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
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:437
int * dfsnvisited
Definition: struct_expr.h:216
SCIP_EXPRITER_TYPE itertype
Definition: struct_expr.h:209
SCIP_EXPRITER_STAGE dfsstage
Definition: struct_expr.h:224
SCIP_QUEUE * queue
Definition: struct_expr.h:221
BMS_BLKMEM * blkmem
Definition: struct_expr.h:205
SCIP_Bool initialized
Definition: struct_expr.h:208
SCIP_EXPR ** dfsexprs
Definition: struct_expr.h:215
SCIP_STAT * stat
Definition: struct_expr.h:206
SCIP_Longint visitedtag
Definition: struct_expr.h:212
SCIP_EXPR * curr
Definition: struct_expr.h:210
unsigned int stopstages
Definition: struct_expr.h:225
SCIP_Real dot
Definition: struct_expr.h:126
SCIP_EXPRCURV curvature
Definition: struct_expr.h:138
SCIP_EXPRDATA * exprdata
Definition: struct_expr.h:108
SCIP_Real evalvalue
Definition: struct_expr.h:124
SCIP_DECL_EXPR_OWNERPRINT((*ownerprint))
SCIP_INTERVAL activity
Definition: struct_expr.h:134
SCIP_EXPRITERDATA iterdata[SCIP_EXPRITER_MAXNACTIVE]
Definition: struct_expr.h:115
SCIP_Longint difftag
Definition: struct_expr.h:129
SCIP_EXPRHDLR * exprhdlr
Definition: struct_expr.h:107
SCIP_EXPR_OWNERDATA * ownerdata
Definition: struct_expr.h:118
SCIP_DECL_EXPR_OWNEREVALACTIVITY((*ownerevalactivity))
SCIP_Bool quadchecked
Definition: struct_expr.h:145
SCIP_Longint evaltag
Definition: struct_expr.h:128
SCIP_Longint activitytag
Definition: struct_expr.h:135
int childrensize
Definition: struct_expr.h:111
SCIP_Real derivative
Definition: struct_expr.h:125
SCIP_EXPR ** children
Definition: struct_expr.h:112
SCIP_Real bardot
Definition: struct_expr.h:127
SCIP_QUADEXPR * quaddata
Definition: struct_expr.h:144
SCIP_DECL_EXPR_OWNERFREE((*ownerfree))
int nchildren
Definition: struct_expr.h:110
SCIP_Bool isintegral
Definition: struct_expr.h:141
SCIP_DECL_EXPRESTIMATE((*estimate))
SCIP_DECL_EXPRSIMPLIFY((*simplify))
SCIP_DECL_EXPRCURVATURE((*curvature))
SCIP_Longint nsimplifycalls
Definition: struct_expr.h:80
SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff))
SCIP_CLOCK * intevaltime
Definition: struct_expr.h:85
SCIP_Longint npropcalls
Definition: struct_expr.h:77
SCIP_DECL_EXPRINTEVAL((*inteval))
SCIP_DECL_EXPRFWDIFF((*fwdiff))
SCIP_Longint nestimatecalls
Definition: struct_expr.h:75
SCIP_CLOCK * simplifytime
Definition: struct_expr.h:87
unsigned int precedence
Definition: struct_expr.h:48
SCIP_DECL_EXPRPARSE((*parse))
SCIP_DECL_EXPREVAL((*eval))
SCIP_Longint ncutoffs
Definition: struct_expr.h:78
SCIP_DECL_EXPRMONOTONICITY((*monotonicity))
SCIP_DECL_EXPRCOMPARE((*compare))
SCIP_DECL_EXPRPRINT((*print))
unsigned int ncreated
Definition: struct_expr.h:74
SCIP_DECL_EXPRCOPYHDLR((*copyhdlr))
SCIP_DECL_EXPRREVERSEPROP((*reverseprop))
SCIP_Longint nsimplified
Definition: struct_expr.h:81
SCIP_CLOCK * proptime
Definition: struct_expr.h:86
SCIP_Longint ndomreds
Definition: struct_expr.h:79
SCIP_DECL_EXPRFREEDATA((*freedata))
SCIP_DECL_EXPRCOPYDATA((*copydata))
SCIP_DECL_EXPRGETSYMDATA((*getsymdata))
SCIP_CLOCK * estimatetime
Definition: struct_expr.h:84
SCIP_DECL_EXPRINTEGRALITY((*integrality))
SCIP_Longint nintevalcalls
Definition: struct_expr.h:76
SCIP_Longint nbranchscores
Definition: struct_expr.h:82
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
Definition: struct_expr.h:166
SCIP_QUADEXPR_QUADTERM * quadexprterms
Definition: struct_expr.h:158
SCIP_Bool eigeninfostored
Definition: struct_expr.h:169
SCIP_Real * lincoefs
Definition: struct_expr.h:155
SCIP_EXPR ** linexprs
Definition: struct_expr.h:154
SCIP_Bool allexprsarevars
Definition: struct_expr.h:163
SCIP_Real constant
Definition: struct_expr.h:151
SCIP_EXPRCURV curvature
Definition: struct_expr.h:165
SCIP_QUADEXPR_BILINTERM * bilinexprterms
Definition: struct_expr.h:161
SCIP_Real * eigenvalues
Definition: struct_expr.h:170
SCIP_Real * eigenvectors
Definition: struct_expr.h:171
type definitions for clocks and timing issues
type and macro definitions related to algebraic expressions
struct SCIP_ExprhdlrData SCIP_EXPRHDLRDATA
Definition: type_expr.h:195
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:54
#define SCIP_EXPRITER_MAXNACTIVE
Definition: type_expr.h:689
struct SCIP_ExprIterData SCIP_EXPRITERDATA
Definition: type_expr.h:719
SCIP_EXPRCURV
Definition: type_expr.h:61
struct SCIP_Expr_OwnerData SCIP_EXPR_OWNERDATA
Definition: type_expr.h:80
SCIP_EXPRITER_TYPE
Definition: type_expr.h:713
unsigned int SCIP_EXPRITER_STAGE
Definition: type_expr.h:699
type definitions for problem statistics