Scippy

SCIP

Solving Constraint Integer Programs

nlhdlr_perspective.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_perspective.c
26 * @ingroup DEFPLUGINS_NLHDLR
27 * @brief perspective nonlinear handler
28 * @author Ksenia Bestuzheva
29 */
30
31#include <string.h>
32
34#include "scip/cons_nonlinear.h"
35#include "scip/scip_sol.h"
37#include "scip/nlhdlr.h"
38
39/* fundamental nonlinear handler properties */
40#define NLHDLR_NAME "perspective"
41#define NLHDLR_DESC "perspective handler for expressions"
42#define NLHDLR_DETECTPRIORITY -20 /**< detect last so that to make use of what other handlers detected */
43#define NLHDLR_ENFOPRIORITY 125 /**< enforce first because perspective cuts are always stronger */
44
45#define DEFAULT_MAXPROPROUNDS 1 /**< maximal number of propagation rounds in probing */
46#define DEFAULT_MINDOMREDUCTION 0.1 /**< minimal relative reduction in a variable's domain for applying probing */
47#define DEFAULT_MINVIOLPROBING 1e-05 /**< minimal violation w.r.t. auxiliary variables for applying probing */
48#define DEFAULT_PROBINGONLYINSEPA TRUE /**< whether to do probing only in separation loop */
49#define DEFAULT_PROBINGFREQ 1 /**< probing frequency (-1 - no probing, 0 - root node only) */
50#define DEFAULT_CONVEXONLY FALSE /**< whether perspective cuts are added only for convex expressions */
51#define DEFAULT_TIGHTENBOUNDS TRUE /**< whether variable semicontinuity is used to tighten variable bounds */
52#define DEFAULT_ADJREFPOINT TRUE /**< whether to adjust the reference point if indicator is not 1 */
53
54/*
55 * Data structures
56 */
57
58/** data structure to store information of a semicontinuous variable
59 *
60 * For a variable x (not stored in the struct), this stores the data of nbnds implications
61 * bvars[i] = 0 -> x = vals[i]
62 * bvars[i] = 1 -> lbs[i] <= x <= ubs[i]
63 * where bvars[i] are binary variables.
64 */
65struct SCVarData
66{
67 SCIP_Real* vals0; /**< values of the variable when the corresponding bvars[i] = 0 */
68 SCIP_Real* lbs1; /**< global lower bounds of the variable when the corresponding bvars[i] = 1 */
69 SCIP_Real* ubs1; /**< global upper bounds of the variable when the corresponding bvars[i] = 1 */
70 SCIP_VAR** bvars; /**< the binary variables on which the variable domain depends */
71 int nbnds; /**< number of suitable on/off bounds the var has */
72 int bndssize; /**< size of the arrays */
73};
74typedef struct SCVarData SCVARDATA;
75
76/** nonlinear handler expression data
77 *
78 * For an expression expr (not stored in the struct), this stores the data of nindicators implications
79 * indicators[i] = 0 -> expr = exprvals[0]
80 * where indicators[i] is an indicator (binary) variable, corresponding to some bvars entry in SCVarData.
81 *
82 * Also stores the variables the expression depends on.
83 */
84struct SCIP_NlhdlrExprData
85{
86 SCIP_Real* exprvals0; /**< 'off' values of the expression for each indicator variable */
87 SCIP_VAR** vars; /**< expression variables (both original and auxiliary) */
88 int nvars; /**< total number of variables in the expression */
89 int varssize; /**< size of the vars array */
90 SCIP_VAR** indicators; /**< all indicator variables for the expression */
91 int nindicators; /**< number of indicator variables */
92};
93
94/** nonlinear handler data */
95struct SCIP_NlhdlrData
96{
97 SCIP_HASHMAP* scvars; /**< maps semicontinuous variables to their on/off bounds (SCVarData) */
98
99 /* parameters */
100 int maxproprounds; /**< maximal number of propagation rounds in probing */
101 SCIP_Real mindomreduction; /**< minimal relative reduction in a variable's domain for applying probing */
102 SCIP_Real minviolprobing; /**< minimal violation w.r.t. auxiliary variables for applying probing */
103 SCIP_Bool probingonlyinsepa; /**< whether to do probing only in separation loop */
104 int probingfreq; /**< if and when to do probing */
105 SCIP_Bool convexonly; /**< whether perspective cuts are added only for convex expressions */
106 SCIP_Bool tightenbounds; /**< whether variable semicontinuity is used to tighten variable bounds */
107 SCIP_Bool adjrefpoint; /**< whether to adjust the reference point if indicator is not 1 */
108};
109
110/*
111 * Local methods
112 */
113
114/*
115 * Helper methods for working with nlhdlrExprData
116 */
117
118/** frees nlhdlrexprdata structure */
119static
121 SCIP* scip, /**< SCIP data structure */
122 SCIP_NLHDLREXPRDATA* nlhdlrexprdata /**< nlhdlr expression data */
123 )
124{
125 int v;
126
127 if( nlhdlrexprdata->nindicators != 0 )
128 {
129 assert(nlhdlrexprdata->indicators != NULL);
130 for( v = nlhdlrexprdata->nindicators - 1; v >= 0; --v )
131 {
132 SCIP_CALL( SCIPreleaseVar(scip, &(nlhdlrexprdata->indicators[v])) );
133 }
134 SCIPfreeBlockMemoryArray(scip, &(nlhdlrexprdata->indicators), nlhdlrexprdata->nindicators);
135 SCIPfreeBlockMemoryArrayNull(scip, &(nlhdlrexprdata->exprvals0), nlhdlrexprdata->nindicators);
136 }
137
138 for( v = nlhdlrexprdata->nvars - 1; v >= 0; --v )
139 {
140 SCIP_CALL( SCIPreleaseVar(scip, &(nlhdlrexprdata->vars[v])) );
141 }
142 SCIPfreeBlockMemoryArrayNull(scip, &nlhdlrexprdata->vars, nlhdlrexprdata->varssize);
143
144 return SCIP_OKAY;
145}
146
147/* remove an indicator from nlhdlr expression data */
148static
150 SCIP* scip, /**< SCIP data structure */
151 SCIP_NLHDLREXPRDATA* nlexprdata, /**< nlhdlr expression data */
152 int pos /**< position of the indicator */
153 )
154{
155 int i;
156
157 assert(pos >= 0 && pos < nlexprdata->nindicators);
158
159 SCIP_CALL( SCIPreleaseVar(scip, &nlexprdata->indicators[pos]) );
160 for( i = pos; i < nlexprdata->nindicators - 1; ++i )
161 {
162 nlexprdata->indicators[i] = nlexprdata->indicators[i+1];
163 }
164
165 --nlexprdata->nindicators;
166
167 return SCIP_OKAY;
168}
169
170/** adds an auxiliary variable to the vars array in nlhdlrexprdata */
171static
173 SCIP* scip, /**< SCIP data structure */
174 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
175 SCIP_HASHMAP* auxvarmap, /**< hashmap linking auxvars to positions in nlhdlrexprdata->vars */
176 SCIP_VAR* auxvar /**< variable to be added */
177 )
178{
179 int pos;
180 int newsize;
181
182 assert(nlhdlrexprdata != NULL);
183 assert(auxvar != NULL);
184
185 pos = SCIPhashmapGetImageInt(auxvarmap, (void*) auxvar);
186
187 if( pos != INT_MAX )
188 return SCIP_OKAY;
189
190 /* ensure size */
191 if( nlhdlrexprdata->nvars + 1 > nlhdlrexprdata->varssize )
192 {
193 newsize = SCIPcalcMemGrowSize(scip, nlhdlrexprdata->nvars + 1);
194 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->vars, nlhdlrexprdata->varssize, newsize) );
195 nlhdlrexprdata->varssize = newsize;
196 }
197 assert(nlhdlrexprdata->nvars + 1 <= nlhdlrexprdata->varssize);
198
199 nlhdlrexprdata->vars[nlhdlrexprdata->nvars] = auxvar;
200 SCIP_CALL( SCIPcaptureVar(scip, auxvar) );
201 SCIP_CALL( SCIPhashmapSetImageInt(auxvarmap, (void*) auxvar, nlhdlrexprdata->nvars) );
202 ++(nlhdlrexprdata->nvars);
203
204 return SCIP_OKAY;
205}
206
207/*
208 * Semicontinuous variable methods
209 */
210
211/** adds an indicator to the data of a semicontinuous variable */
212static
214 SCIP* scip, /**< SCIP data structure */
215 SCVARDATA* scvdata, /**< semicontinuous variable data */
216 SCIP_VAR* indicator, /**< indicator to be added */
217 SCIP_Real val0, /**< value of the variable when indicator == 0 */
218 SCIP_Real lb1, /**< lower bound of the variable when indicator == 1 */
219 SCIP_Real ub1 /**< upper bound of the variable when indicator == 1 */
220 )
221{
222 int newsize;
223 int i;
224 SCIP_Bool found;
225 int pos;
226
227 assert(scvdata != NULL);
228 assert(indicator != NULL);
229
230 /* find the position where to insert */
231 if( scvdata->bvars == NULL )
232 {
233 assert(scvdata->nbnds == 0 && scvdata->bndssize == 0);
234 found = FALSE;
235 pos = 0;
236 }
237 else
238 {
239 found = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, &pos);
240 }
241
242 if( found )
243 return SCIP_OKAY;
244
245 /* ensure sizes */
246 if( scvdata->nbnds + 1 > scvdata->bndssize )
247 {
248 newsize = SCIPcalcMemGrowSize(scip, scvdata->nbnds + 1);
249 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->bvars, scvdata->bndssize, newsize) );
250 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->vals0, scvdata->bndssize, newsize) );
251 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->lbs1, scvdata->bndssize, newsize) );
252 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &scvdata->ubs1, scvdata->bndssize, newsize) );
253 scvdata->bndssize = newsize;
254 }
255 assert(scvdata->nbnds + 1 <= scvdata->bndssize);
256 assert(scvdata->bvars != NULL);
257
258 /* move entries if needed */
259 for( i = scvdata->nbnds; i > pos; --i )
260 {
261 /* coverity[var_deref_op] */
262 scvdata->bvars[i] = scvdata->bvars[i-1];
263 scvdata->vals0[i] = scvdata->vals0[i-1];
264 scvdata->lbs1[i] = scvdata->lbs1[i-1];
265 scvdata->ubs1[i] = scvdata->ubs1[i-1];
266 }
267
268 scvdata->bvars[pos] = indicator;
269 scvdata->vals0[pos] = val0;
270 scvdata->lbs1[pos] = lb1;
271 scvdata->ubs1[pos] = ub1;
272 ++scvdata->nbnds;
273
274 return SCIP_OKAY;
275}
276
277/** find scvardata of var and position of indicator in it
278 *
279 * If indicator is not there, returns NULL.
280 */
281static
283 SCIP_HASHMAP* scvars, /**< hashmap linking variables to scvardata */
284 SCIP_VAR* var, /**< variable */
285 SCIP_VAR* indicator, /**< indicator variable */
286 int* pos /**< pointer to store the position of indicator */
287 )
288{
289 SCIP_Bool exists;
290 SCVARDATA* scvdata;
291
292 assert(var != NULL);
293 assert(scvars != NULL);
294 assert(indicator != NULL);
295
296 scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var);
297 if( scvdata != NULL )
298 {
299 /* look for the indicator variable */
300 exists = SCIPsortedvecFindPtr((void**)scvdata->bvars, SCIPvarComp, (void*)indicator, scvdata->nbnds, pos);
301 if( !exists )
302 return NULL;
303
304 return scvdata;
305 }
306
307 return NULL;
308}
309
310/** checks if a variable is semicontinuous and, if needed, updates the scvars hashmap
311 *
312 * A variable \f$x\f$ is semicontinuous if its bounds depend on at least one binary variable called the indicator,
313 * and indicator = 0 &rArr; \f$x = x^0\f$ for some real constant \f$x^0\f$.
314 */
315static
317 SCIP* scip, /**< SCIP data structure */
318 SCIP_VAR* var, /**< the variable to check */
319 SCIP_HASHMAP* scvars, /**< semicontinuous variable information */
320 SCIP_Bool* result /**< buffer to store whether var is semicontinuous */
321 )
322{
323 SCIP_Real lb0;
324 SCIP_Real ub0;
325 SCIP_Real lb1;
326 SCIP_Real ub1;
327 SCIP_Real glb;
328 SCIP_Real gub;
329 SCIP_Bool exists;
330 int c;
331 int pos;
332 SCIP_VAR** vlbvars;
333 SCIP_VAR** vubvars;
334 SCIP_Real* vlbcoefs;
335 SCIP_Real* vubcoefs;
336 SCIP_Real* vlbconstants;
337 SCIP_Real* vubconstants;
338 int nvlbs;
339 int nvubs;
340 SCVARDATA* scvdata;
341 SCIP_VAR* bvar;
342
343 assert(scip != NULL);
344 assert(var != NULL);
345 assert(scvars != NULL);
346 assert(result != NULL);
347
348 scvdata = (SCVARDATA*) SCIPhashmapGetImage(scvars, (void*)var);
349 if( scvdata != NULL )
350 {
351 *result = TRUE;
352 return SCIP_OKAY;
353 }
354
355 vlbvars = SCIPvarGetVlbVars(var);
356 vubvars = SCIPvarGetVubVars(var);
357 vlbcoefs = SCIPvarGetVlbCoefs(var);
358 vubcoefs = SCIPvarGetVubCoefs(var);
359 vlbconstants = SCIPvarGetVlbConstants(var);
360 vubconstants = SCIPvarGetVubConstants(var);
361 nvlbs = SCIPvarGetNVlbs(var);
362 nvubs = SCIPvarGetNVubs(var);
363 glb = SCIPvarGetLbGlobal(var);
364 gub = SCIPvarGetUbGlobal(var);
365
366 *result = FALSE;
367
368 /* Scan through lower bounds; for each binary vlbvar save the corresponding lb0 and lb1.
369 * Then check if there is an upper bound with this vlbvar and save ub0 and ub1.
370 * If the found bounds imply that the var value is fixed to some val0 when vlbvar = 0,
371 * save vlbvar and val0 to scvdata.
372 */
373 for( c = 0; c < nvlbs; ++c )
374 {
375 if( SCIPvarGetType(vlbvars[c]) != SCIP_VARTYPE_BINARY )
376 continue;
377
378 SCIPdebugMsg(scip, "var <%s>[%f, %f] lower bound: %f <%s> %+f", SCIPvarGetName(var), glb, gub, vlbcoefs[c], SCIPvarGetName(vlbvars[c]), vlbconstants[c]);
379
380 bvar = vlbvars[c];
381
382 lb0 = MAX(vlbconstants[c], glb);
383 lb1 = MAX(vlbconstants[c] + vlbcoefs[c], glb);
384
385 /* look for bvar in vubvars */
386 if( vubvars != NULL )
387 exists = SCIPsortedvecFindPtr((void**)vubvars, SCIPvarComp, bvar, nvubs, &pos);
388 else
389 exists = FALSE;
390 if( exists )
391 { /*lint --e{644}*/
392 SCIPdebugMsgPrint(scip, ", upper bound: %f <%s> %+f", vubcoefs[pos], SCIPvarGetName(vubvars[pos]), vubconstants[pos]); /*lint !e613*/
393
394 /* save the upper bounds */
395 ub0 = MIN(vubconstants[pos], gub);
396 ub1 = MIN(vubconstants[pos] + vubcoefs[pos], gub);
397 }
398 else
399 {
400 /* if there is no upper bound with vubvar = bvar, use global var bounds */
401 ub0 = gub;
402 ub1 = gub;
403 }
404
405 /* the 'off' domain of a semicontinuous var should reduce to a single point and be different from the 'on' domain */
406 SCIPdebugMsgPrint(scip, " -> <%s> in [%f, %f] (off), [%f, %f] (on)\n", SCIPvarGetName(var), lb0, ub0, lb1, ub1);
407 if( SCIPisEQ(scip, lb0, ub0) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
408 {
409 if( scvdata == NULL )
410 {
412 }
413
414 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
415 }
416 }
417
418 /* look for vubvars that have not been processed yet */
419 assert(vubvars != NULL || nvubs == 0);
420 for( c = 0; c < nvubs; ++c )
421 {
422 /* coverity[var_deref_op] */
423 if( SCIPvarGetType(vubvars[c]) != SCIP_VARTYPE_BINARY ) /*lint !e613*/
424 continue;
425
426 bvar = vubvars[c]; /*lint !e613*/
427
428 /* skip vars that are in vlbvars */
429 if( vlbvars != NULL && SCIPsortedvecFindPtr((void**)vlbvars, SCIPvarComp, bvar, nvlbs, &pos) )
430 continue;
431
432 SCIPdebugMsg(scip, "var <%s>[%f, %f] upper bound: %f <%s> %+f",
433 SCIPvarGetName(var), glb, gub, vubcoefs[c], SCIPvarGetName(vubvars[c]), vubconstants[c]); /*lint !e613*/
434
435 lb0 = glb;
436 lb1 = glb;
437 ub0 = MIN(vubconstants[c], gub);
438 ub1 = MIN(vubconstants[c] + vubcoefs[c], gub);
439
440 /* the 'off' domain of a semicontinuous var should reduce to a single point and be different from the 'on' domain */
441 SCIPdebugMsgPrint(scip, " -> <%s> in [%f, %f] (off), [%f, %f] (on)\n", SCIPvarGetName(var), lb0, ub0, lb1, ub1);
442 if( SCIPisEQ(scip, lb0, ub0) && (!SCIPisEQ(scip, lb0, lb1) || !SCIPisEQ(scip, ub0, ub1)) )
443 {
444 if( scvdata == NULL )
445 {
447 }
448
449 SCIP_CALL( addSCVarIndicator(scip, scvdata, bvar, lb0, lb1, ub1) );
450 }
451 }
452
453 if( scvdata != NULL )
454 {
455#ifdef SCIP_DEBUG
456 SCIPdebugMsg(scip, "var <%s> has global bounds [%f, %f] and the following on/off bounds:\n", SCIPvarGetName(var), glb, gub);
457 for( c = 0; c < scvdata->nbnds; ++c )
458 {
459 SCIPdebugMsg(scip, " c = %d, bvar <%s>: val0 = %f\n", c, SCIPvarGetName(scvdata->bvars[c]), scvdata->vals0[c]);
460 }
461#endif
462 SCIP_CALL( SCIPhashmapInsert(scvars, var, scvdata) );
463 *result = TRUE;
464 }
465
466 return SCIP_OKAY;
467}
468
469/*
470 * Semicontinuous expression methods
471 */
472
473/* checks if an expression is semicontinuous
474 *
475 * An expression is semicontinuous if all of its nonlinear variables are semicontinuous
476 * and share at least one common indicator variable
477 */
478static
480 SCIP* scip, /**< SCIP data structure */
481 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
482 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
483 SCIP_EXPR* expr, /**< expression */
484 SCIP_Bool* res /**< buffer to store whether the expression is semicontinuous */
485 )
486{
487 int v;
488 SCIP_Bool var_is_sc;
489 SCVARDATA* scvdata;
490 SCIP_VAR* var;
491 int nindicators;
492 int nbnds0;
493 int c;
494 SCIP_VAR** indicators;
495 SCIP_Bool* nonlinear;
496
497 *res = FALSE;
498
499 /* constant expression is not semicontinuous; variable expressions are of no interest here */
500 if( nlhdlrexprdata->nvars == 0 )
501 return SCIP_OKAY;
502
503 indicators = NULL;
504 nindicators = 0;
505 nbnds0 = 0;
506
507 if( SCIPisExprSum(scip, expr) )
508 {
509 SCIP_EXPRITER* it;
510 SCIP_EXPR* child;
511 SCIP_EXPR* curexpr;
512 int pos;
513 SCIP_Bool issc;
514
515 /* sums are treated separately because if there are variables that are non-semicontinuous but
516 * appear only linearly, we still want to apply perspective to expr
517 */
518
519 SCIP_CALL( SCIPallocClearBufferArray(scip, &nonlinear, nlhdlrexprdata->nvars) );
521
522 for( c = 0; c < SCIPexprGetNChildren(expr); ++c )
523 {
524 child = SCIPexprGetChildren(expr)[c];
525
526 if( SCIPisExprVar(scip, child) )
527 {
528 var = SCIPgetVarExprVar(child);
529
530 /* save information on semicontinuity of child */
531 SCIP_CALL( varIsSemicontinuous(scip, var, nlhdlrdata->scvars, &var_is_sc) );
532
533 /* since child is a variable, go on regardless of the value of var_is_sc */
534 continue;
535 }
536
537 issc = TRUE;
538
540 curexpr = SCIPexpriterGetCurrent(it);
541
542 /* all nonlinear terms of a sum should be semicontinuous in original variables */
543 while( !SCIPexpriterIsEnd(it) )
544 {
545 assert(curexpr != NULL);
546
547 if( SCIPisExprVar(scip, curexpr) )
548 {
549 var = SCIPgetVarExprVar(curexpr);
550
551 if( !SCIPvarIsRelaxationOnly(var) )
552 {
553 SCIP_CALL( varIsSemicontinuous(scip, var, nlhdlrdata->scvars, &var_is_sc) );
554
555 /* mark the variable as nonlinear */
556 (void) SCIPsortedvecFindPtr((void**) nlhdlrexprdata->vars, SCIPvarComp, (void*) var, nlhdlrexprdata->nvars,
557 &pos);
558 assert(0 <= pos && pos < nlhdlrexprdata->nvars);
559 nonlinear[pos] = TRUE;
560
561 if( !var_is_sc )
562 {
563 /* non-semicontinuous child which is (due to a previous check) not a var ->
564 * expr is non-semicontinuous
565 */
566 issc = FALSE;
567 break;
568 }
569 }
570 }
571 curexpr = SCIPexpriterGetNext(it);
572 }
573
574 if( !issc )
575 {
576 SCIPfreeExpriter(&it);
577 goto TERMINATE;
578 }
579 }
580 SCIPfreeExpriter(&it);
581 }
582 else
583 {
584 /* non-sum expression */
585 nonlinear = NULL;
586
587 /* all variables of a non-sum on/off expression should be semicontinuous */
588 for( v = 0; v < nlhdlrexprdata->nvars; ++v )
589 {
590 SCIP_CALL( varIsSemicontinuous(scip, nlhdlrexprdata->vars[v], nlhdlrdata->scvars, &var_is_sc) );
591 if( !var_is_sc )
592 return SCIP_OKAY;
593 }
594 }
595
596 /* look for common binary variables for all variables of the expression */
597
598 SCIPdebugMsg(scip, "Array intersection for var <%s>\n", SCIPvarGetName(nlhdlrexprdata->vars[0]));
599 for( v = 0; v < nlhdlrexprdata->nvars; ++v )
600 {
601 SCIPdebugMsg(scip, "%s; \n", SCIPvarGetName(nlhdlrexprdata->vars[v]));
602
603 if( nonlinear != NULL && !nonlinear[v] )
604 continue;
605
606 scvdata = (SCVARDATA*)SCIPhashmapGetImage(nlhdlrdata->scvars, (void*) nlhdlrexprdata->vars[v]);
607
608 /* we should have exited earlier if there is a nonlinear non-semicontinuous variable */
609 assert(scvdata != NULL);
610
611 if( indicators == NULL )
612 {
613 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &indicators, scvdata->bvars, scvdata->nbnds) );
614 nbnds0 = scvdata->nbnds;
615 nindicators = nbnds0;
616 }
617 else
618 {
619 SCIPcomputeArraysIntersectionPtr((void**)indicators, nindicators, (void**)scvdata->bvars, scvdata->nbnds,
620 SCIPvarComp, (void**)indicators, &nindicators);
621 }
622
623 /* if we have found out that the intersection is empty, expr is not semicontinuous */
624 if( indicators != NULL && nindicators == 0 )
625 {
626 SCIPfreeBlockMemoryArray(scip, &indicators, nbnds0);
627 goto TERMINATE;
628 }
629 }
630
631 /* this can happen if all children are linear vars and none are semicontinuous */
632 if( indicators == NULL )
633 {
634 goto TERMINATE;
635 }
636 assert(nindicators > 0 && nindicators <= nbnds0);
637
638 if( nindicators < nbnds0 )
639 {
640 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &indicators, nbnds0, nindicators) );
641 }
642
643 for( v = 0; v < nindicators; ++v )
644 {
645 SCIP_CALL( SCIPcaptureVar(scip, indicators[v]) );
646 }
647 nlhdlrexprdata->indicators = indicators;
648 nlhdlrexprdata->nindicators = nindicators;
649 *res = TRUE;
650
651 TERMINATE:
652 SCIPfreeBufferArrayNull(scip, &nonlinear);
653
654 return SCIP_OKAY;
655}
656
657/** computes the 'off' value of the expression and the 'off' values of
658 * semicontinuous auxiliary variables for each indicator variable
659 */
660static
662 SCIP* scip, /**< SCIP data structure */
663 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
664 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
665 SCIP_EXPR* expr /**< expression */
666 )
667{
668 SCIP_EXPRITER* it;
669 SCIP_SOL* sol;
670 int i;
671 int v;
672 int norigvars;
673 SCIP_Real* origvals0;
674 SCIP_VAR** origvars;
675 SCVARDATA* scvdata;
676 SCIP_VAR* auxvar;
677 SCIP_EXPR* curexpr;
678 SCIP_HASHMAP* auxvarmap;
679 SCIP_Bool hasnonsc;
680 int pos;
681
682 assert(expr != NULL);
683
684 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(nlhdlrexprdata->exprvals0), nlhdlrexprdata->nindicators) );
685 SCIP_CALL( SCIPcreateSol(scip, &sol, NULL) );
686 SCIP_CALL( SCIPallocBufferArray(scip, &origvals0, nlhdlrexprdata->nvars) );
687 SCIP_CALL( SCIPhashmapCreate(&auxvarmap, SCIPblkmem(scip), 10) );
689 SCIP_CALL( SCIPduplicateBufferArray(scip, &origvars, nlhdlrexprdata->vars, nlhdlrexprdata->nvars) );
690 norigvars = nlhdlrexprdata->nvars;
691
692 for( i = nlhdlrexprdata->nindicators - 1; i >= 0; --i )
693 {
694 hasnonsc = FALSE;
695
696 /* set sol to the off value of all expr vars for this indicator */
697 for( v = 0; v < norigvars; ++v )
698 {
699 /* set vals0[v] = 0 if var is non-sc with respect to indicators[i] - then it will not
700 * contribute to exprvals0[i] since any non-sc var must be linear
701 */
702 scvdata = getSCVarDataInd(nlhdlrdata->scvars, origvars[v], nlhdlrexprdata->indicators[i], &pos);
703 if( scvdata == NULL )
704 {
705 origvals0[v] = 0.0;
706 hasnonsc = TRUE;
707 }
708 else
709 {
710 origvals0[v] = scvdata->vals0[pos];
711 }
712 }
713 SCIP_CALL( SCIPsetSolVals(scip, sol, norigvars, origvars, origvals0) );
714 SCIP_CALL( SCIPevalExpr(scip, expr, sol, 0L) );
715
716 if( SCIPexprGetEvalValue(expr) == SCIP_INVALID ) /*lint !e777*/
717 {
718 SCIPdebugMsg(scip, "expression evaluation failed for %p, removing indicator %s\n",
719 (void*)expr, SCIPvarGetName(nlhdlrexprdata->indicators[i]));
720 /* TODO should we fix the indicator variable to 1? */
721 /* since the loop is backwards, this only modifies the already processed part of nlhdlrexprdata->indicators */
722 SCIP_CALL( removeIndicator(scip, nlhdlrexprdata, i) );
723 continue;
724 }
725
726 nlhdlrexprdata->exprvals0[i] = SCIPexprGetEvalValue(expr);
727
728 /* iterate through the expression and create scvdata for aux vars */
730 curexpr = SCIPexpriterGetCurrent(it);
731
732 while( !SCIPexpriterIsEnd(it) )
733 {
734 auxvar = SCIPgetExprAuxVarNonlinear(curexpr);
735
736 if( auxvar != NULL )
737 {
738 SCIP_Bool issc = TRUE;
739#ifndef NDEBUG
740 SCIP_EXPR** childvarexprs;
741 int nchildvarexprs;
742 SCIP_VAR* var;
743#endif
744
745 if( hasnonsc )
746 {
747 /* expr is a sum with non-semicontinuous linear terms. Therefore, curexpr might be
748 * non-semicontinuous. In that case the auxvar is also non-semicontinuous, so
749 * we will skip on/off bounds computation.
750 */
751 if( SCIPisExprVar(scip, curexpr) )
752 {
753 /* easy case: curexpr is a variable, can check semicontinuity immediately */
754 scvdata = getSCVarDataInd(nlhdlrdata->scvars, SCIPgetVarExprVar(curexpr),
755 nlhdlrexprdata->indicators[i], &pos);
756 issc = scvdata != NULL;
757 }
758 else if( SCIPisExprSum(scip, curexpr) && curexpr == expr )
759 {
760 /* if expr itself is a sum, this is an exception since a sum with nonlinear terms is
761 * allowed to have both semicontinuous and non-semicontinuous variables; we skip it here
762 * and then analyse it term by term
763 */
764 issc = FALSE;
765 }
766
767#ifndef NDEBUG
768 if( !SCIPisExprVar(scip, curexpr) && (!SCIPisExprSum(scip, curexpr) || curexpr != expr) )
769 {
770 /* curexpr is a non-variable expression and does not fit the sum special case,
771 * so it belongs to the non-linear part of expr.
772 * Since the non-linear part of expr must be semicontinuous with respect to
773 * nlhdlrexprdata->indicators[i], curexpr must be semicontinuous
774 */
775
776 SCIP_CALL( SCIPallocBufferArray(scip, &childvarexprs, norigvars) );
777 SCIP_CALL( SCIPgetExprVarExprs(scip, curexpr, childvarexprs, &nchildvarexprs) );
778
779 /* all nonlinear variables of a sum on/off term should be semicontinuous */
780 for( v = 0; v < nchildvarexprs; ++v )
781 {
782 var = SCIPgetVarExprVar(childvarexprs[v]);
783 scvdata = getSCVarDataInd(nlhdlrdata->scvars, var, nlhdlrexprdata->indicators[i], &pos);
784 assert(scvdata != NULL);
785
786 SCIP_CALL( SCIPreleaseExpr(scip, &childvarexprs[v]) );
787 }
788
789 SCIPfreeBufferArray(scip, &childvarexprs);
790 }
791#endif
792 }
793
794 if( issc )
795 {
796 /* we know that all vars are semicontinuous with respect to exprdata->indicators; it remains to:
797 * - get or create the scvardata structure for auxvar
798 * - if had to create scvardata, add it to scvars hashmap
799 * - add the indicator and the off value (= curexpr's off value) to scvardata
800 */
801 scvdata = (SCVARDATA*) SCIPhashmapGetImage(nlhdlrdata->scvars, (void*)auxvar);
802 if( scvdata == NULL )
803 {
805 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->bvars, nlhdlrexprdata->nindicators) );
806 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->vals0, nlhdlrexprdata->nindicators) );
807 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->lbs1, nlhdlrexprdata->nindicators) );
808 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &scvdata->ubs1, nlhdlrexprdata->nindicators) );
809 scvdata->bndssize = nlhdlrexprdata->nindicators;
810 SCIP_CALL( SCIPhashmapInsert(nlhdlrdata->scvars, auxvar, scvdata) );
811 }
812
813 SCIP_CALL( addSCVarIndicator(scip, scvdata, nlhdlrexprdata->indicators[i],
814 SCIPexprGetEvalValue(curexpr), SCIPvarGetLbGlobal(auxvar), SCIPvarGetUbGlobal(auxvar)) );
815 }
816
817 SCIP_CALL( addAuxVar(scip, nlhdlrexprdata, auxvarmap, auxvar) );
818 }
819
820 curexpr = SCIPexpriterGetNext(it);
821 }
822 }
823
824 SCIPfreeExpriter(&it);
825 SCIPhashmapFree(&auxvarmap);
826 SCIPfreeBufferArray(scip, &origvars);
827 SCIPfreeBufferArray(scip, &origvals0);
828 SCIP_CALL( SCIPfreeSol(scip, &sol) );
829
830 return SCIP_OKAY;
831}
832
833/*
834 * Probing and bound tightening methods
835 */
836
837/** go into probing and set some variable bounds */
838static
840 SCIP* scip, /**< SCIP data structure */
841 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
842 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
843 SCIP_VAR* indicator, /**< indicator variable */
844 SCIP_VAR** probingvars, /**< array of vars whose bounds we will change in probing */
845 SCIP_INTERVAL* probingdoms, /**< array of intervals to which bounds of probingvars will be changed in probing */
846 int nprobingvars, /**< number of probing vars */
847 SCIP_SOL* sol, /**< solution to be separated */
848 SCIP_SOL** solcopy, /**< buffer for a copy of sol before going into probing; if *solcopy == sol, then copy is created */
849 SCIP_Bool* cutoff_probing /**< pointer to store whether indicator == 1 is infeasible */
850 )
851{
852 int v;
853 SCIP_Real newlb;
854 SCIP_Real newub;
855 SCIP_Bool propagate;
856
857 propagate = SCIPgetDepth(scip) == 0;
858
859 /* if a copy of sol has not been created yet, then create one now and copy the relevant var values from sol,
860 * because sol can change after SCIPstartProbing, e.g., when linked to the LP solution
861 */
862 if( *solcopy == sol )
863 {
864 SCIP_CALL( SCIPcreateSol(scip, solcopy, NULL) );
865 for( v = 0; v < nlhdlrexprdata->nvars; ++v )
866 {
867 SCIP_CALL( SCIPsetSolVal(scip, *solcopy, nlhdlrexprdata->vars[v], SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[v])) );
868 }
869 for( v = 0; v < nlhdlrexprdata->nindicators; ++v )
870 {
871 SCIP_CALL( SCIPsetSolVal(scip, *solcopy, nlhdlrexprdata->indicators[v], SCIPgetSolVal(scip, sol, nlhdlrexprdata->indicators[v])) );
872 }
873 }
874
875 /* go into probing */
877
878 /* create a probing node */
880
881 /* set indicator to 1 */
882 SCIP_CALL( SCIPchgVarLbProbing(scip, indicator, 1.0) );
883
884 /* apply stored bounds */
885 for( v = 0; v < nprobingvars; ++v )
886 {
887 newlb = SCIPintervalGetInf(probingdoms[v]);
888 newub = SCIPintervalGetSup(probingdoms[v]);
889
890 if( SCIPisGT(scip, newlb, SCIPvarGetLbLocal(probingvars[v])) || (newlb >= 0.0 && SCIPvarGetLbLocal(probingvars[v]) < 0.0) )
891 {
892 SCIP_CALL( SCIPchgVarLbProbing(scip, probingvars[v], newlb) );
893 }
894 if( SCIPisLT(scip, newub, SCIPvarGetUbLocal(probingvars[v])) || (newub <= 0.0 && SCIPvarGetUbLocal(probingvars[v]) > 0.0) )
895 {
896 SCIP_CALL( SCIPchgVarUbProbing(scip, probingvars[v], newub) );
897 }
898 }
899
900 if( propagate )
901 {
902 SCIP_Longint ndomreds;
903
904 SCIP_CALL( SCIPpropagateProbing(scip, nlhdlrdata->maxproprounds, cutoff_probing, &ndomreds) );
905 }
906
907 return SCIP_OKAY;
908}
909
910/** analyse on/off bounds on a variable
911 *
912 * analyses for
913 * 1. tightening bounds in probing for indicator = 1,
914 * 2. fixing indicator / detecting cutoff if one or both states are infeasible,
915 * 3. tightening local bounds if indicator is fixed.
916 *
917 * `probinglb` and `probingub` are only set if `doprobing` is TRUE.
918 * They are either set to bounds that should be used in probing or to `SCIP_INVALID` if bounds on
919 * `var` shouldn't be changed in probing.
920 */
921static
923 SCIP* scip, /**< SCIP data structure */
924 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
925 SCIP_VAR* var, /**< variable */
926 SCIP_VAR* indicator, /**< indicator variable */
927 SCIP_Bool indvalue, /**< indicator value for which the bounds are applied */
928 SCIP_Bool* infeas, /**< pointer to store whether infeasibility has been detected */
929 SCIP_Real* probinglb, /**< pointer to store the lower bound to be applied in probing */
930 SCIP_Real* probingub, /**< pointer to store the upper bound to be applied in probing */
931 SCIP_Bool doprobing, /**< whether we currently consider to go into probing */
932 SCIP_Bool* reduceddom /**< pointer to store whether any variables were fixed */
933 )
934{
935 SCVARDATA* scvdata;
936 int pos;
937 SCIP_Real sclb;
938 SCIP_Real scub;
939 SCIP_Real loclb;
940 SCIP_Real locub;
941 SCIP_Bool bndchgsuccess;
942
943 assert(var != NULL);
944 assert(indicator != NULL);
945 assert(infeas != NULL);
946 assert(reduceddom != NULL);
947
948 /* shouldn't be called if indicator is fixed to !indvalue */
949 assert((indvalue && SCIPvarGetUbLocal(indicator) > 0.5) || (!indvalue && SCIPvarGetLbLocal(indicator) < 0.5));
950
951 *infeas = FALSE;
952 *reduceddom = FALSE;
953 scvdata = getSCVarDataInd(nlhdlrdata->scvars, var, indicator, &pos);
954 if( doprobing )
955 {
956 assert(probinglb != NULL);
957 assert(probingub != NULL);
958
959 *probinglb = SCIP_INVALID;
960 *probingub = SCIP_INVALID;
961 }
962
963 /* nothing to do for non-semicontinuous variables */
964 if( scvdata == NULL )
965 {
966 return SCIP_OKAY;
967 }
968
969 sclb = indvalue ? scvdata->lbs1[pos] : scvdata->vals0[pos];
970 scub = indvalue ? scvdata->ubs1[pos] : scvdata->vals0[pos];
971 loclb = SCIPvarGetLbLocal(var);
972 locub = SCIPvarGetUbLocal(var);
973
974 /* nothing to do for fixed variables */
975 if( SCIPisEQ(scip, loclb, locub) )
976 return SCIP_OKAY;
977
978 /* use a non-redundant lower bound */
979 if( SCIPisGT(scip, sclb, SCIPvarGetLbLocal(var)) || (sclb >= 0.0 && loclb < 0.0) )
980 {
981 /* first check for infeasibility */
982 if( SCIPisFeasGT(scip, sclb, SCIPvarGetUbLocal(var)) )
983 {
984 SCIP_CALL( SCIPfixVar(scip, indicator, indvalue ? 0.0 : 1.0, infeas, &bndchgsuccess) );
985 *reduceddom += bndchgsuccess;
986 if( *infeas )
987 {
988 return SCIP_OKAY;
989 }
990 }
991 else if( nlhdlrdata->tightenbounds &&
992 (SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5) )
993 {
994 /* indicator is fixed; due to a previous check, here it can only be fixed to indvalue;
995 * therefore, sclb is valid for the current node
996 */
997
998 if( indvalue == 0 )
999 {
1000 assert(sclb == scub); /*lint !e777*/
1001 SCIP_CALL( SCIPfixVar(scip, var, sclb, infeas, &bndchgsuccess) );
1002 }
1003 else
1004 {
1005 SCIP_CALL( SCIPtightenVarLb(scip, var, sclb, FALSE, infeas, &bndchgsuccess) );
1006 }
1007 *reduceddom += bndchgsuccess;
1008 if( *infeas )
1009 {
1010 return SCIP_OKAY;
1011 }
1012 }
1013 }
1014
1015 /* use a non-redundant upper bound */
1016 if( SCIPisLT(scip, scub, SCIPvarGetUbLocal(var)) || (scub <= 0.0 && locub > 0.0) )
1017 {
1018 /* first check for infeasibility */
1019 if( SCIPisFeasLT(scip, scub, SCIPvarGetLbLocal(var)) )
1020 {
1021 SCIP_CALL( SCIPfixVar(scip, indicator, indvalue ? 0.0 : 1.0, infeas, &bndchgsuccess) );
1022 *reduceddom += bndchgsuccess;
1023 if( *infeas )
1024 {
1025 return SCIP_OKAY;
1026 }
1027 }
1028 else if( nlhdlrdata->tightenbounds &&
1029 (SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5) )
1030 {
1031 /* indicator is fixed; due to a previous check, here it can only be fixed to indvalue;
1032 * therefore, scub is valid for the current node
1033 */
1034
1035 if( indvalue == 0 )
1036 {
1037 assert(sclb == scub); /*lint !e777*/
1038 SCIP_CALL( SCIPfixVar(scip, var, scub, infeas, &bndchgsuccess) );
1039 }
1040 else
1041 {
1042 SCIP_CALL( SCIPtightenVarUb(scip, var, scub, FALSE, infeas, &bndchgsuccess) );
1043 }
1044 *reduceddom += bndchgsuccess;
1045 if( *infeas )
1046 {
1047 return SCIP_OKAY;
1048 }
1049 }
1050 }
1051
1052 /* If a bound change has been found and indvalue == TRUE, try to use the new bounds.
1053 * This is only done for indvalue == TRUE since this is where enfo asks other nlhdlrs to estimate,
1054 * and at indicator == FALSE we already only have a single point
1055 */
1056 if( doprobing && indvalue && (((scub - sclb) / (locub - loclb)) <= 1.0 - nlhdlrdata->mindomreduction ||
1057 (sclb >= 0.0 && loclb < 0.0) || (scub <= 0.0 && locub > 0.0)) )
1058 {
1059 *probinglb = sclb;
1060 *probingub = scub;
1061 }
1062
1063 SCIPdebugMsg(scip, "%s in [%g, %g] instead of [%g, %g] (vals0 = %g)\n", SCIPvarGetName(var), sclb, scub,
1064 SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), scvdata->vals0[pos]);
1065
1066 return SCIP_OKAY;
1067}
1068
1069/** looks for bound tightenings to be applied either in the current node or in probing
1070 *
1071 * Loops through both possible values of indicator and calls analyseVarOnoffBounds().
1072 * Might update the `*doprobing` flag by setting it to `FALSE` if:
1073 * - indicator is fixed or
1074 * - analyseVarOnoffBounds() hasn't found a sufficient improvement at indicator==1.
1075 *
1076 * If `*doprobing==TRUE`, stores bounds suggested by analyseVarOnoffBounds() in order to apply them in probing together
1077 * with the fixing `indicator=1`.
1078 */
1079static
1081 SCIP* scip, /**< SCIP data structure */
1082 SCIP_NLHDLRDATA* nlhdlrdata, /**< nonlinear handler data */
1083 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
1084 SCIP_VAR* indicator, /**< indicator variable */
1085 SCIP_VAR*** probingvars, /**< array to store variables whose bounds will be changed in probing */
1086 SCIP_INTERVAL** probingdoms, /**< array to store bounds to be applied in probing */
1087 int* nprobingvars, /**< pointer to store number of vars whose bounds will be changed in probing */
1088 SCIP_Bool* doprobing, /**< pointer to the flag telling whether we want to do probing */
1089 SCIP_RESULT* result /**< pointer to store the result */
1090 )
1091{
1092 int v;
1093 SCIP_VAR* var;
1094 SCIP_Bool infeas;
1095 int b;
1096 SCIP_Real probinglb = SCIP_INVALID;
1097 SCIP_Real probingub = SCIP_INVALID;
1098 SCIP_Bool changed;
1099 SCIP_Bool reduceddom;
1100
1101 assert(indicator != NULL);
1102 assert(nprobingvars != NULL);
1103 assert(doprobing != NULL);
1104 assert(result != NULL);
1105
1106 changed = FALSE;
1107
1108 /* no probing if indicator already fixed */
1109 if( SCIPvarGetUbLocal(indicator) <= 0.5 || SCIPvarGetLbLocal(indicator) >= 0.5 )
1110 {
1111 *doprobing = FALSE;
1112 }
1113
1114 /* consider each possible value of indicator */
1115 for( b = 0; b < 2; ++b )
1116 {
1117 for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1118 {
1119 /* nothing left to do if indicator is already fixed to !indvalue
1120 * (checked in the inner loop since analyseVarOnoff bounds might fix the indicator)
1121 */
1122 if( (b == 1 && SCIPvarGetUbLocal(indicator) <= 0.5) || (b == 0 && SCIPvarGetLbLocal(indicator) >= 0.5) )
1123 {
1124 *doprobing = FALSE;
1125 break;
1126 }
1127
1128 var = nlhdlrexprdata->vars[v];
1129
1130 SCIP_CALL( analyseVarOnoffBounds(scip, nlhdlrdata, var, indicator, b == 1, &infeas, &probinglb,
1131 &probingub, *doprobing, &reduceddom) );
1132
1133 if( infeas )
1134 {
1135 *result = SCIP_CUTOFF;
1136 *doprobing = FALSE;
1137 return SCIP_OKAY;
1138 }
1139 else if( reduceddom )
1140 {
1141 *result = SCIP_REDUCEDDOM;
1142 }
1143
1144 if( !(*doprobing) )
1145 continue;
1146
1147 /* if bounds to be applied in probing have been found, store them */
1148 if( probinglb != SCIP_INVALID ) /*lint !e777*/
1149 {
1150 assert(probingub != SCIP_INVALID); /*lint !e777*/
1151
1152 SCIP_CALL( SCIPreallocBufferArray(scip, probingvars, *nprobingvars + 1) );
1153 SCIP_CALL( SCIPreallocBufferArray(scip, probingdoms, *nprobingvars + 1) );
1154 (*probingvars)[*nprobingvars] = var;
1155 (*probingdoms)[*nprobingvars].inf = probinglb;
1156 (*probingdoms)[*nprobingvars].sup = probingub;
1157 ++*nprobingvars;
1158
1159 changed = TRUE;
1160 }
1161 }
1162 }
1163
1164 if( !changed )
1165 {
1166 *doprobing = FALSE;
1167 }
1168
1169 return SCIP_OKAY;
1170}
1171
1172/** saves local bounds on all expression variables, including auxiliary variables, obtained from propagating
1173 * indicator == 1 to the corresponding SCVARDATA (should only be used in the root node)
1174 */
1175static
1177 SCIP_NLHDLREXPRDATA* nlhdlrexprdata, /**< nlhdlr expression data */
1178 SCIP_HASHMAP* scvars, /**< hashmap with semicontinuous variables */
1179 SCIP_VAR* indicator /**< indicator variable */
1180 )
1181{
1182 int v;
1183 SCIP_VAR* var;
1184 SCVARDATA* scvdata;
1185 int pos;
1186 SCIP_Real lb;
1187 SCIP_Real ub;
1188
1189 for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1190 {
1191 var = nlhdlrexprdata->vars[v];
1192 lb = SCIPvarGetLbLocal(var);
1193 ub = SCIPvarGetUbLocal(var);
1194 scvdata = getSCVarDataInd(scvars, var, indicator, &pos);
1195
1196 if( scvdata != NULL )
1197 {
1198 scvdata->lbs1[pos] = MAX(scvdata->lbs1[pos], lb);
1199 scvdata->ubs1[pos] = MIN(scvdata->ubs1[pos], ub);
1200 }
1201 }
1202
1203 return SCIP_OKAY;
1204}
1205
1206/*
1207 * Callback methods of nonlinear handler
1208 */
1209
1210/** nonlinear handler copy callback */
1211static
1212SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrPerspective)
1213{ /*lint --e{715}*/
1214 assert(targetscip != NULL);
1215 assert(sourcenlhdlr != NULL);
1216 assert(strcmp(SCIPnlhdlrGetName(sourcenlhdlr), NLHDLR_NAME) == 0);
1217
1219
1220 return SCIP_OKAY;
1221}
1222
1223
1224/** callback to free data of handler */
1225static
1226SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrFreehdlrdataPerspective)
1227{ /*lint --e{715}*/
1228 SCIPfreeBlockMemory(scip, nlhdlrdata);
1229
1230 return SCIP_OKAY;
1231}
1232
1233
1234/** callback to free expression specific data */
1235static
1236SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataPerspective)
1237{ /*lint --e{715}*/
1238 SCIP_CALL( freeNlhdlrExprData(scip, *nlhdlrexprdata) );
1239 SCIPfreeBlockMemory(scip, nlhdlrexprdata);
1240
1241 return SCIP_OKAY;
1242}
1243
1244/** callback to be called in initialization */
1245#if 0
1246static
1247SCIP_DECL_NLHDLRINIT(nlhdlrInitPerspective)
1248{ /*lint --e{715}*/
1249 return SCIP_OKAY;
1250}
1251#endif
1252
1253/** callback to be called in deinitialization */
1254static
1255SCIP_DECL_NLHDLREXIT(nlhdlrExitPerspective)
1256{ /*lint --e{715}*/
1257 SCIP_HASHMAPENTRY* entry;
1258 SCVARDATA* data;
1259 int c;
1260 SCIP_NLHDLRDATA* nlhdlrdata;
1261
1262 nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1263 assert(nlhdlrdata != NULL);
1264
1265 if( nlhdlrdata->scvars != NULL )
1266 {
1267 for( c = 0; c < SCIPhashmapGetNEntries(nlhdlrdata->scvars); ++c )
1268 {
1269 entry = SCIPhashmapGetEntry(nlhdlrdata->scvars, c);
1270 if( entry != NULL )
1271 {
1272 data = (SCVARDATA*) SCIPhashmapEntryGetImage(entry);
1277 SCIPfreeBlockMemory(scip, &data);
1278 }
1279 }
1280 SCIPhashmapFree(&nlhdlrdata->scvars);
1281 assert(nlhdlrdata->scvars == NULL);
1282 }
1283
1284 return SCIP_OKAY;
1285}
1286
1287/** callback to detect structure in expression tree
1288 *
1289 * We are looking for expressions g(x), where x is a vector of semicontinuous variables that all share at least one
1290 * indicator variable.
1291 */
1292static
1293SCIP_DECL_NLHDLRDETECT(nlhdlrDetectPerspective)
1294{ /*lint --e{715}*/
1295 SCIP_NLHDLRDATA* nlhdlrdata;
1296 SCIP_EXPR** varexprs;
1297 SCIP_Bool success = FALSE;
1298 int i;
1299 SCIP_Bool hassepabelow = FALSE;
1300 SCIP_Bool hassepaabove = FALSE;
1301 SCIP_Bool hasnondefault = FALSE;
1302
1303 nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1304
1305 assert(scip != NULL);
1306 assert(nlhdlr != NULL);
1307 assert(expr != NULL);
1308 assert(participating != NULL);
1309 assert(enforcing != NULL);
1310 assert(nlhdlrexprdata != NULL);
1311 assert(nlhdlrdata != NULL);
1312
1313 /* do not run if we will have no auxvar to add a cut for */
1314 if( SCIPgetExprNAuxvarUsesNonlinear(expr) == 0 )
1315 return SCIP_OKAY;
1316
1317 if( SCIPgetNBinVars(scip) == 0 )
1318 {
1319 SCIPdebugMsg(scip, "problem has no binary variables, not running perspective detection\n");
1320 return SCIP_OKAY;
1321 }
1322
1323 for( i = 0; i < SCIPgetExprNEnfosNonlinear(expr); ++i )
1324 {
1325 SCIP_NLHDLR* nlhdlr2;
1326 SCIP_NLHDLR_METHOD nlhdlr2participates;
1327 SCIP_Bool sepabelowusesactivity;
1328 SCIP_Bool sepaaboveusesactivity;
1329 SCIPgetExprEnfoDataNonlinear(expr, i, &nlhdlr2, NULL, &nlhdlr2participates, &sepabelowusesactivity, &sepaaboveusesactivity, NULL);
1330
1331 if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPABOTH) == 0 )
1332 continue;
1333
1334 if( !SCIPnlhdlrHasEstimate(nlhdlr2) )
1335 continue;
1336
1337 if( strcmp(SCIPnlhdlrGetName(nlhdlr2), "default") != 0 )
1338 hasnondefault = TRUE;
1339
1340 /* If we are supposed to run only on convex expressions, than check whether there is a nlhdlr
1341 * that participates in separation without using activity for it. Otherwise, check for
1342 * participation regardless of activity usage.
1343 */
1344 if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPABELOW) && (!nlhdlrdata->convexonly || !sepabelowusesactivity) )
1345 hassepabelow = TRUE;
1346
1347 if( (nlhdlr2participates & SCIP_NLHDLR_METHOD_SEPAABOVE) && (!nlhdlrdata->convexonly || !sepaaboveusesactivity) )
1348 hassepaabove = TRUE;
1349 }
1350
1351 /* If a sum expression is handled only by default nlhdlr, then all the children will have auxiliary vars.
1352 * Since the sum will then be linear in auxiliary variables, perspective can't improve anything for it
1353 */
1354 if( SCIPisExprSum(scip, expr) && !hasnondefault )
1355 {
1356 SCIPdebugMsg(scip, "sum expr only has default exprhdlr, not running perspective detection\n");
1357 return SCIP_OKAY;
1358 }
1359
1360 /* If no other nlhdlr separates, neither does perspective (if convexonly, only separation
1361 * without using activity counts)
1362 */
1363 if( !hassepabelow && !hassepaabove )
1364 {
1365 SCIPdebugMsg(scip, "no nlhdlr separates without using activity, not running perspective detection\n");
1366 return SCIP_OKAY;
1367 }
1368
1369#ifdef SCIP_DEBUG
1370 SCIPdebugMsg(scip, "Called perspective detect, expr = %p: ", (void*)expr);
1371 SCIPprintExpr(scip, expr, NULL);
1372 SCIPdebugMsgPrint(scip, "\n");
1373#endif
1374
1375 /* allocate memory */
1376 SCIP_CALL( SCIPallocClearBlockMemory(scip, nlhdlrexprdata) );
1377 if( nlhdlrdata->scvars == NULL )
1378 {
1379 SCIP_CALL( SCIPhashmapCreate(&(nlhdlrdata->scvars), SCIPblkmem(scip), SCIPgetNVars(scip)) );
1380 }
1381
1382 /* save varexprs to nlhdlrexprdata */
1383 SCIP_CALL( SCIPgetExprNVars(scip, expr, &(*nlhdlrexprdata)->nvars) );
1384 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*nlhdlrexprdata)->vars, (*nlhdlrexprdata)->nvars) );
1385 SCIP_CALL( SCIPallocBufferArray(scip, &varexprs, (*nlhdlrexprdata)->nvars) );
1386 (*nlhdlrexprdata)->varssize = (*nlhdlrexprdata)->nvars;
1387 SCIP_CALL( SCIPgetExprVarExprs(scip, expr, varexprs, &(*nlhdlrexprdata)->nvars) );
1388 for( i = 0; i < (*nlhdlrexprdata)->nvars; ++i )
1389 {
1390 (*nlhdlrexprdata)->vars[i] = SCIPgetVarExprVar(varexprs[i]);
1391 SCIP_CALL( SCIPreleaseExpr(scip, &varexprs[i]) );
1392 SCIP_CALL( SCIPcaptureVar(scip, (*nlhdlrexprdata)->vars[i]) );
1393 }
1394 SCIPsortPtr((void**) (*nlhdlrexprdata)->vars, SCIPvarComp, (*nlhdlrexprdata)->nvars);
1395 SCIPfreeBufferArray(scip, &varexprs);
1396
1397 /* check if expr is semicontinuous and save indicator variables */
1398 SCIP_CALL( exprIsSemicontinuous(scip, nlhdlrdata, *nlhdlrexprdata, expr, &success) );
1399
1400 if( success )
1401 {
1402 assert(*nlhdlrexprdata != NULL);
1403 assert((*nlhdlrexprdata)->nindicators > 0);
1404
1405 if( hassepaabove )
1406 *participating |= SCIP_NLHDLR_METHOD_SEPAABOVE;
1407 if( hassepabelow )
1408 *participating |= SCIP_NLHDLR_METHOD_SEPABELOW;
1409
1410#ifdef SCIP_DEBUG
1411 SCIPinfoMessage(scip, NULL, "detected an on/off expr: ");
1412 SCIPprintExpr(scip, expr, NULL);
1413 SCIPinfoMessage(scip, NULL, "\n");
1414#endif
1415 }
1416 else
1417 {
1418 assert(*nlhdlrexprdata != NULL);
1419 SCIP_CALL( nlhdlrFreeExprDataPerspective(scip, nlhdlr, expr, nlhdlrexprdata) );
1420 }
1421
1422 return SCIP_OKAY;
1423}
1424
1425
1426/** auxiliary evaluation callback of nonlinear handler */
1427static
1428SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxPerspective)
1429{ /*lint --e{715}*/
1430 int e;
1431 SCIP_Real maxdiff;
1432 SCIP_Real auxvarvalue;
1433 SCIP_Real enfoauxval;
1434
1435 assert(scip != NULL);
1436 assert(expr != NULL);
1437 assert(auxvalue != NULL);
1438
1439 auxvarvalue = SCIPgetSolVal(scip, sol, SCIPgetExprAuxVarNonlinear(expr));
1440 maxdiff = 0.0;
1441 *auxvalue = auxvarvalue;
1442
1443 /* use the auxvalue from one of the other nlhdlrs that estimates for this expr: take the one that is farthest
1444 * from the current value of auxvar
1445 */
1446 for( e = 0; e < SCIPgetExprNEnfosNonlinear(expr); ++e )
1447 {
1448 SCIP_NLHDLR* nlhdlr2;
1449 SCIP_NLHDLREXPRDATA* nlhdlr2exprdata;
1450 SCIP_NLHDLR_METHOD nlhdlr2participation;
1451
1452 SCIPgetExprEnfoDataNonlinear(expr, e, &nlhdlr2, &nlhdlr2exprdata, &nlhdlr2participation, NULL, NULL, NULL);
1453
1454 /* skip nlhdlr that do not participate or do not provide estimate */
1455 if( (nlhdlr2participation & SCIP_NLHDLR_METHOD_SEPABOTH) == 0 || !SCIPnlhdlrHasEstimate(nlhdlr2) )
1456 continue;
1457
1458 SCIP_CALL( SCIPnlhdlrEvalaux(scip, nlhdlr2, expr, nlhdlr2exprdata, &enfoauxval, sol) );
1459
1460 SCIPsetExprEnfoAuxValueNonlinear(expr, e, enfoauxval);
1461
1462 if( REALABS(enfoauxval - auxvarvalue) > maxdiff && enfoauxval != SCIP_INVALID ) /*lint !e777*/
1463 {
1464 maxdiff = REALABS(enfoauxval - auxvarvalue);
1465 *auxvalue = enfoauxval;
1466 }
1467 }
1468
1469 return SCIP_OKAY;
1470}
1471
1472/** separation initialization method of a nonlinear handler */
1473static
1474SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaPerspective)
1475{ /*lint --e{715}*/
1476 int sindicators;
1477
1478 sindicators = nlhdlrexprdata->nindicators;
1479
1480 /* compute 'off' values of expr and subexprs (and thus auxvars too) */
1481 SCIP_CALL( computeOffValues(scip, SCIPnlhdlrGetData(nlhdlr), nlhdlrexprdata, expr) );
1482
1483 /* some indicator variables might have been removed if evaluation failed, check how many remain */
1484 if( nlhdlrexprdata->nindicators == 0 )
1485 {
1486 SCIPfreeBlockMemoryArray(scip, &nlhdlrexprdata->indicators, sindicators);
1487 SCIPfreeBlockMemoryArray(scip, &nlhdlrexprdata->exprvals0, sindicators);
1488 }
1489 else if( nlhdlrexprdata->nindicators < sindicators )
1490 {
1491 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->indicators, sindicators, nlhdlrexprdata->nindicators) );
1492 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &nlhdlrexprdata->exprvals0, sindicators, nlhdlrexprdata->nindicators) );
1493 }
1494
1495 return SCIP_OKAY;
1496}
1497
1498
1499#if 0
1500/** separation deinitialization method of a nonlinear handler (called during CONSEXITSOL) */
1501static
1502SCIP_DECL_NLHDLREXITSEPA(nlhdlrExitSepaPerspective)
1503{ /*lint --e{715}*/
1504 SCIPerrorMessage("method of perspective nonlinear handler not implemented yet\n");
1505 SCIPABORT(); /*lint --e{527}*/
1506
1507 return SCIP_OKAY;
1508}
1509#endif
1510
1511/** nonlinear handler enforcement callback
1512 *
1513 * "Perspectivies" cuts produced by other nonlinear handlers.
1514 *
1515 * Suppose that we want to separate \f$x\f$ from the set \f$\{ x : g(x) \leq 0\}\f$.
1516 * If \f$g(x) = g^0\f$ if indicator \f$z = 0\f$, and a cut is given by \f$\sum_i a_ix_i + c \leq \text{aux}\f$, where \f$x_i = x_i^0\f$ if \f$z = 0\f$ for all \f$i\f$,
1517 * then the "perspectivied" cut is \f[\sum_i a_ix_i + c + (1 - z)\,(g^0 - c - \sum_i a_ix_i^0) \leq \text{aux}.\f]
1518 * This ensures that at \f$z = 1\f$, the new cut is equivalent to the given cut, and at \f$z = 0\f$ it reduces to \f$g^0 \leq \text{aux}\f$.
1519 */
1520static
1521SCIP_DECL_NLHDLRENFO(nlhdlrEnfoPerspective)
1522{ /*lint --e{715}*/
1523 SCIP_ROWPREP* rowprep;
1524 SCIP_VAR* auxvar;
1525 int i;
1526 int j;
1527 SCIP_NLHDLRDATA* nlhdlrdata;
1528 SCIP_Real cst0;
1529 SCIP_VAR* indicator;
1530 SCIP_PTRARRAY* rowpreps2;
1531 SCIP_PTRARRAY* rowpreps;
1532 int nrowpreps;
1533 SCIP_SOL* solcopy;
1534 SCIP_Bool doprobing;
1535 SCIP_BOOLARRAY* addedbranchscores2;
1536 SCIP_Bool stop;
1537 int nenfos;
1538 int* enfoposs;
1539 SCIP_SOL* soladj;
1540 int pos;
1541 SCVARDATA* scvdata;
1542
1543 nlhdlrdata = SCIPnlhdlrGetData(nlhdlr);
1544
1545#ifdef SCIP_DEBUG
1546 SCIPinfoMessage(scip, NULL, "enforcement method of perspective nonlinear handler called for expr %p: ", (void*)expr);
1547 SCIP_CALL( SCIPprintExpr(scip, expr, NULL) );
1548 SCIPinfoMessage(scip, NULL, " at\n");
1549 for( i = 0; i < nlhdlrexprdata->nvars; ++i )
1550 {
1551 SCIPinfoMessage(scip, NULL, "%s = %g\n", SCIPvarGetName(nlhdlrexprdata->vars[i]),
1552 SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[i]));
1553 }
1556#endif
1557
1558 assert(scip != NULL);
1559 assert(expr != NULL);
1560 assert(conshdlr != NULL);
1561 assert(nlhdlrexprdata != NULL);
1562 assert(nlhdlrdata != NULL);
1563
1564 if( nlhdlrexprdata->nindicators == 0 )
1565 {
1566 /* we might have removed all indicators in initsepa */
1567 *result = SCIP_DIDNOTRUN;
1568 return SCIP_OKAY;
1569 }
1570
1571 if( branchcandonly )
1572 {
1573 /* let the regular calls to the nlhdlrs after perspective register branching candidates */
1574 *result = SCIP_DIDNOTRUN;
1575 return SCIP_OKAY;
1576 }
1577
1578 auxvar = SCIPgetExprAuxVarNonlinear(expr);
1579 assert(auxvar != NULL);
1580
1581 /* detect should have picked only those expressions for which at least one other nlhdlr can enforce */
1582 assert(SCIPgetExprNEnfosNonlinear(expr) > 1);
1583
1585
1586 doprobing = FALSE;
1587 nenfos = 0;
1588 soladj = NULL;
1589
1590 /* find suitable nlhdlrs and check if there is enough violation to do probing */
1591 for( j = 0; j < SCIPgetExprNEnfosNonlinear(expr); ++j )
1592 {
1593 SCIP_NLHDLR* nlhdlr2;
1594 SCIP_NLHDLREXPRDATA* nlhdlr2exprdata;
1595 SCIP_NLHDLR_METHOD nlhdlr2participate;
1596 SCIP_Real nlhdlr2auxvalue;
1597 SCIP_Real violation;
1598 SCIP_Bool violbelow;
1599 SCIP_Bool violabove;
1600 SCIP_Bool sepausesactivity = FALSE;
1601
1602 SCIPgetExprEnfoDataNonlinear(expr, j, &nlhdlr2, &nlhdlr2exprdata, &nlhdlr2participate, !overestimate ? &sepausesactivity : NULL, overestimate ? &sepausesactivity: NULL, &nlhdlr2auxvalue); /*lint !e826*/
1603
1604 if( nlhdlr2 == nlhdlr )
1605 continue;
1606
1607 /* if nlhdlr2 cannot estimate, then cannot use it */
1608 if( !SCIPnlhdlrHasEstimate(nlhdlr2) )
1609 continue;
1610
1611 /* if nlhdlr2 does not participate in the separation on the desired side (overestimate), then skip it */
1612 if( (nlhdlr2participate & (overestimate ? SCIP_NLHDLR_METHOD_SEPAABOVE : SCIP_NLHDLR_METHOD_SEPABELOW)) == 0 )
1613 continue;
1614
1615 /* if only working on convex-looking expressions, then skip nlhdlr if it uses activity for estimates */
1616 if( nlhdlrdata->convexonly && sepausesactivity )
1617 continue;
1618
1619 /* evalaux should have called evalaux of nlhdlr2 by now
1620 * check whether handling the violation for nlhdlr2 requires under- or overestimation and this fits to
1621 * overestimate flag
1622 */
1623 SCIP_CALL( SCIPgetExprAbsAuxViolationNonlinear(scip, expr, nlhdlr2auxvalue, sol, &violation, &violbelow,
1624 &violabove) );
1625 assert(violation >= 0.0);
1626
1627 if( (overestimate && !violabove) || (!overestimate && !violbelow) )
1628 continue;
1629
1630 /* if violation is small, cuts would likely be weak - skip perspectification */
1631 if( !allowweakcuts && violation < SCIPfeastol(scip) )
1632 continue;
1633
1634 enfoposs[nenfos] = j;
1635 ++nenfos;
1636
1637 /* enable probing if tightening the domain could be useful for nlhdlr and violation is above threshold */
1638 if( sepausesactivity && violation >= nlhdlrdata->minviolprobing )
1639 doprobing = TRUE;
1640 }
1641
1642 if( nenfos == 0 )
1643 {
1644 *result = SCIP_DIDNOTRUN;
1645 SCIPfreeBufferArray(scip, &enfoposs);
1646 return SCIP_OKAY;
1647 }
1648
1649 /* check probing frequency against depth in b&b tree */
1650 if( nlhdlrdata->probingfreq == -1 || (nlhdlrdata->probingfreq == 0 && SCIPgetDepth(scip) != 0) ||
1651 (nlhdlrdata->probingfreq > 0 && SCIPgetDepth(scip) % nlhdlrdata->probingfreq != 0) )
1652 doprobing = FALSE;
1653
1654 /* if addbranchscores is TRUE, then we can assume to be in enforcement and not in separation */
1655 if( nlhdlrdata->probingonlyinsepa && addbranchscores )
1656 doprobing = FALSE;
1657
1658 /* disable probing if already being in probing or if in a subscip */
1660 doprobing = FALSE;
1661
1662 nrowpreps = 0;
1663 *result = SCIP_DIDNOTFIND;
1664 solcopy = sol;
1665 stop = FALSE;
1666
1667 SCIP_CALL( SCIPcreatePtrarray(scip, &rowpreps2) );
1668 SCIP_CALL( SCIPcreatePtrarray(scip, &rowpreps) );
1669 SCIP_CALL( SCIPcreateBoolarray(scip, &addedbranchscores2) );
1670
1671 /* build cuts for every indicator variable */
1672 for( i = 0; i < nlhdlrexprdata->nindicators && !stop; ++i )
1673 {
1674 int v;
1675 int minidx;
1676 int maxidx;
1677 int r;
1678 SCIP_VAR** probingvars;
1679 SCIP_INTERVAL* probingdoms;
1680 int nprobingvars;
1681 SCIP_Bool doprobingind;
1682 SCIP_Real indval;
1683 SCIP_Real solval;
1684 SCIP_Bool adjrefpoint;
1685
1686 indicator = nlhdlrexprdata->indicators[i];
1687 probingvars = NULL;
1688 probingdoms = NULL;
1689 nprobingvars = 0;
1690 doprobingind = doprobing;
1691 solval = SCIPgetSolVal(scip, solcopy, indicator);
1692 adjrefpoint = nlhdlrdata->adjrefpoint && !SCIPisFeasEQ(scip, solval, 1.0);
1693
1694 SCIP_CALL( analyseOnoffBounds(scip, nlhdlrdata, nlhdlrexprdata, indicator, &probingvars, &probingdoms,
1695 &nprobingvars, &doprobingind, result) );
1696
1697 /* don't add perspective cuts for fixed indicators since there is no use for perspectivy */
1698 if( SCIPvarGetLbLocal(indicator) >= 0.5 )
1699 {
1700 assert(!doprobingind);
1701 continue;
1702 }
1703
1704 if( SCIPvarGetUbLocal(indicator) <= 0.5 )
1705 { /* this case is stronger as it implies that everything is fixed; therefore we are now happy */
1706 assert(!doprobingind);
1707 SCIPfreeBufferArrayNull(scip, &probingvars);
1708 SCIPfreeBufferArrayNull(scip, &probingdoms);
1709 goto TERMINATE;
1710 }
1711
1712 if( doprobingind )
1713 {
1714 SCIP_Bool propagate;
1715 SCIP_Bool cutoff_probing = FALSE;
1716 SCIP_Bool cutoff;
1717 SCIP_Bool fixed;
1718
1719#ifndef NDEBUG
1720 SCIP_Real* solvals;
1721 SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nlhdlrexprdata->nvars) );
1722 for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1723 {
1724 solvals[v] = SCIPgetSolVal(scip, sol, nlhdlrexprdata->vars[v]);
1725 }
1726#endif
1727
1728 propagate = SCIPgetDepth(scip) == 0;
1729
1730 SCIP_CALL( startProbing(scip, nlhdlrdata, nlhdlrexprdata, indicator, probingvars, probingdoms, nprobingvars,
1731 sol, &solcopy, &cutoff_probing) );
1732
1733#ifndef NDEBUG
1734 for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1735 {
1736 assert(solvals[v] == SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->vars[v])); /*lint !e777*/
1737 }
1738 SCIPfreeBufferArray(scip, &solvals);
1739#endif
1740
1741 SCIPfreeBufferArrayNull(scip, &probingvars);
1742 SCIPfreeBufferArrayNull(scip, &probingdoms);
1743
1744 if( propagate )
1745 { /* we are in the root node and startProbing did propagation */
1746 /* probing propagation might have detected infeasibility */
1747 if( cutoff_probing )
1748 {
1749 /* indicator == 1 is infeasible -> set indicator to 0 */
1750
1752
1753 SCIP_CALL( SCIPfixVar(scip, indicator, 0.0, &cutoff, &fixed) );
1754
1755 if( cutoff )
1756 {
1757 *result = SCIP_CUTOFF;
1758 goto TERMINATE;
1759 }
1760
1761 continue;
1762 }
1763
1764 /* probing propagation in the root node can provide better on/off bounds */
1765 SCIP_CALL( tightenOnBounds(nlhdlrexprdata, nlhdlrdata->scvars, indicator) );
1766 }
1767 }
1768
1769 if( adjrefpoint )
1770 {
1771 /* make sure that when we adjust the point, we don't divide by something too close to 0.0 */
1772 indval = MAX(solval, 0.1);
1773
1774 /* create an adjusted point x^adj = (x* - x0) / z* + x0 */
1775 SCIP_CALL( SCIPcreateSol(scip, &soladj, NULL) );
1776 for( v = 0; v < nlhdlrexprdata->nvars; ++v )
1777 {
1778 if( SCIPvarGetStatus(nlhdlrexprdata->vars[v]) == SCIP_VARSTATUS_FIXED )
1779 continue;
1780
1781 scvdata = getSCVarDataInd(nlhdlrdata->scvars, nlhdlrexprdata->vars[v], indicator, &pos);
1782
1783 /* a non-semicontinuous variable must be linear in expr; skip it */
1784 if( scvdata == NULL )
1785 continue;
1786
1787 SCIP_CALL( SCIPsetSolVal(scip, soladj, nlhdlrexprdata->vars[v],
1788 (SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->vars[v]) - scvdata->vals0[pos]) / indval
1789 + scvdata->vals0[pos]) );
1790 }
1791 for( v = 0; v < nlhdlrexprdata->nindicators; ++v )
1792 {
1793 if( SCIPvarGetStatus(nlhdlrexprdata->indicators[v]) == SCIP_VARSTATUS_FIXED )
1794 continue;
1795
1796 SCIP_CALL( SCIPsetSolVal(scip, soladj, nlhdlrexprdata->indicators[v],
1797 SCIPgetSolVal(scip, solcopy, nlhdlrexprdata->indicators[v])) );
1798 }
1799 if( SCIPvarGetStatus(auxvar) != SCIP_VARSTATUS_FIXED )
1800 {
1801 SCIP_CALL( SCIPsetSolVal(scip, soladj, auxvar, SCIPgetSolVal(scip, solcopy, auxvar)) );
1802 }
1803 }
1804
1805 /* use cuts from every suitable nlhdlr */
1806 for( j = 0; j < nenfos; ++j )
1807 {
1808 SCIP_Bool addedbranchscores2j;
1809 SCIP_NLHDLR* nlhdlr2;
1810 SCIP_NLHDLREXPRDATA* nlhdlr2exprdata;
1811 SCIP_Real nlhdlr2auxvalue;
1812 SCIP_Bool success2;
1813
1814 SCIPgetExprEnfoDataNonlinear(expr, enfoposs[j], &nlhdlr2, &nlhdlr2exprdata, NULL, NULL, NULL, &nlhdlr2auxvalue);
1815 assert(SCIPnlhdlrHasEstimate(nlhdlr2) && nlhdlr2 != nlhdlr);
1816
1817 SCIPdebugMsg(scip, "asking nonlinear handler %s to %sestimate\n", SCIPnlhdlrGetName(nlhdlr2), overestimate ? "over" : "under");
1818
1819 /* ask the nonlinear handler for an estimator */
1820 if( adjrefpoint )
1821 {
1822 SCIP_CALL( SCIPnlhdlrEvalaux(scip, nlhdlr2, expr, nlhdlr2exprdata, &nlhdlr2auxvalue, soladj) );
1823
1824 /* coverity[copy_paste_error] */
1825 SCIP_CALL( SCIPnlhdlrEstimate(scip, conshdlr, nlhdlr2, expr,
1826 nlhdlr2exprdata, soladj,
1827 nlhdlr2auxvalue, overestimate, SCIPgetSolVal(scip, solcopy, auxvar),
1828 FALSE, rowpreps2, &success2, &addedbranchscores2j) );
1829 }
1830 else
1831 {
1832 SCIP_CALL( SCIPnlhdlrEstimate(scip, conshdlr, nlhdlr2, expr,
1833 nlhdlr2exprdata, solcopy,
1834 nlhdlr2auxvalue, overestimate, SCIPgetSolVal(scip, solcopy, auxvar),
1835 FALSE, rowpreps2, &success2, &addedbranchscores2j) );
1836 }
1837
1838 minidx = SCIPgetPtrarrayMinIdx(scip, rowpreps2);
1839 maxidx = SCIPgetPtrarrayMaxIdx(scip, rowpreps2);
1840
1841 assert((success2 && minidx <= maxidx) || (!success2 && minidx > maxidx));
1842
1843 /* perspectivy all cuts from nlhdlr2 and add them to rowpreps */
1844 for( r = minidx; r <= maxidx; ++r )
1845 {
1846 SCIP_Real maxcoef;
1847 SCIP_Real* rowprepcoefs;
1848 SCIP_VAR** rowprepvars;
1849
1850 rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps2, r);
1851 assert(rowprep != NULL);
1852
1853#ifdef SCIP_DEBUG
1854 SCIPinfoMessage(scip, NULL, "rowprep for expr ");
1855 SCIPprintExpr(scip, expr, NULL);
1856 SCIPinfoMessage(scip, NULL, "rowprep before perspectivy is: \n");
1857 SCIPprintRowprep(scip, rowprep, NULL);
1858#endif
1859
1860 /* given a rowprep: sum aixi + sum biyi + c, where xi are semicontinuous variables and yi are
1861 * non-semicontinuous variables (which appear in expr linearly, which detect must have ensured),
1862 * perspectivy the semicontinuous part by adding (1-z)(g0 - c - sum aix0i) (the constant is
1863 * treated as belonging to the semicontinuous part)
1864 */
1865
1866 /* we want cst0 = g0 - c - sum aix0i; first add g0 - c */
1867 cst0 = nlhdlrexprdata->exprvals0[i] + SCIProwprepGetSide(rowprep);
1868
1869 maxcoef = 0.0;
1870 rowprepcoefs = SCIProwprepGetCoefs(rowprep);
1871 rowprepvars = SCIProwprepGetVars(rowprep);
1872
1873 for( v = 0; v < SCIProwprepGetNVars(rowprep); ++v )
1874 {
1875 if( REALABS( rowprepcoefs[v]) > maxcoef )
1876 {
1877 maxcoef = REALABS(rowprepcoefs[v]);
1878 }
1879
1880 scvdata = getSCVarDataInd(nlhdlrdata->scvars, rowprepvars[v], indicator, &pos);
1881
1882 /* a non-semicontinuous variable must be linear in expr; skip it */
1883 if( scvdata == NULL )
1884 continue;
1885
1886 cst0 -= rowprepcoefs[v] * scvdata->vals0[pos];
1887 }
1888
1889 /* only perspectivy when the absolute value of cst0 is not too small
1890 * TODO on ex1252a there was cst0=0 - ok to still use the cut?
1891 */
1892 if( cst0 == 0.0 || maxcoef / REALABS(cst0) <= 10.0 / SCIPfeastol(scip) )
1893 {
1894 /* update the rowprep by adding cst0 - cst0*z */
1895 SCIProwprepAddConstant(rowprep, cst0);
1896 SCIP_CALL(SCIPaddRowprepTerm(scip, rowprep, indicator, -cst0));
1897 }
1898 else
1899 {
1900 SCIPfreeRowprep(scip, &rowprep);
1901 continue;
1902 }
1903
1904 SCIP_CALL(SCIPaddRowprepTerm(scip, rowprep, auxvar, -1.0));
1905
1906 SCIPdebugMsg(scip, "rowprep after perspectivy is: \n");
1907#ifdef SCIP_DEBUG
1908 SCIPprintRowprep(scip, rowprep, NULL);
1909#endif
1910
1911 SCIP_CALL( SCIPsetPtrarrayVal(scip, rowpreps, nrowpreps, rowprep) );
1912 SCIP_CALL( SCIPsetBoolarrayVal(scip, addedbranchscores2, nrowpreps, addedbranchscores2j) );
1913 ++nrowpreps;
1914 }
1915
1916 SCIP_CALL( SCIPclearPtrarray(scip, rowpreps2) );
1917 }
1918
1919 if( adjrefpoint )
1920 {
1921 SCIP_CALL( SCIPfreeSol(scip, &soladj) );
1922 }
1923
1924 if( doprobingind )
1925 {
1927 }
1928
1929 /* add all cuts found for indicator i */
1930 for( r = SCIPgetPtrarrayMinIdx(scip, rowpreps); r <= SCIPgetPtrarrayMaxIdx(scip, rowpreps) && !stop; ++r )
1931 {
1932 SCIP_RESULT resultr;
1933
1934#ifdef SCIP_DEBUG
1935 SCIPprintRowprep(scip, rowprep, NULL);
1936#endif
1937 rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps, r);
1938 resultr = SCIP_DIDNOTFIND;
1939
1940 (void) strcat(SCIProwprepGetName(rowprep), "_persp_indicator_");
1941 (void) strcat(SCIProwprepGetName(rowprep), SCIPvarGetName(indicator));
1942
1943 SCIP_CALL( SCIPprocessRowprepNonlinear(scip, nlhdlr, cons, expr, rowprep, overestimate, auxvar, auxvalue,
1944 allowweakcuts, SCIPgetBoolarrayVal(scip, addedbranchscores2, r), FALSE, solcopy, &resultr) );
1945
1946 if( resultr == SCIP_SEPARATED )
1947 *result = SCIP_SEPARATED;
1948 else if( resultr == SCIP_CUTOFF )
1949 {
1950 *result = SCIP_CUTOFF;
1951 stop = TRUE;
1952 }
1953 else if( resultr == SCIP_BRANCHED )
1954 {
1955 if( *result != SCIP_SEPARATED && *result != SCIP_REDUCEDDOM )
1956 *result = SCIP_BRANCHED;
1957 }
1958 else if( resultr != SCIP_DIDNOTFIND )
1959 {
1960 SCIPerrorMessage("estimate called by perspective nonlinear handler returned invalid result <%d>\n", resultr);
1961 return SCIP_INVALIDRESULT;
1962 }
1963 }
1964
1965 /* free all rowpreps for indicator i */
1966 for( r = SCIPgetPtrarrayMinIdx(scip, rowpreps); r <= SCIPgetPtrarrayMaxIdx(scip, rowpreps); ++r )
1967 {
1968 rowprep = (SCIP_ROWPREP*) SCIPgetPtrarrayVal(scip, rowpreps, r);
1969 SCIPfreeRowprep(scip, &rowprep);
1970 }
1971
1972 SCIP_CALL( SCIPclearPtrarray(scip, rowpreps) );
1973 }
1974
1975TERMINATE:
1976 SCIP_CALL( SCIPfreeBoolarray(scip, &addedbranchscores2) );
1977 SCIP_CALL( SCIPfreePtrarray(scip, &rowpreps) );
1978 SCIP_CALL( SCIPfreePtrarray(scip, &rowpreps2) );
1979 if( solcopy != sol )
1980 {
1981 SCIP_CALL( SCIPfreeSol(scip, &solcopy) );
1982 }
1983 SCIPfreeBufferArray(scip, &enfoposs);
1984
1985 return SCIP_OKAY;
1986}
1987
1988
1989/*
1990 * nonlinear handler specific interface methods
1991 */
1992
1993/** includes perspective nonlinear handler in nonlinear constraint handler */
1995 SCIP* scip /**< SCIP data structure */
1996 )
1997{
1998 SCIP_NLHDLRDATA* nlhdlrdata;
1999 SCIP_NLHDLR* nlhdlr;
2000
2001 assert(scip != NULL);
2002
2003 /* create nonlinear handler data */
2004 SCIP_CALL( SCIPallocBlockMemory(scip, &nlhdlrdata) );
2005 BMSclearMemory(nlhdlrdata);
2006
2008 NLHDLR_ENFOPRIORITY, nlhdlrDetectPerspective, nlhdlrEvalauxPerspective, nlhdlrdata) );
2009 assert(nlhdlr != NULL);
2010
2011 SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/maxproprounds",
2012 "maximal number of propagation rounds in probing",
2013 &nlhdlrdata->maxproprounds, FALSE, DEFAULT_MAXPROPROUNDS, -1, INT_MAX, NULL, NULL) );
2014
2015 SCIP_CALL( SCIPaddRealParam(scip, "nlhdlr/" NLHDLR_NAME "/mindomreduction",
2016 "minimal relative reduction in a variable's domain for applying probing",
2017 &nlhdlrdata->mindomreduction, FALSE, DEFAULT_MINDOMREDUCTION, 0.0, 1.0, NULL, NULL) );
2018
2019 SCIP_CALL( SCIPaddRealParam(scip, "nlhdlr/" NLHDLR_NAME "/minviolprobing",
2020 "minimal violation w.r.t. auxiliary variables for applying probing",
2021 &nlhdlrdata->minviolprobing, FALSE, DEFAULT_MINVIOLPROBING, 0.0, SCIP_REAL_MAX, NULL, NULL) );
2022
2023 SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/probingonlyinsepa",
2024 "whether to do probing only in separation",
2025 &nlhdlrdata->probingonlyinsepa, FALSE, DEFAULT_PROBINGONLYINSEPA, NULL, NULL) );
2026
2027 SCIP_CALL( SCIPaddIntParam(scip, "nlhdlr/" NLHDLR_NAME "/probingfreq",
2028 "probing frequency (-1 - no probing, 0 - root node only)",
2029 &nlhdlrdata->probingfreq, FALSE, DEFAULT_PROBINGFREQ, -1, INT_MAX, NULL, NULL) );
2030
2031 SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/convexonly",
2032 "whether perspective cuts are added only for convex expressions",
2033 &nlhdlrdata->convexonly, FALSE, DEFAULT_CONVEXONLY, NULL, NULL) );
2034
2035 SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/tightenbounds",
2036 "whether variable semicontinuity is used to tighten variable bounds",
2037 &nlhdlrdata->tightenbounds, FALSE, DEFAULT_TIGHTENBOUNDS, NULL, NULL) );
2038
2039 SCIP_CALL( SCIPaddBoolParam(scip, "nlhdlr/" NLHDLR_NAME "/adjrefpoint",
2040 "whether to adjust the reference point",
2041 &nlhdlrdata->adjrefpoint, FALSE, DEFAULT_ADJREFPOINT, NULL, NULL) );
2042
2043 SCIPnlhdlrSetCopyHdlr(nlhdlr, nlhdlrCopyhdlrPerspective);
2044 SCIPnlhdlrSetFreeHdlrData(nlhdlr, nlhdlrFreehdlrdataPerspective);
2045 SCIPnlhdlrSetFreeExprData(nlhdlr, nlhdlrFreeExprDataPerspective);
2046 SCIPnlhdlrSetInitExit(nlhdlr, NULL, nlhdlrExitPerspective);
2047 SCIPnlhdlrSetSepa(nlhdlr, nlhdlrInitSepaPerspective, nlhdlrEnfoPerspective, NULL, NULL);
2048
2049 return SCIP_OKAY;
2050}
SCIP_VAR ** b
Definition: circlepacking.c:65
SCIP_Real * r
Definition: circlepacking.c:59
constraint handler for nonlinear constraints specified by algebraic expressions
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_REAL_MAX
Definition: def.h:174
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
void SCIPcomputeArraysIntersectionPtr(void **array1, int narray1, void **array2, int narray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void **intersectarray, int *nintersectarray)
Definition: misc.c:10612
unsigned int SCIPgetExprNAuxvarUsesNonlinear(SCIP_EXPR *expr)
void SCIPgetExprEnfoDataNonlinear(SCIP_EXPR *expr, int idx, SCIP_NLHDLR **nlhdlr, SCIP_NLHDLREXPRDATA **nlhdlrexprdata, SCIP_NLHDLR_METHOD *nlhdlrparticipation, SCIP_Bool *sepabelowusesactivity, SCIP_Bool *sepaaboveusesactivity, SCIP_Real *auxvalue)
void SCIPsetExprEnfoAuxValueNonlinear(SCIP_EXPR *expr, int idx, SCIP_Real auxvalue)
SCIP_VAR * SCIPgetExprAuxVarNonlinear(SCIP_EXPR *expr)
SCIP_RETCODE SCIPprocessRowprepNonlinear(SCIP *scip, SCIP_NLHDLR *nlhdlr, SCIP_CONS *cons, SCIP_EXPR *expr, SCIP_ROWPREP *rowprep, SCIP_Bool overestimate, SCIP_VAR *auxvar, SCIP_Real auxvalue, SCIP_Bool allowweakcuts, SCIP_Bool branchscoresuccess, SCIP_Bool inenforcement, SCIP_SOL *sol, SCIP_RESULT *result)
int SCIPgetExprNEnfosNonlinear(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)
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2605
int SCIPgetNVars(SCIP *scip)
Definition: scip_prob.c:1992
int SCIPgetNBinVars(SCIP *scip)
Definition: scip_prob.c:2037
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapEntryGetImage(SCIP_HASHMAPENTRY *entry)
Definition: misc.c:3570
int SCIPhashmapGetImageInt(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3281
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
int SCIPhashmapGetNEntries(SCIP_HASHMAP *hashmap)
Definition: misc.c:3541
SCIP_HASHMAPENTRY * SCIPhashmapGetEntry(SCIP_HASHMAP *hashmap, int entryidx)
Definition: misc.c:3549
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_RETCODE SCIPhashmapSetImageInt(SCIP_HASHMAP *hashmap, void *origin, int image)
Definition: misc.c:3357
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsgPrint
Definition: scip_message.h:79
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPincludeNlhdlrPerspective(SCIP *scip)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:83
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:139
SCIP_RETCODE 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
int SCIPgetPtrarrayMinIdx(SCIP *scip, SCIP_PTRARRAY *ptrarray)
SCIP_Bool SCIPgetBoolarrayVal(SCIP *scip, SCIP_BOOLARRAY *boolarray, int idx)
SCIP_RETCODE SCIPclearPtrarray(SCIP *scip, SCIP_PTRARRAY *ptrarray)
void * SCIPgetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx)
SCIP_RETCODE SCIPfreePtrarray(SCIP *scip, SCIP_PTRARRAY **ptrarray)
SCIP_RETCODE SCIPfreeBoolarray(SCIP *scip, SCIP_BOOLARRAY **boolarray)
int SCIPgetPtrarrayMaxIdx(SCIP *scip, SCIP_PTRARRAY *ptrarray)
SCIP_RETCODE SCIPsetPtrarrayVal(SCIP *scip, SCIP_PTRARRAY *ptrarray, int idx, void *val)
SCIP_RETCODE SCIPcreateBoolarray(SCIP *scip, SCIP_BOOLARRAY **boolarray)
SCIP_RETCODE SCIPsetBoolarrayVal(SCIP *scip, SCIP_BOOLARRAY *boolarray, int idx, SCIP_Bool val)
SCIP_RETCODE SCIPcreatePtrarray(SCIP *scip, SCIP_PTRARRAY **ptrarray)
SCIP_RETCODE SCIPevalExpr(SCIP *scip, SCIP_EXPR *expr, SCIP_SOL *sol, SCIP_Longint soltag)
Definition: scip_expr.c:1635
int SCIPexprGetNChildren(SCIP_EXPR *expr)
Definition: expr.c:3860
SCIP_Bool SCIPexpriterIsEnd(SCIP_EXPRITER *iterator)
Definition: expriter.c:969
SCIP_Bool SCIPisExprSum(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1453
SCIP_RETCODE SCIPgetExprNVars(SCIP *scip, SCIP_EXPR *expr, int *nvars)
Definition: scip_expr.c:2058
SCIP_RETCODE SCIPreleaseExpr(SCIP *scip, SCIP_EXPR **expr)
Definition: scip_expr.c:1417
SCIP_EXPR * SCIPexpriterGetCurrent(SCIP_EXPRITER *iterator)
Definition: expriter.c:683
SCIP_Bool SCIPisExprVar(SCIP *scip, SCIP_EXPR *expr)
Definition: scip_expr.c:1431
SCIP_RETCODE SCIPcreateExpriter(SCIP *scip, SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2337
SCIP_RETCODE SCIPprintExpr(SCIP *scip, SCIP_EXPR *expr, FILE *file)
Definition: scip_expr.c:1486
SCIP_Real SCIPexprGetEvalValue(SCIP_EXPR *expr)
Definition: expr.c:3934
SCIP_EXPR * SCIPexpriterGetNext(SCIP_EXPRITER *iterator)
Definition: expriter.c:858
SCIP_EXPR ** SCIPexprGetChildren(SCIP_EXPR *expr)
Definition: expr.c:3870
SCIP_VAR * SCIPgetVarExprVar(SCIP_EXPR *expr)
Definition: expr_var.c:416
void SCIPfreeExpriter(SCIP_EXPRITER **iterator)
Definition: scip_expr.c:2351
SCIP_RETCODE SCIPexpriterInit(SCIP_EXPRITER *iterator, SCIP_EXPR *expr, SCIP_EXPRITER_TYPE type, SCIP_Bool allowrevisit)
Definition: expriter.c:501
SCIP_RETCODE SCIPgetExprVarExprs(SCIP *scip, SCIP_EXPR *expr, SCIP_EXPR **varexprs, int *nvarexprs)
Definition: scip_expr.c:2096
SCIP_Real SCIPintervalGetInf(SCIP_INTERVAL interval)
SCIP_Real SCIPintervalGetSup(SCIP_INTERVAL interval)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocClearBlockMemory(scip, ptr)
Definition: scip_mem.h:91
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
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 SCIPduplicateBufferArray(scip, ptr, source, num)
Definition: scip_mem.h:132
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
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
SCIP_NLHDLRDATA * SCIPnlhdlrGetData(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:216
void SCIPnlhdlrSetFreeHdlrData(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRFREEHDLRDATA((*freehdlrdata)))
Definition: nlhdlr.c:87
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
void SCIPnlhdlrSetInitExit(SCIP_NLHDLR *nlhdlr, SCIP_DECL_NLHDLRINIT((*init)), SCIP_DECL_NLHDLREXIT((*exit_)))
Definition: nlhdlr.c:110
const char * SCIPnlhdlrGetName(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:166
SCIP_Bool SCIPnlhdlrHasEstimate(SCIP_NLHDLR *nlhdlr)
Definition: nlhdlr.c:276
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 SCIPchgVarUbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:345
SCIP_RETCODE SCIPchgVarLbProbing(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
Definition: scip_probing.c:301
SCIP_RETCODE SCIPpropagateProbing(SCIP *scip, int maxproprounds, SCIP_Bool *cutoff, SCIP_Longint *ndomredsfound)
Definition: scip_probing.c:580
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
SCIP_RETCODE SCIPstartProbing(SCIP *scip)
Definition: scip_probing.c:119
SCIP_RETCODE SCIPnewProbingNode(SCIP *scip)
Definition: scip_probing.c:165
SCIP_RETCODE SCIPendProbing(SCIP *scip)
Definition: scip_probing.c:260
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
Definition: scip_sol.c:184
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
Definition: scip_sol.c:841
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1119
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
Definition: scip_sol.c:1077
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPgetDepth(SCIP *scip)
Definition: scip_tree.c:670
SCIP_RETCODE SCIPtightenVarLb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5203
int SCIPvarGetNVlbs(SCIP_VAR *var)
Definition: var.c:18270
SCIP_Real * SCIPvarGetVlbCoefs(SCIP_VAR *var)
Definition: var.c:18292
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition: var.c:17538
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_RETCODE SCIPtightenVarUb(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5320
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real * SCIPvarGetVlbConstants(SCIP_VAR *var)
Definition: var.c:18302
int SCIPvarGetNVubs(SCIP_VAR *var)
Definition: var.c:18312
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Bool SCIPvarIsRelaxationOnly(SCIP_VAR *var)
Definition: var.c:17706
SCIP_VAR ** SCIPvarGetVlbVars(SCIP_VAR *var)
Definition: var.c:18282
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_Real * SCIPvarGetVubConstants(SCIP_VAR *var)
Definition: var.c:18344
SCIP_VAR ** SCIPvarGetVubVars(SCIP_VAR *var)
Definition: var.c:18324
SCIP_Real * SCIPvarGetVubCoefs(SCIP_VAR *var)
Definition: var.c:18334
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
SCIP_VAR ** SCIProwprepGetVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:639
SCIP_Real SCIProwprepGetSide(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:659
SCIP_Real * SCIProwprepGetCoefs(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:649
char * SCIProwprepGetName(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:689
void SCIProwprepAddConstant(SCIP_ROWPREP *rowprep, SCIP_Real constant)
Definition: misc_rowprep.c:760
SCIP_RETCODE SCIPaddRowprepTerm(SCIP *scip, SCIP_ROWPREP *rowprep, SCIP_VAR *var, SCIP_Real coef)
Definition: misc_rowprep.c:913
int SCIProwprepGetNVars(SCIP_ROWPREP *rowprep)
Definition: misc_rowprep.c:629
void SCIPfreeRowprep(SCIP *scip, SCIP_ROWPREP **rowprep)
Definition: misc_rowprep.c:583
void SCIPprintRowprep(SCIP *scip, SCIP_ROWPREP *rowprep, FILE *file)
Definition: misc_rowprep.c:801
SCIP_Bool SCIPsortedvecFindPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), void *val, int len, int *pos)
void SCIPsortPtr(void **ptrarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define BMSclearMemory(ptr)
Definition: memory.h:129
private functions of nonlinear handlers of nonlinear constraints
static SCIP_RETCODE varIsSemicontinuous(SCIP *scip, SCIP_VAR *var, SCIP_HASHMAP *scvars, SCIP_Bool *result)
static SCIP_DECL_NLHDLRENFO(nlhdlrEnfoPerspective)
#define NLHDLR_DETECTPRIORITY
static SCIP_DECL_NLHDLRINITSEPA(nlhdlrInitSepaPerspective)
static SCIP_RETCODE tightenOnBounds(SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_HASHMAP *scvars, SCIP_VAR *indicator)
#define DEFAULT_MINVIOLPROBING
#define NLHDLR_ENFOPRIORITY
static SCIP_RETCODE freeNlhdlrExprData(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata)
static SCIP_RETCODE startProbing(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *indicator, SCIP_VAR **probingvars, SCIP_INTERVAL *probingdoms, int nprobingvars, SCIP_SOL *sol, SCIP_SOL **solcopy, SCIP_Bool *cutoff_probing)
static SCIP_RETCODE removeIndicator(SCIP *scip, SCIP_NLHDLREXPRDATA *nlexprdata, int pos)
static SCIP_RETCODE exprIsSemicontinuous(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_EXPR *expr, SCIP_Bool *res)
static SCIP_DECL_NLHDLREVALAUX(nlhdlrEvalauxPerspective)
#define DEFAULT_TIGHTENBOUNDS
#define DEFAULT_ADJREFPOINT
static SCIP_RETCODE analyseVarOnoffBounds(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_VAR *var, SCIP_VAR *indicator, SCIP_Bool indvalue, SCIP_Bool *infeas, SCIP_Real *probinglb, SCIP_Real *probingub, SCIP_Bool doprobing, SCIP_Bool *reduceddom)
#define NLHDLR_DESC
static SCIP_DECL_NLHDLRCOPYHDLR(nlhdlrCopyhdlrPerspective)
#define DEFAULT_MINDOMREDUCTION
#define DEFAULT_PROBINGFREQ
static SCIP_RETCODE addAuxVar(SCIP *scip, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_HASHMAP *auxvarmap, SCIP_VAR *auxvar)
static SCIP_DECL_NLHDLRDETECT(nlhdlrDetectPerspective)
#define NLHDLR_NAME
#define DEFAULT_PROBINGONLYINSEPA
#define DEFAULT_CONVEXONLY
static SCIP_RETCODE analyseOnoffBounds(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_VAR *indicator, SCIP_VAR ***probingvars, SCIP_INTERVAL **probingdoms, int *nprobingvars, SCIP_Bool *doprobing, SCIP_RESULT *result)
static SCIP_RETCODE addSCVarIndicator(SCIP *scip, SCVARDATA *scvdata, SCIP_VAR *indicator, SCIP_Real val0, SCIP_Real lb1, SCIP_Real ub1)
static SCIP_DECL_NLHDLRFREEHDLRDATA(nlhdlrFreehdlrdataPerspective)
static SCIP_DECL_NLHDLRFREEEXPRDATA(nlhdlrFreeExprDataPerspective)
static SCIP_RETCODE computeOffValues(SCIP *scip, SCIP_NLHDLRDATA *nlhdlrdata, SCIP_NLHDLREXPRDATA *nlhdlrexprdata, SCIP_EXPR *expr)
#define DEFAULT_MAXPROPROUNDS
static SCIP_DECL_NLHDLREXIT(nlhdlrExitPerspective)
static SCVARDATA * getSCVarDataInd(SCIP_HASHMAP *scvars, SCIP_VAR *var, SCIP_VAR *indicator, int *pos)
perspective nonlinear handler
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
#define SCIPerrorMessage
Definition: pub_message.h:64
preparation of a linear inequality to become a SCIP_ROW
public methods for solutions
SCIP_Real * vals0
SCIP_VAR ** bvars
SCIP_Real * ubs1
SCIP_Real * lbs1
@ SCIP_EXPRITER_DFS
Definition: type_expr.h:716
#define SCIP_NLHDLR_METHOD_SEPAABOVE
Definition: type_nlhdlr.h:52
struct SCIP_NlhdlrData SCIP_NLHDLRDATA
Definition: type_nlhdlr.h:452
#define SCIP_NLHDLR_METHOD_SEPABOTH
Definition: type_nlhdlr.h:53
#define SCIP_DECL_NLHDLRINIT(x)
Definition: type_nlhdlr.h:105
unsigned int SCIP_NLHDLR_METHOD
Definition: type_nlhdlr.h:57
#define SCIP_DECL_NLHDLREXITSEPA(x)
Definition: type_nlhdlr.h:290
struct SCIP_NlhdlrExprData SCIP_NLHDLREXPRDATA
Definition: type_nlhdlr.h:453
#define SCIP_NLHDLR_METHOD_SEPABELOW
Definition: type_nlhdlr.h:51
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_BRANCHED
Definition: type_result.h:54
@ SCIP_SEPARATED
Definition: type_result.h:49
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_INVALIDRESULT
Definition: type_retcode.h:53
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_VARSTATUS_FIXED
Definition: type_var.h:52