1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 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   	 */
67   	static
68   	SCIP_DECL_EXPRSIMPLIFY(simplifyVar)
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);
148  	   SCIPfreeBufferArray(scip, &vars);
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  	 */
157  	static
158  	SCIP_DECL_EXPRCOMPARE(compareVar)
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 */
170  	static
171  	SCIP_DECL_EXPRCOPYHDLR(copyhdlrVar)
172  	{  /*lint --e{715}*/
173  	   SCIP_CALL( SCIPincludeExprhdlrVar(scip) );
174  	
175  	   return SCIP_OKAY;
176  	}
177  	
178  	/** expression data copy callback */
179  	static
180  	SCIP_DECL_EXPRCOPYDATA(copydataVar)
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 */
201  	static
202  	SCIP_DECL_EXPRFREEDATA(freedataVar)
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 */
219  	static
220  	SCIP_DECL_EXPRPRINT(printVar)
221  	{  /*lint --e{715}*/
222  	   assert(expr != NULL);
223  	   assert(SCIPgetVarExprVar(expr) != NULL);
224  	
225  	   if( stage == SCIP_EXPRITER_ENTEREXPR )
226  	   {
227  	      SCIPinfoMessage(scip, file, "<%s>", SCIPvarGetName(SCIPgetVarExprVar(expr)));
228  	   }
229  	
230  	   return SCIP_OKAY;
231  	}
232  	
233  	/** expression point evaluation callback */
234  	static
235  	SCIP_DECL_EXPREVAL(evalVar)
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 */
246  	static
247  	SCIP_DECL_EXPRBWDIFF(bwdiffVar)
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 */
254  	static
255  	SCIP_DECL_EXPRFWDIFF(fwdiffVar)
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 */
266  	static
267  	SCIP_DECL_EXPRBWFWDIFF(bwfwdiffVar)
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 */
274  	static
275  	SCIP_DECL_EXPRINTEVAL(intevalVar)
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*/
296  	          infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY,  ub));   /*lint !e666*/
297  	   }
298  	
299  	   return SCIP_OKAY;
300  	}
301  	
302  	/** variable hash callback */
303  	static
304  	SCIP_DECL_EXPRHASH(hashVar)
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 */
323  	static
324  	SCIP_DECL_EXPRCURVATURE(curvatureVar)
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 */
338  	static
339  	SCIP_DECL_EXPRMONOTONICITY(monotonicityVar)
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 */
352  	static
353  	SCIP_DECL_EXPRINTEGRALITY(integralityVar)
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 */
365  	SCIP_RETCODE SCIPincludeExprhdlrVar(
366  	   SCIP*                 scip                /**< SCIP data structure */
367  	   )
368  	{
369  	   SCIP_EXPRHDLR* exprhdlr;
370  	
371  	   SCIP_CALL( SCIPincludeExprhdlr(scip, &exprhdlr, EXPRHDLR_NAME, EXPRHDLR_DESC, EXPRHDLR_PRECEDENCE, evalVar, NULL) );
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 */
390  	SCIP_RETCODE SCIPcreateExprVar(
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 */
404  	   SCIP_CALL( SCIPcaptureVar(scip, var) );
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 */
416  	SCIP_VAR* SCIPgetVarExprVar(
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  	}
426