Scippy

SCIP

Solving Constraint Integer Programs

nlhdlr_default.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file nlhdlr_default.c
26 * @ingroup DEFPLUGINS_NLHDLR
27 * @brief default nonlinear handler that calls expression handler methods
28 * @author Stefan Vigerske
29 */
30
31#include <string.h>
32
33#include "scip/nlhdlr_default.h"
34#include "scip/pub_nlhdlr.h"
35#include "scip/cons_nonlinear.h"
36
37/* fundamental nonlinear handler properties */
38#define NLHDLR_NAME "default"
39#define NLHDLR_DESC "default handler for expressions"
40#define NLHDLR_DETECTPRIORITY 0
41#define NLHDLR_ENFOPRIORITY 0
42
43/** translate from one value of infinity to another
44 *
45 * if val is &ge; infty1, then give infty2, else give val
46 */
47#define infty2infty(infty1, infty2, val) ((val) >= (infty1) ? (infty2) : (val))
48
49#define UNDERESTIMATEUSESACTIVITY 0x1u /**< whether underestimation uses activity */
50#define OVERESTIMATEUSESACTIVITY 0x2u /**< whether overestimation uses activity */
51
52/*lint -e666*/
53/*lint -e850*/
54
55/** evaluates an expression w.r.t. the values in the auxiliary variables */
56static
58 SCIP* scip, /**< SCIP data structure */
59 SCIP_EXPR* expr, /**< expression to be evaluated */
60 SCIP_Real* val, /**< buffer to store value of expression */
61 SCIP_SOL* sol /**< solution to be evaluated */
62 )
63{
64 SCIP_Real* childvals;
65 SCIP_VAR* childvar;
66 int c;
67
68 assert(scip != NULL);
69 assert(expr != NULL);
70 assert(val != NULL);
71 assert(SCIPexprGetNChildren(expr) > 0);
72
74
75 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
76 {
78 /* there should be an auxiliary variable, because we created them in detect for every child if we said that we will separate;
79 * at the moment, EVALAUX should only be called for nlhdlrs that said they will separate
80 * if that changes, then we should handle this here, e.g., via *val = SCIPexprGetEvalValue(expr); break;
81 */
82 assert(childvar != NULL);
83
84 childvals[c] = SCIPgetSolVal(scip, sol, childvar);
85 }
86
87 SCIP_CALL( SCIPcallExprEval(scip, expr, childvals, val) );
88
89 SCIPfreeBufferArray(scip, &childvals);
90
91 return SCIP_OKAY;
92}
93
94/** check whether expression should be handled by the default nlhdlr
95 *
96 * if no nlhdlr so far provides enforcement or boundtightening for expr, then the default nlhdlr takes over
97 */
98static
99SCIP_DECL_NLHDLRDETECT(nlhdlrDetectDefault)
100{ /*lint --e{715}*/
101 SCIP_EXPRHDLR* exprhdlr;
102 SCIP_Bool estimatebelowusesactivity = FALSE;
103 SCIP_Bool estimateaboveusesactivity = FALSE;
104 int c;
105
106 assert(scip != NULL);
107 assert(nlhdlr != NULL);
108 assert(expr != NULL);
109 assert(enforcing != NULL);
110 assert(participating != NULL);
111 assert(nlhdlrexprdata != NULL);
112
113 exprhdlr = SCIPexprGetHdlr(expr);
114 assert(exprhdlr != NULL);
115
116 if( (*enforcing & SCIP_NLHDLR_METHOD_ACTIVITY) == 0 )
117 {
118 /* expr handlers having reverseprop but no inteval is something that we don't support at the moment for simplicity */
119 assert(!SCIPexprhdlrHasReverseProp(exprhdlr) || SCIPexprhdlrHasIntEval(exprhdlr));
120
121 /* participate in inteval and/or reverseprop if that is not yet provided in enforcing and we have inteval */
122 if( SCIPexprhdlrHasIntEval(exprhdlr) )
123 *participating = SCIP_NLHDLR_METHOD_ACTIVITY;
124 }
125
126 /* participate in sepa if exprhdlr for expr has an estimate callback and sepa below or above is still missing */
128 {
129 /* communicate back that the nlhdlr will provide the separation on the currently missing sides */
130 if( (*enforcing & SCIP_NLHDLR_METHOD_SEPABELOW) == 0 )
131 *participating |= SCIP_NLHDLR_METHOD_SEPABELOW;
132
133 if( (*enforcing & SCIP_NLHDLR_METHOD_SEPAABOVE) == 0 )
134 *participating |= SCIP_NLHDLR_METHOD_SEPAABOVE;
135 }
136
137 if( !*participating )
138 return SCIP_OKAY;
139
140 /* since this is the default handler, we enforce where we participate */
141 *enforcing |= *participating;
142
143 /* increment activity usage counter and create auxiliary variables if necessary
144 * if separating, first guess whether we will use activities in estimate (distinguish under- and overestimation)
145 * we assume that the exprhdlr will use activity on all children iff we are estimating on a nonconvex side
146 * TODO it would be better to request this information directly from the exprhdlr than inferring it from curvature,
147 * but with the currently available exprhdlr that wouldn't make a difference
148 */
149 if( *participating & SCIP_NLHDLR_METHOD_SEPABOTH )
150 {
151 SCIP_EXPRCURV* childcurv;
152
153 /* allocate memory to store the required curvature of the children (though we don't use it) */
155
156 if( *participating & SCIP_NLHDLR_METHOD_SEPABELOW )
157 {
158 /* check whether the expression is convex */
159 SCIP_Bool isconvex;
160 SCIP_CALL( SCIPcallExprCurvature(scip, expr, SCIP_EXPRCURV_CONVEX, &isconvex, childcurv) );
161 estimatebelowusesactivity = !isconvex;
162 }
163
164 if( *participating & SCIP_NLHDLR_METHOD_SEPAABOVE )
165 {
166 /* check whether the expression is concave */
167 SCIP_Bool isconcave;
168 SCIP_CALL( SCIPcallExprCurvature(scip, expr, SCIP_EXPRCURV_CONCAVE, &isconcave, childcurv) );
169 estimateaboveusesactivity = !isconcave;
170 }
171
172 /* free memory */
173 SCIPfreeBufferArray(scip, &childcurv);
174 }
175
176 /* indicate enforcement methods required in children:
177 * - if separating, make sure that (auxiliary) variable will exist
178 * - if activity computation, then register activity usage
179 * - if estimating on a non-convex side, then indicate activity usage for separation for that side
180 */
181 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
182 {
183 /* todo skip auxvarusage for value-expressions? would then need update in evalExprInAux, too */
185 *participating & SCIP_NLHDLR_METHOD_SEPABOTH,
186 *participating & SCIP_NLHDLR_METHOD_ACTIVITY, estimatebelowusesactivity, estimateaboveusesactivity) );
187 }
188
189 /* remember estimatebelowusesactivity and estimateaboveusesactivity in nlhdlrexprdata */
190 *nlhdlrexprdata = (SCIP_NLHDLREXPRDATA*)(size_t)((estimatebelowusesactivity ? UNDERESTIMATEUSESACTIVITY : 0x0u)
191 | (estimateaboveusesactivity ? OVERESTIMATEUSESACTIVITY : 0x0u));
192
193 return SCIP_OKAY;
194}
195
196/** evaluate expression w.r.t. values of auxiliary variables in children */
197static
198SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalAuxDefault)
199{ /*lint --e{715}*/
200 assert(expr != NULL);
201 assert(auxvalue != NULL);
202
203 SCIP_CALL( evalExprInAux(scip, expr, auxvalue, sol) );
204
205 return SCIP_OKAY;
206}
207
208/** initialize LP relaxation by initial estimators */
209static
210SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaDefault)
211{ /*lint --e{715}*/
212 SCIP_INTERVAL* childrenbounds;
215 SCIP_VAR* auxvar;
216 SCIP_ROWPREP* rowprep;
217 int nreturned;
218 int i, j;
219
220 assert(scip != NULL);
221 assert(expr != NULL);
222 assert(infeasible != NULL);
223
224 *infeasible = FALSE;
225
227 return SCIP_OKAY;
228
229 SCIPdebug( SCIPinfoMessage(scip, NULL, "initsepa exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) );
230 SCIPdebug( SCIPprintExpr(scip, expr, NULL) );
232
233 /* use global bounds of auxvar as global valid bounds for children
234 * if at root node (thus local=global) and estimate actually uses bounds, then intersect with (local) activity of expression
235 */
236 SCIP_CALL( SCIPallocBufferArray(scip, &childrenbounds, SCIPexprGetNChildren(expr)) );
237 for( i = 0; i < SCIPexprGetNChildren(expr); ++i )
238 {
240 assert(auxvar != NULL);
241
242 SCIPintervalSetBounds(&childrenbounds[i],
245
246 if( SCIPgetDepth(scip) == 0 &&
247 ((underestimate && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY)) ||
248 (overestimate && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY ))) )
249 {
251 SCIPintervalIntersect(&childrenbounds[i], childrenbounds[i], SCIPexprGetActivity(SCIPexprGetChildren(expr)[i]));
252 }
253
254 if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, childrenbounds[i]) )
255 {
256 SCIPdebugMsg(scip, "activity for expression %d (unexpectedly) empty in initsepa\n", i);
257 *infeasible = TRUE;
258 SCIPfreeBufferArray(scip, &childrenbounds);
259 return SCIP_OKAY;
260 }
261 }
262
263 /* allocate each coefficients array */
264 for( i = 0; i < SCIP_EXPR_MAXINITESTIMATES; ++i )
265 {
267 }
268
269 /* create rowprep */
272
273 /* call the separation initialization callback of the expression handler and turn estimates into SCIP rows */
274 for( i = 0; i < 2 && !*infeasible; ++i )
275 {
276 nreturned = 0;
277 if( i == 0 && underestimate )
278 {
279 SCIP_CALL( SCIPcallExprInitestimates(scip, expr, childrenbounds, FALSE, coefs, constant, &nreturned) );
281 }
282 if( i == 1 && overestimate )
283 {
284 SCIP_CALL( SCIPcallExprInitestimates(scip, expr, childrenbounds, TRUE, coefs, constant, &nreturned) );
286 }
287
288 for( j = 0; j < nreturned && !*infeasible; ++j )
289 {
290 SCIP_Bool success;
291 int v;
292
293 SCIProwprepReset(rowprep);
294
295 for( v = 0; v < SCIPexprGetNChildren(expr); ++v )
296 {
298 }
300 SCIProwprepAddConstant(rowprep, constant[j]); /*lint !e644*/
301
302 /* special treatment for sums to get equality rows */
303 if( j == 0 && SCIPisExprSum(scip, expr) )
304 {
305 SCIP_Real scalefactor;
306 SCIP_ROW* row;
307
308 /* improve numerics by scaling only (does not relax inequality) */
309 scalefactor = SCIPscaleupRowprep(scip, rowprep, 1.0, &success);
310 if( success && scalefactor == 1.0 && underestimate && overestimate )
311 {
312 /* if the rowprep didn't have to be changed, then turn it into a row, change this to an equality, and add it to the LP */
313 /* TODO do this also if not actually needing both under- and overestimator (should still be valid, but also stronger?) */
314 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "initestimate_sum%d", j);
315
316 SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) );
317
318 /* since we did not relax the estimator, we can turn the row into an equality */
320 {
322 }
323 else
324 {
326 }
327 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
328
329 SCIPdebug( SCIPinfoMessage(scip, NULL, " added %scut ", *infeasible ? "infeasible " : "") );
331
332 SCIP_CALL( SCIPreleaseRow(scip, &row) );
333
334 i = 2; /* to break outside loop on i, too */
335 break;
336 }
337 }
338
339 /* straighten out numerics */
341
342 /* if cleanup removed all but one variable, then the cut is essentially a bound; we can skip this and rely on boundtightening */
343 if( success && SCIProwprepGetNVars(rowprep) > 1 )
344 {
345 /* add the cut */
346 SCIP_ROW* row;
347
348 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "init%sestimate%d_%s",
349 i == 0 ? "under" : "over", j, SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)));
350
351 SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) );
352 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
353
354 SCIPdebug( SCIPinfoMessage(scip, NULL, " added %scut ", *infeasible ? "infeasible " : "") );
356
357 SCIP_CALL( SCIPreleaseRow(scip, &row) );
358 }
359 }
360 }
361
362 SCIPfreeRowprep(scip, &rowprep);
363
364 for( i = SCIP_EXPR_MAXINITESTIMATES-1; i >= 0; --i )
365 {
366 SCIPfreeBufferArray(scip, &coefs[i]);
367 }
368
369 SCIPfreeBufferArray(scip, &childrenbounds);
370
371 return SCIP_OKAY;
372}
373
374/** compute linear estimator */
375static
376SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateDefault)
377{ /*lint --e{715}*/
378 SCIP_Real constant;
379 SCIP_Bool local;
380 SCIP_Bool* branchcand = NULL;
381 int nchildren;
382 int c;
383 SCIP_INTERVAL* localbounds;
384 SCIP_INTERVAL* globalbounds;
385 SCIP_Real* refpoint;
386 SCIP_ROWPREP* rowprep;
387 SCIP_VAR* auxvar;
388
389 assert(scip != NULL);
390 assert(expr != NULL);
391 assert(rowpreps != NULL);
392 assert(success != NULL);
393
394 *addedbranchscores = FALSE;
395
396 nchildren = SCIPexprGetNChildren(expr);
397
398 SCIP_CALL( SCIPallocBufferArray(scip, &localbounds, nchildren) );
399 SCIP_CALL( SCIPallocBufferArray(scip, &globalbounds, nchildren) );
400 SCIP_CALL( SCIPallocBufferArray(scip, &refpoint, nchildren) );
401 /* we need to pass a branchcand array to exprhdlr's estimate also if not asked to add branching scores */
402 SCIP_CALL( SCIPallocBufferArray(scip, &branchcand, nchildren) );
403
404 SCIPdebug( SCIPinfoMessage(scip, NULL, "estimate exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) );
405 SCIPdebug( SCIPprintExpr(scip, expr, NULL) );
407
408 for( c = 0; c < nchildren; ++c )
409 {
411 assert(auxvar != NULL);
412
413 SCIPintervalSetBounds(&localbounds[c],
416
417 if( ((size_t)nlhdlrexprdata & (overestimate ? OVERESTIMATEUSESACTIVITY : UNDERESTIMATEUSESACTIVITY)) )
418 {
419 /* if expr estimate uses bounds, then intersect the auxvar bounds with the current activity, in case the latter is a bit tighter */
421 SCIPintervalIntersectEps(&localbounds[c], SCIPepsilon(scip), localbounds[c], SCIPexprGetActivity(SCIPexprGetChildren(expr)[c]));
422
423 if( SCIPintervalIsEmpty(SCIP_INTERVAL_INFINITY, localbounds[c]) )
424 {
425 *success = FALSE;
426 goto TERMINATE;
427 }
428 }
429 else
430 {
431 /* if we think that expr estimate wouldn't use bounds, then just set something valid */
432 }
433
434 SCIPintervalSetBounds(&globalbounds[c],
437
438 refpoint[c] = SCIPgetSolVal(scip, sol, auxvar);
439
440 branchcand[c] = TRUE;
441 }
442
444
445 /* make sure enough space is available in rowprep arrays */
446 SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nchildren) );
447
448 /* call the estimation callback of the expression handler */
449 SCIP_CALL( SCIPcallExprEstimate(scip, expr, localbounds, globalbounds, refpoint, overestimate, targetvalue,
450 SCIProwprepGetCoefs(rowprep), &constant, &local, success, branchcand) );
451
452 if( *success )
453 {
454 int i;
455
456 SCIProwprepSetLocal(rowprep, local);
457
458 /* add variables to rowprep (coefs were already added by SCIPexprhdlrEstimateExpr) */
459 for( i = 0; i < nchildren; ++i )
460 {
462 SCIProwprepGetCoefs(rowprep)[i]) );
463 }
464
465 SCIProwprepAddConstant(rowprep, constant);
466
467 SCIPdebug( SCIPinfoMessage(scip, NULL, " found rowprep ") );
468 SCIPdebug( SCIPprintRowprepSol(scip, rowprep, sol, NULL) );
469
470 SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, 0, rowprep) );
471
472 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_%s%p_%s%" SCIP_LONGINT_FORMAT,
473 overestimate ? "over" : "under",
475 (void*)expr,
476 sol != NULL ? "sol" : "lp",
478 }
479 else
480 {
481 SCIPfreeRowprep(scip, &rowprep);
482 }
483
484 if( addbranchscores )
485 {
486 SCIP_Real violation;
487
488#ifndef BRSCORE_ABSVIOL
489 SCIP_CALL( SCIPgetExprRelAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
490#else
491 SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, auxvalue, sol, &violation, NULL, NULL) );
492#endif
493 assert(violation > 0.0); /* there should be a violation if we were called to enforce */
494
495 if( nchildren == 1 )
496 {
497 if( branchcand[0] )
498 {
499 SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, SCIPexprGetChildren(expr), 1, violation, sol, addedbranchscores) );
500 }
501 }
502 else
503 {
504 SCIP_EXPR** exprs;
505 int nexprs = 0;
506
507 /* get list of those children that have the branchcand-flag set */
508 SCIP_CALL( SCIPallocBufferArray(scip, &exprs, nchildren) );
509
510 for( c = 0; c < nchildren; ++c )
511 if( branchcand[c] )
512 exprs[nexprs++] = SCIPexprGetChildren(expr)[c];
513
514 SCIP_CALL( SCIPaddExprsViolScoreNonlinear(scip, exprs, nexprs, violation, sol, addedbranchscores) );
515
516 SCIPfreeBufferArray(scip, &exprs);
517 }
518
519 if( *addedbranchscores )
520 {
521 /* count this branchscore as belonging to the exprhdlr, too
522 * thus, it will be counted for the default nlhdlr, but also for this exprhdlr
523 */
525 }
526 }
527
528TERMINATE:
529 SCIPfreeBufferArray(scip, &branchcand);
530 SCIPfreeBufferArray(scip, &refpoint);
531 SCIPfreeBufferArray(scip, &globalbounds);
532 SCIPfreeBufferArray(scip, &localbounds);
533
534 return SCIP_OKAY;
535}
536
537/** solution linearization callback */
538static
539SCIP_DECL_NLHDLRSOLLINEARIZE(nlhdlrSollinearizeDefault)
540{ /*lint --e{715}*/
541 SCIP_Real constant;
542 SCIP_Bool local;
543 SCIP_Bool* branchcand = NULL;
544 int nchildren;
545 int c;
546 int rnd;
547 SCIP_INTERVAL* bounds;
548 SCIP_Real* refpoint;
549 SCIP_VAR* auxvar;
550
551 assert(scip != NULL);
552 assert(expr != NULL);
553
554 SCIPdebug( SCIPinfoMessage(scip, NULL, "sollinearize exprhdlr %s for expr ", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr))) );
555 SCIPdebug( SCIPprintExpr(scip, expr, NULL) );
557
558 nchildren = SCIPexprGetNChildren(expr);
559
560 if( !overestimate && !underestimate )
561 return SCIP_OKAY;
562
563 /* skip on sum, as the estimator doesn't depend on the reference point (expr is linear in auxvars) */
564 if( SCIPisExprSum(scip, expr) )
565 return SCIP_OKAY;
566
567 /* if expr estimate would use bounds, then the function is very likely not convex (w.r.t. global bounds), so skip */
568 if( (overestimate && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY)) &&
569 (underestimate && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY)) )
570 return SCIP_OKAY;
571
572 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nchildren) );
573 SCIP_CALL( SCIPallocBufferArray(scip, &refpoint, nchildren) );
574 /* we need to pass a branchcand array to exprhdlr's estimate also if not asked to add branching scores */
575 SCIP_CALL( SCIPallocBufferArray(scip, &branchcand, nchildren) );
576
577 for( c = 0; c < nchildren; ++c )
578 {
580 assert(auxvar != NULL);
581
582 SCIPintervalSetBounds(&bounds[c],
585
586 refpoint[c] = SCIPgetSolVal(scip, sol, auxvar);
587 }
588
589 for( rnd = (overestimate ? 0 : 1); rnd < (underestimate ? 2 : 1); ++rnd ) /* rnd == 0: overestimate, rnd == 1: underestimate */
590 {
591 SCIP_ROWPREP* rowprep;
592 SCIP_Bool success = FALSE;
593
594 if( rnd == 0 && ((size_t)nlhdlrexprdata & OVERESTIMATEUSESACTIVITY) )
595 continue;
596 if( rnd == 1 && ((size_t)nlhdlrexprdata & UNDERESTIMATEUSESACTIVITY) )
597 continue;
598
600
601 /* make sure enough space is available in rowprep arrays */
602 SCIP_CALL( SCIPensureRowprepSize(scip, rowprep, nchildren + 1) );
603
604 for( c = 0; c < nchildren; ++c )
605 branchcand[c] = TRUE;
606
607 /* call the estimation callback of the expression handler
608 * since we pass the global bounds as local bounds, too, we can ignore whether resulting estimator is marked as local
609 */
610 SCIP_CALL( SCIPcallExprEstimate(scip, expr, bounds, bounds, refpoint, rnd == 0,
611 rnd == 0 ? SCIPinfinity(scip) : -SCIPinfinity(scip),
612 SCIProwprepGetCoefs(rowprep), &constant, &local, &success, branchcand) );
613
614 if( success )
615 {
616 int i;
617
618 /* add variables to rowprep (coefs were already added by SCIPexprhdlrEstimateExpr) */
619 for( i = 0; i < nchildren; ++i )
620 {
622 SCIProwprepGetCoefs(rowprep)[i]) );
623 }
624
625 SCIProwprepAddConstant(rowprep, constant);
626
627 SCIPdebug( SCIPinfoMessage(scip, NULL, " found rowprep ") );
628 SCIPdebug( SCIPprintRowprepSol(scip, rowprep, sol, NULL) );
629
630 (void) SCIPsnprintf(SCIProwprepGetName(rowprep), SCIP_MAXSTRLEN, "%sestimate_%s%p_sol%dnotify",
631 rnd == 0 ? "over" : "under", SCIPexprhdlrGetName(SCIPexprGetHdlr(expr)), (void*)expr, SCIPsolGetIndex(sol));
632
633 /* complete estimator to cut and clean it up */
635 SCIP_CALL( SCIPcleanupRowprep2(scip, rowprep, sol, SCIPgetHugeValue(scip), &success) );
636 }
637
638 /* if cleanup succeeded and rowprep is still global, add to cutpool */
639 if( success && !SCIProwprepIsLocal(rowprep) )
640 {
641 SCIP_ROW* row;
642
643 SCIP_CALL( SCIPgetRowprepRowCons(scip, &row, rowprep, cons) );
645 SCIP_CALL( SCIPreleaseRow(scip, &row) );
646 }
647
648 SCIPfreeRowprep(scip, &rowprep);
649 }
650
651 SCIPfreeBufferArray(scip, &branchcand);
652 SCIPfreeBufferArray(scip, &refpoint);
653 SCIPfreeBufferArray(scip, &bounds);
654
655 return SCIP_OKAY;
656}
657
658/** interval-evaluate expression w.r.t. activity of children */
659static
660SCIP_DECL_NLHDLRINTEVAL(nlhdlrIntevalDefault)
661{ /*lint --e{715}*/
662 assert(scip != NULL);
663 assert(expr != NULL);
664
665 /* call the interval evaluation callback of the expression handler */
666 SCIP_CALL( SCIPcallExprInteval(scip, expr, interval, intevalvar, intevalvardata) );
667
668 return SCIP_OKAY;
669}
670
671/** tighten bounds on children from bounds on expression and bounds on children */
672static
673SCIP_DECL_NLHDLRREVERSEPROP(nlhdlrReversepropDefault)
674{ /*lint --e{715}*/
675 SCIP_INTERVAL* childrenbounds;
676 int c;
677
678 assert(scip != NULL);
679 assert(expr != NULL);
680 assert(infeasible != NULL);
681 assert(nreductions != NULL);
682
683 *nreductions = 0;
684
685 SCIP_CALL( SCIPallocBufferArray(scip, &childrenbounds, SCIPexprGetNChildren(expr)) );
686 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
687 childrenbounds[c] = SCIPgetExprBoundsNonlinear(scip, SCIPexprGetChildren(expr)[c]);
688
689 /* call the reverse propagation callback of the expression handler */
690 SCIP_CALL( SCIPcallExprReverseprop(scip, expr, bounds, childrenbounds, infeasible) );
691
692 if( !*infeasible )
693 {
694 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
695 {
697 infeasible, nreductions) );
698 }
700 }
701
702 SCIPfreeBufferArray(scip, &childrenbounds);
703
704 return SCIP_OKAY;
705}
706
707/** nonlinear handler copy callback */
708static
709SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrDefault)
710{ /*lint --e{715}*/
711 assert(targetscip != NULL);
712 assert(sourcenlhdlr != NULL);
713 assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), NLHDLR_NAME) == 0);
714
715 SCIP_CALL( SCIPincludeNlhdlrDefault(targetscip) );
716
717 return SCIP_OKAY;
718}
719
720/** callback to free expression specific data */
721static
722SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataDefault)
723{ /*lint --e{715}*/
724 assert(nlhdlrexprdata != NULL);
725
726 *nlhdlrexprdata = NULL;
727
728 return SCIP_OKAY;
729}
730
731/** includes default nonlinear handler in nonlinear constraint handler */
733 SCIP* scip /**< SCIP data structure */
734 )
735{
736 SCIP_NLHDLR* nlhdlr;
737
738 assert(scip != NULL);
739
741 NLHDLR_ENFOPRIORITY, nlhdlrDetectDefault, nlhdlrEvalAuxDefault, NULL) );
742 assert(nlhdlr != NULL);
743
744 SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrDefault);
745 SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrFreeExprDataDefault);
746 SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaDefault, NULL, nlhdlrEstimateDefault, NULL);
747 SCIPnlhdlrSetSollinearize(nlhdlr, nlhdlrSollinearizeDefault);
748 SCIPnlhdlrSetProp(nlhdlr, nlhdlrIntevalDefault, nlhdlrReversepropDefault);
749
750 return SCIP_OKAY;
751}
constraint handler for nonlinear constraints specified by algebraic expressions
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Longint
Definition: def.h:158
#define SCIP_INTERVAL_INFINITY
Definition: def.h:195
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_LONGINT_FORMAT
Definition: def.h:165
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPgetExprRelAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPtightenExprIntervalNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_INTERVAL newbounds, SCIP_Bool *cutoff, int *ntightenings)
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_INTERVAL SCIPgetExprBoundsNonlinear(SCIP *scip, SCIP_EXPR *expr)
SCIP_RETCODE SCIPgetExprAbsAuxViolationNonlinear(SCIP *scip, SCIP_EXPR *expr, SCIP_Real auxvalue, SCIP_SOL *sol, SCIP_Real *viol, SCIP_Bool *violunder, SCIP_Bool *violover)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeNlhdlrDefault(SCIP *scip)
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
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:545
void SCIPexprhdlrIncrementNDomainReductions(SCIP_EXPRHDLR *exprhdlr, int nreductions)
Definition: expr.c:771
void SCIPexprhdlrIncrementNBranchings(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:817
SCIP_Bool SCIPexprhdlrHasReverseProp(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:675
SCIP_Bool SCIPexprhdlrHasInitEstimates(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:635
SCIP_Bool SCIPexprhdlrHasEstimate(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:625
SCIP_Bool SCIPexprhdlrHasIntEval(SCIP_EXPRHDLR *exprhdlr)
Definition: expr.c:615
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3860
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1453
SCIP_RETCODE SCIPcallExprEval(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *childrenvalues, SCIP_Real *val)
Definition: scip_expr.c:2185
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1486
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3870
SCIP_INTERVAL SCIPexprGetActivity(SCIP_EXPR *expr)
Definition: expr.c:4016
SCIP_RETCODE SCIPevalExprActivity(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1717
SCIP_EXPRHDLR * SCIPexprGetHdlr(SCIP_EXPR *expr)
Definition: expr.c:3883
void SCIPintervalIntersectEps(SCIP_INTERVAL *resultant, SCIP_Real eps, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
void SCIPintervalIntersect(SCIP_INTERVAL *resultant, SCIP_INTERVAL operand1, SCIP_INTERVAL operand2)
SCIP_Bool SCIPintervalIsEmpty(SCIP_Real infinity, SCIP_INTERVAL operand)
void SCIPintervalSetBounds(SCIP_INTERVAL *resultant, SCIP_Real inf, SCIP_Real sup)
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
void SCIPnlhdlrSetCopyHdlr(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRCOPYHDLR((*copy)))
Definition: nlhdlr.c:76
void SCIPnlhdlrSetFreeExprData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEEXPRDATA((*freeexprdata)))
Definition: nlhdlr.c:98
void SCIPnlhdlrSetProp(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINTEVAL((*inteval)), SCIP_DECL_NLHDLRREVERSEPROP((*reverseprop)))
Definition: nlhdlr.c:123
void SCIPnlhdlrSetSollinearize(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRSOLLINEARIZE((*sollinearize)))
Definition: nlhdlr.c:154
void SCIPnlhdlrSetSepa(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINITSEPA((*initsepa)), SCIP_DECL_NLHDLRENFO((*enfo)), SCIP_DECL_NLHDLRESTIMATE((*estimate)), SCIP_DECL_NLHDLREXITSEPA((*exitsepa)))
Definition: nlhdlr.c:136
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:166
SCIP_RETCODE SCIPincludeNlhdlrNonlinear(SCIP *scip, SCIP_NLHDLR **nlhdlr, const char *name, const char *desc, int detectpriority, int enfopriority, SCIP_DECL_NLHDLRDETECT((*detect)), SCIP_DECL_NLHDLREVALAUX((*evalaux)), SCIP_NLHDLRDATA *nlhdlrdata)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
Definition: lp.c:17292
SCIP_RETCODE SCIPchgRowLhs(SCIP *scip, SCIP_ROW *row, SCIP_Real lhs)
Definition: scip_lp.c:1583
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
Definition: lp.c:17302
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
SCIP_RETCODE SCIPchgRowRhs(SCIP *scip, SCIP_ROW *row, SCIP_Real rhs)
Definition: scip_lp.c:1607
int SCIPsolGetIndex(SCIP_SOL *sol)
Definition: sol.c:2835
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Longint SCIPgetNLPs(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetHugeValue(SCIP *scip)
SCIP_Real SCIPepsilon(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
void SCIProwprepReset(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:719
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)
Definition: misc_rowprep.c:887
SCIP_Real SCIPscaleupRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_Real minscaleup, SCIP_Bool *success)
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:649
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:689
void SCIProwprepSetSidetype(SCIP_ROWPREP *rowprep, SCIP_SIDETYPE sidetype)
Definition: misc_rowprep.c:769
SCIP_Bool SCIProwprepIsLocal(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:679
void SCIPprintRowprepSol(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_SOL *sol, FILE *file)
Definition: misc_rowprep.c:826
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:760
SCIP_SIDETYPE SCIProwprepGetSidetype(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:669
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: misc_rowprep.c:913
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)
Definition: misc_rowprep.c:563
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:629
void SCIProwprepSetLocal(SCIP_ROWPREP *rowprep, SCIP_Bool islocal)
Definition: misc_rowprep.c:780
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:583
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
#define NLHDLR_DETECTPRIORITY
static SCIP_DECL_NLHDLRSOLLINEARIZE(nlhdlrSollinearizeDefault)
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectDefault)
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataDefault)
#define NLHDLR_ENFOPRIORITY
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalAuxDefault)
#define OVERESTIMATEUSESACTIVITY
static SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaDefault)
#define UNDERESTIMATEUSESACTIVITY
#define infty2infty(infty1, infty2, val)
#define NLHDLR_DESC
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrDefault)
#define NLHDLR_NAME
static SCIP_DECL_NLHDLRESTIMATE(nlhdlrEstimateDefault)
static SCIP_DECL_NLHDLRINTEVAL(nlhdlrIntevalDefault)
static SCIP_RETCODE evalExprInAux(SCIP *scip, SCIP_EXPR *expr, SCIP_Real *val, SCIP_SOL *sol)
static SCIP_DECL_NLHDLRREVERSEPROP(nlhdlrReversepropDefault)
default nonlinear handler that calls expression handler methods
#define SCIPdebug(x)
Definition: pub_message.h:93
public functions of nonlinear handlers of nonlinear constraints
SCIP_EXPRCURV
Definition: type_expr.h:61
@ SCIP_EXPRCURV_CONVEX
Definition: type_expr.h:63
@ SCIP_EXPRCURV_CONCAVE
Definition: type_expr.h:64
#define SCIP_EXPR_MAXINITESTIMATES
Definition: type_expr.h:198
@ 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_NLHDLR_METHOD_SEPABOTH
Definition: type_nlhdlr.h:53
#define SCIP_NLHDLR_METHOD_ACTIVITY
Definition: type_nlhdlr.h:54
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
Definition: type_nlhdlr.h:453
#define SCIP_NLHDLR_METHOD_SEPABELOW
Definition: type_nlhdlr.h:51
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63