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