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 implics.c
17 * @ingroup OTHER_CFILES
18 * @brief methods for implications, variable bounds, and clique tables
19 * @author Tobias Achterberg
20 */
21
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23
24 #include "scip/event.h"
25 #include "scip/implics.h"
26 #include "scip/misc.h"
27 #include "scip/pub_implics.h"
28 #include "scip/pub_message.h"
29 #include "scip/pub_misc.h"
30 #include "scip/pub_misc_sort.h"
31 #include "scip/pub_var.h"
32 #include "scip/set.h"
33 #include "scip/struct_implics.h"
34 #include "scip/struct_set.h"
35 #include "scip/struct_stat.h"
36 #include "scip/var.h"
37
38
39
40 /*
41 * methods for variable bounds
42 */
43
44 /** creates a variable bounds data structure */
45 static
vboundsCreate(SCIP_VBOUNDS ** vbounds,BMS_BLKMEM * blkmem)46 SCIP_RETCODE vboundsCreate(
47 SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */
48 BMS_BLKMEM* blkmem /**< block memory */
49 )
50 {
51 assert(vbounds != NULL);
52
53 SCIP_ALLOC( BMSallocBlockMemory(blkmem, vbounds) );
54 (*vbounds)->vars = NULL;
55 (*vbounds)->coefs = NULL;
56 (*vbounds)->constants = NULL;
57 (*vbounds)->len = 0;
58 (*vbounds)->size = 0;
59
60 return SCIP_OKAY;
61 }
62
63 /** frees a variable bounds data structure */
SCIPvboundsFree(SCIP_VBOUNDS ** vbounds,BMS_BLKMEM * blkmem)64 void SCIPvboundsFree(
65 SCIP_VBOUNDS** vbounds, /**< pointer to store variable bounds data structure */
66 BMS_BLKMEM* blkmem /**< block memory */
67 )
68 {
69 assert(vbounds != NULL);
70
71 if( *vbounds != NULL )
72 {
73 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->vars, (*vbounds)->size);
74 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->coefs, (*vbounds)->size);
75 BMSfreeBlockMemoryArrayNull(blkmem, &(*vbounds)->constants, (*vbounds)->size);
76 BMSfreeBlockMemory(blkmem, vbounds);
77 }
78 }
79
80 /** ensures, that variable bounds arrays can store at least num entries */
81 static
vboundsEnsureSize(SCIP_VBOUNDS ** vbounds,BMS_BLKMEM * blkmem,SCIP_SET * set,int num)82 SCIP_RETCODE vboundsEnsureSize(
83 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
84 BMS_BLKMEM* blkmem, /**< block memory */
85 SCIP_SET* set, /**< global SCIP settings */
86 int num /**< minimum number of entries to store */
87 )
88 {
89 assert(vbounds != NULL);
90
91 /* create variable bounds data structure, if not yet existing */
92 if( *vbounds == NULL )
93 {
94 SCIP_CALL( vboundsCreate(vbounds, blkmem) );
95 }
96 assert(*vbounds != NULL);
97 assert((*vbounds)->len <= (*vbounds)->size);
98
99 if( num > (*vbounds)->size )
100 {
101 int newsize;
102
103 newsize = SCIPsetCalcMemGrowSize(set, num);
104 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->vars, (*vbounds)->size, newsize) );
105 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->coefs, (*vbounds)->size, newsize) );
106 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*vbounds)->constants, (*vbounds)->size, newsize) );
107 (*vbounds)->size = newsize;
108 }
109 assert(num <= (*vbounds)->size);
110
111 return SCIP_OKAY;
112 }
113
114 /** binary searches the insertion position of the given variable in the vbounds data structure */
115 static
vboundsSearchPos(SCIP_VBOUNDS * vbounds,SCIP_VAR * var,SCIP_Bool negativecoef,int * insertpos,SCIP_Bool * found)116 SCIP_RETCODE vboundsSearchPos(
117 SCIP_VBOUNDS* vbounds, /**< variable bounds data structure, or NULL */
118 SCIP_VAR* var, /**< variable to search in vbounds data structure */
119 SCIP_Bool negativecoef, /**< is coefficient b negative? */
120 int* insertpos, /**< pointer to store position where to insert new entry */
121 SCIP_Bool* found /**< pointer to store whether the same variable was found at the returned pos */
122 )
123 {
124 SCIP_Bool exists;
125 int pos;
126
127 assert(insertpos != NULL);
128 assert(found != NULL);
129
130 /* check for empty vbounds data */
131 if( vbounds == NULL )
132 {
133 *insertpos = 0;
134 *found = FALSE;
135 return SCIP_OKAY;
136 }
137 assert(vbounds->len >= 0);
138
139 /* binary search for the given variable */
140 exists = SCIPsortedvecFindPtr((void**)vbounds->vars, SCIPvarComp, var, vbounds->len, &pos);
141
142 if( exists )
143 {
144 /* we found the variable: check if the sign of the coefficient matches */
145 assert(var == vbounds->vars[pos]);
146 if( (vbounds->coefs[pos] < 0.0) == negativecoef )
147 {
148 /* the variable exists with the same sign at the current position */
149 *insertpos = pos;
150 *found = TRUE;
151 }
152 else if( negativecoef )
153 {
154 assert(vbounds->coefs[pos] > 0.0);
155 if( pos+1 < vbounds->len && vbounds->vars[pos+1] == var )
156 {
157 /* the variable exists with the desired sign at the next position */
158 assert(vbounds->coefs[pos+1] < 0.0);
159 *insertpos = pos+1;
160 *found = TRUE;
161 }
162 else
163 {
164 /* the negative coefficient should be inserted to the right of the positive one */
165 *insertpos = pos+1;
166 *found = FALSE;
167 }
168 }
169 else
170 {
171 assert(vbounds->coefs[pos] < 0.0);
172 if( pos-1 >= 0 && vbounds->vars[pos-1] == var )
173 {
174 /* the variable exists with the desired sign at the previous position */
175 assert(vbounds->coefs[pos-1] > 0.0);
176 *insertpos = pos-1;
177 *found = TRUE;
178 }
179 else
180 {
181 /* the positive coefficient should be inserted to the left of the negative one */
182 *insertpos = pos;
183 *found = FALSE;
184 }
185 }
186 }
187 else
188 {
189 *insertpos = pos;
190 *found = FALSE;
191 }
192
193 return SCIP_OKAY;
194 }
195
196 /** adds a variable bound to the variable bounds data structure */
SCIPvboundsAdd(SCIP_VBOUNDS ** vbounds,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_BOUNDTYPE vboundtype,SCIP_VAR * var,SCIP_Real coef,SCIP_Real constant,SCIP_Bool * added)197 SCIP_RETCODE SCIPvboundsAdd(
198 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
199 BMS_BLKMEM* blkmem, /**< block memory */
200 SCIP_SET* set, /**< global SCIP settings */
201 SCIP_BOUNDTYPE vboundtype, /**< type of variable bound (LOWER or UPPER) */
202 SCIP_VAR* var, /**< variable z in x <= b*z + d or x >= b*z + d */
203 SCIP_Real coef, /**< coefficient b in x <= b*z + d or x >= b*z + d */
204 SCIP_Real constant, /**< constant d in x <= b*z + d or x >= b*z + d */
205 SCIP_Bool* added /**< pointer to store whether the variable bound was added */
206 )
207 {
208 int insertpos;
209 SCIP_Bool found;
210
211 assert(vbounds != NULL);
212 assert(var != NULL);
213 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
214 assert(SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS);
215 assert(added != NULL);
216 assert(!SCIPsetIsZero(set, coef));
217
218 *added = FALSE;
219
220 /* identify insertion position of variable */
221 SCIP_CALL( vboundsSearchPos(*vbounds, var, (coef < 0.0), &insertpos, &found) );
222 if( found )
223 {
224 /* the same variable already exists in the vbounds data structure: use the better vbound */
225 assert(*vbounds != NULL);
226 assert(0 <= insertpos && insertpos < (*vbounds)->len);
227 assert((*vbounds)->vars[insertpos] == var);
228 assert(((*vbounds)->coefs[insertpos] < 0.0) == (coef < 0.0));
229
230 if( vboundtype == SCIP_BOUNDTYPE_UPPER )
231 {
232 if( constant + MIN(coef, 0.0) < (*vbounds)->constants[insertpos] + MIN((*vbounds)->coefs[insertpos], 0.0) )
233 {
234 (*vbounds)->coefs[insertpos] = coef;
235 (*vbounds)->constants[insertpos] = constant;
236 *added = TRUE;
237 }
238 }
239 else
240 {
241 if( constant + MAX(coef, 0.0) > (*vbounds)->constants[insertpos] + MAX((*vbounds)->coefs[insertpos], 0.0) )
242 {
243 (*vbounds)->coefs[insertpos] = coef;
244 (*vbounds)->constants[insertpos] = constant;
245 *added = TRUE;
246 }
247 }
248 }
249 else
250 {
251 int i;
252
253 /* the given variable does not yet exist in the vbounds */
254 SCIP_CALL( vboundsEnsureSize(vbounds, blkmem, set, *vbounds != NULL ? (*vbounds)->len+1 : 1) );
255 assert(*vbounds != NULL);
256 assert(0 <= insertpos && insertpos <= (*vbounds)->len);
257 assert(0 <= insertpos && insertpos < (*vbounds)->size);
258
259 /* insert variable at the correct position */
260 for( i = (*vbounds)->len; i > insertpos; --i )
261 {
262 assert(!SCIPsetIsZero(set, (*vbounds)->coefs[i-1]));
263 (*vbounds)->vars[i] = (*vbounds)->vars[i-1];
264 (*vbounds)->coefs[i] = (*vbounds)->coefs[i-1];
265 (*vbounds)->constants[i] = (*vbounds)->constants[i-1];
266 }
267 assert(!SCIPsetIsZero(set, coef));
268 (*vbounds)->vars[insertpos] = var;
269 (*vbounds)->coefs[insertpos] = coef;
270 (*vbounds)->constants[insertpos] = constant;
271 (*vbounds)->len++;
272 *added = TRUE;
273 }
274
275 return SCIP_OKAY;
276 }
277
278 /** removes from variable x a variable bound x >=/<= b*z + d with binary or integer z */
SCIPvboundsDel(SCIP_VBOUNDS ** vbounds,BMS_BLKMEM * blkmem,SCIP_VAR * vbdvar,SCIP_Bool negativecoef)279 SCIP_RETCODE SCIPvboundsDel(
280 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
281 BMS_BLKMEM* blkmem, /**< block memory */
282 SCIP_VAR* vbdvar, /**< variable z in x >=/<= b*z + d */
283 SCIP_Bool negativecoef /**< is coefficient b negative? */
284 )
285 {
286 SCIP_Bool found;
287 int pos;
288 int i;
289
290 assert(vbounds != NULL);
291 assert(*vbounds != NULL);
292
293 /* searches for variable z in variable bounds of x */
294 SCIP_CALL( vboundsSearchPos(*vbounds, vbdvar, negativecoef, &pos, &found) );
295 if( !found )
296 return SCIP_OKAY;
297
298 assert(0 <= pos && pos < (*vbounds)->len);
299 assert((*vbounds)->vars[pos] == vbdvar);
300 assert(((*vbounds)->coefs[pos] < 0.0) == negativecoef);
301
302 /* removes z from variable bounds of x */
303 for( i = pos; i < (*vbounds)->len - 1; i++ )
304 {
305 (*vbounds)->vars[i] = (*vbounds)->vars[i+1];
306 (*vbounds)->coefs[i] = (*vbounds)->coefs[i+1];
307 (*vbounds)->constants[i] = (*vbounds)->constants[i+1];
308 }
309 (*vbounds)->len--;
310
311 #ifndef NDEBUG
312 SCIP_CALL( vboundsSearchPos(*vbounds, vbdvar, negativecoef, &pos, &found) );
313 assert(!found);
314 #endif
315
316 /* free vbounds data structure, if it is empty */
317 if( (*vbounds)->len == 0 )
318 SCIPvboundsFree(vbounds, blkmem);
319
320 return SCIP_OKAY; /*lint !e438*/
321 }
322
323 /** reduces the number of variable bounds stored in the given variable bounds data structure */
SCIPvboundsShrink(SCIP_VBOUNDS ** vbounds,BMS_BLKMEM * blkmem,int newnvbds)324 void SCIPvboundsShrink(
325 SCIP_VBOUNDS** vbounds, /**< pointer to variable bounds data structure */
326 BMS_BLKMEM* blkmem, /**< block memory */
327 int newnvbds /**< new number of variable bounds */
328 )
329 {
330 assert(vbounds != NULL);
331 assert(*vbounds != NULL);
332 assert(newnvbds <= (*vbounds)->len);
333
334 if( newnvbds == 0 )
335 SCIPvboundsFree(vbounds, blkmem);
336 else
337 (*vbounds)->len = newnvbds;
338 }
339
340
341
342
343 /*
344 * methods for implications
345 */
346
347 #ifndef NDEBUG
348 /** comparator function for implication variables in the implication data structure */
349 static
SCIP_DECL_SORTPTRCOMP(compVars)350 SCIP_DECL_SORTPTRCOMP(compVars)
351 { /*lint --e{715}*/
352 SCIP_VAR* var1;
353 SCIP_VAR* var2;
354 int var1idx;
355 int var2idx;
356
357 var1 = (SCIP_VAR*)elem1;
358 var2 = (SCIP_VAR*)elem2;
359 assert(var1 != NULL);
360 assert(var2 != NULL);
361 var1idx = SCIPvarGetIndex(var1);
362 var2idx = SCIPvarGetIndex(var2);
363
364 if( var1idx < var2idx )
365 return -1;
366 else if( var1idx > var2idx )
367 return +1;
368 else
369 return 0;
370 }
371
372 /** performs integrity check on implications data structure */
373 static
checkImplics(SCIP_IMPLICS * implics)374 void checkImplics(
375 SCIP_IMPLICS* implics /**< implications data structure */
376 )
377 {
378 SCIP_Bool varfixing;
379
380 if( implics == NULL )
381 return;
382
383 varfixing = FALSE;
384 do
385 {
386 SCIP_VAR** vars;
387 SCIP_BOUNDTYPE* types;
388 int nimpls;
389 int i;
390
391 vars = implics->vars[varfixing];
392 types = implics->types[varfixing];
393 nimpls = implics->nimpls[varfixing];
394
395 assert(0 <= nimpls && nimpls <= implics->size[varfixing]);
396 for( i = 1; i < nimpls; ++i )
397 {
398 int cmp;
399
400 cmp = compVars(vars[i-1], vars[i]);
401 assert(cmp <= 0);
402 assert((cmp == 0) == (vars[i-1] == vars[i]));
403 assert(cmp < 0 || (types[i-1] == SCIP_BOUNDTYPE_LOWER && types[i] == SCIP_BOUNDTYPE_UPPER));
404 }
405
406 varfixing = !varfixing;
407 }
408 while( varfixing == TRUE );
409 }
410 #else
411 #define checkImplics(implics) /**/
412 #endif
413
414 /** creates an implications data structure */
415 static
implicsCreate(SCIP_IMPLICS ** implics,BMS_BLKMEM * blkmem)416 SCIP_RETCODE implicsCreate(
417 SCIP_IMPLICS** implics, /**< pointer to store implications data structure */
418 BMS_BLKMEM* blkmem /**< block memory */
419 )
420 {
421 assert(implics != NULL);
422
423 SCIP_ALLOC( BMSallocBlockMemory(blkmem, implics) );
424
425 (*implics)->vars[0] = NULL;
426 (*implics)->types[0] = NULL;
427 (*implics)->bounds[0] = NULL;
428 (*implics)->ids[0] = NULL;
429 (*implics)->size[0] = 0;
430 (*implics)->nimpls[0] = 0;
431 (*implics)->vars[1] = NULL;
432 (*implics)->types[1] = NULL;
433 (*implics)->bounds[1] = NULL;
434 (*implics)->ids[1] = NULL;
435 (*implics)->size[1] = 0;
436 (*implics)->nimpls[1] = 0;
437
438 return SCIP_OKAY;
439 }
440
441 /** frees an implications data structure */
SCIPimplicsFree(SCIP_IMPLICS ** implics,BMS_BLKMEM * blkmem)442 void SCIPimplicsFree(
443 SCIP_IMPLICS** implics, /**< pointer of implications data structure to free */
444 BMS_BLKMEM* blkmem /**< block memory */
445 )
446 {
447 assert(implics != NULL);
448
449 if( *implics != NULL )
450 {
451 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->vars[0], (*implics)->size[0]);
452 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->types[0], (*implics)->size[0]);
453 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->bounds[0], (*implics)->size[0]);
454 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->ids[0], (*implics)->size[0]);
455 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->vars[1], (*implics)->size[1]);
456 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->types[1], (*implics)->size[1]);
457 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->bounds[1], (*implics)->size[1]);
458 BMSfreeBlockMemoryArrayNull(blkmem, &(*implics)->ids[1], (*implics)->size[1]);
459 BMSfreeBlockMemory(blkmem, implics);
460 }
461 }
462
463 /** ensures, that arrays for x == 0 or x == 1 in implications data structure can store at least num entries */
464 static
implicsEnsureSize(SCIP_IMPLICS ** implics,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_Bool varfixing,int num)465 SCIP_RETCODE implicsEnsureSize(
466 SCIP_IMPLICS** implics, /**< pointer to implications data structure */
467 BMS_BLKMEM* blkmem, /**< block memory */
468 SCIP_SET* set, /**< global SCIP settings */
469 SCIP_Bool varfixing, /**< FALSE if size of arrays for x == 0 has to be ensured, TRUE for x == 1 */
470 int num /**< minimum number of entries to store */
471 )
472 {
473 assert(implics != NULL);
474
475 /* create implications data structure, if not yet existing */
476 if( *implics == NULL )
477 {
478 SCIP_CALL( implicsCreate(implics, blkmem) );
479 }
480 assert(*implics != NULL);
481 assert((*implics)->nimpls[varfixing] <= (*implics)->size[varfixing]);
482
483 if( num > (*implics)->size[varfixing] )
484 {
485 int newsize;
486
487 newsize = SCIPsetCalcMemGrowSize(set, num);
488 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->vars[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
489 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->types[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
490 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->bounds[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
491 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &(*implics)->ids[varfixing], (*implics)->size[varfixing], newsize) ); /*lint !e866*/
492 (*implics)->size[varfixing] = newsize;
493 }
494 assert(num <= (*implics)->size[varfixing]);
495
496 return SCIP_OKAY;
497 }
498
499 /** gets the positions of the implications y >= l and y <= u in the implications data structure;
500 * if no lower or upper bound implication for y was found, -1 is returned
501 */
502 static
implicsSearchVar(SCIP_IMPLICS * implics,SCIP_Bool varfixing,SCIP_VAR * implvar,int * poslower,int * posupper,int * posadd)503 void implicsSearchVar(
504 SCIP_IMPLICS* implics, /**< implications data structure */
505 SCIP_Bool varfixing, /**< FALSE if y is searched in implications for x == 0, TRUE for x == 1 */
506 SCIP_VAR* implvar, /**< variable y to search for */
507 int* poslower, /**< pointer to store position of y_lower (-1 if not found) */
508 int* posupper, /**< pointer to store position of y_upper (-1 if not found) */
509 int* posadd /**< pointer to store position of first y entry, or where a new y entry
510 * should be placed */
511 )
512 {
513 SCIP_Bool found;
514 int right;
515 int pos;
516
517 assert(implics != NULL);
518 assert(poslower != NULL);
519 assert(posupper != NULL);
520 assert(posadd != NULL);
521
522 if( implics->nimpls[varfixing] == 0 )
523 {
524 /* there are no implications with non-binary variable y */
525 *posadd = 0;
526 *poslower = -1;
527 *posupper = -1;
528 return;
529 }
530 right = implics->nimpls[varfixing] - 1;
531 assert(0 <= right);
532
533 /* search for the position in the sorted array (via binary search) */
534 found = SCIPsortedvecFindPtr((void**)(&(implics->vars[varfixing][0])), SCIPvarComp, (void*)implvar, right + 1, &pos);
535
536 if( !found )
537 {
538 /* y was not found */
539 assert(pos >= right || compVars((void*)implics->vars[varfixing][pos], (void*)implvar) > 0);
540 assert(pos == 0 || compVars((void*)implics->vars[varfixing][pos-1], (void*)implvar) < 0);
541 *poslower = -1;
542 *posupper = -1;
543 *posadd = pos;
544 }
545 else
546 {
547 /* y was found */
548 assert(implvar == implics->vars[varfixing][pos]);
549
550 /* set poslower and posupper */
551 if( implics->types[varfixing][pos] == SCIP_BOUNDTYPE_LOWER )
552 {
553 /* y was found as y_lower (on position middle) */
554 *poslower = pos;
555 if( pos + 1 < implics->nimpls[varfixing] && implics->vars[varfixing][pos+1] == implvar )
556 {
557 assert(implics->types[varfixing][pos+1] == SCIP_BOUNDTYPE_UPPER);
558 *posupper = pos + 1;
559 }
560 else
561 *posupper = -1;
562 *posadd = pos;
563 }
564 else
565 {
566 /* y was found as y_upper (on position pos) */
567 *posupper = pos;
568 if( pos - 1 >= 0 && implics->vars[varfixing][pos-1] == implvar )
569 {
570 assert(implics->types[varfixing][pos-1] == SCIP_BOUNDTYPE_LOWER);
571 *poslower = pos - 1;
572 *posadd = pos - 1;
573 }
574 else
575 {
576 *poslower = -1;
577 *posadd = pos;
578 }
579 }
580 }
581 }
582
583 /** returns whether variable y is already contained in implications for x == 0 or x == 1 with the given impltype
584 * y can be contained in structure with y >= b (y_lower) and y <= b (y_upper)
585 */
586 static
implicsSearchImplic(SCIP_IMPLICS * implics,SCIP_Bool varfixing,SCIP_VAR * implvar,SCIP_BOUNDTYPE impltype,int * poslower,int * posupper,int * posadd)587 SCIP_Bool implicsSearchImplic(
588 SCIP_IMPLICS* implics, /**< implications data structure */
589 SCIP_Bool varfixing, /**< FALSE if y is searched in implications for x == 0, TRUE for x == 1 */
590 SCIP_VAR* implvar, /**< variable y to search for */
591 SCIP_BOUNDTYPE impltype, /**< type of implication y <=/>= b to search for */
592 int* poslower, /**< pointer to store position of y_lower (inf if not found) */
593 int* posupper, /**< pointer to store position of y_upper (inf if not found) */
594 int* posadd /**< pointer to store correct position (with respect to impltype) to add y */
595 )
596 {
597 assert(implics != NULL);
598 assert(poslower != NULL);
599 assert(posupper != NULL);
600 assert(posadd != NULL);
601
602 implicsSearchVar(implics, varfixing, implvar, poslower, posupper, posadd);
603 assert(*poslower == -1 || *posupper == -1 || *posupper == (*poslower)+1);
604 assert(*poslower == -1 || *posadd == *poslower);
605 assert(*poslower >= 0 || *posupper == -1 || *posadd == *posupper);
606 assert(0 <= *posadd && *posadd <= implics->nimpls[varfixing]);
607
608 if( impltype == SCIP_BOUNDTYPE_LOWER )
609 return (*poslower >= 0);
610 else
611 {
612 if( *poslower >= 0 )
613 {
614 assert(*posadd == *poslower);
615 (*posadd)++;
616 }
617 return (*posupper >= 0);
618 }
619 }
620
621 /** adds an implication x == 0/1 -> y <= b or y >= b to the implications data structure;
622 * the implication must be non-redundant
623 */
SCIPimplicsAdd(SCIP_IMPLICS ** implics,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_Bool varfixing,SCIP_VAR * implvar,SCIP_BOUNDTYPE impltype,SCIP_Real implbound,SCIP_Bool isshortcut,SCIP_Bool * conflict,SCIP_Bool * added)624 SCIP_RETCODE SCIPimplicsAdd(
625 SCIP_IMPLICS** implics, /**< pointer to implications data structure */
626 BMS_BLKMEM* blkmem, /**< block memory */
627 SCIP_SET* set, /**< global SCIP settings */
628 SCIP_STAT* stat, /**< problem statistics */
629 SCIP_Bool varfixing, /**< FALSE if implication for x == 0 has to be added, TRUE for x == 1 */
630 SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
631 SCIP_BOUNDTYPE impltype, /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
632 SCIP_Real implbound, /**< bound b in implication y <= b or y >= b */
633 SCIP_Bool isshortcut, /**< is the implication a shortcut, i.e., added as part of the transitive closure of another implication? */
634 SCIP_Bool* conflict, /**< pointer to store whether implication causes a conflict for variable x */
635 SCIP_Bool* added /**< pointer to store whether the implication was added */
636 )
637 {
638 int poslower;
639 int posupper;
640 int posadd;
641 SCIP_Bool found;
642 #ifndef NDEBUG
643 int k;
644 #endif
645
646 assert(implics != NULL);
647 assert(*implics == NULL || 0 <= (*implics)->nimpls[varfixing]);
648 assert(stat != NULL);
649 assert(SCIPvarIsActive(implvar));
650 assert(SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(implvar) == SCIP_VARSTATUS_LOOSE);
651 assert((impltype == SCIP_BOUNDTYPE_LOWER && SCIPsetIsFeasGT(set, implbound, SCIPvarGetLbGlobal(implvar)))
652 || (impltype == SCIP_BOUNDTYPE_UPPER && SCIPsetIsFeasLT(set, implbound, SCIPvarGetUbGlobal(implvar))));
653 assert(conflict != NULL);
654 assert(added != NULL);
655
656 SCIPsetDebugMsg(set, "adding implication to implics %p [%u]: <%s> %s %g\n",
657 (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=", implbound);
658
659 checkImplics(*implics);
660
661 *conflict = FALSE;
662 *added = FALSE;
663
664 /* check if variable is already contained in implications data structure */
665 if( *implics != NULL )
666 {
667 found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
668 assert(-1 <= poslower && poslower < (*implics)->nimpls[varfixing]);
669 assert(-1 <= posupper && posupper < (*implics)->nimpls[varfixing]);
670 assert(0 <= posadd && posadd <= (*implics)->nimpls[varfixing]);
671 assert(poslower == -1 || (*implics)->types[varfixing][poslower] == SCIP_BOUNDTYPE_LOWER);
672 assert(posupper == -1 || (*implics)->types[varfixing][posupper] == SCIP_BOUNDTYPE_UPPER);
673 }
674 else
675 {
676 found = FALSE;
677 poslower = -1;
678 posupper = -1;
679 posadd = 0;
680 }
681
682 if( impltype == SCIP_BOUNDTYPE_LOWER )
683 {
684 assert(found == (poslower >= 0));
685
686 /* check if y >= b is redundant */
687 if( poslower >= 0 && SCIPsetIsFeasLE(set, implbound, (*implics)->bounds[varfixing][poslower]) )
688 {
689 SCIPsetDebugMsg(set, " -> implication is redundant to <%s> >= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]);
690 return SCIP_OKAY;
691 }
692
693 /* check if y >= b causes conflict for x (i.e. y <= a (with a < b) is also valid) */
694 if( posupper >= 0 && SCIPsetIsFeasGT(set, implbound, (*implics)->bounds[varfixing][posupper]) )
695 {
696 SCIPsetDebugMsg(set, " -> implication is conflicting to <%s> <= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]);
697 *conflict = TRUE;
698 return SCIP_OKAY;
699 }
700
701 *added = TRUE;
702
703 /* check if entry of the same type already exists */
704 if( found )
705 {
706 assert(poslower >= 0);
707 assert(posadd == poslower);
708
709 /* add y >= b by changing old entry on poslower */
710 assert((*implics)->vars[varfixing][poslower] == implvar);
711 assert(SCIPsetIsFeasGT(set, implbound, (*implics)->bounds[varfixing][poslower]));
712 (*implics)->bounds[varfixing][poslower] = implbound;
713 }
714 else
715 {
716 assert(poslower == -1);
717
718 /* add y >= b by creating a new entry on posadd */
719 SCIP_CALL( implicsEnsureSize(implics, blkmem, set, varfixing,
720 *implics != NULL ? (*implics)->nimpls[varfixing]+1 : 1) );
721 assert(*implics != NULL);
722
723 if( (*implics)->nimpls[varfixing] - posadd > 0 )
724 {
725 int amount = ((*implics)->nimpls[varfixing] - posadd);
726
727 #ifndef NDEBUG
728 for( k = (*implics)->nimpls[varfixing]; k > posadd; k-- )
729 {
730 assert(compVars((void*)(*implics)->vars[varfixing][k-1], (void*)implvar) >= 0);
731 }
732 #endif
733 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/
734 BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/
735 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/
736 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/
737 }
738
739 (*implics)->vars[varfixing][posadd] = implvar;
740 (*implics)->types[varfixing][posadd] = impltype;
741 (*implics)->bounds[varfixing][posadd] = implbound;
742 (*implics)->ids[varfixing][posadd] = (isshortcut ? -stat->nimplications : stat->nimplications);
743 (*implics)->nimpls[varfixing]++;
744 #ifndef NDEBUG
745 for( k = posadd-1; k >= 0; k-- )
746 assert(compVars((void*)(*implics)->vars[varfixing][k], (void*)implvar) <= 0);
747 #endif
748 stat->nimplications++;
749 }
750 }
751 else
752 {
753 assert(found == (posupper >= 0));
754
755 /* check if y <= b is redundant */
756 if( posupper >= 0 && SCIPsetIsFeasGE(set, implbound, (*implics)->bounds[varfixing][posupper]) )
757 {
758 SCIPsetDebugMsg(set, " -> implication is redundant to <%s> <= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][posupper]);
759 return SCIP_OKAY;
760 }
761
762 /* check if y <= b causes conflict for x (i.e. y >= a (with a > b) is also valid) */
763 if( poslower >= 0 && SCIPsetIsFeasLT(set, implbound, (*implics)->bounds[varfixing][poslower]) )
764 {
765 SCIPsetDebugMsg(set, " -> implication is conflicting to <%s> >= %g\n", SCIPvarGetName(implvar), (*implics)->bounds[varfixing][poslower]);
766 *conflict = TRUE;
767 return SCIP_OKAY;
768 }
769
770 *added = TRUE;
771
772 /* check if entry of the same type already exists */
773 if( found )
774 {
775 assert(posupper >= 0);
776 assert(posadd == posupper);
777
778 /* add y <= b by changing old entry on posupper */
779 assert((*implics)->vars[varfixing][posupper] == implvar);
780 assert(SCIPsetIsFeasLT(set, implbound,(*implics)->bounds[varfixing][posupper]));
781 (*implics)->bounds[varfixing][posupper] = implbound;
782 }
783 else
784 {
785 /* add y <= b by creating a new entry on posadd */
786 assert(posupper == -1);
787
788 SCIP_CALL( implicsEnsureSize(implics, blkmem, set, varfixing,
789 *implics != NULL ? (*implics)->nimpls[varfixing]+1 : 1) );
790 assert(*implics != NULL);
791
792 if( (*implics)->nimpls[varfixing] - posadd > 0 )
793 {
794 int amount = ((*implics)->nimpls[varfixing] - posadd);
795
796 #ifndef NDEBUG
797 for( k = (*implics)->nimpls[varfixing]; k > posadd; k-- )
798 {
799 assert(compVars((void*)(*implics)->vars[varfixing][k-1], (void*)implvar) >= 0);
800 }
801 #endif
802 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd+1]), &((*implics)->types[varfixing][posadd]), amount); /*lint !e866*/
803 BMSmoveMemoryArray(&((*implics)->ids[varfixing][posadd+1]), &((*implics)->ids[varfixing][posadd]), amount); /*lint !e866*/
804 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd+1]), &((*implics)->vars[varfixing][posadd]), amount); /*lint !e866*/
805 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd+1]), &((*implics)->bounds[varfixing][posadd]), amount); /*lint !e866*/
806 }
807
808 (*implics)->vars[varfixing][posadd] = implvar;
809 (*implics)->types[varfixing][posadd] = impltype;
810 (*implics)->bounds[varfixing][posadd] = implbound;
811 (*implics)->ids[varfixing][posadd] = (isshortcut ? -stat->nimplications : stat->nimplications);
812 (*implics)->nimpls[varfixing]++;
813 #ifndef NDEBUG
814 for( k = posadd-1; k >= 0; k-- )
815 assert(compVars((void*)(*implics)->vars[varfixing][k], (void*)implvar) <= 0);
816 #endif
817 stat->nimplications++;
818 }
819 }
820
821 checkImplics(*implics);
822
823 return SCIP_OKAY;
824 }
825
826 /** removes the implication x <= 0 or x >= 1 ==> y <= b or y >= b from the implications data structure */
SCIPimplicsDel(SCIP_IMPLICS ** implics,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_Bool varfixing,SCIP_VAR * implvar,SCIP_BOUNDTYPE impltype)827 SCIP_RETCODE SCIPimplicsDel(
828 SCIP_IMPLICS** implics, /**< pointer to implications data structure */
829 BMS_BLKMEM* blkmem, /**< block memory */
830 SCIP_SET* set, /**< global SCIP settings */
831 SCIP_Bool varfixing, /**< FALSE if y should be removed from implications for x <= 0, TRUE for x >= 1 */
832 SCIP_VAR* implvar, /**< variable y in implication y <= b or y >= b */
833 SCIP_BOUNDTYPE impltype /**< type of implication y <= b (SCIP_BOUNDTYPE_UPPER) or y >= b (SCIP_BOUNDTYPE_LOWER) */
834 )
835 { /*lint --e{715}*/
836 int poslower;
837 int posupper;
838 int posadd;
839 SCIP_Bool found;
840
841 assert(implics != NULL);
842 assert(*implics != NULL);
843 assert(implvar != NULL);
844
845 SCIPsetDebugMsg(set, "deleting implication from implics %p [%u]: <%s> %s x\n",
846 (void*)*implics, varfixing, SCIPvarGetName(implvar), impltype == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=");
847
848 checkImplics(*implics);
849
850 /* searches for y in implications of x */
851 found = implicsSearchImplic(*implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd);
852 if( !found )
853 {
854 SCIPsetDebugMsg(set, " -> implication was not found\n");
855 return SCIP_OKAY;
856 }
857
858 assert((impltype == SCIP_BOUNDTYPE_LOWER && poslower >= 0 && posadd == poslower)
859 || (impltype == SCIP_BOUNDTYPE_UPPER && posupper >= 0 && posadd == posupper));
860 assert(0 <= posadd && posadd < (*implics)->nimpls[varfixing]);
861 assert((*implics)->vars[varfixing][posadd] == implvar);
862 assert((*implics)->types[varfixing][posadd] == impltype);
863
864 /* removes y from implications of x */
865 if( (*implics)->nimpls[varfixing] - posadd > 1 )
866 {
867 int amount = ((*implics)->nimpls[varfixing] - posadd - 1);
868
869 BMSmoveMemoryArray(&((*implics)->types[varfixing][posadd]), &((*implics)->types[varfixing][posadd+1]), amount); /*lint !e866*/
870 BMSmoveMemoryArray(&((*implics)->vars[varfixing][posadd]), &((*implics)->vars[varfixing][posadd+1]), amount); /*lint !e866*/
871 BMSmoveMemoryArray(&((*implics)->bounds[varfixing][posadd]), &((*implics)->bounds[varfixing][posadd+1]), amount); /*lint !e866*/
872 }
873 (*implics)->nimpls[varfixing]--;
874
875 /* free implics data structure, if it is empty */
876 if( (*implics)->nimpls[0] == 0 && (*implics)->nimpls[1] == 0 )
877 SCIPimplicsFree(implics, blkmem);
878
879 checkImplics(*implics);
880
881 return SCIP_OKAY;
882 }
883
884 /** returns which implications on given variable y are contained in implications for x == 0 or x == 1 */
SCIPimplicsGetVarImplics(SCIP_IMPLICS * implics,SCIP_Bool varfixing,SCIP_VAR * implvar,SCIP_Bool * haslowerimplic,SCIP_Bool * hasupperimplic)885 void SCIPimplicsGetVarImplics(
886 SCIP_IMPLICS* implics, /**< implications data structure */
887 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
888 SCIP_VAR* implvar, /**< variable y to search for */
889 SCIP_Bool* haslowerimplic, /**< pointer to store whether there exists an implication y >= l */
890 SCIP_Bool* hasupperimplic /**< pointer to store whether there exists an implication y <= u */
891 )
892 {
893 int poslower;
894 int posupper;
895 int posadd;
896
897 assert(haslowerimplic != NULL);
898 assert(hasupperimplic != NULL);
899
900 implicsSearchVar(implics, varfixing, implvar, &poslower, &posupper, &posadd);
901
902 *haslowerimplic = (poslower >= 0);
903 *hasupperimplic = (posupper >= 0);
904 } /*lint !e438*/
905
906 /** returns whether an implication y <= b or y >= b is contained in implications for x == 0 or x == 1 */
SCIPimplicsContainsImpl(SCIP_IMPLICS * implics,SCIP_Bool varfixing,SCIP_VAR * implvar,SCIP_BOUNDTYPE impltype)907 SCIP_Bool SCIPimplicsContainsImpl(
908 SCIP_IMPLICS* implics, /**< implications data structure */
909 SCIP_Bool varfixing, /**< FALSE if y should be searched in implications for x == 0, TRUE for x == 1 */
910 SCIP_VAR* implvar, /**< variable y to search for */
911 SCIP_BOUNDTYPE impltype /**< type of implication y <=/>= b to search for */
912 )
913 {
914 int poslower;
915 int posupper;
916 int posadd;
917
918 return implicsSearchImplic(implics, varfixing, implvar, impltype, &poslower, &posupper, &posadd); /*lint !e438*/
919 } /*lint !e638*/
920
921
922
923
924 /*
925 * methods for cliques
926 */
927
928 /* swaps cliques at positions first and second in cliques array of clique table */
929 static
cliquetableSwapCliques(SCIP_CLIQUETABLE * cliquetable,int first,int second)930 void cliquetableSwapCliques(
931 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
932 int first, /**< first index */
933 int second /**< second index */
934 )
935 {
936 /* nothing to do if clique happens to be at the pole position of clean cliques */
937 if( first != second )
938 {
939 SCIP_CLIQUE* tmp;
940
941 tmp = cliquetable->cliques[first];
942 assert(tmp->index == first);
943 assert(cliquetable->cliques[second]->index == second);
944
945 cliquetable->cliques[first] = cliquetable->cliques[second];
946 cliquetable->cliques[second] = tmp;
947
948 /* change the indices accordingly */
949 tmp->index = second;
950 cliquetable->cliques[first]->index = first;
951 }
952 }
953
954 /* moves clique to the last position of currently dirty cliques */
955 static
cliquetableMarkCliqueForCleanup(SCIP_CLIQUETABLE * cliquetable,SCIP_CLIQUE * clique)956 void cliquetableMarkCliqueForCleanup(
957 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
958 SCIP_CLIQUE* clique /**< clique data structure */
959 )
960 {
961 assert(cliquetable->ndirtycliques <= clique->index);
962 assert(cliquetable->cliques[clique->index] == clique);
963 assert(cliquetable->ndirtycliques < cliquetable->ncliques);
964 assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ndirtycliques]));
965
966 /* nothing to do if clique happens to be at the pole position of clean cliques */
967 if( clique->index > cliquetable->ndirtycliques )
968 {
969 cliquetableSwapCliques(cliquetable, clique->index, cliquetable->ndirtycliques);
970 }
971
972 ++cliquetable->ndirtycliques;
973 }
974
975
976 /** creates a clique data structure with already created variables and values arrays in the size of 'size' */
977 static
cliqueCreateWithData(SCIP_CLIQUE ** clique,BMS_BLKMEM * blkmem,int size,SCIP_VAR ** vars,SCIP_Bool * values,int nvars,int id,SCIP_Bool isequation)978 SCIP_RETCODE cliqueCreateWithData(
979 SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
980 BMS_BLKMEM* blkmem, /**< block memory */
981 int size, /**< initial size of clique */
982 SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given
983 * value */
984 SCIP_Bool* values, /**< values of the variables in the clique */
985 int nvars, /**< number of variables in the clique */
986 int id, /**< unique identifier of the clique */
987 SCIP_Bool isequation /**< is the clique an equation or an inequality? */
988 )
989 {
990 assert(clique != NULL);
991 assert(blkmem != NULL);
992 assert(size >= nvars && nvars > 0);
993 assert(vars != NULL);
994 assert(values != NULL);
995
996 SCIP_ALLOC( BMSallocBlockMemory(blkmem, clique) );
997 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*clique)->vars, vars, size) );
998 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &(*clique)->values, values, size) );
999 (*clique)->nvars = nvars;
1000 (*clique)->size = size;
1001 (*clique)->startcleanup = -1;
1002 (*clique)->id = (unsigned int)id;
1003 (*clique)->eventsissued = FALSE;
1004 (*clique)->equation = isequation;
1005 (*clique)->index = -1;
1006
1007 return SCIP_OKAY;
1008 }
1009
1010 /** frees a clique data structure */
1011 static
cliqueFree(SCIP_CLIQUE ** clique,BMS_BLKMEM * blkmem)1012 void cliqueFree(
1013 SCIP_CLIQUE** clique, /**< pointer to store clique data structure */
1014 BMS_BLKMEM* blkmem /**< block memory */
1015 )
1016 {
1017 assert(clique != NULL);
1018
1019 if( *clique != NULL )
1020 {
1021 BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->vars, (*clique)->size);
1022 BMSfreeBlockMemoryArrayNull(blkmem, &(*clique)->values, (*clique)->size);
1023 BMSfreeBlockMemory(blkmem, clique);
1024 }
1025 }
1026
1027 /** ensures, that clique arrays can store at least num entries */
1028 static
cliqueEnsureSize(SCIP_CLIQUE * clique,BMS_BLKMEM * blkmem,SCIP_SET * set,int num)1029 SCIP_RETCODE cliqueEnsureSize(
1030 SCIP_CLIQUE* clique, /**< clique data structure */
1031 BMS_BLKMEM* blkmem, /**< block memory */
1032 SCIP_SET* set, /**< global SCIP settings */
1033 int num /**< minimum number of entries to store */
1034 )
1035 {
1036 assert(clique != NULL);
1037
1038 if( num > clique->size )
1039 {
1040 int newsize;
1041
1042 newsize = SCIPsetCalcMemGrowSize(set, num);
1043 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->vars, clique->size, newsize) );
1044 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &clique->values, clique->size, newsize) );
1045 clique->size = newsize;
1046 }
1047 assert(num <= clique->size);
1048
1049 return SCIP_OKAY;
1050 }
1051
1052 /** returns the position of the given variable/value pair in the clique; returns -1 if variable/value pair is not member
1053 * of the clique
1054 */
SCIPcliqueSearchVar(SCIP_CLIQUE * clique,SCIP_VAR * var,SCIP_Bool value)1055 int SCIPcliqueSearchVar(
1056 SCIP_CLIQUE* clique, /**< clique data structure */
1057 SCIP_VAR* var, /**< variable to search for */
1058 SCIP_Bool value /**< value of the variable in the clique */
1059 )
1060 {
1061 int varidx;
1062 int left;
1063 int right;
1064
1065 assert(clique != NULL);
1066
1067 varidx = SCIPvarGetIndex(var);
1068 left = -1;
1069 right = clique->nvars;
1070 while( left < right-1 )
1071 {
1072 int middle;
1073 int idx;
1074
1075 middle = (left+right)/2;
1076 idx = SCIPvarGetIndex(clique->vars[middle]);
1077 assert(idx >= 0);
1078 if( varidx < idx )
1079 right = middle;
1080 else if( varidx > idx )
1081 left = middle;
1082 else
1083 {
1084 assert(var == clique->vars[middle]);
1085
1086 /* now watch out for the correct value */
1087 if( clique->values[middle] < value )
1088 {
1089 int i;
1090 for( i = middle+1; i < clique->nvars && clique->vars[i] == var; ++i )
1091 {
1092 if( clique->values[i] == value )
1093 return i;
1094 }
1095 return -1;
1096 }
1097 if( clique->values[middle] > value )
1098 {
1099 int i;
1100 for( i = middle-1; i >= 0 && clique->vars[i] == var; --i )
1101 {
1102 if( clique->values[i] == value )
1103 return i;
1104 }
1105 return -1;
1106 }
1107 return middle;
1108 }
1109 }
1110
1111 return -1;
1112 }
1113
1114 /** returns whether the given variable/value pair is member of the given clique */
SCIPcliqueHasVar(SCIP_CLIQUE * clique,SCIP_VAR * var,SCIP_Bool value)1115 SCIP_Bool SCIPcliqueHasVar(
1116 SCIP_CLIQUE* clique, /**< clique data structure */
1117 SCIP_VAR* var, /**< variable to remove from the clique */
1118 SCIP_Bool value /**< value of the variable in the clique */
1119 )
1120 {
1121 return (SCIPcliqueSearchVar(clique, var, value) >= 0);
1122 }
1123
1124 /** adds a single variable to the given clique */
SCIPcliqueAddVar(SCIP_CLIQUE * clique,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_VAR * var,SCIP_Bool value,SCIP_Bool * doubleentry,SCIP_Bool * oppositeentry)1125 SCIP_RETCODE SCIPcliqueAddVar(
1126 SCIP_CLIQUE* clique, /**< clique data structure */
1127 BMS_BLKMEM* blkmem, /**< block memory */
1128 SCIP_SET* set, /**< global SCIP settings */
1129 SCIP_VAR* var, /**< variable to add to the clique */
1130 SCIP_Bool value, /**< value of the variable in the clique */
1131 SCIP_Bool* doubleentry, /**< pointer to store whether the variable and value occurs twice in the clique */
1132 SCIP_Bool* oppositeentry /**< pointer to store whether the variable with opposite value is in the clique */
1133 )
1134 {
1135 int pos;
1136 int i;
1137
1138 assert(clique != NULL);
1139 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN);
1140 assert(SCIPvarIsBinary(var));
1141 assert(doubleentry != NULL);
1142 assert(oppositeentry != NULL);
1143
1144 SCIPsetDebugMsg(set, "adding variable <%s> == %u to clique %u\n", SCIPvarGetName(var), value, clique->id);
1145
1146 *doubleentry = FALSE;
1147 *oppositeentry = FALSE;
1148
1149 /* allocate memory */
1150 SCIP_CALL( cliqueEnsureSize(clique, blkmem, set, clique->nvars+1) );
1151
1152 /* search for insertion position by binary variable, note that first the entries are order after variable index and
1153 * second after the bool value of the corresponding variable
1154 */
1155 (void) SCIPsortedvecFindPtr((void**) clique->vars, SCIPvarComp, var, clique->nvars, &pos);
1156
1157 assert(pos >= 0 && pos <= clique->nvars);
1158 /* remember insertion position for later, pos might change */
1159 i = pos;
1160
1161 if( pos < clique->nvars )
1162 {
1163 const int amount = clique->nvars - pos;
1164
1165 /* moving elements to correct position */
1166 BMSmoveMemoryArray(&(clique->vars[pos+1]), &(clique->vars[pos]), amount); /*lint !e866*/
1167 BMSmoveMemoryArray(&(clique->values[pos+1]), &(clique->values[pos]), amount); /*lint !e866*/
1168 clique->nvars++;
1169
1170 /* insertion for a variable with cliquevalue FALSE */
1171 if( !value )
1172 {
1173 /* find last entry with the same variable and value behind the insertion position */
1174 for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] == value; ++pos ); /*lint !e722*/
1175
1176 /* check if the same variable with other value also exists */
1177 if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var )
1178 {
1179 assert(clique->values[pos + 1] != value);
1180 *oppositeentry = TRUE;
1181 }
1182
1183 /* check if we found the same variable with the same value more than once */
1184 if( pos != i )
1185 *doubleentry = TRUE;
1186 else
1187 {
1188 /* find last entry with the same variable and different value before the insertion position */
1189 for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value; --pos ); /*lint !e722*/
1190
1191 /* check if we found the same variable with the same value more than once */
1192 if( pos > 0 && clique->vars[pos - 1] == var )
1193 {
1194 assert(clique->values[pos - 1] == value);
1195
1196 *doubleentry = TRUE;
1197 }
1198 /* if we found the same variable with different value, we need to order them correctly */
1199 if( pos != i )
1200 {
1201 assert(clique->vars[pos] == var);
1202 assert(clique->values[pos] != value);
1203
1204 clique->values[pos] = value;
1205 value = !value;
1206 }
1207 }
1208 }
1209 /* insertion for a variable with cliquevalue TRUE */
1210 else
1211 {
1212 /* find last entry with the same variable and different value behind the insertion position */
1213 for( ; pos < clique->nvars - 1 && clique->vars[pos + 1] == var && clique->values[pos + 1] != value; ++pos ); /*lint !e722*/
1214
1215 /* check if the same variable with other value also exists */
1216 if( pos < clique->nvars - 1 && clique->vars[pos + 1] == var )
1217 {
1218 assert(clique->values[pos + 1] == value);
1219 *doubleentry = TRUE;
1220 }
1221
1222 /* check if we found the same variable with different value */
1223 if( pos != i )
1224 {
1225 *oppositeentry = TRUE;
1226
1227 /* if we found the same variable with different value, we need to order them correctly */
1228 assert(clique->vars[pos] == var);
1229 assert(clique->values[pos] != value);
1230
1231 clique->values[pos] = value;
1232 value = !value;
1233 }
1234 else
1235 {
1236 /* find last entry with the same variable and value before the insertion position */
1237 for( ; pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] == value; --pos ); /*lint !e722*/
1238
1239 if( pos != i )
1240 *doubleentry = TRUE;
1241
1242 /* check if we found the same variable with different value up front */
1243 if( pos > 0 && clique->vars[pos - 1] == var && clique->values[pos - 1] != value )
1244 *oppositeentry = TRUE;
1245 }
1246 }
1247 }
1248 else
1249 clique->nvars++;
1250
1251 clique->vars[i] = var;
1252 clique->values[i] = value;
1253 clique->eventsissued = FALSE;
1254
1255 return SCIP_OKAY;
1256 }
1257
1258 /** removes a single variable from the given clique */
SCIPcliqueDelVar(SCIP_CLIQUE * clique,SCIP_CLIQUETABLE * cliquetable,SCIP_VAR * var,SCIP_Bool value)1259 void SCIPcliqueDelVar(
1260 SCIP_CLIQUE* clique, /**< clique data structure */
1261 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1262 SCIP_VAR* var, /**< variable to remove from the clique */
1263 SCIP_Bool value /**< value of the variable in the clique */
1264 )
1265 {
1266 int pos;
1267
1268 assert(clique != NULL);
1269 assert(SCIPvarIsBinary(var));
1270 assert(cliquetable != NULL);
1271
1272 /* if the clique is the leading clique during the cleanup step, we do not need to insert it again */
1273 if( cliquetable->incleanup && clique->index == 0 )
1274 return;
1275
1276 SCIPdebugMessage("marking variable <%s> == %u from clique %u for deletion\n", SCIPvarGetName(var), value, clique->id);
1277
1278 /* find variable in clique */
1279 pos = SCIPcliqueSearchVar(clique, var, value);
1280
1281 assert(0 <= pos && pos < clique->nvars);
1282 assert(clique->vars[pos] == var);
1283 assert(clique->values[pos] == value);
1284
1285 /* inform the clique table that this clique should be cleaned up */
1286 if( clique->startcleanup == -1 )
1287 cliquetableMarkCliqueForCleanup(cliquetable, clique);
1288
1289 if( clique->startcleanup == -1 || pos < clique->startcleanup )
1290 clique->startcleanup = pos;
1291
1292 #ifdef SCIP_MORE_DEBUG
1293 {
1294 int v;
1295 /* all variables prior to the one marked for startcleanup should be unfixed */
1296 for( v = clique->startcleanup - 1; v >= 0; --v )
1297 {
1298 assert(SCIPvarGetUbGlobal(clique->vars[v]) > 0.5);
1299 assert(SCIPvarGetLbGlobal(clique->vars[v]) < 0.5);
1300 }
1301 }
1302 #endif
1303 }
1304
1305 /** gets the position of the given clique in the cliques array; returns -1 if clique is not member of cliques array */
1306 static
cliquesSearchClique(SCIP_CLIQUE ** cliques,int ncliques,SCIP_CLIQUE * clique)1307 int cliquesSearchClique(
1308 SCIP_CLIQUE** cliques, /**< array of cliques */
1309 int ncliques, /**< number of cliques in the cliques array */
1310 SCIP_CLIQUE* clique /**< clique to search for */
1311 )
1312 {
1313 unsigned int cliqueid;
1314 int left;
1315 int right;
1316
1317 assert(cliques != NULL || ncliques == 0);
1318 assert(clique != NULL);
1319
1320 cliqueid = clique->id; /*lint !e732*/
1321 left = -1;
1322 right = ncliques;
1323 while( left < right-1 )
1324 {
1325 unsigned int id;
1326 int middle;
1327
1328 assert(cliques != NULL);
1329 middle = (left+right)/2;
1330 id = cliques[middle]->id; /*lint !e732*/
1331 if( cliqueid < id )
1332 right = middle;
1333 else if( cliqueid > id )
1334 left = middle;
1335 else
1336 {
1337 assert(clique == cliques[middle]);
1338 return middle;
1339 }
1340 }
1341
1342 return -1;
1343 }
1344
1345 #ifdef SCIP_MORE_DEBUG
1346 /** checks whether clique appears in all clique lists of the involved variables */
1347 static
cliqueCheck(SCIP_CLIQUE * clique)1348 void cliqueCheck(
1349 SCIP_CLIQUE* clique /**< clique data structure */
1350 )
1351 {
1352 int i;
1353
1354 assert(clique != NULL);
1355
1356 for( i = 0; i < clique->nvars; ++i )
1357 {
1358 SCIP_CLIQUE** cliques;
1359 int ncliques;
1360 int pos;
1361 SCIP_VAR* var;
1362
1363 var = clique->vars[i];
1364 assert(i == 0 || SCIPvarGetIndex(clique->vars[i-1]) <= SCIPvarGetIndex(var));
1365 assert(i == 0 || clique->vars[i-1] != var || clique->values[i-1] <= clique->values[i]);
1366 ncliques = SCIPvarGetNCliques(var, clique->values[i]);
1367
1368 assert(SCIPvarIsActive(var) || ncliques == 0);
1369
1370 /* cliquelist of inactive variables are already destroyed */
1371 if( ncliques == 0 )
1372 continue;
1373
1374 cliques = SCIPvarGetCliques(var, clique->values[i]);
1375 pos = cliquesSearchClique(cliques, ncliques, clique);
1376
1377 /* assert that the clique is correctly listed in all clique lists of unfixed variables. For fixed variables,
1378 * we require that a clean up has been correctly scheduled, but not yet been processed
1379 */
1380 if( SCIPvarGetUbGlobal(var) - SCIPvarGetLbGlobal(var) > 0.5 )
1381 {
1382 assert(0 <= pos && pos < ncliques);
1383 assert(cliques[pos] == clique);
1384 }
1385 else
1386 assert(0 <= clique->startcleanup && clique->startcleanup <= i);
1387 }
1388 assert(clique->index >= 0);
1389 }
1390 #else
1391 #define cliqueCheck(clique) /**/
1392 #endif
1393
1394 /** creates a clique list data structure */
1395 static
cliquelistCreate(SCIP_CLIQUELIST ** cliquelist,BMS_BLKMEM * blkmem)1396 SCIP_RETCODE cliquelistCreate(
1397 SCIP_CLIQUELIST** cliquelist, /**< pointer to store clique list data structure */
1398 BMS_BLKMEM* blkmem /**< block memory */
1399 )
1400 {
1401 assert(cliquelist != NULL);
1402
1403 SCIP_ALLOC( BMSallocBlockMemory(blkmem, cliquelist) );
1404 (*cliquelist)->cliques[0] = NULL;
1405 (*cliquelist)->cliques[1] = NULL;
1406 (*cliquelist)->ncliques[0] = 0;
1407 (*cliquelist)->ncliques[1] = 0;
1408 (*cliquelist)->size[0] = 0;
1409 (*cliquelist)->size[1] = 0;
1410
1411 return SCIP_OKAY;
1412 }
1413
1414 /** frees a clique list data structure */
SCIPcliquelistFree(SCIP_CLIQUELIST ** cliquelist,BMS_BLKMEM * blkmem)1415 void SCIPcliquelistFree(
1416 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1417 BMS_BLKMEM* blkmem /**< block memory */
1418 )
1419 {
1420 assert(cliquelist != NULL);
1421
1422 if( *cliquelist != NULL )
1423 {
1424 BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[0], (*cliquelist)->size[0]);
1425 BMSfreeBlockMemoryArrayNull(blkmem, &(*cliquelist)->cliques[1], (*cliquelist)->size[1]);
1426 BMSfreeBlockMemory(blkmem, cliquelist);
1427 }
1428 }
1429
1430 /** ensures, that clique list arrays can store at least num entries */
1431 static
cliquelistEnsureSize(SCIP_CLIQUELIST * cliquelist,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_Bool value,int num)1432 SCIP_RETCODE cliquelistEnsureSize(
1433 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
1434 BMS_BLKMEM* blkmem, /**< block memory */
1435 SCIP_SET* set, /**< global SCIP settings */
1436 SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
1437 int num /**< minimum number of entries to store */
1438 )
1439 {
1440 assert(cliquelist != NULL);
1441
1442 if( num > cliquelist->size[value] )
1443 {
1444 int newsize;
1445
1446 newsize = SCIPsetCalcMemGrowSize(set, num);
1447 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &cliquelist->cliques[value], cliquelist->size[value], newsize) ); /*lint !e866*/
1448 cliquelist->size[value] = newsize;
1449 }
1450 assert(num <= cliquelist->size[value]);
1451
1452 return SCIP_OKAY;
1453 }
1454
1455 /** adds a clique to the clique list */
SCIPcliquelistAdd(SCIP_CLIQUELIST ** cliquelist,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_Bool value,SCIP_CLIQUE * clique)1456 SCIP_RETCODE SCIPcliquelistAdd(
1457 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1458 BMS_BLKMEM* blkmem, /**< block memory */
1459 SCIP_SET* set, /**< global SCIP settings */
1460 SCIP_Bool value, /**< value of the variable for which the clique list should be extended */
1461 SCIP_CLIQUE* clique /**< clique that should be added to the clique list */
1462 )
1463 {
1464 unsigned int id;
1465 int i = 0;
1466
1467 assert(cliquelist != NULL);
1468
1469 /* insert clique into list, sorted by clique id */
1470 id = clique->id; /*lint !e732*/
1471
1472 /* allocate memory */
1473 if( *cliquelist == NULL )
1474 {
1475 SCIP_CALL( cliquelistCreate(cliquelist, blkmem) );
1476 }
1477 else
1478 {
1479 if( (*cliquelist)->cliques[value] != NULL )
1480 {
1481 for( i = (*cliquelist)->ncliques[value]; i > 0 && (*cliquelist)->cliques[value][i - 1]->id > id; --i ); /*lint !e574 !e722*/
1482 /* do not put the same clique twice in the cliquelist */
1483 if( i > 0 && (*cliquelist)->cliques[value][i - 1]->id == id )
1484 return SCIP_OKAY;
1485 }
1486 }
1487 SCIP_CALL( cliquelistEnsureSize(*cliquelist, blkmem, set, value, (*cliquelist)->ncliques[value] + 1) );
1488
1489 SCIPsetDebugMsg(set, "adding clique %u to cliquelist %p value %u (length: %d)\n",
1490 clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]);
1491
1492 BMSmoveMemoryArray(&((*cliquelist)->cliques[value][i+1]), &((*cliquelist)->cliques[value][i]), (*cliquelist)->ncliques[value] - i); /*lint !e866*/
1493
1494 (*cliquelist)->cliques[value][i] = clique;
1495 (*cliquelist)->ncliques[value]++;
1496
1497 return SCIP_OKAY;
1498 }
1499
1500 /** removes a clique from the clique list */
SCIPcliquelistDel(SCIP_CLIQUELIST ** cliquelist,BMS_BLKMEM * blkmem,SCIP_Bool value,SCIP_CLIQUE * clique)1501 SCIP_RETCODE SCIPcliquelistDel(
1502 SCIP_CLIQUELIST** cliquelist, /**< pointer to the clique list data structure */
1503 BMS_BLKMEM* blkmem, /**< block memory */
1504 SCIP_Bool value, /**< value of the variable for which the clique list should be reduced */
1505 SCIP_CLIQUE* clique /**< clique that should be deleted from the clique list */
1506 )
1507 {
1508 int pos;
1509
1510 assert(cliquelist != NULL);
1511
1512 /* if a variable appeared twice in its last clique and is now removed both times, the cliquelist is already cleaned
1513 up after the first removal call of this "doubleton" */
1514 if( *cliquelist == NULL )
1515 return SCIP_OKAY;
1516
1517 SCIPdebugMessage("deleting clique %u from cliquelist %p value %u (length: %d)\n",
1518 clique->id, (void*)*cliquelist, value, (*cliquelist)->ncliques[value]);
1519
1520 pos = cliquesSearchClique((*cliquelist)->cliques[value], (*cliquelist)->ncliques[value], clique);
1521
1522 /* clique does not exist in cliquelist, the clique should contain multiple entries of the same variable */
1523 if( pos < 0 )
1524 {
1525 #ifdef SCIP_MORE_DEBUG
1526 SCIP_VAR** clqvars;
1527 SCIP_Bool* clqvalues;
1528 int nclqvars = SCIPcliqueGetNVars(clique);
1529 int v;
1530
1531 assert(nclqvars >= 2);
1532 assert(SCIPcliqueGetVars(clique) != NULL);
1533 assert(SCIPcliqueGetValues(clique) != NULL);
1534
1535 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvars, SCIPcliqueGetVars(clique), nclqvars) );
1536 SCIP_ALLOC( BMSduplicateBlockMemoryArray(blkmem, &clqvalues, SCIPcliqueGetValues(clique), nclqvars) );
1537
1538 /* sort variables and corresponding clique values after variables indices */
1539 SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, nclqvars);
1540
1541 for( v = nclqvars - 1; v > 0; --v )
1542 {
1543 if( clqvars[v] == clqvars[v - 1] )
1544 {
1545 if( clqvalues[v] == clqvalues[v - 1] || (v > 1 && clqvars[v] == clqvars[v - 2]) )
1546 break;
1547 }
1548 }
1549 assert(v > 0);
1550
1551 BMSfreeBlockMemoryArray(blkmem, &clqvalues, nclqvars);
1552 BMSfreeBlockMemoryArray(blkmem, &clqvars, nclqvars);
1553 #endif
1554 return SCIP_OKAY;
1555 }
1556
1557 assert(0 <= pos && pos < (*cliquelist)->ncliques[value]);
1558 assert((*cliquelist)->cliques[value][pos] == clique);
1559
1560 /* remove clique from list */
1561 /* @todo maybe buffered deletion */
1562 (*cliquelist)->ncliques[value]--;
1563 if( pos < (*cliquelist)->ncliques[value] )
1564 {
1565 BMSmoveMemoryArray(&((*cliquelist)->cliques[value][pos]), &((*cliquelist)->cliques[value][pos+1]),
1566 (*cliquelist)->ncliques[value] - pos); /*lint !e866*/
1567 }
1568
1569 /* free cliquelist if it is empty */
1570 if( (*cliquelist)->ncliques[0] == 0 && (*cliquelist)->ncliques[1] == 0 )
1571 SCIPcliquelistFree(cliquelist, blkmem);
1572
1573 return SCIP_OKAY;
1574 }
1575
1576 /** returns whether the given clique lists have a non-empty intersection, i.e. whether there is a clique that appears
1577 * in both lists
1578 */
SCIPcliquelistsHaveCommonClique(SCIP_CLIQUELIST * cliquelist1,SCIP_Bool value1,SCIP_CLIQUELIST * cliquelist2,SCIP_Bool value2)1579 SCIP_Bool SCIPcliquelistsHaveCommonClique(
1580 SCIP_CLIQUELIST* cliquelist1, /**< first clique list data structure */
1581 SCIP_Bool value1, /**< value of first variable */
1582 SCIP_CLIQUELIST* cliquelist2, /**< second clique list data structure */
1583 SCIP_Bool value2 /**< value of second variable */
1584 )
1585 {
1586 SCIP_CLIQUE** cliques1;
1587 SCIP_CLIQUE** cliques2;
1588 int ncliques1;
1589 int ncliques2;
1590 int i1;
1591 int i2;
1592
1593 if( cliquelist1 == NULL || cliquelist2 == NULL )
1594 return FALSE;
1595
1596 ncliques1 = cliquelist1->ncliques[value1];
1597 cliques1 = cliquelist1->cliques[value1];
1598 ncliques2 = cliquelist2->ncliques[value2];
1599 cliques2 = cliquelist2->cliques[value2];
1600
1601 i1 = 0;
1602 i2 = 0;
1603
1604 if( i1 < ncliques1 && i2 < ncliques2 )
1605 {
1606 unsigned int cliqueid;
1607
1608 /* make the bigger clique the first one */
1609 if( ncliques2 > ncliques1 )
1610 {
1611 SCIP_CLIQUE** tmpc;
1612 int tmpi;
1613
1614 tmpc = cliques1;
1615 tmpi = ncliques1;
1616 cliques1 = cliques2;
1617 ncliques1 = ncliques2;
1618 cliques2 = tmpc;
1619 ncliques2 = tmpi;
1620 }
1621
1622 /* check whether both clique lists have a same clique */
1623 while( TRUE ) /*lint !e716*/
1624 {
1625 cliqueid = SCIPcliqueGetId(cliques2[i2]);
1626
1627 /* if last item in clique1 has a smaller index than the actual clique in clique2, than cause of increasing order
1628 * there will be no same item and we can stop */
1629 if( SCIPcliqueGetId(cliques1[ncliques1 - 1]) < cliqueid )
1630 break;
1631
1632 while( SCIPcliqueGetId(cliques1[i1]) < cliqueid )
1633 {
1634 ++i1;
1635 assert(i1 < ncliques1);
1636 }
1637 cliqueid = SCIPcliqueGetId(cliques1[i1]);
1638
1639 /* if last item in clique2 has a smaller index than the actual clique in clique1, than cause of increasing order
1640 * there will be no same item and we can stop */
1641 if( SCIPcliqueGetId(cliques2[ncliques2 - 1]) < cliqueid )
1642 break;
1643
1644 while( SCIPcliqueGetId(cliques2[i2]) < cliqueid )
1645 {
1646 ++i2;
1647 assert(i2 < ncliques2);
1648 }
1649 if( SCIPcliqueGetId(cliques2[i2]) == cliqueid )
1650 return TRUE;
1651 }
1652 }
1653 return FALSE;
1654 }
1655
1656 /** removes all listed entries from the cliques */
SCIPcliquelistRemoveFromCliques(SCIP_CLIQUELIST * cliquelist,SCIP_CLIQUETABLE * cliquetable,SCIP_VAR * var,SCIP_Bool irrelevantvar)1657 void SCIPcliquelistRemoveFromCliques(
1658 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
1659 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1660 SCIP_VAR* var, /**< active problem variable the clique list belongs to */
1661 SCIP_Bool irrelevantvar /**< has the variable become irrelevant, meaning that equality
1662 * cliques need to be relaxed? */
1663 )
1664 {
1665 assert(SCIPvarIsBinary(var));
1666
1667 if( cliquelist != NULL )
1668 {
1669 int value;
1670
1671 SCIPdebugMessage("removing variable <%s> from cliques (%d with value 0, %d with value 1)\n",
1672 SCIPvarGetName(var), cliquelist->ncliques[0], cliquelist->ncliques[1]);
1673
1674 for( value = 0; value < 2; ++value )
1675 {
1676 int i;
1677
1678 assert(SCIPvarGetCliques(var, (SCIP_Bool)value) == cliquelist->cliques[value]);
1679 assert(SCIPvarGetNCliques(var, (SCIP_Bool)value) == cliquelist->ncliques[value]);
1680
1681 /* it is important to iterate from the end of the array because otherwise, each removal causes
1682 * a memory move of the entire array
1683 */
1684 for( i = cliquelist->ncliques[value] - 1; i >= 0; --i )
1685 {
1686 SCIP_CLIQUE* clique;
1687
1688 clique = cliquelist->cliques[value][i];
1689 assert(clique != NULL);
1690
1691 SCIPdebugMessage(" -> removing variable <%s> == %d from clique %u (size %d)\n",
1692 SCIPvarGetName(var), value, clique->id, clique->nvars);
1693
1694 SCIPcliqueDelVar(clique, cliquetable, var, (SCIP_Bool)value);
1695
1696 if( irrelevantvar )
1697 clique->equation = FALSE;
1698
1699 #ifdef SCIP_MORE_DEBUG
1700 /* during the cleanup step, we skip the consistency check because clique may be temporarily inconsistent */
1701 if( ! cliquetable->incleanup || clique->index > 0 )
1702 {
1703 cliqueCheck(clique);
1704 }
1705 #endif
1706 }
1707 }
1708 }
1709 }
1710
1711 /** gets the key of the given element */
1712 static
SCIP_DECL_HASHGETKEY(hashgetkeyClique)1713 SCIP_DECL_HASHGETKEY(hashgetkeyClique)
1714 { /*lint --e{715}*/
1715 return elem;
1716 }
1717
1718 /** returns TRUE iff both keys are equal */
1719 static
SCIP_DECL_HASHKEYEQ(hashkeyeqClique)1720 SCIP_DECL_HASHKEYEQ(hashkeyeqClique)
1721 { /*lint --e{715}*/
1722 SCIP_CLIQUE* clique1;
1723 SCIP_CLIQUE* clique2;
1724 int i;
1725
1726 clique1 = (SCIP_CLIQUE*)key1;
1727 clique2 = (SCIP_CLIQUE*)key2;
1728 assert(clique1 != NULL);
1729 assert(clique2 != NULL);
1730
1731 if( clique1->nvars != clique2->nvars )
1732 return FALSE;
1733
1734 /* the variables are sorted: we can simply check the equality of each pair of variable/values */
1735 for( i = 0; i < clique1->nvars; ++i )
1736 {
1737 if( clique1->vars[i] != clique2->vars[i] || clique1->values[i] != clique2->values[i] )
1738 return FALSE;
1739 }
1740
1741 return TRUE;
1742 }
1743
1744 /** returns the hash value of the key */
1745 static
SCIP_DECL_HASHKEYVAL(hashkeyvalClique)1746 SCIP_DECL_HASHKEYVAL(hashkeyvalClique)
1747 { /*lint --e{715}*/
1748 SCIP_CLIQUE* clique;
1749
1750 clique = (SCIP_CLIQUE*)key;
1751
1752 return clique->nvars == 0 ? 0 : SCIPhashFour(SCIPvarGetIndex(clique->vars[0]), \
1753 SCIPvarGetIndex(clique->vars[clique->nvars-1]), \
1754 clique->nvars, 2*clique->values[0] + clique->values[clique->nvars-1]);
1755 }
1756
1757 #define HASHTABLE_CLIQUETABLE_SIZE 100
1758
1759 /** creates a clique table data structure */
SCIPcliquetableCreate(SCIP_CLIQUETABLE ** cliquetable,SCIP_SET * set,BMS_BLKMEM * blkmem)1760 SCIP_RETCODE SCIPcliquetableCreate(
1761 SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */
1762 SCIP_SET* set, /**< global SCIP settings */
1763 BMS_BLKMEM* blkmem /**< block memory */
1764 )
1765 {
1766 int hashtablesize;
1767
1768 assert(cliquetable != NULL);
1769
1770 SCIP_ALLOC( BMSallocMemory(cliquetable) );
1771
1772 /* create hash table to test for multiple cliques */
1773 hashtablesize = HASHTABLE_CLIQUETABLE_SIZE;
1774 hashtablesize = MAX(hashtablesize, (set->misc_usesmalltables ? SCIP_HASHSIZE_CLIQUES_SMALL : SCIP_HASHSIZE_CLIQUES));
1775 SCIP_CALL( SCIPhashtableCreate(&((*cliquetable)->hashtable), blkmem, hashtablesize,
1776 hashgetkeyClique, hashkeyeqClique, hashkeyvalClique, NULL) );
1777
1778 (*cliquetable)->varidxtable = NULL;
1779 (*cliquetable)->djset = NULL;
1780 (*cliquetable)->cliques = NULL;
1781 (*cliquetable)->ncliques = 0;
1782 (*cliquetable)->size = 0;
1783 (*cliquetable)->ncreatedcliques = 0;
1784 (*cliquetable)->ncleanupfixedvars = 0;
1785 (*cliquetable)->ncleanupaggrvars = 0;
1786 (*cliquetable)->ndirtycliques = 0;
1787 (*cliquetable)->nentries = 0;
1788 (*cliquetable)->incleanup = FALSE;
1789 (*cliquetable)->compsfromscratch = FALSE;
1790 (*cliquetable)->ncliquecomponents = -1;
1791
1792 return SCIP_OKAY;
1793 }
1794
1795 /** frees a clique table data structure */
SCIPcliquetableFree(SCIP_CLIQUETABLE ** cliquetable,BMS_BLKMEM * blkmem)1796 SCIP_RETCODE SCIPcliquetableFree(
1797 SCIP_CLIQUETABLE** cliquetable, /**< pointer to store clique table data structure */
1798 BMS_BLKMEM* blkmem /**< block memory */
1799 )
1800 {
1801 int i;
1802
1803 assert(cliquetable != NULL);
1804 assert(*cliquetable != NULL);
1805
1806 /* free all cliques */
1807 for( i = (*cliquetable)->ncliques - 1; i >= 0; --i )
1808 {
1809 cliqueFree(&(*cliquetable)->cliques[i], blkmem);
1810 }
1811
1812 /* free disjoint set (union find) data structure */
1813 if( (*cliquetable)->djset != NULL )
1814 SCIPdisjointsetFree(&(*cliquetable)->djset, blkmem);
1815
1816 /* free hash table for variable indices */
1817 if( (*cliquetable)->varidxtable != NULL )
1818 SCIPhashmapFree(&(*cliquetable)->varidxtable);
1819
1820 /* free clique table data */
1821 BMSfreeMemoryArrayNull(&(*cliquetable)->cliques);
1822
1823 /* free hash table */
1824 SCIPhashtableFree(&((*cliquetable)->hashtable));
1825
1826 BMSfreeMemory(cliquetable);
1827
1828 return SCIP_OKAY;
1829 }
1830
1831 /** ensures, that clique table arrays can store at least num entries */
1832 static
cliquetableEnsureSize(SCIP_CLIQUETABLE * cliquetable,SCIP_SET * set,int num)1833 SCIP_RETCODE cliquetableEnsureSize(
1834 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1835 SCIP_SET* set, /**< global SCIP settings */
1836 int num /**< minimum number of entries to store */
1837 )
1838 {
1839 assert(cliquetable != NULL);
1840
1841 if( num > cliquetable->size )
1842 {
1843 int newsize;
1844
1845 newsize = SCIPsetCalcMemGrowSize(set, num);
1846 SCIP_ALLOC( BMSreallocMemoryArray(&cliquetable->cliques, newsize) );
1847 cliquetable->size = newsize;
1848 }
1849 assert(num <= cliquetable->size);
1850
1851 return SCIP_OKAY;
1852 }
1853
1854 /** sort variables regarding their index and remove multiple entries of the same variable */
1855 static
sortAndMergeClique(SCIP_VAR ** clqvars,SCIP_Bool * clqvalues,int * nclqvars,SCIP_Bool * isequation,SCIP_CLIQUE * clique,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * transprob,SCIP_PROB * origprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_BRANCHCAND * branchcand,SCIP_EVENTQUEUE * eventqueue,SCIP_CLIQUETABLE * cliquetable,int * nbdchgs,SCIP_Bool * infeasible)1856 SCIP_RETCODE sortAndMergeClique(
1857 SCIP_VAR** clqvars, /**< variables of a clique */
1858 SCIP_Bool* clqvalues, /**< clique values, active or negated, for the variables in a clique */
1859 int* nclqvars, /**< number of clique variables */
1860 SCIP_Bool* isequation, /**< do we have an equation clique at hand? */
1861 SCIP_CLIQUE* clique, /**< clique data structure or NULL */
1862 BMS_BLKMEM* blkmem, /**< block memory */
1863 SCIP_SET* set, /**< global SCIP settings */
1864 SCIP_STAT* stat, /**< problem statistics */
1865 SCIP_PROB* transprob, /**< transformed problem */
1866 SCIP_PROB* origprob, /**< original problem */
1867 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
1868 SCIP_REOPT* reopt, /**< reoptimization data structure */
1869 SCIP_LP* lp, /**< current LP data */
1870 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
1871 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
1872 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
1873 int* nbdchgs, /**< pointer to store number of fixed variables */
1874 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
1875 )
1876 {
1877 int noldbdchgs;
1878 int startidx;
1879
1880 assert(nclqvars != NULL);
1881
1882 SCIPsetDebugMsg(set, "starting merging %d variables in clique %d\n", *nclqvars, (clique == NULL) ? -1 : (int) clique->id);
1883
1884 if( *nclqvars <= 1 )
1885 return SCIP_OKAY;
1886
1887 assert(clqvars != NULL);
1888 assert(clqvalues != NULL);
1889 assert(blkmem != NULL);
1890 assert(set != NULL);
1891 assert(stat != NULL);
1892 assert(transprob != NULL);
1893 assert(origprob != NULL);
1894 assert(tree != NULL);
1895 assert(eventqueue != NULL);
1896 assert(nbdchgs != NULL);
1897 assert(infeasible != NULL);
1898
1899 /* sort variables and corresponding clique values regarding variables indices before merging multiples */
1900 SCIPsortPtrBool((void**) clqvars, clqvalues, SCIPvarComp, *nclqvars);
1901
1902 noldbdchgs = *nbdchgs;
1903 /* check for multiple occurences or pairs of negations in the variable array, this should be very rare when creating a
1904 * new clique */
1905 startidx = *nclqvars - 1;
1906 while( startidx >= 0 )
1907 {
1908 SCIP_VAR* var;
1909 int nones;
1910 int nzeros;
1911 int curr;
1912
1913 var = clqvars[startidx];
1914 /* only column and loose variables can exist now */
1915 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
1916 assert(SCIPvarIsBinary(var));
1917
1918 /* the counters denote the occurrences of the variable var with value TRUE and FALSE as clqvalues, respectively */
1919 if( clqvalues[startidx] )
1920 {
1921 nones = 1;
1922 nzeros = 0;
1923 }
1924 else
1925 {
1926 nzeros = 1;
1927 nones = 0;
1928 }
1929 curr = startidx - 1;
1930
1931 /* loop and increase the counter based on the clique value */
1932 while( curr >= 0 )
1933 {
1934 if( clqvars[curr] == var )
1935 {
1936 if( clqvalues[curr] )
1937 nones++;
1938 else
1939 nzeros++;
1940 }
1941 else
1942 /* var is different from variable at index curr */
1943 break;
1944
1945 --curr;
1946 }
1947 assert(nzeros + nones <= *nclqvars);
1948
1949 /* single occurrence of the variable */
1950 if( nones + nzeros == 1 )
1951 {
1952 startidx = curr;
1953 continue;
1954 }
1955 /* at least two occurrences of both the variable and its negation; infeasible */
1956 if( nones >= 2 && nzeros >= 2 )
1957 {
1958 *infeasible = TRUE;
1959 break;
1960 }
1961
1962 /* do we have the same variable with the same clique value twice? */
1963 if( nones >= 2 || nzeros >= 2 )
1964 {
1965 SCIP_Bool fixvalue;
1966
1967 /* other cases should be handled as infeasible */
1968 assert(nones <= 1 || nzeros <= 1);
1969
1970 /* ensure that the variable is removed from both clique lists before fixing it */
1971 if( clique != NULL )
1972 {
1973 if( nones >= 1 )
1974 {
1975 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, TRUE, clique) );
1976 }
1977 if( nzeros >= 1 )
1978 {
1979 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, FALSE, clique) );
1980 }
1981 }
1982
1983 /* we fix the variable into the direction of fewer occurrences */
1984 fixvalue = nones >= 2 ? FALSE : TRUE;
1985
1986 /* a variable multiple times in one clique forces this variable to be zero */
1987 SCIP_CALL( SCIPvarFixBinary(var, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
1988 cliquetable, fixvalue, infeasible, nbdchgs) );
1989
1990 SCIPsetDebugMsg(set, "same var %s twice in a clique with value %d fixed to %d (was %s)\n", SCIPvarGetName(var), fixvalue ? 0 : 1,
1991 fixvalue ? 1 : 0, *infeasible ? "infeasible" : "feasible");
1992
1993 if( *infeasible )
1994 break;
1995 }
1996
1997 /* do we have a pair of negated variables? */
1998 if( nones >= 1 && nzeros >= 1 )
1999 {
2000 SCIPsetDebugMsg(set, "var %s is paired with its negation in one clique -> fix all other variables\n", SCIPvarGetName(var));
2001
2002 /* a pair of negated variables in one clique forces all other variables in the clique to be zero */
2003 if( nzeros + nones < *nclqvars )
2004 {
2005 int w;
2006
2007 w = *nclqvars - 1;
2008 while( w >= 0 )
2009 {
2010 /* skip all occurrences of variable var itself, these are between curr and startidx */
2011 if( w == startidx )
2012 {
2013 if( curr == -1 )
2014 break;
2015
2016 w = curr;
2017 }
2018 assert(clqvars[w] != var);
2019
2020 /* if one of the other variables occurs multiple times, we can
2021 * 1) deduce infeasibility if it occurs with different values
2022 * 2) wait for the last occurence to fix it
2023 */
2024 while( w > 0 && clqvars[w-1] == clqvars[w] )
2025 {
2026 if( clqvalues[w-1] != clqvalues[w] )
2027 {
2028 *infeasible = TRUE;
2029 break;
2030 }
2031 --w;
2032 }
2033
2034 if( *infeasible )
2035 break;
2036
2037 if( clique != NULL )
2038 {
2039 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[w], blkmem, clqvalues[w], clique) );
2040 }
2041 SCIP_CALL( SCIPvarFixBinary(clqvars[w], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2042 branchcand, eventqueue, cliquetable, !clqvalues[w], infeasible, nbdchgs) );
2043
2044 SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[w]), clqvalues[w],
2045 clqvalues[w] ? 0 : 1, *infeasible ? "infeasible" : "feasible");
2046
2047 if( *infeasible )
2048 break;
2049
2050 --w;
2051 }
2052 }
2053 /* all variables except for var were fixed */
2054 if( clique != NULL )
2055 {
2056 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, TRUE, clique) );
2057 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, FALSE, clique) );
2058 }
2059 *nclqvars = 0;
2060 *isequation = FALSE;
2061
2062 /* break main loop */
2063 break;
2064 }
2065
2066 /* otherwise, we would have an endless loop */
2067 assert(curr < startidx);
2068 startidx = curr;
2069 }
2070
2071 /* we might have found an infeasibility or reduced the clique to size 0 */
2072 if( *infeasible || *nclqvars == 0 )
2073 return SCIP_OKAY;
2074
2075 /* we fixed a variable because it appears at least twice, now we need to remove the fixings
2076 *
2077 * @note that if we are in probing or solving stage, the fixation on the variable might not be carried out yet,
2078 * because it was contradicting a local bound
2079 */
2080 if( *nbdchgs > noldbdchgs )
2081 {
2082 SCIP_VAR* onefixedvar;
2083 SCIP_Bool onefixedvalue;
2084 int w;
2085
2086 /* we initialize the former value only to please gcc */
2087 onefixedvalue = TRUE;
2088 onefixedvar = NULL;
2089
2090 /* remove all inactive variables, thereby checking for a variable that is fixed to one */
2091 startidx = 0;
2092 w = 0;
2093 while( startidx < *nclqvars )
2094 {
2095 SCIP_VAR* var;
2096
2097 var = clqvars[startidx];
2098
2099 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
2100 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE);
2101
2102 /* check if we have a variable fixed to one for this clique */
2103 if( (clqvalues[startidx] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[startidx] && SCIPvarGetUbGlobal(var) < 0.5) )
2104 {
2105 if( onefixedvar != NULL )
2106 {
2107 *infeasible = TRUE;
2108
2109 SCIPsetDebugMsg(set, "two variables in clique %d fixed to one %s%s and %s%s\n", (clique != NULL) ? (int) clique->id : -1,
2110 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clqvalues[startidx] ? "" : "~", SCIPvarGetName(clqvars[startidx]));
2111 return SCIP_OKAY;
2112 }
2113 onefixedvar = var;
2114 onefixedvalue = clqvalues[startidx];
2115 }
2116 /* only keep active variables */
2117 else if( SCIPvarGetLbGlobal(var) < 0.5 && SCIPvarGetUbGlobal(var) > 0.5 )
2118 {
2119 /* we remove all fixed variables */
2120 if( startidx > w )
2121 {
2122 clqvars[w] = clqvars[startidx];
2123 clqvalues[w] = clqvalues[startidx];
2124 }
2125 ++w;
2126 }
2127 else
2128 {
2129 /* can we have some variable fixed to one? */
2130 assert((SCIPvarGetUbGlobal(var) < 0.5 && clqvalues[startidx]) || (SCIPvarGetLbGlobal(var) > 0.5 && !clqvalues[startidx]));
2131
2132 if( clique != NULL )
2133 {
2134 SCIP_CALL( SCIPvarDelCliqueFromList(var, blkmem, clqvalues[startidx], clique) );
2135 }
2136 }
2137 ++startidx;
2138 }
2139
2140 /* the clique has been reduced to w active (unfixed) variables */
2141 *nclqvars = w;
2142
2143 /* in rare cases, a variable fixed to one is only detected in the merging step */
2144 if( onefixedvar != NULL )
2145 {
2146 SCIPsetDebugMsg(set, "variable %s%s in clique %d fixed to one, fixing all other variables to zero\n",
2147 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), (clique != NULL) ? (int) clique->id : -1);
2148
2149 /* handle all active variables by fixing them */
2150 for( startidx = *nclqvars; startidx >= 0; --startidx )
2151 {
2152 assert(SCIPvarGetStatus(clqvars[startidx]) == SCIP_VARSTATUS_COLUMN
2153 || SCIPvarGetStatus(clqvars[startidx]) == SCIP_VARSTATUS_LOOSE);
2154
2155 /* delete the variable from its clique lists and fix it */
2156 if( onefixedvalue != clqvalues[startidx] || clqvars[startidx] != onefixedvar )
2157 {
2158 if( clique != NULL )
2159 {
2160 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[startidx], blkmem, clqvalues[startidx], clique) );
2161 }
2162
2163 /* if one of the other variables occurs multiple times, we can
2164 * 1) deduce infeasibility if it occurs with different values
2165 * 2) wait for the last occurence to fix it
2166 */
2167 while( startidx > 0 && clqvars[startidx - 1] == clqvars[startidx] )
2168 {
2169 if( clqvalues[startidx - 1] != clqvalues[startidx] )
2170 {
2171 *infeasible = TRUE;
2172 return SCIP_OKAY;
2173 }
2174 --startidx; /*lint !e850*/
2175 }
2176
2177 SCIPsetDebugMsg(set, "fixing variable %s in clique %d to %d\n", SCIPvarGetName(clqvars[startidx]), (clique != NULL) ? (int) clique->id : -1,
2178 clqvalues[startidx] ? 0 : 1);
2179
2180 /* note that the variable status will remain unchanged */
2181 SCIP_CALL( SCIPvarFixBinary(clqvars[startidx], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2182 branchcand, eventqueue, cliquetable, !clqvalues[startidx], infeasible, nbdchgs) );
2183
2184 if( *infeasible )
2185 return SCIP_OKAY;
2186 }
2187 }
2188
2189 /* delete clique from onefixedvars clique list */
2190 if( clique != NULL ) /*lint !e850*/
2191 {
2192 SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) );
2193 }
2194
2195 *nclqvars = 0;
2196 *isequation = FALSE;
2197 }
2198 }
2199
2200 assert(!(*infeasible));
2201
2202 if( *isequation )
2203 {
2204 if( *nclqvars == 0 )
2205 {
2206 SCIPsetDebugMsg(set, "empty equation clique left over -> infeasible\n");
2207
2208 *infeasible = TRUE;
2209 }
2210 else if( *nclqvars == 1 )
2211 {
2212 assert(SCIPvarGetStatus(clqvars[0]) == SCIP_VARSTATUS_COLUMN
2213 || SCIPvarGetStatus(clqvars[0]) == SCIP_VARSTATUS_LOOSE);
2214 /* clearing data and removing variable from its clique list */
2215 if( clique != NULL )
2216 {
2217 SCIP_CALL( SCIPvarDelCliqueFromList(clqvars[0], blkmem, clqvalues[0], clique) );
2218 }
2219 SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2220 eventqueue, cliquetable, clqvalues[0], infeasible, nbdchgs) );
2221
2222 SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0],
2223 clqvalues[0] ? 1 : 0, *infeasible ? "infeasible" : "feasible");
2224
2225 *nclqvars = 0;
2226 *isequation = FALSE;
2227 }
2228 }
2229
2230 return SCIP_OKAY;
2231 }
2232
2233 /** helper function that returns the graph node index for a variable during connected component detection */
2234 static
cliquetableGetNodeIndexBinvar(SCIP_CLIQUETABLE * cliquetable,SCIP_VAR * binvar)2235 int cliquetableGetNodeIndexBinvar(
2236 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2237 SCIP_VAR* binvar /**< binary (or binary integer or implicit binary) variable */
2238 )
2239 {
2240 SCIP_VAR* activevar;
2241 int nodeindex;
2242
2243 assert(binvar != NULL);
2244 assert(SCIPvarIsBinary(binvar));
2245
2246 if( cliquetable->varidxtable == NULL )
2247 return -1;
2248
2249 /* get active representative of variable */
2250 if( !SCIPvarIsActive(binvar) )
2251 {
2252 activevar = SCIPvarGetProbvar(binvar);
2253 if( !SCIPvarIsActive(activevar) )
2254 return -1;
2255 }
2256 else
2257 activevar = binvar;
2258
2259 assert(SCIPvarIsBinary(activevar));
2260
2261 /* if the map does not contain an index for this variable, return -1 and mark that the components must be
2262 * recomputed from scratch
2263 */
2264 if( SCIPhashmapExists(cliquetable->varidxtable, (void*)activevar) )
2265 nodeindex = SCIPhashmapGetImageInt(cliquetable->varidxtable, (void *)activevar);
2266 else
2267 {
2268 nodeindex = -1;
2269 cliquetable->compsfromscratch = TRUE;
2270 }
2271
2272 return nodeindex;
2273 }
2274
2275
2276 /** updates connectedness information for the \p clique */
2277 static
cliquetableUpdateConnectednessClique(SCIP_CLIQUETABLE * cliquetable,SCIP_CLIQUE * clique)2278 void cliquetableUpdateConnectednessClique(
2279 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2280 SCIP_CLIQUE* clique /**< clique that should be added */
2281 )
2282 {
2283 int i;
2284 int lastnode;
2285 SCIP_VAR** clqvars;
2286 int nclqvars;
2287
2288 assert(cliquetable != NULL);
2289 assert(clique != NULL);
2290
2291 /* check if disjoint set (union find) data structure has not been allocated yet */
2292 if( cliquetable->djset == NULL )
2293 cliquetable->compsfromscratch = TRUE;
2294
2295 /* return immediately if a component update is already pending */
2296 if( cliquetable->compsfromscratch )
2297 return;
2298
2299 lastnode = -1;
2300 clqvars = clique->vars;
2301 nclqvars = clique->nvars;
2302
2303 /* loop over variables in the clique and connect the corresponding components */
2304 for( i = 0; i < nclqvars && !cliquetable->compsfromscratch; ++i )
2305 {
2306 /* this method may also detect that the clique table must entirely recompute connectedness */
2307 int currnode = cliquetableGetNodeIndexBinvar(cliquetable, clqvars[i]);
2308
2309 /* skip inactive variables */
2310 if( currnode == - 1 )
2311 continue;
2312
2313 /* connect this and the last active variable */
2314 if( lastnode != -1 )
2315 SCIPdisjointsetUnion(cliquetable->djset, lastnode, currnode, FALSE);
2316
2317 lastnode = currnode;
2318 }
2319 }
2320
2321 /** returns the index of the connected component of the clique graph that the variable belongs to, or -1 */
SCIPcliquetableGetVarComponentIdx(SCIP_CLIQUETABLE * cliquetable,SCIP_VAR * var)2322 int SCIPcliquetableGetVarComponentIdx(
2323 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2324 SCIP_VAR* var /**< problem variable */
2325 )
2326 {
2327 int cmpidx = -1;
2328 assert(var != NULL);
2329 assert(cliquetable->djset != NULL);
2330
2331 /* only binary variables can have a component index
2332 *(both integer and implicit integer variables can be binary)
2333 */
2334 if( SCIPvarIsBinary(var) )
2335 {
2336 int nodeindex = cliquetableGetNodeIndexBinvar(cliquetable, var);
2337 assert(nodeindex < SCIPdisjointsetGetSize(cliquetable->djset));
2338
2339 if( nodeindex >= 0 )
2340 cmpidx = SCIPdisjointsetFind(cliquetable->djset, nodeindex);
2341 }
2342
2343 return cmpidx;
2344 }
2345
2346
2347 /** adds a clique to the clique table, using the given values for the given variables;
2348 * performs implications if the clique contains the same variable twice
2349 */
SCIPcliquetableAdd(SCIP_CLIQUETABLE * cliquetable,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * transprob,SCIP_PROB * origprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_BRANCHCAND * branchcand,SCIP_EVENTQUEUE * eventqueue,SCIP_VAR ** vars,SCIP_Bool * values,int nvars,SCIP_Bool isequation,SCIP_Bool * infeasible,int * nbdchgs)2350 SCIP_RETCODE SCIPcliquetableAdd(
2351 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2352 BMS_BLKMEM* blkmem, /**< block memory */
2353 SCIP_SET* set, /**< global SCIP settings */
2354 SCIP_STAT* stat, /**< problem statistics */
2355 SCIP_PROB* transprob, /**< transformed problem */
2356 SCIP_PROB* origprob, /**< original problem */
2357 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2358 SCIP_REOPT* reopt, /**< reoptimization data structure */
2359 SCIP_LP* lp, /**< current LP data */
2360 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2361 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2362 SCIP_VAR** vars, /**< binary variables in the clique: at most one can be set to the given value */
2363 SCIP_Bool* values, /**< values of the variables in the clique; NULL to use TRUE for all vars */
2364 int nvars, /**< number of variables in the clique */
2365 SCIP_Bool isequation, /**< is the clique an equation or an inequality? */
2366 SCIP_Bool* infeasible, /**< pointer to store whether an infeasibility was detected */
2367 int* nbdchgs /**< pointer to count the number of performed bound changes, or NULL */
2368 )
2369 {
2370 SCIP_VAR** clqvars;
2371 SCIP_Bool* clqvalues;
2372 SCIP_CLIQUE* clique;
2373 SCIP_VAR* var;
2374 int size;
2375 int nlocalbdchgs = 0;
2376 int v;
2377 int w;
2378
2379 assert(cliquetable != NULL);
2380 assert(vars != NULL);
2381
2382 SCIPsetDebugMsg(set, "trying to add clique %d with %d vars to clique table\n", cliquetable->ncliques, nvars);
2383
2384 /* check clique on debugging solution */
2385 SCIP_CALL( SCIPdebugCheckClique(set, vars, values, nvars) ); /*lint !e506 !e774*/
2386
2387 *infeasible = FALSE;
2388 size = nvars;
2389
2390 /* copy clique data */
2391 if( values == NULL )
2392 {
2393 SCIP_CALL( SCIPsetAllocBufferArray(set, &clqvalues, size) );
2394
2395 /* initialize clique values data */
2396 for( v = nvars - 1; v >= 0; --v )
2397 clqvalues[v] = TRUE;
2398 }
2399 else
2400 {
2401 SCIP_CALL( SCIPsetDuplicateBufferArray(set, &clqvalues, values, size) );
2402 }
2403 SCIP_CALL( SCIPsetDuplicateBufferArray(set, &clqvars, vars, size) );
2404
2405 /* get active variables */
2406 SCIP_CALL( SCIPvarsGetProbvarBinary(&clqvars, &clqvalues, nvars) );
2407
2408 /* remove all inactive vars */
2409 for( v = nvars - 1; v >= 0; --v )
2410 {
2411 var = clqvars[v];
2412
2413 assert(SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN
2414 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_LOOSE
2415 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED
2416 || SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR);
2417 assert(SCIPvarIsBinary(var));
2418
2419 /* if we have a variables already fixed to one in the clique, fix all other to zero */
2420 if( ! SCIPvarIsMarkedDeleteGlobalStructures(var) &&
2421 ((clqvalues[v] && SCIPvarGetLbGlobal(var) > 0.5) || (!clqvalues[v] && SCIPvarGetUbGlobal(var) < 0.5)) )
2422 {
2423 SCIPsetDebugMsg(set, "in a clique var %s with value %u is fixed to %d -> fix the rest\n", SCIPvarGetName(var), clqvalues[v], clqvalues[v] ? 1 : 0);
2424
2425 for( w = nvars - 1; w >= 0; --w )
2426 {
2427 SCIP_VAR* clqvar = clqvars[w];
2428
2429 /* the rare case where the same variable appears several times is handled later during sort and merge */
2430 if( clqvar != var )
2431 {
2432 SCIP_Bool clqval = clqvalues[w];
2433
2434 /* check if variable is fixed already and terminate with infeasible if this fixing contradicts the clique info */
2435 if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 )
2436 {
2437 /* check if fixing contradicts clique constraint */
2438 if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5)
2439 || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) )
2440 {
2441 *infeasible = TRUE;
2442
2443 goto FREEMEM;
2444 }
2445
2446 continue;
2447 }
2448
2449 /* the following piece of code is disabled because it assumes the clqvars to be sorted which they aren't until the method
2450 * sortAndMergeClique() is called
2451 */
2452 #ifdef SCIP_DISABLED_CODE
2453 /* if one of the other variables occurs multiple times, we can
2454 * 1) deduce infeasibility if it occurs with different values
2455 * 2) wait for the last occurence to fix it
2456 */
2457 while( w > 0 && clqvars[w - 1] == clqvars[w] )
2458 {
2459 if( clqvalues[w - 1] != clqvalues[w] )
2460 {
2461 *infeasible = TRUE;
2462 return SCIP_OKAY;
2463 }
2464 --w;
2465 }
2466 #endif
2467
2468 /* fix the variable */
2469 SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2470 branchcand, eventqueue, cliquetable, !clqval, infeasible, &nlocalbdchgs) );
2471
2472 SCIPsetDebugMsg(set, "fixed var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvar), clqval,
2473 clqval ? 0 : 1, *infeasible ? "infeasible" : "feasible");
2474
2475 if( *infeasible )
2476 break;
2477 }
2478 }
2479
2480 /* all variables are fixed so we can stop */
2481 break; /*lint !e850*/
2482 }
2483
2484 /* only unfixed column and loose variables may be member of a clique */
2485 if( SCIPvarGetUbGlobal(var) - SCIPvarGetLbGlobal(var) < 0.5 ||
2486 (SCIPvarGetStatus(var) != SCIP_VARSTATUS_COLUMN && SCIPvarGetStatus(var) != SCIP_VARSTATUS_LOOSE) ||
2487 SCIPvarIsMarkedDeleteGlobalStructures(var) )
2488 {
2489 --nvars;
2490 clqvars[v] = clqvars[nvars];
2491 clqvalues[v] = clqvalues[nvars];
2492 isequation = isequation && !(SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR) && ! SCIPvarIsMarkedDeleteGlobalStructures(var);
2493 }
2494 }
2495
2496 if( nbdchgs != NULL )
2497 *nbdchgs += nlocalbdchgs;
2498
2499 /* did we fix all variables or are we infeasible? */
2500 if( v >= 0 )
2501 goto FREEMEM;
2502
2503 assert(!*infeasible);
2504
2505 /* check if only one or less variables are left */
2506 if( v < 0 && nvars <= 1)
2507 {
2508 if( isequation )
2509 {
2510 if( nvars == 1 )
2511 {
2512 nlocalbdchgs = 0;
2513
2514 SCIP_CALL( SCIPvarFixBinary(clqvars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2515 branchcand, eventqueue, cliquetable, clqvalues[0], infeasible, &nlocalbdchgs) );
2516
2517 SCIPsetDebugMsg(set, "fixed last clique var %s with value %u to %d (was %s)\n", SCIPvarGetName(clqvars[0]), clqvalues[0],
2518 clqvalues[0] ? 1 : 0, *infeasible ? "infeasible" : "feasible");
2519
2520 if( nbdchgs != NULL )
2521 *nbdchgs += nlocalbdchgs;
2522 }
2523 else if( nvars == 0 )
2524 {
2525 SCIPsetDebugMsg(set, "empty equation clique left over -> infeasible\n");
2526
2527 *infeasible = TRUE;
2528 }
2529 }
2530
2531 goto FREEMEM;
2532 }
2533
2534 nlocalbdchgs = 0;
2535
2536 /* sort the variables and values and remove multiple entries of the same variable */
2537 SCIP_CALL( sortAndMergeClique(clqvars, clqvalues, &nvars, &isequation, NULL, blkmem, set, stat, transprob, origprob, tree,
2538 reopt, lp, branchcand, eventqueue, cliquetable, &nlocalbdchgs, infeasible) );
2539
2540 if( nbdchgs != NULL )
2541 *nbdchgs += nlocalbdchgs;
2542
2543 /* did we stop early due to a pair of negated variables? */
2544 if( nvars == 0 || *infeasible )
2545 goto FREEMEM;
2546
2547 if( !SCIPsetIsInfinity(set, set->presol_clqtablefac) && SCIPcliquetableGetNEntries(cliquetable) + nvars > set->presol_clqtablefac * stat->nnz )
2548 {
2549 SCIPsetDebugMsg(set, "reject %d-variable clique to keep clique table entries below threshold of %g entries\n",
2550 nvars, set->presol_clqtablefac * stat->nnz);
2551
2552 goto FREEMEM;
2553 }
2554
2555 /* if less than two variables are left over, the clique is redundant */
2556 if( nvars > 1 )
2557 {
2558 SCIP_CLIQUE* sameclique;
2559
2560 /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */
2561
2562 /* create the clique data structure */
2563 SCIP_CALL( cliqueCreateWithData(&clique, blkmem, nvars, clqvars, clqvalues, nvars, cliquetable->ncreatedcliques, isequation) );
2564
2565 sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique);
2566
2567 if( sameclique == NULL )
2568 {
2569 SCIPsetDebugMsg(set, "adding clique %u with %d vars to clique table\n", clique->id, nvars);
2570
2571 cliquetable->ncreatedcliques++;
2572
2573 /* add clique to clique table */
2574 SCIP_CALL( cliquetableEnsureSize(cliquetable, set, cliquetable->ncliques+1) );
2575 cliquetable->cliques[cliquetable->ncliques] = clique;
2576 clique->index = cliquetable->ncliques;
2577 cliquetable->ncliques++;
2578 cliquetable->nentries += nvars;
2579 cliquetableUpdateConnectednessClique(cliquetable, clique);
2580
2581 SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) );
2582
2583 /* add filled clique to the cliquelists of all corresponding variables */
2584 SCIP_CALL( SCIPvarsAddClique(clqvars, clqvalues, nvars, blkmem, set, clique) );
2585 }
2586 else
2587 {
2588 SCIPsetDebugMsg(set, "same clique %p (id: %d) already found in cliquetable -> discard new one\n", (void*) sameclique, sameclique->id);
2589
2590 /* update equation status of clique */
2591 /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
2592 * the sameclique from the hashmap while adding the new clique
2593 */
2594 if( !sameclique->equation && clique->equation )
2595 sameclique->equation = TRUE;
2596
2597 cliqueFree(&clique, blkmem);
2598
2599 goto FREEMEM;
2600 }
2601 }
2602 else
2603 {
2604 assert(!isequation);
2605 assert(nvars == 1);
2606
2607 goto FREEMEM;
2608 }
2609 cliqueCheck(clique);
2610
2611 FREEMEM:
2612 SCIPsetFreeBufferArray(set, &clqvars);
2613 SCIPsetFreeBufferArray(set, &clqvalues);
2614
2615 return SCIP_OKAY;
2616 }
2617
2618 /** clean up given clique by removing fixed variables */
2619 static
cliqueCleanup(SCIP_CLIQUE * clique,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * transprob,SCIP_PROB * origprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_BRANCHCAND * branchcand,SCIP_EVENTQUEUE * eventqueue,SCIP_CLIQUETABLE * cliquetable,int * nchgbds,SCIP_Bool * infeasible)2620 SCIP_RETCODE cliqueCleanup(
2621 SCIP_CLIQUE* clique, /**< clique data structure */
2622 BMS_BLKMEM* blkmem, /**< block memory */
2623 SCIP_SET* set, /**< global SCIP settings */
2624 SCIP_STAT* stat, /**< problem statistics */
2625 SCIP_PROB* transprob, /**< transformed problem */
2626 SCIP_PROB* origprob, /**< original problem */
2627 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2628 SCIP_REOPT* reopt, /**< reoptimization data structure */
2629 SCIP_LP* lp, /**< current LP data */
2630 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2631 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2632 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2633 int* nchgbds, /**< pointer to store number of fixed variables */
2634 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2635 )
2636 {
2637 assert(clique != NULL);
2638 assert(blkmem != NULL);
2639 assert(set != NULL);
2640 assert(nchgbds != NULL);
2641 assert(infeasible != NULL);
2642
2643 /* do we need to clean up fixed variables? */
2644 if( !SCIPcliqueIsCleanedUp(clique) )
2645 {
2646 SCIP_VAR* onefixedvar = NULL;
2647 SCIP_Bool onefixedvalue;
2648 SCIP_Bool needsorting = FALSE;
2649 int v;
2650 int w;
2651
2652 w = clique->startcleanup;
2653
2654 SCIPsetDebugMsg(set, "Starting clean up of clique %u (size %d) from position %d\n", clique->id, clique->nvars, w);
2655
2656 /* exchange inactive by active variables */
2657 for( v = w; v < clique->nvars; ++v )
2658 {
2659 SCIP_Bool addvartoclique; /* has the variable status changed such that it needs to be replaced by an active representative? */
2660
2661 addvartoclique = FALSE;
2662 if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_AGGREGATED
2663 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED
2664 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR )
2665 {
2666 needsorting = TRUE;
2667
2668 SCIP_CALL( SCIPvarGetProbvarBinary(&(clique->vars[v]), &(clique->values[v])) );
2669 if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_NEGATED )
2670 {
2671 clique->vars[v] = SCIPvarGetNegationVar(clique->vars[v]);
2672 clique->values[v] = !clique->values[v];
2673 }
2674 else if( SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_MULTAGGR )
2675 {
2676 clique->equation = FALSE;
2677 continue;
2678 }
2679
2680 addvartoclique = TRUE;
2681 }
2682
2683 assert(SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_COLUMN
2684 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_LOOSE
2685 || SCIPvarGetStatus(clique->vars[v]) == SCIP_VARSTATUS_FIXED);
2686
2687 /* check for variables that are either fixed to zero or marked for deletion from global structures */
2688 if( (clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) ||
2689 (!clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5) ||
2690 SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) )
2691 {
2692 if( clique->equation && SCIPvarIsMarkedDeleteGlobalStructures(clique->vars[v]) )
2693 clique->equation = FALSE;
2694
2695 /* the variable will be overwritten by subsequent active variables */
2696 continue;
2697 }
2698
2699 /* check for a variable fixed to one in the clique */
2700 else if( (clique->values[v] && SCIPvarGetLbGlobal(clique->vars[v]) > 0.5)
2701 || (!clique->values[v] && SCIPvarGetUbGlobal(clique->vars[v]) < 0.5) )
2702 {
2703 if( onefixedvar != NULL )
2704 {
2705 *infeasible = TRUE;
2706
2707 SCIPsetDebugMsg(set, "two variables in clique %u fixed to one %s%s and %s%s\n", clique->id,
2708 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->values[v] ? "" : "~",
2709 SCIPvarGetName(clique->vars[v])); /*lint !e530*/
2710 return SCIP_OKAY;
2711 }
2712 onefixedvar = clique->vars[v];
2713 onefixedvalue = clique->values[v];
2714 }
2715 else
2716 {
2717 assert(SCIPvarGetStatus(clique->vars[v]) != SCIP_VARSTATUS_FIXED);
2718 assert(w <= v);
2719
2720 if( w < v )
2721 {
2722 clique->vars[w] = clique->vars[v];
2723 clique->values[w] = clique->values[v];
2724 }
2725
2726 /* add clique to active variable if it replaced a aggregated or negated var */
2727 if( addvartoclique )
2728 {
2729 SCIP_CALL( SCIPvarAddCliqueToList(clique->vars[w], blkmem, set, clique->values[w], clique) );
2730 }
2731 /* increase indexer of last active, i.e. unfixed, variable in clique */
2732 ++w;
2733 }
2734 }
2735 clique->nvars = w;
2736
2737 if( onefixedvar != NULL )
2738 {
2739 SCIPsetDebugMsg(set, "variable %s%s in clique %u fixed to one, fixing all other variables to zero\n",
2740 onefixedvalue ? "" : "~", SCIPvarGetName(onefixedvar), clique->id);
2741
2742 for( v = 0; v < clique->nvars ; ++v )
2743 {
2744 SCIP_VAR* clqvar = clique->vars[v];
2745 SCIP_Bool clqval = clique->values[v];
2746
2747 assert(SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_COLUMN
2748 || SCIPvarGetStatus(clqvar) == SCIP_VARSTATUS_LOOSE);
2749
2750 if( onefixedvalue != clqval || clqvar != onefixedvar )
2751 {
2752 /* the variable could have been fixed already because it appears more than once in the clique */
2753 if( SCIPvarGetLbGlobal(clqvar) > SCIPvarGetUbGlobal(clqvar) - 0.5 )
2754 {
2755 /* the fixing must have occurred previously inside this loop. It may happen that
2756 * the variable occurs together with its negation in that clique, which is usually
2757 * handled during the merge step, but leads to a direct infeasibility because it
2758 * contradicts any other variable fixed to one in this clique
2759 */
2760 if( (clqval && SCIPvarGetLbGlobal(clqvar) > 0.5)
2761 || (! clqval && SCIPvarGetUbGlobal(clqvar) < 0.5) )
2762 {
2763 /* impossible because we would have detected this in the previous cleanup loop */
2764 assert(clqvar != onefixedvar);
2765 *infeasible = TRUE;
2766
2767 return SCIP_OKAY;
2768 }
2769 continue;
2770 }
2771
2772 SCIP_CALL( SCIPvarDelCliqueFromList(clqvar, blkmem, clqval, clique) );
2773
2774 /* the following piece of code is wrong at this point because it assumes sorted variables. can be enabled if sorting
2775 * of variables is performed earlier than it is now
2776 */
2777 #ifdef SCIP_DISABLED_CODE
2778 /* if one of the other variables occurs multiple times, we can
2779 * 1) deduce infeasibility if it occurs with different values
2780 * 2) wait for the last occurence to fix it
2781 */
2782 while( v < clique->nvars - 1 && clique->vars[v + 1] == clqvar )
2783 {
2784 if( clique->values[v + 1] != clique->values[v] )
2785 {
2786 *infeasible = TRUE;
2787 return SCIP_OKAY;
2788 }
2789 ++v;
2790 }
2791 #endif
2792 SCIPsetDebugMsg(set, "fixing variable %s in clique %u to %d\n", SCIPvarGetName(clqvar), clique->id, clqval ? 0 : 1);
2793
2794 SCIP_CALL( SCIPvarFixBinary(clqvar, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
2795 eventqueue, cliquetable, !clqval, infeasible, nchgbds) );
2796
2797 if( *infeasible )
2798 return SCIP_OKAY;
2799 }
2800 }
2801
2802 if( SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_COLUMN /*lint !e850*/
2803 || SCIPvarGetStatus(onefixedvar) == SCIP_VARSTATUS_LOOSE )
2804 {
2805 SCIP_CALL( SCIPvarDelCliqueFromList(onefixedvar, blkmem, onefixedvalue, clique) );
2806 }
2807
2808 clique->nvars = 0;
2809 clique->equation = FALSE;
2810 clique->startcleanup = -1;
2811
2812 return SCIP_OKAY;
2813 }
2814
2815 if( clique->equation )
2816 {
2817 if( clique->nvars == 0 )
2818 {
2819 *infeasible = TRUE;
2820 return SCIP_OKAY;
2821 }
2822 else if( clique->nvars == 1 )
2823 {
2824 assert(SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_COLUMN
2825 || SCIPvarGetStatus(clique->vars[0]) == SCIP_VARSTATUS_LOOSE);
2826
2827 /* clearing data and removing variable from its clique list */
2828 SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[0], blkmem, clique->values[0], clique) );
2829
2830 SCIPsetDebugMsg(set, "fixing last variable %s in clique %u to %d\n", SCIPvarGetName(clique->vars[0]), clique->id,
2831 clique->values[0] ? 1 : 0);
2832
2833 SCIP_CALL( SCIPvarFixBinary(clique->vars[0], blkmem, set, stat, transprob, origprob, tree, reopt, lp,
2834 branchcand, eventqueue, cliquetable, clique->values[0], infeasible, nchgbds) );
2835
2836 clique->nvars = 0;
2837 clique->equation = FALSE;
2838 clique->startcleanup = -1;
2839
2840 return SCIP_OKAY;
2841 }
2842 }
2843
2844 if( needsorting )
2845 {
2846 SCIP_Bool isequation = clique->equation;
2847
2848 /* remove multiple entries of the same variable */
2849 SCIP_CALL( sortAndMergeClique(clique->vars, clique->values, &(clique->nvars), &isequation, clique, blkmem, set, stat,
2850 transprob, origprob, tree, reopt, lp, branchcand, eventqueue, cliquetable, nchgbds, infeasible) );
2851
2852 clique->equation = isequation;
2853 }
2854
2855 /* @todo check if we can aggregate variables if( clique->equation && clique->nvars == 2 ) */
2856
2857 clique->startcleanup = -1;
2858 }
2859 assert(SCIPcliqueIsCleanedUp(clique));
2860
2861 return SCIP_OKAY;
2862 }
2863
2864 #ifdef SCIP_MORE_DEBUG
2865 /** checks whether clique appears in all clique lists of the involved variables */
2866 static
checkNEntries(SCIP_CLIQUETABLE * cliquetable)2867 SCIP_Bool checkNEntries(
2868 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
2869 )
2870 {
2871 SCIP_Longint nentries = 0;
2872 int c;
2873
2874 assert(cliquetable != NULL);
2875
2876 for( c = cliquetable->ncliques - 1; c >= 0; --c )
2877 nentries += cliquetable->cliques[c]->nvars;
2878
2879 return (nentries == cliquetable->nentries);
2880 }
2881 #else
2882 #define checkNEntries(cliquetable) TRUE
2883 #endif
2884
2885 /** removes all empty and single variable cliques from the clique table; removes double entries from the clique table
2886 *
2887 * @note cliques can be processed several times by this method
2888 *
2889 * @todo try to detect infeasible implications, e.g., x = 1 => (y = 0 && y = 1)
2890 */
SCIPcliquetableCleanup(SCIP_CLIQUETABLE * cliquetable,BMS_BLKMEM * blkmem,SCIP_SET * set,SCIP_STAT * stat,SCIP_PROB * transprob,SCIP_PROB * origprob,SCIP_TREE * tree,SCIP_REOPT * reopt,SCIP_LP * lp,SCIP_BRANCHCAND * branchcand,SCIP_EVENTQUEUE * eventqueue,int * nchgbds,SCIP_Bool * infeasible)2891 SCIP_RETCODE SCIPcliquetableCleanup(
2892 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
2893 BMS_BLKMEM* blkmem, /**< block memory */
2894 SCIP_SET* set, /**< global SCIP settings */
2895 SCIP_STAT* stat, /**< problem statistics */
2896 SCIP_PROB* transprob, /**< transformed problem */
2897 SCIP_PROB* origprob, /**< original problem */
2898 SCIP_TREE* tree, /**< branch and bound tree if in solving stage */
2899 SCIP_REOPT* reopt, /**< reoptimization data structure */
2900 SCIP_LP* lp, /**< current LP data */
2901 SCIP_BRANCHCAND* branchcand, /**< branching candidate storage */
2902 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
2903 int* nchgbds, /**< pointer to store number of fixed variables */
2904 SCIP_Bool* infeasible /**< pointer to store whether an infeasibility was detected */
2905 )
2906 {
2907 assert(cliquetable != NULL);
2908 assert(stat != NULL);
2909 assert(infeasible != NULL);
2910
2911 *infeasible = FALSE;
2912
2913 /* check if we have anything to do */
2914 if( stat->npresolfixedvars == cliquetable->ncleanupfixedvars
2915 && stat->npresolaggrvars == cliquetable->ncleanupaggrvars
2916 && cliquetable->ndirtycliques == 0 )
2917 return SCIP_OKAY;
2918
2919 SCIPsetDebugMsg(set, "cleaning up clique table with %d cliques (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
2920
2921 /* delay events */
2922 SCIP_CALL( SCIPeventqueueDelay(eventqueue) );
2923
2924 cliquetable->incleanup = TRUE;
2925 while( cliquetable->ndirtycliques > 0 && !(*infeasible) )
2926 {
2927 SCIP_CLIQUE* clique;
2928 SCIP_CLIQUE* sameclique;
2929
2930 clique = cliquetable->cliques[0];
2931
2932 assert(!SCIPcliqueIsCleanedUp(clique));
2933
2934 /* remove not clean up clique from hastable */
2935 SCIP_CALL( SCIPhashtableRemove(cliquetable->hashtable, (void*)clique) );
2936 cliquetable->nentries -= clique->nvars;
2937 assert(cliquetable->nentries >= 0);
2938
2939 SCIP_CALL( cliqueCleanup(clique, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
2940 cliquetable, nchgbds, infeasible) );
2941
2942 if( *infeasible )
2943 break;
2944
2945 assert(SCIPcliqueIsCleanedUp(clique));
2946
2947 /* swap freshly cleaned clique with last dirty clique */
2948 cliquetable->ndirtycliques--;
2949 cliquetableSwapCliques(cliquetable, 0, cliquetable->ndirtycliques);
2950 cliqueCheck(clique);
2951
2952 /* @todo check if we can/want to aggregate variables with the following code */
2953 #ifdef SCIP_DISABLED_CODE
2954 if( clique->nvars == 2 && clique->equation && SCIPsetGetStage(set) == SCIP_STAGE_PRESOLVING )
2955 {
2956 SCIP_VAR* var0;
2957 SCIP_VAR* var1;
2958 SCIP_Real scalarx;
2959 SCIP_Real scalary;
2960 SCIP_Real rhs = 1.0;
2961 SCIP_Bool aggregated;
2962
2963 printf("aggr vars, clique %d\n", clique->id);
2964
2965 if( SCIPvarGetType(clique->vars[0]) >= SCIPvarGetType(clique->vars[1]) )
2966 {
2967 var0 = clique->vars[0];
2968 var1 = clique->vars[1];
2969
2970 if( !clique->values[0] )
2971 {
2972 scalarx = -1.0;
2973 rhs -= 1.0;
2974 }
2975 else
2976 scalarx = 1.0;
2977
2978 if( !clique->values[1] )
2979 {
2980 scalary = -1.0;
2981 rhs -= 1.0;
2982 }
2983 else
2984 scalary = 1.0;
2985 }
2986 else
2987 {
2988 var0 = clique->vars[1];
2989 var1 = clique->vars[0];
2990
2991 if( !clique->values[0] )
2992 {
2993 scalary = -1.0;
2994 rhs -= 1.0;
2995 }
2996 else
2997 scalary = 1.0;
2998
2999 if( !clique->values[1] )
3000 {
3001 scalarx = -1.0;
3002 rhs -= 1.0;
3003 }
3004 else
3005 scalarx = 1.0;
3006 }
3007
3008 assert((SCIPvarGetStatus(var0) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var0) == SCIP_VARSTATUS_COLUMN)
3009 && (SCIPvarGetStatus(var1) == SCIP_VARSTATUS_LOOSE || SCIPvarGetStatus(var1) == SCIP_VARSTATUS_COLUMN));
3010
3011 /* aggregate the variable */
3012 SCIP_CALL( SCIPvarTryAggregateVars(set, blkmem, stat, transprob, origprob, primal,
3013 tree, lp, cliquetable, branchcand, eventfilter, eventqueue,
3014 var0, var1, scalarx, scalary, rhs, infeasible, &aggregated) );
3015
3016 assert(aggregated || *infeasible);
3017 }
3018 #endif
3019
3020 sameclique = (SCIP_CLIQUE*)SCIPhashtableRetrieve(cliquetable->hashtable, (void*)clique);
3021
3022 /* check if the clique is already contained in the clique table, or if it is redundant (too small) */
3023 if( clique->nvars <= 1 || sameclique != NULL )
3024 {
3025 int j;
3026
3027 /* infeasible or fixing should be performed already on trivial clique */
3028 assert(clique->nvars > 1 || !clique->equation);
3029
3030 /* if the clique which is already in the hashtable is an inequality and the current clique is an equation, we
3031 * update the equation status of the old one
3032 */
3033 if( clique->nvars > 1 && clique->equation && !sameclique->equation )
3034 {
3035 assert(sameclique->nvars >= 2);
3036
3037 /* @note if we might change the order of the clique, e.g. put the equations up front, we should rather remove
3038 * the sameclique from the hashmap while adding the new clique
3039 */
3040 sameclique->equation = TRUE;
3041 }
3042
3043 /* delete the clique from the variables' clique lists */
3044 for( j = 0; j < clique->nvars; ++j )
3045 {
3046 SCIP_CALL( SCIPvarDelCliqueFromList(clique->vars[j], blkmem, clique->values[j], clique) );
3047 }
3048
3049 /* free clique and remove it from clique table */
3050 cliqueFree(&clique, blkmem);
3051 cliquetable->ncliques--;
3052 /* insert a clean clique from the end of the array */
3053 if( cliquetable->ndirtycliques < cliquetable->ncliques )
3054 {
3055 assert(SCIPcliqueIsCleanedUp(cliquetable->cliques[cliquetable->ncliques]));
3056 cliquetable->cliques[cliquetable->ndirtycliques] = cliquetable->cliques[cliquetable->ncliques];
3057 cliquetable->cliques[cliquetable->ndirtycliques]->index = cliquetable->ndirtycliques;
3058 }
3059 }
3060 else
3061 {
3062 cliquetable->nentries += clique->nvars;
3063
3064 SCIP_CALL( SCIPhashtableInsert(cliquetable->hashtable, (void*)clique) );
3065 if( !clique->eventsissued )
3066 {
3067 int j;
3068
3069 /* issue IMPLADDED event on each variable in the clique */
3070 for( j = 0; j < clique->nvars; ++j )
3071 {
3072 SCIP_EVENT* event;
3073
3074 SCIP_CALL( SCIPeventCreateImplAdded(&event, blkmem, clique->vars[j]) );
3075 SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, NULL, &event) );
3076 }
3077 clique->eventsissued = TRUE;
3078 }
3079 }
3080 }
3081 cliquetable->incleanup = FALSE;
3082
3083 /* remember the number of fixed variables and cliques in order to avoid unnecessary cleanups */
3084 cliquetable->ncleanupfixedvars = stat->npresolfixedvars;
3085 cliquetable->ncleanupaggrvars = stat->npresolaggrvars;
3086 assert(*infeasible || cliquetable->ndirtycliques == 0);
3087
3088 assert(*infeasible || checkNEntries(cliquetable)); /*lint !e506*/
3089
3090 SCIPsetDebugMsg(set, "cleaned up clique table has %d cliques left (with %" SCIP_LONGINT_FORMAT " entries)\n", cliquetable->ncliques, cliquetable->nentries);
3091
3092 /* process events */
3093 SCIP_CALL( SCIPeventqueueProcess(eventqueue, blkmem, set, NULL, lp, branchcand, NULL) );
3094
3095 return SCIP_OKAY;
3096 }
3097
3098 /** computes connected components of the clique table
3099 *
3100 * an update becomes necessary if a clique gets added with variables from different components
3101 */
SCIPcliquetableComputeCliqueComponents(SCIP_CLIQUETABLE * cliquetable,SCIP_SET * set,BMS_BLKMEM * blkmem,SCIP_VAR ** vars,int nbinvars,int nintvars,int nimplvars)3102 SCIP_RETCODE SCIPcliquetableComputeCliqueComponents(
3103 SCIP_CLIQUETABLE* cliquetable, /**< clique table data structure */
3104 SCIP_SET* set, /**< global SCIP settings */
3105 BMS_BLKMEM* blkmem, /**< block memory */
3106 SCIP_VAR** vars, /**< array of problem variables, sorted by variable type */
3107 int nbinvars, /**< number of binary variables */
3108 int nintvars, /**< number of integer variables */
3109 int nimplvars /**< number of implicit integer variables */
3110 )
3111 {
3112 SCIP_DISJOINTSET* djset;
3113 int nimplbinvars;
3114 int v;
3115 int c;
3116 int nbinvarstotal;
3117 int ndiscvars;
3118 int nnonbinvars;
3119
3120 SCIP_CLIQUE** cliques;
3121
3122 assert(cliquetable != NULL);
3123 assert(vars != NULL);
3124
3125 nimplbinvars = 0;
3126 cliquetable->compsfromscratch = FALSE;
3127 ndiscvars = nbinvars + nintvars + nimplvars;
3128
3129 /* detect integer and implicit integer variables with bounds {0,1} because they might appear in cliques, as well */
3130 for( v = nbinvars; v < ndiscvars; ++v )
3131 {
3132 if( SCIPvarIsBinary(vars[v]) )
3133 ++nimplbinvars;
3134 }
3135
3136 /* count binary and implicit binary variables */
3137 nbinvarstotal = nbinvars + nimplbinvars;
3138
3139 /* if there are no binary variables, return */
3140 if( nbinvarstotal == 0 )
3141 {
3142 SCIPsetDebugMsg(set, "0 binary variables in total --> 0 connected components in the clique table");
3143 cliquetable->ncliquecomponents = 0;
3144 return SCIP_OKAY;
3145 }
3146
3147 /* no cliques are present */
3148 if( cliquetable->ncliques == 0 )
3149 {
3150 SCIPsetDebugMsg(set, "0 cliques --> Clique table has %d isolated nodes", nbinvarstotal);
3151 cliquetable->ncliquecomponents = nbinvarstotal;
3152 return SCIP_OKAY;
3153 }
3154
3155 /* create or clear the variable index mapping */
3156 if( cliquetable->varidxtable == NULL )
3157 {
3158 SCIP_CALL( SCIPhashmapCreate(&(cliquetable)->varidxtable, blkmem, ndiscvars) );
3159 }
3160 else
3161 {
3162 SCIP_CALL( SCIPhashmapRemoveAll(cliquetable->varidxtable) );
3163 }
3164
3165 /* loop through variables and store their respective positions in the hash map if they are binary */
3166 for( v = 0; v < ndiscvars; ++v )
3167 {
3168 SCIP_VAR* var = vars[v];
3169 if( SCIPvarIsBinary(var) )
3170 {
3171 /* consider only active representatives */
3172 if( SCIPvarIsActive(var) )
3173 {
3174 SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) );
3175 }
3176 else
3177 {
3178 var = SCIPvarGetProbvar(var);
3179 if( SCIPvarIsActive(var) )
3180 {
3181 SCIP_CALL( SCIPhashmapInsertInt(cliquetable->varidxtable, (void*)var, v) );
3182 }
3183 }
3184 }
3185 }
3186
3187 /* free previous disjoint set (union find) data structure which has become outdated if new variables are present */
3188 if( cliquetable->djset != NULL )
3189 SCIPdisjointsetFree(&cliquetable->djset, blkmem);
3190
3191 /* we need to consider integer and implicit integer variables for which SCIPvarIsBinary() returns TRUE.
3192 * These may be scattered across the ninteger + nimplvars implicit integer variables.
3193 * For simplicity, we add all integer and implicit integer variables as nodes to the graph, and subtract
3194 * the amount of nonbinary integer and implicit integer variables afterwards.
3195 */
3196 SCIP_CALL( SCIPdisjointsetCreate(&cliquetable->djset, blkmem, ndiscvars) );
3197 djset = cliquetable->djset;
3198
3199 /* subtract all (implicit) integer for which SCIPvarIsBinary() returns FALSE */
3200 nnonbinvars = (nintvars + nimplvars) - nimplbinvars;
3201
3202 cliques = cliquetable->cliques;
3203
3204 /* for every clique, we connect clique variable components, treating a clique as a path
3205 *
3206 * if the graph turns out to be completely connected (except for the nonbinary variables), we terminate */
3207 for( c = 0; c < cliquetable->ncliques && SCIPdisjointsetGetComponentCount(djset) > 1 + nnonbinvars; ++c )
3208 {
3209 SCIP_CLIQUE* clique;
3210
3211 clique = cliques[c];
3212 cliquetableUpdateConnectednessClique(cliquetable, clique);
3213 }
3214
3215 /* subtract superfluous integer and implicit integer variables added to the auxiliary graph */
3216 cliquetable->ncliquecomponents = SCIPdisjointsetGetComponentCount(djset) - nnonbinvars;
3217 assert(cliquetable->ncliquecomponents >= 0);
3218 assert(cliquetable->ncliquecomponents <= nbinvarstotal);
3219
3220 SCIPsetDebugMsg(set, "connected components detection: %d comps (%d clqs, %d vars)", cliquetable->ncliquecomponents, cliquetable->ncliques, nbinvarstotal);
3221
3222 return SCIP_OKAY;
3223 }
3224
3225 /*
3226 * simple functions implemented as defines
3227 */
3228
3229 /* In debug mode, the following methods are implemented as function calls to ensure
3230 * type validity.
3231 * In optimized mode, the methods are implemented as defines to improve performance.
3232 * However, we want to have them in the library anyways, so we have to undef the defines.
3233 */
3234
3235 #undef SCIPvboundsGetNVbds
3236 #undef SCIPvboundsGetVars
3237 #undef SCIPvboundsGetCoefs
3238 #undef SCIPvboundsGetConstants
3239 #undef SCIPimplicsGetNImpls
3240 #undef SCIPimplicsGetVars
3241 #undef SCIPimplicsGetTypes
3242 #undef SCIPimplicsGetBounds
3243 #undef SCIPimplicsGetIds
3244 #undef SCIPcliqueGetNVars
3245 #undef SCIPcliqueGetVars
3246 #undef SCIPcliqueGetValues
3247 #undef SCIPcliqueGetId
3248 #undef SCIPcliqueGetIndex
3249 #undef SCIPcliqueIsCleanedUp
3250 #undef SCIPcliqueIsEquation
3251 #undef SCIPcliquelistGetNCliques
3252 #undef SCIPcliquelistGetCliques
3253 #undef SCIPcliquelistCheck
3254 #undef SCIPcliquetableGetNCliques
3255 #undef SCIPcliquetableGetCliques
3256 #undef SCIPcliquetableGetNEntries
3257 #undef SCIPcliquetableGetNCliqueComponents
3258 #undef SCIPcliquetableNeedsComponentUpdate
3259
3260 /** gets number of variable bounds contained in given variable bounds data structure */
SCIPvboundsGetNVbds(SCIP_VBOUNDS * vbounds)3261 int SCIPvboundsGetNVbds(
3262 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3263 )
3264 {
3265 return vbounds != NULL ? vbounds->len : 0;
3266 }
3267
3268 /** gets array of variables contained in given variable bounds data structure */
SCIPvboundsGetVars(SCIP_VBOUNDS * vbounds)3269 SCIP_VAR** SCIPvboundsGetVars(
3270 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3271 )
3272 {
3273 return vbounds != NULL ? vbounds->vars : NULL;
3274 }
3275
3276 /** gets array of coefficients contained in given variable bounds data structure */
SCIPvboundsGetCoefs(SCIP_VBOUNDS * vbounds)3277 SCIP_Real* SCIPvboundsGetCoefs(
3278 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3279 )
3280 {
3281 return vbounds != NULL ? vbounds->coefs : NULL;
3282 }
3283
3284 /** gets array of constants contained in given variable bounds data structure */
SCIPvboundsGetConstants(SCIP_VBOUNDS * vbounds)3285 SCIP_Real* SCIPvboundsGetConstants(
3286 SCIP_VBOUNDS* vbounds /**< variable bounds data structure */
3287 )
3288 {
3289 return vbounds != NULL ? vbounds->constants : NULL;
3290 }
3291
3292 /** gets number of implications for a given binary variable fixing */
SCIPimplicsGetNImpls(SCIP_IMPLICS * implics,SCIP_Bool varfixing)3293 int SCIPimplicsGetNImpls(
3294 SCIP_IMPLICS* implics, /**< implication data */
3295 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3296 )
3297 {
3298 return implics != NULL ? implics->nimpls[varfixing] : 0;
3299 }
3300
3301 /** gets array with implied variables for a given binary variable fixing */
SCIPimplicsGetVars(SCIP_IMPLICS * implics,SCIP_Bool varfixing)3302 SCIP_VAR** SCIPimplicsGetVars(
3303 SCIP_IMPLICS* implics, /**< implication data */
3304 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3305 )
3306 {
3307 return implics != NULL ? implics->vars[varfixing] : NULL;
3308 }
3309
3310 /** gets array with implication types for a given binary variable fixing */
SCIPimplicsGetTypes(SCIP_IMPLICS * implics,SCIP_Bool varfixing)3311 SCIP_BOUNDTYPE* SCIPimplicsGetTypes(
3312 SCIP_IMPLICS* implics, /**< implication data */
3313 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3314 )
3315 {
3316 return implics != NULL ? implics->types[varfixing] : NULL;
3317 }
3318
3319 /** gets array with implication bounds for a given binary variable fixing */
SCIPimplicsGetBounds(SCIP_IMPLICS * implics,SCIP_Bool varfixing)3320 SCIP_Real* SCIPimplicsGetBounds(
3321 SCIP_IMPLICS* implics, /**< implication data */
3322 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3323 )
3324 {
3325 return implics != NULL ? implics->bounds[varfixing] : NULL;
3326 }
3327
3328 /** Gets array with unique implication identifiers for a given binary variable fixing.
3329 * If an implication is a shortcut, i.e., it was added as part of the transitive closure of another implication,
3330 * its id is negative, otherwise it is nonnegative.
3331 */
SCIPimplicsGetIds(SCIP_IMPLICS * implics,SCIP_Bool varfixing)3332 int* SCIPimplicsGetIds(
3333 SCIP_IMPLICS* implics, /**< implication data */
3334 SCIP_Bool varfixing /**< should the implications on var == FALSE or var == TRUE be returned? */
3335 )
3336 {
3337 return implics != NULL ? implics->ids[varfixing] : NULL;
3338 }
3339
3340 /** gets number of variables in the cliques */
SCIPcliqueGetNVars(SCIP_CLIQUE * clique)3341 int SCIPcliqueGetNVars(
3342 SCIP_CLIQUE* clique /**< clique data structure */
3343 )
3344 {
3345 assert(clique != NULL);
3346
3347 return clique->nvars;
3348 }
3349
3350 /** gets array of active problem variables in the cliques */
SCIPcliqueGetVars(SCIP_CLIQUE * clique)3351 SCIP_VAR** SCIPcliqueGetVars(
3352 SCIP_CLIQUE* clique /**< clique data structure */
3353 )
3354 {
3355 assert(clique != NULL);
3356
3357 return clique->vars;
3358 }
3359
3360 /** gets array of values of active problem variables in the cliques, i.e. whether the variable is fixed to FALSE or
3361 * to TRUE in the clique
3362 */
SCIPcliqueGetValues(SCIP_CLIQUE * clique)3363 SCIP_Bool* SCIPcliqueGetValues(
3364 SCIP_CLIQUE* clique /**< clique data structure */
3365 )
3366 {
3367 assert(clique != NULL);
3368
3369 return clique->values;
3370 }
3371
3372 /** gets unique identifier of the clique */
SCIPcliqueGetId(SCIP_CLIQUE * clique)3373 unsigned int SCIPcliqueGetId(
3374 SCIP_CLIQUE* clique /**< clique data structure */
3375 )
3376 {
3377 unsigned int id;
3378
3379 assert(clique != NULL);
3380
3381 id = clique->id; /*lint !e732*/
3382
3383 return id;
3384 }
3385
3386 /** gets index of the clique in the clique table */
SCIPcliqueGetIndex(SCIP_CLIQUE * clique)3387 int SCIPcliqueGetIndex(
3388 SCIP_CLIQUE* clique /**< clique data structure */
3389 )
3390 {
3391 assert(clique != NULL);
3392
3393 return clique->index;
3394 }
3395
3396 /** gets unique identifier of the clique */
SCIPcliqueIsCleanedUp(SCIP_CLIQUE * clique)3397 SCIP_Bool SCIPcliqueIsCleanedUp(
3398 SCIP_CLIQUE* clique /**< clique data structure */
3399 )
3400 {
3401 assert(clique != NULL);
3402
3403 return (clique->startcleanup == -1);
3404 }
3405
3406 /** return whether the given clique is an equation */
SCIPcliqueIsEquation(SCIP_CLIQUE * clique)3407 SCIP_Bool SCIPcliqueIsEquation(
3408 SCIP_CLIQUE* clique /**< clique data structure */
3409 )
3410 {
3411 assert(clique != NULL);
3412
3413 return (SCIP_Bool)(clique->equation); /*lint !e571*/
3414 }
3415
3416 /** returns the number of cliques stored in the clique list */
SCIPcliquelistGetNCliques(SCIP_CLIQUELIST * cliquelist,SCIP_Bool value)3417 int SCIPcliquelistGetNCliques(
3418 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3419 SCIP_Bool value /**< value of the variable for which the cliques should be returned */
3420 )
3421 {
3422 return cliquelist != NULL ? cliquelist->ncliques[value] : 0;
3423 }
3424
3425 /** returns the cliques stored in the clique list, or NULL if the clique list is empty */
SCIPcliquelistGetCliques(SCIP_CLIQUELIST * cliquelist,SCIP_Bool value)3426 SCIP_CLIQUE** SCIPcliquelistGetCliques(
3427 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3428 SCIP_Bool value /**< value of the variable for which the cliques should be returned */
3429 )
3430 {
3431 return cliquelist != NULL ? cliquelist->cliques[value] : NULL;
3432 }
3433
3434 /** checks whether variable is contained in all cliques of the cliquelist */
SCIPcliquelistCheck(SCIP_CLIQUELIST * cliquelist,SCIP_VAR * var)3435 void SCIPcliquelistCheck(
3436 SCIP_CLIQUELIST* cliquelist, /**< clique list data structure */
3437 SCIP_VAR* var /**< variable, the clique list belongs to */
3438 )
3439 {
3440 /* @todo might need to change ifndef NDEBUG to ifdef SCIP_MORE_DEBUG because it can take at lot of time to check for
3441 * correctness
3442 */
3443 #ifndef NDEBUG
3444 int value;
3445
3446 assert(SCIPvarGetNCliques(var, FALSE) == SCIPcliquelistGetNCliques(cliquelist, FALSE));
3447 assert(SCIPvarGetCliques(var, FALSE) == SCIPcliquelistGetCliques(cliquelist, FALSE));
3448 assert(SCIPvarGetNCliques(var, TRUE) == SCIPcliquelistGetNCliques(cliquelist, TRUE));
3449 assert(SCIPvarGetCliques(var, TRUE) == SCIPcliquelistGetCliques(cliquelist, TRUE));
3450
3451 for( value = 0; value < 2; ++value )
3452 {
3453 SCIP_CLIQUE** cliques;
3454 int ncliques;
3455 int i;
3456
3457 ncliques = SCIPcliquelistGetNCliques(cliquelist, (SCIP_Bool)value);
3458 cliques = SCIPcliquelistGetCliques(cliquelist, (SCIP_Bool)value);
3459 for( i = 0; i < ncliques; ++i )
3460 {
3461 SCIP_CLIQUE* clique;
3462 int pos;
3463
3464 clique = cliques[i];
3465 assert(clique != NULL);
3466
3467 pos = SCIPcliqueSearchVar(clique, var, (SCIP_Bool)value);
3468 assert(0 <= pos && pos < clique->nvars);
3469 assert(clique->vars[pos] == var);
3470 assert(clique->values[pos] == (SCIP_Bool)value);
3471 }
3472 }
3473 #endif
3474 }
3475
3476 /** gets the number of cliques stored in the clique table */
SCIPcliquetableGetNCliques(SCIP_CLIQUETABLE * cliquetable)3477 int SCIPcliquetableGetNCliques(
3478 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3479 )
3480 {
3481 assert(cliquetable != NULL);
3482
3483 return cliquetable->ncliques;
3484 }
3485
3486 /** gets the number of cliques created so far by the clique table */
SCIPcliquetableGetNCliquesCreated(SCIP_CLIQUETABLE * cliquetable)3487 int SCIPcliquetableGetNCliquesCreated(
3488 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3489 )
3490 {
3491 assert(cliquetable != NULL);
3492
3493 return cliquetable->ncreatedcliques;
3494 }
3495
3496 /** gets the array of cliques stored in the clique table */
SCIPcliquetableGetCliques(SCIP_CLIQUETABLE * cliquetable)3497 SCIP_CLIQUE** SCIPcliquetableGetCliques(
3498 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3499 )
3500 {
3501 assert(cliquetable != NULL);
3502
3503 return cliquetable->cliques;
3504 }
3505
3506 /** gets the number of entries in the whole clique table */
SCIPcliquetableGetNEntries(SCIP_CLIQUETABLE * cliquetable)3507 SCIP_Longint SCIPcliquetableGetNEntries(
3508 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3509 )
3510 {
3511 assert(cliquetable != NULL);
3512
3513 return cliquetable->nentries;
3514 }
3515
3516 /** returns the number of clique components, or -1 if update is necessary first */
SCIPcliquetableGetNCliqueComponents(SCIP_CLIQUETABLE * cliquetable)3517 int SCIPcliquetableGetNCliqueComponents(
3518 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3519 )
3520 {
3521 return cliquetable->compsfromscratch ? -1 : cliquetable->ncliquecomponents;
3522 }
3523
3524 /** returns TRUE iff the connected clique components need an update (because new cliques were added) */
SCIPcliquetableNeedsComponentUpdate(SCIP_CLIQUETABLE * cliquetable)3525 SCIP_Bool SCIPcliquetableNeedsComponentUpdate(
3526 SCIP_CLIQUETABLE* cliquetable /**< clique table data structure */
3527 )
3528 {
3529 return cliquetable->compsfromscratch || cliquetable->djset == NULL;
3530 }
3531