1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15
16 /**@file cons_bounddisjunction.c
17 * @ingroup DEFPLUGINS_CONS
18 * @brief constraint handler for bound disjunction constraints \f$(x_1 \{\leq,\geq\} b_1) \vee \ldots \vee (x_n \{\leq,\geq\} b_n)\f$
19 * @author Tobias Achterberg
20 * @author Marc Pfetsch
21 */
22
23 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
24
25 #include "blockmemshell/memory.h"
26 #include "scip/cons_bounddisjunction.h"
27 #include "scip/cons_linear.h"
28 #include "scip/cons_logicor.h"
29 #include "scip/cons_quadratic.h"
30 #include "scip/cons_setppc.h"
31 #include "scip/pub_conflict.h"
32 #include "scip/pub_cons.h"
33 #include "scip/pub_event.h"
34 #include "scip/pub_lp.h"
35 #include "scip/pub_message.h"
36 #include "scip/pub_misc.h"
37 #include "scip/pub_var.h"
38 #include "scip/scip_branch.h"
39 #include "scip/scip_conflict.h"
40 #include "scip/scip_cons.h"
41 #include "scip/scip_copy.h"
42 #include "scip/scip_event.h"
43 #include "scip/scip_general.h"
44 #include "scip/scip_mem.h"
45 #include "scip/scip_message.h"
46 #include "scip/scip_numerics.h"
47 #include "scip/scip_param.h"
48 #include "scip/scip_prob.h"
49 #include "scip/scip_probing.h"
50 #include "scip/scip_sol.h"
51 #include "scip/scip_solvingstats.h"
52 #include "scip/scip_tree.h"
53 #include "scip/scip_var.h"
54 #include <ctype.h>
55 #include <string.h>
56
57 /**@name Constraint handler properties
58 *
59 * @{
60 */
61
62 #define CONSHDLR_NAME "bounddisjunction"
63 #define CONSHDLR_DESC "bound disjunction constraints"
64 #define CONSHDLR_ENFOPRIORITY -3000000 /**< priority of the constraint handler for constraint enforcing */
65 #define CONSHDLR_CHECKPRIORITY -3000000 /**< priority of the constraint handler for checking feasibility */
66 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
67 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
68 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
69 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
70 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
71 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
72
73 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
74 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
75
76 #define QUADCONSUPGD_PRIORITY 500000 /**< priority of the constraint handler for upgrading of quadratic constraints */
77
78 /**@} */
79
80 /**@name Event handler properties
81 *
82 * @{
83 */
84
85 #define EVENTHDLR_NAME "bounddisjunction"
86 #define EVENTHDLR_DESC "event handler for bound disjunction constraints"
87
88 /**@} */
89
90 /**@name Conflict handler properties
91 *
92 * @{
93 */
94
95 #define CONFLICTHDLR_NAME "bounddisjunction"
96 #define CONFLICTHDLR_DESC "conflict handler creating bound disjunction constraints"
97 #define CONFLICTHDLR_PRIORITY -3000000
98
99 /**@} */
100
101 /**@name Default parameter values
102 *
103 * @{
104 */
105
106 #define DEFAULT_CONTINUOUSFRAC 0.4 /**< maximal percantage of continuous variables within a conflict */
107
108 /**@} */
109
110 /**@name Age increase defines
111 *
112 * @{
113 */
114
115 /* @todo make this a parameter setting */
116 #if 1 /* @todo test which AGEINCREASE formula is better! */
117 #define AGEINCREASE(n) (1.0 + 0.2*n)
118 #else
119 #define AGEINCREASE(n) (0.1*n)
120 #endif
121
122 /**@} */
123
124
125 /**@name Comparison for two values
126 *
127 * @{
128 */
129
130 #ifdef SCIP_DISABLED_CODE /* These only work if one also passes integral values in case of integral variables. This is not always the case and not even asserted. */
131 /** use defines for numeric compare methods to be slightly faster for integral values */
132 #define isFeasLT(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val2) - (val1) > 0.5 : SCIPisFeasLT(scip, val1, val2))
133 #define isFeasLE(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val2) - (val1) > -0.5 : SCIPisFeasLE(scip, val1, val2))
134 #define isFeasGT(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val1) - (val2) > 0.5 : SCIPisFeasGT(scip, val1, val2))
135 #define isFeasGE(scip, var, val1, val2) (SCIPvarIsIntegral(var) ? (val1) - (val2) > -0.5 : SCIPisFeasGE(scip, val1, val2))
136 #else
137 #define isFeasLT(scip, var, val1, val2) SCIPisFeasLT(scip, val1, val2)
138 #define isFeasLE(scip, var, val1, val2) SCIPisFeasLE(scip, val1, val2)
139 #define isFeasGT(scip, var, val1, val2) SCIPisFeasGT(scip, val1, val2)
140 #define isFeasGE(scip, var, val1, val2) SCIPisFeasGE(scip, val1, val2)
141 #endif
142 /**@} */
143
144
145 /** constraint handler data */
146 struct SCIP_ConshdlrData
147 {
148 SCIP_EVENTHDLR* eventhdlr; /**< event handler for events on watched variables */
149 };
150
151 /** bound disjunction constraint data */
152 struct SCIP_ConsData
153 {
154 SCIP_VAR** vars; /**< variables of the literals in the constraint */
155 SCIP_BOUNDTYPE* boundtypes; /**< types of bounds of the literals (lower or upper bounds) */
156 SCIP_Real* bounds; /**< bounds of the literals */
157 int varssize; /**< size of vars, boundtypes, and bounds arrays */
158 int nvars; /**< number of variables in the constraint */
159 int watchedvar1; /**< position of the first watched variable */
160 int watchedvar2; /**< position of the second watched variable */
161 int filterpos1; /**< event filter position of first watched variable */
162 int filterpos2; /**< event filter position of second watched variable */
163 };
164
165 /**@name Local methods
166 *
167 * @{
168 */
169
170 /** adds rounding locks for the given variable in the given bound disjunction constraint */
171 static
lockRounding(SCIP * scip,SCIP_CONS * cons,SCIP_CONSDATA * consdata,int pos)172 SCIP_RETCODE lockRounding(
173 SCIP* scip, /**< SCIP data structure */
174 SCIP_CONS* cons, /**< bound disjunction constraint */
175 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
176 int pos /**< position of the variable in the constraint */
177 )
178 {
179 assert(consdata != NULL);
180 assert(0 <= pos && pos < consdata->nvars);
181
182 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
183 {
184 SCIP_CALL( SCIPlockVarCons(scip, consdata->vars[pos], cons, TRUE, FALSE) );
185 }
186 else
187 {
188 SCIP_CALL( SCIPlockVarCons(scip, consdata->vars[pos], cons, FALSE, TRUE) );
189 }
190
191 return SCIP_OKAY;
192 }
193
194 /** removes rounding locks for the given variable in the given bound disjunction constraint */
195 static
unlockRounding(SCIP * scip,SCIP_CONS * cons,SCIP_CONSDATA * consdata,int pos)196 SCIP_RETCODE unlockRounding(
197 SCIP* scip, /**< SCIP data structure */
198 SCIP_CONS* cons, /**< bound disjunction constraint */
199 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
200 int pos /**< position of the variable in the constraint */
201 )
202 {
203 assert(consdata != NULL);
204 assert(0 <= pos && pos < consdata->nvars);
205
206 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
207 {
208 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, TRUE, FALSE) );
209 }
210 else
211 {
212 SCIP_CALL( SCIPunlockVarCons(scip, consdata->vars[pos], cons, FALSE, TRUE) );
213 }
214
215 return SCIP_OKAY;
216 }
217
218 /** catches the events on a single variable of the bound disjunction constraint */
219 static
catchEvents(SCIP * scip,SCIP_CONS * cons,SCIP_CONSDATA * consdata,SCIP_EVENTHDLR * eventhdlr,int pos,int * filterpos)220 SCIP_RETCODE catchEvents(
221 SCIP* scip, /**< SCIP data structure */
222 SCIP_CONS* cons, /**< bound disjunction constraint */
223 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
224 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
225 int pos, /**< position of the variable in the constraint */
226 int* filterpos /**< pointer to store position of event filter entry, or NULL */
227 )
228 {
229 assert(consdata != NULL);
230 assert(0 <= pos && pos < consdata->nvars);
231
232 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
233 {
234 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED,
235 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
236 }
237 else
238 {
239 SCIP_CALL( SCIPcatchVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_UBRELAXED,
240 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
241 }
242
243 return SCIP_OKAY;
244 }
245
246 /** drops the events on a single variable of the bound disjunction constraint */
247 static
dropEvents(SCIP * scip,SCIP_CONS * cons,SCIP_CONSDATA * consdata,SCIP_EVENTHDLR * eventhdlr,int pos,int filterpos)248 SCIP_RETCODE dropEvents(
249 SCIP* scip, /**< SCIP data structure */
250 SCIP_CONS* cons, /**< bound disjunction constraint */
251 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
252 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
253 int pos, /**< position of the variable in the constraint */
254 int filterpos /**< position of event filter entry returned by SCIPcatchVarEvent(), or -1 */
255 )
256 {
257 assert(consdata != NULL);
258 assert(0 <= pos && pos < consdata->nvars);
259
260 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
261 {
262 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_UBTIGHTENED | SCIP_EVENTTYPE_LBRELAXED,
263 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
264 }
265 else
266 {
267 SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_LBTIGHTENED | SCIP_EVENTTYPE_UBRELAXED,
268 eventhdlr, (SCIP_EVENTDATA*)cons, filterpos) );
269 }
270
271 return SCIP_OKAY;
272 }
273
274 /** creates constraint handler data for bound disjunction constraint handler */
275 static
conshdlrdataCreate(SCIP * scip,SCIP_CONSHDLRDATA ** conshdlrdata,SCIP_EVENTHDLR * eventhdlr)276 SCIP_RETCODE conshdlrdataCreate(
277 SCIP* scip, /**< SCIP data structure */
278 SCIP_CONSHDLRDATA** conshdlrdata, /**< pointer to store the constraint handler data */
279 SCIP_EVENTHDLR* eventhdlr /**< event handler */
280 )
281 {
282 assert(scip != NULL);
283 assert(conshdlrdata != NULL);
284 assert(eventhdlr != NULL);
285
286 SCIP_CALL( SCIPallocBlockMemory(scip, conshdlrdata) );
287
288 /* set event handler for catching events on watched variables */
289 (*conshdlrdata)->eventhdlr = eventhdlr;
290
291 return SCIP_OKAY;
292 }
293
294 /** frees constraint handler data for bound disjunction constraint handler */
295 static
conshdlrdataFree(SCIP * scip,SCIP_CONSHDLRDATA ** conshdlrdata)296 void conshdlrdataFree(
297 SCIP* scip, /**< SCIP data structure */
298 SCIP_CONSHDLRDATA** conshdlrdata /**< pointer to the constraint handler data */
299 )
300 {
301 assert(conshdlrdata != NULL);
302 assert(*conshdlrdata != NULL);
303
304 SCIPfreeBlockMemory(scip, conshdlrdata);
305 }
306
307 /** creates a bound disjunction constraint data object */
308 static
consdataCreate(SCIP * scip,SCIP_CONSDATA ** consdata,int nvars,SCIP_VAR ** vars,SCIP_BOUNDTYPE * boundtypes,SCIP_Real * bounds)309 SCIP_RETCODE consdataCreate(
310 SCIP* scip, /**< SCIP data structure */
311 SCIP_CONSDATA** consdata, /**< pointer to store the bound disjunction constraint data */
312 int nvars, /**< number of variables in the constraint */
313 SCIP_VAR** vars, /**< variables of the literals in the constraint */
314 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
315 SCIP_Real* bounds /**< bounds of the literals */
316 )
317 {
318 assert(consdata != NULL);
319 assert(nvars == 0 || vars != NULL);
320 assert(nvars == 0 || boundtypes != NULL);
321 assert(nvars == 0 || bounds != NULL);
322
323 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
324
325 if( nvars > 0 )
326 {
327 if( SCIPisConsCompressionEnabled(scip) )
328 {
329 int k;
330 int v;
331 int nviolations;
332 SCIP_Bool redundant;
333 SCIP_VAR** varsbuffer;
334 SCIP_BOUNDTYPE* boundtypesbuffer;
335 SCIP_Real* boundsbuffer;
336
337 SCIP_CALL( SCIPallocBufferArray(scip, &varsbuffer, nvars) );
338 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesbuffer, nvars) );
339 SCIP_CALL( SCIPallocBufferArray(scip, &boundsbuffer, nvars) );
340
341 nviolations = 0;
342 k = 0;
343 redundant = FALSE;
344 /* loop over variables, compare fixed ones against its bound disjunction */
345 for( v = 0; v < nvars && !redundant; ++v )
346 {
347 SCIP_VAR* var = vars[v];
348 SCIP_BOUNDTYPE boundtype = boundtypes[v];
349 SCIP_Real bound = bounds[v];
350
351 /* is the variable fixed? */
352 if( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) )
353 {
354 if( (boundtype == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPvarGetLbLocal(var), bound))
355 || (boundtype == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPvarGetUbLocal(var), bound)) )
356 {
357 /* save this feasible assignment at the first position */
358 varsbuffer[0] = var;
359 boundtypesbuffer[0] = boundtype;
360 boundsbuffer[0] = bound;
361 k = 1;
362 redundant = TRUE;
363 }
364 else
365 ++nviolations;
366 }
367 else
368 {
369 /* append unfixed variable to buffer */
370 varsbuffer[k] = var;
371 boundtypesbuffer[k] = boundtype;
372 boundsbuffer[k] = bound;
373 ++k;
374 }
375 }
376
377 /* duplicate a single, infeasible assignment, wlog the first one */
378 if( k == 0 )
379 {
380 assert(nviolations == nvars);
381 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, 1) );
382 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypes, 1) );
383 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, bounds, 1) );
384 (*consdata)->varssize = 1;
385 (*consdata)->nvars = 1;
386 }
387 else
388 {
389 /* if the bound disjunction is already trivially satisfied, we keep only a single feasible assignment */
390 assert(!redundant || k == 1);
391
392 /* we only copy the buffered variables required to represent the constraint */
393 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, k) );
394 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypesbuffer, k) );
395 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, boundsbuffer, k) );
396 (*consdata)->varssize = k;
397 (*consdata)->nvars = k;
398 }
399
400 /* free buffer storage */
401 SCIPfreeBufferArray(scip, &boundsbuffer);
402 SCIPfreeBufferArray(scip, &boundtypesbuffer);
403 SCIPfreeBufferArray(scip, &varsbuffer);
404 }
405 else
406 {
407 /* without problem compression, the entire vars array is copied */
408 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, vars, nvars) );
409 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypes, nvars) );
410 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, bounds, nvars) );
411 (*consdata)->varssize = nvars;
412 (*consdata)->nvars = nvars;
413 }
414 }
415 else
416 {
417 (*consdata)->vars = NULL;
418 (*consdata)->boundtypes = NULL;
419 (*consdata)->bounds = NULL;
420 (*consdata)->varssize = 0;
421 (*consdata)->nvars = 0;
422 }
423 (*consdata)->watchedvar1 = -1;
424 (*consdata)->watchedvar2 = -1;
425 (*consdata)->filterpos1 = -1;
426 (*consdata)->filterpos2 = -1;
427
428 /* get transformed variables, if we are in the transformed problem */
429 if( SCIPisTransformed(scip) )
430 {
431 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
432 }
433
434 return SCIP_OKAY;
435 }
436
437 /** creates a bound disjunction constraint data object with possibly redundant literals */
438 static
consdataCreateRedundant(SCIP * scip,SCIP_CONSDATA ** consdata,int nvars,SCIP_VAR ** vars,SCIP_BOUNDTYPE * boundtypes,SCIP_Real * bounds)439 SCIP_RETCODE consdataCreateRedundant(
440 SCIP* scip, /**< SCIP data structure */
441 SCIP_CONSDATA** consdata, /**< pointer to store the bound disjunction constraint data */
442 int nvars, /**< number of variables in the constraint */
443 SCIP_VAR** vars, /**< variables of the literals in the constraint */
444 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
445 SCIP_Real* bounds /**< bounds of the literals */
446 )
447 {
448 assert(consdata != NULL);
449 assert(nvars == 0 || vars != NULL);
450 assert(nvars == 0 || boundtypes != NULL);
451 assert(nvars == 0 || bounds != NULL);
452
453 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
454
455 if( nvars > 0 )
456 {
457 SCIP_BOUNDTYPE* boundtypesbuffer;
458 SCIP_Real* boundsbuffer;
459 SCIP_VAR** varsbuffer;
460 SCIP_VAR* var;
461 int nvarsbuffer = 0;
462 int nviolated = 0;
463 int v;
464
465 SCIP_CALL( SCIPduplicateBufferArray(scip, &varsbuffer, vars, nvars) );
466 SCIP_CALL( SCIPduplicateBufferArray(scip, &boundtypesbuffer, boundtypes, nvars) );
467 SCIP_CALL( SCIPduplicateBufferArray(scip, &boundsbuffer, bounds, nvars) );
468
469 /* sort variables according to index; this allows us to check for redundancy easily below because duplicate
470 * variables must now appear consecutively */
471 SCIPsortPtrRealInt((void**)varsbuffer, boundsbuffer, (int*) boundtypesbuffer, SCIPvarComp, nvars);
472
473 /* filter out redundant literals */
474 for( v = 0; v < nvars; ++v )
475 {
476 int w;
477
478 /* if we should compress fixed variables */
479 if( SCIPisConsCompressionEnabled(scip) && varsbuffer[v] != NULL )
480 {
481 var = varsbuffer[v];
482
483 /* if the variable is fixed */
484 if( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) )
485 {
486 /* If the literal is feasible for the fixed variable, then the whole constraint is feasible. In this
487 * case, we reduce the constraint to only this literal. */
488 if( (boundtypesbuffer[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPvarGetLbLocal(var), boundsbuffer[v]))
489 || (boundtypesbuffer[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPvarGetUbLocal(var), boundsbuffer[v])) )
490 {
491 /* save this feasible assignment at the first position */
492 varsbuffer[0] = var;
493 boundtypesbuffer[0] = boundtypesbuffer[v];
494 boundsbuffer[0] = boundsbuffer[v];
495 nvarsbuffer = 1;
496 break;
497 }
498 else
499 {
500 /* otherwise the literal is violated - we skip the literal */
501 ++nviolated;
502 continue;
503 }
504 }
505 }
506
507 /* check subsequent variables with the same variable for redundancy */
508 for( w = v + 1; w < nvars && varsbuffer[v] == varsbuffer[w]; ++w )
509 {
510 if( boundtypesbuffer[v] == boundtypesbuffer[w] )
511 {
512 if( boundtypesbuffer[v] == SCIP_BOUNDTYPE_LOWER )
513 {
514 /* check whether current bound is as strong */
515 if( SCIPisLE(scip, boundsbuffer[v], boundsbuffer[w]) )
516 varsbuffer[v] = NULL; /* skip current bound */
517 else if ( SCIPisGT(scip, boundsbuffer[v], bounds[w]) )
518 varsbuffer[w] = NULL; /* remove later bound */
519 }
520 else
521 {
522 assert(boundtypesbuffer[v] == SCIP_BOUNDTYPE_UPPER);
523
524 /* check whether current bound is as strong */
525 if( SCIPisGE(scip, boundsbuffer[v], boundsbuffer[w]) )
526 varsbuffer[v] = NULL; /* skip current bound */
527 else if ( SCIPisLT(scip, boundsbuffer[v], boundsbuffer[w]) )
528 varsbuffer[w] = NULL; /* remove later bound */
529 }
530 }
531 }
532
533 /* keep current bound if it is not redundant (possibly redundant variable w is treated later) */
534 if( varsbuffer[v] != NULL )
535 {
536 /* switch last and current bound */
537 varsbuffer[nvarsbuffer] = varsbuffer[v];
538 boundtypesbuffer[nvarsbuffer] = boundtypesbuffer[v];
539 boundsbuffer[nvarsbuffer] = boundsbuffer[v];
540 ++nvarsbuffer;
541 }
542 }
543 assert( nvarsbuffer > 0 || SCIPisConsCompressionEnabled(scip) ); /* no variables can only happen if compression is enabled */
544
545 #ifndef NDEBUG
546 /* if there are no variables left, this is because all literals are infeasible */
547 if( nvarsbuffer == 0 )
548 {
549 for( v = 0; v < nvars; v++ )
550 {
551 var = vars[v];
552 assert( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var)) );
553 assert( (boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, SCIPvarGetLbLocal(var), bounds[v]))
554 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, SCIPvarGetUbLocal(var), bounds[v])) );
555 }
556 }
557 else
558 {
559 /* check that the literals are not redundant */
560 for( v = 0; v < nvarsbuffer; v++ )
561 {
562 int v2;
563 assert(varsbuffer[v] != NULL);
564 for( v2 = v+1; v2 < nvarsbuffer; v2++ )
565 assert(varsbuffer[v] != varsbuffer[v2] || boundtypesbuffer[v] != boundtypesbuffer[v2]);
566 }
567 }
568 #endif
569
570 /* if all literals are infeasible, we keep the first */
571 if( SCIPisConsCompressionEnabled(scip) && nviolated > 0 && nvarsbuffer == 0 )
572 nvarsbuffer = 1;
573
574 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars, varsbuffer, nvarsbuffer) );
575 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->boundtypes, boundtypesbuffer, nvarsbuffer) );
576 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->bounds, boundsbuffer, nvarsbuffer) );
577 (*consdata)->varssize = nvarsbuffer;
578 (*consdata)->nvars = nvarsbuffer;
579
580 /* free buffer storage */
581 SCIPfreeBufferArray(scip, &boundsbuffer);
582 SCIPfreeBufferArray(scip, &boundtypesbuffer);
583 SCIPfreeBufferArray(scip, &varsbuffer);
584 }
585 else
586 {
587 (*consdata)->vars = NULL;
588 (*consdata)->boundtypes = NULL;
589 (*consdata)->bounds = NULL;
590 (*consdata)->varssize = 0;
591 (*consdata)->nvars = 0;
592 }
593 (*consdata)->watchedvar1 = -1;
594 (*consdata)->watchedvar2 = -1;
595 (*consdata)->filterpos1 = -1;
596 (*consdata)->filterpos2 = -1;
597
598 /* get transformed variables, if we are in the transformed problem */
599 if( SCIPisTransformed(scip) )
600 {
601 SCIP_CALL( SCIPgetTransformedVars(scip, (*consdata)->nvars, (*consdata)->vars, (*consdata)->vars) );
602 }
603
604 return SCIP_OKAY;
605 }
606
607 /** frees a bound disjunction constraint data */
608 static
consdataFree(SCIP * scip,SCIP_CONSDATA ** consdata)609 void consdataFree(
610 SCIP* scip, /**< SCIP data structure */
611 SCIP_CONSDATA** consdata /**< pointer to the bound disjunction constraint */
612 )
613 {
614 assert(consdata != NULL);
615 assert(*consdata != NULL);
616
617 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->vars, (*consdata)->varssize);
618 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->boundtypes, (*consdata)->varssize);
619 SCIPfreeBlockMemoryArrayNull(scip, &(*consdata)->bounds, (*consdata)->varssize);
620 SCIPfreeBlockMemory(scip, consdata);
621 }
622
623 /** prints bound disjunction constraint to file stream */
624 static
consdataPrint(SCIP * scip,SCIP_CONSDATA * consdata,FILE * file,SCIP_Bool endline)625 void consdataPrint(
626 SCIP* scip, /**< SCIP data structure */
627 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
628 FILE* file, /**< output file (or NULL for standard output) */
629 SCIP_Bool endline /**< should an endline be set? */
630 )
631 {
632 int v;
633
634 assert(consdata != NULL);
635
636 /* print coefficients */
637 SCIPinfoMessage(scip, file, "bounddisjunction(");
638 for( v = 0; v < consdata->nvars; ++v )
639 {
640 assert(consdata->vars[v] != NULL);
641 if( v > 0 )
642 SCIPinfoMessage(scip, file, ", ");
643 SCIPinfoMessage(scip, file, "<%s> %s %.15g", SCIPvarGetName(consdata->vars[v]),
644 consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", consdata->bounds[v]);
645 }
646 SCIPinfoMessage(scip, file, ")");
647
648 if( endline )
649 SCIPinfoMessage(scip, file, "\n");
650 }
651
652 /** stores the given variable numbers as watched variables, and updates the event processing */
653 static
switchWatchedvars(SCIP * scip,SCIP_CONS * cons,SCIP_EVENTHDLR * eventhdlr,int watchedvar1,int watchedvar2)654 SCIP_RETCODE switchWatchedvars(
655 SCIP* scip, /**< SCIP data structure */
656 SCIP_CONS* cons, /**< bound disjunction constraint */
657 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
658 int watchedvar1, /**< new first watched variable */
659 int watchedvar2 /**< new second watched variable */
660 )
661 {
662 SCIP_CONSDATA* consdata;
663
664 consdata = SCIPconsGetData(cons);
665 assert(consdata != NULL);
666 assert(watchedvar1 == -1 || watchedvar1 != watchedvar2);
667 assert(watchedvar1 != -1 || watchedvar2 == -1);
668 assert(watchedvar1 == -1 || (0 <= watchedvar1 && watchedvar1 < consdata->nvars));
669 assert(watchedvar2 == -1 || (0 <= watchedvar2 && watchedvar2 < consdata->nvars));
670
671 /* don't watch variables for non active constraints */
672 if( !SCIPconsIsActive(cons) )
673 return SCIP_OKAY;
674
675 /* if one watched variable is equal to the old other watched variable, just switch positions */
676 if( watchedvar1 == consdata->watchedvar2 || watchedvar2 == consdata->watchedvar1 )
677 {
678 int tmp;
679
680 tmp = consdata->watchedvar1;
681 consdata->watchedvar1 = consdata->watchedvar2;
682 consdata->watchedvar2 = tmp;
683 tmp = consdata->filterpos1;
684 consdata->filterpos1 = consdata->filterpos2;
685 consdata->filterpos2 = tmp;
686 }
687 assert(watchedvar1 == -1 || watchedvar1 != consdata->watchedvar2);
688 assert(watchedvar2 == -1 || watchedvar2 != consdata->watchedvar1);
689
690 /* drop events on old watched variables */
691 if( consdata->watchedvar1 != -1 && consdata->watchedvar1 != watchedvar1 )
692 {
693 assert(consdata->filterpos1 != -1);
694 SCIP_CALL( dropEvents(scip, cons, consdata, eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
695 consdata->watchedvar1 = -1;
696 }
697 if( consdata->watchedvar2 != -1 && consdata->watchedvar2 != watchedvar2 )
698 {
699 assert(consdata->filterpos2 != -1);
700 SCIP_CALL( dropEvents(scip, cons, consdata, eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
701 consdata->watchedvar2 = -1;
702 }
703
704 /* catch events on new watched variables */
705 if( watchedvar1 != -1 && watchedvar1 != consdata->watchedvar1 )
706 {
707 SCIP_CALL( catchEvents(scip, cons, consdata, eventhdlr, watchedvar1, &consdata->filterpos1) );
708 }
709 if( watchedvar2 != -1 && watchedvar2 != consdata->watchedvar2 )
710 {
711 SCIP_CALL( catchEvents(scip, cons, consdata, eventhdlr, watchedvar2, &consdata->filterpos2) );
712 }
713
714 /* set the new watched variables */
715 consdata->watchedvar1 = watchedvar1;
716 consdata->watchedvar2 = watchedvar2;
717
718 return SCIP_OKAY;
719 }
720
721 /** check whether two intervals overlap */
722 static
isOverlapping(SCIP * scip,SCIP_VAR * var,SCIP_BOUNDTYPE boundtype1,SCIP_Real bound1,SCIP_BOUNDTYPE boundtype2,SCIP_Real bound2)723 SCIP_Bool isOverlapping(
724 SCIP* scip,
725 SCIP_VAR* var,
726 SCIP_BOUNDTYPE boundtype1,
727 SCIP_Real bound1,
728 SCIP_BOUNDTYPE boundtype2,
729 SCIP_Real bound2
730 )
731 {
732 SCIP_Bool overlapping = FALSE;
733
734 if( boundtype1 == SCIP_BOUNDTYPE_LOWER )
735 {
736 assert(boundtype2 == SCIP_BOUNDTYPE_UPPER);
737
738 if( SCIPisLE(scip, bound1 - bound2, (SCIP_Real)SCIPvarIsIntegral(var)) )
739 overlapping = TRUE;
740 }
741 else
742 {
743 assert(boundtype2 == SCIP_BOUNDTYPE_LOWER);
744
745 if( SCIPisLE(scip, bound2 - bound1, (SCIP_Real)SCIPvarIsIntegral(var)) )
746 overlapping = TRUE;
747 }
748
749 return overlapping;
750 }
751
752 /** deletes coefficient at given position from bound disjunction constraint data */
753 static
delCoefPos(SCIP * scip,SCIP_CONS * cons,SCIP_EVENTHDLR * eventhdlr,int pos)754 SCIP_RETCODE delCoefPos(
755 SCIP* scip, /**< SCIP data structure */
756 SCIP_CONS* cons, /**< bound disjunction constraint */
757 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
758 int pos /**< position of coefficient to delete */
759 )
760 {
761 SCIP_CONSDATA* consdata;
762
763 assert(eventhdlr != NULL);
764
765 consdata = SCIPconsGetData(cons);
766 assert(consdata != NULL);
767 assert(0 <= pos && pos < consdata->nvars);
768 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(consdata->vars[pos]));
769
770 /* remove the rounding locks of variable */
771 SCIP_CALL( unlockRounding(scip, cons, consdata, pos) );
772
773 if( SCIPconsIsTransformed(cons) )
774 {
775 /* if the position is watched, stop watching the position */
776 if( consdata->watchedvar1 == pos )
777 {
778 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar2, -1) );
779 }
780 if( consdata->watchedvar2 == pos )
781 {
782 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, -1) );
783 }
784 }
785 assert(pos != consdata->watchedvar1);
786 assert(pos != consdata->watchedvar2);
787
788 /* move the last variable to the free slot */
789 consdata->vars[pos] = consdata->vars[consdata->nvars-1];
790 consdata->boundtypes[pos] = consdata->boundtypes[consdata->nvars-1];
791 consdata->bounds[pos] = consdata->bounds[consdata->nvars-1];
792 consdata->nvars--;
793
794 /* if the last variable (that moved) was watched, update the watched position */
795 if( consdata->watchedvar1 == consdata->nvars )
796 consdata->watchedvar1 = pos;
797 if( consdata->watchedvar2 == consdata->nvars )
798 consdata->watchedvar2 = pos;
799
800 SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
801
802 return SCIP_OKAY;
803 }
804
805 /** adds literal to bound disjunction constraint data */
806 static
addCoef(SCIP * scip,SCIP_CONS * cons,SCIP_EVENTHDLR * eventhdlr,SCIP_VAR * var,SCIP_BOUNDTYPE boundtype,SCIP_Real bound,SCIP_Bool * redundant)807 SCIP_RETCODE addCoef(
808 SCIP* scip, /**< SCIP data structure */
809 SCIP_CONS* cons, /**< bound disjunction constraint */
810 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
811 SCIP_VAR* var, /**< variable in literal */
812 SCIP_BOUNDTYPE boundtype, /**< boundtype of literal */
813 SCIP_Real bound, /**< bound of literal */
814 SCIP_Bool* redundant /**< flag to indicate whether constraint has been bound redundant */
815 )
816 {
817 SCIP_CONSDATA* consdata;
818 int samebndidx;
819 int v;
820
821 assert(eventhdlr != NULL);
822
823 consdata = SCIPconsGetData(cons);
824 assert(consdata != NULL);
825 assert(var != NULL);
826 assert(!SCIPisInfinity(scip, REALABS(bound)));
827 assert(SCIPconsIsTransformed(cons) == SCIPvarIsTransformed(var));
828
829 /* ensure enough memory in consdata arrays */
830 if( consdata->varssize == consdata->nvars )
831 {
832 int newsize;
833
834 newsize = SCIPcalcMemGrowSize(scip, consdata->nvars + 1);
835 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->varssize, newsize) );
836 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->boundtypes, consdata->varssize, newsize) );
837 SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->bounds, consdata->varssize, newsize) );
838 consdata->varssize = newsize;
839 }
840 assert(consdata->varssize > consdata->nvars);
841
842 /* remember the position of the literal in the constraint that has the same bound type on the same variable
843 *
844 * example: (x >= 5) or (x <= 2) and literal (x >= 2) should be added.
845 * if we see (x >= 5) first, we cannot stop immediately because only in combination with the second literal
846 * we see that the constraint is redundant.
847 */
848 samebndidx = -1;
849
850 for( v = 0; v < consdata->nvars; v++ )
851 {
852 /* check if the variable is already part of the constraint */
853 if( consdata->vars[v] == var )
854 {
855 if( consdata->boundtypes[v] == boundtype )
856 samebndidx = v;
857 else if( isOverlapping(scip, var, consdata->boundtypes[v], consdata->bounds[v], boundtype, bound) )
858 {
859 *redundant = TRUE;
860 return SCIP_OKAY;
861 }
862 }
863 }
864
865 /* the combination of variable and boundtype is already part of the constraint; check whether the clause
866 * can be relaxed
867 */
868 if( samebndidx > -1 )
869 {
870 if( (boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLT(scip, bound, consdata->bounds[samebndidx]))
871 || (boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisGT(scip, bound, consdata->bounds[samebndidx])) )
872 {
873 SCIPdebugMsg(scip, "relax clause of <%s>: (<%s> %s %.15g) -> (<%s> %s %.15g)\n", SCIPconsGetName(cons),
874 SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", consdata->bounds[samebndidx],
875 SCIPvarGetName(var), boundtype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bound);
876 consdata->bounds[samebndidx] = bound;
877 }
878 }
879 else
880 {
881 /* add the variable to the end of the array */
882 consdata->vars[consdata->nvars] = var;
883 consdata->boundtypes[consdata->nvars] = boundtype;
884 consdata->bounds[consdata->nvars] = bound;
885 consdata->nvars++;
886
887 if( SCIPconsIsTransformed(cons) )
888 {
889 /* add rounding lock of variable */
890 SCIP_CALL( lockRounding(scip, cons, consdata, consdata->nvars-1) );
891
892 /* if less than 2 variables are watched, add the new one to the watched variables */
893 if( consdata->watchedvar1 == -1 )
894 {
895 assert(consdata->watchedvar2 == -1);
896 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->nvars-1, -1) );
897 }
898 else if( consdata->watchedvar2 == -1 )
899 {
900 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, consdata->nvars-1) );
901 }
902 }
903 }
904
905 SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
906
907 return SCIP_OKAY;
908 }
909
910 /** deletes all variables with global bounds violating the literal, checks for global bounds satisfying the literal */
911 static
applyGlobalBounds(SCIP * scip,SCIP_CONS * cons,SCIP_EVENTHDLR * eventhdlr,SCIP_Bool * redundant)912 SCIP_RETCODE applyGlobalBounds(
913 SCIP* scip, /**< SCIP data structure */
914 SCIP_CONS* cons, /**< bound disjunction constraint */
915 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
916 SCIP_Bool* redundant /**< returns whether a variable fixed to one exists in the constraint */
917 )
918 {
919 SCIP_CONSDATA* consdata;
920 int v;
921 SCIP_Real bnd;
922
923 assert(eventhdlr != NULL);
924 assert(redundant != NULL);
925
926 consdata = SCIPconsGetData(cons);
927 assert(consdata != NULL);
928 assert(consdata->nvars == 0 || consdata->vars != NULL);
929
930 *redundant = FALSE;
931 v = 0;
932 while( v < consdata->nvars )
933 {
934 SCIP_VAR* var;
935
936 var = consdata->vars[v];
937
938 if( consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
939 {
940 bnd = SCIPcomputeVarLbGlobal(scip, var);
941 if( isFeasGE(scip, var, bnd, consdata->bounds[v]) )
942 {
943 *redundant = TRUE;
944 return SCIP_OKAY;
945 }
946 else
947 {
948 bnd = SCIPcomputeVarUbGlobal(scip, var);
949 if( isFeasLT(scip, var, bnd, consdata->bounds[v]) )
950 {
951 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
952 }
953 else
954 ++v;
955 }
956 }
957 else
958 {
959 assert(consdata->boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
960 bnd = SCIPcomputeVarUbGlobal(scip, var);
961 if( isFeasLE(scip, var, bnd, consdata->bounds[v]) )
962 {
963 *redundant = TRUE;
964 return SCIP_OKAY;
965 }
966 else
967 {
968 bnd = SCIPcomputeVarLbGlobal(scip, var);
969 if( isFeasGT(scip, var, bnd, consdata->bounds[v]) )
970 {
971 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
972 }
973 else
974 ++v;
975 }
976 }
977 }
978
979 SCIPdebugMsg(scip, "after global bounds: ");
980 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
981
982 return SCIP_OKAY;
983 }
984
985 /** returns whether literal at the given position is satisfied in the local bounds */
986 static
isLiteralSatisfied(SCIP * scip,SCIP_CONSDATA * consdata,int pos)987 SCIP_Bool isLiteralSatisfied(
988 SCIP* scip, /**< SCIP data structure */
989 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
990 int pos /**< position of the literal */
991 )
992 {
993 SCIP_Real bnd;
994
995 assert(consdata != NULL);
996 assert(0 <= pos && pos < consdata->nvars);
997
998 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
999 {
1000 bnd = SCIPcomputeVarLbLocal(scip, consdata->vars[pos]);
1001 return isFeasGE(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
1002 }
1003 else
1004 {
1005 bnd = SCIPcomputeVarUbLocal(scip, consdata->vars[pos]);
1006 return isFeasLE(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
1007 }
1008 }
1009
1010 /** returns whether literal at the given position is violated in the local bounds */
1011 static
isLiteralViolated(SCIP * scip,SCIP_CONSDATA * consdata,int pos)1012 SCIP_Bool isLiteralViolated(
1013 SCIP* scip, /**< SCIP data structure */
1014 SCIP_CONSDATA* consdata, /**< bound disjunction constraint data */
1015 int pos /**< position of the literal */
1016 )
1017 {
1018 SCIP_Real bnd;
1019
1020 assert(consdata != NULL);
1021 assert(0 <= pos && pos < consdata->nvars);
1022
1023 if( consdata->boundtypes[pos] == SCIP_BOUNDTYPE_LOWER )
1024 {
1025 bnd = SCIPcomputeVarUbLocal(scip, consdata->vars[pos]);
1026 return isFeasLT(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
1027 }
1028 else
1029 {
1030 bnd = SCIPcomputeVarLbLocal(scip, consdata->vars[pos]);
1031 return isFeasGT(scip, consdata->vars[pos], bnd, consdata->bounds[pos]);
1032 }
1033 }
1034
1035 /** replace variables by their representative active (or multi-aggregated) variables */
1036 static
removeFixedVariables(SCIP * scip,SCIP_CONS * cons,SCIP_EVENTHDLR * eventhdlr,SCIP_Bool * redundant)1037 SCIP_RETCODE removeFixedVariables(
1038 SCIP* scip, /**< SCIP data structure */
1039 SCIP_CONS* cons, /**< bound disjunction constraint */
1040 SCIP_EVENTHDLR* eventhdlr, /**< event handler */
1041 SCIP_Bool* redundant /**< flag to indicate whether constraint has been bound redundant */
1042 )
1043 {
1044 SCIP_CONSDATA* consdata;
1045 SCIP_VAR* var;
1046 SCIP_BOUNDTYPE boundtype;
1047 SCIP_Real bound;
1048 int v;
1049
1050 assert(scip != NULL);
1051 assert(cons != NULL);
1052 assert(eventhdlr != NULL);
1053
1054 consdata = SCIPconsGetData(cons);
1055 assert(consdata != NULL);
1056
1057 v = 0;
1058 while( v < consdata->nvars )
1059 {
1060 #ifndef NDEBUG
1061 SCIP_VAR* oldvar;
1062 #endif
1063 var = consdata->vars[v];
1064 assert(var != NULL);
1065
1066 #ifndef NDEBUG
1067 oldvar = var;
1068 #endif
1069
1070 if( SCIPvarIsActive(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
1071 {
1072 /* check whether the literal is satisfied and the constraint is thus redundant */
1073 if( isLiteralSatisfied(scip, consdata, v) )
1074 {
1075 *redundant = TRUE;
1076 break;
1077 }
1078 if( isLiteralViolated(scip, consdata, v) )
1079 {
1080 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1081 continue;
1082 }
1083
1084 ++v;
1085
1086 continue;
1087 }
1088
1089 /* get active/fixed/multiaggr equivalent of v'th literal */
1090 bound = consdata->bounds[v];
1091 boundtype = consdata->boundtypes[v];
1092 SCIP_CALL( SCIPvarGetProbvarBound(&var, &bound, &boundtype) );
1093 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED || oldvar != var);
1094
1095 SCIPdebugMsg(scip, "in <%s>, replace <%s>[%g,%g] %c= %g by <%s>[%g,%g] %c= %g\n", SCIPconsGetName(cons),
1096 SCIPvarGetName(consdata->vars[v]), SCIPvarGetLbGlobal(consdata->vars[v]), SCIPvarGetUbGlobal(consdata->vars[v]), (consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? '>' : '<'), consdata->bounds[v],
1097 SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), (boundtype == SCIP_BOUNDTYPE_LOWER ? '>' : '<'), bound);
1098
1099 /* if literal is satisfied, then constraint is redundant and we can stop */
1100 if( (boundtype == SCIP_BOUNDTYPE_LOWER && isFeasLE(scip, var, bound, SCIPvarGetLbGlobal(var))) || /*lint !e666*/
1101 (boundtype == SCIP_BOUNDTYPE_UPPER && isFeasGE(scip, var, bound, SCIPvarGetUbGlobal(var))) ) /*lint !e666*/
1102 {
1103 *redundant = TRUE;
1104 break;
1105 }
1106
1107 /* if literal is not fixed, replace it */
1108 if( SCIPvarGetStatus(var) != SCIP_VARSTATUS_FIXED )
1109 {
1110 /* add new literal */
1111 SCIP_CALL( addCoef(scip, cons, eventhdlr, var, boundtype, bound, redundant) );
1112 }
1113
1114 /* remove old literal */
1115 SCIP_CALL( delCoefPos(scip, cons, eventhdlr, v) );
1116 }
1117
1118 return SCIP_OKAY;
1119 }
1120
1121 /** try to upgrade the bounddisjunction constraint
1122 *
1123 * if only binary variables are left, we can upgrade a bounddisjunction to a logicor constraint(, if only two variables
1124 * are left, this logicor constraint can be formulated as set-packing constraint as well)
1125 *
1126 * e.g.: bounddisjunction( x1 >= 1, x2 <= 0; x3 >= 1; x4 <= 0 ) => x1 + ~x2 + x3 + ~x4 >= 1
1127 */
1128 static
upgradeCons(SCIP * scip,SCIP_CONS * cons,int * ndelconss,int * naddconss)1129 SCIP_RETCODE upgradeCons(
1130 SCIP* scip, /**< SCIP data structure */
1131 SCIP_CONS* cons, /**< bound disjunction constraint that detected the conflict */
1132 int* ndelconss, /**< pointer to store the number of delete constraint */
1133 int* naddconss /**< pointer to store the number of added constraint */
1134 )
1135 {
1136 SCIP_CONSDATA* consdata;
1137 SCIP_VAR** newvars;
1138 SCIP_Bool allbinary;
1139 int nvars;
1140 int v;
1141
1142 assert(scip != NULL);
1143 assert(cons != NULL);
1144 assert(ndelconss != NULL);
1145 assert(naddconss != NULL);
1146 assert(naddconss != NULL);
1147 assert(!SCIPconsIsModifiable(cons));
1148
1149 consdata = SCIPconsGetData(cons);
1150 assert(consdata != NULL);
1151
1152 nvars = consdata->nvars;
1153 assert(nvars >= 2);
1154 assert(consdata->vars != NULL);
1155
1156 allbinary = TRUE;
1157
1158 SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars) );
1159
1160 for( v = nvars - 1; v >= 0; --v )
1161 {
1162 if( !SCIPvarIsBinary(consdata->vars[v]) )
1163 {
1164 allbinary = FALSE;
1165 break;
1166 }
1167 else
1168 {
1169 if( consdata->boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1170 {
1171 assert(SCIPisFeasGT(scip, consdata->bounds[v], 0.0));
1172
1173 if( nvars == 2 )
1174 {
1175 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &(newvars[v])) );
1176 }
1177 else
1178 newvars[v] = consdata->vars[v];
1179 }
1180 else
1181 {
1182 assert(consdata->boundtypes[v] == SCIP_BOUNDTYPE_UPPER);
1183 assert(SCIPisFeasLT(scip, consdata->bounds[v], 1.0));
1184
1185 if( nvars > 2 )
1186 {
1187 SCIP_CALL( SCIPgetNegatedVar(scip, consdata->vars[v], &(newvars[v])) );
1188 }
1189 else
1190 newvars[v] = consdata->vars[v];
1191 }
1192 }
1193 }
1194
1195 if( allbinary )
1196 {
1197 SCIP_CONS* newcons;
1198
1199 if( nvars == 2 )
1200 {
1201 SCIP_CALL( SCIPcreateConsSetpack(scip, &newcons, SCIPconsGetName(cons), nvars, newvars,
1202 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
1203 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
1204 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
1205 SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1206 }
1207 else
1208 {
1209 SCIP_CALL( SCIPcreateConsLogicor(scip, &newcons, SCIPconsGetName(cons), nvars, newvars,
1210 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
1211 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons),
1212 SCIPconsIsLocal(cons), SCIPconsIsModifiable(cons),
1213 SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons), SCIPconsIsStickingAtNode(cons)) );
1214 }
1215
1216 SCIPdebugMsg(scip, "updated constraint <%s> to the following %s constraint\n", SCIPconsGetName(cons), (nvars == 2 ? "setppc" : "logicor"));
1217 SCIPdebugPrintCons(scip, newcons, NULL);
1218 SCIP_CALL( SCIPaddCons(scip, newcons) );
1219 SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1220 ++(*naddconss);
1221
1222 SCIP_CALL( SCIPdelCons(scip, cons) );
1223 ++(*ndelconss);
1224 }
1225
1226 SCIPfreeBufferArray(scip, &newvars);
1227
1228 return SCIP_OKAY;
1229 }
1230
1231 /** analyzes conflicting assignment on given constraint, and adds conflict constraint to problem */
1232 static
analyzeConflict(SCIP * scip,SCIP_CONS * cons)1233 SCIP_RETCODE analyzeConflict(
1234 SCIP* scip, /**< SCIP data structure */
1235 SCIP_CONS* cons /**< bound disjunction constraint that detected the conflict */
1236 )
1237 {
1238 SCIP_CONSDATA* consdata;
1239 int v;
1240
1241 /* conflict analysis can only be applied in solving stage and if it is turned on */
1242 if( (SCIPgetStage(scip) != SCIP_STAGE_SOLVING && !SCIPinProbing(scip)) || !SCIPisConflictAnalysisApplicable(scip) )
1243 return SCIP_OKAY;
1244
1245 consdata = SCIPconsGetData(cons);
1246 assert(consdata != NULL);
1247
1248 /* initialize conflict analysis, and add all bounds of infeasible constraint to conflict candidate queue */
1249 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
1250
1251 for( v = 0; v < consdata->nvars; ++v )
1252 {
1253 /* the opposite bound is in conflict with this literal */
1254 SCIP_CALL( SCIPaddConflictBd(scip, consdata->vars[v], SCIPboundtypeOpposite(consdata->boundtypes[v]), NULL) );
1255 }
1256
1257 /* analyze the conflict */
1258 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1259
1260 return SCIP_OKAY;
1261 }
1262
1263 /** disables or deletes the given constraint, depending on the current depth */
1264 static
disableCons(SCIP * scip,SCIP_CONS * cons)1265 SCIP_RETCODE disableCons(
1266 SCIP* scip, /**< SCIP data structure */
1267 SCIP_CONS* cons /**< bound disjunction constraint to be disabled */
1268 )
1269 {
1270 assert(SCIPconsGetValidDepth(cons) <= SCIPgetDepth(scip));
1271
1272 if( SCIPgetDepth(scip) == SCIPconsGetValidDepth(cons) )
1273 {
1274 SCIP_CALL( SCIPdelCons(scip, cons) );
1275 }
1276 else
1277 {
1278 SCIP_CALL( SCIPdisableCons(scip, cons) );
1279 }
1280
1281 return SCIP_OKAY;
1282 }
1283
1284 /** checks constraint for violation only looking at the watched variables, applies bound changes if possible */
1285 static
processWatchedVars(SCIP * scip,SCIP_CONS * cons,SCIP_EVENTHDLR * eventhdlr,SCIP_Bool * cutoff,SCIP_Bool * infeasible,SCIP_Bool * reduceddom,SCIP_Bool * mustcheck)1286 SCIP_RETCODE processWatchedVars(
1287 SCIP* scip, /**< SCIP data structure */
1288 SCIP_CONS* cons, /**< bound disjunction constraint to be processed */
1289 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1290 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1291 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint is infeasible in current bounds */
1292 SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
1293 SCIP_Bool* mustcheck /**< pointer to store whether this constraint must be checked for feasibility */
1294 )
1295 {
1296 SCIP_CONSDATA* consdata;
1297 SCIP_VAR** vars;
1298 SCIP_BOUNDTYPE* boundtypes;
1299 SCIP_Real* bounds;
1300 SCIP_Longint nbranchings1;
1301 SCIP_Longint nbranchings2;
1302 int nvars;
1303 int watchedvar1;
1304 int watchedvar2;
1305
1306 assert(cons != NULL);
1307 assert(SCIPconsGetHdlr(cons) != NULL);
1308 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1309 assert(cutoff != NULL);
1310 assert(reduceddom != NULL);
1311 assert(mustcheck != NULL);
1312
1313 consdata = SCIPconsGetData(cons);
1314 assert(consdata != NULL);
1315 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
1316
1317 /* init bools */
1318 *cutoff = FALSE;
1319 *infeasible = FALSE;
1320 *reduceddom = FALSE;
1321 *mustcheck = FALSE;
1322
1323 SCIPdebugMsg(scip, "processing watched variables of constraint <%s>\n", SCIPconsGetName(cons));
1324
1325 nvars = consdata->nvars;
1326 vars = consdata->vars;
1327 boundtypes = consdata->boundtypes;
1328 bounds = consdata->bounds;
1329 assert(nvars == 0 || vars != NULL);
1330 assert(nvars == 0 || boundtypes != NULL);
1331 assert(nvars == 0 || bounds != NULL);
1332
1333 /* check watched variables if they are satisfying the literal */
1334 if( consdata->watchedvar1 >= 0 && isLiteralSatisfied(scip, consdata, consdata->watchedvar1) )
1335 {
1336 /* the literal is satisfied, making the constraint redundant */
1337 SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar1 satisfied)\n", SCIPconsGetName(cons));
1338 SCIP_CALL( disableCons(scip, cons) );
1339 return SCIP_OKAY;
1340 }
1341 if( consdata->watchedvar2 >= 0 && isLiteralSatisfied(scip, consdata, consdata->watchedvar2) )
1342 {
1343 /* the literal is satisfied, making the constraint redundant */
1344 SCIPdebugMsg(scip, " -> disabling constraint <%s> (watchedvar2 satisfied)\n", SCIPconsGetName(cons));
1345 SCIP_CALL( disableCons(scip, cons) );
1346 return SCIP_OKAY;
1347 }
1348
1349 /* check if watched variables are still undecided */
1350 watchedvar1 = -1;
1351 watchedvar2 = -1;
1352 nbranchings1 = SCIP_LONGINT_MAX;
1353 nbranchings2 = SCIP_LONGINT_MAX;
1354 if( consdata->watchedvar1 >= 0 && !isLiteralViolated(scip, consdata, consdata->watchedvar1) )
1355 {
1356 watchedvar1 = consdata->watchedvar1;
1357 nbranchings1 = -1; /* prefer keeping the watched variable */
1358 }
1359 if( consdata->watchedvar2 >= 0 && !isLiteralViolated(scip, consdata, consdata->watchedvar2) )
1360 {
1361 if( watchedvar1 == -1 )
1362 {
1363 watchedvar1 = consdata->watchedvar2;
1364 nbranchings1 = -1; /* prefer keeping the watched variable */
1365 }
1366 else
1367 {
1368 watchedvar2 = consdata->watchedvar2;
1369 nbranchings2 = -1; /* prefer keeping the watched variable */
1370 }
1371 }
1372 assert(watchedvar1 >= 0 || watchedvar2 == -1);
1373 assert(nbranchings1 <= nbranchings2);
1374 assert(watchedvar1 != -1 || nbranchings1 == SCIP_LONGINT_MAX);
1375 assert(watchedvar2 != -1 || nbranchings2 == SCIP_LONGINT_MAX);
1376
1377 /* search for new watched variables */
1378 if( watchedvar2 == -1 )
1379 {
1380 int v;
1381
1382 for( v = 0; v < nvars; ++v )
1383 {
1384 SCIP_Longint nbranchings;
1385
1386 /* don't process the watched variables again */
1387 if( v == consdata->watchedvar1 || v == consdata->watchedvar2 )
1388 continue;
1389
1390 /* check, if the literal is violated */
1391 if( isLiteralViolated(scip, consdata, v) )
1392 continue;
1393
1394 /* check, if the literal is satisfied */
1395 if( isLiteralSatisfied(scip, consdata, v) )
1396 {
1397 assert(v != consdata->watchedvar1);
1398 assert(v != consdata->watchedvar2);
1399
1400 /* the literal is satisfied, making the constraint redundant;
1401 * make sure, the feasible variable is watched and disable the constraint
1402 */
1403 SCIPdebugMsg(scip, " -> disabling constraint <%s> (variable <%s> fixed to 1.0)\n",
1404 SCIPconsGetName(cons), SCIPvarGetName(vars[v]));
1405 if( consdata->watchedvar1 != -1 )
1406 {
1407 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, consdata->watchedvar1, v) );
1408 }
1409 else
1410 {
1411 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, v, consdata->watchedvar2) );
1412 }
1413 SCIP_CALL( disableCons(scip, cons) );
1414 return SCIP_OKAY;
1415 }
1416
1417 /* the literal is still undecided and can be used as watched variable */
1418 nbranchings = SCIPvarGetNBranchingsCurrentRun(vars[v],
1419 boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? SCIP_BRANCHDIR_DOWNWARDS : SCIP_BRANCHDIR_UPWARDS);
1420 if( nbranchings < nbranchings2 )
1421 {
1422 if( nbranchings < nbranchings1 )
1423 {
1424 watchedvar2 = watchedvar1;
1425 nbranchings2 = nbranchings1;
1426 watchedvar1 = v;
1427 nbranchings1 = nbranchings;
1428 }
1429 else
1430 {
1431 watchedvar2 = v;
1432 nbranchings2 = nbranchings;
1433 }
1434 }
1435 }
1436 }
1437 assert(nbranchings1 <= nbranchings2);
1438 assert(watchedvar1 >= 0 || watchedvar2 == -1);
1439
1440 if( watchedvar1 == -1 )
1441 {
1442 /* there is no undecided literal left -> the constraint is infeasible
1443 * - a modifiable constraint is infeasible
1444 * - an unmodifiable constraint is infeasible and the node can be cut off
1445 */
1446 assert(watchedvar2 == -1);
1447
1448 SCIPdebugMsg(scip, " -> constraint <%s> is infeasible\n", SCIPconsGetName(cons));
1449 *infeasible = TRUE;
1450
1451 SCIP_CALL( SCIPresetConsAge(scip, cons) );
1452 if( !SCIPconsIsModifiable(cons) )
1453 {
1454 /* use conflict analysis to get a conflict constraint out of the conflicting assignment */
1455 SCIP_CALL( analyzeConflict(scip, cons) );
1456
1457 /* mark the node to be cut off */
1458 *cutoff = TRUE;
1459 }
1460 }
1461 else if( watchedvar2 == -1 )
1462 {
1463 /* there is only one undecided literal:
1464 * - a modifiable constraint must be checked manually
1465 * - we cannot change bounds of multi-aggregated variables and have to check manually
1466 * - an unmodifiable constraint is feasible and can be disabled after the remaining literal is satisfied
1467 */
1468 assert(0 <= watchedvar1 && watchedvar1 < nvars);
1469 assert(!isLiteralViolated(scip, consdata, watchedvar1));
1470 assert(!isLiteralSatisfied(scip, consdata, watchedvar1));
1471 if( SCIPconsIsModifiable(cons)
1472 || SCIPvarGetStatus(SCIPvarGetProbvar(vars[watchedvar1])) == SCIP_VARSTATUS_MULTAGGR )
1473 *mustcheck = TRUE;
1474 else
1475 {
1476 SCIP_Bool infbdchg;
1477
1478 #ifndef NDEBUG
1479 int v;
1480
1481 /* check whether all other literals are violated */
1482 for (v = 0; v < nvars; ++v)
1483 {
1484 if ( v != watchedvar1 )
1485 {
1486 assert( isLiteralViolated(scip, consdata, v) );
1487 }
1488 }
1489 #endif
1490
1491 /* satisfy remaining literal and disable constraint; make sure, the fixed-to-one variable is watched */
1492 SCIPdebugMsg(scip, " -> single-literal constraint <%s> (change bound <%s> %s %g) at depth %d\n",
1493 SCIPconsGetName(cons), SCIPvarGetName(vars[watchedvar1]),
1494 boundtypes[watchedvar1] == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", bounds[watchedvar1], SCIPgetDepth(scip));
1495
1496 if( boundtypes[watchedvar1] == SCIP_BOUNDTYPE_LOWER )
1497 {
1498 SCIP_CALL( SCIPinferVarLbCons(scip, vars[watchedvar1], bounds[watchedvar1], cons, watchedvar1, TRUE,
1499 &infbdchg, NULL) );
1500 }
1501 else
1502 {
1503 SCIP_CALL( SCIPinferVarUbCons(scip, vars[watchedvar1], bounds[watchedvar1], cons, watchedvar1, TRUE,
1504 &infbdchg, NULL) );
1505 }
1506 assert(!infbdchg);
1507 SCIP_CALL( SCIPresetConsAge(scip, cons) );
1508 if( watchedvar1 != consdata->watchedvar1 ) /* keep one of the watched variables */
1509 {
1510 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, consdata->watchedvar1) );
1511 }
1512 SCIP_CALL( disableCons(scip, cons) );
1513 *reduceddom = TRUE;
1514 }
1515 }
1516 else
1517 {
1518 SCIPdebugMsg(scip, " -> new watched variables <%s> and <%s> of constraint <%s> are still undecided\n",
1519 SCIPvarGetName(vars[watchedvar1]), SCIPvarGetName(vars[watchedvar2]), SCIPconsGetName(cons));
1520
1521 /* switch to the new watched variables */
1522 SCIP_CALL( switchWatchedvars(scip, cons, eventhdlr, watchedvar1, watchedvar2) );
1523
1524 /* there are at least two undecided variables -> the constraint must be checked manually */
1525 *mustcheck = TRUE;
1526
1527 /* disable propagation of constraint until the corresponding bound of a watched variable changed */
1528 SCIP_CALL( SCIPdisableConsPropagation(scip, cons) );
1529
1530 /* increase aging counter */
1531 SCIP_CALL( SCIPaddConsAge(scip, cons, AGEINCREASE(consdata->nvars)) );
1532 }
1533
1534 return SCIP_OKAY;
1535 }
1536
1537 /** checks constraint for violation, returns TRUE iff constraint is violated */
1538 static
isConsViolated(SCIP * scip,SCIP_CONS * cons,SCIP_SOL * sol)1539 SCIP_Bool isConsViolated(
1540 SCIP* scip, /**< SCIP data structure */
1541 SCIP_CONS* cons, /**< bound disjunction constraint to be checked */
1542 SCIP_SOL* sol /**< primal CIP solution */
1543 )
1544 {
1545 SCIP_CONSDATA* consdata;
1546 SCIP_VAR** vars;
1547 SCIP_BOUNDTYPE* boundtypes;
1548 SCIP_Real* bounds;
1549 SCIP_Real solval;
1550 SCIP_Real viol;
1551 SCIP_Real absviol;
1552 int violpos;
1553 int nvars;
1554 int v;
1555
1556 consdata = SCIPconsGetData(cons);
1557 assert(consdata != NULL);
1558
1559 nvars = consdata->nvars;
1560 vars = consdata->vars;
1561 boundtypes = consdata->boundtypes;
1562 bounds = consdata->bounds;
1563 assert(nvars == 0 || vars != NULL);
1564 assert(nvars == 0 || boundtypes != NULL);
1565 assert(nvars == 0 || bounds != NULL);
1566
1567 /* check the given solution */
1568 absviol = SCIP_REAL_MAX;
1569 violpos = -1;
1570 for( v = 0; v < nvars; ++v )
1571 {
1572 solval = SCIPgetSolVal(scip, sol, vars[v]);
1573
1574 /* update absolute violation if needed */
1575 viol = (boundtypes[v] == SCIP_BOUNDTYPE_LOWER) ? bounds[v] - solval : solval - bounds[v];
1576 if( viol < absviol )
1577 {
1578 absviol = viol;
1579 violpos = v;
1580 }
1581
1582 if( (boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, vars[v], solval, bounds[v]))
1583 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, vars[v], solval, bounds[v])) )
1584 {
1585 return FALSE;
1586 }
1587 }
1588 /* update constraint violation in solution */
1589 if( sol != NULL )
1590 {
1591 SCIP_Real relviol;
1592
1593 assert(0 == nvars || -1 != violpos);
1594
1595 if( 0 == nvars )
1596 relviol = SCIP_REAL_MAX;
1597 else
1598 relviol = SCIPrelDiff(SCIPgetSolVal(scip, sol, vars[violpos]), bounds[violpos]);
1599
1600 SCIPupdateSolConsViolation(scip, sol, absviol, relviol);
1601 }
1602 return TRUE;
1603 }
1604
1605 /* registers variables of a constraint as branching candidates
1606 * indicates whether an n-ary branch is necessary to enforce this constraint,
1607 * because all active literals are w.r.t. continuous variables which bound (in the literal) is at the variable's bound
1608 */
1609 static
registerBranchingCandidates(SCIP * scip,SCIP_CONS * cons,SCIP_SOL * sol,SCIP_Bool * cutoff,SCIP_Bool * neednarybranch)1610 SCIP_RETCODE registerBranchingCandidates(
1611 SCIP* scip, /**< SCIP data structure */
1612 SCIP_CONS* cons, /**< bound disjunction constraint which variables should be registered for branching */
1613 SCIP_SOL* sol, /**< solution (NULL for LP solution) */
1614 SCIP_Bool* cutoff, /**< pointer to store whether the constraint cannot be made feasible by branching */
1615 SCIP_Bool* neednarybranch /**< pointer to store TRUE, if n-ary branching is necessary to enforce this constraint */
1616 )
1617 {
1618 SCIP_CONSDATA* consdata;
1619 SCIP_VAR** vars;
1620 SCIP_BOUNDTYPE* boundtypes;
1621 SCIP_Real* bounds;
1622 SCIP_Real violation;
1623 SCIP_Real varlb;
1624 SCIP_Real varub;
1625 int nvars;
1626 int v;
1627
1628 assert(cons != NULL);
1629 assert(SCIPconsGetHdlr(cons) != NULL);
1630 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1631 assert(cutoff != NULL);
1632 assert(neednarybranch != NULL);
1633
1634 consdata = SCIPconsGetData(cons);
1635 assert(consdata != NULL);
1636 nvars = consdata->nvars;
1637 vars = consdata->vars;
1638 boundtypes = consdata->boundtypes;
1639 bounds = consdata->bounds;
1640 assert(nvars == 0 || vars != NULL);
1641 assert(nvars == 0 || boundtypes != NULL);
1642 assert(nvars == 0 || bounds != NULL);
1643
1644 *cutoff = TRUE;
1645 *neednarybranch = TRUE;
1646
1647 for( v = 0; v < nvars; ++v )
1648 {
1649 SCIP_VAR* var;
1650
1651 var = vars[v];
1652 assert(var != NULL);
1653
1654 /* constraint should be violated, so all bounds in the constraint have to be violated */
1655 assert( !(boundtypes[v] == SCIP_BOUNDTYPE_LOWER && SCIPisFeasGE(scip, SCIPgetSolVal(scip, sol, var), bounds[v])) &&
1656 !(boundtypes[v] == SCIP_BOUNDTYPE_UPPER && SCIPisFeasLE(scip, SCIPgetSolVal(scip, sol, var), bounds[v])) );
1657
1658 varlb = SCIPcomputeVarLbLocal(scip, var);
1659 varub = SCIPcomputeVarUbLocal(scip, var);
1660
1661 /* if literal is x >= varlb, but upper bound on x is < varlb, then this literal can never be satisfied,
1662 * thus there is no use for branching
1663 */
1664 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, varub, bounds[v]) )
1665 continue;
1666
1667 /* if literal is x <= varub, but lower bound on x is > varub, then this literal can never be satisfied,
1668 * thus there is no use for branching
1669 */
1670 if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, varlb, bounds[v]) )
1671 continue;
1672
1673 /* if literal is always satisfied, then no need to branch on it may happen if propagation is disabled for some
1674 * reason and due to numerics current solution does not satisfy literal, but variable bounds do
1675 */
1676 if( isLiteralSatisfied(scip, consdata, v) )
1677 continue;
1678
1679 violation = SCIPgetSolVal(scip, sol, var) - bounds[v];
1680
1681 /* if variable is continuous, then we cannot branch on one of the variable bounds */
1682 if( SCIPvarGetType(vars[v]) != SCIP_VARTYPE_CONTINUOUS ||
1683 ((SCIPisInfinity(scip, -varlb) || !SCIPisFeasEQ(scip, bounds[v], varlb)) &&
1684 (SCIPisInfinity(scip, varub) || !SCIPisFeasEQ(scip, bounds[v], varub))) )
1685 {
1686 SCIP_CALL( SCIPaddExternBranchCand(scip, var, REALABS(violation), bounds[v]) );
1687 *neednarybranch = FALSE;
1688 }
1689 *cutoff = FALSE;
1690 }
1691
1692 return SCIP_OKAY;
1693 }
1694
1695 /** enforces the pseudo or LP solution on the given constraint */
1696 static
enforceCurrentSol(SCIP * scip,SCIP_CONS * cons,SCIP_SOL * sol,SCIP_EVENTHDLR * eventhdlr,SCIP_Bool * cutoff,SCIP_Bool * infeasible,SCIP_Bool * reduceddom,SCIP_Bool * registeredbrcand)1697 SCIP_RETCODE enforceCurrentSol(
1698 SCIP* scip, /**< SCIP data structure */
1699 SCIP_CONS* cons, /**< bound disjunction constraint to be separated */
1700 SCIP_SOL* sol, /**< solution which should be enforced (NULL for LP solution) */
1701 SCIP_EVENTHDLR* eventhdlr, /**< event handler to call for the event processing */
1702 SCIP_Bool* cutoff, /**< pointer to store TRUE, if the node can be cut off */
1703 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the constraint was infeasible */
1704 SCIP_Bool* reduceddom, /**< pointer to store TRUE, if a domain reduction was found */
1705 SCIP_Bool* registeredbrcand /**< pointer to store TRUE, if branching variable candidates were registered or was already true */
1706 )
1707 {
1708 SCIP_Bool mustcheck;
1709 SCIP_Bool neednarybranch;
1710
1711 assert(cons != NULL);
1712 assert(SCIPconsGetHdlr(cons) != NULL);
1713 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1714 assert(cutoff != NULL);
1715 assert(infeasible != NULL);
1716 assert(reduceddom != NULL);
1717 assert(registeredbrcand != NULL);
1718
1719 SCIPdebugMsg(scip, "enforce bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
1720
1721 /* update and check the watched variables, if they were changed since last processing */
1722 if( SCIPconsIsPropagationEnabled(cons) )
1723 {
1724 SCIP_CALL( processWatchedVars(scip, cons, eventhdlr, cutoff, infeasible, reduceddom, &mustcheck) );
1725 }
1726 else
1727 mustcheck = TRUE;
1728
1729 if( mustcheck )
1730 {
1731 if( isConsViolated(scip, cons, sol) )
1732 {
1733 /* constraint was infeasible -> reset age */
1734 SCIP_CALL( SCIPresetConsAge(scip, cons) );
1735 *infeasible = TRUE;
1736
1737 /* register branching candidates */
1738 SCIP_CALL( registerBranchingCandidates(scip, cons, sol, cutoff, &neednarybranch) );
1739
1740 if( !neednarybranch )
1741 *registeredbrcand = TRUE;
1742 }
1743 }
1744
1745 return SCIP_OKAY;
1746 }
1747
1748 /** enforces a constraint by creating an n-ary branch consisting of a set of child nodes, each enforcing one literal
1749 */
1750 static
createNAryBranch(SCIP * scip,SCIP_CONS * cons,SCIP_SOL * sol)1751 SCIP_RETCODE createNAryBranch(
1752 SCIP* scip, /**< SCIP data structure */
1753 SCIP_CONS* cons, /**< bound disjunction constraint to branch on */
1754 SCIP_SOL* sol /**< solution which should be enforced (NULL for LP solution) */
1755 )
1756 {
1757 SCIP_CONSDATA* consdata;
1758 SCIP_VAR** vars;
1759 SCIP_BOUNDTYPE* boundtypes;
1760 SCIP_Real* bounds;
1761 SCIP_Real varlb;
1762 SCIP_Real varub;
1763 int nvars;
1764 int v;
1765
1766 SCIP_Real priority;
1767 SCIP_Real estimate;
1768 SCIP_NODE* node;
1769
1770 assert(cons != NULL);
1771 assert(SCIPconsGetHdlr(cons) != NULL);
1772 assert(strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) == 0);
1773
1774 consdata = SCIPconsGetData(cons);
1775 assert(consdata != NULL);
1776 nvars = consdata->nvars;
1777 vars = consdata->vars;
1778 boundtypes = consdata->boundtypes;
1779 bounds = consdata->bounds;
1780 assert(nvars == 0 || vars != NULL);
1781 assert(nvars == 0 || boundtypes != NULL);
1782 assert(nvars == 0 || bounds != NULL);
1783
1784 for( v = 0; v < nvars; ++v )
1785 {
1786 SCIP_VAR* var;
1787
1788 var = vars[v];
1789 assert(var != NULL);
1790
1791 /* constraint should be violated, so all bounds in the constraint have to be violated */
1792 assert( !(boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasGE(scip, var, SCIPgetSolVal(scip, sol, var), bounds[v])) && /*lint !e666*/
1793 !(boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasLE(scip, var, SCIPgetSolVal(scip, sol, var), bounds[v])) ); /*lint !e666*/
1794
1795 varlb = SCIPcomputeVarLbLocal(scip, var);
1796 varub = SCIPcomputeVarUbLocal(scip, var);
1797
1798 /* if literal is x >= varlb, but upper bound on x is < varlb, then this literal can never be satisfied,
1799 * thus there is no use in creating an extra child for it
1800 */
1801 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER && isFeasLT(scip, var, varub, bounds[v]) )
1802 continue;
1803 /* if literal is x <= varub, but lower bound on x is > varub, then this literal can never be satisfied,
1804 * thus there is no use in creating an extra child for it
1805 */
1806 if( boundtypes[v] == SCIP_BOUNDTYPE_UPPER && isFeasGT(scip, var, varlb, bounds[v]) )
1807 continue;
1808 /* if literal is always satisfied, then no need to branch on it */
1809 if( isLiteralSatisfied(scip, consdata, v) )
1810 continue;
1811
1812 /* create a child that enforces the current literal */
1813 priority = SCIPcalcNodeselPriority(scip, var, boundtypes[v] == SCIP_BOUNDTYPE_LOWER ?
1814 SCIP_BRANCHDIR_UPWARDS : SCIP_BRANCHDIR_DOWNWARDS, bounds[v]);
1815 estimate = SCIPcalcChildEstimate (scip, var, bounds[v]);
1816
1817 SCIPdebugMsg(scip, " -> creating child to enforce: <%s> %c= %g (priority: %g, estimate: %g)\n",
1818 SCIPvarGetName(vars[v]), boundtypes[v] == SCIP_BOUNDTYPE_LOWER ? '>' : '<', bounds[v], priority, estimate);
1819
1820 SCIP_CALL( SCIPcreateChild(scip, &node, priority, estimate) );
1821
1822 /* enforce current literal */
1823 if( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
1824 {
1825 SCIP_CONS* brcons;
1826 SCIP_Real one;
1827
1828 one = 1.0;
1829
1830 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1831 {
1832 SCIP_CALL( SCIPcreateConsLinear(scip, &brcons, "bounddisjbranch", 1, &var, &one, bounds[v], SCIPinfinity(scip),
1833 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
1834 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
1835 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
1836 SCIPconsIsStickingAtNode(cons)) );
1837 }
1838 else
1839 {
1840 SCIP_CALL( SCIPcreateConsLinear(scip, &brcons, "bounddisjbranch", 1, &var, &one, -SCIPinfinity(scip), bounds[v],
1841 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
1842 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
1843 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
1844 SCIPconsIsStickingAtNode(cons)) );
1845 }
1846 SCIP_CALL( SCIPaddConsNode(scip, node, brcons, NULL) );
1847 SCIP_CALL( SCIPreleaseCons(scip, &brcons) );
1848 }
1849 else
1850 {
1851 assert(SCIPvarIsActive(var));
1852 if( boundtypes[v] == SCIP_BOUNDTYPE_LOWER )
1853 {
1854 SCIP_CALL( SCIPchgVarLbNode(scip, node, var, bounds[v]) );
1855 }
1856 else
1857 {
1858 SCIP_CALL( SCIPchgVarUbNode(scip, node, var, bounds[v]) );
1859 }
1860 }
1861
1862 /* delete bound disjunction constraint from child node */
1863 SCIP_CALL( SCIPdelConsNode(scip, node, cons) );
1864 }
1865
1866 return SCIP_OKAY;
1867 }
1868
1869 /** helper function to enforce constraints */
1870 static
enforceConstraint(SCIP * scip,SCIP_CONSHDLR * conshdlr,SCIP_CONS ** conss,int nconss,SCIP_SOL * sol,SCIP_RESULT * result)1871 SCIP_RETCODE enforceConstraint(
1872 SCIP* scip, /**< SCIP data structure */
1873 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1874 SCIP_CONS** conss, /**< constraints to process */
1875 int nconss, /**< number of constraints */
1876 SCIP_SOL* sol, /**< solution to enforce (NULL for the LP solution) */
1877 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
1878 )
1879 {
1880 SCIP_CONSHDLRDATA* conshdlrdata;
1881 SCIP_Bool cutoff;
1882 SCIP_Bool infeasible;
1883 SCIP_Bool reduceddom;
1884 SCIP_Bool registeredbrcand;
1885 SCIP_Bool infeasiblecons;
1886 int c;
1887 int nnarybranchconsvars;
1888 SCIP_CONS* narybranchcons; /* constraint that is a candidate for an n-ary branch */
1889
1890 assert(conshdlr != NULL);
1891 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1892 assert(nconss == 0 || conss != NULL);
1893 assert(result != NULL);
1894
1895 SCIPdebugMsg(scip, "Enforcing %d bound disjunction constraints for %s solution\n", nconss, sol == NULL ? "LP" : "relaxation");
1896
1897 *result = SCIP_FEASIBLE;
1898
1899 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1900 assert(conshdlrdata != NULL);
1901
1902 cutoff = FALSE;
1903 infeasible = FALSE;
1904 reduceddom = FALSE;
1905 registeredbrcand = FALSE;
1906 narybranchcons = NULL;
1907 nnarybranchconsvars = INT_MAX;
1908
1909 /* check all bound disjunction constraints for feasibility */
1910 for( c = 0; c < nconss && !cutoff && !reduceddom; ++c )
1911 {
1912 infeasiblecons = FALSE;
1913 SCIP_CALL( enforceCurrentSol(scip, conss[c], sol, conshdlrdata->eventhdlr, &cutoff, &infeasiblecons, &reduceddom,
1914 ®isteredbrcand) );
1915 infeasible |= infeasiblecons;
1916 if( infeasiblecons && !registeredbrcand )
1917 {
1918 /* if cons. c has less literals than the previous candidate for an n-ary branch, then keep cons. c as candidate for n-ary branch */
1919 if( narybranchcons == NULL || SCIPconsGetData(conss[c])->nvars < nnarybranchconsvars )
1920 {
1921 narybranchcons = conss[c];
1922 nnarybranchconsvars = SCIPconsGetData(narybranchcons)->nvars;
1923 assert(nnarybranchconsvars > 0);
1924 }
1925 }
1926 }
1927
1928 if( cutoff )
1929 *result = SCIP_CUTOFF;
1930 else if( reduceddom )
1931 *result = SCIP_REDUCEDDOM;
1932 else if( infeasible )
1933 {
1934 if( registeredbrcand )
1935 {
1936 *result = SCIP_INFEASIBLE;
1937 }
1938 else
1939 {
1940 SCIP_CALL( createNAryBranch(scip, narybranchcons, sol) );
1941 *result = SCIP_BRANCHED;
1942 }
1943 }
1944
1945 return SCIP_OKAY;
1946 }
1947
1948 /**@} */
1949
1950 /**@name Upgrading methods for special quadratic constraint
1951 *
1952 * @{
1953 */
1954
1955 /** upgrades quadratic complementarity constraints into a bounddisjunction constraint
1956 * If constraint is of form (x - a) * (y - b) = 0 with x >= a and y >= b for some a and b,
1957 * then upgrade to bounddisjunction constraint "x <= a or y <= b".
1958 * If constraint is of form (x - a) * (y - b) >= 0,
1959 * then upgrade to bounddisjunction constraints "x >= a or y <= b" and "x <= a or y >= b".
1960 */
1961 static
SCIP_DECL_QUADCONSUPGD(upgradeConsQuadratic)1962 SCIP_DECL_QUADCONSUPGD(upgradeConsQuadratic)
1963 { /*lint --e{715}*/
1964 char name[SCIP_MAXSTRLEN];
1965 SCIP_BOUNDTYPE boundtypes[2];
1966 SCIP_Real bounds[2];
1967 SCIP_VAR* xy[2];
1968 SCIP_QUADVARTERM* quadvarterms;
1969 SCIP_Real coefxy;
1970 SCIP_Real coefx;
1971 SCIP_Real coefy;
1972 SCIP_Real lhs;
1973 SCIP_Real rhs;
1974 SCIP_Real a;
1975 SCIP_Real b;
1976 SCIP_VAR* x;
1977 SCIP_VAR* y;
1978
1979 assert(scip != NULL);
1980 assert(cons != NULL);
1981 assert(nupgdconss != NULL);
1982 assert(upgdconss != NULL);
1983
1984 *nupgdconss = 0;
1985
1986 SCIPdebugMsg(scip, "upgradeConsQuadratic called for constraint <%s>\n", SCIPconsGetName(cons));
1987 SCIPdebugPrintCons(scip, cons, NULL);
1988
1989 if( SCIPgetNLinearVarsQuadratic(scip, cons) != 0 )
1990 return SCIP_OKAY;
1991 if( SCIPgetNQuadVarTermsQuadratic(scip, cons) != 2 )
1992 return SCIP_OKAY;
1993 if( SCIPgetNBilinTermsQuadratic(scip, cons) != 1 )
1994 return SCIP_OKAY;
1995 /* do not upgrade x*y <=/== rhs with x (or y) binary
1996 * the reformulation for such terms in cons_quadratic should handle this better
1997 */
1998 if( nbinquad > 0 )
1999 return SCIP_OKAY;
2000
2001 lhs = SCIPgetLhsQuadratic(scip, cons);
2002 rhs = SCIPgetRhsQuadratic(scip, cons);
2003
2004 /* we don't want a free constraint */
2005 if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
2006 return SCIP_OKAY;
2007
2008 /* we currently don't want a ranged constraint (could upgrade at most one side) */
2009 if( !SCIPisInfinity(scip, -lhs) && !SCIPisInfinity(scip, rhs) && !SCIPisEQ(scip, lhs, rhs) )
2010 return SCIP_OKAY;
2011
2012 quadvarterms = SCIPgetQuadVarTermsQuadratic(scip, cons);
2013
2014 /* we don't want square terms */
2015 if( !SCIPisZero(scip, quadvarterms[0].sqrcoef) || !SCIPisZero(scip, quadvarterms[1].sqrcoef) )
2016 return SCIP_OKAY;
2017
2018 x = quadvarterms[0].var;
2019 y = quadvarterms[1].var;
2020 assert(x != y);
2021
2022 coefx = quadvarterms[0].lincoef;
2023 coefy = quadvarterms[1].lincoef;
2024
2025 coefxy = SCIPgetBilinTermsQuadratic(scip, cons)[0].coef;
2026 assert(SCIPgetBilinTermsQuadratic(scip, cons)[0].var1 == x || SCIPgetBilinTermsQuadratic(scip, cons)[0].var1 == y);
2027 assert(SCIPgetBilinTermsQuadratic(scip, cons)[0].var2 == x || SCIPgetBilinTermsQuadratic(scip, cons)[0].var2 == y);
2028 assert(!SCIPisZero(scip, coefxy));
2029
2030 /* divide by coefxy */
2031 coefx /= coefxy;
2032 coefy /= coefxy;
2033 if( coefxy > 0.0 )
2034 {
2035 if( !SCIPisInfinity(scip, -lhs) )
2036 lhs /= coefxy;
2037 if( !SCIPisInfinity(scip, rhs) )
2038 rhs /= coefxy;
2039 }
2040 else
2041 {
2042 SCIP_Real tmp;
2043
2044 if( !SCIPisInfinity(scip, rhs) )
2045 tmp = rhs / coefxy;
2046 else
2047 tmp = -SCIPinfinity(scip);
2048 if( !SCIPisInfinity(scip, -lhs) )
2049 rhs = lhs / coefxy;
2050 else
2051 rhs = SCIPinfinity(scip);
2052 lhs = tmp;
2053 }
2054
2055 /* now have form lhs <= x*y + coefx x + coefy y <= rhs
2056 * <-> lhs + coefx * coefy <= (x + coefy) * (y + coefx) <= rhs + coefx * coefy
2057 */
2058
2059 /* handle case (x + coefy) * (y + coefx) == rhs + coefx * coefy */
2060 if( SCIPisEQ(scip, lhs, rhs) )
2061 {
2062 /* check whether rhs + coefx * coefy == 0 */
2063 if( !SCIPisZero(scip, rhs + coefx * coefy) )
2064 return SCIP_OKAY;
2065
2066 a = -coefy;
2067 b = -coefx;
2068
2069 /* now have complementarity form x = a or y = b */
2070
2071 /* we can write this as up to four bounddisjunction constraint:
2072 * (x >= a or y >= b) and (x <= a or y >= b) and (x >= a or y <= b) and (x <= a or y <= b)
2073 *
2074 * count whether we need to create 1, 2, or 4 constraints
2075 */
2076 if( !SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) && !SCIPisLE(scip, SCIPvarGetUbGlobal(x), a) )
2077 *nupgdconss = 2;
2078 else
2079 *nupgdconss = 1;
2080
2081 if( !SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) && !SCIPisLE(scip, SCIPvarGetUbGlobal(y), b) )
2082 *nupgdconss *= 2;
2083
2084 if( upgdconsssize < *nupgdconss )
2085 {
2086 /* signal that we need more memory */
2087 *nupgdconss = -*nupgdconss;
2088 return SCIP_OKAY;
2089 }
2090
2091 xy[0] = x;
2092 xy[1] = y;
2093 bounds[0] = a;
2094 bounds[1] = b;
2095 if( *nupgdconss == 1 )
2096 {
2097 boundtypes[0] = SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER;
2098 boundtypes[1] = SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER;
2099 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], SCIPconsGetName(cons),
2100 2, xy, boundtypes, bounds,
2101 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2102 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2103 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2104 SCIPconsIsStickingAtNode(cons)) );
2105
2106 SCIPdebugMsg(scip, "created bounddisjunction constraint:\n");
2107 SCIPdebugPrintCons(scip, upgdconss[0], NULL);
2108
2109 return SCIP_OKAY;
2110 }
2111 else if( SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) || SCIPisLE(scip, SCIPvarGetUbGlobal(x), a) )
2112 {
2113 assert(!SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) && !SCIPisLE(scip, SCIPvarGetUbGlobal(y), b));
2114 assert(*nupgdconss == 2);
2115
2116 boundtypes[0] = SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER;
2117
2118 /* create constraint with y >= b */
2119 boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
2120 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
2121 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
2122 2, xy, boundtypes, bounds,
2123 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2124 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2125 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2126 SCIPconsIsStickingAtNode(cons)) );
2127
2128 /* create constraint with y <= b */
2129 boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
2130 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper", SCIPconsGetName(cons));
2131 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
2132 2, xy, boundtypes, bounds,
2133 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2134 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2135 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2136 SCIPconsIsStickingAtNode(cons)) );
2137
2138 SCIPdebugMsg(scip, "created bounddisjunction constraints:\n");
2139 SCIPdebugPrintCons(scip, upgdconss[0], NULL);
2140 SCIPdebugPrintCons(scip, upgdconss[1], NULL);
2141 }
2142 else if( SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) || SCIPisLE(scip, SCIPvarGetUbGlobal(y), b) )
2143 {
2144 assert(!SCIPisEQ(scip, SCIPvarGetLbGlobal(x), a) && !SCIPisEQ(scip, SCIPvarGetUbGlobal(x), a));
2145 assert(*nupgdconss == 2);
2146
2147 boundtypes[1] = SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) ? SCIP_BOUNDTYPE_UPPER : SCIP_BOUNDTYPE_LOWER;
2148
2149 /* create constraint with x >= a */
2150 boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
2151 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
2152 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
2153 2, xy, boundtypes, bounds,
2154 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2155 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2156 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2157 SCIPconsIsStickingAtNode(cons)) );
2158
2159 /* create constraint with x <= a */
2160 boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
2161 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
2162 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
2163 2, xy, boundtypes, bounds,
2164 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2165 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2166 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2167 SCIPconsIsStickingAtNode(cons)) );
2168
2169 SCIPdebugMsg(scip, "created bounddisjunction constraints:\n");
2170 SCIPdebugPrintCons(scip, upgdconss[0], NULL);
2171 SCIPdebugPrintCons(scip, upgdconss[1], NULL);
2172 }
2173 else
2174 {
2175 assert(!SCIPisGE(scip, SCIPvarGetLbGlobal(x), a) && !SCIPisLE(scip, SCIPvarGetUbGlobal(x), a));
2176 assert(!SCIPisGE(scip, SCIPvarGetLbGlobal(y), b) && !SCIPisLE(scip, SCIPvarGetUbGlobal(y), b));
2177 assert(*nupgdconss == 4);
2178
2179 /* create constraint x >= a or y >= a */
2180 boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
2181 boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
2182 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower_lower", SCIPconsGetName(cons));
2183 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
2184 2, xy, boundtypes, bounds,
2185 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2186 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2187 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2188 SCIPconsIsStickingAtNode(cons)) );
2189
2190 /* create constraint x >= a or y <= a */
2191 boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
2192 boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
2193 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower_upper", SCIPconsGetName(cons));
2194 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
2195 2, xy, boundtypes, bounds,
2196 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2197 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2198 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2199 SCIPconsIsStickingAtNode(cons)) );
2200
2201 /* create constraint x <= a or y >= a */
2202 boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
2203 boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
2204 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper_lower", SCIPconsGetName(cons));
2205 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[2], name,
2206 2, xy, boundtypes, bounds,
2207 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2208 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2209 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2210 SCIPconsIsStickingAtNode(cons)) );
2211
2212 /* create constraint x <= a or y <= a */
2213 boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
2214 boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
2215 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper_upper", SCIPconsGetName(cons));
2216 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[3], name,
2217 2, xy, boundtypes, bounds,
2218 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2219 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2220 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2221 SCIPconsIsStickingAtNode(cons)) );
2222
2223 SCIPdebugMsg(scip, "created bounddisjunction constraints:\n");
2224 SCIPdebugPrintCons(scip, upgdconss[0], NULL);
2225 SCIPdebugPrintCons(scip, upgdconss[1], NULL);
2226 SCIPdebugPrintCons(scip, upgdconss[2], NULL);
2227 SCIPdebugPrintCons(scip, upgdconss[3], NULL);
2228 }
2229
2230 return SCIP_OKAY;
2231 }
2232
2233 /* handle case (x + coefy) * (y + coefx) <= rhs + coefx * coefy */
2234 if( !SCIPisInfinity(scip, rhs) )
2235 {
2236 assert(SCIPisInfinity(scip, -lhs));
2237
2238 /* check whether rhs + coefx * coefy == 0 */
2239 if( !SCIPisZero(scip, rhs + coefx * coefy) )
2240 return SCIP_OKAY;
2241
2242 a = -coefy;
2243 b = -coefx;
2244
2245 /* now have form (x >= a and y <= b) or (x <= a and y >= b)
2246 * which is equivalent to (x >= a or y >= b) and (x <= a or y <= b)
2247 * the latter can be represented as two bound disjunction constraints
2248 */
2249
2250 if( upgdconsssize < 2 )
2251 {
2252 /* signal that we need more memory */
2253 *nupgdconss = -2;
2254 return SCIP_OKAY;
2255 }
2256
2257 xy[0] = x;
2258 xy[1] = y;
2259 bounds[0] = a;
2260 bounds[1] = b;
2261
2262 /* create constraint x >= a or y >= b */
2263 boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
2264 boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
2265 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
2266 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
2267 2, xy, boundtypes, bounds,
2268 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2269 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2270 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2271 SCIPconsIsStickingAtNode(cons)) );
2272
2273 /* create constraint x <= a or y <= b */
2274 boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
2275 boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
2276 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper", SCIPconsGetName(cons));
2277 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
2278 2, xy, boundtypes, bounds,
2279 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2280 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2281 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2282 SCIPconsIsStickingAtNode(cons)) );
2283
2284 SCIPdebugMsg(scip, "created bounddisjunction constraints:\n");
2285 SCIPdebugPrintCons(scip, upgdconss[0], NULL);
2286 SCIPdebugPrintCons(scip, upgdconss[1], NULL);
2287
2288 *nupgdconss = 2;
2289
2290 return SCIP_OKAY;
2291 }
2292
2293 /* handle remaining case (x + coefy) * (y + coefx) >= lhs + coefx * coefy */
2294 {
2295 assert(!SCIPisInfinity(scip, -lhs));
2296 assert( SCIPisInfinity(scip, rhs));
2297
2298 /* check whether lhs + coefx * coefy == 0 */
2299 if( !SCIPisZero(scip, lhs + coefx * coefy) )
2300 return SCIP_OKAY;
2301
2302 a = -coefy;
2303 b = -coefx;
2304
2305 /* now have form (x >= a and y >= b) or (x <= a and y <= b)
2306 * which is equivalent to (x >= a or y <= b) and (x <= a or y >= b)
2307 * the latter can be represented as two bound disjunction constraints
2308 */
2309
2310 if( upgdconsssize < 2 )
2311 {
2312 /* signal that we need more memory */
2313 *nupgdconss = -2;
2314 return SCIP_OKAY;
2315 }
2316
2317 xy[0] = x;
2318 xy[1] = y;
2319 bounds[0] = a;
2320 bounds[1] = b;
2321
2322 /* create constraint x >= a or y <= b */
2323 boundtypes[0] = SCIP_BOUNDTYPE_LOWER;
2324 boundtypes[1] = SCIP_BOUNDTYPE_UPPER;
2325 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_lower", SCIPconsGetName(cons));
2326 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[0], name,
2327 2, xy, boundtypes, bounds,
2328 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2329 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2330 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2331 SCIPconsIsStickingAtNode(cons)) );
2332
2333 /* create constraint x <= a or y >= b */
2334 boundtypes[0] = SCIP_BOUNDTYPE_UPPER;
2335 boundtypes[1] = SCIP_BOUNDTYPE_LOWER;
2336 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "%s_upper", SCIPconsGetName(cons));
2337 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &upgdconss[1], name,
2338 2, xy, boundtypes, bounds,
2339 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2340 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2341 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2342 SCIPconsIsStickingAtNode(cons)) );
2343
2344 SCIPdebugMsg(scip, "created bounddisjunction constraints:\n");
2345 SCIPdebugPrintCons(scip, upgdconss[0], NULL);
2346 SCIPdebugPrintCons(scip, upgdconss[1], NULL);
2347
2348 *nupgdconss = 2;
2349 }
2350
2351 return SCIP_OKAY;
2352 }
2353
2354 /**@} */
2355
2356 /**@name Callback methods of constraint handler
2357 *
2358 * @{
2359 */
2360
2361 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
2362 static
SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBounddisjunction)2363 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyBounddisjunction)
2364 { /*lint --e{715}*/
2365 assert(scip != NULL);
2366 assert(conshdlr != NULL);
2367 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2368
2369 /* call inclusion method of constraint handler */
2370 SCIP_CALL( SCIPincludeConshdlrBounddisjunction(scip) );
2371
2372 *valid = TRUE;
2373
2374 return SCIP_OKAY;
2375 }
2376
2377 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
2378 static
SCIP_DECL_CONSFREE(consFreeBounddisjunction)2379 SCIP_DECL_CONSFREE(consFreeBounddisjunction)
2380 { /*lint --e{715}*/
2381 SCIP_CONSHDLRDATA* conshdlrdata;
2382
2383 assert(conshdlr != NULL);
2384 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2385 assert(scip != NULL);
2386
2387 /* free constraint handler data */
2388 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2389 assert(conshdlrdata != NULL);
2390
2391 conshdlrdataFree(scip, &conshdlrdata);
2392
2393 SCIPconshdlrSetData(conshdlr, NULL);
2394
2395 return SCIP_OKAY;
2396 }
2397
2398
2399 /** presolving deinitialization method of constraint handler (called after presolving has been finished) */
2400 static
SCIP_DECL_CONSEXITPRE(consExitpreBounddisjunction)2401 SCIP_DECL_CONSEXITPRE(consExitpreBounddisjunction)
2402 { /*lint --e{715}*/
2403 SCIP_CONSHDLRDATA* conshdlrdata;
2404 SCIP_CONS* cons;
2405 SCIP_Bool redundant;
2406 int c;
2407
2408 assert(conshdlr != NULL);
2409 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2410 assert(scip != NULL);
2411
2412 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2413 assert(conshdlrdata != NULL);
2414
2415 /* fast processing of constraints, apply global bounds and remove fixed variables */
2416 for( c = 0; c < nconss; ++c )
2417 {
2418 cons = conss[c];
2419 assert(cons != NULL);
2420
2421 SCIPdebugMsg(scip, "exit-presolving bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2422
2423 if( SCIPconsIsDeleted(cons) )
2424 continue;
2425
2426 /* remove all literals that are violated in global bounds, check redundancy due to global bounds */
2427 SCIP_CALL( applyGlobalBounds(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2428
2429 if( !redundant )
2430 {
2431 /* replace variables by their representative active (or multi-aggregated) variables */
2432 SCIP_CALL( removeFixedVariables(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2433 }
2434
2435 if( redundant && SCIPconsIsAdded(cons) )
2436 {
2437 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is redundant\n", SCIPconsGetName(cons));
2438 SCIP_CALL( SCIPdelCons(scip, cons) );
2439 }
2440 }
2441
2442 return SCIP_OKAY;
2443 }
2444
2445
2446 /** frees specific constraint data */
2447 static
SCIP_DECL_CONSDELETE(consDeleteBounddisjunction)2448 SCIP_DECL_CONSDELETE(consDeleteBounddisjunction)
2449 { /*lint --e{715}*/
2450 assert(conshdlr != NULL);
2451 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2452 assert(consdata != NULL);
2453 assert(*consdata != NULL);
2454
2455 /* free LP row and bound disjunction constraint */
2456 consdataFree(scip, consdata);
2457
2458 return SCIP_OKAY;
2459 }
2460
2461
2462 /** transforms constraint data into data belonging to the transformed problem */
2463 static
SCIP_DECL_CONSTRANS(consTransBounddisjunction)2464 SCIP_DECL_CONSTRANS(consTransBounddisjunction)
2465 { /*lint --e{715}*/
2466 SCIP_CONSDATA* sourcedata;
2467 SCIP_CONSDATA* targetdata;
2468
2469 /*debugMsg(scip, "Trans method of bound disjunction constraints\n");*/
2470
2471 assert(conshdlr != NULL);
2472 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2473 assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
2474 assert(sourcecons != NULL);
2475 assert(targetcons != NULL);
2476
2477 sourcedata = SCIPconsGetData(sourcecons);
2478 assert(sourcedata != NULL);
2479
2480 /* create constraint data for target constraint */
2481 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->nvars, sourcedata->vars,
2482 sourcedata->boundtypes, sourcedata->bounds) );
2483
2484 /* create target constraint */
2485 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
2486 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
2487 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
2488 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
2489 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2490
2491 return SCIP_OKAY;
2492 }
2493
2494
2495 /** constraint enforcing method of constraint handler for LP solutions */
2496 static
SCIP_DECL_CONSENFOLP(consEnfolpBounddisjunction)2497 SCIP_DECL_CONSENFOLP(consEnfolpBounddisjunction)
2498 { /*lint --e{715}*/
2499 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, NULL, result) );
2500
2501 return SCIP_OKAY;
2502 }
2503
2504
2505 /** constraint enforcing method of constraint handler for relaxation solutions */
2506 static
SCIP_DECL_CONSENFORELAX(consEnforelaxBounddisjunction)2507 SCIP_DECL_CONSENFORELAX(consEnforelaxBounddisjunction)
2508 { /*lint --e{715}*/
2509 SCIP_CALL( enforceConstraint(scip, conshdlr, conss, nconss, sol, result) );
2510
2511 return SCIP_OKAY;
2512 }
2513
2514
2515 /** constraint enforcing method of constraint handler for pseudo solutions */
2516 static
SCIP_DECL_CONSENFOPS(consEnfopsBounddisjunction)2517 SCIP_DECL_CONSENFOPS(consEnfopsBounddisjunction)
2518 { /*lint --e{715}*/
2519 SCIP_CONSHDLRDATA* conshdlrdata;
2520 SCIP_Bool cutoff;
2521 SCIP_Bool infeasible;
2522 SCIP_Bool reduceddom;
2523 SCIP_Bool registeredbrcand;
2524 int c;
2525 SCIP_CONS* narybranchcons; /* constraint that is a candidate for an n-ary branch */
2526
2527 assert(conshdlr != NULL);
2528 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2529 assert(nconss == 0 || conss != NULL);
2530 assert(result != NULL);
2531
2532 SCIPdebugMsg(scip, "pseudo enforcing %d bound disjunction constraints\n", nconss);
2533
2534 *result = SCIP_FEASIBLE;
2535
2536 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2537 assert(conshdlrdata != NULL);
2538
2539 cutoff = FALSE;
2540 infeasible = FALSE;
2541 reduceddom = FALSE;
2542 registeredbrcand = FALSE;
2543 narybranchcons = NULL;
2544
2545 /* check all bound disjunction constraints for feasibility */
2546 for( c = 0; c < nconss && !cutoff && !reduceddom; ++c )
2547 {
2548 SCIP_CALL( enforceCurrentSol(scip, conss[c], NULL, conshdlrdata->eventhdlr, &cutoff, &infeasible, &reduceddom,
2549 ®isteredbrcand) );
2550 if( infeasible && !registeredbrcand )
2551 {
2552 /* if cons. c has less literals than the previous candidate for an n-ary branch, then keep cons. c as candidate for n-ary branch */
2553 if( !narybranchcons || SCIPconsGetData(conss[c])->nvars < SCIPconsGetData(narybranchcons)->nvars )
2554 narybranchcons = conss[c];
2555 }
2556 }
2557
2558 if( cutoff )
2559 *result = SCIP_CUTOFF;
2560 else if( reduceddom )
2561 *result = SCIP_REDUCEDDOM;
2562 else if( infeasible )
2563 {
2564 if( registeredbrcand )
2565 {
2566 *result = SCIP_INFEASIBLE;
2567 }
2568 else
2569 {
2570 SCIP_CALL( createNAryBranch(scip, narybranchcons, NULL) );
2571 *result = SCIP_BRANCHED;
2572 }
2573 }
2574
2575 return SCIP_OKAY;
2576 }
2577
2578
2579 /** feasibility check method of constraint handler for integral solutions */
2580 static
SCIP_DECL_CONSCHECK(consCheckBounddisjunction)2581 SCIP_DECL_CONSCHECK(consCheckBounddisjunction)
2582 { /*lint --e{715}*/
2583 SCIP_CONS* cons;
2584 SCIP_CONSDATA* consdata;
2585 int c;
2586
2587 assert(conshdlr != NULL);
2588 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2589 assert(nconss == 0 || conss != NULL);
2590 assert(result != NULL);
2591
2592 *result = SCIP_FEASIBLE;
2593
2594 /* check all bound disjunction constraints for feasibility */
2595 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
2596 {
2597 cons = conss[c];
2598 consdata = SCIPconsGetData(cons);
2599 assert(consdata != NULL);
2600
2601 if( isConsViolated(scip, cons, sol) )
2602 {
2603 if( printreason )
2604 {
2605 int v;
2606
2607 SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
2608 SCIPinfoMessage(scip, NULL, ";\nviolation: ");
2609 for( v = 0; v < consdata->nvars; ++v )
2610 {
2611 assert(consdata->vars[v] != NULL);
2612 if( v > 0 )
2613 SCIPinfoMessage(scip, NULL, ", ");
2614 SCIPinfoMessage(scip, NULL, "<%s> = %.15g",
2615 SCIPvarGetName(consdata->vars[v]), SCIPgetSolVal(scip, sol, consdata->vars[v]));
2616 }
2617 SCIPinfoMessage(scip, NULL, ")\n");
2618 }
2619
2620 /* constraint is violated */
2621 *result = SCIP_INFEASIBLE;
2622 }
2623 }
2624
2625 return SCIP_OKAY;
2626 }
2627
2628
2629 /** domain propagation method of constraint handler */
2630 static
SCIP_DECL_CONSPROP(consPropBounddisjunction)2631 SCIP_DECL_CONSPROP(consPropBounddisjunction)
2632 { /*lint --e{715}*/
2633 SCIP_CONSHDLRDATA* conshdlrdata;
2634 SCIP_Bool cutoff;
2635 SCIP_Bool infeasible;
2636 SCIP_Bool reduceddom;
2637 SCIP_Bool mustcheck;
2638 SCIP_Bool consreduceddom;
2639 int c;
2640
2641 assert(conshdlr != NULL);
2642 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2643 assert(nconss == 0 || conss != NULL);
2644 assert(result != NULL);
2645
2646 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2647 assert(conshdlrdata != NULL);
2648
2649 cutoff = FALSE;
2650 infeasible = FALSE;
2651 reduceddom = FALSE;
2652
2653 /* propagate all useful bound disjunction constraints */
2654 for( c = 0; c < nusefulconss && !cutoff; ++c )
2655 {
2656 SCIP_CALL( processWatchedVars(scip, conss[c], conshdlrdata->eventhdlr,
2657 &cutoff, &infeasible, &consreduceddom, &mustcheck) );
2658 reduceddom = reduceddom || consreduceddom;
2659 }
2660
2661 /* return the correct result */
2662 if( cutoff )
2663 *result = SCIP_CUTOFF;
2664 else if( reduceddom )
2665 *result = SCIP_REDUCEDDOM;
2666 else
2667 *result = SCIP_DIDNOTFIND;
2668
2669 return SCIP_OKAY; /*lint !e438*/
2670 }
2671
2672
2673 /** presolving method of constraint handler */
2674 static
SCIP_DECL_CONSPRESOL(consPresolBounddisjunction)2675 SCIP_DECL_CONSPRESOL(consPresolBounddisjunction)
2676 { /*lint --e{715}*/
2677 SCIP_CONSHDLRDATA* conshdlrdata;
2678 SCIP_CONS* cons;
2679 SCIP_CONSDATA* consdata;
2680 SCIP_Bool infeasible;
2681 SCIP_Bool redundant;
2682 SCIP_Bool tightened;
2683 int c;
2684
2685 assert(conshdlr != NULL);
2686 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2687 assert(scip != NULL);
2688 assert(result != NULL);
2689
2690 *result = SCIP_DIDNOTFIND;
2691
2692 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2693 assert(conshdlrdata != NULL);
2694
2695 /* process constraints */
2696 for( c = 0; c < nconss && *result != SCIP_CUTOFF && !SCIPisStopped(scip); ++c )
2697 {
2698 cons = conss[c];
2699 assert(cons != NULL);
2700 consdata = SCIPconsGetData(cons);
2701 assert(consdata != NULL);
2702
2703 SCIPdebugMsg(scip, "presolving bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2704
2705 /* force presolving the constraint in the initial round */
2706 if( nrounds == 0 )
2707 {
2708 SCIP_CALL( SCIPenableConsPropagation(scip, cons) );
2709 }
2710
2711 /* remove all literals that are violated in global bounds, check redundancy due to global bounds */
2712 SCIP_CALL( applyGlobalBounds(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2713
2714 if( !redundant )
2715 {
2716 /* replace variables by their representative active (or multi-aggregated) variables */
2717 SCIP_CALL( removeFixedVariables(scip, cons, conshdlrdata->eventhdlr, &redundant) );
2718 }
2719
2720 /**@todo find pairs of negated variables in constraint: constraint is redundant */
2721 /**@todo find sets of equal variables in constraint: multiple entries of variable can be replaced by single entry */
2722
2723 if( redundant )
2724 {
2725 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is redundant\n", SCIPconsGetName(cons));
2726 SCIP_CALL( SCIPdelCons(scip, cons) );
2727 (*ndelconss)++;
2728 *result = SCIP_SUCCESS;
2729 continue;
2730 }
2731 else if( !SCIPconsIsModifiable(cons) )
2732 {
2733 /* if unmodifiable constraint has no variables, it is infeasible,
2734 * if unmodifiable constraint has only one variable, the literal can be satisfied and the constraint deleted
2735 */
2736 if( consdata->nvars == 0 )
2737 {
2738 SCIPdebugMsg(scip, "bound disjunction constraint <%s> is infeasible\n", SCIPconsGetName(cons));
2739 *result = SCIP_CUTOFF;
2740 return SCIP_OKAY;
2741 }
2742 else if( consdata->nvars == 1 )
2743 {
2744 SCIPdebugMsg(scip, "bound disjunction constraint <%s> has only one undecided literal\n",
2745 SCIPconsGetName(cons));
2746
2747 assert(consdata->vars != NULL);
2748 assert(!isLiteralSatisfied(scip, consdata, 0));
2749 assert(!isLiteralViolated(scip, consdata, 0));
2750
2751 if( SCIPvarIsActive(consdata->vars[0]) )
2752 {
2753 if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER )
2754 {
2755 SCIP_CALL( SCIPtightenVarLb(scip, consdata->vars[0], consdata->bounds[0], TRUE, &infeasible, &tightened) );
2756 }
2757 else
2758 {
2759 SCIP_CALL( SCIPtightenVarUb(scip, consdata->vars[0], consdata->bounds[0], TRUE, &infeasible, &tightened) );
2760 }
2761 if( infeasible )
2762 {
2763 SCIPdebugMsg(scip, " -> infeasible fixing\n");
2764 *result = SCIP_CUTOFF;
2765 return SCIP_OKAY;
2766 }
2767 assert(tightened);
2768 (*nchgbds)++;
2769 }
2770 else
2771 {
2772 /* upgrade to a linear constraint, if vars[0] is multi-aggregated */
2773 SCIP_CONS* lincons;
2774 SCIP_Real one;
2775
2776 assert(SCIPvarGetStatus(consdata->vars[0]) == SCIP_VARSTATUS_MULTAGGR);
2777
2778 one = 1.0;
2779 if( consdata->boundtypes[0] == SCIP_BOUNDTYPE_LOWER )
2780 {
2781 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons),
2782 1, &consdata->vars[0], &one, consdata->bounds[0], SCIPinfinity(scip),
2783 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2784 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2785 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2786 SCIPconsIsStickingAtNode(cons)) );
2787 }
2788 else
2789 {
2790 SCIP_CALL( SCIPcreateConsLinear(scip, &lincons, SCIPconsGetName(cons),
2791 1, &consdata->vars[0], &one, -SCIPinfinity(scip), consdata->bounds[0],
2792 SCIPconsIsInitial(cons), SCIPconsIsSeparated(cons), SCIPconsIsEnforced(cons),
2793 SCIPconsIsChecked(cons), SCIPconsIsPropagated(cons), SCIPconsIsLocal(cons),
2794 SCIPconsIsModifiable(cons), SCIPconsIsDynamic(cons), SCIPconsIsRemovable(cons),
2795 SCIPconsIsStickingAtNode(cons)) );
2796 }
2797 SCIP_CALL( SCIPaddCons(scip, lincons) );
2798 SCIP_CALL( SCIPreleaseCons(scip, &lincons) );
2799 (*nupgdconss)++;
2800 }
2801
2802 SCIP_CALL( SCIPdelCons(scip, cons) );
2803 (*ndelconss)++;
2804 *result = SCIP_SUCCESS;
2805 continue;
2806 }
2807 else
2808 {
2809 /* try to upgrade the bounddisjunction constraint */
2810 SCIP_CALL( upgradeCons(scip, cons, ndelconss, naddconss) );
2811 }
2812 }
2813 }
2814
2815 /**@todo preprocess pairs of bound disjunction constraints */
2816
2817 return SCIP_OKAY;
2818 }
2819
2820
2821 /** propagation conflict resolving method of constraint handler */
2822 static
SCIP_DECL_CONSRESPROP(consRespropBounddisjunction)2823 SCIP_DECL_CONSRESPROP(consRespropBounddisjunction)
2824 { /*lint --e{715}*/
2825 SCIP_CONSDATA* consdata;
2826 SCIP_VAR** vars;
2827 SCIP_BOUNDTYPE* boundtypes;
2828 #ifndef NDEBUG
2829 SCIP_Real* bounds;
2830 #endif
2831 int v;
2832
2833 assert(conshdlr != NULL);
2834 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2835 assert(cons != NULL);
2836 assert(infervar != NULL);
2837 assert(result != NULL);
2838
2839 consdata = SCIPconsGetData(cons);
2840 assert(consdata != NULL);
2841 assert(consdata->vars != NULL);
2842 assert(consdata->nvars > 0);
2843 assert(0 <= inferinfo && inferinfo < consdata->nvars);
2844 assert(consdata->vars[inferinfo] == infervar);
2845
2846 vars = consdata->vars;
2847 boundtypes = consdata->boundtypes;
2848 #ifndef NDEBUG
2849 bounds = consdata->bounds;
2850 assert(bounds != NULL);
2851 #endif
2852 assert(boundtypes != NULL);
2853
2854 SCIPdebugMsg(scip, "conflict resolving method of bound disjunction constraint handler\n");
2855
2856 /* the only deductions are bounds tightened to a literal's bound on bound disjunction constraints where all other
2857 * literals are violated
2858 */
2859 assert((boundtypes[inferinfo] == SCIP_BOUNDTYPE_LOWER
2860 && SCIPisFeasGE(scip, SCIPgetVarLbAtIndex(scip, infervar, bdchgidx, TRUE), bounds[inferinfo]))
2861 || (boundtypes[inferinfo] == SCIP_BOUNDTYPE_UPPER
2862 && SCIPisFeasLE(scip, SCIPgetVarUbAtIndex(scip, infervar, bdchgidx, TRUE), bounds[inferinfo])));
2863
2864 for( v = 0; v < consdata->nvars; ++v )
2865 {
2866 if( v != inferinfo )
2867 {
2868 assert(consdata->vars[v] != infervar || consdata->boundtypes[v] != consdata->boundtypes[inferinfo]);
2869
2870 /* the reason literal must have been violated
2871 * we do not check for multi-aggregated variables, since SCIPvarGetXbAtIndex is not implemented for them */
2872 /* Use a weaker comparison to SCIPvarGetXbAtIndex here (i.e., SCIPisXT instead of SCIPisFeasXT),
2873 * because SCIPvarGetXbAtIndex might differ from the local bound at time bdchgidx by epsilon. */
2874 assert(SCIPvarGetStatus(vars[v]) == SCIP_VARSTATUS_MULTAGGR
2875 || (boundtypes[v] == SCIP_BOUNDTYPE_LOWER
2876 && SCIPisLT(scip, SCIPgetVarUbAtIndex(scip, vars[v], bdchgidx, TRUE), bounds[v]))
2877 || (boundtypes[v] == SCIP_BOUNDTYPE_UPPER
2878 && SCIPisGT(scip, SCIPgetVarLbAtIndex(scip, vars[v], bdchgidx, TRUE), bounds[v])));
2879 SCIP_CALL( SCIPaddConflictBd(scip, vars[v], SCIPboundtypeOpposite(boundtypes[v]), bdchgidx) );
2880 }
2881 }
2882
2883 *result = SCIP_SUCCESS;
2884
2885 return SCIP_OKAY;
2886 }
2887
2888
2889 /** variable rounding lock method of constraint handler */
2890 static
SCIP_DECL_CONSLOCK(consLockBounddisjunction)2891 SCIP_DECL_CONSLOCK(consLockBounddisjunction)
2892 { /*lint --e{715}*/
2893 SCIP_CONSDATA* consdata;
2894 int i;
2895
2896 consdata = SCIPconsGetData(cons);
2897 assert(consdata != NULL);
2898
2899 /* lock every single coefficient */
2900 for( i = 0; i < consdata->nvars; ++i )
2901 {
2902 if( consdata->boundtypes[i] == SCIP_BOUNDTYPE_LOWER )
2903 {
2904 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlockspos, nlocksneg) );
2905 }
2906 else
2907 {
2908 SCIP_CALL( SCIPaddVarLocksType(scip, consdata->vars[i], locktype, nlocksneg, nlockspos) );
2909 }
2910 }
2911
2912 return SCIP_OKAY;
2913 }
2914
2915
2916 /** constraint activation notification method of constraint handler */
2917 static
SCIP_DECL_CONSACTIVE(consActiveBounddisjunction)2918 SCIP_DECL_CONSACTIVE(consActiveBounddisjunction)
2919 { /*lint --e{715}*/
2920 SCIP_CONSHDLRDATA* conshdlrdata;
2921 SCIP_CONSDATA* consdata;
2922
2923 assert(conshdlr != NULL);
2924 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2925 assert(cons != NULL);
2926 assert(SCIPconsIsTransformed(cons));
2927
2928 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2929 assert(conshdlrdata != NULL);
2930 consdata = SCIPconsGetData(cons);
2931 assert(consdata != NULL);
2932 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
2933
2934 SCIPdebugMsg(scip, "activating information for bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2935 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
2936
2937 /* catch events on watched variables */
2938 if( consdata->watchedvar1 != -1 )
2939 {
2940 SCIP_CALL( catchEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar1,
2941 &consdata->filterpos1) );
2942 }
2943 if( consdata->watchedvar2 != -1 )
2944 {
2945 SCIP_CALL( catchEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar2,
2946 &consdata->filterpos2) );
2947 }
2948
2949 return SCIP_OKAY;
2950 }
2951
2952
2953 /** constraint deactivation notification method of constraint handler */
2954 static
SCIP_DECL_CONSDEACTIVE(consDeactiveBounddisjunction)2955 SCIP_DECL_CONSDEACTIVE(consDeactiveBounddisjunction)
2956 { /*lint --e{715}*/
2957 SCIP_CONSHDLRDATA* conshdlrdata;
2958 SCIP_CONSDATA* consdata;
2959
2960 assert(conshdlr != NULL);
2961 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2962 assert(cons != NULL);
2963 assert(SCIPconsIsTransformed(cons));
2964
2965 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2966 assert(conshdlrdata != NULL);
2967 consdata = SCIPconsGetData(cons);
2968 assert(consdata != NULL);
2969 assert(consdata->watchedvar1 == -1 || consdata->watchedvar1 != consdata->watchedvar2);
2970
2971 SCIPdebugMsg(scip, "deactivating information for bound disjunction constraint <%s>\n", SCIPconsGetName(cons));
2972 SCIPdebug(consdataPrint(scip, consdata, NULL, TRUE));
2973
2974 /* drop events on watched variables */
2975 if( consdata->watchedvar1 != -1 )
2976 {
2977 assert(consdata->filterpos1 != -1);
2978 SCIP_CALL( dropEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar1, consdata->filterpos1) );
2979 consdata->watchedvar1 = -1;
2980 }
2981 if( consdata->watchedvar2 != -1 )
2982 {
2983 assert(consdata->filterpos2 != -1);
2984 SCIP_CALL( dropEvents(scip, cons, consdata, conshdlrdata->eventhdlr, consdata->watchedvar2, consdata->filterpos2) );
2985 consdata->watchedvar2 = -1;
2986 }
2987
2988 return SCIP_OKAY;
2989 }
2990
2991
2992 /** constraint display method of constraint handler */
2993 static
SCIP_DECL_CONSPRINT(consPrintBounddisjunction)2994 SCIP_DECL_CONSPRINT(consPrintBounddisjunction)
2995 { /*lint --e{715}*/
2996 assert( scip != NULL );
2997 assert( conshdlr != NULL );
2998 assert( cons != NULL );
2999
3000 consdataPrint(scip, SCIPconsGetData(cons), file, FALSE);
3001
3002 return SCIP_OKAY;
3003 }
3004
3005 /** constraint copying method of constraint handler */
3006 static
SCIP_DECL_CONSCOPY(consCopyBounddisjunction)3007 SCIP_DECL_CONSCOPY(consCopyBounddisjunction)
3008 { /*lint --e{715}*/
3009 SCIP_VAR** sourcevars;
3010 SCIP_VAR** targetvars;
3011 SCIP_BOUNDTYPE* boundtypes;
3012 SCIP_Real* bounds;
3013 int nvars;
3014 int v;
3015
3016 assert(valid != NULL);
3017
3018 *valid = TRUE;
3019
3020 /* get source data */
3021 sourcevars = SCIPgetVarsBounddisjunction(sourcescip, sourcecons);
3022 nvars = SCIPgetNVarsBounddisjunction(sourcescip, sourcecons);
3023 boundtypes = SCIPgetBoundtypesBounddisjunction(sourcescip, sourcecons);
3024 bounds = SCIPgetBoundsBounddisjunction(sourcescip, sourcecons);
3025
3026 SCIP_CALL( SCIPallocBufferArray(scip, &targetvars, nvars) );
3027
3028 /* map source variables to active variables of the target SCIP */
3029 for( v = 0; v < nvars && *valid; ++v )
3030 {
3031 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[v], &targetvars[v], varmap, consmap, global, valid) );
3032 assert(!(*valid) || targetvars[v] != NULL);
3033 }
3034
3035 /* only create the target constraint, if all variables could be copied */
3036 if( *valid )
3037 {
3038 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name ? name : SCIPconsGetName(sourcecons), nvars, targetvars, boundtypes,
3039 bounds, initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3040 }
3041
3042 SCIPfreeBufferArray(scip, &targetvars);
3043
3044 return SCIP_OKAY;
3045 }
3046
3047 /** constraint parsing method of constraint handler */
3048 static
SCIP_DECL_CONSPARSE(consParseBounddisjunction)3049 SCIP_DECL_CONSPARSE(consParseBounddisjunction)
3050 { /*lint --e{715}*/
3051 SCIP_BOUNDTYPE* boundtypes;
3052 SCIP_Real* bounds;
3053 SCIP_VAR** vars;
3054 char* endptr;
3055 int varssize;
3056 int nvars;
3057
3058 assert( success != NULL );
3059 *success = TRUE;
3060
3061 SCIPdebugMsg(scip, "parse <%s> as bounddisjunction constraint\n", str);
3062
3063 /* skip white space */
3064 while( *str != '\0' && isspace((unsigned char)*str) )
3065 ++str;
3066
3067 /* check for string "bounddisjunction" */
3068 if( strncmp(str, "bounddisjunction(", 16) != 0 )
3069 {
3070 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "error during parsing: expected \"bounddisjunction(\" in <%s>.\n", str);
3071 *success = FALSE;
3072 return SCIP_OKAY;
3073 }
3074
3075 /* skip "bounddisjunction(" */
3076 str += 17;
3077
3078 varssize = 100;
3079 nvars = 0;
3080
3081 /* allocate buffer array for variables */
3082 SCIP_CALL( SCIPallocBufferArray(scip, &vars, varssize) );
3083 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, varssize) );
3084 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, varssize) );
3085
3086 /* parse string until ")" */
3087 while( *str != '\0' && *str != ')' )
3088 {
3089 SCIP_VAR* var;
3090
3091 /* parse variable name */
3092 SCIP_CALL( SCIPparseVarName(scip, str, &var, &endptr) );
3093 str = endptr;
3094
3095 if( var == NULL )
3096 {
3097 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Error while parsing variable.\n");
3098 *success = FALSE;
3099 goto TERMINATE;
3100 }
3101
3102 /* skip white space */
3103 while( *str != '\0' && isspace((unsigned char)*str) && *str != '>' && *str != '<' )
3104 ++str;
3105
3106 /* parse bound type */
3107 switch( *str )
3108 {
3109 case '<':
3110 boundtypes[nvars] = SCIP_BOUNDTYPE_UPPER;
3111 break;
3112 case '>':
3113 boundtypes[nvars] = SCIP_BOUNDTYPE_LOWER;
3114 break;
3115 default:
3116 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "variable with name <%s> does not exist\n", SCIPvarGetName(var));
3117 *success = FALSE;
3118 goto TERMINATE;
3119 }
3120
3121 ++str;
3122 if( *str != '=' )
3123 {
3124 SCIPdebugMsg(scip, "expected '=': %s\n", str);
3125 *success = FALSE;
3126 goto TERMINATE;
3127 }
3128
3129 /* skip '=' */
3130 ++str;
3131
3132 /* skip white space */
3133 while( *str != '\0' && isspace((unsigned char)*str) )
3134 ++str;
3135
3136 /* parse bound value */
3137 if( !SCIPstrToRealValue(str, &bounds[nvars], &endptr) )
3138 {
3139 SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Syntax error during parsing of the weight: %s\n", str);
3140 *success = FALSE;
3141 goto TERMINATE;
3142 }
3143
3144 /* skip white space */
3145 str = endptr;
3146 while( (*str != '\0' && isspace((unsigned char)*str)) || *str == ',' )
3147 ++str;
3148
3149 /* set variable */
3150 vars[nvars++] = var;
3151
3152 /* check if the size of the variable array was big enough */
3153 if( nvars > varssize )
3154 {
3155 /* reallocate memory */
3156 varssize *= 2;
3157 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, varssize) );
3158 SCIP_CALL( SCIPreallocBufferArray(scip, &boundtypes, varssize) );
3159 SCIP_CALL( SCIPreallocBufferArray(scip, &bounds, varssize) );
3160 }
3161 }
3162 /* ignore if the string ended without ")" */
3163
3164 /* add bounddisjunction */
3165 if( *success && nvars > 0 )
3166 {
3167 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name, nvars, vars, boundtypes, bounds,
3168 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3169 }
3170
3171 TERMINATE:
3172 /* free variable buffer */
3173 SCIPfreeBufferArray(scip, &bounds);
3174 SCIPfreeBufferArray(scip, &boundtypes);
3175 SCIPfreeBufferArray(scip, &vars);
3176
3177 return SCIP_OKAY;
3178 }
3179
3180 /** constraint method of constraint handler which returns the variables (if possible) */
3181 static
SCIP_DECL_CONSGETVARS(consGetVarsBounddisjunction)3182 SCIP_DECL_CONSGETVARS(consGetVarsBounddisjunction)
3183 { /*lint --e{715}*/
3184 SCIP_CONSDATA* consdata;
3185
3186 assert(cons != NULL);
3187
3188 consdata = SCIPconsGetData(cons);
3189 assert(consdata != NULL);
3190
3191 if( varssize < consdata->nvars )
3192 (*success) = FALSE;
3193 else
3194 {
3195 assert(vars != NULL);
3196
3197 BMScopyMemoryArray(vars, consdata->vars, consdata->nvars);
3198 (*success) = TRUE;
3199 }
3200
3201 return SCIP_OKAY;
3202 }
3203
3204 /** constraint method of constraint handler which returns the number of variables (if possible) */
3205 static
SCIP_DECL_CONSGETNVARS(consGetNVarsBounddisjunction)3206 SCIP_DECL_CONSGETNVARS(consGetNVarsBounddisjunction)
3207 { /*lint --e{715}*/
3208 SCIP_CONSDATA* consdata;
3209
3210 assert(cons != NULL);
3211
3212 consdata = SCIPconsGetData(cons);
3213 assert(consdata != NULL);
3214
3215 (*nvars) = consdata->nvars;
3216 (*success) = TRUE;
3217
3218 return SCIP_OKAY;
3219 }
3220
3221 /**@} */
3222
3223 /**@name Callback methods of event handler
3224 *
3225 * @{
3226 */
3227
3228 static
SCIP_DECL_EVENTEXEC(eventExecBounddisjunction)3229 SCIP_DECL_EVENTEXEC(eventExecBounddisjunction)
3230 { /*lint --e{715}*/
3231 assert(eventhdlr != NULL);
3232 assert(eventdata != NULL);
3233 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
3234 assert(event != NULL);
3235
3236 /*SCIPdebugMsg(scip, "exec method of event handler for bound disjunction constraints\n");*/
3237
3238 assert(SCIPconsGetData((SCIP_CONS*)eventdata) != NULL);
3239 assert(SCIPconsIsActive((SCIP_CONS*)eventdata) || SCIPconsIsUpdatedeactivate((SCIP_CONS*)eventdata));
3240
3241 if( (SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDRELAXED) != 0 )
3242 {
3243 SCIP_CALL( SCIPenableCons(scip, (SCIP_CONS*)eventdata) );
3244 }
3245 else
3246 assert((SCIPeventGetType(event) & SCIP_EVENTTYPE_BOUNDTIGHTENED) != 0);
3247
3248 SCIP_CALL( SCIPenableConsPropagation(scip, (SCIP_CONS*)eventdata) );
3249
3250 return SCIP_OKAY;
3251 }
3252
3253 /**@} */
3254
3255 /**@name Callback methods of conflict handler
3256 *
3257 * @{
3258 */
3259
3260 /** conflict handler data struct */
3261 struct SCIP_ConflicthdlrData
3262 {
3263 SCIP_Real continuousfrac; /**< maximal percantage of continuous variables within a conflict */
3264 };
3265
3266 /** conflict processing method of conflict handler (called when conflict was found) */
3267 static
SCIP_DECL_CONFLICTEXEC(conflictExecBounddisjunction)3268 SCIP_DECL_CONFLICTEXEC(conflictExecBounddisjunction)
3269 { /*lint --e{715}*/
3270 SCIP_VAR** vars;
3271 SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
3272 SCIP_BOUNDTYPE* boundtypes;
3273 SCIP_Real* bounds;
3274 SCIP_CONS* cons;
3275 char consname[SCIP_MAXSTRLEN];
3276 int nliterals;
3277 int ncontinuous;
3278 int i;
3279
3280 assert(conflicthdlr != NULL);
3281 assert(strcmp(SCIPconflicthdlrGetName(conflicthdlr), CONFLICTHDLR_NAME) == 0);
3282 assert(bdchginfos != NULL || nbdchginfos == 0);
3283 assert(result != NULL);
3284
3285 /* don't process already resolved conflicts */
3286 if( resolved )
3287 {
3288 *result = SCIP_DIDNOTRUN;
3289 return SCIP_OKAY;
3290 }
3291
3292 conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr);
3293 assert(conflicthdlrdata != NULL);
3294
3295 *result = SCIP_DIDNOTFIND;
3296 ncontinuous = 0;
3297
3298 /* create array of variables, boundtypes, and bound values in conflict constraint */
3299 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbdchginfos) );
3300 SCIP_CALL( SCIPallocBufferArray(scip, &boundtypes, nbdchginfos) );
3301 SCIP_CALL( SCIPallocBufferArray(scip, &bounds, nbdchginfos) );
3302
3303 nliterals = 0;
3304
3305 for( i = 0; i < nbdchginfos; ++i )
3306 {
3307 SCIP_VAR* var;
3308 SCIP_Real bound;
3309 SCIP_BOUNDTYPE boundtype;
3310 int j;
3311
3312 assert(bdchginfos != NULL);
3313
3314 var = SCIPbdchginfoGetVar(bdchginfos[i]);
3315 assert(var != NULL);
3316
3317 boundtype = SCIPboundtypeOpposite(SCIPbdchginfoGetBoundtype(bdchginfos[i]));
3318 bound = relaxedbds[i];
3319
3320 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
3321 if( SCIPvarIsIntegral(var) )
3322 bound += (boundtype == SCIP_BOUNDTYPE_LOWER ? +1.0 : -1.0);
3323
3324 /* check whether we have seen the variable before */
3325 for( j = nliterals-1; j >= 0; --j )
3326 {
3327 if( vars[j] != var )
3328 continue;
3329
3330 /* check whether both literals contribute with the same bound type */
3331 if( boundtypes[j] == boundtype )
3332 {
3333 /* check whether the lower bound can be relaxed */
3334 if( boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisLT(scip, bound, bounds[j]) )
3335 {
3336 SCIPdebugMsg(scip, "relax lower bound of variable <%s> from %g to %g in bounddisjunction conflict\n",
3337 SCIPvarGetName(var), bounds[j], bound);
3338 bounds[j] = bound;
3339 }
3340 /* check whether the upper bound can be relaxed */
3341 else if( boundtype == SCIP_BOUNDTYPE_UPPER && SCIPisGT(scip, bound, bounds[j]) )
3342 {
3343 SCIPdebugMsg(scip, "relax upper bound of variable <%s> from %g to %g in bounddisjunction conflict\n",
3344 SCIPvarGetName(var), bounds[j], bound);
3345 bounds[j] = bound;
3346 }
3347
3348 continue;
3349 }
3350 /* check whether the bounds are overlapping */
3351 else if( isOverlapping(scip, var, boundtype, bound, boundtypes[j], bounds[j]) )
3352 {
3353 /* the conflict is redundant -> discard the conflict constraint */
3354 SCIPdebugMsg(scip, "redundant bounddisjunction conflict due to overlapping\n");
3355 goto DISCARDCONFLICT;
3356 }
3357 }
3358
3359 vars[nliterals] = var;
3360 boundtypes[nliterals] = boundtype;
3361 bounds[nliterals] = bound;
3362
3363 /* check if the relaxed bound is really a relaxed bound */
3364 assert(SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER || SCIPisGE(scip, relaxedbds[i], SCIPbdchginfoGetNewbound(bdchginfos[i])));
3365 assert(SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_UPPER || SCIPisLE(scip, relaxedbds[i], SCIPbdchginfoGetNewbound(bdchginfos[i])));
3366
3367 /* for continuous variables, we can only use the relaxed version of the bounds negation: !(x <= u) -> x >= u */
3368 if( !SCIPvarIsIntegral(vars[nliterals]) )
3369 {
3370 if( (boundtypes[i] == SCIP_BOUNDTYPE_LOWER && SCIPisFeasEQ(scip, SCIPvarGetLbGlobal(var), bounds[nliterals]))
3371 || (boundtypes[i] == SCIP_BOUNDTYPE_UPPER && SCIPisFeasEQ(scip, SCIPvarGetUbGlobal(var), bounds[nliterals])) )
3372 {
3373 /* the literal is satisfied in global bounds (may happen due to weak "negation" of continuous variables)
3374 * -> discard the conflict constraint
3375 */
3376 SCIPdebugMsg(scip, "redundant bounddisjunction conflict due to globally fulfilled literal\n");
3377 goto DISCARDCONFLICT;
3378 }
3379 else
3380 ncontinuous++;
3381 }
3382
3383 nliterals++;
3384 }
3385
3386 /* create a constraint out of the conflict set */
3387 if( i == nbdchginfos && ncontinuous < conflicthdlrdata->continuousfrac * nbdchginfos + 0.5 )
3388 {
3389 (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cf%d_%" SCIP_LONGINT_FORMAT, SCIPgetNRuns(scip), SCIPgetNConflictConssApplied(scip));
3390 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, &cons, consname, nliterals, vars, boundtypes, bounds,
3391 FALSE, FALSE, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
3392
3393 /* add conflict to SCIP */
3394 SCIP_CALL( SCIPaddConflict(scip, node, cons, validnode, conftype, cutoffinvolved) );
3395 SCIPdebugMsg(scip, "added conflict\n");
3396 *result = SCIP_CONSADDED;
3397 }
3398
3399 DISCARDCONFLICT:
3400 /* free temporary memory */
3401 SCIPfreeBufferArray(scip, &bounds);
3402 SCIPfreeBufferArray(scip, &boundtypes);
3403 SCIPfreeBufferArray(scip, &vars);
3404
3405 return SCIP_OKAY;
3406 }
3407
3408 /** free method of conflict handler */
3409 static
SCIP_DECL_CONFLICTFREE(conflictFreeBounddisjunction)3410 SCIP_DECL_CONFLICTFREE(conflictFreeBounddisjunction)
3411 {
3412 SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
3413
3414 assert(conflicthdlr != NULL);
3415
3416 /* get conflict handler data */
3417 conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr);
3418 assert(conflicthdlrdata != NULL);
3419
3420 /* free conflict handler structure */
3421 SCIPfreeBlockMemory(scip, &conflicthdlrdata);
3422
3423 return SCIP_OKAY;
3424 }
3425
3426 /**@} */
3427
3428 /**@name Interface methods
3429 *
3430 * @{
3431 */
3432
3433 /** creates the handler for bound disjunction constraints and includes it in SCIP */
SCIPincludeConshdlrBounddisjunction(SCIP * scip)3434 SCIP_RETCODE SCIPincludeConshdlrBounddisjunction(
3435 SCIP* scip /**< SCIP data structure */
3436 )
3437 {
3438 SCIP_CONSHDLRDATA* conshdlrdata;
3439 SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
3440 SCIP_CONFLICTHDLR* conflicthdlr;
3441 SCIP_CONSHDLR* conshdlr;
3442 SCIP_EVENTHDLR* eventhdlr;
3443
3444 /* create event handler for events on watched variables */
3445 SCIP_CALL( SCIPincludeEventhdlrBasic(scip, &eventhdlr, EVENTHDLR_NAME, EVENTHDLR_DESC,
3446 eventExecBounddisjunction, NULL) );
3447
3448 /* allocate memory for conflict handler data */
3449 SCIP_CALL( SCIPallocBlockMemory(scip, &conflicthdlrdata) );
3450
3451 /* create conflict handler parameter */
3452 SCIP_CALL( SCIPaddRealParam(scip,
3453 "conflict/" CONSHDLR_NAME "/continuousfrac", "maximal percantage of continuous variables within a conflict",
3454 &conflicthdlrdata->continuousfrac, FALSE, DEFAULT_CONTINUOUSFRAC, 0.0, 1.0, NULL, NULL) );
3455
3456 /* create conflict handler for bound disjunction constraints */
3457 SCIP_CALL( SCIPincludeConflicthdlrBasic(scip, &conflicthdlr, CONFLICTHDLR_NAME, CONFLICTHDLR_DESC, CONFLICTHDLR_PRIORITY,
3458 conflictExecBounddisjunction, conflicthdlrdata) );
3459
3460 SCIP_CALL( SCIPsetConflicthdlrFree(scip, conflicthdlr, conflictFreeBounddisjunction) );
3461
3462 /* create constraint handler data */
3463 SCIP_CALL( conshdlrdataCreate(scip, &conshdlrdata, eventhdlr) );
3464
3465 /* include constraint handler */
3466 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
3467 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
3468 consEnfolpBounddisjunction, consEnfopsBounddisjunction, consCheckBounddisjunction, consLockBounddisjunction,
3469 conshdlrdata) );
3470
3471 assert(conshdlr != NULL);
3472
3473 /* set non-fundamental callbacks via specific setter functions */
3474 SCIP_CALL( SCIPsetConshdlrActive(scip, conshdlr, consActiveBounddisjunction) );
3475 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyBounddisjunction, consCopyBounddisjunction) );
3476 SCIP_CALL( SCIPsetConshdlrDeactive(scip, conshdlr, consDeactiveBounddisjunction) );
3477 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteBounddisjunction) );
3478 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreBounddisjunction) );
3479 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeBounddisjunction) );
3480 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsBounddisjunction) );
3481 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsBounddisjunction) );
3482 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseBounddisjunction) );
3483 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolBounddisjunction, CONSHDLR_MAXPREROUNDS,
3484 CONSHDLR_PRESOLTIMING) );
3485 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintBounddisjunction) );
3486 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropBounddisjunction, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
3487 CONSHDLR_PROP_TIMING) );
3488 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropBounddisjunction) );
3489 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransBounddisjunction) );
3490 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxBounddisjunction) );
3491
3492 /* register upgrade of quadratic complementarity constraints in cons_quadratic */
3493 if( SCIPfindConshdlr(scip, "quadratic") )
3494 {
3495 SCIP_CALL( SCIPincludeQuadconsUpgrade(scip, upgradeConsQuadratic, QUADCONSUPGD_PRIORITY, TRUE, CONSHDLR_NAME) );
3496 }
3497
3498 return SCIP_OKAY;
3499 }
3500
3501
3502 /** creates and captures a bound disjunction constraint
3503 *
3504 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3505 */
SCIPcreateConsBounddisjunction(SCIP * scip,SCIP_CONS ** cons,const char * name,int nvars,SCIP_VAR ** vars,SCIP_BOUNDTYPE * boundtypes,SCIP_Real * bounds,SCIP_Bool initial,SCIP_Bool separate,SCIP_Bool enforce,SCIP_Bool check,SCIP_Bool propagate,SCIP_Bool local,SCIP_Bool modifiable,SCIP_Bool dynamic,SCIP_Bool removable,SCIP_Bool stickingatnode)3506 SCIP_RETCODE SCIPcreateConsBounddisjunction(
3507 SCIP* scip, /**< SCIP data structure */
3508 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3509 const char* name, /**< name of constraint */
3510 int nvars, /**< number of variables in the constraint */
3511 SCIP_VAR** vars, /**< variables of the literals in the constraint */
3512 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3513 SCIP_Real* bounds, /**< bounds of the literals */
3514 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3515 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3516 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3517 * Usually set to TRUE. */
3518 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3519 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3520 SCIP_Bool check, /**< should the constraint be checked for feasibility?
3521 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3522 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3523 * Usually set to TRUE. */
3524 SCIP_Bool local, /**< is constraint only valid locally?
3525 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3526 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3527 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3528 * adds coefficients to this constraint. */
3529 SCIP_Bool dynamic, /**< is constraint subject to aging?
3530 * Usually set to FALSE. Set to TRUE for own cuts which
3531 * are separated as constraints. */
3532 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3533 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3534 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3535 * if it may be moved to a more global node?
3536 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3537 )
3538 {
3539 SCIP_CONSHDLR* conshdlr;
3540 SCIP_CONSDATA* consdata;
3541
3542 assert(scip != NULL);
3543
3544 /* find the bounddisjunction constraint handler */
3545 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3546 if( conshdlr == NULL )
3547 {
3548 SCIPerrorMessage("bound disjunction constraint handler not found\n");
3549 return SCIP_PLUGINNOTFOUND;
3550 }
3551
3552 #ifndef NDEBUG
3553 {
3554 int v1;
3555 /* ensure that the given data neither contains overlapping nor redundant literals */
3556 for( v1 = 0; v1 < nvars; v1++ )
3557 {
3558 int v2;
3559 for( v2 = v1+1; v2 < nvars; v2++ )
3560 {
3561 assert(vars[v1] != vars[v2] || (SCIPboundtypeOpposite(boundtypes[v1]) == boundtypes[v2]
3562 && !isOverlapping(scip, vars[v1], boundtypes[v1], bounds[v1], boundtypes[v2], bounds[v2])));
3563 }
3564 }
3565 }
3566 #endif
3567
3568 /* create the constraint specific data */
3569 SCIP_CALL( consdataCreate(scip, &consdata, nvars, vars, boundtypes, bounds) );
3570
3571 /* create constraint */
3572 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3573 local, modifiable, dynamic, removable, stickingatnode) );
3574
3575 return SCIP_OKAY;
3576 }
3577
3578 /** creates and captures a bound disjunction constraint
3579 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
3580 * method SCIPcreateConsBounddisjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
3581 *
3582 * @see SCIPcreateConsBounddisjunction() for information about the basic constraint flag configuration
3583 *
3584 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3585 */
SCIPcreateConsBasicBounddisjunction(SCIP * scip,SCIP_CONS ** cons,const char * name,int nvars,SCIP_VAR ** vars,SCIP_BOUNDTYPE * boundtypes,SCIP_Real * bounds)3586 SCIP_RETCODE SCIPcreateConsBasicBounddisjunction(
3587 SCIP* scip, /**< SCIP data structure */
3588 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3589 const char* name, /**< name of constraint */
3590 int nvars, /**< number of variables in the constraint */
3591 SCIP_VAR** vars, /**< variables of the literals in the constraint */
3592 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3593 SCIP_Real* bounds /**< bounds of the literals */
3594 )
3595 {
3596 assert(scip != NULL);
3597
3598 SCIP_CALL( SCIPcreateConsBounddisjunction(scip, cons, name, nvars, vars, boundtypes, bounds,
3599 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3600
3601 return SCIP_OKAY;
3602 }
3603
3604 /** creates and captures a bound disjunction constraint with possibly redundant literals
3605 *
3606 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3607 */
SCIPcreateConsBounddisjunctionRedundant(SCIP * scip,SCIP_CONS ** cons,const char * name,int nvars,SCIP_VAR ** vars,SCIP_BOUNDTYPE * boundtypes,SCIP_Real * bounds,SCIP_Bool initial,SCIP_Bool separate,SCIP_Bool enforce,SCIP_Bool check,SCIP_Bool propagate,SCIP_Bool local,SCIP_Bool modifiable,SCIP_Bool dynamic,SCIP_Bool removable,SCIP_Bool stickingatnode)3608 SCIP_RETCODE SCIPcreateConsBounddisjunctionRedundant(
3609 SCIP* scip, /**< SCIP data structure */
3610 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3611 const char* name, /**< name of constraint */
3612 int nvars, /**< number of variables in the constraint */
3613 SCIP_VAR** vars, /**< variables of the literals in the constraint */
3614 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3615 SCIP_Real* bounds, /**< bounds of the literals */
3616 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3617 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3618 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3619 * Usually set to TRUE. */
3620 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3621 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3622 SCIP_Bool check, /**< should the constraint be checked for feasibility?
3623 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3624 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3625 * Usually set to TRUE. */
3626 SCIP_Bool local, /**< is constraint only valid locally?
3627 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3628 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3629 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3630 * adds coefficients to this constraint. */
3631 SCIP_Bool dynamic, /**< is constraint subject to aging?
3632 * Usually set to FALSE. Set to TRUE for own cuts which
3633 * are separated as constraints. */
3634 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3635 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3636 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3637 * if it may be moved to a more global node?
3638 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3639 )
3640 {
3641 SCIP_CONSHDLR* conshdlr;
3642 SCIP_CONSDATA* consdata;
3643
3644 assert(scip != NULL);
3645
3646 /* find the bounddisjunction constraint handler */
3647 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3648 if( conshdlr == NULL )
3649 {
3650 SCIPerrorMessage("bound disjunction constraint handler not found\n");
3651 return SCIP_PLUGINNOTFOUND;
3652 }
3653
3654 /* create the constraint specific data */
3655 SCIP_CALL( consdataCreateRedundant(scip, &consdata, nvars, vars, boundtypes, bounds) );
3656
3657 /* create constraint */
3658 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3659 local, modifiable, dynamic, removable, stickingatnode) );
3660
3661 return SCIP_OKAY;
3662 }
3663
3664 /** creates and captures a bound disjunction constraint with possibly redundant literals
3665 * in its most basic version, i. e., all constraint flags are set to their basic value as explained for the
3666 * method SCIPcreateConsBounddisjunction(); all flags can be set via SCIPsetConsFLAGNAME-methods in scip.h
3667 *
3668 * @see SCIPcreateConsBounddisjunction() for information about the basic constraint flag configuration
3669 *
3670 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3671 */
SCIPcreateConsBasicBounddisjunctionRedundant(SCIP * scip,SCIP_CONS ** cons,const char * name,int nvars,SCIP_VAR ** vars,SCIP_BOUNDTYPE * boundtypes,SCIP_Real * bounds)3672 SCIP_RETCODE SCIPcreateConsBasicBounddisjunctionRedundant(
3673 SCIP* scip, /**< SCIP data structure */
3674 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3675 const char* name, /**< name of constraint */
3676 int nvars, /**< number of variables in the constraint */
3677 SCIP_VAR** vars, /**< variables of the literals in the constraint */
3678 SCIP_BOUNDTYPE* boundtypes, /**< types of bounds of the literals (lower or upper bounds) */
3679 SCIP_Real* bounds /**< bounds of the literals */
3680 )
3681 {
3682 assert(scip != NULL);
3683
3684 SCIP_CALL( SCIPcreateConsBounddisjunctionRedundant(scip, cons, name, nvars, vars, boundtypes, bounds,
3685 TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3686
3687 return SCIP_OKAY;
3688 }
3689
3690 /** gets number of variables in bound disjunction constraint */ /*lint -e{715}*/
SCIPgetNVarsBounddisjunction(SCIP * scip,SCIP_CONS * cons)3691 int SCIPgetNVarsBounddisjunction(
3692 SCIP* scip, /**< SCIP data structure */
3693 SCIP_CONS* cons /**< constraint data */
3694 )
3695 {
3696 SCIP_CONSDATA* consdata;
3697
3698 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3699 {
3700 SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3701 SCIPABORT();
3702 return 0; /*lint !e527*/
3703 }
3704
3705 consdata = SCIPconsGetData(cons);
3706 assert(consdata != NULL);
3707
3708 return consdata->nvars;
3709 }
3710
3711 /** gets array of variables in bound disjunction constraint */ /*lint -e{715}*/
SCIPgetVarsBounddisjunction(SCIP * scip,SCIP_CONS * cons)3712 SCIP_VAR** SCIPgetVarsBounddisjunction(
3713 SCIP* scip, /**< SCIP data structure */
3714 SCIP_CONS* cons /**< constraint data */
3715 )
3716 {
3717 SCIP_CONSDATA* consdata;
3718
3719 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3720 {
3721 SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3722 SCIPABORT();
3723 return NULL; /*lint !e527*/
3724 }
3725
3726 consdata = SCIPconsGetData(cons);
3727 assert(consdata != NULL);
3728
3729 return consdata->vars;
3730 }
3731
3732 /** gets array of bound types in bound disjunction constraint */ /*lint -e{715}*/
SCIPgetBoundtypesBounddisjunction(SCIP * scip,SCIP_CONS * cons)3733 SCIP_BOUNDTYPE* SCIPgetBoundtypesBounddisjunction(
3734 SCIP* scip, /**< SCIP data structure */
3735 SCIP_CONS* cons /**< constraint data */
3736 )
3737 {
3738 SCIP_CONSDATA* consdata;
3739
3740 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3741 {
3742 SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3743 SCIPABORT();
3744 return NULL; /*lint !e527*/
3745 }
3746
3747 consdata = SCIPconsGetData(cons);
3748 assert(consdata != NULL);
3749
3750 return consdata->boundtypes;
3751 }
3752
3753 /** gets array of bounds in bound disjunction constraint */ /*lint -e{715}*/
SCIPgetBoundsBounddisjunction(SCIP * scip,SCIP_CONS * cons)3754 SCIP_Real* SCIPgetBoundsBounddisjunction(
3755 SCIP* scip, /**< SCIP data structure */
3756 SCIP_CONS* cons /**< constraint data */
3757 )
3758 {
3759 SCIP_CONSDATA* consdata;
3760
3761 if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), CONSHDLR_NAME) != 0 )
3762 {
3763 SCIPerrorMessage("constraint is not a bound disjunction constraint\n");
3764 SCIPABORT();
3765 return NULL; /*lint !e527*/
3766 }
3767
3768 consdata = SCIPconsGetData(cons);
3769 assert(consdata != NULL);
3770
3771 return consdata->bounds;
3772 }
3773
3774 /**@} */
3775