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 i;
68  SCIP_EXPR* sumexpr;
69 
70  assert(expr != NULL);
71  assert(simplifiedexpr != NULL);
72 
73  var = SCIPgetVarExprVar(expr);
74  assert(var != NULL);
75 
76  /* if var is active then there is nothing to simplify */
77  if( SCIPvarIsActive(var) )
78  {
79  *simplifiedexpr = expr;
80  /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
81  SCIPcaptureExpr(*simplifiedexpr);
82  return SCIP_OKAY;
83  }
84 
85  /* var is not active; obtain active representation var = constant + sum coefs_i vars_i */
86  varssize = 5;
87  SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
88  SCIP_CALL( SCIPallocBufferArray(scip, &coefs, varssize) );
89 
90  vars[0] = var;
91  coefs[0] = 1.0;
92  constant = 0.0;
93  nvars = 1;
94  if( !SCIPvarIsOriginal(var) )
95  {
96  int requsize;
97 
98  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, coefs, &nvars, varssize, &constant, &requsize, TRUE) );
99 
100  if( requsize > varssize )
101  {
102  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, requsize) );
103  SCIP_CALL( SCIPreallocBufferArray(scip, &coefs, requsize) );
104  varssize = requsize;
105  SCIP_CALL( SCIPgetProbvarLinearSum(scip, vars, coefs, &nvars, varssize, &constant, &requsize, TRUE) );
106  assert(requsize <= nvars);
107  }
108  }
109 
110  /* create expression for constant + sum coefs_i vars_i */
111  SCIP_CALL( SCIPcreateExprSum(scip, &sumexpr, 0, NULL, NULL, constant, ownercreate, ownercreatedata) );
112 
113  for( i = 0; i < nvars; ++i )
114  {
115  SCIP_EXPR* child;
116 
117  SCIP_CALL( SCIPcreateExprVar(scip, &child, vars[i], ownercreate, ownercreatedata) );
118  SCIP_CALL( SCIPappendExprSumExpr(scip, sumexpr, child, coefs[i]) );
119  SCIP_CALL( SCIPreleaseExpr(scip, &child) );
120  }
121 
122  /* simplify since it might not really be a sum */
123  SCIP_CALL( SCIPcallExprSimplify(scip, sumexpr, simplifiedexpr, ownercreate, ownercreatedata) );
124 
125 #ifdef SCIP_DEBUG
126  SCIPinfoMessage(scip, NULL, "expr_var simplify: <%s> := ", SCIPvarGetName(var));
127  SCIPprintExpr(scip, *simplifiedexpr, NULL);
128  SCIPinfoMessage(scip, NULL, "\n");
129 #endif
130 
131  /* we cannot handle fixings to infinity at the moment (TODO we should) */
132  assert(!SCIPisInfinity(scip, REALABS(constant)));
133 
134  /* release no longer used sumexpr */
135  SCIP_CALL( SCIPreleaseExpr(scip, &sumexpr) );
136 
137  /* free memory */
138  SCIPfreeBufferArray(scip, &coefs);
139  SCIPfreeBufferArray(scip, &vars);
140 
141  return SCIP_OKAY;
142 }
143 
144 /** the order of two variable is given by their indices
145  *
146  * @note this is affected by permutations in the problem
147  */
148 static
150 { /*lint --e{715}*/
151  int index1;
152  int index2;
153 
154  index1 = SCIPvarGetIndex(SCIPgetVarExprVar(expr1));
155  index2 = SCIPvarGetIndex(SCIPgetVarExprVar(expr2));
156 
157  return index1 < index2 ? -1 : index1 == index2 ? 0 : 1;
158 }
159 
160 /** expression handler copy callback */
161 static
163 { /*lint --e{715}*/
165 
166  return SCIP_OKAY;
167 }
168 
169 /** expression data copy callback */
170 static
172 { /*lint --e{715}*/
173  SCIP_VAR* var;
174 
175  assert(targetexprdata != NULL);
176  assert(sourceexpr != NULL);
177 
178  /* copying into a different SCIP should be handled on the SCIPexprCopy() level (via mapexpr) */
179  assert(targetscip == sourcescip);
180 
181  var = SCIPgetVarExprVar(sourceexpr);
182  assert(var != NULL);
183 
184  *targetexprdata = (SCIP_EXPRDATA*)var;
185 
186  SCIP_CALL( SCIPcaptureVar(targetscip, var) );
187 
188  return SCIP_OKAY;
189 }
190 
191 /** expression data free callback */
192 static
194 { /*lint --e{715}*/
195  SCIP_EXPRDATA* exprdata;
196 
197  assert(expr != NULL);
198 
199  exprdata = SCIPexprGetData(expr);
200  assert(exprdata != NULL);
201 
202  SCIP_CALL( SCIPreleaseVar(scip, (SCIP_VAR**)&exprdata) );
203 
204  SCIPexprSetData(expr, NULL);
205 
206  return SCIP_OKAY;
207 }
208 
209 /** expression print callback */
210 static
212 { /*lint --e{715}*/
213  assert(expr != NULL);
214  assert(SCIPgetVarExprVar(expr) != NULL);
215 
216  if( stage == SCIP_EXPRITER_ENTEREXPR )
217  {
218  SCIPinfoMessage(scip, file, "<%s>", SCIPvarGetName(SCIPgetVarExprVar(expr)));
219  }
220 
221  return SCIP_OKAY;
222 }
223 
224 /** expression point evaluation callback */
225 static
227 { /*lint --e{715}*/
228  assert(expr != NULL);
229  assert(SCIPgetVarExprVar(expr) != NULL);
230 
231  *val = SCIPgetSolVal(scip, sol, SCIPgetVarExprVar(expr));
232 
233  return SCIP_OKAY;
234 }
235 
236 /** expression backward derivative evaluation callback */
237 static
239 { /*lint --e{715}*/
240  /* this should never happen because variable expressions do not have children */
241  return SCIP_INVALIDCALL;
242 }
243 
244 /** expression forward derivative evaluation callback */
245 static
247 { /*lint --e{715}*/
248  assert(expr != NULL);
249  assert(SCIPgetVarExprVar(expr) != NULL);
250 
251  *dot = SCIPgetSolVal(scip, direction, SCIPgetVarExprVar(expr));
252 
253  return SCIP_OKAY;
254 }
255 
256 /** expression derivative evaluation callback */
257 static
259 { /*lint --e{715}*/
260  /* this should never happen because variable expressions do not have children */
261  return SCIP_INVALIDCALL;
262 }
263 
264 /** expression interval evaluation callback */
265 static
267 { /*lint --e{715}*/
268  SCIP_VAR* var;
269 
270  assert(expr != NULL);
271 
272  var = SCIPgetVarExprVar(expr);
273  assert(var != NULL);
274 
275  if( intevalvar != NULL )
276  *interval = intevalvar(scip, var, intevalvardata);
277  else
278  {
279  SCIP_Real lb;
280  SCIP_Real ub;
281 
282  lb = SCIPvarGetLbLocal(var);
283  ub = SCIPvarGetUbLocal(var);
284 
285  SCIPintervalSetBounds(interval, /*lint !e666*/
286  -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -lb), /*lint !e666*/
287  infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, ub)); /*lint !e666*/
288  }
289 
290  return SCIP_OKAY;
291 }
292 
293 /** variable hash callback */
294 static
296 { /*lint --e{715}*/
297  SCIP_VAR* var;
298 
299  assert(scip != NULL);
300  assert(expr != NULL);
301  assert(SCIPexprGetNChildren(expr) == 0);
302  assert(hashkey != NULL);
303 
304  var = SCIPgetVarExprVar(expr);
305  assert(var != NULL);
306 
307  *hashkey = EXPRHDLR_HASHKEY;
308  *hashkey ^= SCIPcalcFibHash((SCIP_Real)SCIPvarGetIndex(var));
309 
310  return SCIP_OKAY;
311 }
312 
313 /** expression curvature detection callback */
314 static
316 { /*lint --e{715}*/
317  assert(scip != NULL);
318  assert(expr != NULL);
319  assert(success != NULL);
320  assert(SCIPexprGetNChildren(expr) == 0);
321 
322  /* x -> x is linear, convex, and concave */
323  *success = TRUE;
324 
325  return SCIP_OKAY;
326 }
327 
328 /** expression monotonicity detection callback */
329 static
331 { /*lint --e{715}*/
332  assert(scip != NULL);
333  assert(expr != NULL);
334  assert(result != NULL);
335  assert(SCIPexprGetNChildren(expr) == 0);
336 
337  *result = SCIP_MONOTONE_INC;
338 
339  return SCIP_OKAY;
340 }
341 
342 /** expression integrality detection callback */
343 static
345 { /*lint --e{715}*/
346  assert(scip != NULL);
347  assert(expr != NULL);
348  assert(isintegral != NULL);
349 
350  *isintegral = SCIPvarIsIntegral(SCIPgetVarExprVar(expr));
351 
352  return SCIP_OKAY;
353 }
354 
355 /** creates the handler for variable expression and includes it into SCIP */
357  SCIP* scip /**< SCIP data structure */
358  )
359 {
360  SCIP_EXPRHDLR* exprhdlr;
361 
363  assert(exprhdlr != NULL);
364 
365  SCIPexprhdlrSetCopyFreeHdlr(exprhdlr, copyhdlrVar, NULL);
366  SCIPexprhdlrSetCopyFreeData(exprhdlr, copydataVar, freedataVar);
367  SCIPexprhdlrSetSimplify(exprhdlr, simplifyVar);
368  SCIPexprhdlrSetCompare(exprhdlr, compareVar);
369  SCIPexprhdlrSetPrint(exprhdlr, printVar);
370  SCIPexprhdlrSetIntEval(exprhdlr, intevalVar);
371  SCIPexprhdlrSetHash(exprhdlr, hashVar);
372  SCIPexprhdlrSetDiff(exprhdlr, bwdiffVar, fwdiffVar, bwfwdiffVar);
373  SCIPexprhdlrSetCurvature(exprhdlr, curvatureVar);
374  SCIPexprhdlrSetMonotonicity(exprhdlr, monotonicityVar);
375  SCIPexprhdlrSetIntegrality(exprhdlr, integralityVar);
376 
377  return SCIP_OKAY;
378 }
379 
380 /** creates a variable expression */
382  SCIP* scip, /**< SCIP data structure */
383  SCIP_EXPR** expr, /**< pointer where to store expression */
384  SCIP_VAR* var, /**< variable to be stored */
385  SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
386  void* ownercreatedata /**< data to pass to ownercreate */
387  )
388 {
389  SCIP_EXPRDATA* exprdata;
390 
391  assert(expr != NULL);
392  assert(var != NULL);
393 
394  /* capture the variable so that it doesn't disappear while the expr still points to it */
395  SCIP_CALL( SCIPcaptureVar(scip, var) );
396 
397  exprdata = (SCIP_EXPRDATA*)var;
398 
399  SCIP_CALL( SCIPcreateExpr(scip, expr, SCIPgetExprhdlrVar(scip), exprdata, 0, NULL, ownercreate, ownercreatedata) );
400 
401  return SCIP_OKAY;
402 }
403 
404 /* from pub_expr.h */
405 
406 /** gets the variable of a variable expression */
408  SCIP_EXPR* expr /**< variable expression */
409  )
410 {
411  assert(expr != NULL);
412  assert(strcmp(SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), EXPRHDLR_NAME) == 0);
413  assert(SCIPexprGetData(expr) != NULL);
414 
415  return (SCIP_VAR*)SCIPexprGetData(expr);
416 }
static SCIP_DECL_EXPRCOPYDATA(copydataVar)
Definition: expr_var.c:171
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:193
static SCIP_DECL_EXPRINTEVAL(intevalVar)
Definition: expr_var.c:266
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17966
static SCIP_DECL_EXPRCURVATURE(curvatureVar)
Definition: expr_var.c:315
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1245
static SCIP_DECL_EXPRHASH(hashVar)
Definition: expr_var.c:295
struct SCIP_ExprData SCIP_EXPRDATA
Definition: type_expr.h:44
SCIP_Real SCIPinfinity(SCIP *scip)
static SCIP_DECL_EXPRMONOTONICITY(monotonicityVar)
Definition: expr_var.c:330
#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:381
#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:407
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:211
#define SCIP_CALL(x)
Definition: def.h:384
static SCIP_DECL_EXPRBWFWDIFF(bwfwdiffVar)
Definition: expr_var.c:258
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
SCIP_Bool SCIPvarIsOriginal(SCIP_VAR *var)
Definition: var.c:17380
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:115
static SCIP_DECL_EXPRFWDIFF(fwdiffVar)
Definition: expr_var.c:246
#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:356
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:226
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:344
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:238
#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:162
static SCIP_DECL_EXPRCOMPARE(compareVar)
Definition: expr_var.c:149
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