Scippy

SCIP

Solving Constraint Integer Programs

nlhdlr_signomial.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file nlhdlr_signomial.c
26  * @ingroup DEFPLUGINS_NLHDLR
27  * @brief signomial nonlinear handler
28  * @author Liding Xu
29  */
30 
31 #ifdef SCIP_SIGCUT_DEBUG
32 #ifndef SCIP_SIG_DEBUG
33 #define SCIP_SIG_DEBUG
34 #endif
35 #endif
36 
37 #ifdef SCIP_SIG_DEBUG
38 #define SCIP_DEBUG
39 #endif
40 
41 #include "scip/nlhdlr_signomial.h"
42 #include "scip/cons_nonlinear.h"
43 #include "scip/pub_misc_rowprep.h"
44 #include "scip/pub_nlhdlr.h"
45 #include "scip/scip_expr.h"
46 #include "scip/expr_var.h"
47 #include "scip/expr_pow.h"
48 
49 /* fundamental nonlinear handler properties */
50 #define NLHDLR_NAME "signomial"
51 #define NLHDLR_DESC "handler for signomial expressions"
52 #define NLHDLR_DETECTPRIORITY 30
53 #define NLHDLR_ENFOPRIORITY 30
54 
55 /* handler specific parameters */
56 #define NLHDLR_MAXNUNDERVARS 14 /**< maximum number of variables when underestimating a concave power function (maximum: 14) */
57 #define NLHDLR_MINCUTSCALE 1e-5 /**< minimum scale factor when scaling a cut (minimum: 1e-6) */
58 
59 
60 /** nonlinear handler expression data
61  *
62  * A signomial expression admits the form \f$ cx^a = y \f$, where \f$ y \f$ is an auxiliary variable representing this
63  * expression and all \f$ x \f$ are positive.
64  *
65  * The natural formulation of the expression is defined as \f$ x^a = t = y/c \f$, where \f$ t \f$ is a
66  * non-existant slack variable denoting \f$ y/c \f$. The variables in \f$x\f$ with positive exponents form positive
67  * variables \f$ u \f$, and the associated exponents form positive exponents \f$ f \f$. The variables in \f$ x \f$ with
68  * negative exponents and \f$ t \f$ form negative variables \f$ v \f$, and the associated exponents form negative
69  * exponents \f$ g \f$. Let \f$ s = \max(|f|,|g|) \f$ be a normalization constant, where \f$ |\cdot| \f$ denotes the L1 norm. Apply a scaling step:
70  * Dividing the entries of \f$ f \f$ by \f$ s \f$, and dividing the entries of \f$ g \f$ by \f$ s \f$ as well. Then \f$ x^a = t \f$ has
71  * a reformulation \f$ u^f = v^g \f$, where \f$ u^f, v^g \f$ are two concave power functions.
72  */
73 struct SCIP_NlhdlrExprData
74 {
75  SCIP_Real coef; /**< coefficient \f$c\f$ */
76  SCIP_EXPR** factors; /**< expression factors representing \f$x\f$ */
77  int nfactors; /**< number of factors */
78  int nvars; /**< number of variables \f$(x,y)\f$ */
79  SCIP_Real* exponents; /**< exponents \f$e\f$ */
80  int nposvars; /**< number of positive variables \f$u\f$ */
81  int nnegvars; /**< number of negative variables \f$v\f$ */
82  SCIP_Bool* signs; /**< indicators for sign of variables after reformulation, TRUE for positive, FALSE for negative */
83  SCIP_Real* refexponents; /**< exponents of \f$(x,t)\f$ after reformulation (always positive) */
84  SCIP_Bool isstorecapture; /**< are all variables already got? */
85 
86  /* working parameters will be modified after getting all variables */
87  SCIP_VAR** vars; /**< variables \f$(x,y)\f$ */
88  SCIP_INTERVAL* intervals; /**< intervals storing lower and upper bounds of variables \f$(x,y)\f$ */
89  SCIP_Real* box; /**< the upper/lower bounds of variables, used in SCIPcomputeFacetVertexPolyhedralNonlinear() */
90  SCIP_Real* xstar; /**< the values of variables, used in SCIPcomputeFacetVertexPolyhedralNonlinear() */
91  SCIP_Real* facetcoefs; /**< the coefficients of variables, returned by SCIPcomputeFacetVertexPolyhedralNonlinear() */
92 };
93 
94 /** nonlinear handler data */
95 struct SCIP_NlhdlrData
96 {
97  /* parameters */
98  int maxnundervars; /**< maximum number of variables in underestimating a concave power function */
99  SCIP_Real mincutscale; /**< minimum scale factor when scaling a cut */
100 };
101 
102 /** data struct to be passed on to vertexpoly-evalfunction (see SCIPcomputeFacetVertexPolyhedralNonlinear) */
103 typedef struct
104 {
105  SCIP_NLHDLREXPRDATA* nlhdlrexprdata; /**< expression data */
106  SCIP_Bool sign; /**< the sign of variables in the reformulated constraint for vertexpoly-evalfunction */
107  int nsignvars; /**< the number of variables in the reformulated constraint for vertexpoly-evalfunction */
108  SCIP* scip; /**< SCIP data structure */
110 
111 
112 /*
113  * Local methods
114  */
115 
116 #ifdef SCIP_SIGCUT_DEBUG
117 
118 /** print the information on a signomial term */
119 static
121  SCIP* scip, /**< SCIP data structure */
122  SCIP_EXPR* expr, /**< expression */
123  SCIP_NLHDLREXPRDATA* nlhdlrexprdata /**< expression data */
124  )
125 {
126  assert(expr != NULL);
127 
128  /* print overall statistics and the expression */
129  SCIPdebugMsg(scip, " #all variables: %d, #positive exponent variables: %d, #negative exponent variables: %d, auxvar: %s \n expr: ",
130  nlhdlrexprdata->nvars, nlhdlrexprdata->nposvars, nlhdlrexprdata->nnegvars, SCIPvarGetName(SCIPgetExprAuxVarNonlinear(expr)) );
131  SCIPprintExpr(scip, expr, NULL);
132 
133  /* if variables are detected, we can print more information */
134  if( !nlhdlrexprdata->isstorecapture )
135  {
136  SCIPinfoMessage(scip, NULL, "\n");
137  return SCIP_OKAY;
138  }
139 
140  /* print the natural formulation of the expression */
141  SCIPinfoMessage(scip, NULL, ". natural formulation c x^a = y: %.2f", nlhdlrexprdata->coef);
142  for( int i = 0; i < nlhdlrexprdata->nvars - 1; i++ )
143  {
144  SCIPinfoMessage(scip, NULL, "%s^%.2f", SCIPvarGetName(nlhdlrexprdata->vars[i]), nlhdlrexprdata->exponents[i]);
145  }
146  SCIPinfoMessage(scip, NULL, " = %s", SCIPvarGetName(nlhdlrexprdata->vars[nlhdlrexprdata->nvars - 1]));
147 
148  /* print the reformulation of the expression */
149  SCIPinfoMessage(scip, NULL, ". Reformulation u^f = v^g: ");
150  if( nlhdlrexprdata->nposvars == 0 )
151  {
152  SCIPinfoMessage(scip, NULL, "1");
153  }
154  else
155  {
156  for( int i = 0; i < nlhdlrexprdata->nvars; i++ )
157  if( nlhdlrexprdata->signs[i] )
158  {
159  SCIPinfoMessage(scip, NULL, "%s^%.2f", SCIPvarGetName(nlhdlrexprdata->vars[i]), nlhdlrexprdata->refexponents[i]);
160  }
161  }
162  SCIPinfoMessage(scip, NULL, " = ");
163  if( nlhdlrexprdata->nnegvars == 0 )
164  {
165  SCIPinfoMessage(scip, NULL, "1");
166  }
167  else
168  {
169  for( int i = 0; i < nlhdlrexprdata->nvars; i++ )
170  {
171  if( !nlhdlrexprdata->signs[i] )
172  {
173  if( i == nlhdlrexprdata->nvars - 1 )
174  {
175  SCIPinfoMessage(scip, NULL, "(%s/%.2f)^%.2f", SCIPvarGetName(nlhdlrexprdata->vars[i]), nlhdlrexprdata->coef, nlhdlrexprdata->refexponents[i]);
176  }
177  else
178  {
179  SCIPinfoMessage(scip, NULL, "%s^%.2f", SCIPvarGetName(nlhdlrexprdata->vars[i]), nlhdlrexprdata->refexponents[i]);
180  }
181  }
182  }
183  }
184  SCIPinfoMessage(scip, NULL, "\n");
185 
186  return SCIP_OKAY;
187 }
188 
189 #endif
190 
191 /** free the memory of expression data */
192 static
194  SCIP* scip, /**< SCIP data structure */
195  SCIP_NLHDLREXPRDATA** nlhdlrexprdata, /**< expression data */
196  SCIP_Bool ispartial /**< free the partially allocated memory or the fully allocated memory? */
197  )
198 {
199  SCIPfreeBlockMemoryArrayNull(scip, &(*nlhdlrexprdata)->factors, (*nlhdlrexprdata)->nfactors);
200  SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->exponents, (*nlhdlrexprdata)->nfactors);
201  if( !ispartial )
202  {
203  int nvars = (*nlhdlrexprdata)->nvars;
204  SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->signs, nvars);
205  SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->refexponents, nvars);
206  SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->vars, nvars);
207  SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->intervals, nvars);
208  SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->box, 2*nvars); /*lint !e647*/
209  SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->xstar, nvars);
210  SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->facetcoefs, nvars);
211  }
212  SCIPfreeBlockMemory(scip, nlhdlrexprdata);
213  *nlhdlrexprdata = NULL;
214 }
215 
216 /** reforms a rowprep to a standard form for nonlinear handlers
217  *
218  * The input rowprep is of the form \f$ a_u u + a_v v + b \f$.
219  * If in the overestimate mode, then we relax \f$ t \le x^a \f$, i.e., \f$ 0 \le u^f - v^g \f$. This implies that \f$ t \f$ is in \f$ v = (v',t) \f$.
220  * Therefore, the valid inequality is \f$ 0 \le a_u u + a_v v + b \f$. As overestimate mode requires that \f$ t \f$ is in the left hand side,
221  * the coefficients of \f$ t \f$ must be made negative while keeping the sign of the inequality, we can show that \f$ a_t \le 0 \f$, so it suffices
222  * to divide the both sides by \f$ -a_t \ge 0\f$, which yields \f$ t \le (a_u u + a_v' v' + b) / -a_t \f$.
223  * A rowprep in standard form only contains an estimator of the expression and no auxvar.
224  * If in the underestimate mode, then we relax \f$ x^a \le t \f$, i.e., \f$ u^f - v^g \le 0 \f$. This implies that \f$ t \f$ is in \f$ v = (v',t) \f$.
225  * Therefore, the valid inequality is \f$ a_u u + a_v v + b \le 0 \f$. As overestimate mode requires that \f$ t \f$ is in the left hand side,
226  * the coefficients of \f$ t \f$ must be made negative while keeping the sign of the inequality, we can show that \f$ a_t \le 0 \f$, so it suffices
227  * to divide the both sides by \f$ -a_t \ge 0 \f$, which yields \f$ (a_u u + a_v' v' + b) / -a_t \le t \f$.
228  * A rowprep in standard form only contains an estimator of the expression and no auxvar.
229  */
230 static
232  SCIP* scip, /**< SCIP data structure */
233  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< expression data */
234  SCIP_ROWPREP* rowprep, /**< cut to be reformulated */
235  SCIP_Real mincutscale, /**< min scaling factor for the cut in rowprep */
236  SCIP_Bool* success /**< pointer to store whether the reformulating was successful */
237  )
238 {
239  int i;
240  int nvars;
241  SCIP_Real coefauxvar;
242  SCIP_Real scale;
243  SCIP_Real* coefs;
244  SCIP_VAR* auxvar;
245  SCIP_VAR** vars;
246 
247  assert(rowprep != NULL);
248  assert(nlhdlrexprdata != NULL);
249 
250  coefs = SCIProwprepGetCoefs(rowprep);
251  vars = SCIProwprepGetVars(rowprep);
252  nvars = SCIProwprepGetNVars(rowprep);
253 
254  /* find auxvar's cut coefficient and set it to zero */
255  auxvar = nlhdlrexprdata->vars[nlhdlrexprdata->nfactors];
256  coefauxvar = 1.0;
257  for( i = 0; i < nvars; i++ )
258  {
259  if( vars[i] == auxvar )
260  {
261  coefauxvar = coefs[i];
262  coefs[i] = 0.0;
263  break;
264  }
265  }
266 
267  if( SCIPisZero(scip, coefauxvar) || coefauxvar >= 0.0 )
268  {
269  *success = FALSE;
270  }
271  else
272  {
273  /* the reformation scales the cut so that coefficients and constant are divided by the absolute value of coefauxvar */
274  assert(coefauxvar < 0.0);
275  scale = -1.0 / coefauxvar;
276  for( i = 0; i < nvars; i++ )
277  {
278  if( vars[i] == auxvar )
279  continue;
280  coefs[i] *= scale;
281  }
282  /* set the side to scale*side by adding -side and adding scale*side */
283  SCIProwprepAddSide(rowprep, SCIProwprepGetSide(rowprep) * (-1.0 + scale));
284 
285  *success = SCIPisGT(scip, scale, mincutscale);
286  }
287 }
288 
289 /** store and capture variables associated with the expression and its subexpressions */
290 static
292  SCIP* scip, /**< SCIP data structure */
293  SCIP_EXPR* expr, /**< expression */
294  SCIP_NLHDLREXPRDATA* nlhdlrexprdata /**< expression data */
295  )
296 {
297  int c;
298 
299  assert(!nlhdlrexprdata->isstorecapture);
300 
301  /* get and capture variables \f$x\f$ */
302  for( c = 0; c < nlhdlrexprdata->nfactors; ++c )
303  {
304  nlhdlrexprdata->vars[c] = SCIPgetExprAuxVarNonlinear(nlhdlrexprdata->factors[c]);
305  assert(nlhdlrexprdata->vars[c] != NULL);
306 
307  SCIP_CALL( SCIPcaptureVar(scip, nlhdlrexprdata->vars[c]) );
308  }
309 
310  /* get and capture variable \f$y\f$ */
311  nlhdlrexprdata->vars[c] = SCIPgetExprAuxVarNonlinear(expr);
312  assert(nlhdlrexprdata->vars[c] != NULL);
313  SCIP_CALL( SCIPcaptureVar(scip, nlhdlrexprdata->vars[c]) );
314 
315  nlhdlrexprdata->isstorecapture = TRUE;
316 
317  return SCIP_OKAY;
318 }
319 
320 /** get bounds of variables x,t and check whether they are box constrained signomial variables */
321 static
323  SCIP* scip, /**< SCIP data structure */
324  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< expression data */
325  SCIP_Bool* isboxsignomial /**< buffer to store whether variables are box constrained signomial variables */
326  )
327 {
328  int c;
329  SCIP_Real powinf;
330  SCIP_Real powsup;
331  SCIP_Real productinf = 1;
332  SCIP_Real productsup = 1;
333 
334  assert(nlhdlrexprdata->isstorecapture);
335 
336  *isboxsignomial = FALSE;
337 
338  /* get bounds of x */
339  for( c = 0; c < nlhdlrexprdata->nfactors; c++ )
340  {
341  SCIP_Real inf = SCIPvarGetLbLocal(nlhdlrexprdata->vars[c]);
342  SCIP_Real sup = SCIPvarGetUbLocal(nlhdlrexprdata->vars[c]);
343 
344  /* if the bounds of the variable are not positive and finite, or (bounds equal) then the expression is not a signomial */
345  if( !SCIPisPositive(scip, inf) || !SCIPisPositive(scip, sup) || SCIPisInfinity(scip, sup) || SCIPisEQ(scip, inf, sup) )
346  return;
347 
348  nlhdlrexprdata->intervals[c].inf = inf;
349  nlhdlrexprdata->intervals[c].sup = MAX(sup, inf + 0.1);
350  powinf = pow(inf, nlhdlrexprdata->exponents[c]);
351  powsup = pow(sup, nlhdlrexprdata->exponents[c]);
352  productinf *= MIN(powinf, powsup);
353  productsup *= MAX(powinf, powsup);
354  }
355 
356  /* compute bounds of t by bounds of x */
357  nlhdlrexprdata->intervals[c].inf = productinf;
358  nlhdlrexprdata->intervals[c].sup = productsup;
359 
360  *isboxsignomial = TRUE;
361 }
362 
363 /** evaluate expression at solution w.r.t. auxiliary variables */
364 static
365 SCIP_DECL_VERTEXPOLYFUN(nlhdlrExprEvalPower)
366 {
367  int i;
368  int j;
369  SCIP_Real val;
370  VERTEXPOLYFUN_EVALDATA* evaldata;
371  SCIP_NLHDLREXPRDATA* nlhdlrexprdata;
372 
373  assert(args != NULL);
374 
375  evaldata = (VERTEXPOLYFUN_EVALDATA *)funcdata;
376 
377  assert(evaldata != NULL);
378  assert(nargs == evaldata->nsignvars);
379 
380  nlhdlrexprdata = evaldata->nlhdlrexprdata;
381 
382 #ifdef SCIP_MORE_DEBUG
383  SCIPdebugMsg(evaldata->scip, "eval vertexpolyfun\n");
384 #endif
385  val = 1.0;
386  for( i = 0, j = 0; i < nlhdlrexprdata->nvars; ++i )
387  {
388  if( nlhdlrexprdata->signs[i] != evaldata->sign )
389  continue;
390  /* the reformulated exponent of args[j] is found */
391  val *= pow(args[j], nlhdlrexprdata->refexponents[i]);
392  j++;
393  }
394 
395  return val;
396 }
397 
398 /** determine whether a power function \f$ w^h \f$ is special and add an overunderestimator or underestimator to a given rowprep
399  *
400  * \f$ w^h \f$ is special, if all variables are fixed, or it is a constant to estimate, a univariate power to estimate,
401  * or a bivariate power to underestimate. The estimator is multiplied by the multiplier and stored in the rowprep.
402  */
403 static
405  SCIP* scip, /**< SCIP data structure */
406  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
407  SCIP_Bool sign, /**< the sign of variables of the power function */
408  SCIP_Real multiplier, /**< the multiplier of the estimator */
409  SCIP_Bool overestimate, /**< whether overestimate or underestimator the power function */
410  SCIP_SOL* sol, /**< solution \f$ w' \f$ to use in estimation */
411  SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
412  SCIP_Bool* isspecial, /**< buffer to store whether this function is a special case */
413  SCIP_Bool* success /**< buffer to store whether successful */
414  )
415 {
416  int i;
417  SCIP_Bool allfixed = TRUE;
418  int nsignvars;
419 
420  assert(scip != NULL);
421  assert(nlhdlrexprdata != NULL);
422  assert(rowprep != NULL);
423  assert(isspecial != NULL);
424  assert(success != NULL);
425 
426  *success = FALSE;
427  /* check whether all variables are fixed */
428  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
429  {
430  if( nlhdlrexprdata->signs[i] != sign )
431  continue;
432 
433  if( !SCIPisRelEQ(scip, nlhdlrexprdata->intervals[i].inf, nlhdlrexprdata->intervals[i].sup) )
434  {
435  allfixed = FALSE;
436  break;
437  }
438  }
439 
440  /* allfixed is a special case */
441  if( allfixed )
442  {
443  /* return a constant */
444  SCIP_Real funcval = 1.0;
445  SCIP_Real scale;
446  SCIP_Real val;
447 
448  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
449  {
450  if( nlhdlrexprdata->signs[i] != sign )
451  continue;
452 
453  scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
454  val = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale;
455  funcval *= pow(val, nlhdlrexprdata->refexponents[i]);
456  }
457  SCIProwprepAddConstant(rowprep, multiplier * funcval);
458  *isspecial = TRUE;
459 
460  return SCIP_OKAY;
461  }
462 
463  /* number of variables in the power function */
464  nsignvars = sign ? nlhdlrexprdata->nposvars : nlhdlrexprdata->nnegvars;
465 
466  /* if the power function has no more than 2 variables, this a special case */
467  *isspecial = ( nsignvars <= 1 ) || ( nsignvars == 2 && !overestimate );
468  if( !*isspecial )
469  return SCIP_OKAY;
470 
471  if( nsignvars == 0 )
472  {
473  /* constant case */
474  SCIProwprepAddConstant(rowprep, multiplier);
475  *success = TRUE;
476  }
477  else if( nsignvars == 1 )
478  {
479  /* univariate case, w^h */
480  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
481  {
482  if( nlhdlrexprdata->signs[i] == sign )
483  {
484  /* the variable w is found */
485  SCIP_Real scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1;
486  SCIP_VAR* var = nlhdlrexprdata->vars[i];
487  SCIP_Real refexponent = nlhdlrexprdata->refexponents[i];
488  if( refexponent == 1.0 )
489  {
490  /* h = 1, a univariate linear function. Only rescale, no need for linearization */
491  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, var, multiplier / scale) );
492  }
493  else
494  {
495  /* a univariate power function */
496  SCIP_Real facetconstant;
497  SCIP_Real facetcoef;
498  SCIP_Real val = SCIPgetSolVal(scip, sol, var) / scale;
499  /* local (using bounds) depends on whether we under- or overestimate */
500  SCIP_Bool islocal = !overestimate;
501  SCIPestimateRoot(scip, refexponent, overestimate, nlhdlrexprdata->intervals[i].inf, nlhdlrexprdata->intervals[i].sup,
502  val, &facetconstant, &facetcoef, &islocal, success);
503  SCIProwprepAddConstant(rowprep, multiplier * facetconstant);
504  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, var, multiplier * facetcoef / scale) );
505  }
506  }
507  }
508  *success = TRUE;
509  }
510  else if( nsignvars == 2 && !overestimate )
511  {
512  /* bivariate case, f(w) = w^h = f_0(w_0) f_1(w_1). The convex under envelope is the maxmimum of
513  * two affine functions, each of which is determined by three extreme points the box bound.
514  * One affine function is supported by three lower left points; the other affine function is
515  * supported by three upper right points. For a point xstar in the box, its corresponding affine function can be determined by
516  * which region (upper right or lower left half space) the point is in. Thus, we can determine the region, and use the
517  * associated three extreme point to interpolate the affine function.
518  */
519  SCIP_Bool isupperright;
520  SCIP_Real dw0, dw1;
521  SCIP_Real f0w0l, f0w0u, f1w1l, f1w1u;
522  SCIP_Real fw0lw1u, fw0uw1l;
523  SCIP_Real facetconstant;
524  SCIP_Real facetcoefs[2] = {0.0, 0.0};
525  SCIP_VAR* vars[2] = {NULL, NULL};
526  SCIP_Real refexponents[2] = {0.0, 0.0};
527  SCIP_Real xstar[2] = {0.0, 0.0};;
528  SCIP_Real scale[2] = {0.0, 0.0};;
529  SCIP_Real box[4] = {0.0, 0.0, 0.0, 0.0};
530  int j = 0;
531 
532  /* get refexponents, xstar, scale, and box */
533  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
534  {
535  if( nlhdlrexprdata->signs[i] != sign )
536  continue;
537  box[2 * j] = nlhdlrexprdata->intervals[i].inf;
538  box[2 * j + 1] = nlhdlrexprdata->intervals[i].sup;
539  refexponents[j] = nlhdlrexprdata->refexponents[i];
540  scale[j] = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1;
541  vars[j] = nlhdlrexprdata->vars[i];
542  xstar[j] = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[j]) / scale[j];
543  j++;
544  }
545 
546  /* compute the box length*/
547  dw0 = box[1] - box[0];
548  dw1 = box[3] - box[2];
549 
550  /* determine the location (upper right or lower left half sapce) of the xstar.
551  * (dw1, dw0) is the direction vector to the upper right half space.
552  */
553  isupperright = ( (xstar[0] - box[0]) * dw1 + (xstar[1] - box[3]) * dw0 ) > 0.0;
554 
555  /* compute function values of f_0, f_1 at vertices */
556  f0w0l = pow(box[0], refexponents[0]);
557  f0w0u = pow(box[1], refexponents[0]);
558  f1w1l = pow(box[2], refexponents[1]);
559  f1w1u = pow(box[3], refexponents[1]);
560  fw0lw1u = f0w0l * f1w1u;
561  fw0uw1l = f0w0u * f1w1l;
562  if( isupperright )
563  {
564  /* underestimator: fw0uw1u + (fw0uw1u - fw0lw1u) / (dw0) * (x0 - w0u) + (fw0uw1u - fw0uw1l) / (dw1) * (x1 - w1u) */
565  SCIP_Real fw0uw1u = f0w0u * f1w1u;
566  facetcoefs[0] = (fw0uw1u - fw0lw1u) / dw0;
567  facetcoefs[1] = (fw0uw1u - fw0uw1l) / dw1;
568  facetconstant = fw0uw1u - facetcoefs[0] * box[1] - facetcoefs[1] * box[3];
569  }
570  else
571  {
572  /* underestimator: fw0lw1l + (fw0uw1l - fw0lw1l) / (dw0) * (x0 - w0l) + (fw0lw1u- fw0lw1l) / (dw1) * (x1 - w1l) */
573  SCIP_Real fw0lw1l = f0w0l * f1w1l;
574  facetcoefs[0] = (fw0uw1l - fw0lw1l) / dw0;
575  facetcoefs[1] = (fw0lw1u - fw0lw1l) / dw1;
576  facetconstant = fw0lw1l - facetcoefs[0] * box[0] - facetcoefs[1] * box[2];
577  }
578  SCIProwprepAddConstant(rowprep, multiplier * facetconstant);
579  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, vars[0], multiplier * facetcoefs[0] / scale[0]) );
580  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, vars[1], multiplier * facetcoefs[1] / scale[1]) );
581  *success = TRUE;
582  }
583 
584  return SCIP_OKAY;
585 }
586 
587 /** adds an underestimator for a multivariate concave power function \f$ w^h \f$ to a given rowprep
588  *
589  * Calls \ref SCIPcomputeFacetVertexPolyhedralNonlinear() for \f$ w^h \f$ and
590  * box set to local bounds of auxiliary variables. The estimator is multiplied
591  * by the multiplier and stored in the rowprep.
592  */
593 static
595  SCIP* scip, /**< SCIP data structure */
596  SCIP_CONSHDLR* conshdlr, /**< nonlinear constraint handler */
597  SCIP_NLHDLR* nlhdlr, /**< nonlinear handler */
598  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
599  SCIP_Bool sign, /**< the sign of variables of the power function */
600  SCIP_Real multiplier, /**< the multiplier of the estimator */
601  SCIP_SOL* sol, /**< solution \f$ w' \f$ to use*/
602  SCIP_Real targetvalue, /**< a target value to achieve; if not reachable, then can give up early */
603  SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
604  SCIP_Bool* success /**< buffer to store whether successful */
605  )
606 {
607  int i;
608  int j;
609  int nsignvars;
610  SCIP_Real facetconstant;
611  SCIP_Real scale;
612  SCIP_Real* box;
613  SCIP_Real* facetcoefs;
614  SCIP_Real* xstar;
615  VERTEXPOLYFUN_EVALDATA evaldata;
616 
617  assert(scip != NULL);
618  assert(nlhdlr != NULL);
619  assert(nlhdlrexprdata != NULL);
620  assert(rowprep != NULL);
621  assert(success != NULL);
622 
623  *success = FALSE;
624 
625  /* number of variables of sign */
626  nsignvars = sign ? nlhdlrexprdata->nposvars : nlhdlrexprdata->nnegvars;
627 
628  /* data structure to evaluate the power function */
629  evaldata.nlhdlrexprdata = nlhdlrexprdata;
630  evaldata.sign = sign;
631  evaldata.nsignvars = nsignvars;
632  evaldata.scip = scip;
633 
634  /* compute box constraints and reference value of variables*/
635  xstar = nlhdlrexprdata->xstar;
636  box = nlhdlrexprdata->box;
637  j = 0;
638  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
639  {
640  if( nlhdlrexprdata->signs[i] != sign )
641  continue;
642 
643  box[2 * j] = nlhdlrexprdata->intervals[i].inf;
644  box[2 * j + 1] = nlhdlrexprdata->intervals[i].sup;
645  scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
646  xstar[j] = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale;
647  j++;
648  }
649 
650  /* find a facet of the underestimator */
651  facetcoefs = nlhdlrexprdata->facetcoefs;
652  SCIP_CALL( SCIPcomputeFacetVertexPolyhedralNonlinear(scip, conshdlr, FALSE, nlhdlrExprEvalPower, (void*)&evaldata, xstar, box,
653  nsignvars, targetvalue, success, facetcoefs, &facetconstant) );
654 
655  if( !*success )
656  {
657  SCIPdebugMsg(scip, "failed to compute facet of convex hull\n");
658  return SCIP_OKAY;
659  }
660 
661  /* set coefficients in the rowprep */
662  SCIProwprepAddConstant(rowprep, multiplier * facetconstant);
663  j = 0;
664  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
665  {
666  if( nlhdlrexprdata->signs[i] != sign )
667  continue;
668  scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
669  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, nlhdlrexprdata->vars[i], multiplier * facetcoefs[j] / scale) );
670  j++;
671  }
672 
673  return SCIP_OKAY;
674 }
675 
676 /** adds an overestimator for a concave power function \f$ w^h \f$ to a given rowprep
677  *
678  * The estimator is multiplied by the multiplier and stored in the rowprep.
679  */
680 static
682  SCIP* scip, /**< SCIP data structure */
683  SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
684  SCIP_Bool sign, /**< the sign of variables of the power function */
685  SCIP_Real multiplier, /**< the multiplier of the estimator */
686  SCIP_SOL* sol, /**< solution to use */
687  SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
688  SCIP_Bool* success /**< buffer to store whether successful */
689  )
690 {
691  int i;
692  SCIP_Real facetcoef;
693  SCIP_Real facetconstant;
694  SCIP_Real funcval;
695  SCIP_Real refexponent;
696  SCIP_Real sumrefexponents;
697  SCIP_Real scale;
698  SCIP_Real val;
699  SCIP_VAR* var;
700  assert(scip != NULL);
701  assert(nlhdlrexprdata != NULL);
702  assert(rowprep != NULL);
703  assert(success != NULL);
704 
705  *success = FALSE;
706 
707  /* compute the value and the sum of reformulated exponents of the power function */
708  sumrefexponents = 0;
709  funcval = 1;
710  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
711  {
712  if( nlhdlrexprdata->signs[i] != sign )
713  continue;
714  scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
715  val = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale;
716  val = MAX(val, 0.1);
717  refexponent = nlhdlrexprdata->refexponents[i];
718  sumrefexponents += refexponent;
719  funcval *= pow(val, refexponent);
720  }
721 
722  /* overestimate by gradient cut: w'^h + h w'^(h - 1)(w - w') */
723  facetconstant = (1 - sumrefexponents) * funcval;
724  SCIProwprepAddConstant(rowprep, multiplier * facetconstant);
725  for( i = 0; i < nlhdlrexprdata->nvars; ++i )
726  {
727  if( nlhdlrexprdata->signs[i] != sign )
728  continue;
729  scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
730  var = nlhdlrexprdata->vars[i];
731  val = SCIPgetSolVal(scip, sol, var) / scale;
732  val = MAX(val, 0.1);
733  facetcoef = nlhdlrexprdata->refexponents[i] * funcval / val;
734  SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, var, multiplier * facetcoef / scale) );
735  }
736 
737  *success = TRUE;
738 
739  return SCIP_OKAY;
740 }
741 
742 /*
743  * Callback methods of nonlinear handler
744  */
745 
746 /** nonlinear handler estimation callback */
747 static
748 SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateSignomial)
749 { /*lint --e{715}*/
750  SCIP_Bool isboxsignomial;
751  SCIP_Bool isspecial;
752  SCIP_Bool undersign;
753  SCIP_Bool oversign;
754  int i;
755  int nundervars;
756  SCIP_Real undermultiplier;
757  SCIP_Real overmultiplier;
758  SCIP_NLHDLRDATA* nlhdlrdata;
759  SCIP_ROWPREP* rowprep;
760  SCIP_Real targetunder;
761  SCIP_Real scale;
762 
763  assert(conshdlr != NULL);
764  assert(nlhdlr != NULL);
765  assert(expr != NULL);
766  assert(nlhdlrexprdata != NULL);
767  assert(rowpreps != NULL);
768  *success = FALSE;
769  *addedbranchscores = FALSE;
770 
771  /* store and capture the vars of an expression, if the vars are not stored and captured yet */
772  if( !nlhdlrexprdata->isstorecapture )
773  {
774  SCIP_CALL( storeCaptureVars(scip, expr, nlhdlrexprdata) );
775  }
776 
777  /* check whether all variables have finite positive bounds, which is necessary for the expression to be a signomial term */
778  /* TODO consider allowing 0.0 lower bounds for u variables (and handle gradients at 0.0) */
779  isboxsignomial = FALSE;
780  checkSignomialBounds(scip, nlhdlrexprdata, &isboxsignomial);
781 
782  if( !isboxsignomial )
783  return SCIP_OKAY;
784 
785  nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
786 
787  /* determine the sign of variables for over- and underestimators, and the multiplier for estimators in the rowprep */
788  if( overestimate )
789  {
790  /* relax t <= x^a, i.e., 0 <= u^f - v^g, overestimate u^f, underestimate v^g */
791  oversign = TRUE;
792  undersign = FALSE;
793  overmultiplier = 1.0;
794  undermultiplier = -1.0;
795  nundervars = nlhdlrexprdata->nnegvars;
796  }
797  else
798  {
799  /* relax x^a <= t, i.e., u^f - v^g <= 0, underestimate u^f, overestimate v^g */
800  oversign = FALSE;
801  undersign = TRUE;
802  overmultiplier = -1.0;
803  undermultiplier = 1.0;
804  nundervars = nlhdlrexprdata->nposvars;
805  }
806 
807  /* compute the value of the overestimator, which is a target value for computing the underestimator efficiently */
808  targetunder = 1.0;
809  for( i = 0; i < nlhdlrexprdata->nvars; i++ )
810  {
811  if( nlhdlrexprdata->signs[i] == oversign )
812  {
813  scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
814  targetunder *= pow(SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale, nlhdlrexprdata->refexponents[i]);
815  }
816  }
817 
818 #ifdef SCIP_SIGCUT_DEBUG
819  SCIP_Real targetover = 1.0;
820 
821  /* print information on estimators */
822  SCIP_CALL( printSignomial(scip, expr, nlhdlrexprdata));
823  SCIPinfoMessage(scip, NULL, " Auxvalue: %f, targetvalue: %f, %sestimate.", auxvalue, targetvalue, overestimate ? "over" : "under");
824 
825  targetunder = 1.0;
826  for( i = 0; i < nlhdlrexprdata->nvars; i++ )
827  {
828  if( nlhdlrexprdata->signs[i] == undersign )
829  {
830  scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
831  targetover *= pow(SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale, nlhdlrexprdata->refexponents[i]);
832  }
833  }
834  SCIPinfoMessage(scip, NULL, " Underestimate: %s, overestimate: %s.",
835  undersign ? "positive" : "negative", oversign ? "positive" : "negative");
836  SCIPinfoMessage(scip, NULL, " Undervalue (targetover): %f, overvalue (targetunder): %f.", targetover, targetunder);
837 #endif
838 
839  /* create a rowprep and allocate memory for it */
841  SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nlhdlrexprdata->nvars + 1) );
842 
843  /* only underestimate a concave function, if the number of variables is below a given threshold */
844  if( nundervars <= nlhdlrdata->maxnundervars )
845  {
846  /* compute underestimator */
847  isspecial = FALSE;
848  /* check and compute the special case */
849  SCIP_CALL( estimateSpecialPower(scip, nlhdlrexprdata, undersign, undermultiplier, FALSE, sol, rowprep, &isspecial, success) );
850  if( !isspecial )
851  {
852  SCIP_CALL( underEstimatePower(scip, conshdlr, nlhdlr, nlhdlrexprdata, undersign, undermultiplier, sol, targetunder, rowprep, success) );
853  }
854  }
855 
856  if( *success )
857  {
858  /* compute overestimator */
859  isspecial = FALSE;
860  /* check and compute the special case */
861  SCIP_CALL( estimateSpecialPower(scip, nlhdlrexprdata, oversign, overmultiplier, TRUE, sol, rowprep, &isspecial, success) );
862  if( !isspecial )
863  {
864  SCIP_CALL( overEstimatePower(scip, nlhdlrexprdata, oversign, overmultiplier, sol, rowprep, success) );
865  }
866  }
867 
868  if( *success )
869  {
870  reformRowprep(scip, nlhdlrexprdata, rowprep, nlhdlrdata->mincutscale, success);
871  if( *success )
872  {
873  SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, 0, rowprep) );
874  }
875  }
876 
877  if( !*success )
878  SCIPfreeRowprep(scip, &rowprep);
879 
880  return SCIP_OKAY;
881 }
882 
883 /** callback to detect structure in expression tree */
884 static
885 SCIP_DECL_NLHDLRDETECT(nlhdlrDetectSignomial)
886 { /*lint --e{715}*/
887  assert(expr != NULL);
888  assert(enforcing != NULL);
889  assert(participating != NULL);
890 
891  /* for now, we do not get active if separation is already (or does not need to be) provided */
892  if( (*enforcing & SCIP_NLHDLR_METHOD_SEPABOTH) == SCIP_NLHDLR_METHOD_SEPABOTH )
893  {
894  return SCIP_OKAY;
895  }
896 
897  /* check for product expressions with more than one child */
898  if( SCIPisExprProduct(scip, expr) && SCIPexprGetNChildren(expr) >= 2 )
899  {
900  int c;
901  int nf = SCIPexprGetNChildren(expr);
902  int nvars = nf + 1;
903  SCIP_Bool ismultilinear = TRUE;
904 
905  /* create expression data for the nonlinear handler */
906  SCIP_CALL( SCIPallocClearBlockMemory(scip, nlhdlrexprdata) );
907  (*nlhdlrexprdata)->nfactors = nf;
908  (*nlhdlrexprdata)->nvars = nvars;
909 
910  /* allocate memory for expression data */
911  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->factors, nf) );
912  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->exponents, nf) );
913 
914  /* get monomial information */
915  SCIP_CALL( SCIPgetExprMonomialData(scip, expr, &((*nlhdlrexprdata)->coef), (*nlhdlrexprdata)->exponents, (*nlhdlrexprdata)->factors) );
916 
917  /* skip multilinear terms, since we wouldn't do better than expr_product */
918  for( c = 0; c < nf; c++ )
919  {
920  if( !SCIPisEQ(scip, (*nlhdlrexprdata)->exponents[c], 1.0) )
921  {
922  ismultilinear = FALSE;
923  break;
924  }
925  }
926 
927  if( ismultilinear )
928  {
929  /* if multilinear, we free memory of the expression data and do nothing */
930  freeExprDataMem(scip, nlhdlrexprdata, TRUE);
931  return SCIP_OKAY;
932  }
933  else
934  {
935  SCIP_Real normalize;
936  SCIP_Real sumlexponents = 0;
937  SCIP_Real sumrexponents = 1;
938  int nposvars = 0;
939 
940  /* allocate more memory for expression data */
941  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->signs, nvars) );
942  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->refexponents, nvars) );
943  SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*nlhdlrexprdata)->vars, nvars) );
944  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->intervals, nvars) );
945  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->xstar, nvars) );
946  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->facetcoefs, nvars) );
947  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->box, 2 * nvars) );
948 
949  (*nlhdlrexprdata)->isstorecapture = FALSE;
950 
951  /* detect more information for the reformulation: we first compute the sum
952  * of positive and negative exponents and determine the sign indicators
953  */
954  for( c = 0; c < nf; c++ )
955  {
956  /* capture sub expressions */
957  SCIPcaptureExpr((*nlhdlrexprdata)->factors[c]);
958  if( (*nlhdlrexprdata)->exponents[c] > 0.0 )
959  {
960  /* add a positive exponent */
961  sumlexponents += (*nlhdlrexprdata)->exponents[c];
962  (*nlhdlrexprdata)->signs[c] = TRUE;
963  nposvars++;
964  }
965  else
966  {
967  /* subtract a negative exponent */
968  sumrexponents -= (*nlhdlrexprdata)->exponents[c];
969  (*nlhdlrexprdata)->signs[c] = FALSE;
970  }
971  /* set null to working variables, meaning that they are not stored yet */
972  }
973  (*nlhdlrexprdata)->signs[nf] = FALSE;
974  (*nlhdlrexprdata)->nposvars = nposvars;
975  (*nlhdlrexprdata)->nnegvars = nf - nposvars + 1;
976 
977  /* compute the normalization constant */
978  normalize = MAX(sumlexponents, sumrexponents);
979  /* normalize positive and negative exponents */
980  for( c = 0; c < nf; c++ )
981  {
982  if( (*nlhdlrexprdata)->signs[c] )
983  (*nlhdlrexprdata)->refexponents[c] = (*nlhdlrexprdata)->exponents[c] / normalize;
984  else
985  (*nlhdlrexprdata)->refexponents[c] = -(*nlhdlrexprdata)->exponents[c] / normalize;
986  }
987  (*nlhdlrexprdata)->refexponents[nf] = 1.0 / normalize;
988 
989  /* tell children that we will use their auxvar and use its activity for estimation */
990  for( c = 0; c < nf; c++ )
991  {
992  SCIP_CALL( SCIPregisterExprUsageNonlinear(scip, (*nlhdlrexprdata)->factors[c], TRUE, FALSE, TRUE, TRUE) );
993  }
994  }
995  }
996 
997  if( *nlhdlrexprdata != NULL )
998  {
999  *participating = SCIP_NLHDLR_METHOD_SEPABOTH;
1000  }
1001 
1002 #ifdef SCIP_SIGCUT_DEBUG
1003  if( *participating )
1004  {
1005  SCIPdebugMsg(scip, "scip depth: %d, step: %d, expr pointer: %p, expr data pointer: %p, detected expr: total vars (exps) %d ",
1006  SCIPgetSubscipDepth(scip), SCIPgetStage(scip), (void *)expr, (void *)nlhdlrexprdata, (*nlhdlrexprdata)->nfactors);
1007  SCIPprintExpr(scip, expr, NULL);
1008  SCIPinfoMessage(scip, NULL, " participating: %d\n", *participating);
1009  }
1010 #endif
1011 
1012  return SCIP_OKAY;
1013 }
1014 
1015 /** auxiliary evaluation callback of nonlinear handler */
1016 static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxSignomial)
1017 { /*lint --e{715}*/
1018  int c;
1019  SCIP_Real val;
1020  SCIP_VAR* var;
1021 
1022  *auxvalue = nlhdlrexprdata->coef;
1023  for( c = 0; c < nlhdlrexprdata->nfactors; ++c )
1024  {
1025  assert(nlhdlrexprdata->factors[c] != NULL);
1026 
1027  var = SCIPgetExprAuxVarNonlinear(nlhdlrexprdata->factors[c]);
1028  assert(var != NULL);
1029 
1030  val = SCIPgetSolVal(scip, sol, var);
1031  if( SCIPisPositive(scip, val) )
1032  {
1033  *auxvalue *= pow(val, nlhdlrexprdata->exponents[c]);
1034  }
1035  else
1036  {
1037  *auxvalue = SCIP_INVALID;
1038  break;
1039  }
1040  }
1041 
1042  return SCIP_OKAY;
1043 }
1044 
1045 /** nonlinear handler copy callback */
1046 static
1047 SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrSignomial)
1048 { /*lint --e{715}*/
1049  assert(targetscip != NULL);
1050  assert(sourcenlhdlr != NULL);
1051  assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), NLHDLR_NAME) == 0);
1052 
1053  SCIP_CALL( SCIPincludeNlhdlrSignomial(targetscip) );
1054 
1055  return SCIP_OKAY;
1056 }
1057 
1058 /** callback to free data of handler */
1059 static
1060 SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrFreehdlrDataSignomial)
1061 { /*lint --e{715}*/
1062  assert(nlhdlrdata != NULL);
1063 
1064  SCIPfreeBlockMemory(scip, nlhdlrdata);
1065 
1066  return SCIP_OKAY;
1067 }
1068 
1069 /** callback to free expression specific data */
1070 static
1071 SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataSignomial)
1072 { /*lint --e{715}*/
1073  int c;
1074 
1075  /* release expressions */
1076  for( c = 0; c < (*nlhdlrexprdata)->nfactors; c++ )
1077  {
1078  SCIP_CALL( SCIPreleaseExpr(scip, &(*nlhdlrexprdata)->factors[c]) );
1079  }
1080 
1081  /* release variables */
1082  if( (*nlhdlrexprdata)->isstorecapture )
1083  {
1084  for( c = 0; c < (*nlhdlrexprdata)->nvars; c++ )
1085  {
1086  if( (*nlhdlrexprdata)->vars[c] != NULL )
1087  {
1088  SCIP_CALL( SCIPreleaseVar(scip, &(*nlhdlrexprdata)->vars[c]) );
1089  }
1090  }
1091  }
1092 
1093  /* free memory */
1094  freeExprDataMem(scip, nlhdlrexprdata, FALSE);
1095 
1096  return SCIP_OKAY;
1097 }
1098 
1099 
1100 /*
1101  * nonlinear handler specific interface methods
1102  */
1103 
1104 /** includes signomial nonlinear handler in nonlinear constraint handler */
1107  SCIP* scip /**< SCIP data structure */
1108  )
1109 {
1110  SCIP_NLHDLRDATA* nlhdlrdata;
1111  SCIP_NLHDLR* nlhdlr;
1112 
1113  assert(scip != NULL);
1114 
1115  /* create nonlinear handler specific data */
1116  SCIP_CALL( SCIPallocBlockMemory(scip, &nlhdlrdata));
1117  BMSclearMemory(nlhdlrdata);
1118 
1120  NLHDLR_ENFOPRIORITY, nlhdlrDetectSignomial, nlhdlrEvalauxSignomial, nlhdlrdata) );
1121  assert(nlhdlr != NULL);
1122 
1123  SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrSignomial);
1124  SCIPnlhdlrSetFreeHdlrData(nlhdlr, nlhdlrFreehdlrDataSignomial);
1125  SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrFreeExprDataSignomial);
1126  SCIPnlhdlrSetSepa(nlhdlr, NULL, NULL, nlhdlrEstimateSignomial, NULL);
1127 
1128  /* parameters */
1129  SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/maxnundervars",
1130  "maximum number of variables when underestimating a concave power function",
1131  &nlhdlrdata->maxnundervars, TRUE, NLHDLR_MAXNUNDERVARS, 2, 14, NULL, NULL) );
1132  SCIP_CALL( SCIPaddRealParam(scip, "nlhdlr/" NLHDLR_NAME "/mincutscale",
1133  "minimum scale factor when scaling a cut",
1134  &nlhdlrdata->mincutscale, TRUE, NLHDLR_MINCUTSCALE, 1e-6, 1e6, NULL, NULL) );
1135 
1136  return SCIP_OKAY;
1137 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
void SCIPestimateRoot(SCIP *scip, SCIP_Real exponent, SCIP_Bool overestimate, SCIP_Real xlb, SCIP_Real xub, SCIP_Real xref, SCIP_Real *constant, SCIP_Real *slope, SCIP_Bool *islocal, SCIP_Bool *success)
Definition: expr_pow.c:3396
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataSignomial)
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define NLHDLR_ENFOPRIORITY
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1486
static void printSignomial(SCIP *scip, FILE *file, char *linebuffer, int *linecnt, SCIP_EXPR *expr, SCIP_Real coef, SCIP_Bool needsign)
Definition: reader_pip.c:2177
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3854
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEEXPRDATA((*freeexprdata)))
Definition: nlhdlr.c:98
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:97
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1247
static void freeExprDataMem(SCIP *scip, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_Bool ispartial)
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
static SCIP_RETCODE underEstimatePower(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_NLHDLR *nlhdlr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_SOL *sol, SCIP_Real targetvalue, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
#define FALSE
Definition: def.h:94
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEHDLRDATA((*freehdlrdata)))
Definition: nlhdlr.c:87
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2605
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_NLHDLREXPRDATA * nlhdlrexprdata
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define NLHDLR_DESC
#define NLHDLR_MINCUTSCALE
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition: scip_expr.c:1409
#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:887
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectSignomial)
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1464
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:649
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrSignomial)
#define NLHDLR_DETECTPRIORITY
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:629
static SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateSignomial)
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxSignomial)
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:166
SCIP_VAR ** vars
Definition: struct_misc.h:288
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)
public functions to work with algebraic expressions
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17420
static SCIP_RETCODE overEstimatePower(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *success)
power and signed power expression handlers
SCIP_RETCODE SCIPincludeNlhdlrSignomial(SCIP *scip)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:583
#define SCIP_CALL(x)
Definition: def.h:380
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
Definition: misc_rowprep.c:746
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)), SCIP_DECL_NLHDLREXITSEPA((*exitsepa)))
Definition: nlhdlr.c:136
#define SCIP_Bool
Definition: def.h:91
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:760
static SCIP_RETCODE estimateSpecialPower(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool sign, SCIP_Real multiplier, SCIP_Bool overestimate, SCIP_SOL *sol, SCIP_ROWPREP *rowprep, SCIP_Bool *isspecial, SCIP_Bool *success)
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1417
constraint handler for nonlinear constraints specified by algebraic expressions
#define MIN(x, y)
Definition: def.h:243
#define NLHDLR_MAXNUNDERVARS
#define NLHDLR_NAME
static SCIP_DECL_VERTEXPOLYFUN(nlhdlrExprEvalPower)
static SCIP_RETCODE storeCaptureVars(SCIP *scip, SCIP_EXPR *expr, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
#define BMSclearMemory(ptr)
Definition: memory.h:129
signomial nonlinear handler
#define MAX(x, y)
Definition: def.h:239
static SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrFreehdlrDataSignomial)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwprepGetSide(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:659
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1213
#define SCIP_Real
Definition: def.h:173
#define SCIP_INVALID
Definition: def.h:193
SCIP_NLHDLRDATA * SCIPnlhdlrGetData(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:216
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
Definition: type_nlhdlr.h:453
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
Definition: misc_rowprep.c:563
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
Definition: type_nlhdlr.h:452
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetExprMonomialData(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *coef, SCIP_Real *exponents, SCIP_EXPR **factors)
Definition: scip_expr.c:2623
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: misc_rowprep.c:913
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
public functions of nonlinear handlers of nonlinear constraints
#define SCIP_NLHDLR_METHOD_SEPABOTH
Definition: type_nlhdlr.h:53
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
static void checkSignomialBounds(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_Bool *isboxsignomial)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
preparation of a linear inequality to become a SCIP_ROW
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
SCIP_VAR ** SCIProwprepGetVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:639
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRCOPYHDLR((*copy)))
Definition: nlhdlr.c:76
static void reformRowprep(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_ROWPREP *rowprep, SCIP_Real mincutscale, SCIP_Bool *success)