SCIP Doxygen Documentation
 
Loading...
Searching...
No Matches
expr_exp.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file expr_exp.c
26 * @ingroup DEFPLUGINS_EXPR
27 * @brief exponential expression handler
28 * @author Stefan Vigerske
29 * @author Benjamin Mueller
30 * @author Ksenia Bestuzheva
31 */
32
33/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34
35#define _USE_MATH_DEFINES /* to get M_E on Windows */ /*lint !750 */
36
37#include <string.h>
38#include <math.h>
39
40#include "scip/expr_exp.h"
41#include "scip/expr_value.h"
42
43#define EXPRHDLR_NAME "exp"
44#define EXPRHDLR_DESC "exponential expression"
45#define EXPRHDLR_PRECEDENCE 85000
46#define EXPRHDLR_HASHKEY SCIPcalcFibHash(10181.0)
47
48/*
49 * Data structures
50 */
51
52/*
53 * Local methods
54 */
55
56/** computes coefficients of secant of an exponential term */
57static
59 SCIP* scip, /**< SCIP data structure */
60 SCIP_Real lb, /**< lower bound on variable */
61 SCIP_Real ub, /**< upper bound on variable */
62 SCIP_Real* lincoef, /**< buffer to add coefficient of secant */
63 SCIP_Real* linconstant, /**< buffer to add constant of secant */
64 SCIP_Bool* success /**< buffer to set to FALSE if secant has failed due to large numbers or unboundedness */
65 )
66{
67 SCIP_Real coef;
68 SCIP_Real constant;
69
70 assert(scip != NULL);
73 assert(SCIPisLE(scip, lb, ub));
74 assert(lincoef != NULL);
77
78 if( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
79 {
80 /* unboundedness */
81 *success = FALSE;
82 return;
83 }
84
85 /* if lb and ub are too close use a safe secant */
86 if( SCIPisEQ(scip, lb, ub) )
87 {
88 coef = 0.0;
89 constant = exp(ub);
90 }
91 else
92 {
93 coef = (exp(ub) - exp(lb)) / (ub - lb);
94 constant = exp(ub) - coef * ub;
95 }
96
97 if( SCIPisInfinity(scip, REALABS(coef)) || SCIPisInfinity(scip, REALABS(constant)) )
98 {
99 *success = FALSE;
100 return;
101 }
102
103 *lincoef += coef;
104 *linconstant += constant;
105}
106
107/** computes coefficients of linearization of an exponential term in a reference point */
108static
110 SCIP* scip, /**< SCIP data structure */
111 SCIP_Real refpoint, /**< point for which to compute value of linearization */
112 SCIP_Bool isint, /**< whether corresponding variable is a discrete variable, and thus linearization could be moved */
113 SCIP_Real* lincoef, /**< buffer to add coefficient of secant */
114 SCIP_Real* linconstant, /**< buffer to add constant of secant */
115 SCIP_Bool* success /**< buffer to set to FALSE if secant has failed due to large numbers or unboundedness */
116 )
117{
118 SCIP_Real constant;
119 SCIP_Real coef;
120
121 assert(scip != NULL);
122 assert(lincoef != NULL);
124 assert(success != NULL);
125
127 {
128 *success = FALSE;
129 return;
130 }
131
133 {
134 coef = exp(refpoint);
135 constant = exp(refpoint) * (1.0 - refpoint);
136 }
137 else
138 {
139 /* exp(x) -> secant between f=floor(refpoint) and f+1 = ((e-1)*e^f) * x + e^f - f * ((e-1)*e^f) */
140 SCIP_Real f;
141
142 f = SCIPfloor(scip, refpoint);
143
144 coef = (M_E - 1.0) * exp(f);
145 constant = exp(f) - f * coef;
146 }
147
148 if( SCIPisInfinity(scip, REALABS(coef)) || SCIPisInfinity(scip, REALABS(constant)) )
149 {
150 *success = FALSE;
151 return;
152 }
153
154 *lincoef += coef;
155 *linconstant += constant;
156}
157
158/*
159 * Callback methods of expression handler
160 */
161
162/** simplifies an exp expression
163 *
164 * Evaluates the exponential function when its child is a value expression.
165 *
166 * TODO: exp(log(*)) = *
167 */
168static
170{
171 SCIP_EXPR* child;
172
173 assert(scip != NULL);
174 assert(expr != NULL);
176 assert(SCIPexprGetNChildren(expr) == 1);
177
178 child = SCIPexprGetChildren(expr)[0];
179 assert(child != NULL);
180
181 /**! [SnippetExprSimplifyExp] */
182 /* check for value expression */
183 if( SCIPisExprValue(scip, child) )
184 {
186 }
187 else
188 {
189 *simplifiedexpr = expr;
190
191 /* we have to capture it, since it must simulate a "normal" simplified call in which a new expression is created */
193 }
194 /**! [SnippetExprSimplifyExp] */
195
196 return SCIP_OKAY;
197}
198
199/** expression handler copy callback */
200static
202{ /*lint --e{715}*/
204
205 return SCIP_OKAY;
206}
207
208/** expression data copy callback */
209static
211{ /*lint --e{715}*/
215
217
218 return SCIP_OKAY;
219}
220
221/** expression data free callback */
222static
224{ /*lint --e{715}*/
225 assert(expr != NULL);
226
227 SCIPexprSetData(expr, NULL);
228
229 return SCIP_OKAY;
230}
231
232/** expression parse callback */
233static
235{ /*lint --e{715}*/
237
238 assert(expr != NULL);
239
240 /**! [SnippetExprParseExp] */
241 /* parse child expression from remaining string */
244
245 /* create exponential expression */
247 assert(*expr != NULL);
248
249 /* release child expression since it has been captured by the exponential expression */
251
252 *success = TRUE;
253 /**! [SnippetExprParseExp] */
254
255 return SCIP_OKAY;
256}
257
258/** expression point evaluation callback */
259static
261{ /*lint --e{715}*/
262 assert(expr != NULL);
263 assert(SCIPexprGetData(expr) == NULL);
264 assert(SCIPexprGetNChildren(expr) == 1);
265 assert(SCIPexprGetEvalValue(SCIPexprGetChildren(expr)[0]) != SCIP_INVALID); /*lint !e777*/
266
268
269 return SCIP_OKAY;
270}
271
272/** expression derivative evaluation callback */
273static
275{ /*lint --e{715}*/
276 assert(expr != NULL);
277 assert(childidx == 0);
279 assert(SCIPexprGetEvalValue(expr) != SCIP_INVALID); /*lint !e777*/
280
281 *val = SCIPexprGetEvalValue(expr);
282
283 return SCIP_OKAY;
284}
285
286/** expression interval evaluation callback */
287static
305
306/** expression estimator callback */
307static
309{ /*lint --e{715}*/
310 assert(scip != NULL);
311 assert(expr != NULL);
312 assert(SCIPexprGetNChildren(expr) == 1);
314 assert(coefs != NULL);
315 assert(constant != NULL);
316 assert(islocal != NULL);
317 assert(branchcand != NULL);
318 assert(*branchcand == TRUE);
319 assert(success != NULL);
320
321 *success = TRUE;
322 *coefs = 0.0;
323 *constant = 0.0;
324
325 if( overestimate )
326 {
327 addExpSecant(scip, localbounds[0].inf, localbounds[0].sup, coefs, constant, success);
328 *islocal = TRUE; /* secants are only valid locally */
329 }
330 else
331 {
333 *islocal = FALSE; /* linearization are globally valid */
334 *branchcand = FALSE;
335 }
336
337 return SCIP_OKAY;
338}
339
340/** initital estimates callback for an exponential expression */
341static
343{
345 SCIP_Bool overest[4] = {FALSE, FALSE, FALSE, TRUE};
346 SCIP_EXPR* child;
347 SCIP_Real lb;
348 SCIP_Real ub;
349 SCIP_Bool success;
350 int i;
351
352 assert(scip != NULL);
353 assert(expr != NULL);
354 assert(SCIPexprGetNChildren(expr) == 1);
356
357 /* get expression data */
358 child = SCIPexprGetChildren(expr)[0];
359 assert(child != NULL);
360
361 lb = bounds[0].inf;
362 ub = bounds[0].sup;
363
364 if( !overestimate )
365 {
366 SCIP_Real lbfinite;
367 SCIP_Real ubfinite;
368
369 /* make bounds finite */
370 lbfinite = SCIPisInfinity(scip, -lb) ? MIN(-5.0, ub - 0.1 * REALABS(ub)) : lb; /*lint !e666*/
371 ubfinite = SCIPisInfinity(scip, ub) ? MAX( 3.0, lb + 0.1 * REALABS(lb)) : ub; /*lint !e666*/
372
373 refpointsunder[0] = (7.0 * lbfinite + ubfinite) / 8.0;
374 refpointsunder[1] = (lbfinite + ubfinite) / 2.0;
375 refpointsunder[2] = (lbfinite + 7.0 * ubfinite) / 8.0;
376 }
377
378 *nreturned = 0;
379 for( i = 0; i < 4; ++i )
380 {
381 if( !overest[i] && overestimate )
382 continue;
383
384 if( overest[i] && (!overestimate || SCIPisInfinity(scip, ub) || SCIPisInfinity(scip, -lb)) )
385 continue;
386
387 assert(overest[i] || (SCIPisLE(scip, refpointsunder[i], ub) && SCIPisGE(scip, refpointsunder[i], lb))); /*lint !e661*/
388
389 coefs[*nreturned][0] = 0.0;
390 constant[*nreturned] = 0.0;
391
392 success = TRUE;
393
394 if( !overest[i] )
395 {
396 assert(i < 3);
397 /* coverity[overrun] */
398 addExpLinearization(scip, refpointsunder[i], SCIPexprIsIntegral(child), coefs[*nreturned], &constant[*nreturned], &success); /*lint !e661*/
399 }
400 else
401 addExpSecant(scip, lb, ub, coefs[*nreturned], &constant[*nreturned], &success);
402
403 if( success )
404 ++*nreturned;
405 }
406
407 return SCIP_OKAY;
408}
409
410/** expression reverse propagation callback */
411static
413{ /*lint --e{715}*/
414 assert(scip != NULL);
415 assert(expr != NULL);
416 assert(SCIPexprGetNChildren(expr) == 1);
417 assert(SCIPintervalGetInf(bounds) >= 0.0);
418
419 if( SCIPintervalGetSup(bounds) <= 0.0 )
420 {
421 *infeasible = TRUE;
422 return SCIP_OKAY;
423 }
424
425 /* f = exp(c0) -> c0 = log(f) */
427
428 return SCIP_OKAY;
429}
430
431/** expression hash callback */
432static
434{ /*lint --e{715}*/
435 assert(scip != NULL);
436 assert(expr != NULL);
437 assert(SCIPexprGetNChildren(expr) == 1);
438 assert(hashkey != NULL);
440
442 *hashkey ^= childrenhashes[0];
443
444 return SCIP_OKAY;
445}
446
447/** expression curvature detection callback */
448static
450{ /*lint --e{715}*/
451 assert(scip != NULL);
452 assert(expr != NULL);
454 assert(success != NULL);
455 assert(SCIPexprGetNChildren(expr) == 1);
456
457 /* expression is convex if child is convex; expression cannot be concave or linear */
459 {
460 *success = TRUE;
462 }
463 else
464 *success = FALSE;
465
466 return SCIP_OKAY;
467}
468
469/** expression monotonicity detection callback */
470static
472{ /*lint --e{715}*/
473 assert(scip != NULL);
474 assert(expr != NULL);
475 assert(result != NULL);
476 assert(childidx == 0);
477
479
480 return SCIP_OKAY;
481}
482
483/** creates the handler for exponential expressions and includes it into SCIP */
508
509/** creates an exponential expression */
511 SCIP* scip, /**< SCIP data structure */
512 SCIP_EXPR** expr, /**< pointer where to store expression */
513 SCIP_EXPR* child, /**< single child */
514 SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), /**< function to call to create ownerdata */
515 void* ownercreatedata /**< data to pass to ownercreate */
516 )
517{
518 assert(expr != NULL);
519 assert(child != NULL);
521
523
524 return SCIP_OKAY;
525}
526
527/** indicates whether expression is of exp-type */ /*lint -e{715}*/
529 SCIP* scip, /**< SCIP data structure */
530 SCIP_EXPR* expr /**< expression */
531 )
532{ /*lint --e{715}*/
533 assert(expr != NULL);
534
536}
#define SCIP_INVALID
Definition def.h:206
#define SCIP_INTERVAL_INFINITY
Definition def.h:208
#define TRUE
Definition def.h:95
#define FALSE
Definition def.h:96
#define REALABS(x)
Definition def.h:210
#define SCIP_CALL(x)
Definition def.h:388
#define EXPRHDLR_HASHKEY
Definition expr_exp.c:46
static void addExpSecant(SCIP *scip, SCIP_Real lb, SCIP_Real ub, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
Definition expr_exp.c:58
#define EXPRHDLR_NAME
Definition expr_exp.c:43
#define EXPRHDLR_DESC
Definition expr_exp.c:44
#define EXPRHDLR_PRECEDENCE
Definition expr_exp.c:45
static void addExpLinearization(SCIP *scip, SCIP_Real refpoint, SCIP_Bool isint, SCIP_Real *lincoef, SCIP_Real *linconstant, SCIP_Bool *success)
Definition expr_exp.c:109
exponential expression handler
constant value expression handler
SCIP_Bool SCIPisExprExp(SCIP *scip, SCIP_EXPR *expr)
Definition expr_exp.c:528
SCIP_RETCODE SCIPcreateExprExp(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPR *child, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition expr_exp.c:510
SCIP_RETCODE SCIPcreateExprValue(SCIP *scip, SCIP_EXPR **expr, SCIP_Real value, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition expr_value.c:270
SCIP_RETCODE SCIPincludeExprhdlrExp(SCIP *scip)
Definition expr_exp.c:484
const char * SCIPexprhdlrGetName(SCIP_EXPRHDLR *exprhdlr)
Definition expr.c:532
void SCIPexprhdlrSetCurvature(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:416
void SCIPexprhdlrSetParse(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:405
void SCIPexprhdlrSetIntEval(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:486
void SCIPexprhdlrSetMonotonicity(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:427
void SCIPexprhdlrSetReverseProp(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:508
void SCIPexprhdlrSetHash(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:449
SCIP_RETCODE SCIPincludeExprhdlr(SCIP *scip, SCIP_EXPRHDLR **exprhdlr, const char *name, const char *desc, unsigned int precedence, SCIP_DECL_EXPREVAL((*eval)), SCIP_EXPRHDLRDATA *data)
Definition scip_expr.c:814
void SCIPexprhdlrSetSimplify(SCIP_EXPRHDLR *exprhdlr,)
Definition expr.c:497
void SCIPexprhdlrSetDiff(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRBWDIFF((*bwdiff)), SCIP_DECL_EXPRFWDIFF((*fwdiff)),)
Definition expr.c:471
void SCIPexprhdlrSetCopyFreeHdlr(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYHDLR((*copyhdlr)),)
Definition expr.c:368
SCIP_EXPRHDLR * SCIPfindExprhdlr(SCIP *scip, const char *name)
Definition scip_expr.c:859
void SCIPexprhdlrSetCopyFreeData(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRCOPYDATA((*copydata)),)
Definition expr.c:381
void SCIPexprhdlrSetEstimate(SCIP_EXPRHDLR *exprhdlr, SCIP_DECL_EXPRINITESTIMATES((*initestimates)),)
Definition expr.c:519
SCIP_RETCODE SCIPcreateExpr(SCIP *scip, SCIP_EXPR **expr, SCIP_EXPRHDLR *exprhdlr, SCIP_EXPRDATA *exprdata, int nchildren, SCIP_EXPR **children, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition scip_expr.c:964
void SCIPexprSetData(SCIP_EXPR *expr, SCIP_EXPRDATA *exprdata)
Definition expr.c:3849
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition expr.c:3801
SCIP_Bool SCIPexprIsIntegral(SCIP_EXPR *expr)
Definition expr.c:4020
SCIP_Bool SCIPisExprValue(SCIP *scip, SCIP_EXPR *expr)
Definition scip_expr.c:1432
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition scip_expr.c:1407
SCIP_EXPRDATA * SCIPexprGetData(SCIP_EXPR *expr)
Definition expr.c:3834
SCIP_RETCODE SCIPparseExpr(SCIP *scip, SCIP_EXPR **expr, const char *exprstr, const char **finalpos, SCIP_DECL_EXPR_OWNERCREATE((*ownercreate)), void *ownercreatedata)
Definition scip_expr.c:1370
SCIP_Real SCIPgetValueExprValue(SCIP_EXPR *expr)
Definition expr_value.c:294
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition expr.c:3875
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition expr.c:3811
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition expr.c:3957
void SCIPcaptureExpr(SCIP_EXPR *expr)
Definition scip_expr.c:1399
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition expr.c:3824
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalLog(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
void SCIPintervalExp(SCIP_Real infinity, SCIP_INTERVAL *resultant, SCIP_INTERVAL operand)
void SCIPintervalSetEmpty(SCIP_INTERVAL *resultant)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
return SCIP_OKAY
assert(minobj< SCIPgetCutoffbound(scip))
#define NULL
Definition lpi_spx1.cpp:161
#define MAX(x, y)
Definition tclique_def.h:92
#define SCIP_DECL_EXPR_OWNERCREATE(x)
Definition type_expr.h:140
#define SCIP_DECL_EXPRREVERSEPROP(x)
Definition type_expr.h:654
#define SCIP_DECL_EXPRINITESTIMATES(x)
Definition type_expr.h:605
#define SCIP_DECL_EXPRCURVATURE(x)
Definition type_expr.h:337
#define SCIP_DECL_EXPRFREEDATA(x)
Definition type_expr.h:265
@ SCIP_EXPRCURV_CONVEX
Definition type_expr.h:60
#define SCIP_DECL_EXPRPARSE(x)
Definition type_expr.h:309
#define SCIP_DECL_EXPRBWDIFF(x)
Definition type_expr.h:446
#define SCIP_DECL_EXPRINTEVAL(x)
Definition type_expr.h:536
#define SCIP_DECL_EXPRMONOTONICITY(x)
Definition type_expr.h:355
@ SCIP_MONOTONE_INC
Definition type_expr.h:69
#define SCIP_DECL_EXPRSIMPLIFY(x)
Definition type_expr.h:629
#define SCIP_DECL_EXPREVAL(x)
Definition type_expr.h:423
#define SCIP_DECL_EXPRHASH(x)
Definition type_expr.h:388
#define SCIP_DECL_EXPRCOPYHDLR(x)
Definition type_expr.h:207
#define SCIP_DECL_EXPRCOPYDATA(x)
Definition type_expr.h:246
#define SCIP_DECL_EXPRESTIMATE(x)
Definition type_expr.h:572
enum SCIP_Retcode SCIP_RETCODE