Scippy

SCIP

Solving Constraint Integer Programs

exprinterpret.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-2016 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file exprinterpret.h
17  * @brief methods to interpret (evaluate) an expression tree "fast"
18  * @author Stefan Vigerske
19  * @author Thorsten Gellermann
20  * Realized similar to LPI: one implementation of an interpreter is linked in.
21  */
22 
23 /* @todo product Gradient times vector
24  @todo product Hessian times vector
25  @todo product Hessian of Lagrangian times vector
26  @todo sparse Hessian of expression tree
27  @todo sparse Hessian of Lagrangian (sets of expression trees and quadratic parts)?
28 */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #ifndef __SCIP_EXPRINTERPRET_H__
33 #define __SCIP_EXPRINTERPRET_H__
34 
35 #include "scip/def.h"
36 #include "blockmemshell/memory.h"
37 #include "nlpi/type_expr.h"
39 #include "scip/intervalarith.h"
40 
41 #ifdef __cplusplus
42 extern "C" {
43 #endif
44 
45 /** gets name and version of expression interpreter */
46 extern
47 const char* SCIPexprintGetName(void);
48 
49 /** gets descriptive text of expression interpreter */
50 extern
51 const char* SCIPexprintGetDesc(void);
52 
53 /** gets capabilities of expression interpreter (using bitflags) */
54 extern
56 
57 /** creates an expression interpreter object */
58 extern
60  BMS_BLKMEM* blkmem, /**< block memory data structure */
61  SCIP_EXPRINT** exprint /**< buffer to store pointer to expression interpreter */
62  );
63 
64 /** frees an expression interpreter object */
65 extern
67  SCIP_EXPRINT** exprint /**< expression interpreter that should be freed */
68  );
69 
70 /** compiles an expression tree and stores compiled data in expression tree */
71 extern
73  SCIP_EXPRINT* exprint, /**< interpreter data structure */
74  SCIP_EXPRTREE* tree /**< expression tree */
75  );
76 
77 /** gives the capability to evaluate an expression by the expression interpreter
78  *
79  * In cases of user-given expressions, higher order derivatives may not be available for the user-expression,
80  * even if the expression interpreter could handle these. This method allows to recognize that, e.g., the
81  * Hessian for an expression is not available because it contains a user expression that does not provide
82  * Hessians.
83  */
84 extern
86  SCIP_EXPRINT* exprint, /**< interpreter data structure */
87  SCIP_EXPRTREE* tree /**< expression tree */
88  );
89 
90 /** frees interpreter data */
91 extern
93  SCIP_EXPRINTDATA** interpreterdata /**< interpreter data that should freed */
94  );
95 
96 /** notify expression interpreter that a new parameterization is used
97  * this probably causes retaping by AD algorithms
98  */
99 extern
101  SCIP_EXPRINT* exprint, /**< interpreter data structure */
102  SCIP_EXPRTREE* tree /**< expression tree */
103  );
104 
105 /** evaluates an expression tree */
106 extern
108  SCIP_EXPRINT* exprint, /**< interpreter data structure */
109  SCIP_EXPRTREE* tree, /**< expression tree */
110  SCIP_Real* varvals, /**< values of variables */
111  SCIP_Real* val /**< buffer to store value of expression */
112  );
113 
114 /** evaluates an expression tree on intervals */
115 extern
117  SCIP_EXPRINT* exprint, /**< interpreter data structure */
118  SCIP_EXPRTREE* tree, /**< expression tree */
119  SCIP_Real infinity, /**< value for infinity */
120  SCIP_INTERVAL* varvals, /**< interval values of variables */
121  SCIP_INTERVAL* val /**< buffer to store interval value of expression */
122  );
123 
124 /** computes value and gradient of an expression tree */
125 extern
127  SCIP_EXPRINT* exprint, /**< interpreter data structure */
128  SCIP_EXPRTREE* tree, /**< expression tree */
129  SCIP_Real* varvals, /**< values of variables, can be NULL if new_varvals is FALSE */
130  SCIP_Bool new_varvals, /**< have variable values changed since last call to a point evaluation routine? */
131  SCIP_Real* val, /**< buffer to store expression value */
132  SCIP_Real* gradient /**< buffer to store expression gradient, need to have length at least SCIPexprtreeGetNVars(tree) */
133  );
134 
135 /** computes interval value and interval gradient of an expression tree */
136 extern
138  SCIP_EXPRINT* exprint, /**< interpreter data structure */
139  SCIP_EXPRTREE* tree, /**< expression tree */
140  SCIP_Real infinity, /**< value for infinity */
141  SCIP_INTERVAL* varvals, /**< interval values of variables, can be NULL if new_varvals is FALSE */
142  SCIP_Bool new_varvals, /**< have variable interval values changed since last call to an interval evaluation routine? */
143  SCIP_INTERVAL* val, /**< buffer to store expression interval value */
144  SCIP_INTERVAL* gradient /**< buffer to store expression interval gradient, need to have length at least SCIPexprtreeGetNVars(tree) */
145  );
146 
147 /** gives sparsity pattern of hessian
148  *
149  * NOTE: this function might be replaced later by something nicer.
150  * Since the AD code might need to do a forward sweep, you should pass variable values in here.
151  */
152 extern
154  SCIP_EXPRINT* exprint, /**< interpreter data structure */
155  SCIP_EXPRTREE* tree, /**< expression tree */
156  SCIP_Real* varvals, /**< values of variables */
157  SCIP_Bool* sparsity /**< buffer to store sparsity pattern of Hessian, sparsity[i+n*j] indicates whether entry (i,j) is nonzero in the hessian */
158  );
159 
160 /** computes value and dense hessian of an expression tree
161  *
162  * The full hessian is computed (lower left and upper right triangle).
163  */
164 extern
166  SCIP_EXPRINT* exprint, /**< interpreter data structure */
167  SCIP_EXPRTREE* tree, /**< expression tree */
168  SCIP_Real* varvals, /**< values of variables, can be NULL if new_varvals is FALSE */
169  SCIP_Bool new_varvals, /**< have variable values changed since last call to an evaluation routine? */
170  SCIP_Real* val, /**< buffer to store function value */
171  SCIP_Real* hessian /**< buffer to store hessian values, need to have size at least n*n */
172  );
173 
174 #ifdef __cplusplus
175 }
176 #endif
177 
178 #endif /* __SCIP_EXPRINTERPRET_H__ */
SCIP_RETCODE SCIPexprintNewParametrization(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
SCIP_RETCODE SCIPexprintCompile(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
SCIP_RETCODE SCIPexprintEvalInt(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_INTERVAL *val)
type definitions for expression interpreter
SCIP_RETCODE SCIPexprintFreeData(SCIP_EXPRINTDATA **interpreterdata)
SCIP_EXPRINTCAPABILITY SCIPexprintGetCapability(void)
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
unsigned int SCIP_EXPRINTCAPABILITY
SCIP_RETCODE SCIPexprintCreate(BMS_BLKMEM *blkmem, SCIP_EXPRINT **exprint)
interval arithmetics for provable bounds
SCIP_RETCODE SCIPexprintGradInt(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_Bool new_varvals, SCIP_INTERVAL *val, SCIP_INTERVAL *gradient)
SCIP_RETCODE SCIPexprintHessianDense(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool new_varvals, SCIP_Real *val, SCIP_Real *hessian)
#define SCIP_Bool
Definition: def.h:53
type definitions for expressions and expression trees
#define SCIP_Real
Definition: def.h:127
const char * SCIPexprintGetName(void)
SCIP_RETCODE SCIPexprintHessianSparsityDense(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool *sparsity)
SCIP_EXPRINTCAPABILITY SCIPexprintGetExprtreeCapability(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree)
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:392
const char * SCIPexprintGetDesc(void)
struct SCIP_ExprIntData SCIP_EXPRINTDATA
SCIP_RETCODE SCIPexprintGrad(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Bool new_varvals, SCIP_Real *val, SCIP_Real *gradient)
SCIP_RETCODE SCIPexprintEval(SCIP_EXPRINT *exprint, SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Real *val)
SCIP_RETCODE SCIPexprintFree(SCIP_EXPRINT **exprint)
memory allocation routines