Scippy

SCIP

Solving Constraint Integer Programs

expr_var.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-2022 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 expr_var.c
17  * @ingroup DEFPLUGINS_EXPR
18  * @brief variable expression handler
19  * @author Stefan Vigerske
20  * @author Benjamin Mueller
21  * @author Felipe Serrano
22  */
23 
24 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
25 
26 #include <string.h>
27 #include "scip/expr_var.h"
28 #include "scip/expr_sum.h"
29 
30 #ifdef NDEBUG
31 #undef SCIPgetVarExprVar
32 #endif
33 
34 #define EXPRHDLR_NAME "var"
35 #define EXPRHDLR_DESC "SCIP variable expression"
36 #define EXPRHDLR_PRECEDENCE 0
37 #define EXPRHDLR_HASHKEY SCIPcalcFibHash(22153.0)
38 
39 /** translate from one value of infinity to another
40  *
41  * if val is >= infty1, then give infty2, else give val
42  */
43 #define infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val))
44 
45 
46 /** simplifies a variable expression
47  *
48  * We replace the variable when fixed by its value.
49  * If a variable is fixed, (multi)aggregated or more generally, inactive, we replace it with its active counterpart
50  *
51  * Implementation note:
52  * - we follow the general approach of the simplify, where we replace the var expression for its
53  * simplified expression only in the current parent. So if we see that there is any performance issue in the simplify
54  * we might have to revisit this decision.
55  * - we build the sum expression by appending variable expressions one at a time. This may be
56  * speed-up if we allocate memory for all the variable expressions and build the sum directly.
57  */
58 static
60 { /*lint --e{715}*/
61  SCIP_VAR* var;
62  SCIP_VAR** vars;
63  SCIP_Real* coefs;
64  SCIP_Real constant;
65  int nvars;
66  int varssize;
67  int requsize;
68  int i;
69  SCIP_EXPR* sumexpr;
70 
71  assert(expr != NULL);
72  assert(simplifiedexpr != NULL);
73 
74  var = SCIPgetVarExprVar(expr);
75  assert(var != NULL);
76 
77  /* if var is active then there is nothing to simplify */
78  if( SCIPvarIsActive(var) )
79  {
80  *simplifiedexpr = expr;
81  /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
82  SCIPcaptureExpr(*simplifiedexpr);
83  return SCIP_OKAY;
84  }
85 
86  /* var is not active; obtain active representation var = constant + sum coefs_i vars_i */
87  varssize = 5;
88  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
89  SCIP_CALL( SCIPallocBufferArray(scip, &coefs, varssize) );
90 
91  vars[0] = var;
92  coefs[0] = 1.0;
93  constant = 0.0;
94  nvars = 1;
95  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, coefs, &nvars, varssize, &constant, &requsize, TRUE) );
96 
97  if( requsize > varssize )
98  {
99  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requsize) );
100  SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, requsize) );
101  varssize = requsize;
102  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, coefs, &nvars, varssize, &constant, &requsize, TRUE) );
103  assert(requsize <= nvars);
104  }
105 
106  /* create expression for constant + sum coefs_i vars_i */
107  SCIP_CALL( SCIPcreateExprSum(scip, &sumexpr, 0, NULL, NULL, constant, ownercreate, ownercreatedata) );
108 
109  for( i = 0; i < nvars; ++i )
110  {
111  SCIP_EXPR* child;
112 
113  SCIP_CALL( SCIPcreateExprVar(scip, &child, vars[i], ownercreate, ownercreatedata) );
114  SCIP_CALL( SCIPappendExprSumExpr(scip, sumexpr, child, coefs[i]) );
115  SCIP_CALL( SCIPreleaseExpr(scip, &child) );
116  }
117 
118  /* simplify since it might not really be a sum */
119  SCIP_CALL( SCIPcallExprSimplify(scip, sumexpr, simplifiedexpr, ownercreate, ownercreatedata) );
120 
121 #ifdef SCIP_DEBUG
122  SCIPinfoMessage(scip, NULL, "expr_var simplify: <%s> := ", SCIPvarGetName(var));
123  SCIPprintExpr(scip, *simplifiedexpr, NULL);
124  SCIPinfoMessage(scip, NULL, "\n");
125 #endif
126 
127  /* we cannot handle fixings to infinity at the moment (TODO we should) */
128  assert(!SCIPisInfinity(scip, REALABS(constant)));
129 
130  /* release no longer used sumexpr */
131  SCIP_CALL( SCIPreleaseExpr(scip, &sumexpr) );
132 
133  /* free memory */
134  SCIPfreeBufferArray(scip, &coefs);
135  SCIPfreeBufferArray(scip, &vars);
136 
137  return SCIP_OKAY;
138 }
139 
140 /** the order of two variable is given by their indices
141  *
142  * @note this is affected by permutations in the problem
143  */
144 static
146 { /*lint --e{715}*/
147  int index1;
148  int index2;
149 
150  index1 = SCIPvarGetIndex(SCIPgetVarExprVar(expr1));
151  index2 = SCIPvarGetIndex(SCIPgetVarExprVar(expr2));
152 
153  return index1 < index2 ? -1 : index1 == index2 ? 0 : 1;
154 }
155 
156 /** expression handler copy callback */
157 static
159 { /*lint --e{715}*/
161 
162  return SCIP_OKAY;
163 }
164 
165 /** expression data copy callback */
166 static
168 { /*lint --e{715}*/
169  SCIP_VAR* var;
170 
171  assert(targetexprdata != NULL);
172  assert(sourceexpr != NULL);
173 
174  /* copying into a different SCIP should be handled on the SCIPexprCopy() level (via mapexpr) */
175  assert(targetscip == sourcescip);
176 
177  var = SCIPgetVarExprVar(sourceexpr);
178  assert(var != NULL);
179 
180  *targetexprdata = (SCIP_EXPRDATA*)var;
181 
182  SCIP_CALL( SCIPcaptureVar(targetscip, var) );
183 
184  return SCIP_OKAY;
185 }
186 
187 /** expression data free callback */
188 static
190 { /*lint --e{715}*/
191  SCIP_EXPRDATA* exprdata;
192 
193  assert(expr != NULL);
194 
195  exprdata = SCIPexprGetData(expr);
196  assert(exprdata != NULL);
197 
198  SCIP_CALL( SCIPreleaseVar(scip, (SCIP_VAR**)&exprdata) );
199 
200  SCIPexprSetData(expr, NULL);
201 
202  return SCIP_OKAY;
203 }
204 
205 /** expression print callback */
206 static
208 { /*lint --e{715}*/
209  assert(expr != NULL);
210  assert(SCIPgetVarExprVar(expr) != NULL);
211 
212  if( stage == SCIP_EXPRITER_ENTEREXPR )
213  {
214  SCIPinfoMessage(scip, file, "<%s>", SCIPvarGetName(SCIPgetVarExprVar(expr)));
215  }
216 
217  return SCIP_OKAY;
218 }
219 
220 /** expression point evaluation callback */
221 static
223 { /*lint --e{715}*/
224  assert(expr != NULL);
225  assert(SCIPgetVarExprVar(expr) != NULL);
226 
227  *val = SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr));
228 
229  return SCIP_OKAY;
230 }
231 
232 /** expression backward derivative evaluation callback */
233 static
235 { /*lint --e{715}*/
236  /* this should never happen because variable expressions do not have children */
237  return SCIP_INVALIDCALL;
238 }
239 
240 /** expression forward derivative evaluation callback */
241 static
243 { /*lint --e{715}*/
244  assert(expr != NULL);
245  assert(SCIPgetVarExprVar(expr) != NULL);
246 
247  *dot = SCIPgetSolVal(scip, direction, SCIPgetVarExprVar(expr));
248 
249  return SCIP_OKAY;
250 }
251 
252 /** expression derivative evaluation callback */
253 static
255 { /*lint --e{715}*/
256  /* this should never happen because variable expressions do not have children */
257  return SCIP_INVALIDCALL;
258 }
259 
260 /** expression interval evaluation callback */
261 static
263 { /*lint --e{715}*/
264  SCIP_VAR* var;
265 
266  assert(expr != NULL);
267 
268  var = SCIPgetVarExprVar(expr);
269  assert(var != NULL);
270 
271  if( intevalvar != NULL )
272  *interval = intevalvar(scip, var, intevalvardata);
273  else
274  {
275  SCIP_Real lb;
276  SCIP_Real ub;
277 
278  lb = SCIPvarGetLbLocal(var);
279  ub = SCIPvarGetUbLocal(var);
280 
281  SCIPintervalSetBounds(interval, /*lint !e666*/
282  -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -lb), /*lint !e666*/
283  infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, ub)); /*lint !e666*/
284  }
285 
286  return SCIP_OKAY;
287 }
288 
289 /** variable hash callback */
290 static
292 { /*lint --e{715}*/
293  SCIP_VAR* var;
294 
295  assert(scip != NULL);
296  assert(expr != NULL);
297  assert(SCIPexprGetNChildren(expr) == 0);
298  assert(hashkey != NULL);
299 
300  var = SCIPgetVarExprVar(expr);
301  assert(var != NULL);
302 
303  *hashkey = EXPRHDLR_HASHKEY;
304  *hashkey ^= SCIPcalcFibHash((SCIP_Real)SCIPvarGetIndex(var));
305 
306  return SCIP_OKAY;
307 }
308 
309 /** expression curvature detection callback */
310 static
312 { /*lint --e{715}*/
313  assert(scip != NULL);
314  assert(expr != NULL);
315  assert(success != NULL);
316  assert(SCIPexprGetNChildren(expr) == 0);
317 
318  /* x -> x is linear, convex, and concave */
319  *success = TRUE;
320 
321  return SCIP_OKAY;
322 }
323 
324 /** expression monotonicity detection callback */
325 static
327 { /*lint --e{715}*/
328  assert(scip != NULL);
329  assert(expr != NULL);
330  assert(result != NULL);
331  assert(SCIPexprGetNChildren(expr) == 0);
332 
333  *result = SCIP_MONOTONE_INC;
334 
335  return SCIP_OKAY;
336 }
337 
338 /** expression integrality detection callback */
339 static
341 { /*lint --e{715}*/
342  assert(scip != NULL);
343  assert(expr != NULL);
344  assert(isintegral != NULL);
345 
346  *isintegral = SCIPvarIsIntegral(SCIPgetVarExprVar(expr));
347 
348  return SCIP_OKAY;
349 }
350 
351 /** creates the handler for variable expression and includes it into SCIP */
353  SCIP* scip /**< SCIP data structure */
354  )
355 {
356  SCIP_EXPRHDLR* exprhdlr;
357 
359  assert(exprhdlr != NULL);
360 
361  SCIPexprhdlrSetCopyFreeHdlr(exprhdlr, copyhdlrVar, NULL);
362  SCIPexprhdlrSetCopyFreeData(exprhdlr, copydataVar, freedataVar);
363  SCIPexprhdlrSetSimplify(exprhdlr, simplifyVar);
364  SCIPexprhdlrSetCompare(exprhdlr, compareVar);
365  SCIPexprhdlrSetPrint(exprhdlr, printVar);
366  SCIPexprhdlrSetIntEval(exprhdlr, intevalVar);
367  SCIPexprhdlrSetHash(exprhdlr, hashVar);
368  SCIPexprhdlrSetDiff(exprhdlr, bwdiffVar, fwdiffVar, bwfwdiffVar);
369  SCIPexprhdlrSetCurvature(exprhdlr, curvatureVar);
370  SCIPexprhdlrSetMonotonicity(exprhdlr, monotonicityVar);
371  SCIPexprhdlrSetIntegrality(exprhdlr, integralityVar);
372 
373  return SCIP_OKAY;
374 }
375 
376 /** creates a variable expression */
378  SCIP* scip, /**< SCIP data structure */
379  SCIP_EXPR** expr, /**< pointer where to store expression */
380  SCIP_VAR* var, /**< variable to be stored */
381  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
382  void* ownercreatedata /**< data to pass to ownercreate */
383  )
384 {
385  SCIP_EXPRDATA* exprdata;
386 
387  assert(expr != NULL);
388  assert(var != NULL);
389 
390  /* capture the variable so that it doesn't disappear while the expr still points to it */
391  SCIP_CALL( SCIPcaptureVar(scip, var) );
392 
393  exprdata = (SCIP_EXPRDATA*)var;
394 
395  SCIP_CALL( SCIPcreateExpr(scip, expr, SCIPgetExprhdlrVar(scip), exprdata, 0, NULL, ownercreate, ownercreatedata) );
396 
397  return SCIP_OKAY;
398 }
399 
400 /* from pub_expr.h */
401 
402 /** gets the variable of a variable expression */
404  SCIP_EXPR* expr /**< variable expression */
405  )
406 {
407  assert(expr != NULL);
408  assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0);
409  assert(SCIPexprGetData(expr) != NULL);
410 
411  return (SCIP_VAR*)SCIPexprGetData(expr);
412 }
static SCIP_DECL_EXPRCOPYDATA(copydataVar)
Definition: expr_var.c:167
SCIP_EXPRHDLR * SCIPgetExprhdlrVar(SCIP *scip)
Definition: scip_expr.c:871
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1476
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3798
#define EXPRHDLR_NAME
Definition: expr_var.c:34
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)), SCIP_DECL_EXPRBWFWDIFF((*bwfwdiff)))
Definition: expr.c:464
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:525
static SCIP_DECL_EXPRFREEDATA(freedataVar)
Definition: expr_var.c:189
static SCIP_DECL_EXPRINTEVAL(intevalVar)
Definition: expr_var.c:262
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
static SCIP_DECL_EXPRCURVATURE(curvatureVar)
Definition: expr_var.c:311
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
static SCIP_DECL_EXPRHASH(hashVar)
Definition: expr_var.c:291
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:44
SCIP_Real SCIPinfinity(SCIP *scip)
static SCIP_DECL_EXPRMONOTONICITY(monotonicityVar)
Definition: expr_var.c:326
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
#define EXPRHDLR_PRECEDENCE
Definition: expr_var.c:36
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRHASH((*hash)))
Definition: expr.c:442
void SCIPexprhdlrSetIntegrality(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEGRALITY((*integrality)))
Definition: expr.c:431
SCIP_RETCODE SCIPcreateExprVar(SCIP *scip, SCIP_EXPR **expr, SCIP_VAR *var, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_var.c:377
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:127
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1399
variable expression handler
SCIP_RETCODE SCIPappendExprSumExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child, SCIP_Real childcoef)
Definition: expr_sum.c:1107
#define SCIP_EXPRITER_ENTEREXPR
Definition: type_expr.h:667
SCIP_RETCODE SCIPcreateExprSum(SCIP *scip, SCIP_EXPR **expr, int nchildren, SCIP_EXPR **children, SCIP_Real *coefficients, SCIP_Real constant, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_sum.c:1070
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:199
SCIP_EXPRDATA * SCIPexprGetData(SCIP_EXPR *expr)
Definition: expr.c:3831
SCIP_RETCODE SCIPcreateExpr(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, int nchildren, SCIP_EXPR **children, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:964
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:403
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17251
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:201
static SCIP_DECL_EXPRPRINT(printVar)
Definition: expr_var.c:207
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_DECL_EXPRBWFWDIFF(bwfwdiffVar)
Definition: expr_var.c:254
SCIP_RETCODE SCIPgetProbvarLinearSum(SCIP *scip, SCIP_VAR **vars, SCIP_Real *scalars, int *nvars, int varssize, SCIP_Real *constant, int *requiredsize, SCIP_Bool mergemultiples)
Definition: scip_var.c:1735
void SCIPexprhdlrSetCopyFreeHdlr(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)), SCIP_DECL_EXPRFREEHDLR((*freehdlr)))
Definition: expr.c:359
#define SCIP_INTERVAL_INFINITY
Definition: def.h:199
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
static SCIP_DECL_EXPRFWDIFF(fwdiffVar)
Definition: expr_var.c:242
#define infty2infty(infty1, infty2, val)
Definition: expr_var.c:43
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition: type_expr.h:131
SCIP_RETCODE SCIPincludeExprhdlrVar(SCIP *scip)
Definition: expr_var.c:352
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRMONOTONICITY((*monotonicity)))
Definition: expr.c:420
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
#define EXPRHDLR_HASHKEY
Definition: expr_var.c:37
static SCIP_DECL_EXPREVAL(evalVar)
Definition: expr_var.c:222
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3821
void SCIPexprhdlrSetPrint(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRPRINT((*print)))
Definition: expr.c:387
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
void SCIPexprhdlrSetCopyFreeData(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)), SCIP_DECL_EXPRFREEDATA((*freedata)))
Definition: expr.c:372
static SCIP_DECL_EXPRINTEGRALITY(integralityVar)
Definition: expr_var.c:340
void SCIPexprhdlrSetCompare(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOMPARE((*compare)))
Definition: expr.c:453
static SCIP_DECL_EXPRSIMPLIFY(simplifyVar)
Definition: expr_var.c:59
void SCIPexprhdlrSetCurvature(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCURVATURE((*curvature)))
Definition: expr.c:409
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition: expr.c:3846
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1211
#define SCIP_Real
Definition: def.h:177
static SCIP_DECL_EXPRBWDIFF(bwdiffVar)
Definition: expr_var.c:234
#define EXPRHDLR_DESC
Definition: expr_var.c:35
int SCIPvarGetIndex(SCIP_VAR *var)
Definition: var.c:17590
unsigned int SCIPcalcFibHash(SCIP_Real v)
Definition: misc.c:10242
sum expression handler
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17976
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition: scip_expr.c:814
SCIP_Bool SCIPvarIsIntegral(SCIP_VAR *var)
Definition: var.c:17442
static SCIP_DECL_EXPRCOPYHDLR(copyhdlrVar)
Definition: expr_var.c:158
static SCIP_DECL_EXPRCOMPARE(compareVar)
Definition: expr_var.c:145
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1352
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRSIMPLIFY((*simplify)))
Definition: expr.c:490
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINTEVAL((*inteval)))
Definition: expr.c:479
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17580
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:119