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 */
43   	struct SCIP_Exprhdlr
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 */
91   	struct 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 */
100  	typedef struct SCIP_QuadExpr  SCIP_QUADEXPR;     /**< representation of expression as quadratic */
101  	typedef struct SCIP_QuadExpr_QuadTerm  SCIP_QUADEXPR_QUADTERM;  /**< a single term associated to a quadratic variable */
102  	typedef struct SCIP_QuadExpr_BilinTerm SCIP_QUADEXPR_BILINTERM; /**< a single bilinear term */
103  	
104  	/** an algebraic expression */
105  	struct SCIP_Expr
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 */
149  	struct SCIP_QuadExpr
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 */
175  	struct SCIP_QuadExpr_QuadTerm
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  	 */
192  	struct SCIP_QuadExpr_BilinTerm
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 */
203  	struct SCIP_ExprIter
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_ */
229