Scippy

SCIP

Solving Constraint Integer Programs

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