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