1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 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 visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file scip_expr.c
17 * @ingroup OTHER_CFILES
18 * @brief public methods for expression handlers
19 * @author Tobias Achterberg
20 * @author Timo Berthold
21 * @author Gerald Gamrath
22 * @author Leona Gottwald
23 * @author Stefan Heinz
24 * @author Gregor Hendel
25 * @author Thorsten Koch
26 * @author Alexander Martin
27 * @author Marc Pfetsch
28 * @author Michael Winkler
29 * @author Kati Wolter
30 *
31 * @todo check all SCIP_STAGE_* switches, and include the new stages TRANSFORMED and INITSOLVE
32 */
33
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35
36 #include "blockmemshell/memory.h"
37 #include "nlpi/pub_expr.h"
38 #include "scip/debug.h"
39 #include "scip/intervalarith.h"
40 #include "scip/pub_message.h"
41 #include "scip/pub_nlp.h"
42 #include "scip/pub_var.h"
43 #include "scip/scip_expr.h"
44 #include "scip/scip_mem.h"
45 #include "scip/scip_numerics.h"
46 #include "scip/scip_sol.h"
47 #include "scip/scip_var.h"
48
49 /** translate from one value of infinity to another
50 *
51 * if val is >= infty1, then give infty2, else give val
52 */
53 #define infty2infty(infty1, infty2, val) (val >= infty1 ? infty2 : val)
54
55 /** replaces array of variables in expression tree by corresponding transformed variables
56 *
57 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
58 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
59 *
60 * @pre This method can be called if @p scip is in one of the following stages:
61 * - \ref SCIP_STAGE_TRANSFORMING
62 * - \ref SCIP_STAGE_TRANSFORMED
63 * - \ref SCIP_STAGE_INITPRESOLVE
64 * - \ref SCIP_STAGE_PRESOLVING
65 * - \ref SCIP_STAGE_EXITPRESOLVE
66 * - \ref SCIP_STAGE_PRESOLVED
67 * - \ref SCIP_STAGE_INITSOLVE
68 * - \ref SCIP_STAGE_SOLVING
69 * - \ref SCIP_STAGE_SOLVED
70 * - \ref SCIP_STAGE_EXITSOLVE
71 * - \ref SCIP_STAGE_FREETRANS
72 *
73 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
74 */
SCIPgetExprtreeTransformedVars(SCIP * scip,SCIP_EXPRTREE * tree)75 SCIP_RETCODE SCIPgetExprtreeTransformedVars(
76 SCIP* scip, /**< SCIP data structure */
77 SCIP_EXPRTREE* tree /**< expression tree */
78 )
79 {
80 assert(scip != NULL);
81 assert(tree != NULL);
82
83 SCIP_CALL( SCIPcheckStage(scip, "SCIPgetExprtreeTransformedVars", FALSE, FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
84
85 if( SCIPexprtreeGetNVars(tree) == 0 )
86 return SCIP_OKAY;
87
88 SCIP_CALL( SCIPgetTransformedVars(scip, SCIPexprtreeGetNVars(tree), SCIPexprtreeGetVars(tree), SCIPexprtreeGetVars(tree)) );
89
90 return SCIP_OKAY;
91 }
92
93 /** evaluates an expression tree for a primal solution or LP solution
94 *
95 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
96 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
97 *
98 * @pre This method can be called if @p scip is in one of the following stages:
99 * - \ref SCIP_STAGE_PROBLEM
100 * - \ref SCIP_STAGE_TRANSFORMING
101 * - \ref SCIP_STAGE_TRANSFORMED
102 * - \ref SCIP_STAGE_INITPRESOLVE
103 * - \ref SCIP_STAGE_PRESOLVING
104 * - \ref SCIP_STAGE_EXITPRESOLVE
105 * - \ref SCIP_STAGE_PRESOLVED
106 * - \ref SCIP_STAGE_INITSOLVE
107 * - \ref SCIP_STAGE_SOLVING
108 * - \ref SCIP_STAGE_SOLVED
109 * - \ref SCIP_STAGE_EXITSOLVE
110 * - \ref SCIP_STAGE_FREETRANS
111 *
112 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
113 */
SCIPevalExprtreeSol(SCIP * scip,SCIP_EXPRTREE * tree,SCIP_SOL * sol,SCIP_Real * val)114 SCIP_RETCODE SCIPevalExprtreeSol(
115 SCIP* scip, /**< SCIP data structure */
116 SCIP_EXPRTREE* tree, /**< expression tree */
117 SCIP_SOL* sol, /**< a solution, or NULL for current LP solution */
118 SCIP_Real* val /**< buffer to store value */
119 )
120 {
121 SCIP_Real* varvals;
122 int nvars;
123
124 assert(scip != NULL);
125 assert(tree != NULL);
126 assert(val != NULL);
127
128 SCIP_CALL( SCIPcheckStage(scip, "SCIPevalExprtreeSol", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
129
130 nvars = SCIPexprtreeGetNVars(tree);
131
132 if( nvars == 0 )
133 {
134 SCIP_CALL( SCIPexprtreeEval(tree, NULL, val) );
135 return SCIP_OKAY;
136 }
137
138 SCIP_CALL( SCIPallocBufferArray(scip, &varvals, nvars) );
139 SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, SCIPexprtreeGetVars(tree), varvals) );
140
141 SCIP_CALL( SCIPexprtreeEval(tree, varvals, val) );
142
143 SCIPfreeBufferArray(scip, &varvals);
144
145 return SCIP_OKAY;
146 }
147
148 /** evaluates an expression tree w.r.t. current global bounds
149 *
150 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
151 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
152 *
153 * @pre This method can be called if @p scip is in one of the following stages:
154 * - \ref SCIP_STAGE_PROBLEM
155 * - \ref SCIP_STAGE_TRANSFORMING
156 * - \ref SCIP_STAGE_TRANSFORMED
157 * - \ref SCIP_STAGE_INITPRESOLVE
158 * - \ref SCIP_STAGE_PRESOLVING
159 * - \ref SCIP_STAGE_EXITPRESOLVE
160 * - \ref SCIP_STAGE_PRESOLVED
161 * - \ref SCIP_STAGE_INITSOLVE
162 * - \ref SCIP_STAGE_SOLVING
163 * - \ref SCIP_STAGE_SOLVED
164 * - \ref SCIP_STAGE_EXITSOLVE
165 * - \ref SCIP_STAGE_FREETRANS
166 *
167 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
168 */
SCIPevalExprtreeGlobalBounds(SCIP * scip,SCIP_EXPRTREE * tree,SCIP_Real infinity,SCIP_INTERVAL * val)169 SCIP_RETCODE SCIPevalExprtreeGlobalBounds(
170 SCIP* scip, /**< SCIP data structure */
171 SCIP_EXPRTREE* tree, /**< expression tree */
172 SCIP_Real infinity, /**< value to use for infinity */
173 SCIP_INTERVAL* val /**< buffer to store result */
174 )
175 {
176 SCIP_INTERVAL* varvals;
177 SCIP_VAR** vars;
178 int nvars;
179 int i;
180
181 assert(scip != NULL);
182 assert(tree != NULL);
183 assert(val != NULL);
184
185 SCIP_CALL( SCIPcheckStage(scip, "SCIPevalExprtreeGlobalBounds", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
186
187 nvars = SCIPexprtreeGetNVars(tree);
188
189 if( nvars == 0 )
190 {
191 SCIP_CALL( SCIPexprtreeEvalInt(tree, infinity, NULL, val) );
192 return SCIP_OKAY;
193 }
194
195 vars = SCIPexprtreeGetVars(tree);
196 assert(vars != NULL);
197
198 SCIP_CALL( SCIPallocBufferArray(scip, &varvals, nvars) );
199 for( i = 0; i < nvars; ++i )
200 {
201 SCIPintervalSetBounds(&varvals[i],
202 -infty2infty(SCIPinfinity(scip), infinity, -SCIPvarGetLbGlobal(vars[i])), /*lint !e666*/
203 infty2infty(SCIPinfinity(scip), infinity, SCIPvarGetUbGlobal(vars[i]))); /*lint !e666*/
204 }
205
206 SCIP_CALL( SCIPexprtreeEvalInt(tree, infinity, varvals, val) );
207
208 SCIPfreeBufferArray(scip, &varvals);
209
210 return SCIP_OKAY;
211 }
212
213 /** evaluates an expression tree w.r.t. current local bounds
214 *
215 * @return \ref SCIP_OKAY is returned if everything worked. Otherwise a suitable error code is passed. See \ref
216 * SCIP_Retcode "SCIP_RETCODE" for a complete list of error codes.
217 *
218 * @pre This method can be called if @p scip is in one of the following stages:
219 * - \ref SCIP_STAGE_PROBLEM
220 * - \ref SCIP_STAGE_TRANSFORMING
221 * - \ref SCIP_STAGE_TRANSFORMED
222 * - \ref SCIP_STAGE_INITPRESOLVE
223 * - \ref SCIP_STAGE_PRESOLVING
224 * - \ref SCIP_STAGE_EXITPRESOLVE
225 * - \ref SCIP_STAGE_PRESOLVED
226 * - \ref SCIP_STAGE_INITSOLVE
227 * - \ref SCIP_STAGE_SOLVING
228 * - \ref SCIP_STAGE_SOLVED
229 * - \ref SCIP_STAGE_EXITSOLVE
230 * - \ref SCIP_STAGE_FREETRANS
231 *
232 * See \ref SCIP_Stage "SCIP_STAGE" for a complete list of all possible solving stages.
233 */
SCIPevalExprtreeLocalBounds(SCIP * scip,SCIP_EXPRTREE * tree,SCIP_Real infinity,SCIP_INTERVAL * val)234 SCIP_RETCODE SCIPevalExprtreeLocalBounds(
235 SCIP* scip, /**< SCIP data structure */
236 SCIP_EXPRTREE* tree, /**< expression tree */
237 SCIP_Real infinity, /**< value to use for infinity */
238 SCIP_INTERVAL* val /**< buffer to store result */
239 )
240 {
241 SCIP_INTERVAL* varvals;
242 SCIP_VAR** vars;
243 int nvars;
244 int i;
245
246 assert(scip != NULL);
247 assert(tree != NULL);
248 assert(val != NULL);
249
250 SCIP_CALL( SCIPcheckStage(scip, "SCIPevalExprtreeLocalBounds", FALSE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE) );
251
252 nvars = SCIPexprtreeGetNVars(tree);
253
254 if( nvars == 0 )
255 {
256 SCIP_CALL( SCIPexprtreeEvalInt(tree, infinity, NULL, val) );
257 return SCIP_OKAY;
258 }
259
260 vars = SCIPexprtreeGetVars(tree);
261 assert(vars != NULL);
262
263 SCIP_CALL( SCIPallocBufferArray(scip, &varvals, nvars) );
264 for( i = 0; i < nvars; ++i )
265 {
266 /* due to numerics, the lower bound on a variable in SCIP can be slightly higher than the upper bound
267 * in this case, we take the most conservative way and switch the bounds
268 * further, we translate SCIP's value for infinity to the users value for infinity
269 */
270 SCIPintervalSetBounds(&varvals[i],
271 -infty2infty(SCIPinfinity(scip), infinity, -MIN(SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i]))), /*lint !e666*/
272 infty2infty(SCIPinfinity(scip), infinity, MAX(SCIPvarGetLbLocal(vars[i]), SCIPvarGetUbLocal(vars[i])))); /*lint !e666*/
273 }
274
275 SCIP_CALL( SCIPexprtreeEvalInt(tree, infinity, varvals, val) );
276
277 SCIPfreeBufferArray(scip, &varvals);
278
279 return SCIP_OKAY;
280 }
281
282 #undef infty2infty
283