Scippy

SCIP

Solving Constraint Integer Programs

nlhdlr_default.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 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
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  {
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) */
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 */
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;
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 
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  {
240  assert(auxvar != NULL);
241 
242  SCIPintervalSetBounds(&childrenbounds[i],
245 
246  if( SCIPgetDepth(scip) == 0 &&
247  ((underestimate && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY)) ||
248  (overestimate && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY ))) )
249  {
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  {
267  }
268 
269  /* create rowprep */
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) );
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  {
298  }
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  {
411  assert(auxvar != NULL);
412 
413  SCIPintervalSetBounds(&localbounds[c],
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 */
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],
437 
438  refpoint[c] = SCIPgetSolVal(scip, sol, auxvar);
439 
440  branchcand[c] = TRUE;
441  }
442 
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  {
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",
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  */
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  {
580  assert(auxvar != NULL);
581 
582  SCIPintervalSetBounds(&bounds[c],
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 
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  {
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 */
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  {
697  infeasible, nreductions) );
698  }
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 */
733  SCIP* scip /**< SCIP data structure */
734  )
735 {
736  SCIP_NLHDLR* nlhdlr;
737 
738  assert(scip != NULL);
739 
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 }
#define NULL
Definition: def.h:267
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1486
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectDefault)
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1717
#define SCIP_NLHDLR_METHOD_SEPABELOW
Definition: type_nlhdlr.h:51
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3854
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18079
static SCIP_DECL_NLHDLRINTEVAL(nlhdlrIntevalDefault)
#define SCIP_MAXSTRLEN
Definition: def.h:288
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEEXPRDATA((*freeexprdata)))
Definition: nlhdlr.c:98
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:545
SCIP_RETCODE SCIPcleanupRowprep2(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
#define FALSE
Definition: def.h:94
#define UNDERESTIMATEUSESACTIVITY
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:689
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
void SCIPintervalIntersectEps(SCIP_INTERVAL *resultant, SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
#define TRUE
Definition: def.h:93
#define SCIPdebug(x)
Definition: pub_message.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
#define NLHDLR_DESC
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition: expr.c:4010
SCIP_SIDETYPE SCIProwprepGetSidetype(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:669
#define NLHDLR_DETECTPRIORITY
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
Definition: misc_rowprep.c:887
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
static SCIP_DECL_NLHDLRSOLLINEARIZE(nlhdlrSollinearizeDefault)
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrDefault)
static SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaDefault)
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:649
static SCIP_RETCODE evalExprInAux(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *val, SCIP_SOL *sol)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3864
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18089
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:629
SCIP_Bool SCIProwprepIsLocal(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:679
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:166
#define infty2infty(infty1, infty2, val)
SCIP_Real SCIPscaleupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real minscaleup, SCIP_Bool *success)
SCIP_Bool SCIPexprhdlrHasEstimate(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:625
SCIP_RETCODE SCIPincludeNlhdlrNonlinear(SCIP *scip, SCIP_NLHDLR **nlhdlr, const char *name, const char *desc, int detectpriority, int enfopriority, SCIP_DECL_NLHDLRDETECT((*detect)), SCIP_DECL_NLHDLREVALAUX((*evalaux)), SCIP_NLHDLRDATA *nlhdlrdata)
void SCIProwprepSetSidetype(SCIP_ROWPREP *rowprep, SCIP_SIDETYPE sidetype)
Definition: misc_rowprep.c:769
#define NLHDLR_NAME
void SCIProwprepReset(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:719
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1453
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:583
#define SCIP_CALL(x)
Definition: def.h:380
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalAuxDefault)
static SCIP_DECL_NLHDLRREVERSEPROP(nlhdlrReversepropDefault)
SCIP_Bool SCIPexprhdlrHasIntEval(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:615
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
void SCIPnlhdlrSetSollinearize(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRSOLLINEARIZE((*sollinearize)))
Definition: nlhdlr.c:154
#define SCIP_INTERVAL_INFINITY
Definition: def.h:195
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)), SCIP_DECL_NLHDLREXITSEPA((*exitsepa)))
Definition: nlhdlr.c:136
SCIP_RETCODE SCIPcallExprEval(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *val)
Definition: scip_expr.c:2185
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
default nonlinear handler that calls expression handler methods
#define SCIP_Bool
Definition: def.h:91
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1607
#define OVERESTIMATEUSESACTIVITY
SCIP_Bool SCIPexprhdlrHasReverseProp(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:675
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:760
SCIP_EXPRCURV
Definition: type_expr.h:60
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_RETCODE SCIPincludeNlhdlrDefault(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1583
void SCIPnlhdlrSetProp(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINTEVAL((*inteval)), SCIP_DECL_NLHDLRREVERSEPROP((*reverseprop)))
Definition: nlhdlr.c:123
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3877
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPtightenExprIntervalNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_INTERVAL newbounds, SCIP_Bool *cutoff, int *ntightenings)
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
void SCIPprintRowprepSol(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, FILE *file)
Definition: misc_rowprep.c:826
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_Real SCIPgetHugeValue(SCIP *scip)
SCIP_Bool SCIPexprhdlrHasInitEstimates(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:635
void SCIPexprhdlrIncrementNDomainReductions(SCIP_EXPRHDLR *exprhdlr, int nreductions)
Definition: expr.c:771
#define SCIP_NLHDLR_METHOD_ACTIVITY
Definition: type_nlhdlr.h:54
SCIP_RETCODE SCIPgetExprAbsAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
SCIP_RETCODE SCIPaddExprsViolScoreNonlinear(SCIP *scip, SCIP_EXPR **exprs, int nexprs, SCIP_Real violscore, SCIP_SOL *sol, SCIP_Bool *success)
#define SCIP_Real
Definition: def.h:173
#define NLHDLR_ENFOPRIORITY
SCIP_RETCODE SCIPgetExprRelAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
#define SCIP_EXPR_MAXINITESTIMATES
Definition: type_expr.h:198
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
#define SCIP_Longint
Definition: def.h:158
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
Definition: type_nlhdlr.h:443
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: misc_rowprep.c:563
static SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateDefault)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: misc_rowprep.c:913
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
Definition: misc_rowprep.c:780
public functions of nonlinear handlers of nonlinear constraints
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_INTERVAL SCIPgetExprBoundsNonlinear(SCIP *scip, SCIP_EXPR *expr)
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataDefault)
#define SCIP_NLHDLR_METHOD_SEPABOTH
Definition: type_nlhdlr.h:53
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
void SCIPexprhdlrIncrementNBranchings(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:817
#define SCIP_NLHDLR_METHOD_SEPAABOVE
Definition: type_nlhdlr.h:52
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2835
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRCOPYHDLR((*copy)))
Definition: nlhdlr.c:76