Scippy

SCIP

Solving Constraint Integer Programs

nlhdlr_convex.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_convex.c
26  * @ingroup DEFPLUGINS_NLHDLR
27  * @brief nonlinear handlers for convex and concave expressions
28  * @author Benjamin Mueller
29  * @author Stefan Vigerske
30  *
31  * TODO convex: perturb reference point if separation fails due to too large numbers
32  */
33 
34 #include <string.h>
35 
36 #include "scip/nlhdlr_convex.h"
37 #include "scip/pub_nlhdlr.h"
38 #include "scip/scip_expr.h"
39 #include "scip/cons_nonlinear.h"
40 #include "scip/expr_var.h"
41 #include "scip/expr_abs.h"
42 #include "scip/pub_misc_rowprep.h"
43 #include "scip/dbldblarith.h"
44 
45 /* fundamental nonlinear handler properties */
46 #define CONVEX_NLHDLR_NAME "convex"
47 #define CONVEX_NLHDLR_DESC "handler that identifies and estimates convex expressions"
48 #define CONVEX_NLHDLR_DETECTPRIORITY 50
49 #define CONVEX_NLHDLR_ENFOPRIORITY 50
50 
51 #define CONCAVE_NLHDLR_NAME "concave"
52 #define CONCAVE_NLHDLR_DESC "handler that identifies and estimates concave expressions"
53 #define CONCAVE_NLHDLR_DETECTPRIORITY 40
54 #define CONCAVE_NLHDLR_ENFOPRIORITY 40
55 
56 #define DEFAULT_DETECTSUM FALSE
57 #define DEFAULT_EXTENDEDFORM TRUE
58 #define DEFAULT_CVXQUADRATIC_CONVEX TRUE
59 #define DEFAULT_CVXQUADRATIC_CONCAVE FALSE
60 #define DEFAULT_CVXSIGNOMIAL TRUE
61 #define DEFAULT_CVXPRODCOMP TRUE
62 #define DEFAULT_HANDLETRIVIAL FALSE
63 
64 #define INITLPMAXVARVAL 1000.0 /**< maximal absolute value of variable for still generating a linearization cut at that point in initlp */
65 
66 /*lint -e440*/
67 /*lint -e441*/
68 /*lint -e666*/
69 /*lint -e777*/
70 
71 /*
72  * Data structures
73  */
74 
75 /** nonlinear handler expression data */
76 struct SCIP_NlhdlrExprData
77 {
78  SCIP_EXPR* nlexpr; /**< expression (copy) for which this nlhdlr estimates */
79  SCIP_HASHMAP* nlexpr2origexpr; /**< mapping of our copied expression to original expression */
80 
81  int nleafs; /**< number of distinct leafs of nlexpr, i.e., number of distinct (auxiliary) variables handled */
82  SCIP_EXPR** leafexprs; /**< distinct leaf expressions (excluding value-expressions), thus variables */
83 };
84 
85 /** nonlinear handler data */
86 struct SCIP_NlhdlrData
87 {
88  SCIP_Bool isnlhdlrconvex; /**< whether this data is used for the convex nlhdlr (TRUE) or the concave one (FALSE) */
89  SCIP_SOL* evalsol; /**< solution used for evaluating expression in a different point,
90  e.g., for facet computation of vertex-polyhedral function */
91 
92  /* parameters */
93  SCIP_Bool detectsum; /**< whether to run detection when the root of an expression is a non-quadratic sum */
94  SCIP_Bool extendedform; /**< whether to create extended formulations instead of looking for maximal possible subexpression */
95 
96  /* advanced parameters (maybe remove some day) */
97  SCIP_Bool cvxquadratic; /**< whether to use convexity check on quadratics */
98  SCIP_Bool cvxsignomial; /**< whether to use convexity check on signomials */
99  SCIP_Bool cvxprodcomp; /**< whether to use convexity check on product composition f(h)*h */
100  SCIP_Bool handletrivial; /**< whether to handle trivial expressions, i.e., those where all children are variables */
101 };
102 
103 /** data struct to be be passed on to vertexpoly-evalfunction (see SCIPcomputeFacetVertexPolyhedralNonlinear) */
104 typedef struct
105 {
110 
111 /** stack used in constructExpr to store expressions that need to be investigated ("to do list") */
112 typedef struct
113 {
114  SCIP_EXPR** stack; /**< stack elements */
115  int stacksize; /**< allocated space (in number of pointers) */
116  int stackpos; /**< position of top element of stack */
117 } EXPRSTACK;
118 
119 #define DECL_CURVCHECK(x) SCIP_RETCODE x( \
120  SCIP* scip, /**< SCIP data structure */ \
121  SCIP_EXPR* nlexpr, /**< nlhdlr-expr to check */ \
122  SCIP_Bool isrootexpr, /**< whether nlexpr is the root from where detection has been started */ \
123  EXPRSTACK* stack, /**< stack where to add generated leafs */ \
124  SCIP_HASHMAP* nlexpr2origexpr, /**< mapping from our expression copy to original expression */ \
125  SCIP_NLHDLRDATA* nlhdlrdata, /**< data of nlhdlr */ \
126  SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */ \
127  SCIP_Bool* success /**< whether we found something */ \
128  )
129 
130 /*
131  * static methods
132  */
133 
134 /** create nlhdlr-expression
135  *
136  * does not create children, i.e., assumes that this will be a leaf
137  */
138 static
140  SCIP* scip, /**< SCIP data structure */
141  SCIP_HASHMAP* nlexpr2origexpr, /**< mapping from copied to original expression */
142  SCIP_EXPR** nlhdlrexpr, /**< buffer to store created expr */
143  SCIP_EXPR* origexpr, /**< original expression to be copied */
144  SCIP_EXPRCURV curv /**< curvature to achieve */
145  )
146 {
147  assert(scip != NULL);
148  assert(nlexpr2origexpr != NULL);
149  assert(nlhdlrexpr != NULL);
150  assert(origexpr != NULL);
151 
152  if( SCIPexprGetNChildren(origexpr) == 0 )
153  {
154  /* for leaves, do not copy */
155  *nlhdlrexpr = origexpr;
156  SCIPcaptureExpr(*nlhdlrexpr);
157  if( !SCIPhashmapExists(nlexpr2origexpr, (void*)*nlhdlrexpr) )
158  {
159  SCIP_CALL( SCIPhashmapInsert(nlexpr2origexpr, (void*)*nlhdlrexpr, (void*)origexpr) );
160  }
161  return SCIP_OKAY;
162  }
163 
164  /* create copy of expression, but without children */
165  SCIP_CALL( SCIPduplicateExprShallow(scip, origexpr, nlhdlrexpr, NULL, NULL) );
166  assert(*nlhdlrexpr != NULL); /* copies within the same SCIP must always work */
167 
168  /* store the curvature we want to get in the curvature flag of the copied expression
169  * it's a bit of a misuse, but once we are done with everything, this is actually correct
170  */
171  SCIPexprSetCurvature(*nlhdlrexpr, curv);
172 
173  /* remember which the original expression was */
174  SCIP_CALL( SCIPhashmapInsert(nlexpr2origexpr, (void*)*nlhdlrexpr, (void*)origexpr) );
175 
176  return SCIP_OKAY;
177 }
178 
179 /** expand nlhdlr-expression by adding children according to original expression */
180 static
182  SCIP* scip, /**< SCIP data structure */
183  SCIP_HASHMAP* nlexpr2origexpr, /**< mapping from copied to original expression */
184  SCIP_EXPR* nlhdlrexpr, /**< expression for which to create children */
185  SCIP_EXPRCURV* childrencurv /**< curvature required for children, or NULL if to set to UNKNOWN */
186  )
187 {
188  SCIP_EXPR* origexpr;
189  SCIP_EXPR* child;
190  int nchildren;
191  int i;
192 
193  assert(scip != NULL);
194  assert(nlhdlrexpr != NULL);
195  assert(SCIPexprGetNChildren(nlhdlrexpr) == 0);
196 
197  origexpr = (SCIP_EXPR*)SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlhdlrexpr);
198 
199  nchildren = SCIPexprGetNChildren(origexpr);
200  if( nchildren == 0 )
201  return SCIP_OKAY;
202 
203  for( i = 0; i < nchildren; ++i )
204  {
205  SCIP_CALL( nlhdlrExprCreate(scip, nlexpr2origexpr, &child, SCIPexprGetChildren(origexpr)[i],
206  childrencurv != NULL ? childrencurv[i] : SCIP_EXPRCURV_UNKNOWN) );
207  SCIP_CALL( SCIPappendExprChild(scip, nlhdlrexpr, child) );
208  /* append captures child, so we can release the capture from nlhdlrExprCreate */
209  SCIP_CALL( SCIPreleaseExpr(scip, &child) );
210  }
211 
212  assert(SCIPexprGetNChildren(nlhdlrexpr) == SCIPexprGetNChildren(origexpr));
213 
214  return SCIP_OKAY;
215 }
216 
217 /** evaluate expression at solution w.r.t. auxiliary variables */
218 static
219 SCIP_DECL_VERTEXPOLYFUN(nlhdlrExprEvalConcave)
220 {
221  VERTEXPOLYFUN_EVALDATA* evaldata = (VERTEXPOLYFUN_EVALDATA*)funcdata;
222  int i;
223 
224  assert(args != NULL);
225  assert(nargs == evaldata->nlhdlrexprdata->nleafs);
226  assert(evaldata != NULL);
227 
228 #ifdef SCIP_MORE_DEBUG
229  SCIPdebugMsg(evaldata->scip, "eval vertexpolyfun at\n");
230 #endif
231  for( i = 0; i < nargs; ++i )
232  {
233 #ifdef SCIP_MORE_DEBUG
234  SCIPdebugMsg(evaldata->scip, " <%s> = %g\n",
235  SCIPvarGetName(SCIPgetVarExprVar(evaldata->nlhdlrexprdata->leafexprs[i])), args[i]);
236 #endif
237  SCIP_CALL_ABORT( SCIPsetSolVal(evaldata->scip, evaldata->evalsol,
238  SCIPgetVarExprVar(evaldata->nlhdlrexprdata->leafexprs[i]), args[i]) );
239  }
240 
241  SCIP_CALL_ABORT( SCIPevalExpr(evaldata->scip, evaldata->nlhdlrexprdata->nlexpr, evaldata->evalsol, 0L) );
242 
243  return SCIPexprGetEvalValue(evaldata->nlhdlrexprdata->nlexpr);
244 }
245 
246 /** initialize expression stack */
247 static
249  SCIP* scip, /**< SCIP data structure */
250  EXPRSTACK* exprstack, /**< stack to initialize */
251  int initsize /**< initial size */
252  )
253 {
254  assert(scip != NULL);
255  assert(exprstack != NULL);
256  assert(initsize > 0);
257 
258  SCIP_CALL( SCIPallocBufferArray(scip, &exprstack->stack, initsize) );
259  exprstack->stacksize = initsize;
260  exprstack->stackpos = -1;
261 
262  return SCIP_OKAY;
263 }
264 
265 /** free expression stack */
266 static
268  SCIP* scip, /**< SCIP data structure */
269  EXPRSTACK* exprstack /**< free expression stack */
270  )
271 {
272  assert(scip != NULL);
273  assert(exprstack != NULL);
274 
275  SCIPfreeBufferArray(scip, &exprstack->stack);
276 }
277 
278 /** add expressions to expression stack */
279 static
281  SCIP* scip, /**< SCIP data structure */
282  EXPRSTACK* exprstack, /**< expression stack */
283  int nexprs, /**< number of expressions to push */
284  SCIP_EXPR** exprs /**< expressions to push */
285  )
286 {
287  assert(scip != NULL);
288  assert(exprstack != NULL);
289 
290  if( nexprs == 0 )
291  return SCIP_OKAY;
292 
293  assert(exprs != NULL);
294 
295  if( exprstack->stackpos+1 + nexprs > exprstack->stacksize ) /*lint !e644*/
296  {
297  exprstack->stacksize = SCIPcalcMemGrowSize(scip, exprstack->stackpos+1 + nexprs); /*lint !e644*/
298  SCIP_CALL( SCIPreallocBufferArray(scip, &exprstack->stack, exprstack->stacksize) );
299  }
300 
301  memcpy(exprstack->stack + (exprstack->stackpos+1), exprs, nexprs * sizeof(SCIP_EXPR*)); /*lint !e679*/ /*lint !e737*/
302  exprstack->stackpos += nexprs;
303 
304  return SCIP_OKAY;
305 }
306 
307 /** gives expression from top of expression stack and removes it from stack */
308 static
310  EXPRSTACK* exprstack /**< expression stack */
311  )
312 {
313  assert(exprstack != NULL);
314  assert(exprstack->stackpos >= 0);
315 
316  return exprstack->stack[exprstack->stackpos--];
317 }
318 
319 /** indicate whether expression stack is empty */
320 static
322  EXPRSTACK* exprstack /**< expression stack */
323  )
324 {
325  assert(exprstack != NULL);
326 
327  return exprstack->stackpos < 0;
328 }
329 
330 /** looks whether given expression is (proper) quadratic and has a given curvature
331  *
332  * If having a given curvature, currently require all arguments of quadratic to be linear.
333  * Hence, not using this for a simple square term, as curvCheckExprhdlr may provide a better condition on argument curvature then.
334  * Also we wouldn't do anything useful for a single bilinear term.
335  * Thus, run on sum's only.
336  */
337 static
338 DECL_CURVCHECK(curvCheckQuadratic)
339 { /*lint --e{715}*/
340  SCIP_EXPR* expr;
341  SCIP_EXPRCURV presentcurv;
342  SCIP_EXPRCURV wantedcurv;
343  SCIP_HASHSET* lonelysquares = NULL;
344  SCIP_Bool isquadratic;
345  int nbilinexprs;
346  int nquadexprs;
347  int i;
348 
349  assert(nlexpr != NULL);
350  assert(stack != NULL);
351  assert(nlexpr2origexpr != NULL);
352  assert(success != NULL);
353 
354  *success = FALSE;
355 
356  if( !nlhdlrdata->cvxquadratic )
357  return SCIP_OKAY;
358 
359  if( !SCIPisExprSum(scip, nlexpr) )
360  return SCIP_OKAY;
361 
362  wantedcurv = SCIPexprGetCurvature(nlexpr);
363  if( wantedcurv == SCIP_EXPRCURV_LINEAR )
364  return SCIP_OKAY;
365  assert(wantedcurv == SCIP_EXPRCURV_CONVEX || wantedcurv == SCIP_EXPRCURV_CONCAVE);
366 
367  expr = (SCIP_EXPR*)SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlexpr);
368  assert(expr != NULL);
369 
370  /* check whether quadratic */
371  SCIP_CALL( SCIPcheckExprQuadratic(scip, expr, &isquadratic) );
372 
373  /* if not quadratic, then give up here */
374  if( !isquadratic )
375  return SCIP_OKAY;
376 
377  SCIPexprGetQuadraticData(expr, NULL, NULL, NULL, NULL, &nquadexprs, &nbilinexprs, NULL, NULL);
378 
379  /* if only single square term (+linear), then give up here (let curvCheckExprhdlr handle this) */
380  if( nquadexprs <= 1 )
381  return SCIP_OKAY;
382 
383  /* if root expression is only sum of squares (+linear) and detectsum is disabled, then give up here, too */
384  if( isrootexpr && !nlhdlrdata->detectsum && nbilinexprs == 0 )
385  return SCIP_OKAY;
386 
387  /* get curvature of quadratic
388  * TODO as we know what curvature we want, we could first do some simple checks like computing xQx for a random x
389  */
390  SCIP_CALL( SCIPcomputeExprQuadraticCurvature(scip, expr, &presentcurv, assumevarfixed, FALSE) );
391 
392  /* if not having desired curvature, return */
393  if( presentcurv != wantedcurv )
394  return SCIP_OKAY;
395 
396  *success = TRUE;
397 
398  if( !nlhdlrdata->detectsum )
399  {
400  /* first step towards block-decomposition of quadratic term:
401  * collect all square-expressions (in original expr) which have no adjacent bilinear term
402  * we will treat these x^2 as linear, i.e., add an auxvar for them, so x^2 maybe linearized
403  * more efficiently (in particular if x is discrete)
404  */
405  SCIP_CALL( SCIPhashsetCreate(&lonelysquares, SCIPblkmem(scip), nquadexprs) );
406  for( i = 0; i < nquadexprs; ++i )
407  {
408  int nadjbilin;
409  SCIP_EXPR* sqrexpr;
410 
411  SCIPexprGetQuadraticQuadTerm(expr, i, NULL, NULL, NULL, &nadjbilin, NULL, &sqrexpr);
412  if( nadjbilin == 0 )
413  {
414  assert(sqrexpr != NULL);
415  SCIP_CALL( SCIPhashsetInsert(lonelysquares, SCIPblkmem(scip), (void*)sqrexpr) );
416  }
417  }
418  }
419 
420  /* add immediate children to nlexpr */
421  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, nlexpr, NULL) );
422  assert(SCIPexprGetNChildren(nlexpr) == SCIPexprGetNChildren(expr));
423 
424  /* put children that are not square or product on stack
425  * grow child for children that are square or product and put this child on stack
426  * require all children to be linear
427  */
428  for( i = 0; i < SCIPexprGetNChildren(nlexpr); ++i )
429  {
430  SCIP_EXPR* child;
432 
433  child = SCIPexprGetChildren(nlexpr)[i];
434  assert(child != NULL);
435 
436  assert(SCIPhashmapGetImage(nlexpr2origexpr, (void*)child) == SCIPexprGetChildren(expr)[i]);
437 
438  if( SCIPisExprPower(scip, child) && SCIPgetExponentExprPow(child) == 2.0 &&
439  (lonelysquares == NULL || !SCIPhashsetExists(lonelysquares, SCIPexprGetChildren(expr)[i])) )
440  {
441  /* square term that isn't lonely, i.e., orig-version of child is a square-expr and nadjbilin>0 */
442  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, child, curvlinear) );
443  assert(SCIPexprGetNChildren(child) == 1);
444  SCIP_CALL( exprstackPush(scip, stack, 1, SCIPexprGetChildren(child)) );
445  }
446  else if( SCIPisExprProduct(scip, child) && SCIPexprGetNChildren(SCIPexprGetChildren(expr)[i]) == 2 )
447  /* using original version of child here as NChildren(child)==0 atm */
448  {
449  /* bilinear term */
450  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, child, curvlinear) );
451  assert(SCIPexprGetNChildren(child) == 2);
452  SCIP_CALL( exprstackPush(scip, stack, 2, SCIPexprGetChildren(child)) );
453  }
454  else
455  {
456  /* linear term (or term to be considered as linear) or lonely square term
457  * if we want extended formulations, then require linearity, so an auxvar will be introduced if it is nonlinear
458  * if we do not want extended formulations, then the term needs to have curvature "wantedcurv"
459  * thus, if the coef is negative, then the child needs to have the curvature opposite to "wantedcurv"
460  */
461  if( nlhdlrdata->extendedform )
462  SCIPexprSetCurvature(child, SCIP_EXPRCURV_LINEAR);
463  else
464  SCIPexprSetCurvature(child, SCIPexprcurvMultiply(SCIPgetCoefsExprSum(nlexpr)[i], wantedcurv));
465  SCIP_CALL( exprstackPush(scip, stack, 1, &child) );
466  }
467  }
468 
469  if( lonelysquares != NULL )
470  SCIPhashsetFree(&lonelysquares, SCIPblkmem(scip));
471 
472  return SCIP_OKAY;
473 }
474 
475 /** looks whether top of given expression looks like a signomial that can have a given curvature
476  *
477  * e.g., sqrt(x)*sqrt(y) is convex if x,y >= 0 and x and y are convex
478  *
479  * unfortunately, doesn't work for tls, because i) it's originally sqrt(x*y), and ii) it is expanded into some sqrt(z*y+y);
480  * but works for cvxnonsep_nsig
481  */
482 static
483 DECL_CURVCHECK(curvCheckSignomial)
484 { /*lint --e{715}*/
485  SCIP_EXPR* expr;
486  SCIP_EXPR* child;
487  SCIP_Real* exponents;
488  SCIP_INTERVAL* bounds;
489  SCIP_EXPRCURV* curv;
490  int nfactors;
491  int i;
492 
493  assert(nlexpr != NULL);
494  assert(stack != NULL);
495  assert(nlexpr2origexpr != NULL);
496  assert(success != NULL);
497 
498  *success = FALSE;
499 
500  if( !nlhdlrdata->cvxsignomial )
501  return SCIP_OKAY;
502 
503  if( !SCIPisExprProduct(scip, nlexpr) )
504  return SCIP_OKAY;
505 
506  expr = (SCIP_EXPR*)SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlexpr);
507  assert(expr != NULL);
508 
509  nfactors = SCIPexprGetNChildren(expr);
510  if( nfactors <= 1 ) /* boooring */
511  return SCIP_OKAY;
512 
513  SCIP_CALL( SCIPallocBufferArray(scip, &exponents, nfactors) );
514  SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nfactors) );
515  SCIP_CALL( SCIPallocBufferArray(scip, &curv, nfactors) );
516 
517  for( i = 0; i < nfactors; ++i )
518  {
519  child = SCIPexprGetChildren(expr)[i];
520  assert(child != NULL);
521 
522  if( !SCIPisExprPower(scip, child) )
523  {
524  exponents[i] = 1.0;
526  bounds[i] = SCIPexprGetActivity(child);
527  }
528  else
529  {
530  exponents[i] = SCIPgetExponentExprPow(child);
532  bounds[i] = SCIPexprGetActivity(SCIPexprGetChildren(child)[0]);
533  }
534  }
535 
537  nfactors, exponents, bounds, curv) )
538  goto TERMINATE;
539 
540  /* add immediate children to nlexpr
541  * some entries in curv actually apply to arguments of pow's, will correct this next
542  */
543  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, nlexpr, curv) );
544  assert(SCIPexprGetNChildren(nlexpr) == nfactors);
545 
546  /* put children that are not power on stack
547  * grow child for children that are power and put this child on stack
548  * if extendedform, then require children to be linear
549  * unless they are linear, an auxvar will be introduced for them and thus they will be handled as var here
550  */
551  for( i = 0; i < nfactors; ++i )
552  {
553  child = SCIPexprGetChildren(nlexpr)[i];
554  assert(child != NULL);
555 
556  if( SCIPisExprPower(scip, child) )
557  {
558  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, child, &curv[i]) );
559  assert(SCIPexprGetNChildren(child) == 1);
560  child = SCIPexprGetChildren(child)[0];
561  }
562  assert(SCIPexprGetNChildren(child) == 0);
563 
564  if( nlhdlrdata->extendedform )
565  {
567 #ifdef SCIP_DEBUG
568  SCIPinfoMessage(scip, NULL, "Extendedform: Require linearity for ");
569  SCIPprintExpr(scip, child, NULL);
570  SCIPinfoMessage(scip, NULL, "\n");
571 #endif
572  }
573 
574  SCIP_CALL( exprstackPush(scip, stack, 1, &child) );
575  }
576 
577  *success = TRUE;
578 
579 TERMINATE:
580  SCIPfreeBufferArray(scip, &curv);
581  SCIPfreeBufferArray(scip, &bounds);
582  SCIPfreeBufferArray(scip, &exponents);
583 
584  return SCIP_OKAY;
585 }
586 
587 /** looks for \f$f(c h(x)+d) h(x) \cdot \text{constant}\f$ and tries to conclude conditions on curvature
588  *
589  * Assume \f$h\f$ is univariate:
590  * - First derivative is \f$f'(c h + d) c h' h + f(c h + d) h'\f$.
591  * - Second derivative is \f{align}{&f''(c h + d) c h' c h' h + f'(c h + d) (c h'' h + c h' h') + f'(c h + d) c h' h' + f(c h + d) h'' \\
592  * =& f''(c h + d) c^2 h'^2 h + f'(c h + d) c h'' h + 2 f'(c h + d) c h'^2 + f(c h + d) h''.\f}
593  * Remove always positive factors leaves \f[f''(c h + d) h,\quad f'(c h + d) c h'' h,\quad f'(c h + d) c,\quad f(c h + d) h''.\f]
594  * For convexity we want all these terms to be nonnegative. For concavity we want all of them to be nonpositive.
595  * Note, that in each term either both \f$f'(c h + d)\f$ and \f$c\f$ occur, or none of them.
596  * - Thus, \f$f(c h(x) + d)h(x)\f$ is convex if \f$cf\f$ is monotonically increasing \f$(c f' \geq 0)\f$ and either
597  * - \f$f\f$ is convex \f$(f'' \geq 0)\f$ and \f$h\f$ is nonnegative \f$(h \geq 0)\f$ and \f$h\f$ is convex \f$(h'' \geq 0)\f$ and [\f$f\f$ is nonnegative \f$(f \geq 0)\f$ or \f$h\f$ is linear \f$(h''=0)\f$], or
598  * - \f$f\f$ is concave \f$(f'' \leq 0)\f$ and \f$h\f$ is nonpositive \f$(h \leq 0)\f$ and \f$h\f$ is concave \f$(h'' \leq 0)\f$ and [\f$f\f$ is nonpositive \f$(f \leq 0)\f$ or \f$h\f$ is linear \f$(h''=0)\f$].
599  * - Further, \f$f(c h(x) + d)h(x)\f$ is concave if \f$cf\f$ is monotonically decreasing \f$(c f' \leq 0)\f$ and either
600  * - f is convex \f$(f'' \geq 0)\f$ and \f$h\f$ is nonpositive \f$(h \leq 0)\f$ and \f$h\f$ is concave \f$(h'' \leq 0)\f$ and [\f$f\f$ is nonnegative \f$(f \geq 0)\f$ or \f$h\f$ is linear \f$(h''=0)\f$], or
601  * - f is concave \f$(f'' \leq 0)\f$ and \f$h\f$ is nonnegative \f$(h >= 0)\f$ and \f$h\f$ is convex \f$(h'' \geq 0)\f$ and [\f$f\f$ is nonpositive \f$(f \leq 0)\f$ or \f$h\f$ is linear \f$(h''=0)\f$].
602  *
603  * This should hold also for multivariate and linear \f$h\f$, as things are invariant under linear transformations.
604  * Similar to signomial, I'll assume that this will also hold for other multivariate \f$h\f$ (someone has a formal proof?).
605  */
606 static
607 DECL_CURVCHECK(curvCheckProductComposite)
608 { /*lint --e{715}*/
609  SCIP_EXPR* expr;
610  SCIP_EXPR* f;
611  SCIP_EXPR* h = NULL;
612  SCIP_Real c = 0.0;
613  SCIP_EXPR* ch = NULL; /* c * h */
614  SCIP_Real d;
615  SCIP_INTERVAL fbounds;
616  SCIP_INTERVAL hbounds;
617  SCIP_MONOTONE fmonotonicity;
618  SCIP_EXPRCURV desiredcurv;
619  SCIP_EXPRCURV hcurv;
620  SCIP_EXPRCURV dummy;
621  int fidx;
622 
623  assert(nlexpr != NULL);
624  assert(stack != NULL);
625  assert(nlexpr2origexpr != NULL);
626  assert(success != NULL);
627 
628  *success = FALSE;
629 
630  if( !nlhdlrdata->cvxprodcomp )
631  return SCIP_OKAY;
632 
633  if( !SCIPisExprProduct(scip, nlexpr) )
634  return SCIP_OKAY;
635 
636  expr = (SCIP_EXPR*)SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlexpr);
637  assert(expr != NULL);
638 
639  if( SCIPexprGetNChildren(expr) != 2 )
640  return SCIP_OKAY;
641 
642  /* check whether we have f(c * h(x)) * h(x) or h(x) * f(c * h(x)) */
643  for( fidx = 0; fidx <= 1; ++fidx )
644  {
645  f = SCIPexprGetChildren(expr)[fidx];
646 
647  if( SCIPexprGetNChildren(f) != 1 )
648  continue;
649 
650  ch = SCIPexprGetChildren(f)[0];
651  c = 1.0;
652  h = ch;
653 
654  /* check whether ch is of the form c*h(x), then switch h to child ch */
655  if( SCIPisExprSum(scip, ch) && SCIPexprGetNChildren(ch) == 1 )
656  {
657  c = SCIPgetCoefsExprSum(ch)[0];
658  h = SCIPexprGetChildren(ch)[0];
659  assert(c != 1.0 || SCIPgetConstantExprSum(ch) != 0.0); /* we could handle this, but it should have been simplified away */
660  }
661 
662 #ifndef NLHDLR_CONVEX_UNITTEST
663  /* can assume that duplicate subexpressions have been identified and comparing pointer is sufficient */
664  if( SCIPexprGetChildren(expr)[1-fidx] == h )
665 #else
666  /* called from unittest -> duplicate subexpressions were not identified -> compare more expensively */
667  if( SCIPcompareExpr(scip, SCIPexprGetChildren(expr)[1-fidx], h) == 0 )
668 #endif
669  break;
670  }
671  if( fidx == 2 )
672  return SCIP_OKAY;
673 
674  /* constant of c*h(x)+d */
675  d = h != ch ? SCIPgetConstantExprSum(ch) : 0.0;
676 
677 #ifdef SCIP_MORE_DEBUG
678  SCIPinfoMessage(scip, NULL, "f(c*h+d)*h with f = %s, c = %g, d = %g, h = ", SCIPexprhdlrGetName(SCIPexprGetHdlr(f)), c, d);
679  SCIPprintExpr(scip, h, NULL);
680  SCIPinfoMessage(scip, NULL, "\n");
681 #endif
682 
683  assert(c != 0.0);
684 
687  fbounds = SCIPexprGetActivity(f);
688  hbounds = SCIPexprGetActivity(h);
689 
690  /* if h has mixed sign, then cannot conclude anything */
691  if( hbounds.inf < 0.0 && hbounds.sup > 0.0 )
692  return SCIP_OKAY;
693 
694  /* If we have some convex or concave x*abs(c*x+d), then gradients at x=-d/c may be very wrong due to
695  * rounding errors and non-differentiability of abs() at zero (#3411). Therefore, we skip handling
696  * such expression in this nonlinear handler when one of the bounds of c*x+d is very close to zero.
697  * (If zero is in between the bounds of c*x+d, then the composition wouldn't be regarded as convex/concave anyway.)
698  */
699  if( SCIPisExprAbs(scip, f) && (SCIPisZero(scip, c*hbounds.inf+d) || SCIPisZero(scip, c*hbounds.sup+d)) )
700  return SCIP_OKAY;
701 
702  SCIP_CALL( SCIPcallExprMonotonicity(scip, f, 0, &fmonotonicity) );
703 
704  /* if f is not monotone, then cannot conclude anything */
705  if( fmonotonicity == SCIP_MONOTONE_UNKNOWN )
706  return SCIP_OKAY;
707 
708  /* curvature we want to achieve (negate if product has negative coef) */
709  desiredcurv = SCIPexprcurvMultiply(SCIPgetCoefExprProduct(nlexpr), SCIPexprGetCurvature(nlexpr));
710 
711  /* now check the conditions as stated above */
712  if( desiredcurv == SCIP_EXPRCURV_CONVEX )
713  {
714  /* f(c h(x)+d)h(x) is convex if c*f is monotonically increasing (c f' >= 0) and either
715  * - f is convex (f'' >= 0) and h is nonnegative (h >= 0) and h is convex (h'' >= 0) and [f is nonnegative (f >= 0) or h is linear (h''=0)], or
716  * - f is concave (f'' <= 0) and h is nonpositive (h <= 0) and h is concave (h'' <= 0) and [f is nonpositive (f <= 0) or h is linear (h''=0)]
717  * as the curvature requirements on f are on f only and not the composition f(h), we can ignore the requirements returned by SCIPcallExprCurvature (last arg)
718  */
719  if( (c > 0.0 && fmonotonicity != SCIP_MONOTONE_INC) || (c < 0.0 && fmonotonicity != SCIP_MONOTONE_DEC) )
720  return SCIP_OKAY;
721 
722  /* check whether f can be convex (h>=0) or concave (h<=0), resp., and derive requirements for h */
723  if( hbounds.inf >= 0 )
724  {
725  SCIP_CALL( SCIPcallExprCurvature(scip, f, SCIP_EXPRCURV_CONVEX, success, &dummy) );
726 
727  /* now h also needs to be convex; and if f < 0, then h actually needs to be linear */
728  if( fbounds.inf < 0.0 )
729  hcurv = SCIP_EXPRCURV_LINEAR;
730  else
731  hcurv = SCIP_EXPRCURV_CONVEX;
732  }
733  else
734  {
735  SCIP_CALL( SCIPcallExprCurvature(scip, f, SCIP_EXPRCURV_CONCAVE, success, &dummy) );
736 
737  /* now h also needs to be concave; and if f > 0, then h actually needs to be linear */
738  if( fbounds.sup > 0.0 )
739  hcurv = SCIP_EXPRCURV_LINEAR;
740  else
741  hcurv = SCIP_EXPRCURV_CONCAVE;
742  }
743  }
744  else
745  {
746  /* f(c h(x)+d)*h(x) is concave if c*f is monotonically decreasing (c f' <= 0) and either
747  * - f is convex (f'' >= 0) and h is nonpositive (h <= 0) and h is concave (h'' <= 0) and [f is nonnegative (f >= 0) or h is linear (h''=0)], or
748  * - f is concave (f'' <= 0) and h is nonnegative (h >= 0) and h is convex (h'' >= 0) and [f is nonpositive (f <= 0) or h is linear (h''=0)]
749  * as the curvature requirements on f are on f only and not the composition f(h), we can ignore the requirements returned by SCIPcallExprCurvature (last arg)
750  */
751  if( (c > 0.0 && fmonotonicity != SCIP_MONOTONE_DEC) || (c < 0.0 && fmonotonicity != SCIP_MONOTONE_INC) )
752  return SCIP_OKAY;
753 
754  /* check whether f can be convex (h<=0) or concave (h>=0), resp., and derive requirements for h */
755  if( hbounds.sup <= 0 )
756  {
757  SCIP_CALL( SCIPcallExprCurvature(scip, f, SCIP_EXPRCURV_CONVEX, success, &dummy) );
758 
759  /* now h also needs to be concave; and if f < 0, then h actually needs to be linear */
760  if( fbounds.inf < 0.0 )
761  hcurv = SCIP_EXPRCURV_LINEAR;
762  else
763  hcurv = SCIP_EXPRCURV_CONCAVE;
764  }
765  else
766  {
767  SCIP_CALL( SCIPcallExprCurvature(scip, f, SCIP_EXPRCURV_CONCAVE, success, &dummy) );
768 
769  /* now h also needs to be convex; and if f > 0, then h actually needs to be linear */
770  if( fbounds.sup > 0.0 )
771  hcurv = SCIP_EXPRCURV_LINEAR;
772  else
773  hcurv = SCIP_EXPRCURV_CONVEX;
774  }
775  }
776 
777  if( !*success )
778  return SCIP_OKAY;
779 
780  /* add immediate children (f and ch) to nlexpr; we set required curvature for h further below */
781  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, nlexpr, NULL) );
782  assert(SCIPexprGetNChildren(nlexpr) == 2);
783 
784  /* copy of f (and h) should have same child position in nlexpr as f (and h) has on expr (resp) */
785  assert(SCIPhashmapGetImage(nlexpr2origexpr, (void*)SCIPexprGetChildren(nlexpr)[fidx]) == (void*)f);
786 #ifndef NLHDLR_CONVEX_UNITTEST
787  assert(SCIPhashmapGetImage(nlexpr2origexpr, (void*)SCIPexprGetChildren(nlexpr)[1-fidx]) == (void*)h);
788 #endif
789  /* push this h onto stack for further checking */
790  SCIP_CALL( exprstackPush(scip, stack, 1, &(SCIPexprGetChildren(nlexpr)[1-fidx])) );
791 
792  /* if we prefer extended formulations, then we always want h() to be linear */
793  if( nlhdlrdata->extendedform )
794  hcurv = SCIP_EXPRCURV_LINEAR;
795 
796  /* h-child of product should have curvature hcurv */
797  SCIPexprSetCurvature(SCIPexprGetChildren(nlexpr)[1-fidx], hcurv);
798 
799  if( h != ch )
800  {
801  /* add copy of ch as child to copy of f */
802  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, SCIPexprGetChildren(nlexpr)[fidx], NULL) );
803  assert(SCIPexprGetNChildren(SCIPexprGetChildren(nlexpr)[fidx]) == 1);
804  assert(SCIPhashmapGetImage(nlexpr2origexpr, (void*)SCIPexprGetChildren(SCIPexprGetChildren(nlexpr)[fidx])[0]) == (void*)ch);
805 
806  /* add copy of h (created above as child of product) as child in copy of ch */
808  SCIPexprGetChildren(SCIPexprGetChildren(nlexpr)[fidx])[0] /* copy of ch */,
809  SCIPexprGetChildren(nlexpr)[1-fidx] /* copy of h */) );
810  }
811  else
812  {
813  /* add copy of h (created above as child of product) as child in copy of f */
815  SCIPexprGetChildren(nlexpr)[fidx] /* copy of f */,
816  SCIPexprGetChildren(nlexpr)[1-fidx] /* copy of h */) );
817  }
818 
819  return SCIP_OKAY;
820 }
821 
822 /** use expression handlers curvature callback to check whether given curvature can be achieved */
823 static
824 DECL_CURVCHECK(curvCheckExprhdlr)
825 { /*lint --e{715}*/
826  SCIP_EXPR* origexpr;
827  int nchildren;
828  SCIP_EXPRCURV* childcurv;
829 
830  assert(nlexpr != NULL);
831  assert(stack != NULL);
832  assert(nlexpr2origexpr != NULL);
833  assert(success != NULL);
834 
835  origexpr = (SCIP_EXPR*)SCIPhashmapGetImage(nlexpr2origexpr, nlexpr);
836  assert(origexpr != NULL);
837  nchildren = SCIPexprGetNChildren(origexpr);
838 
839  if( nchildren == 0 )
840  {
841  /* if originally no children, then should be var or value, which should have every curvature,
842  * so should always be success
843  */
844  SCIP_CALL( SCIPcallExprCurvature(scip, origexpr, SCIPexprGetCurvature(nlexpr), success, NULL) );
845  assert(*success);
846 
847  return SCIP_OKAY;
848  }
849 
850  /* ignore sums if > 1 children
851  * NOTE: this means that for something like 1+f(x), even if f is a trivial convex expression, we would handle 1+f(x)
852  * with this nlhdlr, instead of formulating this as 1+z and handling z=f(x) with the default nlhdlr, i.e., the exprhdlr
853  * today, I prefer handling this here, as it avoids introducing an extra auxiliary variable
854  */
855  if( isrootexpr && !nlhdlrdata->detectsum && SCIPisExprSum(scip, nlexpr) && nchildren > 1 )
856  return SCIP_OKAY;
857 
858  SCIP_CALL( SCIPallocBufferArray(scip, &childcurv, nchildren) );
859 
860  /* check whether and under which conditions origexpr can have desired curvature */
861  SCIP_CALL( SCIPcallExprCurvature(scip, origexpr, SCIPexprGetCurvature(nlexpr), success, childcurv) );
862 #ifdef SCIP_MORE_DEBUG
863  SCIPprintExpr(scip, origexpr, NULL);
864  SCIPinfoMessage(scip, NULL, " is %s? %d\n", SCIPexprcurvGetName(SCIPexprGetCurvature(nlexpr)), *success);
865 #endif
866  if( !*success )
867  goto TERMINATE;
868 
869  /* if origexpr can have curvature curv, then don't treat it as leaf, but include its children */
870  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, nlexpr, childcurv) );
871  assert(SCIPexprGetChildren(nlexpr) != NULL);
872  assert(SCIPexprGetNChildren(nlexpr) == nchildren);
873 
874  /* If we prefer extended formulations, then require all children to be linear.
875  * Unless they are, auxvars will be introduced and they will be handles as variables, which can be an
876  * advantage in the context of extended formulations.
877  */
878  if( nlhdlrdata->extendedform )
879  {
880  int i;
881  for( i = 0; i < nchildren; ++i )
883 #ifdef SCIP_DEBUG
884  SCIPinfoMessage(scip, NULL, "require linearity for children of ");
885  SCIPprintExpr(scip, origexpr, NULL);
886  SCIPinfoMessage(scip, NULL, "\n");
887 #endif
888  }
889 
890  /* add children expressions to to-do list (stack) */
891  SCIP_CALL( exprstackPush(scip, stack, nchildren, SCIPexprGetChildren(nlexpr)) );
892 
893 TERMINATE:
894  SCIPfreeBufferArray(scip, &childcurv);
895 
896  return SCIP_OKAY;
897 }
898 
899 /** curvature check and expression-growing methods
900  *
901  * some day this could be plugins added by users at runtime, but for now we have a fixed list here
902  * @note curvCheckExprhdlr should be last
903  */
904 static DECL_CURVCHECK((*CURVCHECKS[])) = { curvCheckProductComposite, curvCheckSignomial, curvCheckQuadratic, curvCheckExprhdlr };
905 /** number of curvcheck methods */
906 static const int NCURVCHECKS = sizeof(CURVCHECKS) / sizeof(void*);
907 
908 /** checks whether expression is a sum with more than one child and each child being a variable or going to be a variable if `expr` is a nlhdlr-specific copy
909  *
910  * Within constructExpr(), we can have an expression of any type which is a copy of an original expression,
911  * but without children. At the end of constructExpr() (after the loop with the stack), these expressions
912  * will remain as leafs and will eventually be turned into variables in collectLeafs(). Thus, we treat
913  * every child that has no children as if it were a variable. Theoretically, there is still the possibility
914  * that it could be a constant (value-expression), but simplify should have removed these.
915  */
916 static
918  SCIP* scip, /**< SCIP data structure */
919  SCIP_EXPR* expr /**< expression to check */
920  )
921 {
922  int nchildren;
923  int c;
924 
925  assert(expr != NULL);
926 
927  if( !SCIPisExprSum(scip, expr) )
928  return FALSE;
929 
930  nchildren = SCIPexprGetNChildren(expr);
931  if( nchildren <= 1 )
932  return FALSE;
933 
934  for( c = 0; c < nchildren; ++c )
935  /*if( !SCIPisExprVar(scip, SCIPexprGetChildren(expr)[c]) ) */
936  if( SCIPexprGetNChildren(SCIPexprGetChildren(expr)[c]) > 0 )
937  return FALSE;
938 
939  return TRUE;
940 }
941 
942 /** constructs a subexpression (as nlhdlr-expression) of maximal size that has a given curvature
943  *
944  * If the curvature cannot be achieved for an expression in the original expression graph,
945  * then this expression becomes a leaf in the nlhdlr-expression.
946  *
947  * Sets `*rootnlexpr` to NULL if failed.
948  */
949 static
951  SCIP* scip, /**< SCIP data structure */
952  SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
953  SCIP_EXPR** rootnlexpr, /**< buffer to store created expression */
954  SCIP_HASHMAP* nlexpr2origexpr, /**< mapping from our expression copy to original expression */
955  int* nleafs, /**< number of leafs in constructed expression */
956  SCIP_EXPR* rootexpr, /**< expression */
957  SCIP_EXPRCURV curv, /**< curvature to achieve */
958  SCIP_HASHMAP* assumevarfixed, /**< hashmap containing variables that should be assumed to be fixed, or NULL */
959  SCIP_Bool assumecurvature, /**< whether to assume that desired curvature is given (skips curvature checks) */
960  SCIP_Bool* curvsuccess /**< pointer to store whether the curvature could be achieved
961  w.r.t. the original variables (might be NULL) */
962  )
963 {
964  SCIP_EXPR* nlexpr;
965  EXPRSTACK stack; /* to do list: expressions where to check whether they can have the desired curvature when taking their children into account */
966  int oldstackpos;
967  SCIP_Bool isrootexpr = TRUE;
968 
969  assert(scip != NULL);
970  assert(nlhdlrdata != NULL);
971  assert(rootnlexpr != NULL);
972  assert(nlexpr2origexpr != NULL);
973  assert(nleafs != NULL);
974  assert(rootexpr != NULL);
975  assert(curv == SCIP_EXPRCURV_CONVEX || curv == SCIP_EXPRCURV_CONCAVE);
976 
977  /* create root expression */
978  SCIP_CALL( nlhdlrExprCreate(scip, nlexpr2origexpr, rootnlexpr, rootexpr, curv) );
979 
980  *nleafs = 0;
981  if( curvsuccess != NULL )
982  *curvsuccess = TRUE;
983 
984  SCIP_CALL( exprstackInit(scip, &stack, 20) );
985  SCIP_CALL( exprstackPush(scip, &stack, 1, rootnlexpr) );
986  while( !exprstackIsEmpty(&stack) )
987  {
988  /* take expression from stack */
989  nlexpr = exprstackPop(&stack);
990  assert(nlexpr != NULL);
991  assert(SCIPexprGetNChildren(nlexpr) == 0);
992 
993  oldstackpos = stack.stackpos;
994  if( nlhdlrdata->isnlhdlrconvex && !SCIPexprhdlrHasBwdiff(SCIPexprGetHdlr(nlexpr)) )
995  {
996  /* if bwdiff is not implemented, then we could not generate cuts in the convex nlhdlr, so "stop" (treat nlexpr as variable) */
997  }
998  else if( !nlhdlrdata->isnlhdlrconvex && exprIsMultivarLinear(scip, (SCIP_EXPR*)SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlexpr)) )
999  {
1000  /* if we are in the concave handler, we would like to treat linear multivariate subexpressions by a new auxvar always,
1001  * e.g., handle log(x+y) as log(z), z=x+y, because the estimation problem will be smaller then without making the estimator worse
1002  * (cons_nonlinear does this, too)
1003  * this check takes care of this when x and y are original variables
1004  * however, it isn't unlikely that we will have sums that become linear after we add auxvars for some children
1005  * this will be handled in a postprocessing below
1006  * for now, the check is performed on the original expression since there is not enough information in nlexpr yet
1007  */
1008 #ifdef SCIP_MORE_DEBUG
1009  SCIPprintExpr(scip, SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlexpr), NULL);
1010  SCIPinfoMessage(scip, NULL, "... is a multivariate linear sum that we'll treat as auxvar\n");
1011 #endif
1012  }
1013  else if( SCIPexprGetCurvature(nlexpr) != SCIP_EXPRCURV_UNKNOWN && !assumecurvature )
1014  {
1015  /* if we are here, either convexity or concavity is required; try to check for this curvature */
1016  SCIP_Bool success;
1017  int method;
1018 
1019  /* try through curvature check methods until one succeeds */
1020  for( method = 0; method < NCURVCHECKS; ++method )
1021  {
1022  SCIP_CALL( CURVCHECKS[method](scip, nlexpr, isrootexpr, &stack, nlexpr2origexpr, nlhdlrdata, assumevarfixed, &success) );
1023  if( success )
1024  break;
1025  }
1026  }
1027  else
1028  {
1029  /* if we don't care about curvature in this subtree anymore (very unlikely),
1030  * or we are told to assume that the desired curvature is present (assumecurvature==TRUE),
1031  * then only continue iterating this subtree to assemble leaf expressions
1032  */
1033  SCIP_CALL( nlhdlrExprGrowChildren(scip, nlexpr2origexpr, nlexpr, NULL) );
1034 
1035  /* add children expressions, if any, to to-do list (stack) */
1036  SCIP_CALL( exprstackPush(scip, &stack, SCIPexprGetNChildren(nlexpr), SCIPexprGetChildren(nlexpr)) );
1037  }
1038  assert(stack.stackpos >= oldstackpos); /* none of the methods above should have removed something from the stack */
1039 
1040  isrootexpr = FALSE;
1041 
1042  /* if nothing was added, then none of the successors of nlexpr were added to the stack
1043  * this is either because nlexpr was already a variable or value expressions, thus a leaf,
1044  * or because the desired curvature could not be achieved, so it will be handled as variables, thus a leaf
1045  */
1046  if( stack.stackpos == oldstackpos )
1047  {
1048  ++*nleafs;
1049 
1050  /* check whether the new leaf is not an original variable (or constant) */
1051  if( curvsuccess != NULL && !SCIPisExprVar(scip, nlexpr) && !SCIPisExprValue(scip, nlexpr) )
1052  *curvsuccess = FALSE;
1053  }
1054  }
1055 
1056  exprstackFree(scip, &stack);
1057 
1058  if( !nlhdlrdata->isnlhdlrconvex && *rootnlexpr != NULL )
1059  {
1060  /* remove multivariate linear subexpressions, that is, change some f(z1+z2) into f(z3) (z3=z1+z2 will be done by nlhdlr_default)
1061  * this handles the case that was not covered by the above check, which could recognize f(x+y) for x, y original variables
1062  */
1063  SCIP_EXPRITER* it;
1064 
1065  SCIP_CALL( SCIPcreateExpriter(scip, &it) );
1066  SCIP_CALL( SCIPexpriterInit(it, *rootnlexpr, SCIP_EXPRITER_DFS, FALSE) );
1068 
1069  while( !SCIPexpriterIsEnd(it) )
1070  {
1071  SCIP_EXPR* child;
1072 
1073  child = SCIPexpriterGetChildExprDFS(it);
1074  assert(child != NULL);
1075 
1076  /* We want to change some f(x+y+z) into just f(), where f is the expression the iterator points to
1077  * and x+y+z is child. A child of a child, e.g., z, may not be a variable yet (these are added in collectLeafs later),
1078  * but an expression of some nonlinear type without children.
1079  */
1080  if( exprIsMultivarLinear(scip, child) )
1081  {
1082  /* turn child (x+y+z) into a sum without children
1083  * collectLeafs() should then replace this by an auxvar
1084  */
1085 #ifdef SCIP_MORE_DEBUG
1086  SCIPprintExpr(scip, child, NULL);
1087  SCIPinfoMessage(scip, NULL, "... is a multivariate linear sum that we'll treat as auxvar instead (postprocess)\n");
1088 #endif
1089 
1090  /* TODO remove children from nlexpr2origexpr ?
1091  * should also do this if they are not used somewhere else; we could check nuses for this
1092  * however, it shouldn't matter to have some stray entries in the hashmap either
1093  */
1094  SCIP_CALL( SCIPremoveExprChildren(scip, child) );
1095  assert(SCIPexprGetNChildren(child) == 0);
1096 
1097  (void) SCIPexpriterSkipDFS(it);
1098  }
1099  else
1100  {
1101  (void) SCIPexpriterGetNext(it);
1102  }
1103  }
1104 
1105  SCIPfreeExpriter(&it);
1106  }
1107 
1108  if( *rootnlexpr != NULL )
1109  {
1110  SCIP_Bool istrivial = TRUE;
1111 
1112  /* if handletrivial is enabled, then only require that rootnlexpr itself has required curvature (so has children; see below) and
1113  * that we are not a trivial sum (because the previous implementation of this nlhdlr didn't allow this, either)
1114  */
1115  if( !nlhdlrdata->handletrivial || SCIPisExprSum(scip, *rootnlexpr) )
1116  {
1117  /* if all children do not have children, i.e., are variables, or will be replaced by auxvars, then free
1118  * also if rootnlexpr has no children, then free
1119  */
1120  int i;
1121  for( i = 0; i < SCIPexprGetNChildren(*rootnlexpr); ++i )
1122  {
1123  if( SCIPexprGetNChildren(SCIPexprGetChildren(*rootnlexpr)[i]) > 0 )
1124  {
1125  istrivial = FALSE;
1126  break;
1127  }
1128  }
1129  }
1130  else if( SCIPexprGetNChildren(*rootnlexpr) > 0 ) /* if handletrivial, then just require children */
1131  istrivial = FALSE;
1132 
1133  if( istrivial )
1134  {
1135  SCIP_CALL( SCIPreleaseExpr(scip, rootnlexpr) );
1136  }
1137  }
1138 
1139  return SCIP_OKAY;
1140 }
1141 
1142 /** collects (non-value) leaf expressions and ensure that they correspond to a variable (original or auxiliary)
1143  *
1144  * For children where we could not achieve the desired curvature, get the auxvar and replace the child by a
1145  * var-expression that points to this auxvar.
1146  * Collect all leaf expressions (if not a value-expression) and index them.
1147  */
1148 static
1150  SCIP* scip, /**< SCIP data structure */
1151  SCIP_NLHDLREXPRDATA* nlhdlrexprdata /**< nlhdlr expression data */
1152  )
1153 {
1154  SCIP_EXPRITER* it;
1155  SCIP_EXPR* nlexpr;
1156  SCIP_HASHMAP* leaf2index;
1157  int i;
1158 
1159  assert(nlhdlrexprdata != NULL);
1160  assert(nlhdlrexprdata->nlexpr != NULL);
1161  assert(nlhdlrexprdata->nlexpr2origexpr != NULL);
1162  /* nleafs should be the upper bound on the number of variables given by constructExpr
1163  * leafexprs should be NULL, as this is what we want to setup here
1164  */
1165  assert(nlhdlrexprdata->nleafs > 0);
1166  assert(nlhdlrexprdata->leafexprs == NULL);
1167 
1168  /* collect all auxvars and collect all variables */
1169  SCIP_CALL( SCIPhashmapCreate(&leaf2index, SCIPblkmem(scip), nlhdlrexprdata->nleafs) );
1170  nlhdlrexprdata->nleafs = 0; /* we start a new count, this time skipping value-expressions */
1171 
1172  SCIP_CALL( SCIPcreateExpriter(scip, &it) );
1173  SCIP_CALL( SCIPexpriterInit(it, nlhdlrexprdata->nlexpr, SCIP_EXPRITER_DFS, FALSE) );
1175 
1176  for( nlexpr = SCIPexpriterGetCurrent(it); !SCIPexpriterIsEnd(it); nlexpr = SCIPexpriterGetNext(it) )
1177  {
1178  SCIP_EXPR* child;
1179  SCIP_EXPR* origexpr;
1180 
1181  assert(nlexpr != NULL);
1182 
1183  child = SCIPexpriterGetChildExprDFS(it);
1184 
1185  /* if the to-be-visited child has children, then it doesn't need to be replaced by a new expression (representing the auxvar) */
1186  if( SCIPexprGetNChildren(child) > 0 )
1187  continue;
1188 
1189  origexpr = (SCIP_EXPR*)SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)child);
1190  assert(origexpr != NULL);
1191 
1192  if( SCIPexprGetNChildren(origexpr) > 0 )
1193  {
1194  SCIP_EXPR* newchild;
1195  int childidx;
1196  SCIP_VAR* var;
1197 
1198  /* having a child that had children in original but not in copy means that we could not achieve the desired curvature
1199  * thus, replace by a new child that points to the auxvar of the original expression
1200  * we registered in createNlhdlrExprData that we need an auxvar, so it should exist now
1201  */
1202  var = SCIPgetExprAuxVarNonlinear(origexpr);
1203  assert(var != NULL);
1204 
1205  SCIP_CALL( SCIPcreateExprVar(scip, &newchild, var, NULL, NULL) ); /* this captures newchild once */
1206 
1207  childidx = SCIPexpriterGetChildIdxDFS(it);
1208  SCIP_CALL( SCIPreplaceExprChild(scip, nlexpr, childidx, newchild) ); /* this captures newchild again */
1209 
1210  /* do not remove child->origexpr from hashmap, as child may appear again due to common subexprs
1211  * (created by curvCheckProductComposite, for example)
1212  * if it doesn't reappear, though, but the memory address is reused, we need to make sure it
1213  * points to the right origexpr
1214  */
1215  /* SCIP_CALL( SCIPhashmapRemove(nlexpr2origexpr, (void*)child) ); */
1216  SCIP_CALL( SCIPhashmapSetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)newchild, (void*)origexpr) );
1217 
1218  if( !SCIPhashmapExists(leaf2index, (void*)newchild) )
1219  {
1220  /* new leaf -> new index and remember in hashmap */
1221  SCIP_CALL( SCIPhashmapInsertInt(leaf2index, (void*)newchild, nlhdlrexprdata->nleafs++) );
1222  }
1223 
1224  child = newchild;
1225  SCIP_CALL( SCIPreleaseExpr(scip, &newchild) ); /* because it was captured by both create and replace */
1226  }
1227  else if( SCIPisExprVar(scip, child) )
1228  {
1229  /* if variable, then add to hashmap, if not already there */
1230  if( !SCIPhashmapExists(leaf2index, (void*)child) )
1231  {
1232  SCIP_CALL( SCIPhashmapInsertInt(leaf2index, (void*)child, nlhdlrexprdata->nleafs++) );
1233  }
1234  }
1235  /* else: it's probably a value-expression, nothing to do */
1236 
1237  /* update integrality flag for future leaf expressions: convex nlhdlr may use this information */
1238  SCIP_CALL( SCIPcomputeExprIntegrality(scip, child) );
1239  }
1240  assert(nlhdlrexprdata->nleafs > 0);
1241 
1242  SCIPfreeExpriter(&it);
1243 
1244  /* assemble auxvars array */
1245  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(nlhdlrexprdata->leafexprs), nlhdlrexprdata->nleafs) );
1246  for( i = 0; i < SCIPhashmapGetNEntries(leaf2index); ++i )
1247  {
1248  SCIP_HASHMAPENTRY* entry;
1249  SCIP_EXPR* leaf;
1250  int idx;
1251 
1252  entry = SCIPhashmapGetEntry(leaf2index, i);
1253  if( entry == NULL )
1254  continue;
1255 
1256  leaf = (SCIP_EXPR*) SCIPhashmapEntryGetOrigin(entry);
1257  assert(leaf != NULL);
1258  assert(SCIPisExprVar(scip, leaf));
1259 
1260  idx = SCIPhashmapEntryGetImageInt(entry);
1261  assert(idx >= 0);
1262  assert(idx < nlhdlrexprdata->nleafs);
1263 
1264  nlhdlrexprdata->leafexprs[idx] = leaf;
1265 
1266  SCIPdebugMsg(scip, "leaf %d: <%s>\n", idx, SCIPvarGetName(SCIPgetVarExprVar(leaf)));
1267  }
1268 
1269  SCIPhashmapFree(&leaf2index);
1270 
1271  return SCIP_OKAY;
1272 }
1273 
1274 /** creates nonlinear handler expression data structure and registers expr usage */
1275 static
1277  SCIP* scip, /**< SCIP data structure */
1278  SCIP_NLHDLRDATA* nlhdlrdata, /**< nlhdlr data */
1279  SCIP_NLHDLREXPRDATA** nlhdlrexprdata, /**< pointer to store nlhdlr expression data */
1280  SCIP_EXPR* expr, /**< original expression */
1281  SCIP_EXPR* nlexpr, /**< our copy of expression */
1282  SCIP_HASHMAP* nlexpr2origexpr, /**< mapping of expression copy to original */
1283  int nleafs, /**< number of leafs as counted by constructExpr */
1284  SCIP_NLHDLR_METHOD participating /**< the enfo methods in which we plan to participate */
1285  )
1286 {
1287  SCIP_EXPRITER* it;
1288  SCIP_Bool usingaux;
1289 
1290  assert(scip != NULL);
1291  assert(expr != NULL);
1292  assert(nlhdlrexprdata != NULL);
1293  assert(*nlhdlrexprdata == NULL);
1294  assert(nlexpr != NULL);
1295  assert(nlexpr2origexpr != NULL);
1296 
1297  assert(SCIPexprGetNChildren(nlexpr) > 0);
1298  assert(SCIPexprGetChildren(nlexpr) != NULL);
1299 
1300  SCIP_CALL( SCIPallocClearBlockMemory(scip, nlhdlrexprdata) );
1301  (*nlhdlrexprdata)->nlexpr = nlexpr;
1302  (*nlhdlrexprdata)->nlexpr2origexpr = nlexpr2origexpr;
1303  (*nlhdlrexprdata)->nleafs = nleafs;
1304 
1305  usingaux = FALSE;
1306 
1307  SCIP_CALL( SCIPcreateExpriter(scip, &it) );
1310 
1311  for( ; !SCIPexpriterIsEnd(it); (void) SCIPexpriterGetNext(it) )
1312  {
1313  SCIP_EXPR* child;
1314  SCIP_EXPR* origexpr;
1315 
1316  /* check whether to-be-visited child needs to be replaced by a new expression (representing the auxvar)
1317  * if child has children, then that is not the case
1318  * if child has no children, but also corresponding origexpr has no chilren, then this is also not the case
1319  */
1320  child = SCIPexpriterGetChildExprDFS(it);
1321  if( SCIPexprGetNChildren(child) > 0 )
1322  continue;
1323 
1324  origexpr = (SCIP_EXPR*)SCIPhashmapGetImage(nlexpr2origexpr, (void*)child);
1325  assert(origexpr != NULL);
1326 
1327  /* if child had children in original but not in copy means that we could not achieve the desired curvature
1328  * thus, we will later replace by a new child that points to the auxvar of the original expression
1329  * as we do not have the auxvar now, we will only register that we will need the auxvar later (if origexpr isn't a variable or constant)
1330  * if we are working for the concave nlhdlr, then we also indicate interest on the exprs activity for estimate (distinguish below or above)
1331  */
1332  SCIP_CALL( SCIPregisterExprUsageNonlinear(scip, origexpr,
1333  SCIPexprGetNChildren(origexpr) > 0, FALSE,
1334  !nlhdlrdata->isnlhdlrconvex && (participating & SCIP_NLHDLR_METHOD_SEPABELOW),
1335  !nlhdlrdata->isnlhdlrconvex && (participating & SCIP_NLHDLR_METHOD_SEPAABOVE)) );
1336 
1337  /* remember that we use an auxvar */
1338  if( SCIPexprGetNChildren(origexpr) > 0 )
1339  usingaux = TRUE;
1340  }
1341 
1342  SCIPfreeExpriter(&it);
1343 
1344 #ifdef SCIP_DEBUG
1345  SCIPprintExpr(scip, nlexpr, NULL);
1346  SCIPinfoMessage(scip, NULL, " (%p) is handled as %s\n", SCIPhashmapGetImage(nlexpr2origexpr, (void*)nlexpr),
1348 #endif
1349 
1350  /* If we don't work on the extended formulation, then set curvature also in original expression
1351  * (in case someone wants to pick this up; this might be removed again).
1352  * This doesn't ensure that every convex or concave original expression is actually marked here.
1353  * Not only because our tests are incomprehensive, but also because we may not detect on sums,
1354  * prefer extended formulations (in nlhdlr_convex), or introduce auxvars for linear subexpressions
1355  * on purpose (in nlhdlr_concave).
1356  */
1357  if( !usingaux )
1359 
1360  return SCIP_OKAY;
1361 }
1362 
1363 /** adds an estimator for a vertex-polyhedral (e.g., concave) function to a given rowprep
1364  *
1365  * Calls \ref SCIPcomputeFacetVertexPolyhedralNonlinear() for given function and
1366  * box set to local bounds of auxiliary variables.
1367  */
1368 static
1370  SCIP* scip, /**< SCIP data structure */
1371  SCIP_CONSHDLR* conshdlr, /**< nonlinear constraint handler */
1372  SCIP_NLHDLR* nlhdlr, /**< nonlinear handler */
1373  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
1374  SCIP_SOL* sol, /**< solution to use, unless usemidpoint is TRUE */
1375  SCIP_Bool usemidpoint, /**< whether to use the midpoint of the domain instead of sol */
1376  SCIP_Bool overestimate, /**< whether over- or underestimating */
1377  SCIP_Real targetvalue, /**< a target value to achieve; if not reachable, then can give up early */
1378  SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
1379  SCIP_Bool* success /**< buffer to store whether successful */
1380  )
1381 {
1382  SCIP_NLHDLRDATA* nlhdlrdata;
1383  VERTEXPOLYFUN_EVALDATA evaldata;
1384  SCIP_Real* xstar;
1385  SCIP_Real* box;
1386  SCIP_Real facetconstant;
1387  SCIP_VAR* var;
1388  int i;
1389  SCIP_Bool allfixed;
1390 
1391  assert(scip != NULL);
1392  assert(nlhdlr != NULL);
1393  assert(nlhdlrexprdata != NULL);
1394  assert(rowprep != NULL);
1395  assert(success != NULL);
1396 
1397  *success = FALSE;
1398 
1399  /* caller is responsible to have checked whether we can estimate, i.e., expression curvature and overestimate flag match */
1400  assert( overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONCAVE); /* if underestimate, then must be concave */
1401  assert(!overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONVEX); /* if overestimate, then must be convex */
1402 
1403 #ifdef SCIP_DEBUG
1404  SCIPinfoMessage(scip, NULL, "%sestimate expression ", overestimate ? "over" : "under");
1405  SCIPprintExpr(scip, nlhdlrexprdata->nlexpr, NULL);
1406  SCIPinfoMessage(scip, NULL, " at point\n");
1407  for( i = 0; i < nlhdlrexprdata->nleafs; ++i )
1408  {
1409  var = SCIPgetVarExprVar(nlhdlrexprdata->leafexprs[i]);
1410  assert(var != NULL);
1411 
1412  SCIPinfoMessage(scip, NULL, " <%s> = %g [%g,%g]\n", SCIPvarGetName(var),
1413  usemidpoint ? 0.5 * (SCIPvarGetLbLocal(var) + SCIPvarGetUbLocal(var)) : SCIPgetSolVal(scip, sol, var),
1415  }
1416 #endif
1417 
1418  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1419  assert(nlhdlrdata != NULL);
1420 
1421  if( nlhdlrdata->evalsol == NULL )
1422  {
1423  SCIP_CALL( SCIPcreateSol(scip, &nlhdlrdata->evalsol, NULL) );
1424  }
1425 
1426  evaldata.nlhdlrexprdata = nlhdlrexprdata;
1427  evaldata.evalsol = nlhdlrdata->evalsol;
1428  evaldata.scip = scip;
1429 
1430  SCIP_CALL( SCIPallocBufferArray(scip, &xstar, nlhdlrexprdata->nleafs) );
1431  SCIP_CALL( SCIPallocBufferArray(scip, &box, 2*nlhdlrexprdata->nleafs) );
1432 
1433  allfixed = TRUE;
1434  for( i = 0; i < nlhdlrexprdata->nleafs; ++i )
1435  {
1436  var = SCIPgetVarExprVar(nlhdlrexprdata->leafexprs[i]);
1437  assert(var != NULL);
1438 
1439  box[2*i] = SCIPvarGetLbLocal(var);
1440  if( SCIPisInfinity(scip, -box[2*i]) )
1441  {
1442  SCIPdebugMsg(scip, "lower bound at -infinity, no estimate possible\n");
1443  goto TERMINATE;
1444  }
1445 
1446  box[2*i+1] = SCIPvarGetUbLocal(var);
1447  if( SCIPisInfinity(scip, box[2*i+1]) )
1448  {
1449  SCIPdebugMsg(scip, "upper bound at +infinity, no estimate possible\n");
1450  goto TERMINATE;
1451  }
1452 
1453  if( !SCIPisRelEQ(scip, box[2*i], box[2*i+1]) )
1454  allfixed = FALSE;
1455 
1456  if( usemidpoint )
1457  xstar[i] = 0.5 * (box[2*i] + box[2*i+1]);
1458  else
1459  xstar[i] = SCIPgetSolVal(scip, sol, var);
1460  assert(xstar[i] != SCIP_INVALID);
1461  }
1462 
1463  if( allfixed )
1464  {
1465  /* SCIPcomputeFacetVertexPolyhedralNonlinear prints a warning and does not succeed if all is fixed */
1466  SCIPdebugMsg(scip, "all variables fixed, skip estimate\n");
1467  goto TERMINATE;
1468  }
1469 
1470  SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nlhdlrexprdata->nleafs + 1) );
1471 
1472  SCIP_CALL( SCIPcomputeFacetVertexPolyhedralNonlinear(scip, conshdlr, overestimate, nlhdlrExprEvalConcave, (void*)&evaldata,
1473  xstar, box, nlhdlrexprdata->nleafs, targetvalue, success, SCIProwprepGetCoefs(rowprep), &facetconstant) );
1474 
1475  if( !*success )
1476  {
1477  SCIPdebugMsg(scip, "failed to compute facet of convex hull\n");
1478  goto TERMINATE;
1479  }
1480 
1481  SCIProwprepSetLocal(rowprep, TRUE);
1482  SCIProwprepAddConstant(rowprep, facetconstant);
1483  for( i = 0; i < nlhdlrexprdata->nleafs; ++i )
1484  {
1485  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetVarExprVar(nlhdlrexprdata->leafexprs[i]), SCIProwprepGetCoefs(rowprep)[i]) );
1486  }
1487 
1488 #ifdef SCIP_DEBUG
1489  SCIPinfoMessage(scip, NULL, "computed estimator: ");
1490  SCIPprintRowprep(scip, rowprep, NULL);
1491 #endif
1492 
1493  TERMINATE:
1494  SCIPfreeBufferArray(scip, &box);
1495  SCIPfreeBufferArray(scip, &xstar);
1496 
1497  return SCIP_OKAY;
1498 }
1499 
1500 /** adds an estimator computed via a gradient to a given rowprep */
1501 static
1503  SCIP* scip, /**< SCIP data structure */
1504  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
1505  SCIP_SOL* sol, /**< solution to use */
1506  SCIP_Real auxvalue, /**< value of nlexpr in sol - we may not be able to take this value
1507  from nlexpr if it was evaluated at a different sol recently */
1508  SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
1509  SCIP_Bool* success /**< buffer to store whether successful */
1510  )
1511 {
1512  SCIP_EXPR* nlexpr;
1513  SCIP_Real QUAD(constant);
1514  int i;
1515 
1516  assert(nlhdlrexprdata != NULL);
1517  assert(rowprep != NULL);
1518  assert(success != NULL);
1519 
1520  nlexpr = nlhdlrexprdata->nlexpr;
1521  assert(nlexpr != NULL);
1522 
1523 #ifdef SCIP_DEBUG
1524  SCIPinfoMessage(scip, NULL, "estimate expression ");
1525  SCIPprintExpr(scip, nlexpr, NULL);
1526  SCIPinfoMessage(scip, NULL, " by gradient\n");
1527 #endif
1528 
1529  *success = FALSE;
1530 
1531  /* evaluation error -> skip */
1532  if( auxvalue == SCIP_INVALID )
1533  {
1534  SCIPdebugMsg(scip, "evaluation error / too large value (%g) for %p\n", auxvalue, (void*)nlexpr);
1535  return SCIP_OKAY;
1536  }
1537 
1538  /* compute gradient (TODO: this also re-evaluates (soltag=0), which shouldn't be necessary unless we tried ConvexSecant before) */
1539  SCIP_CALL( SCIPevalExprGradient(scip, nlexpr, sol, 0L) );
1540 
1541  /* gradient evaluation error -> skip */
1542  if( SCIPexprGetDerivative(nlexpr) == SCIP_INVALID )
1543  {
1544  SCIPdebugMsg(scip, "gradient evaluation error for %p\n", (void*)nlexpr);
1545  return SCIP_OKAY;
1546  }
1547 
1548  /* add gradient underestimator to rowprep: f(sol) + (x - sol) \nabla f(sol)
1549  * constant will store f(sol) - sol * \nabla f(sol)
1550  * to avoid some cancellation errors when linear variables take huge values (like 1e20),
1551  * we use double-double arithemtic here
1552  */
1553  QUAD_ASSIGN(constant, SCIPexprGetEvalValue(nlexpr)); /* f(sol) */
1554  for( i = 0; i < nlhdlrexprdata->nleafs; ++i )
1555  {
1556  SCIP_VAR* var;
1557  SCIP_Real deriv;
1558  SCIP_Real varval;
1559 
1560  assert(SCIPexprGetDiffTag(nlhdlrexprdata->leafexprs[i]) == SCIPexprGetDiffTag(nlexpr));
1561  deriv = SCIPexprGetDerivative(nlhdlrexprdata->leafexprs[i]);
1562  if( deriv == SCIP_INVALID )
1563  {
1564  SCIPdebugMsg(scip, "gradient evaluation error for component %d of %p\n", i, (void*)nlexpr);
1565  return SCIP_OKAY;
1566  }
1567 
1568  var = SCIPgetVarExprVar(nlhdlrexprdata->leafexprs[i]);
1569  assert(var != NULL);
1570 
1571  varval = SCIPgetSolVal(scip, sol, var);
1572 
1573  SCIPdebugMsg(scip, "add %g * (<%s> - %g) to rowprep\n", deriv, SCIPvarGetName(var), varval);
1574 
1575  /* add deriv * var to rowprep and deriv * (-varval) to constant */
1576  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, var, deriv) );
1577  SCIPquadprecSumQD(constant, constant, -deriv * varval);
1578  }
1579 
1580  SCIProwprepAddConstant(rowprep, QUAD_TO_DBL(constant));
1581  SCIProwprepSetLocal(rowprep, FALSE);
1582 
1583  *success = TRUE;
1584 
1585  return SCIP_OKAY;
1586 }
1587 
1588 /** adds an estimator generated by putting a secant through the coordinates given by the two closest integer points */
1589 static
1591  SCIP* scip, /**< SCIP data structure */
1592  SCIP_NLHDLR* nlhdlr, /**< nonlinear handler */
1593  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
1594  SCIP_SOL* sol, /**< solution to use, unless usemidpoint is TRUE */
1595  SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
1596  SCIP_Bool* success /**< buffer to store whether successful */
1597  )
1598 {
1599  SCIP_NLHDLRDATA* nlhdlrdata;
1600  SCIP_EXPR* nlexpr;
1601  SCIP_VAR* var;
1602  SCIP_Real x;
1603  SCIP_Real left, right;
1604  SCIP_Real fleft, fright;
1605 
1606  assert(nlhdlrexprdata != NULL);
1607  assert(nlhdlrexprdata->nleafs == 1);
1608  assert(rowprep != NULL);
1609  assert(success != NULL);
1610 
1611  nlexpr = nlhdlrexprdata->nlexpr;
1612  assert(nlexpr != NULL);
1613 
1614  *success = FALSE;
1615 
1616  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1617  assert(nlhdlrdata != NULL);
1618 
1619  var = SCIPgetVarExprVar(nlhdlrexprdata->leafexprs[0]);
1620  assert(var != NULL);
1621 
1622  x = SCIPgetSolVal(scip, sol, var);
1623 
1624 #ifdef SCIP_DEBUG
1625  SCIPinfoMessage(scip, NULL, "estimate expression ");
1626  SCIPprintExpr(scip, nlexpr, NULL);
1627  SCIPinfoMessage(scip, NULL, " by secant\n");
1628  SCIPinfoMessage(scip, NULL, "integral variable <%s> = %g [%g,%g]\n", SCIPvarGetName(var),
1629  x, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var));
1630 #endif
1631 
1632  /* find out coordinates of var left and right to sol */
1633  if( SCIPisIntegral(scip, x) )
1634  {
1635  x = SCIPround(scip, x);
1636  if( SCIPisEQ(scip, x, SCIPvarGetLbGlobal(var)) )
1637  {
1638  left = x;
1639  right = left + 1.0;
1640  }
1641  else
1642  {
1643  right = x;
1644  left = right - 1.0;
1645  }
1646  }
1647  else
1648  {
1649  left = SCIPfloor(scip, x);
1650  right = SCIPceil(scip, x);
1651  }
1652  assert(left != right);
1653 
1654  /* now evaluate at left and right */
1655  if( nlhdlrdata->evalsol == NULL )
1656  {
1657  SCIP_CALL( SCIPcreateSol(scip, &nlhdlrdata->evalsol, NULL) );
1658  }
1659 
1660  SCIP_CALL( SCIPsetSolVal(scip, nlhdlrdata->evalsol, var, left) );
1661  SCIP_CALL( SCIPevalExpr(scip, nlexpr, nlhdlrdata->evalsol, 0L) );
1662 
1663  /* evaluation error or a too large constant -> skip */
1664  fleft = SCIPexprGetEvalValue(nlexpr);
1665  if( SCIPisInfinity(scip, REALABS(fleft)) )
1666  {
1667  SCIPdebugMsg(scip, "evaluation error / too large value (%g) for %p\n", SCIPexprGetEvalValue(nlexpr), (void*)nlexpr);
1668  return SCIP_OKAY;
1669  }
1670 
1671  SCIP_CALL( SCIPsetSolVal(scip, nlhdlrdata->evalsol, var, right) );
1672  SCIP_CALL( SCIPevalExpr(scip, nlexpr, nlhdlrdata->evalsol, 0L) );
1673 
1674  /* evaluation error or a too large constant -> skip */
1675  fright = SCIPexprGetEvalValue(nlexpr);
1676  if( SCIPisInfinity(scip, REALABS(fright)) )
1677  {
1678  SCIPdebugMsg(scip, "evaluation error / too large value (%g) for %p\n", SCIPexprGetEvalValue(nlexpr), (void*)nlexpr);
1679  return SCIP_OKAY;
1680  }
1681 
1682  SCIPdebugMsg(scip, "f(%g)=%g, f(%g)=%g\n", left, fleft, right, fright);
1683 
1684  /* skip if too steep
1685  * for clay0204h, this resulted in a wrong cut from f(0)=1e12 f(1)=0.99998,
1686  * since due to limited precision, this was handled as if f(1)=1
1687  */
1688  if( (!SCIPisZero(scip, fleft) && REALABS(fright/fleft)*SCIPepsilon(scip) > 1.0) ||
1689  (!SCIPisZero(scip, fright) && REALABS(fleft/fright)*SCIPepsilon(scip) > 1.0) )
1690  {
1691  SCIPdebugMsg(scip, "function is too steep, abandoning\n");
1692  return SCIP_OKAY;
1693  }
1694 
1695  /* now add f(left) + (f(right) - f(left)) * (x - left) as estimator to rowprep */
1696  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, var, fright - fleft) );
1697  SCIProwprepAddConstant(rowprep, fleft - (fright - fleft) * left);
1698  SCIProwprepSetLocal(rowprep, FALSE);
1699 
1700  *success = TRUE;
1701 
1702  return SCIP_OKAY;
1703 }
1704 
1705 /*
1706  * Callback methods of convex nonlinear handler
1707  */
1708 
1709 /** free handler data of convex or concave nlhdlr */
1710 static
1711 SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrfreeHdlrDataConvexConcave)
1712 { /*lint --e{715}*/
1713  assert(scip != NULL);
1714  assert(nlhdlrdata != NULL);
1715  assert(*nlhdlrdata != NULL);
1716  assert((*nlhdlrdata)->evalsol == NULL);
1717 
1718  SCIPfreeBlockMemory(scip, nlhdlrdata);
1719 
1720  return SCIP_OKAY;
1721 }
1722 
1723 /** callback to free expression specific data */
1724 static
1725 SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrfreeExprDataConvexConcave)
1726 { /*lint --e{715}*/
1727  assert(scip != NULL);
1728  assert(nlhdlrexprdata != NULL);
1729  assert(*nlhdlrexprdata != NULL);
1730 
1731  SCIPfreeBlockMemoryArrayNull(scip, &(*nlhdlrexprdata)->leafexprs, (*nlhdlrexprdata)->nleafs);
1732  SCIP_CALL( SCIPreleaseExpr(scip, &(*nlhdlrexprdata)->nlexpr) );
1733  SCIPhashmapFree(&(*nlhdlrexprdata)->nlexpr2origexpr);
1734 
1735  SCIPfreeBlockMemory(scip, nlhdlrexprdata);
1736 
1737  return SCIP_OKAY;
1738 }
1739 
1740 /** deinitialization of problem-specific data */
1741 static
1742 SCIP_DECL_NLHDLREXIT(nlhdlrExitConvex)
1743 {
1744  SCIP_NLHDLRDATA* nlhdlrdata;
1745 
1746  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1747  assert(nlhdlrdata != NULL);
1748 
1749  if( nlhdlrdata->evalsol != NULL )
1750  {
1751  SCIP_CALL( SCIPfreeSol(scip, &nlhdlrdata->evalsol) );
1752  }
1753 
1754  return SCIP_OKAY;
1755 }
1756 
1757 /** checks whether expression (or -expression) is convex, possibly after introducing auxiliary variables */
1758 static
1759 SCIP_DECL_NLHDLRDETECT(nlhdlrDetectConvex)
1760 { /*lint --e{715}*/
1761  SCIP_NLHDLRDATA* nlhdlrdata;
1762  SCIP_EXPR* nlexpr = NULL;
1763  SCIP_HASHMAP* nlexpr2origexpr;
1764  int nleafs = 0;
1765 
1766  assert(scip != NULL);
1767  assert(nlhdlr != NULL);
1768  assert(expr != NULL);
1769  assert(enforcing != NULL);
1770  assert(participating != NULL);
1771  assert(nlhdlrexprdata != NULL);
1772 
1773  /* we currently do not participate if only activity computation is required */
1774  if( (*enforcing & SCIP_NLHDLR_METHOD_SEPABOTH) == SCIP_NLHDLR_METHOD_SEPABOTH )
1775  return SCIP_OKAY;
1776 
1777  /* ignore pure constants and variables */
1778  if( SCIPexprGetNChildren(expr) == 0 )
1779  return SCIP_OKAY;
1780 
1781  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1782  assert(nlhdlrdata != NULL);
1783  assert(nlhdlrdata->isnlhdlrconvex);
1784 
1785  SCIPdebugMsg(scip, "nlhdlr_convex detect for expr %p\n", (void*)expr);
1786 
1787  /* initialize mapping from copied expression to original one
1788  * 20 is not a bad estimate for the size of convex subexpressions that we can usually discover
1789  * when expressions will be allowed to store "user"data, we could get rid of this hashmap (TODO)
1790  */
1791  SCIP_CALL( SCIPhashmapCreate(&nlexpr2origexpr, SCIPblkmem(scip), 20) );
1792 
1793  if( (*enforcing & SCIP_NLHDLR_METHOD_SEPABELOW) == 0 ) /* if no separation below yet */
1794  {
1795  SCIP_CALL( constructExpr(scip, nlhdlrdata, &nlexpr, nlexpr2origexpr, &nleafs, expr,
1797  if( nlexpr != NULL )
1798  {
1799  assert(SCIPexprGetNChildren(nlexpr) > 0); /* should not be trivial */
1800 
1801  *participating |= SCIP_NLHDLR_METHOD_SEPABELOW;
1802 
1803  SCIPdebugMsg(scip, "detected expr %p to be convex -> can enforce expr <= auxvar\n", (void*)expr);
1804  }
1805  else
1806  {
1807  SCIP_CALL( SCIPhashmapRemoveAll(nlexpr2origexpr) );
1808  }
1809  }
1810 
1811  if( (*enforcing & SCIP_NLHDLR_METHOD_SEPAABOVE) == 0 && nlexpr == NULL ) /* if no separation above and not convex */
1812  {
1813  SCIP_CALL( constructExpr(scip, nlhdlrdata, &nlexpr, nlexpr2origexpr, &nleafs, expr,
1815  if( nlexpr != NULL )
1816  {
1817  assert(SCIPexprGetNChildren(nlexpr) > 0); /* should not be trivial */
1818 
1819  *participating |= SCIP_NLHDLR_METHOD_SEPAABOVE;
1820 
1821  SCIPdebugMsg(scip, "detected expr %p to be concave -> can enforce expr >= auxvar\n", (void*)expr);
1822  }
1823  }
1824 
1825  /* everything we participate in we also enforce */
1826  *enforcing |= *participating;
1827 
1828  assert(*participating || nlexpr == NULL);
1829  if( !*participating )
1830  {
1831  SCIPhashmapFree(&nlexpr2origexpr);
1832  return SCIP_OKAY;
1833  }
1834 
1835  /* create the expression data of the nonlinear handler
1836  * notify conshdlr about expr for which we will require auxiliary variables
1837  */
1838  SCIP_CALL( createNlhdlrExprData(scip, nlhdlrdata, nlhdlrexprdata, expr, nlexpr, nlexpr2origexpr, nleafs, *participating) );
1839 
1840  return SCIP_OKAY;
1841 }
1842 
1843 /** auxiliary evaluation callback */
1844 static
1845 SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalAuxConvexConcave)
1846 { /*lint --e{715}*/
1847  assert(nlhdlrexprdata != NULL);
1848  assert(nlhdlrexprdata->nlexpr != NULL);
1849  assert(auxvalue != NULL);
1850 
1851  SCIP_CALL( SCIPevalExpr(scip, nlhdlrexprdata->nlexpr, sol, 0L) );
1852  *auxvalue = SCIPexprGetEvalValue(nlhdlrexprdata->nlexpr);
1853 
1854  return SCIP_OKAY;
1855 }
1856 
1857 /** init sepa callback that initializes LP */
1858 static
1859 SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaConvex)
1860 { /*lint --e{715}*/
1861  SCIP_EXPR* nlexpr;
1862  SCIP_EXPRCURV curvature;
1863  SCIP_Bool success;
1864  SCIP_ROWPREP* rowprep = NULL;
1865  SCIP_ROW* row;
1866  SCIP_Real lb;
1867  SCIP_Real ub;
1868  SCIP_Real lambda;
1869  SCIP_SOL* sol;
1870  int k;
1871 
1872  assert(scip != NULL);
1873  assert(expr != NULL);
1874  assert(nlhdlrexprdata != NULL);
1875 
1876  /* setup nlhdlrexprdata->leafexprs */
1877  SCIP_CALL( collectLeafs(scip, nlhdlrexprdata) );
1878 
1879  nlexpr = nlhdlrexprdata->nlexpr;
1880  assert(nlexpr != NULL);
1881  assert(SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)nlexpr) == expr);
1882 
1883  curvature = SCIPexprGetCurvature(nlexpr);
1884  assert(curvature == SCIP_EXPRCURV_CONVEX || curvature == SCIP_EXPRCURV_CONCAVE);
1885 
1886  /* we can only be estimating on the convex side */
1887  if( curvature == SCIP_EXPRCURV_CONVEX )
1888  overestimate = FALSE;
1889  else if( curvature == SCIP_EXPRCURV_CONCAVE )
1890  underestimate = FALSE;
1891  if( !overestimate && !underestimate )
1892  return SCIP_OKAY;
1893 
1894  /* linearizes at 5 different points obtained as convex combination of the lower and upper bound of the variables
1895  * present in the convex expression; whether more weight is given to the lower or upper bound of a variable depends
1896  * on whether the fixing of the variable to that value is better for the objective function
1897  */
1898  SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
1899 
1900  *infeasible = FALSE;
1901 
1902  for( k = 0; k < 5; ++k )
1903  {
1904  int i;
1905  lambda = 0.1 * (k+1); /* lambda = 0.1, 0.2, 0.3, 0.4, 0.5 */
1906 
1907  for( i = 0; i < nlhdlrexprdata->nleafs; ++i )
1908  {
1909  SCIP_VAR* var;
1910 
1911  var = SCIPgetVarExprVar(nlhdlrexprdata->leafexprs[i]);
1912 
1913  lb = SCIPvarGetLbGlobal(var);
1914  ub = SCIPvarGetUbGlobal(var);
1915 
1916  /* make sure the absolute values of bounds are not too large */
1917  if( ub > -INITLPMAXVARVAL )
1918  lb = MAX(lb, -INITLPMAXVARVAL);
1919  if( lb < INITLPMAXVARVAL )
1920  ub = MIN(ub, INITLPMAXVARVAL);
1921 
1922  /* in the case when ub < -maxabsbnd or lb > maxabsbnd, we still want to at least make bounds finite */
1923  if( SCIPisInfinity(scip, -lb) )
1924  lb = MIN(-10.0, ub - 0.1*REALABS(ub));
1925  if( SCIPisInfinity(scip, ub) )
1926  ub = MAX( 10.0, lb + 0.1*REALABS(lb));
1927 
1929  SCIP_CALL( SCIPsetSolVal(scip, sol, var, lambda * ub + (1.0 - lambda) * lb) );
1930  else
1931  SCIP_CALL( SCIPsetSolVal(scip, sol, var, lambda * lb + (1.0 - lambda) * ub) );
1932  }
1933 
1935  SCIP_CALL( estimateGradient(scip, nlhdlrexprdata, sol, 0.0, rowprep, &success) );
1936  if( !success )
1937  {
1938  SCIPdebugMsg(scip, "failed to linearize for k = %d\n", k);
1939  SCIPfreeRowprep(scip, &rowprep);
1940  continue;
1941  }
1942 
1943  /* add auxiliary variable */
1944  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(expr), -1.0) );
1945 
1946  /* straighten out numerics */
1947  SCIP_CALL( SCIPcleanupRowprep2(scip, rowprep, NULL, SCIPgetHugeValue(scip), &success) );
1948  if( !success )
1949  {
1950  SCIPdebugMsg(scip, "failed to cleanup rowprep numerics for k = %d\n", k);
1951  SCIPfreeRowprep(scip, &rowprep);
1952  continue;
1953  }
1954 
1955  (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_gradient%p_initsepa_%d",
1956  overestimate ? "over" : "under", (void*)expr, k);
1957  SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) );
1958  SCIPfreeRowprep(scip, &rowprep);
1959 
1960 #ifdef SCIP_DEBUG
1961  SCIPinfoMessage(scip, NULL, "initsepa computed row: ");
1962  SCIPprintRow(scip, row, NULL);
1963 #endif
1964 
1965  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
1966  SCIP_CALL( SCIPreleaseRow(scip, &row) );
1967 
1968  if( *infeasible )
1969  break;
1970  }
1971 
1972  SCIP_CALL( SCIPfreeSol(scip, &sol) );
1973 
1974  return SCIP_OKAY;
1975 }
1976 
1977 /** estimator callback */
1978 static
1979 SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateConvex)
1980 { /*lint --e{715}*/
1981  SCIP_ROWPREP* rowprep;
1982 
1983  assert(scip != NULL);
1984  assert(expr != NULL);
1985  assert(nlhdlrexprdata != NULL);
1986  assert(nlhdlrexprdata->nlexpr != NULL);
1987  assert(rowpreps != NULL);
1988  assert(success != NULL);
1989 
1990  assert(SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)nlhdlrexprdata->nlexpr) == expr);
1991 
1992  /* we must be called only for the side that we indicated to participate in during DETECT */
1993  assert(SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONVEX
1994  || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONCAVE);
1995  assert(!overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONCAVE);
1996  assert( overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONVEX);
1997 
1998  *success = FALSE;
1999  *addedbranchscores = FALSE;
2000 
2001  /* we can skip eval as nlhdlrEvalAux should have been called for same solution before */
2002  /* SCIP_CALL( nlhdlrExprEval(scip, nlexpr, sol) ); */
2003  assert(auxvalue == SCIPexprGetEvalValue(nlhdlrexprdata->nlexpr)); /* given value (originally from
2004  nlhdlrEvalAuxConvexConcave) should coincide with the one stored in nlexpr */
2005 
2007 
2008  if( nlhdlrexprdata->nleafs == 1 && SCIPexprIsIntegral(nlhdlrexprdata->leafexprs[0]) )
2009  {
2010  SCIP_CALL( estimateConvexSecant(scip, nlhdlr, nlhdlrexprdata, sol, rowprep, success) );
2011 
2012  (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_convexsecant%p_%s%" SCIP_LONGINT_FORMAT,
2013  overestimate ? "over" : "under",
2014  (void*)expr,
2015  sol != NULL ? "sol" : "lp",
2016  sol != NULL ? (SCIP_Longint) SCIPsolGetIndex(sol) : SCIPgetNLPs(scip));
2017  }
2018 
2019  /* if secant method was not used or failed, then try with gradient */
2020  if( !*success )
2021  {
2022  SCIP_CALL( estimateGradient(scip, nlhdlrexprdata, sol, auxvalue, rowprep, success) );
2023 
2024  (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_convexgradient%p_%s%" SCIP_LONGINT_FORMAT,
2025  overestimate ? "over" : "under",
2026  (void*)expr,
2027  sol != NULL ? "sol" : "lp",
2028  sol != NULL ? (SCIP_Longint) SCIPsolGetIndex(sol) : SCIPgetNLPs(scip));
2029  }
2030 
2031  if( *success )
2032  {
2033  SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, 0, rowprep) );
2034  }
2035  else
2036  {
2037  SCIPfreeRowprep(scip, &rowprep);
2038  }
2039 
2040  return SCIP_OKAY;
2041 }
2042 
2043 /** include nlhdlr in another scip instance */
2044 static
2045 SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrConvex)
2046 { /*lint --e{715}*/
2047  assert(targetscip != NULL);
2048  assert(sourcenlhdlr != NULL);
2049  assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), CONVEX_NLHDLR_NAME) == 0);
2050 
2051  SCIP_CALL( SCIPincludeNlhdlrConvex(targetscip) );
2052 
2053  return SCIP_OKAY;
2054 }
2055 
2056 /** includes convex nonlinear handler in nonlinear constraint handler */
2058  SCIP* scip /**< SCIP data structure */
2059  )
2060 {
2061  SCIP_NLHDLR* nlhdlr;
2062  SCIP_NLHDLRDATA* nlhdlrdata;
2063 
2064  assert(scip != NULL);
2065 
2066  SCIP_CALL( SCIPallocBlockMemory(scip, &nlhdlrdata) );
2067  nlhdlrdata->isnlhdlrconvex = TRUE;
2068  nlhdlrdata->evalsol = NULL;
2069 
2071  CONVEX_NLHDLR_DETECTPRIORITY, CONVEX_NLHDLR_ENFOPRIORITY, nlhdlrDetectConvex, nlhdlrEvalAuxConvexConcave, nlhdlrdata) );
2072  assert(nlhdlr != NULL);
2073 
2074  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONVEX_NLHDLR_NAME "/detectsum",
2075  "whether to run convexity detection when the root of an expression is a non-quadratic sum",
2076  &nlhdlrdata->detectsum, FALSE, DEFAULT_DETECTSUM, NULL, NULL) );
2077 
2078  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONVEX_NLHDLR_NAME "/extendedform",
2079  "whether to create extended formulations instead of looking for maximal convex expressions",
2080  &nlhdlrdata->extendedform, FALSE, DEFAULT_EXTENDEDFORM, NULL, NULL) );
2081 
2082  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONVEX_NLHDLR_NAME "/cvxquadratic",
2083  "whether to use convexity check on quadratics",
2084  &nlhdlrdata->cvxquadratic, TRUE, DEFAULT_CVXQUADRATIC_CONVEX, NULL, NULL) );
2085 
2086  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONVEX_NLHDLR_NAME "/cvxsignomial",
2087  "whether to use convexity check on signomials",
2088  &nlhdlrdata->cvxsignomial, TRUE, DEFAULT_CVXSIGNOMIAL, NULL, NULL) );
2089 
2090  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONVEX_NLHDLR_NAME "/cvxprodcomp",
2091  "whether to use convexity check on product composition f(h)*h",
2092  &nlhdlrdata->cvxprodcomp, TRUE, DEFAULT_CVXPRODCOMP, NULL, NULL) );
2093 
2094  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONVEX_NLHDLR_NAME "/handletrivial",
2095  "whether to also handle trivial convex expressions",
2096  &nlhdlrdata->handletrivial, TRUE, DEFAULT_HANDLETRIVIAL, NULL, NULL) );
2097 
2098  SCIPnlhdlrSetFreeHdlrData(nlhdlr, nlhdlrfreeHdlrDataConvexConcave);
2099  SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrConvex);
2100  SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrfreeExprDataConvexConcave);
2101  SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaConvex, NULL, nlhdlrEstimateConvex, NULL);
2102  SCIPnlhdlrSetInitExit(nlhdlr, NULL, nlhdlrExitConvex);
2103 
2104  return SCIP_OKAY;
2105 }
2106 
2107 /*
2108  * Callback methods of concave nonlinear handler
2109  */
2110 
2111 /** deinitialization of problem-specific data */
2112 static
2113 SCIP_DECL_NLHDLREXIT(nlhdlrExitConcave)
2114 {
2115  SCIP_NLHDLRDATA* nlhdlrdata;
2116 
2117  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
2118  assert(nlhdlrdata != NULL);
2119 
2120  if( nlhdlrdata->evalsol != NULL )
2121  {
2122  SCIP_CALL( SCIPfreeSol(scip, &nlhdlrdata->evalsol) );
2123  }
2124 
2125  return SCIP_OKAY;
2126 }
2127 
2128 /** checks whether expression (or -expression) is concave, possibly after introducing auxiliary variables */
2129 static
2130 SCIP_DECL_NLHDLRDETECT(nlhdlrDetectConcave)
2131 { /*lint --e{715}*/
2132  SCIP_NLHDLRDATA* nlhdlrdata;
2133  SCIP_EXPR* nlexpr = NULL;
2134  SCIP_HASHMAP* nlexpr2origexpr;
2135  int nleafs = 0;
2136 
2137  assert(scip != NULL);
2138  assert(nlhdlr != NULL);
2139  assert(expr != NULL);
2140  assert(enforcing != NULL);
2141  assert(participating != NULL);
2142  assert(nlhdlrexprdata != NULL);
2143 
2144  /* we currently do not participate if only activity computation is required */
2145  if( (*enforcing & SCIP_NLHDLR_METHOD_SEPABOTH) == SCIP_NLHDLR_METHOD_SEPABOTH )
2146  return SCIP_OKAY;
2147 
2148  /* ignore pure constants and variables */
2149  if( SCIPexprGetNChildren(expr) == 0 )
2150  return SCIP_OKAY;
2151 
2152  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
2153  assert(nlhdlrdata != NULL);
2154  assert(!nlhdlrdata->isnlhdlrconvex);
2155 
2156  SCIPdebugMsg(scip, "nlhdlr_concave detect for expr %p\n", (void*)expr);
2157 
2158  /* initialize mapping from copied expression to original one
2159  * 20 is not a bad estimate for the size of concave subexpressions that we can usually discover
2160  * when expressions will be allowed to store "user"data, we could get rid of this hashmap (TODO)
2161  */
2162  SCIP_CALL( SCIPhashmapCreate(&nlexpr2origexpr, SCIPblkmem(scip), 20) );
2163 
2164  if( (*enforcing & SCIP_NLHDLR_METHOD_SEPABELOW) == 0 ) /* if no separation below yet */
2165  {
2166  SCIP_CALL( constructExpr(scip, nlhdlrdata, &nlexpr, nlexpr2origexpr, &nleafs, expr,
2168 
2169  if( nlexpr != NULL && nleafs > SCIP_MAXVERTEXPOLYDIM )
2170  {
2171  SCIPdebugMsg(scip, "Too many variables (%d) in constructed expression. Will not be able to estimate. Rejecting.\n", nleafs);
2172  SCIP_CALL( SCIPreleaseExpr(scip, &nlexpr) );
2173  }
2174 
2175  if( nlexpr != NULL )
2176  {
2177  assert(SCIPexprGetNChildren(nlexpr) > 0); /* should not be trivial */
2178 
2179  *participating |= SCIP_NLHDLR_METHOD_SEPABELOW;
2180 
2181  SCIPdebugMsg(scip, "detected expr %p to be concave -> can enforce expr <= auxvar\n", (void*)expr);
2182  }
2183  else
2184  {
2185  SCIP_CALL( SCIPhashmapRemoveAll(nlexpr2origexpr) );
2186  }
2187  }
2188 
2189  if( (*enforcing & SCIP_NLHDLR_METHOD_SEPAABOVE) == 0 && nlexpr == NULL ) /* if no separation above and not concave */
2190  {
2191  SCIP_CALL( constructExpr(scip, nlhdlrdata, &nlexpr, nlexpr2origexpr, &nleafs, expr,
2193 
2194  if( nlexpr != NULL && nleafs > SCIP_MAXVERTEXPOLYDIM )
2195  {
2196  SCIPdebugMsg(scip, "Too many variables (%d) in constructed expression. Will not be able to estimate. Rejecting.\n", nleafs);
2197  SCIP_CALL( SCIPreleaseExpr(scip, &nlexpr) );
2198  }
2199 
2200  if( nlexpr != NULL )
2201  {
2202  assert(SCIPexprGetNChildren(nlexpr) > 0); /* should not be trivial */
2203 
2204  *participating |= SCIP_NLHDLR_METHOD_SEPAABOVE;
2205 
2206  SCIPdebugMsg(scip, "detected expr %p to be convex -> can enforce expr >= auxvar\n", (void*)expr);
2207  }
2208  }
2209 
2210  /* everything we participate in we also enforce (at the moment) */
2211  *enforcing |= *participating;
2212 
2213  assert(*participating || nlexpr == NULL);
2214  if( !*participating )
2215  {
2216  SCIPhashmapFree(&nlexpr2origexpr);
2217  return SCIP_OKAY;
2218  }
2219 
2220  /* create the expression data of the nonlinear handler
2221  * notify conshdlr about expr for which we will require auxiliary variables and use activity
2222  */
2223  SCIP_CALL( createNlhdlrExprData(scip, nlhdlrdata, nlhdlrexprdata, expr, nlexpr, nlexpr2origexpr, nleafs, *participating) );
2224 
2225  return SCIP_OKAY;
2226 }
2227 
2228 /** init sepa callback that initializes LP */
2229 static
2230 SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaConcave)
2231 {
2232  SCIP_EXPR* nlexpr;
2233  SCIP_EXPRCURV curvature;
2234  SCIP_Bool success;
2235  SCIP_ROWPREP* rowprep = NULL;
2236  SCIP_ROW* row;
2237 
2238  assert(scip != NULL);
2239  assert(expr != NULL);
2240  assert(nlhdlrexprdata != NULL);
2241 
2242  nlexpr = nlhdlrexprdata->nlexpr;
2243  assert(nlexpr != NULL);
2244  assert(SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)nlexpr) == expr);
2245 
2246  /* setup nlhdlrexprdata->leafexprs */
2247  SCIP_CALL( collectLeafs(scip, nlhdlrexprdata) );
2248 
2249  curvature = SCIPexprGetCurvature(nlexpr);
2250  assert(curvature == SCIP_EXPRCURV_CONVEX || curvature == SCIP_EXPRCURV_CONCAVE);
2251  /* we can only be estimating on non-convex side */
2252  if( curvature == SCIP_EXPRCURV_CONCAVE )
2253  overestimate = FALSE;
2254  else if( curvature == SCIP_EXPRCURV_CONVEX )
2255  underestimate = FALSE;
2256  if( !overestimate && !underestimate )
2257  return SCIP_OKAY;
2258 
2259  /* compute estimator and store in rowprep */
2261  SCIP_CALL( estimateVertexPolyhedral(scip, conshdlr, nlhdlr, nlhdlrexprdata, NULL, TRUE, overestimate,
2262  overestimate ? SCIPinfinity(scip) : -SCIPinfinity(scip), rowprep, &success) );
2263  if( !success )
2264  {
2265  SCIPdebugMsg(scip, "failed to compute facet of convex hull\n");
2266  goto TERMINATE;
2267  }
2268 
2269  /* add auxiliary variable */
2270  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, SCIPgetExprAuxVarNonlinear(expr), -1.0) );
2271 
2272  /* straighten out numerics */
2273  SCIP_CALL( SCIPcleanupRowprep2(scip, rowprep, NULL, SCIPgetHugeValue(scip), &success) );
2274  if( !success )
2275  {
2276  SCIPdebugMsg(scip, "failed to cleanup rowprep numerics\n");
2277  goto TERMINATE;
2278  }
2279 
2280  (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_concave%p_initsepa",
2281  overestimate ? "over" : "under", (void*)expr);
2282  SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) );
2283 
2284 #ifdef SCIP_DEBUG
2285  SCIPinfoMessage(scip, NULL, "initsepa computed row: ");
2286  SCIPprintRow(scip, row, NULL);
2287 #endif
2288 
2289  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
2290  SCIP_CALL( SCIPreleaseRow(scip, &row) );
2291 
2292  TERMINATE:
2293  if( rowprep != NULL )
2294  SCIPfreeRowprep(scip, &rowprep);
2295 
2296  return SCIP_OKAY;
2297 }
2298 
2299 /** estimator callback */
2300 static
2301 SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateConcave)
2302 { /*lint --e{715}*/
2303  SCIP_ROWPREP* rowprep;
2304 
2305  assert(scip != NULL);
2306  assert(expr != NULL);
2307  assert(nlhdlrexprdata != NULL);
2308  assert(nlhdlrexprdata->nlexpr != NULL);
2309  assert(rowpreps != NULL);
2310  assert(success != NULL);
2311 
2312  assert(SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, (void*)nlhdlrexprdata->nlexpr) == expr);
2313 
2314  /* we must be called only for the side that we indicated to participate in during DETECT */
2315  assert(SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONVEX
2316  || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONCAVE);
2317  assert(!overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONVEX);
2318  assert( overestimate || SCIPexprGetCurvature(nlhdlrexprdata->nlexpr) == SCIP_EXPRCURV_CONCAVE);
2319 
2320  *success = FALSE;
2321  *addedbranchscores = FALSE;
2322 
2324 
2325  SCIP_CALL( estimateVertexPolyhedral(scip, conshdlr, nlhdlr, nlhdlrexprdata, sol, FALSE, overestimate, targetvalue, rowprep, success) );
2326 
2327  if( *success )
2328  {
2329  SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, 0, rowprep) );
2330 
2331  (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_concave%p_%s%" SCIP_LONGINT_FORMAT,
2332  overestimate ? "over" : "under",
2333  (void*)expr,
2334  sol != NULL ? "sol" : "lp",
2335  sol != NULL ? (SCIP_Longint) SCIPsolGetIndex(sol) : SCIPgetNLPs(scip));
2336  }
2337  else
2338  {
2339  SCIPfreeRowprep(scip, &rowprep);
2340  }
2341 
2342  if( addbranchscores )
2343  {
2344  SCIP_Real violation;
2345 
2346  /* check how much is the violation on the side that we estimate */
2347  if( auxvalue == SCIP_INVALID )
2348  {
2349  /* if cannot evaluate, then always branch */
2350  violation = SCIPinfinity(scip);
2351  }
2352  else
2353  {
2354  SCIP_Real auxval;
2355 
2356  /* get value of auxiliary variable of this expression */
2357  assert(SCIPgetExprAuxVarNonlinear(expr) != NULL);
2358  auxval = SCIPgetSolVal(scip, sol, SCIPgetExprAuxVarNonlinear(expr));
2359 
2360  /* compute the violation
2361  * if we underestimate, then we enforce expr <= auxval, so violation is (positive part of) auxvalue - auxval
2362  * if we overestimate, then we enforce expr >= auxval, so violation is (positive part of) auxval - auxvalue
2363  */
2364  if( !overestimate )
2365  violation = MAX(0.0, auxvalue - auxval);
2366  else
2367  violation = MAX(0.0, auxval - auxvalue);
2368  }
2369  assert(violation >= 0.0);
2370 
2371  /* add violation as branching-score to expressions; the core will take care distributing this onto variables */
2372  if( nlhdlrexprdata->nleafs == 1 )
2373  {
2374  SCIP_EXPR* e;
2375  e = (SCIP_EXPR*)SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, nlhdlrexprdata->leafexprs[0]);
2376  SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, &e, 1, violation, sol, addedbranchscores) );
2377  }
2378  else
2379  {
2380  SCIP_EXPR** exprs;
2381  int c;
2382 
2383  /* map leaf expressions back to original expressions
2384  * TODO do this once at end of detect and store in nlhdlrexprdata
2385  */
2386  SCIP_CALL( SCIPallocBufferArray(scip, &exprs, nlhdlrexprdata->nleafs) );
2387  for( c = 0; c < nlhdlrexprdata->nleafs; ++c )
2388  exprs[c] = (SCIP_EXPR*)SCIPhashmapGetImage(nlhdlrexprdata->nlexpr2origexpr, nlhdlrexprdata->leafexprs[c]);
2389 
2390  SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, exprs, nlhdlrexprdata->nleafs, violation, sol, addedbranchscores) );
2391 
2392  SCIPfreeBufferArray(scip, &exprs);
2393  }
2394  }
2395 
2396  return SCIP_OKAY;
2397 }
2398 
2399 /** includes nonlinear handler in another scip instance */
2400 static
2401 SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrConcave)
2402 { /*lint --e{715}*/
2403  assert(targetscip != NULL);
2404  assert(sourcenlhdlr != NULL);
2405  assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), CONCAVE_NLHDLR_NAME) == 0);
2406 
2407  SCIP_CALL( SCIPincludeNlhdlrConcave(targetscip) );
2408 
2409  return SCIP_OKAY;
2410 }
2411 
2412 /** includes concave nonlinear handler in nonlinear constraint handler */
2413 SCIP_EXPORT
2415  SCIP* scip /**< SCIP data structure */
2416  )
2417 {
2418  SCIP_NLHDLR* nlhdlr;
2419  SCIP_NLHDLRDATA* nlhdlrdata;
2420 
2421  assert(scip != NULL);
2422 
2423  SCIP_CALL( SCIPallocBlockMemory(scip, &nlhdlrdata) );
2424  nlhdlrdata->isnlhdlrconvex = FALSE;
2425  nlhdlrdata->evalsol = NULL;
2426 
2428  CONCAVE_NLHDLR_DETECTPRIORITY, CONCAVE_NLHDLR_ENFOPRIORITY, nlhdlrDetectConcave, nlhdlrEvalAuxConvexConcave, nlhdlrdata) );
2429  assert(nlhdlr != NULL);
2430 
2431  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONCAVE_NLHDLR_NAME "/detectsum",
2432  "whether to run convexity detection when the root of an expression is a sum",
2433  &nlhdlrdata->detectsum, FALSE, DEFAULT_DETECTSUM, NULL, NULL) );
2434 
2435  /* "extended" formulations of a concave expressions can give worse estimators */
2436  nlhdlrdata->extendedform = FALSE;
2437 
2438  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONCAVE_NLHDLR_NAME "/cvxquadratic",
2439  "whether to use convexity check on quadratics",
2440  &nlhdlrdata->cvxquadratic, TRUE, DEFAULT_CVXQUADRATIC_CONCAVE, NULL, NULL) );
2441 
2442  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONCAVE_NLHDLR_NAME "/cvxsignomial",
2443  "whether to use convexity check on signomials",
2444  &nlhdlrdata->cvxsignomial, TRUE, DEFAULT_CVXSIGNOMIAL, NULL, NULL) );
2445 
2446  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONCAVE_NLHDLR_NAME "/cvxprodcomp",
2447  "whether to use convexity check on product composition f(h)*h",
2448  &nlhdlrdata->cvxprodcomp, TRUE, DEFAULT_CVXPRODCOMP, NULL, NULL) );
2449 
2450  SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" CONCAVE_NLHDLR_NAME "/handletrivial",
2451  "whether to also handle trivial convex expressions",
2452  &nlhdlrdata->handletrivial, TRUE, DEFAULT_HANDLETRIVIAL, NULL, NULL) );
2453 
2454  SCIPnlhdlrSetFreeHdlrData(nlhdlr, nlhdlrfreeHdlrDataConvexConcave);
2455  SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrConcave);
2456  SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrfreeExprDataConvexConcave);
2457  SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaConcave, NULL, nlhdlrEstimateConcave, NULL);
2458  SCIPnlhdlrSetInitExit(nlhdlr, NULL, nlhdlrExitConcave);
2459 
2460  return SCIP_OKAY;
2461 }
2462 
2463 /** checks whether a given expression is convex or concave w.r.t. the original variables
2464  *
2465  * This function uses the methods that are used in the detection algorithm of the convex nonlinear handler.
2466  */
2468  SCIP* scip, /**< SCIP data structure */
2469  SCIP_EXPR* expr, /**< expression */
2470  SCIP_EXPRCURV curv, /**< curvature to check for */
2471  SCIP_Bool* success, /**< buffer to store whether expression has curvature curv (w.r.t. original variables) */
2472  SCIP_HASHMAP* assumevarfixed /**< hashmap containing variables that should be assumed to be fixed, or NULL */
2473  )
2474 {
2475  SCIP_NLHDLRDATA nlhdlrdata;
2476  SCIP_EXPR* rootnlexpr;
2477  SCIP_HASHMAP* nlexpr2origexpr;
2478  int nleafs;
2479 
2480  assert(expr != NULL);
2481  assert(curv != SCIP_EXPRCURV_UNKNOWN);
2482  assert(success != NULL);
2483 
2484  /* create temporary hashmap */
2485  SCIP_CALL( SCIPhashmapCreate(&nlexpr2origexpr, SCIPblkmem(scip), 20) );
2486 
2487  /* prepare nonlinear handler data */
2488  nlhdlrdata.isnlhdlrconvex = TRUE;
2489  nlhdlrdata.evalsol = NULL;
2490  nlhdlrdata.detectsum = TRUE;
2491  nlhdlrdata.extendedform = FALSE;
2492  nlhdlrdata.cvxquadratic = TRUE;
2493  nlhdlrdata.cvxsignomial = TRUE;
2494  nlhdlrdata.cvxprodcomp = TRUE;
2495  nlhdlrdata.handletrivial = TRUE;
2496 
2497  SCIP_CALL( constructExpr(scip, &nlhdlrdata, &rootnlexpr, nlexpr2origexpr, &nleafs, expr, curv, assumevarfixed, FALSE, success) );
2498 
2499  /* free created expression */
2500  if( rootnlexpr != NULL )
2501  {
2502  SCIP_CALL( SCIPreleaseExpr(scip, &rootnlexpr) );
2503  }
2504 
2505  /* free hashmap */
2506  SCIPhashmapFree(&nlexpr2origexpr);
2507 
2508  return SCIP_OKAY;
2509 }
static SCIP_RETCODE estimateConvexSecant(SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
void SCIPexprGetQuadraticData(SCIP_EXPR *expr, SCIP_Real *constant, int *nlinexprs, SCIP_EXPR ***linexprs, SCIP_Real **lincoefs, int *nquadexprs, int *nbilinexprs, SCIP_Real **eigenvalues, SCIP_Real **eigenvectors)
Definition: expr.c:4067
static SCIP_Bool exprstackIsEmpty(EXPRSTACK *exprstack)
#define DECL_CURVCHECK(x)
const char * SCIPexprcurvGetName(SCIP_EXPRCURV curv)
Definition: exprcurv.c:585
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:500
SCIP_RETCODE SCIPduplicateExprShallow(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **copyexpr, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: scip_expr.c:1291
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
SCIP_MONOTONE
Definition: type_expr.h:66
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1476
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPquadprecSumQD(r, a, b)
Definition: dbldblarith.h:62
SCIP_RETCODE SCIPcomputeExprQuadraticCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV *curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool storeeigeninfo)
Definition: scip_expr.c:2551
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1708
#define CONCAVE_NLHDLR_NAME
Definition: nlhdlr_convex.c:51
#define SCIP_NLHDLR_METHOD_SEPABELOW
Definition: type_nlhdlr.h:51
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3808
#define DEFAULT_EXTENDEDFORM
Definition: nlhdlr_convex.c:57
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17923
#define SCIP_MAXSTRLEN
Definition: def.h:302
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEEXPRDATA((*freeexprdata)))
Definition: nlhdlr.c:94
#define DEFAULT_CVXPRODCOMP
Definition: nlhdlr_convex.c:61
SCIP_NLHDLREXPRDATA * nlhdlrexprdata
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:534
SCIP_RETCODE SCIPcleanupRowprep2(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, SCIP_Real maxcoefbound, SCIP_Bool *success)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17979
SCIP_Real SCIPgetConstantExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1181
#define CONCAVE_NLHDLR_DESC
Definition: nlhdlr_convex.c:52
SCIP_EXPR * SCIPexpriterSkipDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:929
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
Definition: misc_rowprep.c:792
void * SCIPhashmapEntryGetOrigin(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3510
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
SCIP_Bool SCIPassumeConvexNonlinear(SCIP_CONSHDLR *conshdlr)
SCIP_RETCODE SCIPcheckExprQuadratic(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool *isquadratic)
Definition: scip_expr.c:2342
#define FALSE
Definition: def.h:96
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3024
void SCIPexprSetCurvature(SCIP_EXPR *expr, SCIP_EXPRCURV curvature)
Definition: expr.c:4016
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEHDLRDATA((*freehdlrdata)))
Definition: nlhdlr.c:83
SCIP_Bool SCIPexprhdlrHasBwdiff(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:584
#define CONVEX_NLHDLR_DESC
Definition: nlhdlr_convex.c:47
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:687
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10788
SCIP_Real SCIPgetExponentExprPow(SCIP_EXPR *expr)
Definition: expr_pow.c:3352
#define TRUE
Definition: def.h:95
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
Definition: misc.c:3709
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_EXPR ** stack
SCIP_RETCODE SCIPhashmapInsertInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3142
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
Definition: misc.c:3767
static SCIP_RETCODE estimateVertexPolyhedral(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_Bool usemidpoint, SCIP_Bool overestimate, SCIP_Real targetvalue, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition: expr.c:3964
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define CONVEX_NLHDLR_ENFOPRIORITY
Definition: nlhdlr_convex.c:49
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3211
SCIP_RETCODE SCIPincludeNlhdlrConvex(SCIP *scip)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcreateExprVar(SCIP *scip, SCIP_EXPR **expr, SCIP_VAR *var, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition: expr_var.c:390
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define QUAD_ASSIGN(a, constant)
Definition: dbldblarith.h:51
defines macros for basic operations in double-double arithmetic giving roughly twice the precision of...
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1399
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
variable expression handler
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
Definition: misc_rowprep.c:878
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:682
SCIP_VAR ** x
Definition: circlepacking.c:63
SCIP_RETCODE SCIPevalExprGradient(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1658
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalAuxConvexConcave)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1454
#define QUAD_TO_DBL(x)
Definition: dbldblarith.h:49
SCIP_RETCODE SCIPgetRowprepRowCons(SCIP *scip, SCIP_ROW **row, SCIP_ROWPREP *rowprep, SCIP_CONS *cons)
SCIP_RETCODE SCIPevalExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1625
int SCIPcompareExpr(SCIP *scip, SCIP_EXPR *expr1, SCIP_EXPR *expr2)
Definition: scip_expr.c:1725
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3373
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:647
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3818
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17933
SCIP_Real inf
Definition: intervalarith.h:55
static SCIP_RETCODE exprstackInit(SCIP *scip, EXPRSTACK *exprstack, int initsize)
#define CONVEX_NLHDLR_NAME
Definition: nlhdlr_convex.c:46
static SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateConvex)
SCIP_Real * SCIPgetCoefsExprSum(SCIP_EXPR *expr)
Definition: expr_sum.c:1166
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3882
SCIP_Real SCIPexprGetDerivative(SCIP_EXPR *expr)
Definition: expr.c:3908
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3491
#define CONVEX_NLHDLR_DETECTPRIORITY
Definition: nlhdlr_convex.c:48
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3499
SCIP_RETCODE SCIPcomputeFacetVertexPolyhedralNonlinear(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_Bool overestimate, SCIP_DECL_VERTEXPOLYFUN((*function)), void *fundata, SCIP_Real *xstar, SCIP_Real *box, int nallvars, SCIP_Real targetvalue, SCIP_Bool *success, SCIP_Real *facetcoefs, SCIP_Real *facetconstant)
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:150
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:416
static SCIP_RETCODE estimateGradient(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_SOL *sol, SCIP_Real auxvalue, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
Definition: misc.c:3740
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)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
public functions to work with algebraic expressions
#define QUAD(x)
Definition: dbldblarith.h:47
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1432
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17264
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3058
void SCIPexprGetQuadraticQuadTerm(SCIP_EXPR *quadexpr, int termidx, SCIP_EXPR **expr, SCIP_Real *lincoef, SCIP_Real *sqrcoef, int *nadjbilin, int **adjbilin, SCIP_EXPR **sqrexpr)
Definition: expr.c:4114
#define NULL
Definition: lpi_spx1.cpp:164
static SCIP_RETCODE collectLeafs(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
#define REALABS(x)
Definition: def.h:210
SCIP_RETCODE SCIPreplaceExprChild(SCIP *scip, SCIP_EXPR *expr, int childidx, SCIP_EXPR *newchild)
Definition: scip_expr.c:1238
SCIP_Longint SCIPexprGetDiffTag(SCIP_EXPR *expr)
Definition: expr.c:3951
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
#define SCIP_CALL(x)
Definition: def.h:394
int SCIPexpriterGetChildIdxDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:706
SCIP_VAR * h
Definition: circlepacking.c:68
SCIP_Real sup
Definition: intervalarith.h:56
static SCIP_Bool exprIsMultivarLinear(SCIP *scip, SCIP_EXPR *expr)
static SCIP_DECL_VERTEXPOLYFUN(nlhdlrExprEvalConcave)
SCIP_RETCODE SCIPhasExprCurvature(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPRCURV curv, SCIP_Bool *success, SCIP_HASHMAP *assumevarfixed)
#define CONCAVE_NLHDLR_ENFOPRIORITY
Definition: nlhdlr_convex.c:54
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_EXPRCURV SCIPexprGetCurvature(SCIP_EXPR *expr)
Definition: expr.c:4006
static SCIP_RETCODE nlhdlrExprGrowChildren(SCIP *scip, SCIP_HASHMAP *nlexpr2origexpr, SCIP_EXPR *nlhdlrexpr, SCIP_EXPRCURV *childrencurv)
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectConvex)
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2302
SCIP_Real SCIPgetCoefExprProduct(SCIP_EXPR *expr)
nonlinear handlers for convex and concave expressions, respectively
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
static SCIP_DECL_NLHDLREXIT(nlhdlrExitConvex)
#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
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrConvex)
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:751
SCIP_RETCODE SCIPhashmapRemoveAll(SCIP_HASHMAP *hashmap)
Definition: misc.c:3583
SCIP_EXPRCURV
Definition: type_expr.h:57
unsigned int SCIP_NLHDLR_METHOD
Definition: type_nlhdlr.h:57
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1407
#define DEFAULT_CVXQUADRATIC_CONCAVE
Definition: nlhdlr_convex.c:59
constraint handler for nonlinear constraints specified by algebraic expressions
static SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaConvex)
#define MAX(x, y)
Definition: tclique_def.h:92
SCIP_Bool SCIPexprcurvMonomialInv(SCIP_EXPRCURV monomialcurv, int nfactors, SCIP_Real *exponents, SCIP_INTERVAL *factorbounds, SCIP_EXPRCURV *factorcurv)
Definition: exprcurv.c:456
SCIP_RETCODE SCIPappendExprChild(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR *child)
Definition: scip_expr.c:1220
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:985
SCIP_Bool SCIPexprIsIntegral(SCIP_EXPR *expr)
Definition: expr.c:4027
SCIP_RETCODE SCIPcomputeExprIntegrality(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1990
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:857
SCIP_EXPR * SCIPexpriterGetChildExprDFS(SCIP_EXPRITER *iterator)
Definition: expriter.c:720
static SCIP_EXPR * exprstackPop(EXPRSTACK *exprstack)
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3831
SCIP_Bool SCIPisExprPower(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1465
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
absolute expression handler
static void exprstackFree(SCIP *scip, EXPRSTACK *exprstack)
#define DEFAULT_CVXQUADRATIC_CONVEX
Definition: nlhdlr_convex.c:58
#define CONCAVE_NLHDLR_DETECTPRIORITY
Definition: nlhdlr_convex.c:53
void SCIPexpriterSetStagesDFS(SCIP_EXPRITER *iterator, SCIP_EXPRITER_STAGE stopstages)
Definition: expriter.c:663
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2316
#define INITLPMAXVARVAL
Definition: nlhdlr_convex.c:64
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetHugeValue(SCIP *scip)
static const int NCURVCHECKS
SCIP_Bool SCIPisExprAbs(SCIP *scip, SCIP_EXPR *expr)
Definition: expr_abs.c:546
#define SCIP_MAXVERTEXPOLYDIM
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1421
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
Definition: misc.c:3750
SCIP_RETCODE SCIPhashmapSetImage(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3273
void SCIPnlhdlrSetInitExit(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINIT((*init)), SCIP_DECL_NLHDLREXIT((*exit_)))
Definition: nlhdlr.c:106
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:186
#define SCIP_INVALID
Definition: def.h:206
int SCIPhashmapEntryGetImageInt(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3530
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2209
SCIP_NLHDLRDATA * SCIPnlhdlrGetData(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:200
#define DEFAULT_HANDLETRIVIAL
Definition: nlhdlr_convex.c:62
#define SCIP_Longint
Definition: def.h:171
SCIP_BOUNDTYPE SCIPvarGetBestBoundType(SCIP_VAR *var)
Definition: var.c:18035
static SCIP_RETCODE nlhdlrExprCreate(SCIP *scip, SCIP_HASHMAP *nlexpr2origexpr, SCIP_EXPR **nlhdlrexpr, SCIP_EXPR *origexpr, SCIP_EXPRCURV curv)
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrfreeExprDataConvexConcave)
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
Definition: type_nlhdlr.h:413
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: misc_rowprep.c:561
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
Definition: type_nlhdlr.h:412
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
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
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define DEFAULT_DETECTSUM
Definition: nlhdlr_convex.c:56
SCIP_EXPRCURV SCIPexprcurvMultiply(SCIP_Real factor, SCIP_EXPRCURV curvature)
Definition: exprcurv.c:87
#define DEFAULT_CVXSIGNOMIAL
Definition: nlhdlr_convex.c:60
static SCIP_RETCODE exprstackPush(SCIP *scip, EXPRSTACK *exprstack, int nexprs, SCIP_EXPR **exprs)
#define SCIP_EXPRITER_VISITINGCHILD
Definition: type_expr.h:677
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3106
static SCIP_RETCODE createNlhdlrExprData(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_EXPR *expr, SCIP_EXPR *nlexpr, SCIP_HASHMAP *nlexpr2origexpr, int nleafs, SCIP_NLHDLR_METHOD participating)
static SCIP_RETCODE constructExpr(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_EXPR **rootnlexpr, SCIP_HASHMAP *nlexpr2origexpr, int *nleafs, SCIP_EXPR *rootexpr, SCIP_EXPRCURV curv, SCIP_HASHMAP *assumevarfixed, SCIP_Bool assumecurvature, SCIP_Bool *curvsuccess)
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:968
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
Definition: misc_rowprep.c:771
public functions of nonlinear handlers of nonlinear constraints
#define SCIP_CALL_ABORT(x)
Definition: def.h:373
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPincludeNlhdlrConcave(SCIP *scip)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPround(SCIP *scip, SCIP_Real val)
#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:1361
#define SCIP_NLHDLR_METHOD_SEPAABOVE
Definition: type_nlhdlr.h:52
static SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrfreeHdlrDataConvexConcave)
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2644
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
preparation of a linear inequality to become a SCIP_ROW
SCIP_RETCODE SCIPremoveExprChildren(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1257
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_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
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRCOPYHDLR((*copy)))
Definition: nlhdlr.c:72