SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
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
42#include "scip/cons_nonlinear.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 \$ are two concave power functions.
72 */
73struct 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 */
95struct 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) */
103typedef 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 */
119static
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 {
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 {
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 */
192static
193void freeExprDataMem(
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
200 SCIPfreeBlockMemoryArrayNull(scip, &(*nlhdlrexprdata)->factors, (*nlhdlrexprdata)->nfactors);
201 SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->exponents, (*nlhdlrexprdata)->nfactors);
202 if( !ispartial )
203 {
204 int nvars = (*nlhdlrexprdata)->nvars;
205 SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->signs, nvars);
206 SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->refexponents, nvars);
207 SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->vars, nvars);
208 SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->intervals, nvars);
209 SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->box, 2*nvars); /*lint !e647*/
210 SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->xstar, nvars);
211 SCIPfreeBlockMemoryArray(scip, &(*nlhdlrexprdata)->facetcoefs, nvars);
212 }
213 SCIPfreeBlockMemory(scip, nlhdlrexprdata);
214 *nlhdlrexprdata = NULL;
215}
216
217/** reforms a rowprep to a standard form for nonlinear handlers
218 *
219 * The input rowprep is of the form \f$ a_u u + a_v v + b \f$.
220 * 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$.
221 * 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,
222 * 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
223 * 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$.
224 * A rowprep in standard form only contains an estimator of the expression and no auxvar.
225 * 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$.
226 * 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,
227 * 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
228 * 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$.
229 * A rowprep in standard form only contains an estimator of the expression and no auxvar.
230 */
231static
232void reformRowprep(
233 SCIP* scip, /**< SCIP data structure */
234 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< expression data */
235 SCIP_ROWPREP* rowprep, /**< cut to be reformulated */
236 SCIP_Real mincutscale, /**< min scaling factor for the cut in rowprep */
237 SCIP_Bool* success /**< pointer to store whether the reformulating was successful */
238)
239{
240 int i;
241 int nvars;
242 SCIP_Real coefauxvar;
243 SCIP_Real scale;
244 SCIP_Real* coefs;
245 SCIP_VAR* auxvar;
246 SCIP_VAR** vars;
247
248 assert(rowprep != NULL);
249 assert(nlhdlrexprdata != NULL);
250
254
255 /* find auxvar's cut coefficient and set it to zero */
256 auxvar = nlhdlrexprdata->vars[nlhdlrexprdata->nfactors];
257 coefauxvar = 1.0;
258 for( i = 0; i < nvars; i++ )
259 {
260 if( vars[i] == auxvar )
261 {
262 coefauxvar = coefs[i];
263 coefs[i] = 0.0;
264 break;
265 }
266 }
267
268 if( SCIPisZero(scip, coefauxvar) || coefauxvar >= 0.0 )
269 {
270 *success = FALSE;
271 }
272 else
273 {
274 /* the reformation scales the cut so that coefficients and constant are divided by the absolute value of coefauxvar */
275 assert(coefauxvar < 0.0);
276 scale = -1.0 / coefauxvar;
277 for( i = 0; i < nvars; i++ )
278 {
279 if( vars[i] == auxvar )
280 continue;
281 coefs[i] *= scale;
282 }
283 /* set the side to scale*side by adding -side and adding scale*side */
285
286 *success = SCIPisGT(scip, scale, mincutscale);
287 }
288}
289
290/** store and capture variables associated with the expression and its subexpressions */
291static
293 SCIP* scip, /**< SCIP data structure */
294 SCIP_EXPR* expr, /**< expression */
295 SCIP_NLHDLREXPRDATA* nlhdlrexprdata /**< expression data */
296 )
297{
298 int c;
299
300 assert(!nlhdlrexprdata->isstorecapture);
301
302 /* get and capture variables \f$x\f$ */
303 for( c = 0; c < nlhdlrexprdata->nfactors; ++c )
304 {
305 nlhdlrexprdata->vars[c] = SCIPgetExprAuxVarNonlinear(nlhdlrexprdata->factors[c]);
306 assert(nlhdlrexprdata->vars[c] != NULL);
307
308 SCIP_CALL( SCIPcaptureVar(scip, nlhdlrexprdata->vars[c]) );
309 }
310
311 /* get and capture variable \f$y\f$ */
312 nlhdlrexprdata->vars[c] = SCIPgetExprAuxVarNonlinear(expr);
313 assert(nlhdlrexprdata->vars[c] != NULL);
314 SCIP_CALL( SCIPcaptureVar(scip, nlhdlrexprdata->vars[c]) );
315
316 nlhdlrexprdata->isstorecapture = TRUE;
317
318 return SCIP_OKAY;
319}
320
321/** get bounds of variables x,t and check whether they are box constrained signomial variables */
322static
324 SCIP* scip, /**< SCIP data structure */
325 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< expression data */
326 SCIP_Bool* isboxsignomial /**< buffer to store whether variables are box constrained signomial variables */
327 )
328{
329 int c;
330 SCIP_Real powinf;
331 SCIP_Real powsup;
332 SCIP_Real productinf = 1;
333 SCIP_Real productsup = 1;
334
335 assert(nlhdlrexprdata->isstorecapture);
336
338
339 /* get bounds of x */
340 for( c = 0; c < nlhdlrexprdata->nfactors; c++ )
341 {
342 SCIP_Real inf = SCIPvarGetLbLocal(nlhdlrexprdata->vars[c]);
343 SCIP_Real sup = SCIPvarGetUbLocal(nlhdlrexprdata->vars[c]);
344
345 /* if the bounds of the variable are not positive and finite, or (bounds equal) then the expression is not a signomial */
346 if( !SCIPisPositive(scip, inf) || !SCIPisPositive(scip, sup) || SCIPisInfinity(scip, sup) || SCIPisEQ(scip, inf, sup) )
347 return;
348
349 nlhdlrexprdata->intervals[c].inf = inf;
350 nlhdlrexprdata->intervals[c].sup = MAX(sup, inf + 0.1);
351 powinf = pow(inf, nlhdlrexprdata->exponents[c]);
352 powsup = pow(sup, nlhdlrexprdata->exponents[c]);
355 }
356
357 /* compute bounds of t by bounds of x */
358 nlhdlrexprdata->intervals[c].inf = productinf;
359 nlhdlrexprdata->intervals[c].sup = productsup;
360
362}
363
364/** evaluate expression at solution w.r.t. auxiliary variables */
365static
367{
368 int i;
369 int j;
370 SCIP_Real val;
372 SCIP_NLHDLREXPRDATA* nlhdlrexprdata;
373
374 assert(args != NULL);
375
377
378 assert(evaldata != NULL);
379 assert(nargs == evaldata->nsignvars);
380
381 nlhdlrexprdata = evaldata->nlhdlrexprdata;
382
383#ifdef SCIP_MORE_DEBUG
384 SCIPdebugMsg(evaldata->scip, "eval vertexpolyfun\n");
385#endif
386 val = 1.0;
387 for( i = 0, j = 0; i < nlhdlrexprdata->nvars; ++i )
388 {
389 if( nlhdlrexprdata->signs[i] != evaldata->sign )
390 continue;
391 /* the reformulated exponent of args[j] is found */
392 val *= pow(args[j], nlhdlrexprdata->refexponents[i]);
393 j++;
394 }
395
396 return val;
397}
398
399/** determine whether a power function \f$ w^h \f$ is special and add an overunderestimator or underestimator to a given rowprep
400 *
401 * \f$ w^h \f$ is special, if all variables are fixed, or it is a constant to estimate, a univariate power to estimate,
402 * or a bivariate power to underestimate. The estimator is multiplied by the multiplier and stored in the rowprep.
403 */
404static
406 SCIP* scip, /**< SCIP data structure */
407 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
408 SCIP_Bool sign, /**< the sign of variables of the power function */
409 SCIP_Real multiplier, /**< the multiplier of the estimator */
410 SCIP_Bool overestimate, /**< whether overestimate or underestimator the power function */
411 SCIP_SOL* sol, /**< solution \f$ w' \f$ to use in estimation */
412 SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
413 SCIP_Bool* isspecial, /**< buffer to store whether this function is a special case */
414 SCIP_Bool* success /**< buffer to store whether successful */
415 )
416{
417 int i;
418 SCIP_Bool allfixed = TRUE;
419 int nsignvars;
420
421 assert(scip != NULL);
422 assert(nlhdlrexprdata != NULL);
423 assert(rowprep != NULL);
425 assert(success != NULL);
426
427 *success = FALSE;
428 /* check whether all variables are fixed */
429 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
430 {
431 if( nlhdlrexprdata->signs[i] != sign )
432 continue;
433
434 if( !SCIPisRelEQ(scip, nlhdlrexprdata->intervals[i].inf, nlhdlrexprdata->intervals[i].sup) )
435 {
436 allfixed = FALSE;
437 break;
438 }
439 }
440
441 /* allfixed is a special case */
442 if( allfixed )
443 {
444 /* return a constant */
445 SCIP_Real funcval = 1.0;
446 SCIP_Real scale;
447 SCIP_Real val;
448
449 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
450 {
451 if( nlhdlrexprdata->signs[i] != sign )
452 continue;
453
454 scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
455 val = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale;
456 funcval *= pow(val, nlhdlrexprdata->refexponents[i]);
457 }
459 *isspecial = TRUE;
460
461 return SCIP_OKAY;
462 }
463
464 /* number of variables in the power function */
465 nsignvars = sign ? nlhdlrexprdata->nposvars : nlhdlrexprdata->nnegvars;
466
467 /* if the power function has no more than 2 variables, this a special case */
468 *isspecial = ( nsignvars <= 1 ) || ( nsignvars == 2 && !overestimate );
469 if( !*isspecial )
470 return SCIP_OKAY;
471
472 if( nsignvars == 0 )
473 {
474 /* constant case */
476 *success = TRUE;
477 }
478 else if( nsignvars == 1 )
479 {
480 /* univariate case, w^h */
481 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
482 {
483 if( nlhdlrexprdata->signs[i] == sign )
484 {
485 /* the variable w is found */
486 SCIP_Real scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1;
487 SCIP_VAR* var = nlhdlrexprdata->vars[i];
488 SCIP_Real refexponent = nlhdlrexprdata->refexponents[i];
489 if( refexponent == 1.0 )
490 {
491 /* h = 1, a univariate linear function. Only rescale, no need for linearization */
493 }
494 else
495 {
496 /* a univariate power function */
497 SCIP_Real facetconstant;
498 SCIP_Real facetcoef;
499 SCIP_Real val = SCIPgetSolVal(scip, sol, var) / scale;
500 /* local (using bounds) depends on whether we under- or overestimate */
501 SCIP_Bool islocal = !overestimate;
502 SCIPestimateRoot(scip, refexponent, overestimate, nlhdlrexprdata->intervals[i].inf, nlhdlrexprdata->intervals[i].sup,
506 }
507 }
508 }
509 *success = TRUE;
510 }
511 else if( nsignvars == 2 && !overestimate )
512 {
513 /* bivariate case, f(w) = w^h = f_0(w_0) f_1(w_1). The convex under envelope is the maxmimum of
514 * two affine functions, each of which is determined by three extreme points the box bound.
515 * One affine function is supported by three lower left points; the other affine function is
516 * supported by three upper right points. For a point xstar in the box, its corresponding affine function can be determined by
517 * which region (upper right or lower left half space) the point is in. Thus, we can determine the region, and use the
518 * associated three extreme point to interpolate the affine function.
519 */
520 SCIP_Bool isupperright;
521 SCIP_Real dw0, dw1;
522 SCIP_Real f0w0l, f0w0u, f1w1l, f1w1u;
523 SCIP_Real fw0lw1u, fw0uw1l;
524 SCIP_Real facetconstant;
525 SCIP_Real facetcoefs[2] = {0.0, 0.0};
526 SCIP_VAR* vars[2] = {NULL, NULL};
527 SCIP_Real refexponents[2] = {0.0, 0.0};
528 SCIP_Real xstar[2] = {0.0, 0.0};;
529 SCIP_Real scale[2] = {0.0, 0.0};;
530 SCIP_Real box[4] = {0.0, 0.0, 0.0, 0.0};
531 int j = 0;
532
533 /* get refexponents, xstar, scale, and box */
534 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
535 {
536 if( nlhdlrexprdata->signs[i] != sign )
537 continue;
538 box[2 * j] = nlhdlrexprdata->intervals[i].inf;
539 box[2 * j + 1] = nlhdlrexprdata->intervals[i].sup;
540 refexponents[j] = nlhdlrexprdata->refexponents[i];
541 scale[j] = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1;
542 vars[j] = nlhdlrexprdata->vars[i];
543 xstar[j] = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[j]) / scale[j];
544 j++;
545 }
546
547 /* compute the box length*/
548 dw0 = box[1] - box[0];
549 dw1 = box[3] - box[2];
550
551 /* determine the location (upper right or lower left half sapce) of the xstar.
552 * (dw1, dw0) is the direction vector to the upper right half space.
553 */
554 isupperright = ( (xstar[0] - box[0]) * dw1 + (xstar[1] - box[3]) * dw0 ) > 0.0;
555
556 /* compute function values of f_0, f_1 at vertices */
557 f0w0l = pow(box[0], refexponents[0]);
558 f0w0u = pow(box[1], refexponents[0]);
559 f1w1l = pow(box[2], refexponents[1]);
560 f1w1u = pow(box[3], refexponents[1]);
561 fw0lw1u = f0w0l * f1w1u;
562 fw0uw1l = f0w0u * f1w1l;
563 if( isupperright )
564 {
565 /* underestimator: fw0uw1u + (fw0uw1u - fw0lw1u) / (dw0) * (x0 - w0u) + (fw0uw1u - fw0uw1l) / (dw1) * (x1 - w1u) */
566 SCIP_Real fw0uw1u = f0w0u * f1w1u;
567 facetcoefs[0] = (fw0uw1u - fw0lw1u) / dw0;
568 facetcoefs[1] = (fw0uw1u - fw0uw1l) / dw1;
569 facetconstant = fw0uw1u - facetcoefs[0] * box[1] - facetcoefs[1] * box[3];
570 }
571 else
572 {
573 /* underestimator: fw0lw1l + (fw0uw1l - fw0lw1l) / (dw0) * (x0 - w0l) + (fw0lw1u- fw0lw1l) / (dw1) * (x1 - w1l) */
574 SCIP_Real fw0lw1l = f0w0l * f1w1l;
575 facetcoefs[0] = (fw0uw1l - fw0lw1l) / dw0;
576 facetcoefs[1] = (fw0lw1u - fw0lw1l) / dw1;
577 facetconstant = fw0lw1l - facetcoefs[0] * box[0] - facetcoefs[1] * box[2];
578 }
582 *success = TRUE;
583 }
584
585 return SCIP_OKAY;
586}
587
588/** adds an underestimator for a multivariate concave power function \f$ w^h \f$ to a given rowprep
589 *
590 * Calls \ref SCIPcomputeFacetVertexPolyhedralNonlinear() for \f$ w^h \f$ and
591 * box set to local bounds of auxiliary variables. The estimator is multiplied
592 * by the multiplier and stored in the rowprep.
593 */
594static
596 SCIP* scip, /**< SCIP data structure */
597 SCIP_CONSHDLR* conshdlr, /**< nonlinear constraint handler */
598 SCIP_NLHDLR* nlhdlr, /**< nonlinear handler */
599 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
600 SCIP_Bool sign, /**< the sign of variables of the power function */
601 SCIP_Real multiplier, /**< the multiplier of the estimator */
602 SCIP_SOL* sol, /**< solution \f$ w' \f$ to use*/
603 SCIP_Real targetvalue, /**< a target value to achieve; if not reachable, then can give up early */
604 SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
605 SCIP_Bool* success /**< buffer to store whether successful */
606 )
607{
608 int i;
609 int j;
610 int nsignvars;
611 SCIP_Real facetconstant;
612 SCIP_Real scale;
613 SCIP_Real* box;
614 SCIP_Real* facetcoefs;
615 SCIP_Real* xstar;
617
618 assert(scip != NULL);
619 assert(nlhdlr != NULL);
620 assert(nlhdlrexprdata != NULL);
621 assert(rowprep != NULL);
622 assert(success != NULL);
623
624 *success = FALSE;
625
626 /* number of variables of sign */
627 nsignvars = sign ? nlhdlrexprdata->nposvars : nlhdlrexprdata->nnegvars;
628
629 /* data structure to evaluate the power function */
630 evaldata.nlhdlrexprdata = nlhdlrexprdata;
631 evaldata.sign = sign;
632 evaldata.nsignvars = nsignvars;
633 evaldata.scip = scip;
634
635 /* compute box constraints and reference value of variables*/
636 xstar = nlhdlrexprdata->xstar;
637 box = nlhdlrexprdata->box;
638 j = 0;
639 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
640 {
641 if( nlhdlrexprdata->signs[i] != sign )
642 continue;
643
644 box[2 * j] = nlhdlrexprdata->intervals[i].inf;
645 box[2 * j + 1] = nlhdlrexprdata->intervals[i].sup;
646 scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
647 xstar[j] = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale;
648 j++;
649 }
650
651 /* find a facet of the underestimator */
652 facetcoefs = nlhdlrexprdata->facetcoefs;
654 nsignvars, targetvalue, success, facetcoefs, &facetconstant) );
655
656 if( !*success )
657 {
658 SCIPdebugMsg(scip, "failed to compute facet of convex hull\n");
659 return SCIP_OKAY;
660 }
661
662 /* set coefficients in the rowprep */
664 j = 0;
665 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
666 {
667 if( nlhdlrexprdata->signs[i] != sign )
668 continue;
669 scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
670 SCIP_CALL( SCIPaddRowprepTerm(scip, rowprep, nlhdlrexprdata->vars[i], multiplier * facetcoefs[j] / scale) );
671 j++;
672 }
673
674 return SCIP_OKAY;
675}
676
677/** adds an overestimator for a concave power function \f$ w^h \f$ to a given rowprep
678 *
679 * The estimator is multiplied by the multiplier and stored in the rowprep.
680 */
681static
683 SCIP* scip, /**< SCIP data structure */
684 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nonlinear handler expression data */
685 SCIP_Bool sign, /**< the sign of variables of the power function */
686 SCIP_Real multiplier, /**< the multiplier of the estimator */
687 SCIP_SOL* sol, /**< solution to use */
688 SCIP_ROWPREP* rowprep, /**< rowprep where to store estimator */
689 SCIP_Bool* success /**< buffer to store whether successful */
690 )
691{
692 int i;
693 SCIP_Real facetcoef;
694 SCIP_Real facetconstant;
695 SCIP_Real funcval;
696 SCIP_Real refexponent;
697 SCIP_Real sumrefexponents;
698 SCIP_Real scale;
699 SCIP_Real val;
700 SCIP_VAR* var;
701 assert(scip != NULL);
702 assert(nlhdlrexprdata != NULL);
703 assert(rowprep != NULL);
704 assert(success != NULL);
705
706 *success = FALSE;
707
708 /* compute the value and the sum of reformulated exponents of the power function */
709 sumrefexponents = 0;
710 funcval = 1;
711 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
712 {
713 if( nlhdlrexprdata->signs[i] != sign )
714 continue;
715 scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
716 val = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale;
717 val = MAX(val, 0.1);
718 refexponent = nlhdlrexprdata->refexponents[i];
720 funcval *= pow(val, refexponent);
721 }
722
723 /* overestimate by gradient cut: w'^h + h w'^(h - 1)(w - w') */
726 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
727 {
728 if( nlhdlrexprdata->signs[i] != sign )
729 continue;
730 scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
731 var = nlhdlrexprdata->vars[i];
732 val = SCIPgetSolVal(scip, sol, var) / scale;
733 val = MAX(val, 0.1);
734 facetcoef = nlhdlrexprdata->refexponents[i] * funcval / val;
736 }
737
738 *success = TRUE;
739
740 return SCIP_OKAY;
741}
742
743/*
744 * Callback methods of nonlinear handler
745 */
746
747/** nonlinear handler estimation callback */
748static
750{ /*lint --e{715}*/
751 SCIP_Bool isboxsignomial;
752 SCIP_Bool isspecial;
753 SCIP_Bool undersign;
754 SCIP_Bool oversign;
755 int i;
756 int nundervars;
757 SCIP_Real undermultiplier;
758 SCIP_Real overmultiplier;
761 SCIP_Real targetunder;
762 SCIP_Real scale;
763
764 assert(conshdlr != NULL);
765 assert(nlhdlr != NULL);
766 assert(expr != NULL);
767 assert(nlhdlrexprdata != NULL);
768 assert(rowpreps != NULL);
769 *success = FALSE;
771
772 /* store and capture the vars of an expression, if the vars are not stored and captured yet */
773 if( !nlhdlrexprdata->isstorecapture )
774 {
775 SCIP_CALL( storeCaptureVars(scip, expr, nlhdlrexprdata) );
776 }
777
778 /* check whether all variables have finite positive bounds, which is necessary for the expression to be a signomial term */
779 /* TODO consider allowing 0.0 lower bounds for u variables (and handle gradients at 0.0) */
781 checkSignomialBounds(scip, nlhdlrexprdata, &isboxsignomial);
782
783 if( !isboxsignomial )
784 return SCIP_OKAY;
785
787
788 /* determine the sign of variables for over- and underestimators, and the multiplier for estimators in the rowprep */
789 if( overestimate )
790 {
791 /* relax t <= x^a, i.e., 0 <= u^f - v^g, overestimate u^f, underestimate v^g */
792 oversign = TRUE;
794 overmultiplier = 1.0;
795 undermultiplier = -1.0;
796 nundervars = nlhdlrexprdata->nnegvars;
797 }
798 else
799 {
800 /* relax x^a <= t, i.e., u^f - v^g <= 0, underestimate u^f, overestimate v^g */
801 oversign = FALSE;
802 undersign = TRUE;
803 overmultiplier = -1.0;
804 undermultiplier = 1.0;
805 nundervars = nlhdlrexprdata->nposvars;
806 }
807
808 /* compute the value of the overestimator, which is a target value for computing the underestimator efficiently */
809 targetunder = 1.0;
810 for( i = 0; i < nlhdlrexprdata->nvars; i++ )
811 {
812 if( nlhdlrexprdata->signs[i] == oversign )
813 {
814 scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
815 targetunder *= pow(SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale, nlhdlrexprdata->refexponents[i]);
816 }
817 }
818
819#ifdef SCIP_SIGCUT_DEBUG
820 SCIP_Real targetover = 1.0;
821
822 /* print information on estimators */
823 SCIP_CALL( printSignomial(scip, expr, nlhdlrexprdata));
824 SCIPinfoMessage(scip, NULL, " Auxvalue: %f, targetvalue: %f, %sestimate.", auxvalue, targetvalue, overestimate ? "over" : "under");
825
826 targetunder = 1.0;
827 for( i = 0; i < nlhdlrexprdata->nvars; i++ )
828 {
829 if( nlhdlrexprdata->signs[i] == undersign )
830 {
831 scale = i == (nlhdlrexprdata->nvars - 1) ? nlhdlrexprdata->coef : 1.0;
832 targetover *= pow(SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]) / scale, nlhdlrexprdata->refexponents[i]);
833 }
834 }
835 SCIPinfoMessage(scip, NULL, " Underestimate: %s, overestimate: %s.",
836 undersign ? "positive" : "negative", oversign ? "positive" : "negative");
837 SCIPinfoMessage(scip, NULL, " Undervalue (targetover): %f, overvalue (targetunder): %f.", targetover, targetunder);
838#endif
839
840 /* create a rowprep and allocate memory for it */
842 SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nlhdlrexprdata->nvars + 1) );
843
844 /* only underestimate a concave function, if the number of variables is below a given threshold */
846 {
847 /* compute underestimator */
849 /* check and compute the special case */
851 if( !isspecial )
852 {
853 SCIP_CALL( underEstimatePower(scip, conshdlr, nlhdlr, nlhdlrexprdata, undersign, undermultiplier, sol, targetunder, rowprep, success) );
854 }
855 }
856
857 if( *success )
858 {
859 /* compute overestimator */
861 /* check and compute the special case */
863 if( !isspecial )
864 {
866 }
867 }
868
869 if( *success )
870 {
871 reformRowprep(scip, nlhdlrexprdata, rowprep, nlhdlrdata->mincutscale, success);
872 if( *success )
873 {
875 }
876 }
877
878 if( !*success )
880
881 return SCIP_OKAY;
882}
883
884/** callback to detect structure in expression tree */
885static
887{ /*lint --e{715}*/
888
889 assert(expr != NULL);
892
893 /* for now, we do not get active if separation is already (or does not need to be) provided */
895 {
896 return SCIP_OKAY;
897 }
898
899 /* check for product expressions with more than one child */
900 if( SCIPisExprProduct(scip, expr) && SCIPexprGetNChildren(expr) >= 2 )
901 {
902 int c;
903 int nf = SCIPexprGetNChildren(expr);
904 int nvars = nf + 1;
905 SCIP_Bool ismultilinear = TRUE;
906
907 /* create expression data for the nonlinear handler */
908 SCIP_CALL( SCIPallocClearBlockMemory(scip, nlhdlrexprdata) );
909 (*nlhdlrexprdata)->nfactors = nf;
910 (*nlhdlrexprdata)->nvars = nvars;
911
912 /* allocate memory for expression data */
913 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->factors, nf) );
914 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->exponents, nf) );
915
916 /* get monomial information */
917 SCIP_CALL( SCIPgetExprMonomialData(scip, expr, &((*nlhdlrexprdata)->coef), (*nlhdlrexprdata)->exponents, (*nlhdlrexprdata)->factors) );
918
919 /* skip multilinear terms, since we wouldn't do better than expr_product */
920 for( c = 0; c < nf; c++ )
921 {
922 if( !SCIPisEQ(scip, (*nlhdlrexprdata)->exponents[c], 1.0) )
923 {
925 break;
926 }
927 }
928
929 if( ismultilinear )
930 {
931 /* if multilinear, we free memory of the expression data and do nothing */
932 freeExprDataMem(scip, nlhdlrexprdata, TRUE);
933 return SCIP_OKAY;
934 }
935 else
936 {
937 SCIP_Real normalize;
938 SCIP_Real sumlexponents = 0;
939 SCIP_Real sumrexponents = 1;
940 int nposvars = 0;
941
942 /* allocate more memory for expression data */
943 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->signs, nvars) );
944 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->refexponents, nvars) );
945 SCIP_CALL( SCIPallocClearBlockMemoryArray(scip, &(*nlhdlrexprdata)->vars, nvars) );
946 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->intervals, nvars) );
947 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->xstar, nvars) );
948 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->facetcoefs, nvars) );
949 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->box, 2 * nvars) );
950
951 (*nlhdlrexprdata)->isstorecapture = FALSE;
952
953 /* detect more information for the reformulation: we first compute the sum
954 * of positive and negative exponents and determine the sign indicators
955 */
956 for( c = 0; c < nf; c++ )
957 {
958 /* capture sub expressions */
959 SCIPcaptureExpr((*nlhdlrexprdata)->factors[c]);
960 if( (*nlhdlrexprdata)->exponents[c] > 0.0 )
961 {
962 /* add a positive exponent */
963 sumlexponents += (*nlhdlrexprdata)->exponents[c];
964 (*nlhdlrexprdata)->signs[c] = TRUE;
965 nposvars++;
966 }
967 else
968 {
969 /* subtract a negative exponent */
970 sumrexponents -= (*nlhdlrexprdata)->exponents[c];
971 (*nlhdlrexprdata)->signs[c] = FALSE;
972 }
973 /* set null to working variables, meaning that they are not stored yet */
974 }
975 (*nlhdlrexprdata)->signs[nf] = FALSE;
976 (*nlhdlrexprdata)->nposvars = nposvars;
977 (*nlhdlrexprdata)->nnegvars = nf - nposvars + 1;
978
979 /* compute the normalization constant */
980 normalize = MAX(sumlexponents, sumrexponents);
981 /* normalize positive and negative exponents */
982 for( c = 0; c < nf; c++ )
983 {
984 if( (*nlhdlrexprdata)->signs[c] )
985 (*nlhdlrexprdata)->refexponents[c] = (*nlhdlrexprdata)->exponents[c] / normalize;
986 else
987 (*nlhdlrexprdata)->refexponents[c] = -(*nlhdlrexprdata)->exponents[c] / normalize;
988 }
989 (*nlhdlrexprdata)->refexponents[nf] = 1.0 / normalize;
990
991 /* tell children that we will use their auxvar and use its activity for estimation */
992 for( c = 0; c < nf; c++ )
993 {
994 SCIP_CALL( SCIPregisterExprUsageNonlinear(scip, (*nlhdlrexprdata)->factors[c], TRUE, FALSE, TRUE, TRUE) );
995 }
996 }
997 }
998
999 if( *nlhdlrexprdata != NULL )
1000 {
1002 }
1003
1004#ifdef SCIP_SIGCUT_DEBUG
1005 if( *participating )
1006 {
1007 SCIPdebugMsg(scip, "scip depth: %d, step: %d, expr pointer: %p, expr data pointer: %p, detected expr: total vars (exps) %d ",
1008 SCIPgetSubscipDepth(scip), SCIPgetStage(scip), (void *)expr, (void *)nlhdlrexprdata, (*nlhdlrexprdata)->nfactors);
1009 SCIPprintExpr(scip, expr, NULL);
1010 SCIPinfoMessage(scip, NULL, " participating: %d\n", *participating);
1011 }
1012#endif
1013
1014 return SCIP_OKAY;
1015}
1016
1017/** auxiliary evaluation callback of nonlinear handler */
1019{ /*lint --e{715}*/
1020 int c;
1021 SCIP_Real val;
1022 SCIP_VAR* var;
1023
1024 *auxvalue = nlhdlrexprdata->coef;
1025 for( c = 0; c < nlhdlrexprdata->nfactors; ++c )
1026 {
1027 assert(nlhdlrexprdata->factors[c] != NULL);
1028
1029 var = SCIPgetExprAuxVarNonlinear(nlhdlrexprdata->factors[c]);
1030 assert(var != NULL);
1031
1032 val = SCIPgetSolVal(scip, sol, var);
1033 if( SCIPisPositive(scip, val) )
1034 {
1035 *auxvalue *= pow(val, nlhdlrexprdata->exponents[c]);
1036 }
1037 else
1038 {
1039 *auxvalue = SCIP_INVALID;
1040 break;
1041 }
1042 }
1043
1044 return SCIP_OKAY;
1045}
1046
1047/** nonlinear handler copy callback */
1048static
1050{ /*lint --e{715}*/
1054
1056
1057 return SCIP_OKAY;
1058}
1059
1060/** callback to free data of handler */
1061static
1063{ /*lint --e{715}*/
1065
1067
1068 return SCIP_OKAY;
1069}
1070
1071/** callback to free expression specific data */
1072static
1074{ /*lint --e{715}*/
1075 int c;
1076
1077 /* release expressions */
1078 for( c = 0; c < (*nlhdlrexprdata)->nfactors; c++ )
1079 {
1080 SCIP_CALL( SCIPreleaseExpr(scip, &(*nlhdlrexprdata)->factors[c]) );
1081 }
1082
1083 /* release variables */
1084 if( (*nlhdlrexprdata)->isstorecapture )
1085 {
1086 for( c = 0; c < (*nlhdlrexprdata)->nvars; c++ )
1087 {
1088 if( (*nlhdlrexprdata)->vars[c] != NULL )
1089 {
1090 SCIP_CALL( SCIPreleaseVar(scip, &(*nlhdlrexprdata)->vars[c]) );
1091 }
1092 }
1093 }
1094
1095 /* free memory */
1096 freeExprDataMem(scip, nlhdlrexprdata, FALSE);
1097
1098 return SCIP_OKAY;
1099}
1100
1101
1102/*
1103 * nonlinear handler specific interface methods
1104 */
1105
1106/** includes signomial nonlinear handler in nonlinear constraint handler */
1109 SCIP* scip /**< SCIP data structure */
1110 )
1111{
1113 SCIP_NLHDLR* nlhdlr;
1114
1115 assert(scip != NULL);
1116
1117 /* create nonlinear handler specific data */
1120
1123 assert(nlhdlr != NULL);
1124
1129
1130 /* parameters */
1131 SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/maxnundervars",
1132 "maximum number of variables when underestimating a concave power function",
1133 &nlhdlrdata->maxnundervars, TRUE, NLHDLR_MAXNUNDERVARS, 2, 14, NULL, NULL) );
1134 SCIP_CALL( SCIPaddRealParam(scip, "nlhdlr/" NLHDLR_NAME "/mincutscale",
1135 "minimum scale factor when scaling a cut",
1136 &nlhdlrdata->mincutscale, TRUE, NLHDLR_MINCUTSCALE, 1e-6, 1e6, NULL, NULL) );
1137
1138 return SCIP_OKAY;
1139}
constraint handler for nonlinear constraints specified by algebraic expressions
#define NULL
Definition def.h:267
#define SCIP_INVALID
Definition def.h:193
#define MIN(x, y)
Definition def.h:243
#define TRUE
Definition def.h:93
#define FALSE
Definition def.h:94
#define MAX(x, y)
Definition def.h:239
#define SCIP_CALL(x)
Definition def.h:374
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:3395
power and signed power expression handlers
variable expression handler
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPregisterExprUsageNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Bool useauxvar, SCIP_Bool useactivityforprop, SCIP_Bool useactivityforsepabelow, SCIP_Bool useactivityforsepaabove)
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)
#define SCIP_DECL_VERTEXPOLYFUN(f)
int SCIPgetSubscipDepth(SCIP *scip)
Definition scip_copy.c:2605
SCIP_STAGE SCIPgetStage(SCIP *scip)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
#define SCIPdebugMsg
SCIP_RETCODE SCIPincludeNlhdlrSignomial(SCIP *scip)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:83
SCIP_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
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition expr.c:3854
SCIP_Bool SCIPisExprProduct(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1464
SCIP_RETCODE SCIPgetExprMonomialData(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *coef, SCIP_Real *exponents, SCIP_EXPR **factors)
Definition scip_expr.c:2623
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition scip_expr.c:1417
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition scip_expr.c:1486
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition scip_expr.c:1409
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:110
#define SCIPallocClearBlockMemory(scip, ptr)
Definition scip_mem.h:91
#define SCIPallocClearBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:97
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition scip_mem.h:111
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIP_NLHDLRDATA * SCIPnlhdlrGetData(SCIP_NLHDLR *nlhdlr)
Definition nlhdlr.c:216
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr,)
Definition nlhdlr.c:98
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
Definition nlhdlr.c:166
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)),)
Definition nlhdlr.c:136
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr,)
Definition nlhdlr.c:87
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr,)
Definition nlhdlr.c:76
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)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1217
SCIP_Bool SCIPisRelEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:18144
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1250
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:18134
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1216
SCIP_VAR ** SCIProwprepGetVars(SCIP_ROWPREP *rowprep)
SCIP_Real SCIProwprepGetSide(SCIP_ROWPREP *rowprep)
SCIP_RETCODE SCIPensureRowprepSize(SCIP *scip, SCIP_ROWPREP *rowprep, int size)
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
SCIP_RETCODE SCIPcreateRowprep(SCIP *scip, SCIP_ROWPREP **rowprep, SCIP_SIDETYPE sidetype, SCIP_Bool local)
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
void SCIProwprepAddSide(SCIP_ROWPREP *rowprep, SCIP_Real side)
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
return SCIP_OKAY
int c
static SCIP_SOL * sol
assert(minobj< SCIPgetCutoffbound(scip))
int nvars
SCIP_VAR * var
static SCIP_VAR ** vars
#define BMSclearMemory(ptr)
Definition memory.h:129
#define NLHDLR_DETECTPRIORITY
#define NLHDLR_MAXNUNDERVARS
#define NLHDLR_ENFOPRIORITY
#define NLHDLR_DESC
#define NLHDLR_NAME
#define NLHDLR_MINCUTSCALE
signomial nonlinear handler
preparation of a linear inequality to become a SCIP_ROW
public functions of nonlinear handlers of nonlinear constraints
static void printSignomial(SCIP *scip, FILE *file, char *linebuffer, int *linecnt, SCIP_EXPR *expr, SCIP_Real coef, SCIP_Bool needsign)
public functions to work with algebraic expressions
@ SCIP_SIDETYPE_RIGHT
Definition type_lp.h:65
@ SCIP_SIDETYPE_LEFT
Definition type_lp.h:64
#define SCIP_DECL_NLHDLREVALAUX(x)
#define SCIP_DECL_NLHDLRESTIMATE(x)
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
#define SCIP_NLHDLR_METHOD_SEPABOTH
Definition type_nlhdlr.h:53
#define SCIP_DECL_NLHDLRCOPYHDLR(x)
Definition type_nlhdlr.h:70
#define SCIP_DECL_NLHDLRFREEEXPRDATA(x)
Definition type_nlhdlr.h:94
#define SCIP_DECL_NLHDLRDETECT(x)
#define SCIP_DECL_NLHDLRFREEHDLRDATA(x)
Definition type_nlhdlr.h:82
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
enum SCIP_Retcode SCIP_RETCODE