Scippy

SCIP

Solving Constraint Integer Programs

scip_expr.c
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-2020 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  */
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 
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  */
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  */
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  */
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
SCIP_RETCODE SCIPexprtreeEvalInt(SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *varvals, SCIP_INTERVAL *val)
Definition: expr.c:8743
SCIP_RETCODE SCIPevalExprtreeSol(SCIP *scip, SCIP_EXPRTREE *tree, SCIP_SOL *sol, SCIP_Real *val)
Definition: scip_expr.c:114
public methods for memory management
#define infinity
Definition: gastrans.c:71
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1484
SCIP_RETCODE SCIPevalExprtreeGlobalBounds(SCIP *scip, SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *val)
Definition: scip_expr.c:169
#define FALSE
Definition: def.h:73
#define TRUE
Definition: def.h:72
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
public methods for problem variables
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:123
public methods for SCIP variables
public methods for numerical tolerances
public methods for expressions, expression trees, expression graphs, and related stuff ...
interval arithmetics for provable bounds
SCIP_RETCODE SCIPcheckStage(SCIP *scip, const char *method, SCIP_Bool init, SCIP_Bool problem, SCIP_Bool transforming, SCIP_Bool transformed, SCIP_Bool initpresolve, SCIP_Bool presolving, SCIP_Bool exitpresolve, SCIP_Bool presolved, SCIP_Bool initsolve, SCIP_Bool solving, SCIP_Bool solved, SCIP_Bool exitsolve, SCIP_Bool freetrans, SCIP_Bool freescip)
Definition: debug.c:2025
public methods for expression handlers
#define NULL
Definition: lpi_spx1.cpp:155
int SCIPexprtreeGetNVars(SCIP_EXPRTREE *tree)
Definition: expr.c:8616
#define SCIP_CALL(x)
Definition: def.h:364
public methods for NLP management
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Real SCIPinfinity(SCIP *scip)
#define infty2infty(infty1, infty2, val)
Definition: scip_expr.c:53
SCIP_EXPORT SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17677
SCIP_RETCODE SCIPgetExprtreeTransformedVars(SCIP *scip, SCIP_EXPRTREE *tree)
Definition: scip_expr.c:75
#define MAX(x, y)
Definition: tclique_def.h:83
methods for debugging
SCIP_VAR ** SCIPexprtreeGetVars(SCIP_EXPRTREE *tree)
Definition: nlp.c:103
SCIP_EXPORT SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17723
SCIP_EXPORT SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17733
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1390
public methods for solutions
SCIP_EXPORT SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17667
public methods for message output
#define SCIP_Real
Definition: def.h:163
SCIP_RETCODE SCIPevalExprtreeLocalBounds(SCIP *scip, SCIP_EXPRTREE *tree, SCIP_Real infinity, SCIP_INTERVAL *val)
Definition: scip_expr.c:234
SCIP_RETCODE SCIPexprtreeEval(SCIP_EXPRTREE *tree, SCIP_Real *varvals, SCIP_Real *val)
Definition: expr.c:8727
memory allocation routines