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