Scippy

SCIP

Solving Constraint Integer Programs

nlhdlr_perspective.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-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_perspective.c
26  * @ingroup DEFPLUGINS_NLHDLR
27  * @brief perspective nonlinear handler
28  * @author Ksenia Bestuzheva
29  */
30 
31 #include <string.h>
32 
34 #include "scip/cons_nonlinear.h"
35 #include "scip/scip_sol.h"
36 #include "scip/pub_misc_rowprep.h"
37 #include "scip/nlhdlr.h"
38 
39 /* fundamental nonlinear handler properties */
40 #define NLHDLR_NAME "perspective"
41 #define NLHDLR_DESC "perspective handler for expressions"
42 #define NLHDLR_DETECTPRIORITY -20 /**< detect last so that to make use of what other handlers detected */
43 #define NLHDLR_ENFOPRIORITY 125 /**< enforce first because perspective cuts are always stronger */
44 
45 #define DEFAULT_MAXPROPROUNDS 1 /**< maximal number of propagation rounds in probing */
46 #define DEFAULT_MINDOMREDUCTION 0.1 /**< minimal relative reduction in a variable's domain for applying probing */
47 #define DEFAULT_MINVIOLPROBING 1e-05 /**< minimal violation w.r.t. auxiliary variables for applying probing */
48 #define DEFAULT_PROBINGONLYINSEPA TRUE /**< whether to do probing only in separation loop */
49 #define DEFAULT_PROBINGFREQ 1 /**< probing frequency (-1 - no probing, 0 - root node only) */
50 #define DEFAULT_CONVEXONLY FALSE /**< whether perspective cuts are added only for convex expressions */
51 #define DEFAULT_TIGHTENBOUNDS TRUE /**< whether variable semicontinuity is used to tighten variable bounds */
52 #define DEFAULT_ADJREFPOINT TRUE /**< whether to adjust the reference point if indicator is not 1 */
53 
54 /*
55  * Data structures
56  */
57 
58 /** data structure to store information of a semicontinuous variable
59  *
60  * For a variable x (not stored in the struct), this stores the data of nbnds implications
61  * bvars[i] = 0 -> x = vals[i]
62  * bvars[i] = 1 -> lbs[i] <= x <= ubs[i]
63  * where bvars[i] are binary variables.
64  */
65 struct SCVarData
66 {
67  SCIP_Real* vals0; /**< values of the variable when the corresponding bvars[i] = 0 */
68  SCIP_Real* lbs1; /**< global lower bounds of the variable when the corresponding bvars[i] = 1 */
69  SCIP_Real* ubs1; /**< global upper bounds of the variable when the corresponding bvars[i] = 1 */
70  SCIP_VAR** bvars; /**< the binary variables on which the variable domain depends */
71  int nbnds; /**< number of suitable on/off bounds the var has */
72  int bndssize; /**< size of the arrays */
73 };
74 typedef struct SCVarData SCVARDATA;
75 
76 /** nonlinear handler expression data
77  *
78  * For an expression expr (not stored in the struct), this stores the data of nindicators implications
79  * indicators[i] = 0 -> expr = exprvals[0]
80  * where indicators[i] is an indicator (binary) variable, corresponding to some bvars entry in SCVarData.
81  *
82  * Also stores the variables the expression depends on.
83  */
84 struct SCIP_NlhdlrExprData
85 {
86  SCIP_Real* exprvals0; /**< 'off' values of the expression for each indicator variable */
87  SCIP_VAR** vars; /**< expression variables (both original and auxiliary) */
88  int nvars; /**< total number of variables in the expression */
89  int varssize; /**< size of the vars array */
90  SCIP_VAR** indicators; /**< all indicator variables for the expression */
91  int nindicators; /**< number of indicator variables */
92 };
93 
94 /** nonlinear handler data */
95 struct SCIP_NlhdlrData
96 {
97  SCIP_HASHMAP* scvars; /**< maps semicontinuous variables to their on/off bounds (SCVarData) */
98 
99  /* parameters */
100  int maxproprounds; /**< maximal number of propagation rounds in probing */
101  SCIP_Real mindomreduction; /**< minimal relative reduction in a variable's domain for applying probing */
102  SCIP_Real minviolprobing; /**< minimal violation w.r.t. auxiliary variables for applying probing */
103  SCIP_Bool probingonlyinsepa; /**< whether to do probing only in separation loop */
104  int probingfreq; /**< if and when to do probing */
105  SCIP_Bool convexonly; /**< whether perspective cuts are added only for convex expressions */
106  SCIP_Bool tightenbounds; /**< whether variable semicontinuity is used to tighten variable bounds */
107  SCIP_Bool adjrefpoint; /**< whether to adjust the reference point if indicator is not 1 */
108 };
109 
110 /*
111  * Local methods
112  */
113 
114 /*
115  * Helper methods for working with nlhdlrExprData
116  */
117 
118 /** frees nlhdlrexprdata structure */
119 static
121  SCIP* scip, /**< SCIP data structure */
122  SCIP_NLHDLREXPRDATA* nlhdlrexprdata /**< nlhdlr expression data */
123  )
124 {
125  int v;
126 
127  if( nlhdlrexprdata->nindicators != 0 )
128  {
129  assert(nlhdlrexprdata->indicators != NULL);
130  for( v = nlhdlrexprdata->nindicators - 1; v >= 0; --v )
131  {
132  SCIP_CALL( SCIPreleaseVar(scip, &(nlhdlrexprdata->indicators[v])) );
133  }
134  SCIPfreeBlockMemoryArray(scip, &(nlhdlrexprdata->indicators), nlhdlrexprdata->nindicators);
135  SCIPfreeBlockMemoryArrayNull(scip, &(nlhdlrexprdata->exprvals0), nlhdlrexprdata->nindicators);
136  }
137 
138  for( v = nlhdlrexprdata->nvars - 1; v >= 0; --v )
139  {
140  SCIP_CALL( SCIPreleaseVar(scip, &(nlhdlrexprdata->vars[v])) );
141  }
142  SCIPfreeBlockMemoryArrayNull(scip, &nlhdlrexprdata->vars, nlhdlrexprdata->varssize);
143 
144  return SCIP_OKAY;
145 }
146 
147 /* remove an indicator from nlhdlr expression data */
148 static
150  SCIP* scip, /**< SCIP data structure */
151  SCIP_NLHDLREXPRDATA* nlexprdata, /**< nlhdlr expression data */
152  int pos /**< position of the indicator */
153  )
154 {
155  int i;
156 
157  assert(pos >= 0 && pos < nlexprdata->nindicators);
158 
159  SCIP_CALL( SCIPreleaseVar(scip, &nlexprdata->indicators[pos]) );
160  for( i = pos; i < nlexprdata->nindicators - 1; ++i )
161  {
162  nlexprdata->indicators[i] = nlexprdata->indicators[i+1];
163  }
164 
165  --nlexprdata->nindicators;
166 
167  return SCIP_OKAY;
168 }
169 
170 /** adds an auxiliary variable to the vars array in nlhdlrexprdata */
171 static
173  SCIP* scip, /**< SCIP data structure */
174  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
175  SCIP_HASHMAP* auxvarmap, /**< hashmap linking auxvars to positions in nlhdlrexprdata->vars */
176  SCIP_VAR* auxvar /**< variable to be added */
177  )
178 {
179  int pos;
180  int newsize;
181 
182  assert(nlhdlrexprdata != NULL);
183  assert(auxvar != NULL);
184 
185  pos = SCIPhashmapGetImageInt(auxvarmap, (void*) auxvar);
186 
187  if( pos != INT_MAX )
188  return SCIP_OKAY;
189 
190  /* ensure size */
191  if( nlhdlrexprdata->nvars + 1 > nlhdlrexprdata->varssize )
192  {
193  newsize = SCIPcalcMemGrowSize(scip, nlhdlrexprdata->nvars + 1);
194  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->vars, nlhdlrexprdata->varssize, newsize) );
195  nlhdlrexprdata->varssize = newsize;
196  }
197  assert(nlhdlrexprdata->nvars + 1 <= nlhdlrexprdata->varssize);
198 
199  nlhdlrexprdata->vars[nlhdlrexprdata->nvars] = auxvar;
200  SCIP_CALL( SCIPcaptureVar(scip, auxvar) );
201  SCIP_CALL( SCIPhashmapSetImageInt(auxvarmap, (void*) auxvar, nlhdlrexprdata->nvars) );
202  ++(nlhdlrexprdata->nvars);
203 
204  return SCIP_OKAY;
205 }
206 
207 /*
208  * Semicontinuous variable methods
209  */
210 
211 /** adds an indicator to the data of a semicontinuous variable */
212 static
214  SCIP* scip, /**< SCIP data structure */
215  SCVARDATA* scvdata, /**< semicontinuous variable data */
216  SCIP_VAR* indicator, /**< indicator to be added */
217  SCIP_Real val0, /**< value of the variable when indicator == 0 */
218  SCIP_Real lb1, /**< lower bound of the variable when indicator == 1 */
219  SCIP_Real ub1 /**< upper bound of the variable when indicator == 1 */
220  )
221 {
222  int newsize;
223  int i;
224  SCIP_Bool found;
225  int pos;
226 
227  assert(scvdata != NULL);
228  assert(indicator != NULL);
229 
230  /* find the position where to insert */
231  if( scvdata->bvars == NULL )
232  {
233  assert(scvdata->nbnds == 0 && scvdata->bndssize == 0);
234  found = FALSE;
235  pos = 0;
236  }
237  else
238  {
239  found = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, &pos);
240  }
241 
242  if( found )
243  return SCIP_OKAY;
244 
245  /* ensure sizes */
246  if( scvdata->nbnds + 1 > scvdata->bndssize )
247  {
248  newsize = SCIPcalcMemGrowSize(scip, scvdata->nbnds + 1);
249  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->bvars, scvdata->bndssize, newsize) );
250  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->vals0, scvdata->bndssize, newsize) );
251  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->lbs1, scvdata->bndssize, newsize) );
252  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->ubs1, scvdata->bndssize, newsize) );
253  scvdata->bndssize = newsize;
254  }
255  assert(scvdata->nbnds + 1 <= scvdata->bndssize);
256  assert(scvdata->bvars != NULL);
257 
258  /* move entries if needed */
259  for( i = scvdata->nbnds; i > pos; --i )
260  {
261  /* coverity[forward_null] */
262  scvdata->bvars[i] = scvdata->bvars[i-1];
263  scvdata->vals0[i] = scvdata->vals0[i-1];
264  scvdata->lbs1[i] = scvdata->lbs1[i-1];
265  scvdata->ubs1[i] = scvdata->ubs1[i-1];
266  }
267 
268  scvdata->bvars[pos] = indicator;
269  scvdata->vals0[pos] = val0;
270  scvdata->lbs1[pos] = lb1;
271  scvdata->ubs1[pos] = ub1;
272  ++scvdata->nbnds;
273 
274  return SCIP_OKAY;
275 }
276 
277 /** find scvardata of var and position of indicator in it
278  *
279  * If indicator is not there, returns NULL.
280  */
281 static
283  SCIP_HASHMAP* scvars, /**< hashmap linking variables to scvardata */
284  SCIP_VAR* var, /**< variable */
285  SCIP_VAR* indicator, /**< indicator variable */
286  int* pos /**< pointer to store the position of indicator */
287  )
288 {
289  SCIP_Bool exists;
290  SCVARDATA* scvdata;
291 
292  assert(var != NULL);
293  assert(scvars != NULL);
294  assert(indicator != NULL);
295 
296  scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var);
297  if( scvdata != NULL )
298  {
299  /* look for the indicator variable */
300  exists = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, pos);
301  if( !exists )
302  return NULL;
303 
304  return scvdata;
305  }
306 
307  return NULL;
308 }
309 
310 /** checks if a variable is semicontinuous and, if needed, updates the scvars hashmap
311  *
312  * A variable \f$x\f$ is semicontinuous if its bounds depend on at least one binary variable called the indicator,
313  * and indicator = 0 &rArr; \f$x = x^0\f$ for some real constant \f$x^0\f$.
314  */
315 static
317  SCIP* scip, /**< SCIP data structure */
318  SCIP_VAR* var, /**< the variable to check */
319  SCIP_HASHMAP* scvars, /**< semicontinuous variable information */
320  SCIP_Bool* result /**< buffer to store whether var is semicontinuous */
321  )
322 {
323  SCIP_Real lb0;
324  SCIP_Real ub0;
325  SCIP_Real lb1;
326  SCIP_Real ub1;
327  SCIP_Real glb;
328  SCIP_Real gub;
329  SCIP_Bool exists;
330  int c;
331  int pos;
332  SCIP_VAR** vlbvars;
333  SCIP_VAR** vubvars;
334  SCIP_Real* vlbcoefs;
335  SCIP_Real* vubcoefs;
336  SCIP_Real* vlbconstants;
337  SCIP_Real* vubconstants;
338  int nvlbs;
339  int nvubs;
340  SCVARDATA* scvdata;
341  SCIP_VAR* bvar;
342 
343  assert(scip != NULL);
344  assert(var != NULL);
345  assert(scvars != NULL);
346  assert(result != NULL);
347 
348  scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var);
349  if( scvdata != NULL )
350  {
351  *result = TRUE;
352  return SCIP_OKAY;
353  }
354 
355  vlbvars = SCIPvarGetVlbVars(var);
356  vubvars = SCIPvarGetVubVars(var);
357  vlbcoefs = SCIPvarGetVlbCoefs(var);
358  vubcoefs = SCIPvarGetVubCoefs(var);
359  vlbconstants = SCIPvarGetVlbConstants(var);
360  vubconstants = SCIPvarGetVubConstants(var);
361  nvlbs = SCIPvarGetNVlbs(var);
362  nvubs = SCIPvarGetNVubs(var);
363  glb = SCIPvarGetLbGlobal(var);
364  gub = SCIPvarGetUbGlobal(var);
365 
366  *result = FALSE;
367 
368  /* Scan through lower bounds; for each binary vlbvar save the corresponding lb0 and lb1.
369  * Then check if there is an upper bound with this vlbvar and save ub0 and ub1.
370  * If the found bounds imply that the var value is fixed to some val0 when vlbvar = 0,
371  * save vlbvar and val0 to scvdata.
372  */
373  for( c = 0; c < nvlbs; ++c )
374  {
375  if( SCIPvarGetType(vlbvars[c]) != SCIP_VARTYPE_BINARY )
376  continue;
377 
378  SCIPdebugMsg(scip, "var <%s>[%f, %f] lower bound: %f <%s> %+f", SCIPvarGetName(var), glb, gub, vlbcoefs[c], SCIPvarGetName(vlbvars[c]), vlbconstants[c]);
379 
380  bvar = vlbvars[c];
381 
382  lb0 = MAX(vlbconstants[c], glb);
383  lb1 = MAX(vlbconstants[c] + vlbcoefs[c], glb);
384 
385  /* look for bvar in vubvars */
386  if( vubvars != NULL )
387  exists = SCIPsortedvecFindPtr((void**)vubvars, SCIPvarComp, bvar, nvubs, &pos);
388  else
389  exists = FALSE;
390  if( exists )
391  { /*lint --e{644}*/
392  SCIPdebugMsgPrint(scip, ", upper bound: %f <%s> %+f", vubcoefs[pos], SCIPvarGetName(vubvars[pos]), vubconstants[pos]); /*lint !e613*/
393 
394  /* save the upper bounds */
395  ub0 = MIN(vubconstants[pos], gub);
396  ub1 = MIN(vubconstants[pos] + vubcoefs[pos], gub);
397  }
398  else
399  {
400  /* if there is no upper bound with vubvar = bvar, use global var bounds */
401  ub0 = gub;
402  ub1 = gub;
403  }
404 
405  /* the 'off' domain of a semicontinuous var should reduce to a single point and be different from the 'on' domain */
406  SCIPdebugMsgPrint(scip, " -> <%s> in [%f, %f] (off), [%f, %f] (on)\n", SCIPvarGetName(var), lb0, ub0, lb1, ub1);
407  if( SCIPisEQ(scip, lb0, ub0) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
408  {
409  if( scvdata == NULL )
410  {
411  SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) );
412  }
413 
414  SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
415  }
416  }
417 
418  /* look for vubvars that have not been processed yet */
419  assert(vubvars != NULL || nvubs == 0);
420  for( c = 0; c < nvubs; ++c )
421  {
422  /* coverity[forward_null] */
423  if( SCIPvarGetType(vubvars[c]) != SCIP_VARTYPE_BINARY ) /*lint !e613*/
424  continue;
425 
426  bvar = vubvars[c]; /*lint !e613*/
427 
428  /* skip vars that are in vlbvars */
429  if( vlbvars != NULL && SCIPsortedvecFindPtr((void**)vlbvars, SCIPvarComp, bvar, nvlbs, &pos) )
430  continue;
431 
432  SCIPdebugMsg(scip, "var <%s>[%f, %f] upper bound: %f <%s> %+f",
433  SCIPvarGetName(var), glb, gub, vubcoefs[c], SCIPvarGetName(vubvars[c]), vubconstants[c]); /*lint !e613*/
434 
435  lb0 = glb;
436  lb1 = glb;
437  ub0 = MIN(vubconstants[c], gub);
438  ub1 = MIN(vubconstants[c] + vubcoefs[c], gub);
439 
440  /* the 'off' domain of a semicontinuous var should reduce to a single point and be different from the 'on' domain */
441  SCIPdebugMsgPrint(scip, " -> <%s> in [%f, %f] (off), [%f, %f] (on)\n", SCIPvarGetName(var), lb0, ub0, lb1, ub1);
442  if( SCIPisEQ(scip, lb0, ub0) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
443  {
444  if( scvdata == NULL )
445  {
446  SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) );
447  }
448 
449  SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
450  }
451  }
452 
453  if( scvdata != NULL )
454  {
455 #ifdef SCIP_DEBUG
456  SCIPdebugMsg(scip, "var <%s> has global bounds [%f, %f] and the following on/off bounds:\n", SCIPvarGetName(var), glb, gub);
457  for( c = 0; c < scvdata->nbnds; ++c )
458  {
459  SCIPdebugMsg(scip, " c = %d, bvar <%s>: val0 = %f\n", c, SCIPvarGetName(scvdata->bvars[c]), scvdata->vals0[c]);
460  }
461 #endif
462  SCIP_CALL( SCIPhashmapInsert(scvars, var, scvdata) );
463  *result = TRUE;
464  }
465 
466  return SCIP_OKAY;
467 }
468 
469 /*
470  * Semicontinuous expression methods
471  */
472 
473 /* checks if an expression is semicontinuous
474  *
475  * An expression is semicontinuous if all of its nonlinear variables are semicontinuous
476  * and share at least one common indicator variable
477  */
478 static
480  SCIP* scip, /**< SCIP data structure */
481  SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
482  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
483  SCIP_EXPR* expr, /**< expression */
484  SCIP_Bool* res /**< buffer to store whether the expression is semicontinuous */
485  )
486 {
487  int v;
488  SCIP_Bool var_is_sc;
489  SCVARDATA* scvdata;
490  SCIP_VAR* var;
491  int nindicators;
492  int nbnds0;
493  int c;
494  SCIP_VAR** indicators;
495  SCIP_Bool* nonlinear;
496 
497  *res = FALSE;
498 
499  /* constant expression is not semicontinuous; variable expressions are of no interest here */
500  if( nlhdlrexprdata->nvars == 0 )
501  return SCIP_OKAY;
502 
503  indicators = NULL;
504  nindicators = 0;
505  nbnds0 = 0;
506 
507  if( SCIPisExprSum(scip, expr) )
508  {
509  SCIP_EXPRITER* it;
510  SCIP_EXPR* child;
511  SCIP_EXPR* curexpr;
512  int pos;
513  SCIP_Bool issc;
514 
515  /* sums are treated separately because if there are variables that are non-semicontinuous but
516  * appear only linearly, we still want to apply perspective to expr
517  */
518 
519  SCIP_CALL( SCIPallocClearBufferArray(scip, &nonlinear, nlhdlrexprdata->nvars) );
520  SCIP_CALL( SCIPcreateExpriter(scip, &it) );
521 
522  for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
523  {
524  child = SCIPexprGetChildren(expr)[c];
525 
526  if( SCIPisExprVar(scip, child) )
527  {
528  var = SCIPgetVarExprVar(child);
529 
530  /* save information on semicontinuity of child */
531  SCIP_CALL( varIsSemicontinuous(scip, var, nlhdlrdata->scvars, &var_is_sc) );
532 
533  /* since child is a variable, go on regardless of the value of var_is_sc */
534  continue;
535  }
536 
537  issc = TRUE;
538 
540  curexpr = SCIPexpriterGetCurrent(it);
541 
542  /* all nonlinear terms of a sum should be semicontinuous in original variables */
543  while( !SCIPexpriterIsEnd(it) )
544  {
545  assert(curexpr != NULL);
546 
547  if( SCIPisExprVar(scip, curexpr) )
548  {
549  var = SCIPgetVarExprVar(curexpr);
550 
551  if( !SCIPvarIsRelaxationOnly(var) )
552  {
553  SCIP_CALL( varIsSemicontinuous(scip, var, nlhdlrdata->scvars, &var_is_sc) );
554 
555  /* mark the variable as nonlinear */
556  (void) SCIPsortedvecFindPtr((void**) nlhdlrexprdata->vars, SCIPvarComp, (void*) var, nlhdlrexprdata->nvars,
557  &pos);
558  assert(0 <= pos && pos < nlhdlrexprdata->nvars);
559  nonlinear[pos] = TRUE;
560 
561  if( !var_is_sc )
562  {
563  /* non-semicontinuous child which is (due to a previous check) not a var ->
564  * expr is non-semicontinuous
565  */
566  issc = FALSE;
567  break;
568  }
569  }
570  }
571  curexpr = SCIPexpriterGetNext(it);
572  }
573 
574  if( !issc )
575  {
576  SCIPfreeExpriter(&it);
577  goto TERMINATE;
578  }
579  }
580  SCIPfreeExpriter(&it);
581  }
582  else
583  {
584  /* non-sum expression */
585  nonlinear = NULL;
586 
587  /* all variables of a non-sum on/off expression should be semicontinuous */
588  for( v = 0; v < nlhdlrexprdata->nvars; ++v )
589  {
590  SCIP_CALL( varIsSemicontinuous(scip, nlhdlrexprdata->vars[v], nlhdlrdata->scvars, &var_is_sc) );
591  if( !var_is_sc )
592  return SCIP_OKAY;
593  }
594  }
595 
596  /* look for common binary variables for all variables of the expression */
597 
598  SCIPdebugMsg(scip, "Array intersection for var <%s>\n", SCIPvarGetName(nlhdlrexprdata->vars[0]));
599  for( v = 0; v < nlhdlrexprdata->nvars; ++v )
600  {
601  SCIPdebugMsg(scip, "%s; \n", SCIPvarGetName(nlhdlrexprdata->vars[v]));
602 
603  if( nonlinear != NULL && !nonlinear[v] )
604  continue;
605 
606  scvdata = (SCVARDATA*)SCIPhashmapGetImage(nlhdlrdata->scvars, (void*) nlhdlrexprdata->vars[v]);
607 
608  /* we should have exited earlier if there is a nonlinear non-semicontinuous variable */
609  assert(scvdata != NULL);
610 
611  if( indicators == NULL )
612  {
613  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &indicators, scvdata->bvars, scvdata->nbnds) );
614  nbnds0 = scvdata->nbnds;
615  nindicators = nbnds0;
616  }
617  else
618  {
619  SCIPcomputeArraysIntersectionPtr((void**)indicators, nindicators, (void**)scvdata->bvars, scvdata->nbnds,
620  SCIPvarComp, (void**)indicators, &nindicators);
621  }
622 
623  /* if we have found out that the intersection is empty, expr is not semicontinuous */
624  if( indicators != NULL && nindicators == 0 )
625  {
626  SCIPfreeBlockMemoryArray(scip, &indicators, nbnds0);
627  goto TERMINATE;
628  }
629  }
630 
631  /* this can happen if all children are linear vars and none are semicontinuous */
632  if( indicators == NULL )
633  {
634  goto TERMINATE;
635  }
636  assert(nindicators > 0 && nindicators <= nbnds0);
637 
638  if( nindicators < nbnds0 )
639  {
640  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &indicators, nbnds0, nindicators) );
641  }
642 
643  for( v = 0; v < nindicators; ++v )
644  {
645  SCIP_CALL( SCIPcaptureVar(scip, indicators[v]) );
646  }
647  nlhdlrexprdata->indicators = indicators;
648  nlhdlrexprdata->nindicators = nindicators;
649  *res = TRUE;
650 
651  TERMINATE:
652  SCIPfreeBufferArrayNull(scip, &nonlinear);
653 
654  return SCIP_OKAY;
655 }
656 
657 /** computes the 'off' value of the expression and the 'off' values of
658  * semicontinuous auxiliary variables for each indicator variable
659  */
660 static
662  SCIP* scip, /**< SCIP data structure */
663  SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
664  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
665  SCIP_EXPR* expr /**< expression */
666  )
667 {
668  SCIP_EXPRITER* it;
669  SCIP_SOL* sol;
670  int i;
671  int v;
672  int norigvars;
673  SCIP_Real* origvals0;
674  SCIP_VAR** origvars;
675  SCVARDATA* scvdata;
676  SCIP_VAR* auxvar;
677  SCIP_EXPR* curexpr;
678  SCIP_HASHMAP* auxvarmap;
679  SCIP_Bool hasnonsc;
680  int pos;
681 
682  assert(expr != NULL);
683 
684  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(nlhdlrexprdata->exprvals0), nlhdlrexprdata->nindicators) );
685  SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
686  SCIP_CALL( SCIPallocBufferArray(scip, &origvals0, nlhdlrexprdata->nvars) );
687  SCIP_CALL( SCIPhashmapCreate(&auxvarmap, SCIPblkmem(scip), 10) );
688  SCIP_CALL( SCIPcreateExpriter(scip, &it) );
689  SCIP_CALL( SCIPduplicateBufferArray(scip, &origvars, nlhdlrexprdata->vars, nlhdlrexprdata->nvars) );
690  norigvars = nlhdlrexprdata->nvars;
691 
692  for( i = nlhdlrexprdata->nindicators - 1; i >= 0; --i )
693  {
694  hasnonsc = FALSE;
695 
696  /* set sol to the off value of all expr vars for this indicator */
697  for( v = 0; v < norigvars; ++v )
698  {
699  /* set vals0[v] = 0 if var is non-sc with respect to indicators[i] - then it will not
700  * contribute to exprvals0[i] since any non-sc var must be linear
701  */
702  scvdata = getSCVarDataInd(nlhdlrdata->scvars, origvars[v], nlhdlrexprdata->indicators[i], &pos);
703  if( scvdata == NULL )
704  {
705  origvals0[v] = 0.0;
706  hasnonsc = TRUE;
707  }
708  else
709  {
710  origvals0[v] = scvdata->vals0[pos];
711  }
712  }
713  SCIP_CALL( SCIPsetSolVals(scip, sol, norigvars, origvars, origvals0) );
714  SCIP_CALL( SCIPevalExpr(scip, expr, sol, 0L) );
715 
716  if( SCIPexprGetEvalValue(expr) == SCIP_INVALID ) /*lint !e777*/
717  {
718  SCIPdebugMsg(scip, "expression evaluation failed for %p, removing indicator %s\n",
719  (void*)expr, SCIPvarGetName(nlhdlrexprdata->indicators[i]));
720  /* TODO should we fix the indicator variable to 1? */
721  /* since the loop is backwards, this only modifies the already processed part of nlhdlrexprdata->indicators */
722  SCIP_CALL( removeIndicator(scip, nlhdlrexprdata, i) );
723  continue;
724  }
725 
726  nlhdlrexprdata->exprvals0[i] = SCIPexprGetEvalValue(expr);
727 
728  /* iterate through the expression and create scvdata for aux vars */
730  curexpr = SCIPexpriterGetCurrent(it);
731 
732  while( !SCIPexpriterIsEnd(it) )
733  {
734  auxvar = SCIPgetExprAuxVarNonlinear(curexpr);
735 
736  if( auxvar != NULL )
737  {
738  SCIP_Bool issc = TRUE;
739 #ifndef NDEBUG
740  SCIP_EXPR** childvarexprs;
741  int nchildvarexprs;
742  SCIP_VAR* var;
743 #endif
744 
745  if( hasnonsc )
746  {
747  /* expr is a sum with non-semicontinuous linear terms. Therefore, curexpr might be
748  * non-semicontinuous. In that case the auxvar is also non-semicontinuous, so
749  * we will skip on/off bounds computation.
750  */
751  if( SCIPisExprVar(scip, curexpr) )
752  {
753  /* easy case: curexpr is a variable, can check semicontinuity immediately */
754  scvdata = getSCVarDataInd(nlhdlrdata->scvars, SCIPgetVarExprVar(curexpr),
755  nlhdlrexprdata->indicators[i], &pos);
756  issc = scvdata != NULL;
757  }
758  else if( SCIPisExprSum(scip, curexpr) && curexpr == expr )
759  {
760  /* if expr itself is a sum, this is an exception since a sum with nonlinear terms is
761  * allowed to have both semicontinuous and non-semicontinuous variables; we skip it here
762  * and then analyse it term by term
763  */
764  issc = FALSE;
765  }
766 
767 #ifndef NDEBUG
768  if( !SCIPisExprVar(scip, curexpr) && (!SCIPisExprSum(scip, curexpr) || curexpr != expr) )
769  {
770  /* curexpr is a non-variable expression and does not fit the sum special case,
771  * so it belongs to the non-linear part of expr.
772  * Since the non-linear part of expr must be semicontinuous with respect to
773  * nlhdlrexprdata->indicators[i], curexpr must be semicontinuous
774  */
775 
776  SCIP_CALL( SCIPallocBufferArray(scip, &childvarexprs, norigvars) );
777  SCIP_CALL( SCIPgetExprVarExprs(scip, curexpr, childvarexprs, &nchildvarexprs) );
778 
779  /* all nonlinear variables of a sum on/off term should be semicontinuous */
780  for( v = 0; v < nchildvarexprs; ++v )
781  {
782  var = SCIPgetVarExprVar(childvarexprs[v]);
783  scvdata = getSCVarDataInd(nlhdlrdata->scvars, var, nlhdlrexprdata->indicators[i], &pos);
784  assert(scvdata != NULL);
785 
786  SCIP_CALL( SCIPreleaseExpr(scip, &childvarexprs[v]) );
787  }
788 
789  SCIPfreeBufferArray(scip, &childvarexprs);
790  }
791 #endif
792  }
793 
794  if( issc )
795  {
796  /* we know that all vars are semicontinuous with respect to exprdata->indicators; it remains to:
797  * - get or create the scvardata structure for auxvar
798  * - if had to create scvardata, add it to scvars hashmap
799  * - add the indicator and the off value (= curexpr's off value) to scvardata
800  */
801  scvdata = (SCVARDATA*) SCIPhashmapGetImage(nlhdlrdata->scvars, (void*)auxvar);
802  if( scvdata == NULL )
803  {
804  SCIP_CALL( SCIPallocClearBlockMemory(scip, &scvdata) );
805  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->bvars, nlhdlrexprdata->nindicators) );
806  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->vals0, nlhdlrexprdata->nindicators) );
807  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->lbs1, nlhdlrexprdata->nindicators) );
808  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->ubs1, nlhdlrexprdata->nindicators) );
809  scvdata->bndssize = nlhdlrexprdata->nindicators;
810  SCIP_CALL( SCIPhashmapInsert(nlhdlrdata->scvars, auxvar, scvdata) );
811  }
812 
813  SCIP_CALL( addSCVarIndicator(scip, scvdata, nlhdlrexprdata->indicators[i],
814  SCIPexprGetEvalValue(curexpr), SCIPvarGetLbGlobal(auxvar), SCIPvarGetUbGlobal(auxvar)) );
815  }
816 
817  SCIP_CALL( addAuxVar(scip, nlhdlrexprdata, auxvarmap, auxvar) );
818  }
819 
820  curexpr = SCIPexpriterGetNext(it);
821  }
822  }
823 
824  SCIPfreeExpriter(&it);
825  SCIPhashmapFree(&auxvarmap);
826  SCIPfreeBufferArray(scip, &origvars);
827  SCIPfreeBufferArray(scip, &origvals0);
828  SCIP_CALL( SCIPfreeSol(scip, &sol) );
829 
830  return SCIP_OKAY;
831 }
832 
833 /*
834  * Probing and bound tightening methods
835  */
836 
837 /** go into probing and set some variable bounds */
838 static
840  SCIP* scip, /**< SCIP data structure */
841  SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
842  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
843  SCIP_VAR* indicator, /**< indicator variable */
844  SCIP_VAR** probingvars, /**< array of vars whose bounds we will change in probing */
845  SCIP_INTERVAL* probingdoms, /**< array of intervals to which bounds of probingvars will be changed in probing */
846  int nprobingvars, /**< number of probing vars */
847  SCIP_SOL* sol, /**< solution to be separated */
848  SCIP_SOL** solcopy, /**< buffer for a copy of sol before going into probing; if *solcopy == sol, then copy is created */
849  SCIP_Bool* cutoff_probing /**< pointer to store whether indicator == 1 is infeasible */
850  )
851 {
852  int v;
853  SCIP_Real newlb;
854  SCIP_Real newub;
855  SCIP_Bool propagate;
856 
857  propagate = SCIPgetDepth(scip) == 0;
858 
859  /* if a copy of sol has not been created yet, then create one now and copy the relevant var values from sol,
860  * because sol can change after SCIPstartProbing, e.g., when linked to the LP solution
861  */
862  if( *solcopy == sol )
863  {
864  SCIP_CALL( SCIPcreateSol(scip, solcopy, NULL) );
865  for( v = 0; v < nlhdlrexprdata->nvars; ++v )
866  {
867  SCIP_CALL( SCIPsetSolVal(scip, *solcopy, nlhdlrexprdata->vars[v], SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[v])) );
868  }
869  for( v = 0; v < nlhdlrexprdata->nindicators; ++v )
870  {
871  SCIP_CALL( SCIPsetSolVal(scip, *solcopy, nlhdlrexprdata->indicators[v], SCIPgetSolVal(scip, sol, nlhdlrexprdata->indicators[v])) );
872  }
873  }
874 
875  /* go into probing */
876  SCIP_CALL( SCIPstartProbing(scip) );
877 
878  /* create a probing node */
879  SCIP_CALL( SCIPnewProbingNode(scip) );
880 
881  /* set indicator to 1 */
882  SCIP_CALL( SCIPchgVarLbProbing(scip, indicator, 1.0) );
883 
884  /* apply stored bounds */
885  for( v = 0; v < nprobingvars; ++v )
886  {
887  newlb = SCIPintervalGetInf(probingdoms[v]);
888  newub = SCIPintervalGetSup(probingdoms[v]);
889 
890  if( SCIPisGT(scip, newlb, SCIPvarGetLbLocal(probingvars[v])) || (newlb >= 0.0 && SCIPvarGetLbLocal(probingvars[v]) < 0.0) )
891  {
892  SCIP_CALL( SCIPchgVarLbProbing(scip, probingvars[v], newlb) );
893  }
894  if( SCIPisLT(scip, newub, SCIPvarGetUbLocal(probingvars[v])) || (newub <= 0.0 && SCIPvarGetUbLocal(probingvars[v]) > 0.0) )
895  {
896  SCIP_CALL( SCIPchgVarUbProbing(scip, probingvars[v], newub) );
897  }
898  }
899 
900  if( propagate )
901  {
902  SCIP_Longint ndomreds;
903 
904  SCIP_CALL( SCIPpropagateProbing(scip, nlhdlrdata->maxproprounds, cutoff_probing, &ndomreds) );
905  }
906 
907  return SCIP_OKAY;
908 }
909 
910 /** analyse on/off bounds on a variable
911  *
912  * analyses for
913  * 1. tightening bounds in probing for indicator = 1,
914  * 2. fixing indicator / detecting cutoff if one or both states are infeasible,
915  * 3. tightening local bounds if indicator is fixed.
916  *
917  * `probinglb` and `probingub` are only set if `doprobing` is TRUE.
918  * They are either set to bounds that should be used in probing or to `SCIP_INVALID` if bounds on
919  * `var` shouldn't be changed in probing.
920  */
921 static
923  SCIP* scip, /**< SCIP data structure */
924  SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
925  SCIP_VAR* var, /**< variable */
926  SCIP_VAR* indicator, /**< indicator variable */
927  SCIP_Bool indvalue, /**< indicator value for which the bounds are applied */
928  SCIP_Bool* infeas, /**< pointer to store whether infeasibility has been detected */
929  SCIP_Real* probinglb, /**< pointer to store the lower bound to be applied in probing */
930  SCIP_Real* probingub, /**< pointer to store the upper bound to be applied in probing */
931  SCIP_Bool doprobing, /**< whether we currently consider to go into probing */
932  SCIP_Bool* reduceddom /**< pointer to store whether any variables were fixed */
933  )
934 {
935  SCVARDATA* scvdata;
936  int pos;
937  SCIP_Real sclb;
938  SCIP_Real scub;
939  SCIP_Real loclb;
940  SCIP_Real locub;
941  SCIP_Bool bndchgsuccess;
942 
943  assert(var != NULL);
944  assert(indicator != NULL);
945  assert(infeas != NULL);
946  assert(reduceddom != NULL);
947 
948  /* shouldn't be called if indicator is fixed to !indvalue */
949  assert((indvalue && SCIPvarGetUbLocal(indicator) > 0.5) || (!indvalue && SCIPvarGetLbLocal(indicator) < 0.5));
950 
951  *infeas = FALSE;
952  *reduceddom = FALSE;
953  scvdata = getSCVarDataInd(nlhdlrdata->scvars, var, indicator, &pos);
954  if( doprobing )
955  {
956  assert(probinglb != NULL);
957  assert(probingub != NULL);
958 
959  *probinglb = SCIP_INVALID;
960  *probingub = SCIP_INVALID;
961  }
962 
963  /* nothing to do for non-semicontinuous variables */
964  if( scvdata == NULL )
965  {
966  return SCIP_OKAY;
967  }
968 
969  sclb = indvalue ? scvdata->lbs1[pos] : scvdata->vals0[pos];
970  scub = indvalue ? scvdata->ubs1[pos] : scvdata->vals0[pos];
971  loclb = SCIPvarGetLbLocal(var);
972  locub = SCIPvarGetUbLocal(var);
973 
974  /* nothing to do for fixed variables */
975  if( SCIPisEQ(scip, loclb, locub) )
976  return SCIP_OKAY;
977 
978  /* use a non-redundant lower bound */
979  if( SCIPisGT(scip, sclb, SCIPvarGetLbLocal(var)) || (sclb >= 0.0 && loclb < 0.0) )
980  {
981  /* first check for infeasibility */
982  if( SCIPisFeasGT(scip, sclb, SCIPvarGetUbLocal(var)) )
983  {
984  SCIP_CALL( SCIPfixVar(scip, indicator, indvalue ? 0.0 : 1.0, infeas, &bndchgsuccess) );
985  *reduceddom += bndchgsuccess;
986  if( *infeas )
987  {
988  return SCIP_OKAY;
989  }
990  }
991  else if( nlhdlrdata->tightenbounds &&
992  (SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5) )
993  {
994  /* indicator is fixed; due to a previous check, here it can only be fixed to indvalue;
995  * therefore, sclb is valid for the current node
996  */
997 
998  if( indvalue == 0 )
999  {
1000  assert(sclb == scub); /*lint !e777*/
1001  SCIP_CALL( SCIPfixVar(scip, var, sclb, infeas, &bndchgsuccess) );
1002  }
1003  else
1004  {
1005  SCIP_CALL( SCIPtightenVarLb(scip, var, sclb, FALSE, infeas, &bndchgsuccess) );
1006  }
1007  *reduceddom += bndchgsuccess;
1008  if( *infeas )
1009  {
1010  return SCIP_OKAY;
1011  }
1012  }
1013  }
1014 
1015  /* use a non-redundant upper bound */
1016  if( SCIPisLT(scip, scub, SCIPvarGetUbLocal(var)) || (scub <= 0.0 && locub > 0.0) )
1017  {
1018  /* first check for infeasibility */
1019  if( SCIPisFeasLT(scip, scub, SCIPvarGetLbLocal(var)) )
1020  {
1021  SCIP_CALL( SCIPfixVar(scip, indicator, indvalue ? 0.0 : 1.0, infeas, &bndchgsuccess) );
1022  *reduceddom += bndchgsuccess;
1023  if( *infeas )
1024  {
1025  return SCIP_OKAY;
1026  }
1027  }
1028  else if( nlhdlrdata->tightenbounds &&
1029  (SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5) )
1030  {
1031  /* indicator is fixed; due to a previous check, here it can only be fixed to indvalue;
1032  * therefore, scub is valid for the current node
1033  */
1034 
1035  if( indvalue == 0 )
1036  {
1037  assert(sclb == scub); /*lint !e777*/
1038  SCIP_CALL( SCIPfixVar(scip, var, scub, infeas, &bndchgsuccess) );
1039  }
1040  else
1041  {
1042  SCIP_CALL( SCIPtightenVarUb(scip, var, scub, FALSE, infeas, &bndchgsuccess) );
1043  }
1044  *reduceddom += bndchgsuccess;
1045  if( *infeas )
1046  {
1047  return SCIP_OKAY;
1048  }
1049  }
1050  }
1051 
1052  /* If a bound change has been found and indvalue == TRUE, try to use the new bounds.
1053  * This is only done for indvalue == TRUE since this is where enfo asks other nlhdlrs to estimate,
1054  * and at indicator == FALSE we already only have a single point
1055  */
1056  if( doprobing && indvalue && (((scub - sclb) / (locub - loclb)) <= 1.0 - nlhdlrdata->mindomreduction ||
1057  (sclb >= 0.0 && loclb < 0.0) || (scub <= 0.0 && locub > 0.0)) )
1058  {
1059  *probinglb = sclb;
1060  *probingub = scub;
1061  }
1062 
1063  SCIPdebugMsg(scip, "%s in [%g, %g] instead of [%g, %g] (vals0 = %g)\n", SCIPvarGetName(var), sclb, scub,
1064  SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), scvdata->vals0[pos]);
1065 
1066  return SCIP_OKAY;
1067 }
1068 
1069 /** looks for bound tightenings to be applied either in the current node or in probing
1070  *
1071  * Loops through both possible values of indicator and calls analyseVarOnoffBounds().
1072  * Might update the `*doprobing` flag by setting it to `FALSE` if:
1073  * - indicator is fixed or
1074  * - analyseVarOnoffBounds() hasn't found a sufficient improvement at indicator==1.
1075  *
1076  * If `*doprobing==TRUE`, stores bounds suggested by analyseVarOnoffBounds() in order to apply them in probing together
1077  * with the fixing `indicator=1`.
1078  */
1079 static
1081  SCIP* scip, /**< SCIP data structure */
1082  SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
1083  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
1084  SCIP_VAR* indicator, /**< indicator variable */
1085  SCIP_VAR*** probingvars, /**< array to store variables whose bounds will be changed in probing */
1086  SCIP_INTERVAL** probingdoms, /**< array to store bounds to be applied in probing */
1087  int* nprobingvars, /**< pointer to store number of vars whose bounds will be changed in probing */
1088  SCIP_Bool* doprobing, /**< pointer to the flag telling whether we want to do probing */
1089  SCIP_RESULT* result /**< pointer to store the result */
1090  )
1091 {
1092  int v;
1093  SCIP_VAR* var;
1094  SCIP_Bool infeas;
1095  int b;
1096  SCIP_Real probinglb = SCIP_INVALID;
1097  SCIP_Real probingub = SCIP_INVALID;
1098  SCIP_Bool changed;
1099  SCIP_Bool reduceddom;
1100 
1101  assert(indicator != NULL);
1102  assert(nprobingvars != NULL);
1103  assert(doprobing != NULL);
1104  assert(result != NULL);
1105 
1106  changed = FALSE;
1107 
1108  /* no probing if indicator already fixed */
1109  if( SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5 )
1110  {
1111  *doprobing = FALSE;
1112  }
1113 
1114  /* consider each possible value of indicator */
1115  for( b = 0; b < 2; ++b )
1116  {
1117  for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1118  {
1119  /* nothing left to do if indicator is already fixed to !indvalue
1120  * (checked in the inner loop since analyseVarOnoff bounds might fix the indicator)
1121  */
1122  if( (b == 1 && SCIPvarGetUbLocal(indicator) <= 0.5) || (b == 0 && SCIPvarGetLbLocal(indicator) >= 0.5) )
1123  {
1124  *doprobing = FALSE;
1125  break;
1126  }
1127 
1128  var = nlhdlrexprdata->vars[v];
1129 
1130  SCIP_CALL( analyseVarOnoffBounds(scip, nlhdlrdata, var, indicator, b == 1, &infeas, &probinglb,
1131  &probingub, *doprobing, &reduceddom) );
1132 
1133  if( infeas )
1134  {
1135  *result = SCIP_CUTOFF;
1136  *doprobing = FALSE;
1137  return SCIP_OKAY;
1138  }
1139  else if( reduceddom )
1140  {
1141  *result = SCIP_REDUCEDDOM;
1142  }
1143 
1144  if( !(*doprobing) )
1145  continue;
1146 
1147  /* if bounds to be applied in probing have been found, store them */
1148  if( probinglb != SCIP_INVALID ) /*lint !e777*/
1149  {
1150  assert(probingub != SCIP_INVALID); /*lint !e777*/
1151 
1152  SCIP_CALL( SCIPreallocBufferArray(scip, probingvars, *nprobingvars + 1) );
1153  SCIP_CALL( SCIPreallocBufferArray(scip, probingdoms, *nprobingvars + 1) );
1154  (*probingvars)[*nprobingvars] = var;
1155  (*probingdoms)[*nprobingvars].inf = probinglb;
1156  (*probingdoms)[*nprobingvars].sup = probingub;
1157  ++*nprobingvars;
1158 
1159  changed = TRUE;
1160  }
1161  }
1162  }
1163 
1164  if( !changed )
1165  {
1166  *doprobing = FALSE;
1167  }
1168 
1169  return SCIP_OKAY;
1170 }
1171 
1172 /** saves local bounds on all expression variables, including auxiliary variables, obtained from propagating
1173  * indicator == 1 to the corresponding SCVARDATA (should only be used in the root node)
1174  */
1175 static
1177  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
1178  SCIP_HASHMAP* scvars, /**< hashmap with semicontinuous variables */
1179  SCIP_VAR* indicator /**< indicator variable */
1180  )
1181 {
1182  int v;
1183  SCIP_VAR* var;
1184  SCVARDATA* scvdata;
1185  int pos;
1186  SCIP_Real lb;
1187  SCIP_Real ub;
1188 
1189  for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1190  {
1191  var = nlhdlrexprdata->vars[v];
1192  lb = SCIPvarGetLbLocal(var);
1193  ub = SCIPvarGetUbLocal(var);
1194  scvdata = getSCVarDataInd(scvars, var, indicator, &pos);
1195 
1196  if( scvdata != NULL )
1197  {
1198  scvdata->lbs1[pos] = MAX(scvdata->lbs1[pos], lb);
1199  scvdata->ubs1[pos] = MIN(scvdata->ubs1[pos], ub);
1200  }
1201  }
1202 
1203  return SCIP_OKAY;
1204 }
1205 
1206 /*
1207  * Callback methods of nonlinear handler
1208  */
1209 
1210 /** nonlinear handler copy callback */
1211 static
1212 SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrPerspective)
1213 { /*lint --e{715}*/
1214  assert(targetscip != NULL);
1215  assert(sourcenlhdlr != NULL);
1216  assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), NLHDLR_NAME) == 0);
1217 
1218  SCIP_CALL( SCIPincludeNlhdlrPerspective(targetscip) );
1219 
1220  return SCIP_OKAY;
1221 }
1222 
1223 
1224 /** callback to free data of handler */
1225 static
1226 SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrFreehdlrdataPerspective)
1227 { /*lint --e{715}*/
1228  SCIPfreeBlockMemory(scip, nlhdlrdata);
1229 
1230  return SCIP_OKAY;
1231 }
1232 
1233 
1234 /** callback to free expression specific data */
1235 static
1236 SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataPerspective)
1237 { /*lint --e{715}*/
1238  SCIP_CALL( freeNlhdlrExprData(scip, *nlhdlrexprdata) );
1239  SCIPfreeBlockMemory(scip, nlhdlrexprdata);
1240 
1241  return SCIP_OKAY;
1242 }
1243 
1244 /** callback to be called in initialization */
1245 #if 0
1246 static
1247 SCIP_DECL_NLHDLRINIT(nlhdlrInitPerspective)
1248 { /*lint --e{715}*/
1249  return SCIP_OKAY;
1250 }
1251 #endif
1252 
1253 /** callback to be called in deinitialization */
1254 static
1255 SCIP_DECL_NLHDLREXIT(nlhdlrExitPerspective)
1256 { /*lint --e{715}*/
1257  SCIP_HASHMAPENTRY* entry;
1258  SCVARDATA* data;
1259  int c;
1260  SCIP_NLHDLRDATA* nlhdlrdata;
1261 
1262  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1263  assert(nlhdlrdata != NULL);
1264 
1265  if( nlhdlrdata->scvars != NULL )
1266  {
1267  for( c = 0; c < SCIPhashmapGetNEntries(nlhdlrdata->scvars); ++c )
1268  {
1269  entry = SCIPhashmapGetEntry(nlhdlrdata->scvars, c);
1270  if( entry != NULL )
1271  {
1272  data = (SCVARDATA*) SCIPhashmapEntryGetImage(entry);
1273  SCIPfreeBlockMemoryArray(scip, &data->ubs1, data->bndssize);
1274  SCIPfreeBlockMemoryArray(scip, &data->lbs1, data->bndssize);
1275  SCIPfreeBlockMemoryArray(scip, &data->vals0, data->bndssize);
1276  SCIPfreeBlockMemoryArray(scip, &data->bvars, data->bndssize);
1277  SCIPfreeBlockMemory(scip, &data);
1278  }
1279  }
1280  SCIPhashmapFree(&nlhdlrdata->scvars);
1281  assert(nlhdlrdata->scvars == NULL);
1282  }
1283 
1284  return SCIP_OKAY;
1285 }
1286 
1287 /** callback to detect structure in expression tree
1288  *
1289  * We are looking for expressions g(x), where x is a vector of semicontinuous variables that all share at least one
1290  * indicator variable.
1291  */
1292 static
1293 SCIP_DECL_NLHDLRDETECT(nlhdlrDetectPerspective)
1294 { /*lint --e{715}*/
1295  SCIP_NLHDLRDATA* nlhdlrdata;
1296  SCIP_EXPR** varexprs;
1297  SCIP_Bool success = FALSE;
1298  int i;
1299  SCIP_Bool hassepabelow = FALSE;
1300  SCIP_Bool hassepaabove = FALSE;
1301  SCIP_Bool hasnondefault = FALSE;
1302 
1303  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1304 
1305  assert(scip != NULL);
1306  assert(nlhdlr != NULL);
1307  assert(expr != NULL);
1308  assert(participating != NULL);
1309  assert(enforcing != NULL);
1310  assert(nlhdlrexprdata != NULL);
1311  assert(nlhdlrdata != NULL);
1312 
1313  /* do not run if we will have no auxvar to add a cut for */
1314  if( SCIPgetExprNAuxvarUsesNonlinear(expr) == 0 )
1315  return SCIP_OKAY;
1316 
1317  if( SCIPgetNBinVars(scip) == 0 )
1318  {
1319  SCIPdebugMsg(scip, "problem has no binary variables, not running perspective detection\n");
1320  return SCIP_OKAY;
1321  }
1322 
1323  for( i = 0; i < SCIPgetExprNEnfosNonlinear(expr); ++i )
1324  {
1325  SCIP_NLHDLR* nlhdlr2;
1326  SCIP_NLHDLR_METHOD nlhdlr2participates;
1327  SCIP_Bool sepabelowusesactivity;
1328  SCIP_Bool sepaaboveusesactivity;
1329  SCIPgetExprEnfoDataNonlinear(expr, i, &nlhdlr2, NULL, &nlhdlr2participates, &sepabelowusesactivity, &sepaaboveusesactivity, NULL);
1330 
1331  if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPABOTH) == 0 )
1332  continue;
1333 
1334  if( !SCIPnlhdlrHasEstimate(nlhdlr2) )
1335  continue;
1336 
1337  if( strcmp(SCIPnlhdlrGetName(nlhdlr2), "default") != 0 )
1338  hasnondefault = TRUE;
1339 
1340  /* If we are supposed to run only on convex expressions, than check whether there is a nlhdlr
1341  * that participates in separation without using activity for it. Otherwise, check for
1342  * participation regardless of activity usage.
1343  */
1344  if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPABELOW) && (!nlhdlrdata->convexonly || !sepabelowusesactivity) )
1345  hassepabelow = TRUE;
1346 
1347  if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPAABOVE) && (!nlhdlrdata->convexonly || !sepaaboveusesactivity) )
1348  hassepaabove = TRUE;
1349  }
1350 
1351  /* If a sum expression is handled only by default nlhdlr, then all the children will have auxiliary vars.
1352  * Since the sum will then be linear in auxiliary variables, perspective can't improve anything for it
1353  */
1354  if( SCIPisExprSum(scip, expr) && !hasnondefault )
1355  {
1356  SCIPdebugMsg(scip, "sum expr only has default exprhdlr, not running perspective detection\n");
1357  return SCIP_OKAY;
1358  }
1359 
1360  /* If no other nlhdlr separates, neither does perspective (if convexonly, only separation
1361  * without using activity counts)
1362  */
1363  if( !hassepabelow && !hassepaabove )
1364  {
1365  SCIPdebugMsg(scip, "no nlhdlr separates without using activity, not running perspective detection\n");
1366  return SCIP_OKAY;
1367  }
1368 
1369 #ifdef SCIP_DEBUG
1370  SCIPdebugMsg(scip, "Called perspective detect, expr = %p: ", (void*)expr);
1371  SCIPprintExpr(scip, expr, NULL);
1372  SCIPdebugMsgPrint(scip, "\n");
1373 #endif
1374 
1375  /* allocate memory */
1376  SCIP_CALL( SCIPallocClearBlockMemory(scip, nlhdlrexprdata) );
1377  if( nlhdlrdata->scvars == NULL )
1378  {
1379  SCIP_CALL( SCIPhashmapCreate(&(nlhdlrdata->scvars), SCIPblkmem(scip), SCIPgetNVars(scip)) );
1380  }
1381 
1382  /* save varexprs to nlhdlrexprdata */
1383  SCIP_CALL( SCIPgetExprNVars(scip, expr, &(*nlhdlrexprdata)->nvars) );
1384  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->vars, (*nlhdlrexprdata)->nvars) );
1385  SCIP_CALL( SCIPallocBufferArray(scip, &varexprs, (*nlhdlrexprdata)->nvars) );
1386  (*nlhdlrexprdata)->varssize = (*nlhdlrexprdata)->nvars;
1387  SCIP_CALL( SCIPgetExprVarExprs(scip, expr, varexprs, &(*nlhdlrexprdata)->nvars) );
1388  for( i = 0; i < (*nlhdlrexprdata)->nvars; ++i )
1389  {
1390  (*nlhdlrexprdata)->vars[i] = SCIPgetVarExprVar(varexprs[i]);
1391  SCIP_CALL( SCIPreleaseExpr(scip, &varexprs[i]) );
1392  SCIP_CALL( SCIPcaptureVar(scip, (*nlhdlrexprdata)->vars[i]) );
1393  }
1394  SCIPsortPtr((void**) (*nlhdlrexprdata)->vars, SCIPvarComp, (*nlhdlrexprdata)->nvars);
1395  SCIPfreeBufferArray(scip, &varexprs);
1396 
1397  /* check if expr is semicontinuous and save indicator variables */
1398  SCIP_CALL( exprIsSemicontinuous(scip, nlhdlrdata, *nlhdlrexprdata, expr, &success) );
1399 
1400  if( success )
1401  {
1402  assert(*nlhdlrexprdata != NULL);
1403  assert((*nlhdlrexprdata)->nindicators > 0);
1404 
1405  if( hassepaabove )
1406  *participating |= SCIP_NLHDLR_METHOD_SEPAABOVE;
1407  if( hassepabelow )
1408  *participating |= SCIP_NLHDLR_METHOD_SEPABELOW;
1409 
1410 #ifdef SCIP_DEBUG
1411  SCIPinfoMessage(scip, NULL, "detected an on/off expr: ");
1412  SCIPprintExpr(scip, expr, NULL);
1413  SCIPinfoMessage(scip, NULL, "\n");
1414 #endif
1415  }
1416  else
1417  {
1418  assert(*nlhdlrexprdata != NULL);
1419  SCIP_CALL( nlhdlrFreeExprDataPerspective(scip, nlhdlr, expr, nlhdlrexprdata) );
1420  }
1421 
1422  return SCIP_OKAY;
1423 }
1424 
1425 
1426 /** auxiliary evaluation callback of nonlinear handler */
1427 static
1428 SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxPerspective)
1429 { /*lint --e{715}*/
1430  int e;
1431  SCIP_Real maxdiff;
1432  SCIP_Real auxvarvalue;
1433  SCIP_Real enfoauxval;
1434 
1435  assert(scip != NULL);
1436  assert(expr != NULL);
1437  assert(auxvalue != NULL);
1438 
1439  auxvarvalue = SCIPgetSolVal(scip, sol, SCIPgetExprAuxVarNonlinear(expr));
1440  maxdiff = 0.0;
1441  *auxvalue = auxvarvalue;
1442 
1443  /* use the auxvalue from one of the other nlhdlrs that estimates for this expr: take the one that is farthest
1444  * from the current value of auxvar
1445  */
1446  for( e = 0; e < SCIPgetExprNEnfosNonlinear(expr); ++e )
1447  {
1448  SCIP_NLHDLR* nlhdlr2;
1449  SCIP_NLHDLREXPRDATA* nlhdlr2exprdata;
1450  SCIP_NLHDLR_METHOD nlhdlr2participation;
1451 
1452  SCIPgetExprEnfoDataNonlinear(expr, e, &nlhdlr2, &nlhdlr2exprdata, &nlhdlr2participation, NULL, NULL, NULL);
1453 
1454  /* skip nlhdlr that do not participate or do not provide estimate */
1455  if( (nlhdlr2participation & SCIP_NLHDLR_METHOD_SEPABOTH) == 0 || !SCIPnlhdlrHasEstimate(nlhdlr2) )
1456  continue;
1457 
1458  SCIP_CALL( SCIPnlhdlrEvalaux(scip, nlhdlr2, expr, nlhdlr2exprdata, &enfoauxval, sol) );
1459 
1460  SCIPsetExprEnfoAuxValueNonlinear(expr, e, enfoauxval);
1461 
1462  if( REALABS(enfoauxval - auxvarvalue) > maxdiff && enfoauxval != SCIP_INVALID ) /*lint !e777*/
1463  {
1464  maxdiff = REALABS(enfoauxval - auxvarvalue);
1465  *auxvalue = enfoauxval;
1466  }
1467  }
1468 
1469  return SCIP_OKAY;
1470 }
1471 
1472 /** separation initialization method of a nonlinear handler */
1473 static
1474 SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaPerspective)
1475 { /*lint --e{715}*/
1476  int sindicators;
1477 
1478  sindicators = nlhdlrexprdata->nindicators;
1479 
1480  /* compute 'off' values of expr and subexprs (and thus auxvars too) */
1481  SCIP_CALL( computeOffValues(scip, SCIPnlhdlrGetData(nlhdlr), nlhdlrexprdata, expr) );
1482 
1483  /* some indicator variables might have been removed if evaluation failed, check how many remain */
1484  if( nlhdlrexprdata->nindicators == 0 )
1485  {
1486  SCIPfreeBlockMemoryArray(scip, &nlhdlrexprdata->indicators, sindicators);
1487  SCIPfreeBlockMemoryArray(scip, &nlhdlrexprdata->exprvals0, sindicators);
1488  }
1489  else if( nlhdlrexprdata->nindicators < sindicators )
1490  {
1491  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->indicators, sindicators, nlhdlrexprdata->nindicators) );
1492  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->exprvals0, sindicators, nlhdlrexprdata->nindicators) );
1493  }
1494 
1495  return SCIP_OKAY;
1496 }
1497 
1498 
1499 #if 0
1500 /** separation deinitialization method of a nonlinear handler (called during CONSEXITSOL) */
1501 static
1502 SCIP_DECL_NLHDLREXITSEPA(nlhdlrExitSepaPerspective)
1503 { /*lint --e{715}*/
1504  SCIPerrorMessage("method of perspective nonlinear handler not implemented yet\n");
1505  SCIPABORT(); /*lint --e{527}*/
1506 
1507  return SCIP_OKAY;
1508 }
1509 #endif
1510 
1511 /** nonlinear handler enforcement callback
1512  *
1513  * "Perspectivies" cuts produced by other nonlinear handlers.
1514  *
1515  * Suppose that we want to separate \f$x\f$ from the set \f$\{ x : g(x) \leq 0\}\f$.
1516  * If \f$g(x) = g^0\f$ if indicator \f$z = 0\f$, and a cut is given by \f$\sum_i a_ix_i + c \leq \text{aux}\f$, where \f$x_i = x_i^0\f$ if \f$z = 0\f$ for all \f$i\f$,
1517  * then the "perspectivied" cut is \f[\sum_i a_ix_i + c + (1 - z)\,(g^0 - c - \sum_i a_ix_i^0) \leq \text{aux}.\f]
1518  * This ensures that at \f$z = 1\f$, the new cut is equivalent to the given cut, and at \f$z = 0\f$ it reduces to \f$g^0 \leq \text{aux}\f$.
1519  */
1520 static
1521 SCIP_DECL_NLHDLRENFO(nlhdlrEnfoPerspective)
1522 { /*lint --e{715}*/
1523  SCIP_ROWPREP* rowprep;
1524  SCIP_VAR* auxvar;
1525  int i;
1526  int j;
1527  SCIP_NLHDLRDATA* nlhdlrdata;
1528  SCIP_Real cst0;
1529  SCIP_VAR* indicator;
1530  SCIP_PTRARRAY* rowpreps2;
1531  SCIP_PTRARRAY* rowpreps;
1532  int nrowpreps;
1533  SCIP_SOL* solcopy;
1534  SCIP_Bool doprobing;
1535  SCIP_BOOLARRAY* addedbranchscores2;
1536  SCIP_Bool stop;
1537  int nenfos;
1538  int* enfoposs;
1539  SCIP_SOL* soladj;
1540  int pos;
1541  SCVARDATA* scvdata;
1542 
1543  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1544 
1545 #ifdef SCIP_DEBUG
1546  SCIPinfoMessage(scip, NULL, "enforcement method of perspective nonlinear handler called for expr %p: ", (void*)expr);
1547  SCIP_CALL( SCIPprintExpr(scip, expr, NULL) );
1548  SCIPinfoMessage(scip, NULL, " at\n");
1549  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
1550  {
1551  SCIPinfoMessage(scip, NULL, "%s = %g\n", SCIPvarGetName(nlhdlrexprdata->vars[i]),
1552  SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]));
1553  }
1556 #endif
1557 
1558  assert(scip != NULL);
1559  assert(expr != NULL);
1560  assert(conshdlr != NULL);
1561  assert(nlhdlrexprdata != NULL);
1562  assert(nlhdlrdata != NULL);
1563 
1564  if( nlhdlrexprdata->nindicators == 0 )
1565  {
1566  /* we might have removed all indicators in initsepa */
1567  *result = SCIP_DIDNOTRUN;
1568  return SCIP_OKAY;
1569  }
1570 
1571  auxvar = SCIPgetExprAuxVarNonlinear(expr);
1572  assert(auxvar != NULL);
1573 
1574  /* detect should have picked only those expressions for which at least one other nlhdlr can enforce */
1575  assert(SCIPgetExprNEnfosNonlinear(expr) > 1);
1576 
1578 
1579  doprobing = FALSE;
1580  nenfos = 0;
1581  soladj = NULL;
1582 
1583  /* find suitable nlhdlrs and check if there is enough violation to do probing */
1584  for( j = 0; j < SCIPgetExprNEnfosNonlinear(expr); ++j )
1585  {
1586  SCIP_NLHDLR* nlhdlr2;
1587  SCIP_NLHDLREXPRDATA* nlhdlr2exprdata;
1588  SCIP_NLHDLR_METHOD nlhdlr2participate;
1589  SCIP_Real nlhdlr2auxvalue;
1590  SCIP_Real violation;
1591  SCIP_Bool violbelow;
1592  SCIP_Bool violabove;
1593  SCIP_Bool sepausesactivity = FALSE;
1594 
1595  SCIPgetExprEnfoDataNonlinear(expr, j, &nlhdlr2, &nlhdlr2exprdata, &nlhdlr2participate, !overestimate ? &sepausesactivity : NULL, overestimate ? &sepausesactivity: NULL, &nlhdlr2auxvalue); /*lint !e826*/
1596 
1597  if( nlhdlr2 == nlhdlr )
1598  continue;
1599 
1600  /* if nlhdlr2 cannot estimate, then cannot use it */
1601  if( !SCIPnlhdlrHasEstimate(nlhdlr2) )
1602  continue;
1603 
1604  /* if nlhdlr2 does not participate in the separation on the desired side (overestimate), then skip it */
1605  if( (nlhdlr2participate & (overestimate ? SCIP_NLHDLR_METHOD_SEPAABOVE : SCIP_NLHDLR_METHOD_SEPABELOW)) == 0 )
1606  continue;
1607 
1608  /* if only working on convex-looking expressions, then skip nlhdlr if it uses activity for estimates */
1609  if( nlhdlrdata->convexonly && sepausesactivity )
1610  continue;
1611 
1612  /* evalaux should have called evalaux of nlhdlr2 by now
1613  * check whether handling the violation for nlhdlr2 requires under- or overestimation and this fits to
1614  * overestimate flag
1615  */
1616  SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, nlhdlr2auxvalue, sol, &violation, &violbelow,
1617  &violabove) );
1618  assert(violation >= 0.0);
1619 
1620  if( (overestimate && !violabove) || (!overestimate && !violbelow) )
1621  continue;
1622 
1623  /* if violation is small, cuts would likely be weak - skip perspectification */
1624  if( !allowweakcuts && violation < SCIPfeastol(scip) )
1625  continue;
1626 
1627  enfoposs[nenfos] = j;
1628  ++nenfos;
1629 
1630  /* enable probing if tightening the domain could be useful for nlhdlr and violation is above threshold */
1631  if( sepausesactivity && violation >= nlhdlrdata->minviolprobing )
1632  doprobing = TRUE;
1633  }
1634 
1635  if( nenfos == 0 )
1636  {
1637  *result = SCIP_DIDNOTRUN;
1638  SCIPfreeBufferArray(scip, &enfoposs);
1639  return SCIP_OKAY;
1640  }
1641 
1642  /* check probing frequency against depth in b&b tree */
1643  if( nlhdlrdata->probingfreq == -1 || (nlhdlrdata->probingfreq == 0 && SCIPgetDepth(scip) != 0) ||
1644  (nlhdlrdata->probingfreq > 0 && SCIPgetDepth(scip) % nlhdlrdata->probingfreq != 0) )
1645  doprobing = FALSE;
1646 
1647  /* if addbranchscores is TRUE, then we can assume to be in enforcement and not in separation */
1648  if( nlhdlrdata->probingonlyinsepa && addbranchscores )
1649  doprobing = FALSE;
1650 
1651  /* disable probing if already being in probing or if in a subscip */
1652  if( SCIPinProbing(scip) || SCIPgetSubscipDepth(scip) != 0 )
1653  doprobing = FALSE;
1654 
1655  nrowpreps = 0;
1656  *result = SCIP_DIDNOTFIND;
1657  solcopy = sol;
1658  stop = FALSE;
1659 
1660  SCIP_CALL( SCIPcreatePtrarray(scip, &rowpreps2) );
1661  SCIP_CALL( SCIPcreatePtrarray(scip, &rowpreps) );
1662  SCIP_CALL( SCIPcreateBoolarray(scip, &addedbranchscores2) );
1663 
1664  /* build cuts for every indicator variable */
1665  for( i = 0; i < nlhdlrexprdata->nindicators && !stop; ++i )
1666  {
1667  int v;
1668  int minidx;
1669  int maxidx;
1670  int r;
1671  SCIP_VAR** probingvars;
1672  SCIP_INTERVAL* probingdoms;
1673  int nprobingvars;
1674  SCIP_Bool doprobingind;
1675  SCIP_Real indval;
1676  SCIP_Real solval;
1677  SCIP_Bool adjrefpoint;
1678 
1679  indicator = nlhdlrexprdata->indicators[i];
1680  probingvars = NULL;
1681  probingdoms = NULL;
1682  nprobingvars = 0;
1683  doprobingind = doprobing;
1684  solval = SCIPgetSolVal(scip, solcopy, indicator);
1685  adjrefpoint = nlhdlrdata->adjrefpoint && !SCIPisFeasEQ(scip, solval, 1.0);
1686 
1687  SCIP_CALL( analyseOnoffBounds(scip, nlhdlrdata, nlhdlrexprdata, indicator, &probingvars, &probingdoms,
1688  &nprobingvars, &doprobingind, result) );
1689 
1690  /* don't add perspective cuts for fixed indicators since there is no use for perspectivy */
1691  if( SCIPvarGetLbLocal(indicator) >= 0.5 )
1692  {
1693  assert(!doprobingind);
1694  continue;
1695  }
1696  if( SCIPvarGetUbLocal(indicator) <= 0.5 )
1697  { /* this case is stronger as it implies that everything is fixed;
1698  * therefore we are now happy
1699  */
1700  assert(!doprobingind);
1701  SCIPfreeBufferArrayNull(scip, &probingvars);
1702  SCIPfreeBufferArrayNull(scip, &probingdoms);
1703  goto TERMINATE;
1704  }
1705 
1706  if( doprobingind )
1707  {
1708  SCIP_Bool propagate;
1709  SCIP_Bool cutoff_probing;
1710  SCIP_Bool cutoff;
1711  SCIP_Bool fixed;
1712 
1713 #ifndef NDEBUG
1714  SCIP_Real* solvals;
1715  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nlhdlrexprdata->nvars) );
1716  for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1717  {
1718  solvals[v] = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[v]);
1719  }
1720 #endif
1721 
1722  propagate = SCIPgetDepth(scip) == 0;
1723 
1724  SCIP_CALL( startProbing(scip, nlhdlrdata, nlhdlrexprdata, indicator, probingvars, probingdoms, nprobingvars,
1725  sol, &solcopy, &cutoff_probing) );
1726 
1727 #ifndef NDEBUG
1728  for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1729  {
1730  assert(solvals[v] == SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->vars[v])); /*lint !e777*/
1731  }
1732  SCIPfreeBufferArray(scip, &solvals);
1733 #endif
1734 
1735  SCIPfreeBufferArrayNull(scip, &probingvars);
1736  SCIPfreeBufferArrayNull(scip, &probingdoms);
1737 
1738  if( propagate )
1739  { /* we are in the root node and startProbing did propagation */
1740  /* probing propagation might have detected infeasibility */
1741  if( cutoff_probing )
1742  {
1743  /* indicator == 1 is infeasible -> set indicator to 0 */
1744 
1746 
1747  SCIP_CALL( SCIPfixVar(scip, indicator, 0.0, &cutoff, &fixed) );
1748 
1749  if( cutoff )
1750  {
1751  *result = SCIP_CUTOFF;
1752  goto TERMINATE;
1753  }
1754 
1755  continue;
1756  }
1757 
1758  /* probing propagation in the root node can provide better on/off bounds */
1759  SCIP_CALL( tightenOnBounds(nlhdlrexprdata, nlhdlrdata->scvars, indicator) );
1760  }
1761  }
1762 
1763  if( adjrefpoint )
1764  {
1765  /* make sure that when we adjust the point, we don't divide by something too close to 0.0 */
1766  indval = MAX(solval, 0.1);
1767 
1768  /* create an adjusted point x^adj = (x* - x0) / z* + x0 */
1769  SCIP_CALL( SCIPcreateSol(scip, &soladj, NULL) );
1770  for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1771  {
1772  if( SCIPvarGetStatus(nlhdlrexprdata->vars[v]) == SCIP_VARSTATUS_FIXED )
1773  continue;
1774 
1775  scvdata = getSCVarDataInd(nlhdlrdata->scvars, nlhdlrexprdata->vars[v], indicator, &pos);
1776 
1777  /* a non-semicontinuous variable must be linear in expr; skip it */
1778  if( scvdata == NULL )
1779  continue;
1780 
1781  SCIP_CALL( SCIPsetSolVal(scip, soladj, nlhdlrexprdata->vars[v],
1782  (SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->vars[v]) - scvdata->vals0[pos]) / indval
1783  + scvdata->vals0[pos]) );
1784  }
1785  for( v = 0; v < nlhdlrexprdata->nindicators; ++v )
1786  {
1787  if( SCIPvarGetStatus(nlhdlrexprdata->indicators[v]) == SCIP_VARSTATUS_FIXED )
1788  continue;
1789 
1790  SCIP_CALL( SCIPsetSolVal(scip, soladj, nlhdlrexprdata->indicators[v],
1791  SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->indicators[v])) );
1792  }
1793  if( SCIPvarGetStatus(auxvar) != SCIP_VARSTATUS_FIXED )
1794  {
1795  SCIP_CALL( SCIPsetSolVal(scip, soladj, auxvar, SCIPgetSolVal(scip, solcopy, auxvar)) );
1796  }
1797  }
1798 
1799  /* use cuts from every suitable nlhdlr */
1800  for( j = 0; j < nenfos; ++j )
1801  {
1802  SCIP_Bool addedbranchscores2j;
1803  SCIP_NLHDLR* nlhdlr2;
1804  SCIP_NLHDLREXPRDATA* nlhdlr2exprdata;
1805  SCIP_Real nlhdlr2auxvalue;
1806  SCIP_Bool success2;
1807 
1808  SCIPgetExprEnfoDataNonlinear(expr, enfoposs[j], &nlhdlr2, &nlhdlr2exprdata, NULL, NULL, NULL, &nlhdlr2auxvalue);
1809  assert(SCIPnlhdlrHasEstimate(nlhdlr2) && nlhdlr2 != nlhdlr);
1810 
1811  SCIPdebugMsg(scip, "asking nonlinear handler %s to %sestimate\n", SCIPnlhdlrGetName(nlhdlr2), overestimate ? "over" : "under");
1812 
1813  /* ask the nonlinear handler for an estimator */
1814  if( adjrefpoint )
1815  {
1816  SCIP_CALL( SCIPnlhdlrEvalaux(scip, nlhdlr2, expr, nlhdlr2exprdata, &nlhdlr2auxvalue, soladj) );
1817 
1818  /* coverity[copy_paste_error] */
1819  SCIP_CALL( SCIPnlhdlrEstimate(scip, conshdlr, nlhdlr2, expr,
1820  nlhdlr2exprdata, soladj,
1821  nlhdlr2auxvalue, overestimate, SCIPgetSolVal(scip, solcopy, auxvar),
1822  FALSE, rowpreps2, &success2, &addedbranchscores2j) );
1823  }
1824  else
1825  {
1826  SCIP_CALL( SCIPnlhdlrEstimate(scip, conshdlr, nlhdlr2, expr,
1827  nlhdlr2exprdata, solcopy,
1828  nlhdlr2auxvalue, overestimate, SCIPgetSolVal(scip, solcopy, auxvar),
1829  FALSE, rowpreps2, &success2, &addedbranchscores2j) );
1830  }
1831 
1832  minidx = SCIPgetPtrarrayMinIdx(scip, rowpreps2);
1833  maxidx = SCIPgetPtrarrayMaxIdx(scip, rowpreps2);
1834 
1835  assert((success2 && minidx <= maxidx) || (!success2 && minidx > maxidx));
1836 
1837  /* perspectivy all cuts from nlhdlr2 and add them to rowpreps */
1838  for( r = minidx; r <= maxidx; ++r )
1839  {
1840  SCIP_Real maxcoef;
1841  SCIP_Real* rowprepcoefs;
1842  SCIP_VAR** rowprepvars;
1843 
1844  rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps2, r);
1845  assert(rowprep != NULL);
1846 
1847 #ifdef SCIP_DEBUG
1848  SCIPinfoMessage(scip, NULL, "rowprep for expr ");
1849  SCIPprintExpr(scip, expr, NULL);
1850  SCIPinfoMessage(scip, NULL, "rowprep before perspectivy is: \n");
1851  SCIPprintRowprep(scip, rowprep, NULL);
1852 #endif
1853 
1854  /* given a rowprep: sum aixi + sum biyi + c, where xi are semicontinuous variables and yi are
1855  * non-semicontinuous variables (which appear in expr linearly, which detect must have ensured),
1856  * perspectivy the semicontinuous part by adding (1-z)(g0 - c - sum aix0i) (the constant is
1857  * treated as belonging to the semicontinuous part)
1858  */
1859 
1860  /* we want cst0 = g0 - c - sum aix0i; first add g0 - c */
1861  cst0 = nlhdlrexprdata->exprvals0[i] + SCIProwprepGetSide(rowprep);
1862 
1863  maxcoef = 0.0;
1864  rowprepcoefs = SCIProwprepGetCoefs(rowprep);
1865  rowprepvars = SCIProwprepGetVars(rowprep);
1866 
1867  for( v = 0; v < SCIProwprepGetNVars(rowprep); ++v )
1868  {
1869  if( REALABS( rowprepcoefs[v]) > maxcoef )
1870  {
1871  maxcoef = REALABS(rowprepcoefs[v]);
1872  }
1873 
1874  scvdata = getSCVarDataInd(nlhdlrdata->scvars, rowprepvars[v], indicator, &pos);
1875 
1876  /* a non-semicontinuous variable must be linear in expr; skip it */
1877  if( scvdata == NULL )
1878  continue;
1879 
1880  cst0 -= rowprepcoefs[v] * scvdata->vals0[pos];
1881  }
1882 
1883  /* only perspectivy when the absolute value of cst0 is not too small
1884  * TODO on ex1252a there was cst0=0 - ok to still use the cut?
1885  */
1886  if( cst0 == 0.0 || maxcoef / REALABS(cst0) <= 10.0 / SCIPfeastol(scip) )
1887  {
1888  /* update the rowprep by adding cst0 - cst0*z */
1889  SCIProwprepAddConstant(rowprep, cst0);
1890  SCIP_CALL(SCIPaddRowprepTerm(scip, rowprep, indicator, -cst0));
1891  }
1892  else
1893  {
1894  SCIPfreeRowprep(scip, &rowprep);
1895  continue;
1896  }
1897 
1898  SCIP_CALL(SCIPaddRowprepTerm(scip, rowprep, auxvar, -1.0));
1899 
1900  SCIPdebugMsg(scip, "rowprep after perspectivy is: \n");
1901 #ifdef SCIP_DEBUG
1902  SCIPprintRowprep(scip, rowprep, NULL);
1903 #endif
1904 
1905  SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, nrowpreps, rowprep) );
1906  SCIP_CALL( SCIPsetBoolarrayVal(scip, addedbranchscores2, nrowpreps, addedbranchscores2j) );
1907  ++nrowpreps;
1908  }
1909 
1910  SCIP_CALL( SCIPclearPtrarray(scip, rowpreps2) );
1911  }
1912 
1913  if( adjrefpoint )
1914  {
1915  SCIP_CALL( SCIPfreeSol(scip, &soladj) );
1916  }
1917 
1918  if( doprobingind )
1919  {
1921  }
1922 
1923  /* add all cuts found for indicator i */
1924  for( r = SCIPgetPtrarrayMinIdx(scip, rowpreps); r <= SCIPgetPtrarrayMaxIdx(scip, rowpreps) && !stop; ++r )
1925  {
1926  SCIP_RESULT resultr;
1927 
1928 #ifdef SCIP_DEBUG
1929  SCIPprintRowprep(scip, rowprep, NULL);
1930 #endif
1931  rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps, r);
1932  resultr = SCIP_DIDNOTFIND;
1933 
1934  (void) strcat(SCIProwprepGetName(rowprep), "_persp_indicator_");
1935  (void) strcat(SCIProwprepGetName(rowprep), SCIPvarGetName(indicator));
1936 
1937  SCIP_CALL( SCIPprocessRowprepNonlinear(scip, nlhdlr, cons, expr, rowprep, overestimate, auxvar, auxvalue,
1938  allowweakcuts, SCIPgetBoolarrayVal(scip, addedbranchscores2, r), FALSE, solcopy, &resultr) );
1939 
1940  if( resultr == SCIP_SEPARATED )
1941  *result = SCIP_SEPARATED;
1942  else if( resultr == SCIP_CUTOFF )
1943  {
1944  *result = SCIP_CUTOFF;
1945  stop = TRUE;
1946  }
1947  else if( resultr == SCIP_BRANCHED )
1948  {
1949  if( *result != SCIP_SEPARATED && *result != SCIP_REDUCEDDOM )
1950  *result = SCIP_BRANCHED;
1951  }
1952  else if( resultr != SCIP_DIDNOTFIND )
1953  {
1954  SCIPerrorMessage("estimate called by perspective nonlinear handler returned invalid result <%d>\n", resultr);
1955  return SCIP_INVALIDRESULT;
1956  }
1957  }
1958 
1959  /* free all rowpreps for indicator i */
1960  for( r = SCIPgetPtrarrayMinIdx(scip, rowpreps); r <= SCIPgetPtrarrayMaxIdx(scip, rowpreps); ++r )
1961  {
1962  rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps, r);
1963  SCIPfreeRowprep(scip, &rowprep);
1964  }
1965 
1966  SCIP_CALL( SCIPclearPtrarray(scip, rowpreps) );
1967  }
1968 
1969 TERMINATE:
1970  SCIP_CALL( SCIPfreeBoolarray(scip, &addedbranchscores2) );
1971  SCIP_CALL( SCIPfreePtrarray(scip, &rowpreps) );
1972  SCIP_CALL( SCIPfreePtrarray(scip, &rowpreps2) );
1973  if( solcopy != sol )
1974  {
1975  SCIP_CALL( SCIPfreeSol(scip, &solcopy) );
1976  }
1977  SCIPfreeBufferArray(scip, &enfoposs);
1978 
1979  return SCIP_OKAY;
1980 }
1981 
1982 
1983 /*
1984  * nonlinear handler specific interface methods
1985  */
1986 
1987 /** includes perspective nonlinear handler in nonlinear constraint handler */
1989  SCIP* scip /**< SCIP data structure */
1990  )
1991 {
1992  SCIP_NLHDLRDATA* nlhdlrdata;
1993  SCIP_NLHDLR* nlhdlr;
1994 
1995  assert(scip != NULL);
1996 
1997  /* create nonlinear handler data */
1998  SCIP_CALL( SCIPallocBlockMemory(scip, &nlhdlrdata) );
1999  BMSclearMemory(nlhdlrdata);
2000 
2002  NLHDLR_ENFOPRIORITY, nlhdlrDetectPerspective, nlhdlrEvalauxPerspective, nlhdlrdata) );
2003  assert(nlhdlr != NULL);
2004 
2005  SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/maxproprounds",
2006  "maximal number of propagation rounds in probing",
2007  &nlhdlrdata->maxproprounds, FALSE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX, NULL, NULL) );
2008 
2009  SCIP_CALL( SCIPaddRealParam(scip, "nlhdlr/" NLHDLR_NAME "/mindomreduction",
2010  "minimal relative reduction in a variable's domain for applying probing",
2011  &nlhdlrdata->mindomreduction, FALSE, DEFAULT_MINDOMREDUCTION, 0.0, 1.0, NULL, NULL) );
2012 
2013  SCIP_CALL( SCIPaddRealParam(scip, "nlhdlr/" NLHDLR_NAME "/minviolprobing",
2014  "minimal violation w.r.t. auxiliary variables for applying probing",
2015  &nlhdlrdata->minviolprobing, FALSE, DEFAULT_MINVIOLPROBING, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2016 
2017  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/probingonlyinsepa",
2018  "whether to do probing only in separation",
2019  &nlhdlrdata->probingonlyinsepa, FALSE, DEFAULT_PROBINGONLYINSEPA, NULL, NULL) );
2020 
2021  SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/probingfreq",
2022  "probing frequency (-1 - no probing, 0 - root node only)",
2023  &nlhdlrdata->probingfreq, FALSE, DEFAULT_PROBINGFREQ, -1, INT_MAX, NULL, NULL) );
2024 
2025  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/convexonly",
2026  "whether perspective cuts are added only for convex expressions",
2027  &nlhdlrdata->convexonly, FALSE, DEFAULT_CONVEXONLY, NULL, NULL) );
2028 
2029  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/tightenbounds",
2030  "whether variable semicontinuity is used to tighten variable bounds",
2031  &nlhdlrdata->tightenbounds, FALSE, DEFAULT_TIGHTENBOUNDS, NULL, NULL) );
2032 
2033  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/adjrefpoint",
2034  "whether to adjust the reference point",
2035  &nlhdlrdata->adjrefpoint, FALSE, DEFAULT_ADJREFPOINT, NULL, NULL) );
2036 
2037  SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrPerspective);
2038  SCIPnlhdlrSetFreeHdlrData(nlhdlr, nlhdlrFreehdlrdataPerspective);
2039  SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrFreeExprDataPerspective);
2040  SCIPnlhdlrSetInitExit(nlhdlr, NULL, nlhdlrExitPerspective);
2041  SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaPerspective, nlhdlrEnfoPerspective, NULL, NULL);
2042 
2043  return SCIP_OKAY;
2044 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
#define SCIP_DECL_NLHDLREXITSEPA(x)
Definition: type_nlhdlr.h:290
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
static SCIP_DECL_NLHDLREXIT(nlhdlrExitPerspective)
#define NLHDLR_ENFOPRIORITY
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define DEFAULT_MINVIOLPROBING
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3520
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18137
static SCIP_RETCODE addSCVarIndicator(SCIP *scip, SCVARDATA *scvdata, SCIP_VAR *indicator, SCIP_Real val0, SCIP_Real lb1, SCIP_Real ub1)
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:500
SCIP_Real SCIPfeastol(SCIP *scip)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrFreehdlrdataPerspective)
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1476
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3307
unsigned int SCIPgetExprNAuxvarUsesNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPcreateBoolarray(SCIP *scip, SCIP_BOOLARRAY **boolarray)
#define NLHDLR_DESC
#define SCIP_NLHDLR_METHOD_SEPABELOW
Definition: type_nlhdlr.h:51
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3808
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18115
SCIP_RETCODE SCIPincludeNlhdlrPerspective(SCIP *scip)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17923
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEEXPRDATA((*freeexprdata)))
Definition: nlhdlr.c:94
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17979
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
Definition: misc_rowprep.c:792
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
#define FALSE
Definition: def.h:96
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3024
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEHDLRDATA((*freehdlrdata)))
Definition: nlhdlr.c:83
#define DEFAULT_TIGHTENBOUNDS
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2600
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:687
#define TRUE
Definition: def.h:95
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18157
static SCIP_RETCODE exprIsSemicontinuous(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_EXPR *expr, SCIP_Bool *res)
static SCIP_RETCODE analyseOnoffBounds(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *indicator, SCIP_VAR ***probingvars, SCIP_INTERVAL **probingdoms, int *nprobingvars, SCIP_Bool *doprobing, SCIP_RESULT *result)
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
int SCIPgetPtrarrayMaxIdx(SCIP *scip, SCIP_PTRARRAY *ptrarray)
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18127
#define SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3211
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
static SCIP_RETCODE removeIndicator(SCIP *scip, SCIP_NLHDLREXPRDATA *nlexprdata, int pos)
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:682
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
SCIP_Real * vals0
SCIP_RETCODE SCIPsetBoolarrayVal(SCIP *scip, SCIP_BOOLARRAY *boolarray, int idx, SCIP_Bool val)
SCIP_RETCODE SCIPevalExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1625
#define DEFAULT_CONVEXONLY
SCIP_RETCODE SCIPclearPtrarray(SCIP *scip, SCIP_PTRARRAY *ptrarray)
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:647
void * SCIPgetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx)
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataPerspective)
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3818
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17933
static SCIP_RETCODE analyseVarOnoffBounds(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_VAR *var, SCIP_VAR *indicator, SCIP_Bool indvalue, SCIP_Bool *infeas, SCIP_Real *probinglb, SCIP_Real *probingub, SCIP_Bool doprobing, SCIP_Bool *reduceddom)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:627
#define NLHDLR_DETECTPRIORITY
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3882
#define SCIPerrorMessage
Definition: pub_message.h:64
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3491
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3499
static SCIP_RETCODE tightenOnBounds(SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_HASHMAP *scvars, SCIP_VAR *indicator)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetExprNEnfosNonlinear(SCIP_EXPR *expr)
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:150
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:416
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)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxPerspective)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18189
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17264
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3058
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
static SCIP_RETCODE startProbing(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *indicator, SCIP_VAR **probingvars, SCIP_INTERVAL *probingdoms, int nprobingvars, SCIP_SOL *sol, SCIP_SOL **solcopy, SCIP_Bool *cutoff_probing)
#define NULL
Definition: lpi_spx1.cpp:164
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
#define REALABS(x)
Definition: def.h:210
SCIP_RETCODE SCIPgetExprVarExprs(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **varexprs, int *nvarexprs)
Definition: scip_expr.c:2071
SCIP_RETCODE SCIPfreeBoolarray(SCIP *scip, SCIP_BOOLARRAY **boolarray)
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1443
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:581
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define SCIP_CALL(x)
Definition: def.h:394
static SCIP_RETCODE computeOffValues(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_EXPR *expr)
static SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaPerspective)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18147
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17551
#define DEFAULT_ADJREFPOINT
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18179
void SCIPgetExprEnfoDataNonlinear(SCIP_EXPR *expr, int idx, SCIP_NLHDLR **nlhdlr, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_NLHDLR_METHOD *nlhdlrparticipation, SCIP_Bool *sepabelowusesactivity, SCIP_Bool *sepaaboveusesactivity, SCIP_Real *auxvalue)
#define DEFAULT_PROBINGFREQ
#define DEFAULT_PROBINGONLYINSEPA
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2302
static SCIP_RETCODE varIsSemicontinuous(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *scvars, SCIP_Bool *result)
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)), SCIP_DECL_NLHDLREXITSEPA((*exitsepa)))
Definition: nlhdlr.c:132
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1221
#define SCIP_Bool
Definition: def.h:93
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:751
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
unsigned int SCIP_NLHDLR_METHOD
Definition: type_nlhdlr.h:57
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
static SCVARDATA * getSCVarDataInd(SCIP_HASHMAP *scvars, SCIP_VAR *var, SCIP_VAR *indicator, int *pos)
constraint handler for nonlinear constraints specified by algebraic expressions
#define SCIP_DECL_NLHDLRINIT(x)
Definition: type_nlhdlr.h:105
#define MAX(x, y)
Definition: tclique_def.h:92
SCIP_RETCODE SCIPgetExprNVars(SCIP *scip, SCIP_EXPR *expr, int *nvars)
Definition: scip_expr.c:2033
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:985
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:857
perspective nonlinear handler
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectPerspective)
#define DEFAULT_MAXPROPROUNDS
#define BMSclearMemory(ptr)
Definition: memory.h:131
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2045
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:2000
#define SCIP_REAL_MAX
Definition: def.h:187
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2316
SCIP_Real * r
Definition: circlepacking.c:59
SCIP_VAR ** b
Definition: circlepacking.c:65
SCIP_RETCODE SCIPcreatePtrarray(SCIP *scip, SCIP_PTRARRAY **ptrarray)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPprocessRowprepNonlinear(SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_CONS *cons, SCIP_EXPR *expr, SCIP_ROWPREP *rowprep, SCIP_Bool overestimate, SCIP_VAR *auxvar, SCIP_Real auxvalue, SCIP_Bool allowweakcuts, SCIP_Bool branchscoresuccess, SCIP_Bool inenforcement, SCIP_SOL *sol, SCIP_RESULT *result)
public methods for solutions
SCIP_Real SCIProwprepGetSide(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:657
static SCIP_RETCODE freeNlhdlrExprData(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
static SCIP_DECL_NLHDLRENFO(nlhdlrEnfoPerspective)
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
SCIP_RETCODE SCIPgetExprAbsAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17383
void SCIPnlhdlrSetInitExit(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINIT((*init)), SCIP_DECL_NLHDLREXIT((*exit_)))
Definition: nlhdlr.c:106
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
#define SCIP_Real
Definition: def.h:186
SCIP_Real * lbs1
#define SCIP_INVALID
Definition: def.h:206
SCIP_Bool SCIPnlhdlrHasEstimate(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:250
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18169
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrPerspective)
SCIP_VAR ** bvars
SCIP_NLHDLRDATA * SCIPnlhdlrGetData(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:200
#define SCIP_Longint
Definition: def.h:171
SCIP_Real * ubs1
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
Definition: type_nlhdlr.h:413
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17429
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
Definition: type_nlhdlr.h:412
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1263
SCIP_Bool SCIPgetBoolarrayVal(SCIP *scip, SCIP_BOOLARRAY *boolarray, int idx)
void SCIPsetExprEnfoAuxValueNonlinear(SCIP_EXPR *expr, int idx, SCIP_Real auxvalue)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17989
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: misc_rowprep.c:904
int SCIPgetPtrarrayMinIdx(SCIP *scip, SCIP_PTRARRAY *ptrarray)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3106
private functions of nonlinear handlers of nonlinear constraints
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:968
static SCIP_RETCODE addAuxVar(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_HASHMAP *auxvarmap, SCIP_VAR *auxvar)
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3231
void SCIPcomputeArraysIntersectionPtr(void **array1, int narray1, void **array2, int narray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void **intersectarray, int *nintersectarray)
Definition: misc.c:10523
#define SCIPABORT()
Definition: def.h:366
#define SCIP_NLHDLR_METHOD_SEPABOTH
Definition: type_nlhdlr.h:53
SCIP_RETCODE SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
#define NLHDLR_NAME
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
#define SCIP_NLHDLR_METHOD_SEPAABOVE
Definition: type_nlhdlr.h:52
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
#define DEFAULT_MINDOMREDUCTION
preparation of a linear inequality to become a SCIP_ROW
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_VAR ** SCIProwprepGetVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:637
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:328
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
SCIP_RETCODE SCIPfreePtrarray(SCIP *scip, SCIP_PTRARRAY **ptrarray)
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRCOPYHDLR((*copy)))
Definition: nlhdlr.c:72