Scippy

SCIP

Solving Constraint Integer Programs

exprcurv.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 exprcurv.c
26 * @ingroup OTHER_CFILES
27 * @brief functions to work with curvature (convex, concave, etc)
28 * @author Stefan Vigerske
29 *
30 * Declarations are in pub_expr.h
31 */
32
33#include "scip/pub_expr.h"
34#include "scip/pub_message.h"
35
36/** curvature names as strings */
37static
38const char* curvnames[4] =
39 {
40 "unknown",
41 "convex",
42 "concave",
43 "linear"
44 };
45
46#ifdef NDEBUG
47#undef SCIPexprcurvAdd
48#undef SCIPexprcurvNegate
49#undef SCIPexprcurvMultiply
50#endif
51
52/** gives curvature for a sum of two functions with given curvature */
53SCIP_EXPRCURV SCIPexprcurvAdd(
54 SCIP_EXPRCURV curv1, /**< curvature of first summand */
55 SCIP_EXPRCURV curv2 /**< curvature of second summand */
56 )
57{
58 return (SCIP_EXPRCURV) (curv1 & curv2);
59}
60
61/** gives the curvature for the negation of a function with given curvature */
62SCIP_EXPRCURV SCIPexprcurvNegate(
63 SCIP_EXPRCURV curvature /**< curvature of function */
64 )
65{
66 switch( curvature )
67 {
68 case SCIP_EXPRCURV_CONCAVE:
69 return SCIP_EXPRCURV_CONVEX;
70
71 case SCIP_EXPRCURV_CONVEX:
72 return SCIP_EXPRCURV_CONCAVE;
73
74 case SCIP_EXPRCURV_LINEAR:
75 case SCIP_EXPRCURV_UNKNOWN:
76 /* can return curvature, do this below */
77 break;
78
79 default:
80 SCIPerrorMessage("unknown curvature status.\n");
81 SCIPABORT();
82 }
83
84 return curvature;
85}
86
87/** gives curvature for a functions with given curvature multiplied by a constant factor */
88SCIP_EXPRCURV SCIPexprcurvMultiply(
89 SCIP_Real factor, /**< constant factor */
90 SCIP_EXPRCURV curvature /**< curvature of other factor */
91 )
92{
93 if( factor == 0.0 )
94 return SCIP_EXPRCURV_LINEAR;
95 if( factor > 0.0 )
96 return curvature;
97 return SCIPexprcurvNegate(curvature);
98}
99
100/** gives curvature for base^exponent for given bounds and curvature of base-function and constant exponent */
101SCIP_EXPRCURV SCIPexprcurvPower(
102 SCIP_INTERVAL basebounds, /**< bounds on base function */
103 SCIP_EXPRCURV basecurv, /**< curvature of base function */
104 SCIP_Real exponent /**< exponent */
105 )
106{
107 SCIP_Bool expisint;
108
109 assert(basebounds.inf <= basebounds.sup);
110
111 if( exponent == 0.0 )
112 return SCIP_EXPRCURV_LINEAR;
113
114 if( exponent == 1.0 )
115 return basecurv;
116
117 expisint = EPSISINT(exponent, 0.0); /*lint !e835*/
118
119 /* if exponent is fractional, then power is not defined for a negative base
120 * thus, consider only positive part of basebounds
121 */
122 if( !expisint && basebounds.inf < 0.0 )
123 {
124 basebounds.inf = 0.0;
125 if( basebounds.sup < 0.0 )
126 return SCIP_EXPRCURV_LINEAR;
127 }
128
129 /* if basebounds contains 0.0, consider negative and positive interval separately, if possible */
130 if( basebounds.inf < 0.0 && basebounds.sup > 0.0 )
131 {
132 SCIP_INTERVAL leftbounds;
133 SCIP_INTERVAL rightbounds;
134
135 /* something like x^(-2) may look convex on each side of zero, but is not convex on the whole interval
136 * due to the singularity at 0.0 */
137 if( exponent < 0.0 )
138 return SCIP_EXPRCURV_UNKNOWN;
139
140 SCIPintervalSetBounds(&leftbounds, basebounds.inf, 0.0);
141 SCIPintervalSetBounds(&rightbounds, 0.0, basebounds.sup);
142
143 return (SCIP_EXPRCURV) (SCIPexprcurvPower(leftbounds, basecurv, exponent) & SCIPexprcurvPower(rightbounds, basecurv, exponent));
144 }
145 assert(basebounds.inf >= 0.0 || basebounds.sup <= 0.0);
146
147 /* (base^exponent)'' = exponent * ( (exponent-1) base^(exponent-2) (base')^2 + base^(exponent-1) base'' )
148 *
149 * if base'' is positive, i.e., base is convex, then
150 * - for base > 0.0 and exponent > 1.0, the second deriv. is positive -> convex
151 * - for base < 0.0 and exponent > 1.0, we can't say (first and second summand opposite signs)
152 * - for base > 0.0 and 0.0 < exponent < 1.0, we can't say (first sommand negative, second summand positive)
153 * - for base > 0.0 and exponent < 0.0, we can't say (first and second summand opposite signs)
154 * - for base < 0.0 and exponent < 0.0 and even, the second deriv. is positive -> convex
155 * - for base < 0.0 and exponent < 0.0 and odd, the second deriv. is negative -> concave
156 *
157 * if base'' is negative, i.e., base is concave, then
158 * - for base > 0.0 and exponent > 1.0, we can't say (first summand positive, second summand negative)
159 * - for base < 0.0 and exponent > 1.0 and even, the second deriv. is positive -> convex
160 * - for base < 0.0 and exponent > 1.0 and odd, the second deriv. is negative -> concave
161 * - for base > 0.0 and 0.0 < exponent < 1.0, the second deriv. is negative -> concave
162 * - for base > 0.0 and exponent < 0.0, the second deriv. is positive -> convex
163 * - for base < 0.0 and exponent < 0.0, we can't say (first and second summand opposite signs)
164 *
165 * if base'' is zero, i.e., base is linear, then
166 * (base^exponent)'' = exponent * (exponent-1) base^(exponent-2) (base')^2
167 * - just multiply signs
168 */
169
170 if( basecurv == SCIP_EXPRCURV_LINEAR )
171 {
172 SCIP_Real sign;
173
174 /* base^(exponent-2) is negative, if base < 0.0 and exponent is odd */
175 sign = exponent * (exponent - 1.0);
176 assert(basebounds.inf >= 0.0 || expisint);
177 if( basebounds.inf < 0.0 && ((int)exponent)%2 != 0 )
178 sign *= -1.0;
179 assert(sign != 0.0);
180
181 return sign > 0.0 ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE;
182 }
183
184 if( basecurv == SCIP_EXPRCURV_CONVEX )
185 {
186 if( basebounds.sup <= 0.0 && exponent < 0.0 && expisint )
187 return ((int)exponent)%2 == 0 ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE;
188 if( basebounds.inf >= 0.0 && exponent > 1.0 )
189 return SCIP_EXPRCURV_CONVEX ;
190 return SCIP_EXPRCURV_UNKNOWN;
191 }
192
193 if( basecurv == SCIP_EXPRCURV_CONCAVE )
194 {
195 if( basebounds.sup <= 0.0 && exponent > 1.0 && expisint )
196 return ((int)exponent)%2 == 0 ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE;
197 if( basebounds.inf >= 0.0 && exponent < 1.0 )
198 return exponent < 0.0 ? SCIP_EXPRCURV_CONVEX : SCIP_EXPRCURV_CONCAVE;
199 return SCIP_EXPRCURV_UNKNOWN;
200 }
201
202 return SCIP_EXPRCURV_UNKNOWN;
203}
204
205/** gives required curvature for base so that base^exponent has given curvature under given bounds on base and constant exponent
206 *
207 * returns curvature unknown if expected curvature cannot be obtained
208 */
209SCIP_EXPRCURV SCIPexprcurvPowerInv(
210 SCIP_INTERVAL basebounds, /**< bounds on base function */
211 SCIP_Real exponent, /**< exponent, must not be 0 */
212 SCIP_EXPRCURV powercurv /**< expected curvature for power */
213 )
214{
215 SCIP_Bool expisint;
216
217 assert(basebounds.inf <= basebounds.sup);
218 assert(exponent != 0.0);
219 assert(powercurv != SCIP_EXPRCURV_UNKNOWN);
220
221 if( exponent == 1.0 )
222 return powercurv;
223
224 /* power is usually never linear, now that exponent != 1 */
225 if( powercurv == SCIP_EXPRCURV_LINEAR )
226 return SCIP_EXPRCURV_UNKNOWN;
227
228 expisint = EPSISINT(exponent, 0.0); /*lint !e835*/
229
230 /* if exponent is fractional, then power is only defined for a non-negative base
231 * boundtightening should have ensured this before calling this function,
232 * but sometimes this does not work and so we correct this here for us
233 */
234 if( !expisint && basebounds.inf < 0.0 )
235 {
236 basebounds.inf = 0.0;
237 if( basebounds.sup < 0.0 )
238 return SCIP_EXPRCURV_UNKNOWN;
239 }
240
241 /* if basebounds contains 0.0, consider negative and positive interval separately, if possible */
242 if( basebounds.inf < 0.0 && basebounds.sup > 0.0 )
243 {
244 SCIP_INTERVAL leftbounds;
245 SCIP_INTERVAL rightbounds;
246 SCIP_EXPRCURV leftcurv;
247 SCIP_EXPRCURV rightcurv;
248
249 /* something like x^(-2) may look convex on each side of zero, but is not convex on the whole
250 * interval due to the singularity at 0.0 */
251 if( exponent < 0.0 )
252 return SCIP_EXPRCURV_UNKNOWN;
253
254 SCIPintervalSetBounds(&leftbounds, basebounds.inf, 0.0);
255 SCIPintervalSetBounds(&rightbounds, 0.0, basebounds.sup);
256
257 leftcurv = SCIPexprcurvPowerInv(leftbounds, exponent, powercurv);
258 rightcurv = SCIPexprcurvPowerInv(rightbounds, exponent, powercurv);
259
260 /* now need to intersect */
261 if( leftcurv == SCIP_EXPRCURV_LINEAR )
262 return rightcurv;
263 if( rightcurv == SCIP_EXPRCURV_LINEAR )
264 return leftcurv;
265 if( leftcurv == SCIP_EXPRCURV_UNKNOWN || rightcurv == SCIP_EXPRCURV_UNKNOWN )
266 return SCIP_EXPRCURV_UNKNOWN;
267 assert(leftcurv == SCIP_EXPRCURV_CONVEX || leftcurv == SCIP_EXPRCURV_CONCAVE);
268 assert(rightcurv == SCIP_EXPRCURV_CONVEX || rightcurv == SCIP_EXPRCURV_CONCAVE);
269 return SCIP_EXPRCURV_LINEAR;
270 }
271 assert(basebounds.inf >= 0.0 || basebounds.sup <= 0.0);
272
273 /* inverting the logic from SCIPexprcurvPower here */
274 if( powercurv == SCIP_EXPRCURV_CONVEX )
275 {
276 SCIP_Real sign;
277
278 if( basebounds.sup <= 0.0 && exponent < 0.0 && expisint && ((int)exponent)%2 == 0 )
279 return SCIP_EXPRCURV_CONVEX;
280 if( basebounds.inf >= 0.0 && exponent > 1.0 )
281 return SCIP_EXPRCURV_CONVEX;
282 if( basebounds.sup <= 0.0 && exponent > 1.0 && expisint && ((int)exponent)%2 == 0 )
283 return SCIP_EXPRCURV_CONCAVE;
284 if( basebounds.inf >= 0.0 && exponent < 0.0 )
285 return SCIP_EXPRCURV_CONCAVE;
286
287 /* base^(exponent-2) is negative, if base < 0.0 and exponent is odd */
288 sign = exponent * (exponent - 1.0);
289 assert(basebounds.inf >= 0.0 || expisint);
290 if( basebounds.inf < 0.0 && ((int)exponent)%2 != 0 )
291 sign *= -1.0;
292 assert(sign != 0.0);
293
294 if( sign > 0.0 )
295 return SCIP_EXPRCURV_LINEAR;
296 }
297 else
298 {
299 SCIP_Real sign;
300
301 assert(powercurv == SCIP_EXPRCURV_CONCAVE); /* linear handled at top, unknown should not be the case */
302
303 if( basebounds.sup <= 0.0 && exponent < 0.0 && expisint && ((int)exponent)%2 != 0 )
304 return SCIP_EXPRCURV_CONVEX;
305 if( basebounds.sup <= 0.0 && exponent > 1.0 && expisint && ((int)exponent)%2 != 0 )
306 return SCIP_EXPRCURV_CONCAVE;
307 if( basebounds.inf >= 0.0 && exponent < 1.0 && exponent >= 0.0 )
308 return SCIP_EXPRCURV_CONCAVE;
309
310 /* base^(exponent-2) is negative, if base < 0.0 and exponent is odd */
311 sign = exponent * (exponent - 1.0);
312 assert(basebounds.inf >= 0.0 || expisint);
313 if( basebounds.inf < 0.0 && ((int)exponent)%2 != 0 )
314 sign *= -1.0;
315 assert(sign != 0.0);
316
317 if( sign < 0.0 )
318 return SCIP_EXPRCURV_LINEAR;
319 }
320
321 return SCIP_EXPRCURV_UNKNOWN;
322}
323
324/** gives curvature for a monomial with given curvatures and bounds for each factor
325 *
326 * See Maranas and Floudas, Finding All Solutions of Nonlinearly Constrained Systems of Equations, JOGO 7, 1995
327 * for the categorization in the case that all factors are linear.
328 *
329 * Exponents can also be negative or rational.
330 */
331SCIP_EXPRCURV SCIPexprcurvMonomial(
332 int nfactors, /**< number of factors in monomial */
333 SCIP_Real* exponents, /**< exponents in monomial, or NULL if all 1.0 */
334 int* factoridxs, /**< indices of factors (but not exponents), or NULL if identity mapping */
335 SCIP_EXPRCURV* factorcurv, /**< curvature of each factor */
336 SCIP_INTERVAL* factorbounds /**< bounds of each factor */
337 )
338{
339 SCIP_Real mult;
340 SCIP_Real e;
341 SCIP_INTERVAL bounds;
342 SCIP_EXPRCURV curv;
343 SCIP_EXPRCURV fcurv;
344 int nnegative;
345 int npositive;
346 SCIP_Real sum;
347 SCIP_Bool expcurvpos;
348 SCIP_Bool expcurvneg;
349 int j;
350 int f;
351
352 assert(nfactors >= 0);
353 assert(factorcurv != NULL || nfactors == 0);
354 assert(factorbounds != NULL || nfactors == 0);
355
356 if( nfactors == 0 )
357 return SCIP_EXPRCURV_LINEAR;
358
359 if( nfactors == 1 )
360 {
361 f = factoridxs != NULL ? factoridxs[0] : 0;
362 e = exponents != NULL ? exponents[0] : 1.0;
363 /* SCIPdebugMessage("monomial [%g,%g]^%g is %s\n",
364 factorbounds[f].inf, factorbounds[f].sup, e,
365 SCIPexprcurvGetName(SCIPexprcurvPower(factorbounds[f], factorcurv[f], e))); */
366 return SCIPexprcurvPower(factorbounds[f], factorcurv[f], e); /*lint !e613*/
367 }
368
369 mult = 1.0;
370
371 nnegative = 0; /* number of negative exponents */
372 npositive = 0; /* number of positive exponents */
373 sum = 0.0; /* sum of exponents */
374 expcurvpos = TRUE; /* whether exp_j * f_j''(x) >= 0 for all factors (assuming f_j >= 0) */
375 expcurvneg = TRUE; /* whether exp_j * f_j''(x) <= 0 for all factors (assuming f_j >= 0) */
376
377 for( j = 0; j < nfactors; ++j )
378 {
379 f = factoridxs != NULL ? factoridxs[j] : j;
380 if( factorcurv[f] == SCIP_EXPRCURV_UNKNOWN ) /*lint !e613*/
381 return SCIP_EXPRCURV_UNKNOWN;
382
383 e = exponents != NULL ? exponents[j] : 1.0;
384 bounds = factorbounds[f]; /*lint !e613*/
385
386 /* if argument is negative, then exponent should be integer; correct bounds if that doesn't hold */
387 if( !EPSISINT(e, 0.0) && bounds.inf < 0.0 ) /*lint !e835*/
388 {
389 bounds.inf = 0.0;
390 if( bounds.sup < 0.0 )
391 return SCIP_EXPRCURV_UNKNOWN;
392 }
393
394 if( bounds.inf < 0.0 && bounds.sup > 0.0 )
395 return SCIP_EXPRCURV_UNKNOWN;
396
397 if( e < 0.0 )
398 ++nnegative;
399 else
400 ++npositive;
401 sum += e;
402
403 if( bounds.inf < 0.0 )
404 {
405 /* flip j'th argument: (f_j)^(exp_j) = (-1)^(exp_j) (-f_j)^(exp_j) */
406
407 /* -f_j has negated curvature of f_j */
408 fcurv = SCIPexprcurvNegate(factorcurv[f]); /*lint !e613*/
409
410 /* negate monomial, if exponent is odd, i.e., (-1)^(exp_j) = -1 */
411 if( (int)e % 2 != 0 )
412 mult *= -1.0;
413 }
414 else
415 {
416 fcurv = factorcurv[f]; /*lint !e613*/
417 }
418
419 /* check if exp_j * fcurv is convex (>= 0) and/or concave */
420 fcurv = SCIPexprcurvMultiply(e, fcurv);
421 if( !(fcurv & SCIP_EXPRCURV_CONVEX) )
422 expcurvpos = FALSE;
423 if( !(fcurv & SCIP_EXPRCURV_CONCAVE) )
424 expcurvneg = FALSE;
425 }
426
427 /* if all factors are linear, then a product f_j^exp_j with f_j >= 0 is convex if
428 * - all exponents are negative, or
429 * - all except one exponent j* are negative and exp_j* >= 1 - sum_{j!=j*}exp_j, but the latter is equivalent to sum_j exp_j >= 1
430 * further, the product is concave if
431 * - all exponents are positive and the sum of exponents is <= 1.0
432 *
433 * if factors are nonlinear, then we require additionally, that for convexity
434 * - each factor is convex if exp_j >= 0, or concave if exp_j <= 0, i.e., exp_j*f_j'' >= 0
435 * and for concavity, we require that
436 * - all factors are concave, i.e., exp_j*f_j'' <= 0
437 */
438
439 if( nnegative == nfactors && expcurvpos )
440 curv = SCIP_EXPRCURV_CONVEX;
441 else if( nnegative == nfactors-1 && EPSGE(sum, 1.0, 1e-9) && expcurvpos )
442 curv = SCIP_EXPRCURV_CONVEX;
443 else if( npositive == nfactors && EPSLE(sum, 1.0, 1e-9) && expcurvneg )
444 curv = SCIP_EXPRCURV_CONCAVE;
445 else
446 curv = SCIP_EXPRCURV_UNKNOWN;
447 curv = SCIPexprcurvMultiply(mult, curv);
448
449 return curv;
450}
451
452/** for a monomial with given bounds for each factor, gives condition on the curvature of each factor,
453 * so that monomial has a requested curvature, if possible
454 *
455 * @return whether `monomialcurv` can be achieved
456 */
457SCIP_Bool SCIPexprcurvMonomialInv(
458 SCIP_EXPRCURV monomialcurv, /**< desired curvature */
459 int nfactors, /**< number of factors in monomial */
460 SCIP_Real* exponents, /**< exponents in monomial, or NULL if all 1.0 */
461 SCIP_INTERVAL* factorbounds, /**< bounds of each factor */
462 SCIP_EXPRCURV* factorcurv /**< buffer to store required curvature of each factor */
463 )
464{
465 int nnegative;
466 int npositive;
467 SCIP_INTERVAL bounds;
468 SCIP_Real e;
469 SCIP_Real sum;
470 int j;
471
472 assert(monomialcurv != SCIP_EXPRCURV_UNKNOWN);
473 assert(nfactors >= 1);
474 assert(factorbounds != NULL);
475 assert(factorcurv != NULL);
476
477 if( nfactors == 1 )
478 {
479 factorcurv[0] = SCIPexprcurvPowerInv(factorbounds[0], exponents != NULL ? exponents[0] : 1.0, monomialcurv);
480 return factorcurv[0] != SCIP_EXPRCURV_UNKNOWN;
481 }
482
483 /* any decent monomial with at least 2 factors is not linear */
484 if( monomialcurv == SCIP_EXPRCURV_LINEAR )
485 return FALSE;
486
487 /* count positive and negative exponents, sum of exponents; flip negative factors */
488 nnegative = 0; /* number of negative exponents */
489 npositive = 0; /* number of positive exponents */
490 sum = 0.0; /* sum of exponents */
491 for( j = 0; j < nfactors; ++j )
492 {
493 e = exponents != NULL ? exponents[j] : 1.0;
494 assert(e != 0.0); /* should have been simplified away */
495
496 bounds = factorbounds[j];
497
498 /* if argument is negative, then exponent should be integer
499 * if that didn't happen, consider argument as if non-negative
500 */
501 if( !EPSISINT(e, 0.0) && bounds.inf < 0.0 ) /*lint !e835*/
502 {
503 bounds.inf = 0.0;
504 if( bounds.sup < 0.0 )
505 return FALSE;
506 }
507
508 /* mixed signs are bad */
509 if( bounds.inf < 0.0 && bounds.sup > 0.0 )
510 return FALSE;
511
512 if( e < 0.0 )
513 ++nnegative;
514 else
515 ++npositive;
516 sum += e;
517
518 if( bounds.inf < 0.0 )
519 {
520 /* flip j'th argument: (f_j)^(exp_j) = (-1)^(exp_j) (-f_j)^(exp_j)
521 * thus, negate monomial, if exponent is odd, i.e., (-1)^(exp_j) = -1
522 */
523 if( (int)e % 2 != 0 )
524 monomialcurv = SCIPexprcurvNegate(monomialcurv);
525 }
526 }
527
528 /* if all factors are linear, then a product f_j^exp_j with f_j >= 0 is convex if
529 * - all exponents are negative, or
530 * - all except one exponent j* are negative and exp_j* >= 1 - sum_{j!=j*}exp_j, but the latter is equivalent to sum_j exp_j >= 1
531 * further, the product is concave if
532 * - all exponents are positive and the sum of exponents is <= 1.0
533 *
534 * if factors are nonlinear, then we require additionally, that for convexity
535 * - each factor is convex if exp_j >= 0, or concave if exp_j <= 0, i.e., exp_j*f_j'' >= 0
536 * and for concavity, we require that
537 * - all factors are concave, i.e., exp_j*f_j'' <= 0
538 */
539
540 if( monomialcurv == SCIP_EXPRCURV_CONVEX )
541 {
542 if( nnegative < nfactors-1 ) /* at least two positive exponents */
543 return FALSE;
544 if( nnegative < nfactors && !EPSGE(sum, 1.0, 1e-9) ) /* one negative exponent, but sum is not >= 1 */
545 return FALSE;
546
547 /* monomial will be convex, if each factor is convex if exp_j >= 0, or concave if exp_j <= 0, i.e., exp_j*f_j'' >= 0 */
548 for( j = 0; j < nfactors; ++j )
549 {
550 e = exponents != NULL ? exponents[j] : 1.0;
551
552 /* if factor is negative, then factorcurv[j] need to be flipped, which we can also get by flipping e */
553 if( factorbounds[j].inf < 0.0 && EPSISINT(e, 0.0) ) /*lint !e835*/
554 e = -e;
555 if( e >= 0.0 )
556 factorcurv[j] = SCIP_EXPRCURV_CONVEX;
557 else
558 factorcurv[j] = SCIP_EXPRCURV_CONCAVE;
559 }
560 }
561 else
562 {
563 assert(monomialcurv == SCIP_EXPRCURV_CONCAVE);
564 if( npositive < nfactors ) /* at least one negative exponent */
565 return FALSE;
566 if( !EPSLE(sum, 1.0, 1e-9) ) /* sum is not <= 1 */
567 return FALSE;
568
569 /* monomial will be concave, if each factor is concave */
570 for( j = 0; j < nfactors; ++j )
571 {
572 e = exponents != NULL ? exponents[j] : 1.0;
573
574 /* if factor is negative, then factorcurv[j] need to be flipped, i.e. convex */
575 if( factorbounds[j].inf < 0.0 && EPSISINT(e, 0.0) ) /*lint !e835*/
576 factorcurv[j] = SCIP_EXPRCURV_CONVEX;
577 else
578 factorcurv[j] = SCIP_EXPRCURV_CONCAVE;
579 }
580 }
581
582 return TRUE;
583}
584
585/** gives name as string for a curvature */
586const char* SCIPexprcurvGetName(
587 SCIP_EXPRCURV curv /**< curvature */
588 )
589{
590 assert(0 <= curv && curv <= SCIP_EXPRCURV_LINEAR); /*lint !e685 !e2650 !e587 !e831 !e641 !e568*/
591
592 return curvnames[curv];
593}
NULL
#define NULL
Definition: def.h:266
EPSGE
#define EPSGE(x, y, eps)
Definition: def.h:201
EPSISINT
#define EPSISINT(x, eps)
Definition: def.h:209
SCIP_Bool
#define SCIP_Bool
Definition: def.h:91
EPSLE
#define EPSLE(x, y, eps)
Definition: def.h:199
SCIP_Real
#define SCIP_Real
Definition: def.h:172
TRUE
#define TRUE
Definition: def.h:93
FALSE
#define FALSE
Definition: def.h:94
SCIPABORT
#define SCIPABORT()
Definition: def.h:345
curvnames
static const char * curvnames[4]
Definition: exprcurv.c:38
SCIPexprcurvGetName
const char * SCIPexprcurvGetName(SCIP_EXPRCURV curv)
Definition: exprcurv.c:586
SCIPexprcurvMonomial
SCIP_EXPRCURV SCIPexprcurvMonomial(int nfactors, SCIP_Real *exponents, int *factoridxs, SCIP_EXPRCURV *factorcurv, SCIP_INTERVAL *factorbounds)
Definition: exprcurv.c:331
SCIPexprcurvPower
SCIP_EXPRCURV SCIPexprcurvPower(SCIP_INTERVAL basebounds, SCIP_EXPRCURV basecurv, SCIP_Real exponent)
Definition: exprcurv.c:101
SCIPexprcurvPowerInv
SCIP_EXPRCURV SCIPexprcurvPowerInv(SCIP_INTERVAL basebounds, SCIP_Real exponent, SCIP_EXPRCURV powercurv)
Definition: exprcurv.c:209
SCIPexprcurvMonomialInv
SCIP_Bool SCIPexprcurvMonomialInv(SCIP_EXPRCURV monomialcurv, int nfactors, SCIP_Real *exponents, SCIP_INTERVAL *factorbounds, SCIP_EXPRCURV *factorcurv)
Definition: exprcurv.c:457
SCIPexprcurvMultiply
SCIP_EXPRCURV SCIPexprcurvMultiply(SCIP_Real factor, SCIP_EXPRCURV curvature)
Definition: exprcurv.c:88
SCIPexprcurvAdd
SCIP_EXPRCURV SCIPexprcurvAdd(SCIP_EXPRCURV curv1, SCIP_EXPRCURV curv2)
Definition: exprcurv.c:53
SCIPexprcurvNegate
SCIP_EXPRCURV SCIPexprcurvNegate(SCIP_EXPRCURV curvature)
Definition: exprcurv.c:62
SCIPintervalSetBounds
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
Definition: intervalarith.c:433
pub_expr.h
public functions to work with algebraic expressions
pub_message.h
public methods for message output
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_Interval
Definition: intervalarith.h:54
SCIP_Interval::sup
SCIP_Real sup
Definition: intervalarith.h:56
SCIP_Interval::inf
SCIP_Real inf
Definition: intervalarith.h:55
SCIP_EXPRCURV
SCIP_EXPRCURV
Definition: type_expr.h:61
SCIP_EXPRCURV_CONVEX
@ SCIP_EXPRCURV_CONVEX
Definition: type_expr.h:63
SCIP_EXPRCURV_LINEAR
@ SCIP_EXPRCURV_LINEAR
Definition: type_expr.h:65
SCIP_EXPRCURV_UNKNOWN
@ SCIP_EXPRCURV_UNKNOWN
Definition: type_expr.h:62
SCIP_EXPRCURV_CONCAVE
@ SCIP_EXPRCURV_CONCAVE
Definition: type_expr.h:64