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   nlhdlr_default.c
26   	 * @ingroup DEFPLUGINS_NLHDLR
27   	 * @brief  default nonlinear handler that calls expression handler methods
28   	 * @author Stefan Vigerske
29   	 */
30   	
31   	#include <string.h>
32   	
33   	#include "scip/nlhdlr_default.h"
34   	#include "scip/pub_nlhdlr.h"
35   	#include "scip/cons_nonlinear.h"
36   	
37   	/* fundamental nonlinear handler properties */
38   	#define NLHDLR_NAME            "default"
39   	#define NLHDLR_DESC            "default handler for expressions"
40   	#define NLHDLR_DETECTPRIORITY  0
41   	#define NLHDLR_ENFOPRIORITY    0
42   	
43   	/** translate from one value of infinity to another
44   	 *
45   	 *  if val is &ge; infty1, then give infty2, else give val
46   	 */
47   	#define infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val))
48   	
49   	#define UNDERESTIMATEUSESACTIVITY 0x1u  /**< whether underestimation uses activity */
50   	#define OVERESTIMATEUSESACTIVITY  0x2u  /**< whether overestimation uses activity */
51   	
52   	/*lint -e666*/
53   	/*lint -e850*/
54   	
55   	/** evaluates an expression w.r.t. the values in the auxiliary variables */
56   	static
57   	SCIP_RETCODE evalExprInAux(
58   	   SCIP*                 scip,               /**< SCIP data structure */
59   	   SCIP_EXPR*            expr,               /**< expression to be evaluated */
60   	   SCIP_Real*            val,                /**< buffer to store value of expression */
61   	   SCIP_SOL*             sol                 /**< solution to be evaluated */
62   	   )
63   	{
64   	   SCIP_Real* childvals;
65   	   SCIP_VAR* childvar;
66   	   int c;
67   	
68   	   assert(scip != NULL);
69   	   assert(expr != NULL);
70   	   assert(val != NULL);
71   	   assert(SCIPexprGetNChildren(expr) > 0);
72   	
73   	   SCIP_CALL( SCIPallocBufferArray(scip, &childvals, SCIPexprGetNChildren(expr)) );
74   	
75   	   for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
76   	   {
77   	      childvar = SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[c]);
78   	      /* there should be an auxiliary variable, because we created them in detect for every child if we said that we will separate;
79   	       * at the moment, EVALAUX should only be called for nlhdlrs that said they will separate
80   	       * if that changes, then we should handle this here, e.g., via *val = SCIPexprGetEvalValue(expr); break;
81   	       */
82   	      assert(childvar != NULL);
83   	
84   	      childvals[c] = SCIPgetSolVal(scip, sol, childvar);
85   	   }
86   	
87   	   SCIP_CALL( SCIPcallExprEval(scip, expr, childvals, val) );
88   	
89   	   SCIPfreeBufferArray(scip, &childvals);
90   	
91   	   return SCIP_OKAY;
92   	}
93   	
94   	/** check whether expression should be handled by the default nlhdlr
95   	 *
96   	 * if no nlhdlr so far provides enforcement or boundtightening for expr, then the default nlhdlr takes over
97   	 */
98   	static
99   	SCIP_DECL_NLHDLRDETECT(nlhdlrDetectDefault)
100  	{ /*lint --e{715}*/
101  	   SCIP_EXPRHDLR* exprhdlr;
102  	   SCIP_Bool estimatebelowusesactivity = FALSE;
103  	   SCIP_Bool estimateaboveusesactivity = FALSE;
104  	   int c;
105  	
106  	   assert(scip != NULL);
107  	   assert(nlhdlr != NULL);
108  	   assert(expr != NULL);
109  	   assert(enforcing != NULL);
110  	   assert(participating != NULL);
111  	   assert(nlhdlrexprdata != NULL);
112  	
113  	   exprhdlr = SCIPexprGetHdlr(expr);
114  	   assert(exprhdlr != NULL);
115  	
116  	   if( (*enforcing & SCIP_NLHDLR_METHOD_ACTIVITY) == 0 )
117  	   {
118  	      /* expr handlers having reverseprop but no inteval is something that we don't support at the moment for simplicity */
119  	      assert(!SCIPexprhdlrHasReverseProp(exprhdlr) || SCIPexprhdlrHasIntEval(exprhdlr));
120  	
121  	      /* participate in inteval and/or reverseprop if that is not yet provided in enforcing and we have inteval */
122  	      if( SCIPexprhdlrHasIntEval(exprhdlr) )
123  	         *participating = SCIP_NLHDLR_METHOD_ACTIVITY;
124  	   }
125  	
126  	   /* participate in sepa if exprhdlr for expr has an estimate callback and sepa below or above is still missing */
127  	   if( ((*enforcing & SCIP_NLHDLR_METHOD_SEPABOTH) != SCIP_NLHDLR_METHOD_SEPABOTH) && SCIPexprhdlrHasEstimate(exprhdlr) )
128  	   {
129  	      /* communicate back that the nlhdlr will provide the separation on the currently missing sides */
130  	      if( (*enforcing & SCIP_NLHDLR_METHOD_SEPABELOW) == 0 )
131  	         *participating |= SCIP_NLHDLR_METHOD_SEPABELOW;
132  	
133  	      if( (*enforcing & SCIP_NLHDLR_METHOD_SEPAABOVE) == 0 )
134  	         *participating |= SCIP_NLHDLR_METHOD_SEPAABOVE;
135  	   }
136  	
137  	   if( !*participating )
138  	      return SCIP_OKAY;
139  	
140  	   /* since this is the default handler, we enforce where we participate */
141  	   *enforcing |= *participating;
142  	
143  	   /* increment activity usage counter and create auxiliary variables if necessary
144  	    * if separating, first guess whether we will use activities in estimate (distinguish under- and overestimation)
145  	    * we assume that the exprhdlr will use activity on all children iff we are estimating on a nonconvex side
146  	    * TODO it would be better to request this information directly from the exprhdlr than inferring it from curvature,
147  	    * but with the currently available exprhdlr that wouldn't make a difference
148  	    */
149  	   if( *participating & SCIP_NLHDLR_METHOD_SEPABOTH )
150  	   {
151  	      SCIP_EXPRCURV* childcurv;
152  	
153  	      /* allocate memory to store the required curvature of the children (though we don't use it) */
154  	      SCIP_CALL( SCIPallocBufferArray(scip, &childcurv, SCIPexprGetNChildren(expr)) );
155  	
156  	      if( *participating & SCIP_NLHDLR_METHOD_SEPABELOW )
157  	      {
158  	         /* check whether the expression is convex */
159  	         SCIP_Bool isconvex;
160  	         SCIP_CALL( SCIPcallExprCurvature(scip, expr, SCIP_EXPRCURV_CONVEX, &isconvex, childcurv) );
161  	         estimatebelowusesactivity = !isconvex;
162  	      }
163  	
164  	      if( *participating & SCIP_NLHDLR_METHOD_SEPAABOVE )
165  	      {
166  	         /* check whether the expression is concave */
167  	         SCIP_Bool isconcave;
168  	         SCIP_CALL( SCIPcallExprCurvature(scip, expr, SCIP_EXPRCURV_CONCAVE, &isconcave, childcurv) );
169  	         estimateaboveusesactivity = !isconcave;
170  	      }
171  	
172  	      /* free memory */
173  	      SCIPfreeBufferArray(scip, &childcurv);
174  	   }
175  	
176  	   /* indicate enforcement methods required in children:
177  	    * - if separating, make sure that (auxiliary) variable will exist
178  	    * - if activity computation, then register activity usage
179  	    * - if estimating on a non-convex side, then indicate activity usage for separation for that side
180  	    */
181  	   for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
182  	   {
183  	      /* todo skip auxvarusage for value-expressions? would then need update in evalExprInAux, too */
184  	      SCIP_CALL( SCIPregisterExprUsageNonlinear(scip, SCIPexprGetChildren(expr)[c],
185  	         *participating & SCIP_NLHDLR_METHOD_SEPABOTH,
186  	         *participating & SCIP_NLHDLR_METHOD_ACTIVITY, estimatebelowusesactivity, estimateaboveusesactivity) );
187  	   }
188  	
189  	   /* remember estimatebelowusesactivity and estimateaboveusesactivity in nlhdlrexprdata */
190  	   *nlhdlrexprdata = (SCIP_NLHDLREXPRDATA*)(size_t)((estimatebelowusesactivity ? UNDERESTIMATEUSESACTIVITY : 0x0u)
191  	      | (estimateaboveusesactivity ? OVERESTIMATEUSESACTIVITY : 0x0u));
192  	
193  	   return SCIP_OKAY;
194  	}
195  	
196  	/** evaluate expression w.r.t. values of auxiliary variables in children */
197  	static
198  	SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalAuxDefault)
199  	{ /*lint --e{715}*/
200  	   assert(expr != NULL);
201  	   assert(auxvalue != NULL);
202  	
203  	   SCIP_CALL( evalExprInAux(scip, expr, auxvalue, sol) );
204  	
205  	   return SCIP_OKAY;
206  	}
207  	
208  	/** initialize LP relaxation by initial estimators */
209  	static
210  	SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaDefault)
211  	{ /*lint --e{715}*/
212  	   SCIP_INTERVAL* childrenbounds;
213  	   SCIP_Real* coefs[SCIP_EXPR_MAXINITESTIMATES];
214  	   SCIP_Real constant[SCIP_EXPR_MAXINITESTIMATES];
215  	   SCIP_VAR* auxvar;
216  	   SCIP_ROWPREP* rowprep;
217  	   int nreturned;
218  	   int i, j;
219  	
220  	   assert(scip != NULL);
221  	   assert(expr != NULL);
222  	   assert(infeasible != NULL);
223  	
224  	   *infeasible = FALSE;
225  	
226  	   if( !SCIPexprhdlrHasInitEstimates(SCIPexprGetHdlr(expr)) )
227  	      return SCIP_OKAY;
228  	
229  	   SCIPdebug( SCIPinfoMessage(scip, NULL, "initsepa exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) );
230  	   SCIPdebug( SCIPprintExpr(scip, expr, NULL) );
231  	   SCIPdebug( SCIPinfoMessage(scip, NULL, "\n") );
232  	
233  	   /* use global bounds of auxvar as global valid bounds for children
234  	    * if at root node (thus local=global) and estimate actually uses bounds, then intersect with (local) activity of expression
235  	    */
236  	   SCIP_CALL( SCIPallocBufferArray(scip, &childrenbounds, SCIPexprGetNChildren(expr)) );
237  	   for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
238  	   {
239  	      auxvar = SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[i]);
240  	      assert(auxvar != NULL);
241  	
242  	      SCIPintervalSetBounds(&childrenbounds[i],
243  	         -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -SCIPvarGetLbGlobal(auxvar)),
244  	          infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY,  SCIPvarGetUbGlobal(auxvar)));
245  	
246  	      if( SCIPgetDepth(scip) == 0 &&
247  	          ((underestimate && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY)) ||
248  	           (overestimate  && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY ))) )
249  	      {
250  	         SCIP_CALL( SCIPevalExprActivity(scip, SCIPexprGetChildren(expr)[i]) );
251  	         SCIPintervalIntersect(&childrenbounds[i], childrenbounds[i], SCIPexprGetActivity(SCIPexprGetChildren(expr)[i]));
252  	      }
253  	
254  	      if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childrenbounds[i]) )
255  	      {
256  	         SCIPdebugMsg(scip, "activity for expression %d (unexpectedly) empty in initsepa\n", i);
257  	         *infeasible = TRUE;
258  	         SCIPfreeBufferArray(scip, &childrenbounds);
259  	         return SCIP_OKAY;
260  	      }
261  	   }
262  	
263  	   /* allocate each coefficients array */
264  	   for( i = 0; i < SCIP_EXPR_MAXINITESTIMATES; ++i )
265  	   {
266  	      SCIP_CALL( SCIPallocBufferArray(scip, &coefs[i], SCIPexprGetNChildren(expr)) );
267  	   }
268  	
269  	   /* create rowprep */
270  	   SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, SCIP_SIDETYPE_RIGHT, FALSE) );
271  	   SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, SCIPexprGetNChildren(expr)+1) );
272  	
273  	   /* call the separation initialization callback of the expression handler and turn estimates into SCIP rows */
274  	   for( i = 0; i < 2 && !*infeasible; ++i )
275  	   {
276  	      nreturned = 0;
277  	      if( i == 0 && underestimate )
278  	      {
279  	         SCIP_CALL( SCIPcallExprInitestimates(scip, expr, childrenbounds, FALSE, coefs, constant, &nreturned) );
280  	         assert(SCIProwprepGetSidetype(rowprep) == SCIP_SIDETYPE_RIGHT);
281  	      }
282  	      if( i == 1 && overestimate )
283  	      {
284  	         SCIP_CALL( SCIPcallExprInitestimates(scip, expr, childrenbounds, TRUE, coefs, constant, &nreturned) );
285  	         SCIProwprepSetSidetype(rowprep, SCIP_SIDETYPE_LEFT);
286  	      }
287  	
288  	      for( j = 0; j < nreturned && !*infeasible; ++j )
289  	      {
290  	         SCIP_Bool success;
291  	         int v;
292  	
293  	         SCIProwprepReset(rowprep);
294  	
295  	         for( v = 0; v < SCIPexprGetNChildren(expr); ++v )
296  	         {
297  	            SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[v]), coefs[j][v]) );
298  	         }
299  	         SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(expr), -1.0) );
300  	         SCIProwprepAddConstant(rowprep, constant[j]);  /*lint !e644*/
301  	
302  	         /* special treatment for sums to get equality rows */
303  	         if( j == 0 && SCIPisExprSum(scip, expr) )
304  	         {
305  	            SCIP_Real scalefactor;
306  	            SCIP_ROW* row;
307  	
308  	            /* improve numerics by scaling only (does not relax inequality) */
309  	            scalefactor = SCIPscaleupRowprep(scip, rowprep, 1.0, &success);
310  	            if( success && scalefactor == 1.0 && underestimate && overestimate )
311  	            {
312  	               /* if the rowprep didn't have to be changed, then turn it into a row, change this to an equality, and add it to the LP */
313  	               /* TODO do this also if not actually needing both under- and overestimator (should still be valid, but also stronger?) */
314  	               (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "initestimate_sum%d", j);
315  	
316  	               SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) );
317  	
318  	               /* since we did not relax the estimator, we can turn the row into an equality */
319  	               if( SCIPisInfinity(scip, SCIProwGetRhs(row)) )
320  	               {
321  	                  SCIP_CALL( SCIPchgRowRhs(scip, row, SCIProwGetLhs(row)) );
322  	               }
323  	               else
324  	               {
325  	                  SCIP_CALL( SCIPchgRowLhs(scip, row, SCIProwGetRhs(row)) );
326  	               }
327  	               SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
328  	
329  	               SCIPdebug( SCIPinfoMessage(scip, NULL, "  added %scut ", *infeasible ? "infeasible " : "") );
330  	               SCIPdebug( SCIPprintRow(scip, row, NULL) );
331  	
332  	               SCIP_CALL( SCIPreleaseRow(scip, &row) );
333  	
334  	               i = 2;  /* to break outside loop on i, too */
335  	               break;
336  	            }
337  	         }
338  	
339  	         /* straighten out numerics */
340  	         SCIP_CALL( SCIPcleanupRowprep2(scip, rowprep, NULL, SCIPgetHugeValue(scip), &success) );
341  	
342  	         /* if cleanup removed all but one variable, then the cut is essentially a bound; we can skip this and rely on boundtightening */
343  	         if( success && SCIProwprepGetNVars(rowprep) > 1 )
344  	         {
345  	            /* add the cut */
346  	            SCIP_ROW* row;
347  	
348  	            (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "init%sestimate%d_%s",
349  	                  i == 0 ? "under" : "over", j, SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)));
350  	
351  	            SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) );
352  	            SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
353  	
354  	            SCIPdebug( SCIPinfoMessage(scip, NULL, "  added %scut ", *infeasible ? "infeasible " : "") );
355  	            SCIPdebug( SCIPprintRow(scip, row, NULL) );
356  	
357  	            SCIP_CALL( SCIPreleaseRow(scip, &row) );
358  	         }
359  	      }
360  	   }
361  	
362  	   SCIPfreeRowprep(scip, &rowprep);
363  	
364  	   for( i = SCIP_EXPR_MAXINITESTIMATES-1; i >= 0; --i )
365  	   {
366  	      SCIPfreeBufferArray(scip, &coefs[i]);
367  	   }
368  	
369  	   SCIPfreeBufferArray(scip, &childrenbounds);
370  	
371  	   return SCIP_OKAY;
372  	}
373  	
374  	/** compute linear estimator */
375  	static
376  	SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateDefault)
377  	{ /*lint --e{715}*/
378  	   SCIP_Real constant;
379  	   SCIP_Bool local;
380  	   SCIP_Bool* branchcand = NULL;
381  	   int nchildren;
382  	   int c;
383  	   SCIP_INTERVAL* localbounds;
384  	   SCIP_INTERVAL* globalbounds;
385  	   SCIP_Real* refpoint;
386  	   SCIP_ROWPREP* rowprep;
387  	   SCIP_VAR* auxvar;
388  	
389  	   assert(scip != NULL);
390  	   assert(expr != NULL);
391  	   assert(rowpreps != NULL);
392  	   assert(success != NULL);
393  	
394  	   *addedbranchscores = FALSE;
395  	
396  	   nchildren = SCIPexprGetNChildren(expr);
397  	
398  	   SCIP_CALL( SCIPallocBufferArray(scip, &localbounds, nchildren) );
399  	   SCIP_CALL( SCIPallocBufferArray(scip, &globalbounds, nchildren) );
400  	   SCIP_CALL( SCIPallocBufferArray(scip, &refpoint, nchildren) );
401  	   /* we need to pass a branchcand array to exprhdlr's estimate also if not asked to add branching scores */
402  	   SCIP_CALL( SCIPallocBufferArray(scip, &branchcand, nchildren) );
403  	
404  	   SCIPdebug( SCIPinfoMessage(scip, NULL, "estimate exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) );
405  	   SCIPdebug( SCIPprintExpr(scip, expr, NULL) );
406  	   SCIPdebug( SCIPinfoMessage(scip, NULL, "\n") );
407  	
408  	   for( c = 0; c < nchildren; ++c )
409  	   {
410  	      auxvar = SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[c]);
411  	      assert(auxvar != NULL);
412  	
413  	      SCIPintervalSetBounds(&localbounds[c],
414  	         -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -SCIPvarGetLbLocal(auxvar)),
415  	          infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY,  SCIPvarGetUbLocal(auxvar)));
416  	
417  	      if( ((size_t)nlhdlrexprdata & (overestimate ? OVERESTIMATEUSESACTIVITY : UNDERESTIMATEUSESACTIVITY)) )
418  	      {
419  	         /* if expr estimate uses bounds, then intersect the auxvar bounds with the current activity, in case the latter is a bit tighter */
420  	         SCIP_CALL( SCIPevalExprActivity(scip, SCIPexprGetChildren(expr)[c]) );
421  	         SCIPintervalIntersectEps(&localbounds[c], SCIPepsilon(scip), localbounds[c], SCIPexprGetActivity(SCIPexprGetChildren(expr)[c]));
422  	
423  	         if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, localbounds[c]) )
424  	         {
425  	            *success = FALSE;
426  	            goto TERMINATE;
427  	         }
428  	      }
429  	      else
430  	      {
431  	         /* if we think that expr estimate wouldn't use bounds, then just set something valid */
432  	      }
433  	
434  	      SCIPintervalSetBounds(&globalbounds[c],
435  	         -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -SCIPvarGetLbGlobal(auxvar)),
436  	          infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY,  SCIPvarGetUbGlobal(auxvar)));
437  	
438  	      refpoint[c] = SCIPgetSolVal(scip, sol, auxvar);
439  	
440  	      branchcand[c] = TRUE;
441  	   }
442  	
443  	   SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, overestimate ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, TRUE) );
444  	
445  	   /* make sure enough space is available in rowprep arrays */
446  	   SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nchildren) );
447  	
448  	   /* call the estimation callback of the expression handler */
449  	   SCIP_CALL( SCIPcallExprEstimate(scip, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue,
450  	         SCIProwprepGetCoefs(rowprep), &constant, &local, success, branchcand) );
451  	
452  	   if( *success )
453  	   {
454  	      int i;
455  	
456  	      SCIProwprepSetLocal(rowprep, local);
457  	
458  	      /* add variables to rowprep (coefs were already added by SCIPexprhdlrEstimateExpr) */
459  	      for( i = 0; i < nchildren; ++i )
460  	      {
461  	         SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[i]),
462  	               SCIProwprepGetCoefs(rowprep)[i]) );
463  	      }
464  	
465  	      SCIProwprepAddConstant(rowprep, constant);
466  	
467  	      SCIPdebug( SCIPinfoMessage(scip, NULL, "  found rowprep ") );
468  	      SCIPdebug( SCIPprintRowprepSol(scip, rowprep, sol, NULL) );
469  	
470  	      SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, 0, rowprep) );
471  	
472  	      (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_%s%p_%s%" SCIP_LONGINT_FORMAT,
473  	         overestimate ? "over" : "under",
474  	         SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)),
475  	         (void*)expr,
476  	         sol != NULL ? "sol" : "lp",
477  	         sol != NULL ? (SCIP_Longint) SCIPsolGetIndex(sol) : SCIPgetNLPs(scip));
478  	   }
479  	   else
480  	   {
481  	      SCIPfreeRowprep(scip, &rowprep);
482  	   }
483  	
484  	   if( addbranchscores )
485  	   {
486  	      SCIP_Real violation;
487  	
488  	#ifndef BRSCORE_ABSVIOL
489  	      SCIP_CALL( SCIPgetExprRelAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
490  	#else
491  	      SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
492  	#endif
493  	      assert(violation > 0.0);  /* there should be a violation if we were called to enforce */
494  	
495  	      if( nchildren == 1 )
496  	      {
497  	         if( branchcand[0] )
498  	         {
499  	            SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, SCIPexprGetChildren(expr), 1, violation, sol, addedbranchscores) );
500  	         }
501  	      }
502  	      else
503  	      {
504  	         SCIP_EXPR** exprs;
505  	         int nexprs = 0;
506  	
507  	         /* get list of those children that have the branchcand-flag set */
508  	         SCIP_CALL( SCIPallocBufferArray(scip, &exprs, nchildren) );
509  	
510  	         for( c = 0; c < nchildren; ++c )
511  	            if( branchcand[c] )
512  	               exprs[nexprs++] = SCIPexprGetChildren(expr)[c];
513  	
514  	         SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, exprs, nexprs, violation, sol, addedbranchscores) );
515  	
516  	         SCIPfreeBufferArray(scip, &exprs);
517  	      }
518  	
519  	      if( *addedbranchscores )
520  	      {
521  	         /* count this branchscore as belonging to the exprhdlr, too
522  	          * thus, it will be counted for the default nlhdlr, but also for this exprhdlr
523  	          */
524  	         SCIPexprhdlrIncrementNBranchings(SCIPexprGetHdlr(expr));
525  	      }
526  	   }
527  	
528  	TERMINATE:
529  	   SCIPfreeBufferArray(scip, &branchcand);
530  	   SCIPfreeBufferArray(scip, &refpoint);
531  	   SCIPfreeBufferArray(scip, &globalbounds);
532  	   SCIPfreeBufferArray(scip, &localbounds);
533  	
534  	   return SCIP_OKAY;
535  	}
536  	
537  	/** solution linearization callback */
538  	static
539  	SCIP_DECL_NLHDLRSOLLINEARIZE(nlhdlrSollinearizeDefault)
540  	{ /*lint --e{715}*/
541  	   SCIP_Real constant;
542  	   SCIP_Bool local;
543  	   SCIP_Bool* branchcand = NULL;
544  	   int nchildren;
545  	   int c;
546  	   int rnd;
547  	   SCIP_INTERVAL* bounds;
548  	   SCIP_Real* refpoint;
549  	   SCIP_VAR* auxvar;
550  	
551  	   assert(scip != NULL);
552  	   assert(expr != NULL);
553  	
554  	   SCIPdebug( SCIPinfoMessage(scip, NULL, "sollinearize exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) );
555  	   SCIPdebug( SCIPprintExpr(scip, expr, NULL) );
556  	   SCIPdebug( SCIPinfoMessage(scip, NULL, "\n") );
557  	
558  	   nchildren = SCIPexprGetNChildren(expr);
559  	
560  	   if( !overestimate && !underestimate )
561  	      return SCIP_OKAY;
562  	
563  	   /* skip on sum, as the estimator doesn't depend on the reference point (expr is linear in auxvars) */
564  	   if( SCIPisExprSum(scip, expr) )
565  	      return SCIP_OKAY;
566  	
567  	   /* if expr estimate would use bounds, then the function is very likely not convex (w.r.t. global bounds), so skip */
568  	   if( (overestimate && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY)) &&
569  	       (underestimate && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY)) )
570  	      return SCIP_OKAY;
571  	
572  	   SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nchildren) );
573  	   SCIP_CALL( SCIPallocBufferArray(scip, &refpoint, nchildren) );
574  	   /* we need to pass a branchcand array to exprhdlr's estimate also if not asked to add branching scores */
575  	   SCIP_CALL( SCIPallocBufferArray(scip, &branchcand, nchildren) );
576  	
577  	   for( c = 0; c < nchildren; ++c )
578  	   {
579  	      auxvar = SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[c]);
580  	      assert(auxvar != NULL);
581  	
582  	      SCIPintervalSetBounds(&bounds[c],
583  	         -infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY, -SCIPvarGetLbGlobal(auxvar)),
584  	          infty2infty(SCIPinfinity(scip), SCIP_INTERVAL_INFINITY,  SCIPvarGetUbGlobal(auxvar)));
585  	
586  	      refpoint[c] = SCIPgetSolVal(scip, sol, auxvar);
587  	   }
588  	
589  	   for( rnd = (overestimate ? 0 : 1); rnd < (underestimate ? 2 : 1); ++rnd )  /* rnd == 0: overestimate, rnd == 1: underestimate */
590  	   {
591  	      SCIP_ROWPREP* rowprep;
592  	      SCIP_Bool success = FALSE;
593  	
594  	      if( rnd == 0 && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY) )
595  	         continue;
596  	      if( rnd == 1 && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY) )
597  	         continue;
598  	
599  	      SCIP_CALL( SCIPcreateRowprep(scip, &rowprep, rnd == 0 ? SCIP_SIDETYPE_LEFT : SCIP_SIDETYPE_RIGHT, FALSE) );
600  	
601  	      /* make sure enough space is available in rowprep arrays */
602  	      SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nchildren + 1) );
603  	
604  	      for( c = 0; c < nchildren; ++c )
605  	         branchcand[c] = TRUE;
606  	
607  	      /* call the estimation callback of the expression handler
608  	       * since we pass the global bounds as local bounds, too, we can ignore whether resulting estimator is marked as local
609  	       */
610  	      SCIP_CALL( SCIPcallExprEstimate(scip, expr, bounds, bounds, refpoint, rnd == 0,
611  	         rnd == 0 ? SCIPinfinity(scip) : -SCIPinfinity(scip),
612  	         SCIProwprepGetCoefs(rowprep), &constant, &local, &success, branchcand) );
613  	
614  	      if( success )
615  	      {
616  	         int i;
617  	
618  	         /* add variables to rowprep (coefs were already added by SCIPexprhdlrEstimateExpr) */
619  	         for( i = 0; i < nchildren; ++i )
620  	         {
621  	            SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(SCIPexprGetChildren(expr)[i]),
622  	               SCIProwprepGetCoefs(rowprep)[i]) );
623  	         }
624  	
625  	         SCIProwprepAddConstant(rowprep, constant);
626  	
627  	         SCIPdebug( SCIPinfoMessage(scip, NULL, "  found rowprep ") );
628  	         SCIPdebug( SCIPprintRowprepSol(scip, rowprep, sol, NULL) );
629  	
630  	         (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_%s%p_sol%dnotify",
631  	            rnd == 0 ? "over" : "under", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), (void*)expr, SCIPsolGetIndex(sol));
632  	
633  	         /* complete estimator to cut and clean it up */
634  	         SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(expr), -1.0) );
635  	         SCIP_CALL( SCIPcleanupRowprep2(scip, rowprep, sol, SCIPgetHugeValue(scip), &success) );
636  	      }
637  	
638  	      /* if cleanup succeeded and rowprep is still global, add to cutpool */
639  	      if( success && !SCIProwprepIsLocal(rowprep) )
640  	      {
641  	         SCIP_ROW* row;
642  	
643  	         SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) );
644  	         SCIP_CALL( SCIPaddPoolCut(scip, row) );
645  	         SCIP_CALL( SCIPreleaseRow(scip, &row) );
646  	      }
647  	
648  	      SCIPfreeRowprep(scip, &rowprep);
649  	   }
650  	
651  	   SCIPfreeBufferArray(scip, &branchcand);
652  	   SCIPfreeBufferArray(scip, &refpoint);
653  	   SCIPfreeBufferArray(scip, &bounds);
654  	
655  	   return SCIP_OKAY;
656  	}
657  	
658  	/** interval-evaluate expression w.r.t. activity of children */
659  	static
660  	SCIP_DECL_NLHDLRINTEVAL(nlhdlrIntevalDefault)
661  	{ /*lint --e{715}*/
662  	   assert(scip != NULL);
663  	   assert(expr != NULL);
664  	
665  	   /* call the interval evaluation callback of the expression handler */
666  	   SCIP_CALL( SCIPcallExprInteval(scip, expr, interval, intevalvar, intevalvardata) );
667  	
668  	   return SCIP_OKAY;
669  	}
670  	
671  	/** tighten bounds on children from bounds on expression and bounds on children */
672  	static
673  	SCIP_DECL_NLHDLRREVERSEPROP(nlhdlrReversepropDefault)
674  	{ /*lint --e{715}*/
675  	   SCIP_INTERVAL* childrenbounds;
676  	   int c;
677  	
678  	   assert(scip != NULL);
679  	   assert(expr != NULL);
680  	   assert(infeasible != NULL);
681  	   assert(nreductions != NULL);
682  	
683  	   *nreductions = 0;
684  	
685  	   SCIP_CALL( SCIPallocBufferArray(scip, &childrenbounds, SCIPexprGetNChildren(expr)) );
686  	   for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
687  	      childrenbounds[c] = SCIPgetExprBoundsNonlinear(scip, SCIPexprGetChildren(expr)[c]);
688  	
689  	   /* call the reverse propagation callback of the expression handler */
690  	   SCIP_CALL( SCIPcallExprReverseprop(scip, expr, bounds, childrenbounds, infeasible) );
691  	
692  	   if( !*infeasible )
693  	   {
694  	      for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
695  	      {
696  	         SCIP_CALL( SCIPtightenExprIntervalNonlinear(scip, SCIPexprGetChildren(expr)[c], childrenbounds[c],
697  	               infeasible, nreductions) );
698  	      }
699  	      SCIPexprhdlrIncrementNDomainReductions(SCIPexprGetHdlr(expr), *nreductions);
700  	   }
701  	
702  	   SCIPfreeBufferArray(scip, &childrenbounds);
703  	
704  	   return SCIP_OKAY;
705  	}
706  	
707  	/** nonlinear handler copy callback */
708  	static
709  	SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrDefault)
710  	{ /*lint --e{715}*/
711  	   assert(targetscip != NULL);
712  	   assert(sourcenlhdlr != NULL);
713  	   assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), NLHDLR_NAME) == 0);
714  	
715  	   SCIP_CALL( SCIPincludeNlhdlrDefault(targetscip) );
716  	
717  	   return SCIP_OKAY;
718  	}
719  	
720  	/** callback to free expression specific data */
721  	static
722  	SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataDefault)
723  	{  /*lint --e{715}*/
724  	   assert(nlhdlrexprdata != NULL);
725  	
726  	   *nlhdlrexprdata = NULL;
727  	
728  	   return SCIP_OKAY;
729  	}
730  	
731  	/** includes default nonlinear handler in nonlinear constraint handler */
732  	SCIP_RETCODE SCIPincludeNlhdlrDefault(
733  	   SCIP*                 scip                /**< SCIP data structure */
734  	   )
735  	{
736  	   SCIP_NLHDLR* nlhdlr;
737  	
738  	   assert(scip != NULL);
739  	
740  	   SCIP_CALL( SCIPincludeNlhdlrNonlinear(scip, &nlhdlr, NLHDLR_NAME, NLHDLR_DESC, NLHDLR_DETECTPRIORITY,
741  	         NLHDLR_ENFOPRIORITY, nlhdlrDetectDefault, nlhdlrEvalAuxDefault, NULL) );
742  	   assert(nlhdlr != NULL);
743  	
744  	   SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrDefault);
745  	   SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrFreeExprDataDefault);
746  	   SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaDefault, NULL, nlhdlrEstimateDefault, NULL);
747  	   SCIPnlhdlrSetSollinearize(nlhdlr, nlhdlrSollinearizeDefault);
748  	   SCIPnlhdlrSetProp(nlhdlr, nlhdlrIntevalDefault, nlhdlrReversepropDefault);
749  	
750  	   return SCIP_OKAY;
751  	}
752