Scippy

SCIP

Solving Constraint Integer Programs

conflictstore.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-2021 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file conflictstore.c
17  * @ingroup OTHER_CFILES
18  * @brief methods for storing conflicts
19  * @author Jakob Witzig
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include <assert.h>
25 #include <string.h>
26 
27 #include "scip/conflictstore.h"
28 #include "scip/cons.h"
29 #include "scip/event.h"
30 #include "scip/set.h"
31 #include "scip/tree.h"
32 #include "scip/misc.h"
33 #include "scip/prob.h"
34 #include "scip/reopt.h"
35 #include "scip/scip.h"
36 #include "scip/def.h"
37 #include "scip/cons_linear.h"
39 
40 
41 #define CONFLICTSTORE_DUALRAYSIZE 100 /* default size of conflict store */
42 #define CONFLICTSTORE_DUALSOLSIZE 75 /* default size of conflict store */
43 #define CONFLICTSTORE_MINSIZE 2000 /* default minimal size of a dynamic conflict store */
44 #define CONFLICTSTORE_MAXSIZE 60000 /* maximal size of a dynamic conflict store (multiplied by 3) */
45 #define CONFLICTSTORE_SIZE 10000 /* default size of conflict store */
46 #define CONFLICTSTORE_SORTFREQ 20 /* frequency to resort the conflict array */
47 
48 /* event handler properties */
49 #define EVENTHDLR_NAME "ConflictStore"
50 #define EVENTHDLR_DESC "Solution event handler for conflict store."
51 
52 
53 /* exec the event handler */
54 static
55 SCIP_DECL_EVENTEXEC(eventExecConflictstore)
56 {/*lint --e{715}*/
57  assert(eventhdlr != NULL);
58  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
59  assert(event != NULL);
61 
63  {
65  }
66 
67  return SCIP_OKAY;
68 }
69 
70 /** solving process initialization method of event handler (called when branch and bound process is about to begin) */
71 static
72 SCIP_DECL_EVENTINITSOL(eventInitsolConflictstore)
73 {
74  SCIP_Bool cleanboundexceeding;
75 
76  assert(scip != NULL);
77  assert(eventhdlr != NULL);
78  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
79 
80  SCIP_CALL( SCIPgetBoolParam(scip, "conflict/cleanboundexceedings", &cleanboundexceeding) );
81 
82  if( !cleanboundexceeding )
83  return SCIP_OKAY;
84 
86 
87  return SCIP_OKAY;
88 }
89 
90 /** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
91 static
92 SCIP_DECL_EVENTEXITSOL(eventExitsolConflictstore)
93 {
94  SCIP_Bool cleanboundexceeding;
95 
96  assert(scip != NULL);
97  assert(eventhdlr != NULL);
98  assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
99 
100  SCIP_CALL( SCIPgetBoolParam(scip, "conflict/cleanboundexceedings", &cleanboundexceeding) );
101 
102  if( !cleanboundexceeding )
103  return SCIP_OKAY;
104 
106 
107  return SCIP_OKAY;
108 }
109 
110 /* comparison method for constraints */
111 static
113 {
114  /*lint --e{715}*/
115  SCIP_CONS* cons1 = (SCIP_CONS*)elem1;
116  SCIP_CONS* cons2 = (SCIP_CONS*)elem2;
117 
118  assert(cons1 != NULL);
119  assert(cons2 != NULL);
120 
121  if( SCIPconsGetAge(cons1) > SCIPconsGetAge(cons2) + 1e-09 )
122  return -1;
123  else if ( SCIPconsGetAge(cons1) < SCIPconsGetAge(cons2) - 1e-09 )
124  return +1;
125  else
126 #ifdef SCIP_DISABLED_CODE
127  /* @todo if both constraints have the same age we prefere the constraint with more non-zeros
128  * this requires a larges change of the callback, passing void-pointer (i.e. a scip
129  * object) would necessary.
130  */
131  {
132  SCIP_Bool success;
133  int nvars1;
134  int nvars2;
135 
136  SCIP_CALL( SCIPgetConsNVars(scip, cons1, &nvars1, &success) );
137  assert(success);
138 
139  SCIP_CALL( SCIPgetConsNVars(scip, cons2, &nvars2, &success) );
140  assert(success);
141 
142  if( nvars1 >= nvars2 )
143  return -1;
144  else
145  return +1;
146  }
147 #else
148  {
149  SCIP_CONSHDLR* conshdlr1 = SCIPconsGetHdlr(cons1);
150  SCIP_CONSHDLR* conshdlr2 = SCIPconsGetHdlr(cons2);
151 
152  if( strcmp(SCIPconshdlrGetName(conshdlr1), "linear") == strcmp(SCIPconshdlrGetName(conshdlr2), "linear") )
153  return 0;
154  else if( strcmp(SCIPconshdlrGetName(conshdlr1), "linear") == 0 )
155  return -1;
156  else
157  return +1;
158  }
159 #endif
160 }
161 
162 /* initializes the conflict store */
163 static
165  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
166  SCIP_SET* set, /**< global SCIP settings */
167  SCIP_PROB* transprob /**< transformed problem */
168  )
169 {
170  assert(conflictstore != NULL);
171 
172  /* calculate the maximal size of the conflict store */
173  if( conflictstore->maxstoresize == -1 )
174  {
175  SCIP_CALL( SCIPsetGetIntParam(set, "conflict/maxstoresize", &conflictstore->maxstoresize) );
176 
177  /* the size should be dynamic wrt number of variables after presolving */
178  if( conflictstore->maxstoresize == -1 )
179  {
180  int nconss;
181  int nvars;
182 
183  nconss = SCIPprobGetNConss(transprob);
184  nvars = SCIPprobGetNVars(transprob);
185 
186  conflictstore->initstoresize = CONFLICTSTORE_MINSIZE;
187  conflictstore->initstoresize += 2*nconss;
188 
189  if( nvars/2 <= 500 )
190  conflictstore->initstoresize += (int) CONFLICTSTORE_MAXSIZE/100;
191  else if( nvars/2 <= 5000 )
192  conflictstore->initstoresize += (int) CONFLICTSTORE_MAXSIZE/10;
193  else
194  conflictstore->initstoresize += CONFLICTSTORE_MAXSIZE/2;
195 
196  conflictstore->initstoresize = MIN(conflictstore->initstoresize, CONFLICTSTORE_MAXSIZE);
197  conflictstore->storesize = conflictstore->initstoresize;
198  conflictstore->maxstoresize = (int)(MIN(3.0 * conflictstore->initstoresize, CONFLICTSTORE_MAXSIZE));
199  }
200  else
201  {
202  conflictstore->initstoresize = conflictstore->maxstoresize;
203  conflictstore->storesize = conflictstore->maxstoresize;
204  }
205 
206 #ifdef NDEBUG
207  if( conflictstore->maxstoresize == 0 )
208  SCIPsetDebugMsg(set, "usage of conflict pool is disabled.\n");
209  else
210  SCIPsetDebugMsg(set, "[init,max] size of conflict pool is [%d,%d].\n",
211  conflictstore->initstoresize, conflictstore->maxstoresize);
212 #endif
213  }
214 
215  return SCIP_OKAY;
216 }
217 
218 /** resizes conflict and primal bound arrays to be able to store at least num entries */
219 static
221  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
222  SCIP_SET* set, /**< global SCIP settings */
223  BMS_BLKMEM* blkmem, /**< block memory */
224  int num /**< minimal number of slots in array */
225  )
226 {
227  assert(conflictstore != NULL);
228  assert(set != NULL);
229 
230  /* we do not allocate more memory as allowed */
231  if( conflictstore->conflictsize == conflictstore->maxstoresize )
232  return SCIP_OKAY;
233 
234  if( num > conflictstore->conflictsize )
235  {
236  int newsize;
237 #ifndef NDEBUG
238  int i;
239 #endif
240  /* initialize the complete data structure */
241  if( conflictstore->conflictsize == 0 )
242  {
243  assert(conflictstore->storesize > 0);
244 
245  newsize = MIN(conflictstore->storesize, CONFLICTSTORE_SIZE);
246  newsize = MAX(newsize, num);
247  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->conflicts, newsize) );
248  SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->confprimalbnds, newsize) );
249  }
250  else
251  {
252  newsize = SCIPsetCalcMemGrowSize(set, num);
253  newsize = MIN(conflictstore->maxstoresize, newsize);
254  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->conflicts, conflictstore->conflictsize, \
255  newsize) );
256  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->confprimalbnds, conflictstore->conflictsize, \
257  newsize) );
258  }
259 
260 #ifndef NDEBUG
261  for( i = conflictstore->nconflicts; i < newsize; i++ )
262  {
263  conflictstore->conflicts[i] = NULL;
264  conflictstore->confprimalbnds[i] = -SCIPsetInfinity(set);
265  }
266 #endif
267  conflictstore->conflictsize = newsize;
268  }
269  assert(num <= conflictstore->conflictsize || conflictstore->conflictsize == conflictstore->maxstoresize);
270 
271  return SCIP_OKAY;
272 }
273 
274 /* increase the dynamic storage if we could not delete enough conflicts
275  *
276  * we want to have at least set->conf_maxconss free slots in the conflict array, because this is the maximal number
277  * of conflicts generated at a node. we increase the size by the minimum of set->conf_maxconss and 1% of the current
278  * store size. nevertheless, we don't exceed conflictstore->maxstoresize.
279  */
280 static
282  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
283  SCIP_SET* set /**< global SCIP settings */
284  )
285 {
286  assert(conflictstore != NULL);
287 
288  /* increase storage */
289  if( conflictstore->storesize - conflictstore->nconflicts <= set->conf_maxconss
290  && conflictstore->storesize < conflictstore->maxstoresize )
291  {
292  SCIP_Real increase = ceil(0.01 * conflictstore->storesize);
293  conflictstore->storesize += MIN(set->conf_maxconss, (int)(increase));
294  conflictstore->storesize = MIN(conflictstore->storesize, conflictstore->maxstoresize);
295  }
296 
297  return;
298 }
299 
300 /* removes conflict at position pos */
301 static
303  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
304  SCIP_SET* set, /**< global SCIP settings */
305  SCIP_STAT* stat, /**< dynamic SCIP statistics */
306  SCIP_PROB* transprob, /**< transformed problem, or NULL if delete = FALSE */
307  BMS_BLKMEM* blkmem, /**< block memory */
308  SCIP_REOPT* reopt, /**< reoptimization data */
309  int pos, /**< position to remove */
310  SCIP_Bool deleteconflict /**< should the conflict be deleted? */
311  )
312 {
313  SCIP_CONS* conflict;
314  int lastpos;
315 
316  assert(conflictstore != NULL);
317  assert(pos >= 0 && pos < conflictstore->nconflicts);
318 
319  lastpos = conflictstore->nconflicts-1;
320  conflict = conflictstore->conflicts[pos];
321  assert(conflict != NULL);
322 
323  /* decrease number of conflicts depending an a cutoff bound */
324  conflictstore->ncbconflicts -= (SCIPsetIsInfinity(set, REALABS(conflictstore->confprimalbnds[pos])) ? 0 : 1);
325 
326 #ifdef SCIP_PRINT_DETAILS
327  SCIPsetDebugMsg(set, "-> remove conflict <%s> at pos=%d with age=%g\n", SCIPconsGetName(conflict), pos, SCIPconsGetAge(conflict));
328 #endif
329 
330  /* remove conflict locks */
331  SCIP_CALL( SCIPconsAddLocks(conflict, set, SCIP_LOCKTYPE_CONFLICT, -1, 0) );
332 
333  /* mark the constraint as deleted */
334  if( deleteconflict && !SCIPconsIsDeleted(conflict) )
335  {
336  assert(transprob != NULL);
337  SCIP_CALL( SCIPconsDelete(conflictstore->conflicts[pos], blkmem, set, stat, transprob, reopt) );
338  }
339  SCIP_CALL( SCIPconsRelease(&conflictstore->conflicts[pos], blkmem, set) );
340 
341  /* replace with conflict at the last position */
342  if( pos < lastpos )
343  {
344  conflictstore->conflicts[pos] = conflictstore->conflicts[lastpos];
345  conflictstore->confprimalbnds[pos] = conflictstore->confprimalbnds[lastpos];
346  }
347 
348 #ifndef NDEBUG
349  conflictstore->conflicts[lastpos] = NULL;
350  conflictstore->confprimalbnds[lastpos] = -SCIPsetInfinity(set);
351 #endif
352 
353  /* decrease number of conflicts */
354  --conflictstore->nconflicts;
355 
356  return SCIP_OKAY;
357 }
358 
359 /* removes proof based on a dual ray at position pos */
360 static
362  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
363  SCIP_SET* set, /**< global SCIP settings */
364  SCIP_STAT* stat, /**< dynamic SCIP statistics */
365  SCIP_PROB* transprob, /**< transformed problem, or NULL if delete = FALSE */
366  BMS_BLKMEM* blkmem, /**< block memory */
367  SCIP_REOPT* reopt, /**< reoptimization data */
368  int pos, /**< position to remove */
369  SCIP_Bool deleteconflict /**< should the dual ray be deleted? */
370  )
371 {
372  SCIP_CONS* dualproof;
373  SCIP_Bool success;
374  int lastpos;
375  int nvars;
376 
377  assert(conflictstore != NULL);
378 
379  lastpos = conflictstore->ndualrayconfs-1;
380  dualproof = conflictstore->dualrayconfs[pos];
381  assert(dualproof != NULL);
382 
383  /* decrease the number of non-zeros */
384  SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) );
385  assert(success);
386  conflictstore->nnzdualrays -= nvars;
387 
388 #ifdef SCIP_PRINT_DETAILS
389  SCIPsetDebugMsg(set, "-> remove dual proof (ray) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars);
390 #endif
391 
392  /* remove conflict locks */
393  SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, -1, 0) );
394 
395  /* mark the constraint as deleted */
396  if( deleteconflict && !SCIPconsIsDeleted(dualproof) )
397  {
398  assert(transprob != NULL);
399  SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) );
400  }
401  SCIP_CALL( SCIPconsRelease(&dualproof, blkmem, set) );
402 
403  /* replace with dual ray at the last position */
404  if( pos < lastpos )
405  {
406  conflictstore->dualrayconfs[pos] = conflictstore->dualrayconfs[lastpos];
407  conflictstore->drayrelaxonly[pos] = conflictstore->drayrelaxonly[lastpos];
408 
409 #ifndef NDEBUG
410  conflictstore->dualrayconfs[lastpos] = NULL;
411  conflictstore->drayrelaxonly[lastpos] = TRUE;
412 #endif
413  }
414 
415  /* decrease number of dual rays */
416  --conflictstore->ndualrayconfs;
417 
418  return SCIP_OKAY;
419 }
420 
421 /* removes proof based on a dual solution at position pos */
422 static
424  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
425  SCIP_SET* set, /**< global SCIP settings */
426  SCIP_STAT* stat, /**< dynamic SCIP statistics */
427  SCIP_PROB* transprob, /**< transformed problem, or NULL if delete = FALSE */
428  BMS_BLKMEM* blkmem, /**< block memory */
429  SCIP_REOPT* reopt, /**< reoptimization data */
430  int pos, /**< position to remove */
431  SCIP_Bool deleteconflict /**< should the dual ray be deleted? */
432  )
433 {
434  SCIP_CONS* dualproof;
435  SCIP_Bool success;
436  int lastpos;
437  int nvars;
438 
439  assert(conflictstore != NULL);
440  assert(pos >= 0 && pos < conflictstore->ndualsolconfs);
441 
442  lastpos = conflictstore->ndualsolconfs-1;
443  dualproof = conflictstore->dualsolconfs[pos];
444  assert(dualproof != NULL);
445 
446  /* decrease the number of non-zeros */
447  SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) );
448  assert(success);
449  conflictstore->nnzdualsols -= nvars;
450 
451 #ifdef SCIP_PRINT_DETAILS
452  SCIPsetDebugMsg(set, "-> remove dual proof (sol) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars);
453 #endif
454 
455  /* remove conflict locks */
456  SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, -1, 0) );
457 
458  /* mark the constraint as deleted */
459  if( deleteconflict && !SCIPconsIsDeleted(dualproof) )
460  {
461  assert(transprob != NULL);
462  SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) );
463  }
464  SCIP_CALL( SCIPconsRelease(&dualproof, blkmem, set) );
465 
466  /* replace with dual ray at the last position */
467  if( pos < lastpos )
468  {
469  conflictstore->dualsolconfs[pos] = conflictstore->dualsolconfs[lastpos];
470  conflictstore->dualprimalbnds[pos] = conflictstore->dualprimalbnds[lastpos];
471  conflictstore->scalefactors[pos] = conflictstore->scalefactors[lastpos];
472  conflictstore->updateside[pos] = conflictstore->updateside[lastpos];
473  conflictstore->dsolrelaxonly[pos] = conflictstore->dsolrelaxonly[lastpos];
474 
475 #ifndef NDEBUG
476  conflictstore->dualsolconfs[lastpos] = NULL;
477  conflictstore->dualprimalbnds[lastpos] = SCIP_UNKNOWN;
478  conflictstore->scalefactors[lastpos] = 1.0;
479  conflictstore->updateside[lastpos] = FALSE;
480  conflictstore->dsolrelaxonly[lastpos] = TRUE;
481 #endif
482  }
483 
484  /* decrease number of dual rays */
485  --conflictstore->ndualsolconfs;
486 
487  return SCIP_OKAY;
488 }
489 
490 /** removes all deleted conflicts from the storage */
491 static
493  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
494  SCIP_SET* set, /**< global SCIP settings */
495  SCIP_STAT* stat, /**< dynamic SCIP statistics */
496  BMS_BLKMEM* blkmem, /**< block memory */
497  SCIP_REOPT* reopt, /**< reoptimization data */
498  int* ndelconfs /**< pointer to store the number of deleted conflicts */
499  )
500 {
501  int i;
502 
503  assert(conflictstore != NULL);
504 
505  (*ndelconfs) = 0;
506 
507  /* we traverse backwards to avoid swapping of pointers */
508  for( i = conflictstore->nconflicts-1; i >= 0; i-- )
509  {
510  assert(conflictstore->conflicts[i] != NULL);
511 
512  /* check whether the constraint is already marked as deleted */
513  if( SCIPconsIsDeleted(conflictstore->conflicts[i]) || SCIPconsIsChecked(conflictstore->conflicts[i]) )
514  {
515  /* remove conflict at current position */
516  SCIP_CALL( delPosConflict(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
517 
518  ++(*ndelconfs);
519  }
520  }
521  SCIPsetDebugMsg(set, "> removed %d/%d as deleted marked conflicts.\n", *ndelconfs, conflictstore->nconflicts + (*ndelconfs));
522 
523  return SCIP_OKAY;
524 }
525 
526 /** removes all deleted dual proofs of infeasible LP relaxations from the storage */
527 static
529  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
530  SCIP_SET* set, /**< global SCIP settings */
531  SCIP_STAT* stat, /**< dynamic SCIP statistics */
532  BMS_BLKMEM* blkmem, /**< block memory */
533  SCIP_REOPT* reopt, /**< reoptimization data */
534  int* ndelproofs /**< pointer to store the number of deleted conflicts */
535  )
536 {
537  int i;
538 
539  assert(conflictstore != NULL);
540 
541  (*ndelproofs) = 0;
542 
543  /* we traverse backwards to avoid swapping of pointers */
544  for( i = conflictstore->ndualrayconfs-1; i >= 0; i-- )
545  {
546  assert(conflictstore->dualrayconfs[i] != NULL);
547 
548  /* check whether the constraint is already marked as deleted */
549  if( SCIPconsIsDeleted(conflictstore->dualrayconfs[i]) || SCIPconsIsChecked(conflictstore->dualrayconfs[i]) )
550  {
551  /* remove proof at current position */
552  SCIP_CALL( delPosDualray(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
553 
554  ++(*ndelproofs);
555  }
556  }
557 
558  SCIPsetDebugMsg(set, "> removed %d/%d as deleted marked dual infeasibility proofs.\n",
559  *ndelproofs, conflictstore->ndualrayconfs + (*ndelproofs));
560 
561  return SCIP_OKAY;
562 }
563 
564 /** removes all deleted dual proofs of bound exceeding LP relaxations from the storage */
565 static
567  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
568  SCIP_SET* set, /**< global SCIP settings */
569  SCIP_STAT* stat, /**< dynamic SCIP statistics */
570  BMS_BLKMEM* blkmem, /**< block memory */
571  SCIP_REOPT* reopt, /**< reoptimization data */
572  int* ndelproofs /**< pointer to store the number of deleted conflicts */
573  )
574 {
575  int i;
576 
577  assert(conflictstore != NULL);
578 
579  (*ndelproofs) = 0;
580 
581  /* we traverse backwards to avoid swapping of pointers */
582  for( i = conflictstore->ndualsolconfs-1; i >= 0; i-- )
583  {
584  assert(conflictstore->dualsolconfs[i] != NULL);
585 
586  /* check whether the constraint is already marked as deleted */
587  if( SCIPconsIsDeleted(conflictstore->dualsolconfs[i]) || SCIPconsIsChecked(conflictstore->dualsolconfs[i]) )
588  {
589  /* remove proof at current position */
590  SCIP_CALL( delPosDualsol(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
591 
592  ++(*ndelproofs);
593  }
594  }
595 
596  SCIPsetDebugMsg(set, "> removed %d/%d as deleted marked dual boundexceeding proofs.\n",
597  *ndelproofs, conflictstore->ndualrayconfs + (*ndelproofs));
598 
599  return SCIP_OKAY;
600 }
601 
602 /** cleans up the storage */
603 static
605  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
606  SCIP_SET* set, /**< global SCIP settings */
607  SCIP_STAT* stat, /**< dynamic SCIP statistics */
608  SCIP_PROB* transprob, /**< transformed problem */
609  BMS_BLKMEM* blkmem, /**< block memory */
610  SCIP_REOPT* reopt /**< reoptimization data */
611  )
612 {
613  int ndelconfs;
614 
615  assert(conflictstore != NULL);
616  assert(blkmem != NULL);
617  assert(set != NULL);
618  assert(stat != NULL);
619  assert(transprob != NULL);
620 
621  /* the storage is empty */
622  if( conflictstore->nconflicts == 0 )
623  return SCIP_OKAY;
624  assert(conflictstore->nconflicts >= 1);
625 
626  ndelconfs = 0;
627 
628  /* remove all as deleted marked conflicts */
629  SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) );
630 
631  /* return if at least one conflict could be deleted */
632  if( ndelconfs > 0 )
633  goto TERMINATE;
634 
635  /* only clean up the storage if it is filled enough */
636  if( conflictstore->nconflicts < conflictstore->conflictsize )
637  goto TERMINATE;
638 
639  /* resort the array regularly */
640  if( conflictstore->ncleanups % CONFLICTSTORE_SORTFREQ == 0 )
641  {
642  /* sort conflict */
643  SCIPsortPtrReal((void**)conflictstore->conflicts, conflictstore->confprimalbnds, compareConss, conflictstore->nconflicts);
644  assert(SCIPsetIsGE(set, SCIPconsGetAge(conflictstore->conflicts[0]),
645  SCIPconsGetAge(conflictstore->conflicts[conflictstore->nconflicts-1])));
646  }
647  assert(conflictstore->nconflicts > 0);
648 
649  if( conflictstore->ncleanups % CONFLICTSTORE_SORTFREQ == 0 )
650  {
651  /* remove conflict at first position (array is sorted) */
652  SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, 0, TRUE) );
653  }
654  else
655  {
656  SCIP_Real maxage;
657  int oldest_i;
658  int i;
659 
660  assert(!SCIPconsIsDeleted(conflictstore->conflicts[0]));
661 
662  maxage = SCIPconsGetAge(conflictstore->conflicts[0]);
663  oldest_i = 0;
664 
665  /* check the first 10% of conflicts and find the oldest */
666  for( i = 1; i < 0.1 * conflictstore->nconflicts; i++ )
667  {
668  assert(!SCIPconsIsDeleted(conflictstore->conflicts[i]));
669 
670  if( SCIPconsGetAge(conflictstore->conflicts[i]) > maxage )
671  {
672  maxage = SCIPconsGetAge(conflictstore->conflicts[i]);
673  oldest_i = i;
674  }
675  }
676 
677  /* remove conflict at position oldest_i */
678  SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, oldest_i, TRUE) );
679  }
680  ++ndelconfs;
681 
682  /* adjust size of the storage if we use a dynamic store */
683  if( set->conf_maxstoresize == -1 )
684  adjustStorageSize(conflictstore, set);
685  assert(conflictstore->initstoresize <= conflictstore->storesize);
686  assert(conflictstore->storesize <= conflictstore->maxstoresize);
687 
688  TERMINATE:
689 
690  /* increase the number of clean ups */
691  ++conflictstore->ncleanups;
692 
693  SCIPsetDebugMsg(set, "clean-up #%lld: removed %d/%d conflicts, %d depending on cutoff bound\n",
694  conflictstore->ncleanups, ndelconfs, conflictstore->nconflicts+ndelconfs, conflictstore->ncbconflicts);
695 
696  return SCIP_OKAY; /*lint !e438*/
697 }
698 
699 /** adds an original conflict constraint to the store
700  *
701  * @note the constraint will be only transfered to the storage of the transformed problem after calling
702  * SCIPconflictstoreTransform()
703  */
704 static
706  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
707  SCIP_SET* set, /**< global SCIP settings */
708  BMS_BLKMEM* blkmem, /**< block memory */
709  SCIP_CONS* cons /**< conflict constraint */
710  )
711 {
712  assert(conflictstore != NULL);
713  assert(cons != NULL);
714 
715  if( conflictstore->origconfs == NULL )
716  {
718  conflictstore->origconflictsize = CONFLICTSTORE_MINSIZE;
719  }
720  else if( conflictstore->norigconfs == conflictstore->origconflictsize )
721  {
722  int newsize = SCIPsetCalcMemGrowSize(set, conflictstore->origconflictsize+1);
723  SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->origconfs, conflictstore->origconflictsize, newsize) );
724  conflictstore->origconflictsize = newsize;
725  }
726 
727  SCIPconsCapture(cons);
728  conflictstore->origconfs[conflictstore->norigconfs] = cons;
729  ++conflictstore->norigconfs;
730 
731  return SCIP_OKAY;
732 }
733 
734 
735 /** creates conflict store */
737  SCIP_CONFLICTSTORE** conflictstore, /**< pointer to store conflict store */
738  SCIP_SET* set /**< global SCIP settings */
739  )
740 {
741  assert(conflictstore != NULL);
742 
743  SCIP_ALLOC( BMSallocMemory(conflictstore) );
744 
745  (*conflictstore)->conflicts = NULL;
746  (*conflictstore)->confprimalbnds = NULL;
747  (*conflictstore)->dualprimalbnds = NULL;
748  (*conflictstore)->scalefactors = NULL;
749  (*conflictstore)->updateside = NULL;
750  (*conflictstore)->drayrelaxonly = NULL;
751  (*conflictstore)->dsolrelaxonly = NULL;
752  (*conflictstore)->dualrayconfs = NULL;
753  (*conflictstore)->dualsolconfs = NULL;
754  (*conflictstore)->origconfs = NULL;
755  (*conflictstore)->nnzdualrays = 0;
756  (*conflictstore)->nnzdualsols = 0;
757  (*conflictstore)->conflictsize = 0;
758  (*conflictstore)->origconflictsize = 0;
759  (*conflictstore)->nconflicts = 0;
760  (*conflictstore)->ndualrayconfs = 0;
761  (*conflictstore)->ndualsolconfs = 0;
762  (*conflictstore)->norigconfs = 0;
763  (*conflictstore)->ncbconflicts = 0;
764  (*conflictstore)->nconflictsfound = 0;
765  (*conflictstore)->initstoresize = -1;
766  (*conflictstore)->storesize = -1;
767  (*conflictstore)->maxstoresize = -1;
768  (*conflictstore)->ncleanups = 0;
769  (*conflictstore)->lastcutoffbound = SCIP_INVALID;
770  (*conflictstore)->lastnodenum = -1;
771  (*conflictstore)->eventhdlr = SCIPsetFindEventhdlr(set, EVENTHDLR_NAME);
772 
773  /* create event handler for LP events */
774  if( (*conflictstore)->eventhdlr == NULL )
775  {
776  SCIP_CALL( SCIPeventhdlrCreate(&(*conflictstore)->eventhdlr, set, EVENTHDLR_NAME, EVENTHDLR_DESC, NULL, NULL,
777  NULL, NULL, eventInitsolConflictstore, eventExitsolConflictstore, NULL, eventExecConflictstore, NULL) );
778  SCIP_CALL( SCIPsetIncludeEventhdlr(set, (*conflictstore)->eventhdlr) );
779  }
780  assert((*conflictstore)->eventhdlr != NULL);
781 
782  return SCIP_OKAY;
783 }
784 
785 /** frees conflict store */
787  SCIP_CONFLICTSTORE** conflictstore, /**< pointer to store conflict store */
788  BMS_BLKMEM* blkmem, /**< block memory */
789  SCIP_SET* set, /**< global SCIP settings */
790  SCIP_STAT* stat, /**< dynamic SCIP statistics */
791  SCIP_REOPT* reopt /**< reoptimization data */
792  )
793 {
794  assert(conflictstore != NULL);
795  assert(*conflictstore != NULL);
796 
797  /* clear the storage */
798  SCIP_CALL( SCIPconflictstoreClear(*conflictstore, blkmem, set, stat, reopt) );
799 
800  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->origconfs, (*conflictstore)->origconflictsize);
801  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->conflicts, (*conflictstore)->conflictsize);
802  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->confprimalbnds, (*conflictstore)->conflictsize);
803  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE);
804  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->drayrelaxonly, CONFLICTSTORE_DUALRAYSIZE);
805  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE);
806  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE);
807  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->scalefactors, CONFLICTSTORE_DUALSOLSIZE);
808  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->updateside, CONFLICTSTORE_DUALSOLSIZE);
809  BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dsolrelaxonly, CONFLICTSTORE_DUALSOLSIZE);
810  BMSfreeMemoryNull(conflictstore);
811 
812  return SCIP_OKAY;
813 }
814 
815 /** clears conflict store */
817  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
818  BMS_BLKMEM* blkmem, /**< block memory */
819  SCIP_SET* set, /**< global SCIP settings */
820  SCIP_STAT* stat, /**< dynamic SCIP statistics */
821  SCIP_REOPT* reopt /**< reoptimization data */
822  )
823 {
824  int i;
825 
826  assert(conflictstore != NULL);
827 
828  SCIPsetDebugMsg(set, "clearing conflict store: %d origconfs, %d conflicts, %d dual proofs\n",
829  conflictstore->norigconfs, conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs);
830 
831  /* remove original constraints (if present) */
832  if( conflictstore->origconfs != NULL )
833  {
834  for( i = 0; i < conflictstore->norigconfs; i++ )
835  {
836  SCIP_CONS* conflict = conflictstore->origconfs[i];
837  SCIP_CALL( SCIPconsRelease(&conflict, blkmem, set) );
838  }
839  conflictstore->norigconfs = 0;
840  }
841 
842  /* clean up storage of conflict constraints */
843  if( conflictstore->conflicts != NULL )
844  {
845  /* we traverse in reverse order to avoid swapping of pointers */
846  for( i = conflictstore->nconflicts-1; i >= 0; i--)
847  {
848  SCIP_CALL( delPosConflict(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
849  }
850  assert(conflictstore->nconflicts == 0);
851  }
852 
853  /* clean up storage of proof constraints based on dual rays */
854  if( conflictstore->dualrayconfs != NULL )
855  {
856  /* we traverse in reverse order to avoid swapping of pointers */
857  for( i = conflictstore->ndualrayconfs-1; i >= 0; i-- )
858  {
859  SCIP_CALL( delPosDualray(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
860  }
861  assert(conflictstore->ndualrayconfs == 0);
862  }
863 
864  /* clean up storage of proof constraints based on dual solutions */
865  if( conflictstore->dualsolconfs != NULL )
866  {
867  /* we traverse in reverse order to avoid swapping of pointers */
868  for( i = conflictstore->ndualsolconfs-1; i >= 0; i-- )
869  {
870  SCIP_CALL( delPosDualsol(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
871  }
872  assert(conflictstore->ndualsolconfs == 0);
873  }
874 
875  return SCIP_OKAY;
876 }
877 
878 /** cleans up conflict store */
880  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
881  BMS_BLKMEM* blkmem, /**< block memory */
882  SCIP_SET* set, /**< global SCIP settings */
883  SCIP_STAT* stat, /**< dynamic SCIP statistics */
884  SCIP_PROB* transprob, /**< transformed problem */
885  SCIP_REOPT* reopt /**< reoptimization data */
886  )
887 {
888  int ndelconfs;
889  int ndeldualray;
890  int ndeldualsol;
891 
892  assert(conflictstore != NULL);
893 
894  SCIPsetDebugMsg(set, "cleaning conflict store: %d conflicts, %d dual proofs\n",
895  conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs);
896 
897  ndelconfs = 0;
898  ndeldualray = 0;
899  ndeldualsol = 0;
900 
901  /* remove all conflicts that are marked as deleted or where the check flag has changed to TRUE.
902  *
903  * the latter case might happen during processing parallel constraints, e.g., cons_knapsack.c:detectRedundantConstraints().
904  * in that case, the conflict constraint should stay, e.g., it has the stricter capacity, and replaces a model
905  * constraint. hence, the conflict is now a constraint that is needed to stay correct. therefore, the conflictpool
906  * is not allowed to delete this constraint from the entire problem.
907  */
908  SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) );
909 
910  /* remove all dual infeasibility proofs that are marked as deleted or where the check flag has changed to TRUE. */
911  SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeldualray) );
912 
913  /* remove all dual bound exceeding proofs that are marked as deleted or where the check flag has changed to TRUE. */
914  SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeldualsol) );
915 
916  /* don't update bound exceeding proofs after a restart
917  *
918  * TODO: check whether we want to delete bound exceeding proofs in general during a restart
919  */
920  if( SCIPisInRestart(set->scip) )
921  {
922  int i;
923 
924  for( i = conflictstore->ndualrayconfs-1; i >= 0 ; i-- )
925  {
926  if( conflictstore->drayrelaxonly[i] )
927  {
928  SCIP_CALL( delPosDualray(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) );
929  }
930  }
931 
932  for( i = conflictstore->ndualsolconfs-1; i >= 0 ; i-- )
933  {
934  if( conflictstore->dsolrelaxonly[i] )
935  {
936  SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) );
937  }
938  else
939  {
940  conflictstore->updateside[i] = FALSE;
941  }
942  }
943  }
944 
945  return SCIP_OKAY;
946 }
947 
948 /** adds a constraint to the pool of proof constraints based on dual rays
949  *
950  * @note this methods captures the constraint
951  */
953  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
954  SCIP_CONS* dualproof, /**< constraint based on a dual ray */
955  BMS_BLKMEM* blkmem, /**< block memory */
956  SCIP_SET* set, /**< global SCIP settings */
957  SCIP_STAT* stat, /**< dynamic SCIP statistics */
958  SCIP_PROB* transprob, /**< transformed problem */
959  SCIP_REOPT* reopt, /**< reoptimization data */
960  SCIP_Bool hasrelaxvar /**< does the dual proof contain at least one variable that exists in
961  * the current relaxation only? */
962  )
963 {
964  int nvars;
965  SCIP_Bool success;
966 
967  assert(conflictstore != NULL);
968  assert(conflictstore->ndualrayconfs <= CONFLICTSTORE_DUALRAYSIZE);
969 
970  /* mark the constraint to be a conflict */
971  SCIPconsMarkConflict(dualproof);
972 
973  /* create an array to store constraints based on dual rays */
974  if( conflictstore->dualrayconfs == NULL )
975  {
978  }
979 
980  /* the store is full, we proceed as follows
981  *
982  * 1. check whether some constraints are marked as deleted and remove those
983  * 2. if no constraint is marked as deleted: remove the oldest
984  */
985  if( conflictstore->ndualrayconfs == CONFLICTSTORE_DUALRAYSIZE )
986  {
987  int ndeleted = 0;
988 
989  /* remove all as deleted marked dual infeasibility proofs */
990  SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) );
991 
992  /* if we could not remove a dual ray that is already marked as deleted we need to remove the oldest active one */
993  if( ndeleted == 0 )
994  {
995  SCIP_Bool local = SCIPconsIsLocal(dualproof);
996  int pos = 0;
997 
998  /* sort dual rays */
999  SCIPsortPtrBool((void**)conflictstore->dualrayconfs, conflictstore->drayrelaxonly, compareConss,
1000  conflictstore->ndualrayconfs);
1001  assert(SCIPsetIsGE(set, SCIPconsGetAge(conflictstore->dualrayconfs[0]),
1002  SCIPconsGetAge(conflictstore->dualrayconfs[conflictstore->ndualrayconfs-1])));
1003 
1004  while( pos < conflictstore->ndualrayconfs-1 && local != SCIPconsIsLocal(conflictstore->dualrayconfs[pos]) )
1005  pos++;
1006 
1007  /* we don't want to keep the dual proof */
1008  if( pos >= conflictstore->ndualrayconfs )
1009  {
1010  SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) );
1011  return SCIP_OKAY;
1012  }
1013 
1014  SCIP_CALL( delPosDualray(conflictstore, set, stat, transprob, blkmem, reopt, pos, TRUE) );
1015  }
1016  }
1017 
1018  /* add the new constraint based on a dual ray at the last position */
1019  SCIPconsCapture(dualproof);
1020  conflictstore->dualrayconfs[conflictstore->ndualrayconfs] = dualproof;
1021  conflictstore->drayrelaxonly[conflictstore->ndualrayconfs] = hasrelaxvar;
1022  ++conflictstore->ndualrayconfs;
1023 
1024  /* add conflict locks */
1025  SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, +1, 0) );
1026 
1027  /* increase the number of non-zeros */
1028  SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) );
1029  assert(success);
1030  conflictstore->nnzdualrays += nvars;
1031 
1032  return SCIP_OKAY;
1033 }
1034 
1035 /** adds a constraint to the pool of proof constraints based on dual solutions
1036  *
1037  * @note this methods captures the constraint
1038  */
1040  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1041  SCIP_CONS* dualproof, /**< constraint based on a dual solution */
1042  BMS_BLKMEM* blkmem, /**< block memory */
1043  SCIP_SET* set, /**< global SCIP settings */
1044  SCIP_STAT* stat, /**< dynamic SCIP statistics */
1045  SCIP_PROB* transprob, /**< transformed problem */
1046  SCIP_REOPT* reopt, /**< reoptimization data */
1047  SCIP_Real scale, /**< scaling factor that needs to be considered when updating the side */
1048  SCIP_Bool updateside, /**< should the side be updated if a new incumbent is found */
1049  SCIP_Bool hasrelaxvar /**< does the dual proof contain at least one variable that exists in
1050  * the current relaxation only? */
1051  )
1052 {
1053  int nvars;
1054  SCIP_Bool success;
1055 
1056  assert(conflictstore != NULL);
1057  assert(conflictstore->ndualsolconfs <= CONFLICTSTORE_DUALSOLSIZE);
1058 
1059  /* mark the constraint to be a conflict */
1060  SCIPconsMarkConflict(dualproof);
1061 
1062  /* create an array to store constraints based on dual rays */
1063  if( conflictstore->dualsolconfs == NULL )
1064  {
1070  }
1071 
1072  /* the store is full, we proceed as follows
1073  *
1074  * 1. check whether some constraints are marked as deleted and remove those
1075  * 2. if no constraint is marked as deleted: remove the oldest
1076  */
1077  if( conflictstore->ndualsolconfs == CONFLICTSTORE_DUALSOLSIZE )
1078  {
1079  int ndeleted = 0;
1080 
1081  /* remove all as deleted marked dual bound exceeding proofs */
1082  SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) );
1083 
1084  /* if we could not remove a dual proof that is already marked as deleted we need to remove the oldest active one */
1085  if( ndeleted == 0 )
1086  {
1087  SCIP_Bool local = SCIPconsIsLocal(dualproof);
1088  int pos = 0;
1089 
1090  /* sort dual rays */
1091  SCIPsortPtrRealRealBoolBool((void**)conflictstore->dualsolconfs, conflictstore->dualprimalbnds,
1092  conflictstore->scalefactors, conflictstore->updateside, conflictstore->dsolrelaxonly,
1093  compareConss, conflictstore->ndualsolconfs);
1094  assert(SCIPsetIsGE(set, SCIPconsGetAge(conflictstore->dualsolconfs[0]),
1095  SCIPconsGetAge(conflictstore->dualsolconfs[conflictstore->ndualsolconfs-1])));
1096 
1097  while( pos < conflictstore->ndualsolconfs-1 && local != SCIPconsIsLocal(conflictstore->dualsolconfs[pos]) )
1098  pos++;
1099 
1100  /* we don't want to keep the dual proof */
1101  if( pos >= conflictstore->ndualsolconfs )
1102  {
1103  SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) );
1104  return SCIP_OKAY;
1105  }
1106 
1107  SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, pos, TRUE) );
1108  }
1109  }
1110 
1111  /* add the new constraint based on a dual solution at the last position */
1112  SCIPconsCapture(dualproof);
1113  conflictstore->dualsolconfs[conflictstore->ndualsolconfs] = dualproof;
1114  conflictstore->dualprimalbnds[conflictstore->ndualsolconfs] = SCIPgetCutoffbound(set->scip) - SCIPsetSumepsilon(set);
1115  conflictstore->scalefactors[conflictstore->ndualsolconfs] = scale;
1116  conflictstore->updateside[conflictstore->ndualsolconfs] = updateside;
1117  conflictstore->dsolrelaxonly[conflictstore->ndualsolconfs] = hasrelaxvar;
1118  ++conflictstore->ndualsolconfs;
1119 
1120  /* add conflict locks */
1121  SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, +1, 0) );
1122 
1123  /* increase the number of non-zeros */
1124  SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) );
1125  assert(success);
1126  conflictstore->nnzdualsols += nvars;
1127 
1128  return SCIP_OKAY;
1129 }
1130 
1131 /** adds a conflict to the conflict store
1132  *
1133  * @note this method captures the constraint
1134  */
1136  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1137  BMS_BLKMEM* blkmem, /**< block memory */
1138  SCIP_SET* set, /**< global SCIP settings */
1139  SCIP_STAT* stat, /**< dynamic SCIP statistics */
1140  SCIP_TREE* tree, /**< branch and bound tree (or NULL for an original constraint) */
1141  SCIP_PROB* transprob, /**< transformed problem (or NULL for an original constraint) */
1142  SCIP_REOPT* reopt, /**< reoptimization data */
1143  SCIP_CONS* cons, /**< constraint representing the conflict */
1144  SCIP_CONFTYPE conftype, /**< type of the conflict */
1145  SCIP_Bool cutoffinvolved, /**< is a cutoff bound involved in this conflict */
1146  SCIP_Real primalbound /**< primal bound the conflict depend on (or -SCIPinfinity) */
1147  )
1148 {
1149  SCIP_Longint curnodenum;
1150  int nconflicts;
1151 
1152  assert(conflictstore != NULL);
1153  assert(blkmem != NULL);
1154  assert(set != NULL);
1155  assert(stat != NULL);
1156  assert(tree != NULL || SCIPconsIsOriginal(cons));
1157  assert(transprob != NULL || SCIPconsIsOriginal(cons));
1158  assert(cons != NULL);
1159  assert(conftype != SCIP_CONFTYPE_BNDEXCEEDING || cutoffinvolved);
1160  assert(!cutoffinvolved || !SCIPsetIsInfinity(set, REALABS(primalbound)));
1161 
1162  /* mark the constraint to be a conflict */
1163  SCIPconsMarkConflict(cons);
1164 
1165  /* add the constraint to a special store */
1166  if( SCIPconsIsOriginal(cons) )
1167  {
1168  assert(SCIPsetGetStage(set) == SCIP_STAGE_PROBLEM);
1169  SCIP_CALL( conflictstoreAddOrigConflict(conflictstore, set, blkmem, cons) );
1170  return SCIP_OKAY;
1171  }
1172 
1173  nconflicts = conflictstore->nconflicts;
1174 
1175  /* initialize the storage */
1176  if( conflictstore->maxstoresize == -1 )
1177  {
1178  SCIP_CALL( initConflictstore(conflictstore, set, transprob) );
1179  }
1180  assert(conflictstore->initstoresize >= 0);
1181  assert(conflictstore->initstoresize <= conflictstore->maxstoresize);
1182 
1183  /* return if conflict pool is disabled */
1184  if( conflictstore->maxstoresize <= 0 )
1185  return SCIP_OKAY;
1186 
1187  SCIP_CALL( conflictstoreEnsureMem(conflictstore, set, blkmem, nconflicts+1) );
1188 
1189  /* return if the store has size zero */
1190  if( conflictstore->conflictsize == 0 )
1191  {
1192  assert(conflictstore->maxstoresize == 0);
1193  return SCIP_OKAY;
1194  }
1195 
1196  assert(tree != NULL);
1197  curnodenum = (SCIPtreeGetFocusNode(tree) == NULL ? -1 : SCIPnodeGetNumber(SCIPtreeGetFocusNode(tree)));
1198 
1199  /* clean up the storage if we are at a new node or the storage is full */
1200  if( conflictstore->lastnodenum != curnodenum || conflictstore->nconflicts == conflictstore->conflictsize )
1201  {
1202  SCIP_CALL( conflictstoreCleanUpStorage(conflictstore, set, stat, transprob, blkmem, reopt) );
1203  }
1204 
1205  /* update the last seen node */
1206  conflictstore->lastnodenum = curnodenum;
1207 
1208  SCIPconsCapture(cons);
1209  conflictstore->conflicts[conflictstore->nconflicts] = cons;
1210  conflictstore->confprimalbnds[conflictstore->nconflicts] = primalbound;
1211  conflictstore->ncbconflicts += (SCIPsetIsInfinity(set, REALABS(primalbound)) ? 0 : 1);
1212 
1213  ++conflictstore->nconflicts;
1214  ++conflictstore->nconflictsfound;
1215 
1216  /* add conflict locks */
1217  SCIP_CALL( SCIPconsAddLocks(cons, set, SCIP_LOCKTYPE_CONFLICT, +1, 0) );
1218 
1219 #ifdef SCIP_PRINT_DETAILS
1220  SCIPsetDebugMsg(set, "add conflict <%s> to conflict store at position %d\n", SCIPconsGetName(cons), conflictstore->nconflicts-1);
1221  SCIPsetDebugMsg(set, " -> conflict type: %d, cutoff involved = %u\n", conftype, cutoffinvolved);
1222  if( cutoffinvolved )
1223  SCIPsetDebugMsg(set, " -> current primal bound: %g\n", primalbound);
1224 #endif
1225 
1226  return SCIP_OKAY;
1227 }
1228 
1229 /** deletes all conflicts depending on a cutoff bound larger than the given bound */
1231  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1232  SCIP_SET* set, /**< global SCIP settings */
1233  SCIP_STAT* stat, /**< dynamic SCIP statistics */
1234  BMS_BLKMEM* blkmem, /**< block memory */
1235  SCIP_PROB* transprob, /**< transformed problem*/
1236  SCIP_REOPT* reopt, /**< reoptimization data */
1237  SCIP_Real cutoffbound /**< current cutoff bound */
1238  )
1239 {
1240  SCIP_Real improvement;
1241  int ndelconfs;
1242  int nchgsides;
1243  int i;
1244 
1245  assert(conflictstore != NULL);
1246  assert(set != NULL);
1247  assert(stat != NULL);
1248  assert(blkmem != NULL);
1249  assert(transprob != NULL);
1250 
1251  /* return if we do not want to use the storage */
1252  if( set->conf_maxstoresize == 0 )
1253  return SCIP_OKAY;
1254 
1255  /* return if we do not want to remove conflicts related to an older cutoff bound */
1256  if( !set->conf_cleanbnddepend )
1257  return SCIP_OKAY;
1258 
1259  /* there is nothing to clean */
1260  if( conflictstore->ndualsolconfs == 0 && conflictstore->nconflicts == 0 )
1261  return SCIP_OKAY;
1262 
1263  /* we can stop whenever we have found a new incumbent but the cutoff bound has not changed */
1264  if( conflictstore->lastcutoffbound != SCIP_INVALID && SCIPsetIsGE(set, cutoffbound, conflictstore->lastcutoffbound) ) /*lint !e777*/
1265  return SCIP_OKAY;
1266 
1267  conflictstore->lastcutoffbound = cutoffbound;
1268 
1269  /* calculate scalar to determine whether the old primal bound is worse enough to remove the conflict */
1270  if( SCIPsetIsPositive(set, cutoffbound) )
1271  improvement = (1 - set->conf_minimprove);
1272  else
1273  improvement = (1 + set->conf_minimprove);
1274 
1275  /* remove all conflicts depending on a primalbound*improvement > cutoffbound
1276  *
1277  * note: we cannot remove conflicts that are marked as deleted because at this point in time we would destroy
1278  * the internal data structure
1279  */
1280  ndelconfs = 0;
1281  for( i = 0; i < conflictstore->nconflicts; )
1282  {
1283  assert(conflictstore->conflicts[i] != NULL);
1284 
1285  /* check if the conflict depends on the cutoff bound */
1286  if( SCIPsetIsGT(set, improvement * conflictstore->confprimalbnds[i], cutoffbound) )
1287  {
1288  /* remove conflict at current position
1289  *
1290  * don't increase i because delPosConflict will swap the last pointer to the i-th position
1291  */
1292  SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) );
1293  ++ndelconfs;
1294  }
1295  else
1296  /* increase i */
1297  ++i;
1298  }
1299  assert(conflictstore->ncbconflicts >= 0);
1300  assert(conflictstore->nconflicts >= 0);
1301 
1302  SCIPsetDebugMsg(set, "-> removed %d/%d conflicts, %d depending on cutoff bound\n", ndelconfs,
1303  conflictstore->nconflicts+ndelconfs, ndelconfs);
1304 
1305  ndelconfs = 0;
1306  nchgsides = 0;
1307  /* update all proof constraints based on a dual solution */
1308  for( i = 0; i < conflictstore->ndualsolconfs; )
1309  {
1310  SCIP_CONSHDLR* conshdlr;
1311  SCIP_CONS* dualproof;
1312 
1313  dualproof = conflictstore->dualsolconfs[i];
1314  assert(dualproof != NULL);
1315 
1316  if( SCIPconsIsDeleted(dualproof) )
1317  {
1318  ++i;
1319  continue;
1320  }
1321  if( !conflictstore->updateside[i] || SCIPsetIsLE(set, improvement * conflictstore->dualprimalbnds[i], cutoffbound) )
1322  {
1323  ++i;
1324  continue;
1325  }
1326  conshdlr = SCIPconsGetHdlr(dualproof);
1327  assert(conshdlr != NULL);
1328 
1329  if( strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 )
1330  {
1331  SCIP_Real rhs;
1332  SCIP_Real newside;
1333 
1334  assert(SCIPsetIsGT(set, conflictstore->dualprimalbnds[i], cutoffbound));
1335 
1336  rhs = SCIPgetRhsLinear(set->scip, dualproof);
1337 
1338  if( !SCIPsetIsInfinity(set, rhs) )
1339  {
1340  assert(SCIPsetIsInfinity(set, -SCIPgetLhsLinear(set->scip, dualproof)));
1341  assert(SCIPsetIsPositive(set, conflictstore->scalefactors[i]));
1342 
1343  /* get unscaled rhs */
1344  newside = rhs * conflictstore->scalefactors[i];
1345  newside -= conflictstore->dualprimalbnds[i];
1346  newside += cutoffbound - SCIPsetSumepsilon(set);
1347 
1348  /* scale rhs */
1349  newside /= conflictstore->scalefactors[i];
1350 
1351  SCIP_CALL( SCIPchgRhsLinear(set->scip, dualproof, newside) );
1352  }
1353  else
1354  {
1355  SCIP_Real lhs;
1356 
1357  lhs = SCIPgetLhsLinear(set->scip, dualproof);
1358  assert(!SCIPsetIsInfinity(set, -lhs));
1359  assert(SCIPsetIsNegative(set, conflictstore->scalefactors[i]));
1360 
1361  /* get unscaled lhs */
1362  newside = lhs * conflictstore->scalefactors[i];
1363  newside += conflictstore->dualprimalbnds[i];
1364  newside -= (cutoffbound - SCIPsetSumepsilon(set));
1365 
1366  /* scale lhs */
1367  newside /= conflictstore->scalefactors[i];
1368 
1369  SCIP_CALL( SCIPchgLhsLinear(set->scip, dualproof, newside) );
1370  }
1371 
1372  ++nchgsides;
1373 
1374  conflictstore->dualprimalbnds[i] = cutoffbound - SCIPsetSumepsilon(set);
1375 
1376  ++i;
1377  }
1378  else if( SCIPsetIsGT(set, improvement * conflictstore->dualprimalbnds[i], cutoffbound) )
1379  {
1380  /* remove conflict at current position
1381  *
1382  * don't increase i because delPosDualsol will swap the last pointer to the i-th position
1383  */
1384  SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) );
1385  ++ndelconfs;
1386  }
1387  else
1388  /* increase i */
1389  ++i;
1390  }
1391 
1392  SCIPsetDebugMsg(set, "-> changed %d sides of dual solution constraints\n", nchgsides);
1393  SCIPsetDebugMsg(set, "-> deleted %d dual solution constraints\n", ndelconfs);
1394 
1395  return SCIP_OKAY;
1396 }
1397 
1398 /** returns the maximal size of the conflict pool */
1400  SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1401  )
1402 {
1403  assert(conflictstore != NULL);
1404 
1405  return MIN(conflictstore->storesize, conflictstore->maxstoresize);
1406 }
1407 
1408 /** returns the initial size of the conflict pool */
1410  SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1411  )
1412 {
1413  assert(conflictstore != NULL);
1414 
1415  return conflictstore->initstoresize;
1416 }
1417 
1418 /** returns the number of stored conflicts on the conflict pool
1419  *
1420  * @note the number of active conflicts can be less
1421  */
1423  SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1424  )
1425 {
1426  assert(conflictstore != NULL);
1427 
1428  return conflictstore->nconflicts;
1429 }
1430 
1431 /** returns all active conflicts stored in the conflict store */
1433  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1434  SCIP_CONS** conflicts, /**< array to store conflicts */
1435  int conflictsize, /**< size of the conflict array */
1436  int* nconflicts /**< pointer to store the number of conflicts */
1437  )
1438 {
1439  int i;
1440 
1441  assert(conflictstore != NULL);
1442 
1443  /* return if the allocated memory is obviously to small */
1444  if( conflictstore->nconflicts > conflictsize )
1445  {
1446  (*nconflicts) = conflictstore->nconflicts;
1447  return SCIP_OKAY;
1448  }
1449 
1450  (*nconflicts) = 0;
1451  for( i = 0; i < conflictstore->nconflicts; i++ )
1452  {
1453  SCIP_CONS* conflict;
1454 
1455  conflict = conflictstore->conflicts[i];
1456  assert(conflict != NULL);
1457 
1458  /* skip deactivated and deleted constraints */
1459  if( !SCIPconsIsActive(conflict) || SCIPconsIsDeleted(conflict) )
1460  continue;
1461 
1462  /* count exact number conflicts */
1463  if( *nconflicts > conflictsize )
1464  ++(*nconflicts);
1465  else
1466  {
1467  conflicts[*nconflicts] = conflict;
1468  ++(*nconflicts);
1469  }
1470  }
1471 
1472  return SCIP_OKAY;
1473 }
1474 
1475 /** transformes all original conflicts into transformed conflicts */
1477  SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1478  BMS_BLKMEM* blkmem, /**< block memory */
1479  SCIP_SET* set, /**< global SCIP settings */
1480  SCIP_STAT* stat, /**< dynamic SCIP statistics */
1481  SCIP_TREE* tree, /**< branch and bound tree */
1482  SCIP_PROB* transprob, /**< transformed problem */
1483  SCIP_REOPT* reopt /**< reoptimization data */
1484  )
1485 {
1486  int ntransconss;
1487  int i;
1488 
1489  assert(conflictstore != NULL);
1490  assert(set != NULL);
1491  assert(SCIPsetGetStage(set) == SCIP_STAGE_TRANSFORMING);
1492 
1493  /* return if no original constraints are stored */
1494  if( conflictstore->norigconfs == 0 )
1495  return SCIP_OKAY;
1496 
1497  ntransconss = 0;
1498 
1499  for( i = 0; i < conflictstore->norigconfs; i++ )
1500  {
1501  SCIP_CONS* transcons;
1502 
1503  assert(conflictstore->origconfs[i] != NULL);
1504  assert(SCIPconsIsOriginal(conflictstore->origconfs[i]));
1505 
1506  transcons = SCIPconsGetTransformed(conflictstore->origconfs[i]);
1507 
1508  if( transcons != NULL )
1509  {
1510  SCIP_CALL( SCIPconflictstoreAddConflict(conflictstore, blkmem, set, stat, tree, transprob, reopt, transcons, \
1512 
1513  ++ntransconss;
1514  }
1515 
1516  SCIP_CALL( SCIPconsRelease(&conflictstore->origconfs[i], blkmem, set) );
1517  }
1518 
1519  SCIPsetDebugMsg(set, "-> transform %d/%d conflicts into transformed space\n", ntransconss, conflictstore->norigconfs);
1520 
1521  conflictstore->norigconfs = 0;
1522 
1523  return SCIP_OKAY;
1524 }
1525 
1526 /** returns the average number of non-zeros over all stored dual ray constraints */
1528  SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1529  )
1530 {
1531  assert(conflictstore != NULL);
1532 
1533  if( conflictstore->ndualrayconfs == 0 )
1534  return 0.0;
1535  else
1536  return (SCIP_Real) conflictstore->nnzdualrays / ((SCIP_Real) conflictstore->ndualrayconfs);
1537 }
1538 
1539 /** returns the number of all stored dual ray constraints */
1541  SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1542  )
1543 {
1544  assert(conflictstore != NULL);
1545 
1546  return conflictstore->ndualrayconfs;
1547 }
1548 
1549 /** returns the average number of non-zeros over all stored boundexceeding proofs */
1551  SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1552  )
1553 {
1554  assert(conflictstore != NULL);
1555  assert(conflictstore->ndualsolconfs >= 0);
1556 
1557  if( conflictstore->ndualsolconfs == 0 )
1558  return 0.0;
1559  else
1560  return (SCIP_Real) conflictstore->nnzdualsols / ((SCIP_Real) conflictstore->ndualsolconfs);
1561 }
1562 
1563 /** returns the number of all stored boundexceeding proofs */
1565  SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1566  )
1567 {
1568  assert(conflictstore != NULL);
1569 
1570  return conflictstore->ndualsolconfs;
1571 }
1572 
SCIP_RETCODE SCIPclearConflictStore(SCIP *scip, SCIP_EVENT *event)
Definition: scip_prob.c:3284
SCIP_RETCODE SCIPconsDelete(SCIP_CONS *cons, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_REOPT *reopt)
Definition: cons.c:6342
SCIP_RETCODE SCIPsetIncludeEventhdlr(SCIP_SET *set, SCIP_EVENTHDLR *eventhdlr)
Definition: set.c:4744
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6200
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:461
internal methods for managing events
static SCIP_DECL_SORTPTRCOMP(compareConss)
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6258
#define EVENTHDLR_NAME
Definition: conflictstore.c:49
#define CONFLICTSTORE_SORTFREQ
Definition: conflictstore.c:46
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:356
int SCIPprobGetNConss(SCIP_PROB *prob)
Definition: prob.c:2397
internal methods for branch and bound tree
static SCIP_RETCODE delPosDualsol(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
static SCIP_DECL_EVENTEXITSOL(eventExitsolConflictstore)
Definition: conflictstore.c:92
int SCIPconflictstoreGetNConflictsInStore(SCIP_CONFLICTSTORE *conflictstore)
SCIP_RETCODE SCIPconflictstoreTransform(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_REOPT *reopt)
SCIP_RETCODE SCIPconflictstoreClean(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt)
#define CONFLICTSTORE_MINSIZE
Definition: conflictstore.c:43
SCIP_RETCODE SCIPconflictstoreCleanNewIncumbent(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Real cutoffbound)
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6323
SCIP_EVENTHDLR * SCIPsetFindEventhdlr(SCIP_SET *set, const char *name)
Definition: set.c:4767
static SCIP_RETCODE cleanDeletedAndCheckedDualsolCons(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelproofs)
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6065
int SCIPprobGetNVars(SCIP_PROB *prob)
Definition: prob.c:2343
void SCIPconsMarkConflict(SCIP_CONS *cons)
Definition: cons.c:6983
#define FALSE
Definition: def.h:87
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:315
static SCIP_RETCODE conflictstoreEnsureMem(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, BMS_BLKMEM *blkmem, int num)
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
static SCIP_RETCODE cleanDeletedAndCheckedConflicts(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelconfs)
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5779
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition: tree.c:8300
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6334
SCIP_CONS * SCIPconsGetTransformed(SCIP_CONS *cons)
Definition: cons.c:6711
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPconsAddLocks(SCIP_CONS *cons, SCIP_SET *set, SCIP_LOCKTYPE locktype, int nlockspos, int nlocksneg)
Definition: cons.c:7241
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8138
Definition: heur_padm.c:123
static SCIP_RETCODE cleanDeletedAndCheckedDualrayCons(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelproofs)
#define CONFLICTSTORE_DUALRAYSIZE
Definition: conflictstore.c:41
SCIP_RETCODE SCIPconflictstoreCreate(SCIP_CONFLICTSTORE **conflictstore, SCIP_SET *set)
int SCIPconflictstoreGetNDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
SCIP_Bool SCIPconsIsOriginal(SCIP_CONS *cons)
Definition: cons.c:8376
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6294
static SCIP_DECL_EVENTEXEC(eventExecConflictstore)
Definition: conflictstore.c:55
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7432
static SCIP_RETCODE delPosDualray(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
#define CONFLICTSTORE_DUALSOLSIZE
Definition: conflictstore.c:42
SCIP_RETCODE SCIPconflictstoreClear(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
SCIP_Real SCIPconsGetAge(SCIP_CONS *cons)
Definition: cons.c:8236
internal methods for storing and manipulating the main problem
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4167
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2558
SCIP_RETCODE SCIPconflictstoreAddDualraycons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Bool hasrelaxvar)
void SCIPsortPtrBool(void **ptrarray, SCIP_Bool *boolarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
static SCIP_RETCODE conflictstoreAddOrigConflict(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_CONS *cons)
SCIP_RETCODE SCIPconflictstoreFree(SCIP_CONFLICTSTORE **conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8077
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:241
internal miscellaneous methods
#define NULL
Definition: lpi_spx1.cpp:155
#define REALABS(x)
Definition: def.h:201
internal methods for global SCIP settings
internal methods for storing conflicts
#define SCIP_CALL(x)
Definition: def.h:384
int SCIPconflictstoreGetInitPoolSize(SCIP_CONFLICTSTORE *conflictstore)
#define CONFLICTSTORE_MAXSIZE
Definition: conflictstore.c:44
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8316
static SCIP_RETCODE initConflictstore(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_PROB *transprob)
static SCIP_RETCODE delPosConflict(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
data structures and methods for collecting reoptimization information
#define SCIP_UNKNOWN
Definition: def.h:198
SCIP_RETCODE SCIPconsGetNVars(SCIP_CONS *cons, SCIP_SET *set, int *nvars, SCIP_Bool *success)
Definition: cons.c:6310
#define SCIP_Bool
Definition: def.h:84
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:277
SCIP_Real SCIPsetSumepsilon(SCIP_SET *set)
Definition: set.c:6097
#define BMSallocBlockMemoryArray(mem, ptr, num)
Definition: memory.h:447
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1021
static SCIP_RETCODE conflictstoreCleanUpStorage(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt)
SCIP_RETCODE SCIPconsRelease(SCIP_CONS **cons, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition: cons.c:6195
SCIP_RETCODE SCIPsetGetIntParam(SCIP_SET *set, const char *name, int *value)
Definition: set.c:3167
#define MAX(x, y)
Definition: tclique_def.h:83
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8097
SCIP_Real SCIPconflictstoreGetAvgNnzDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
#define CONFLICTSTORE_SIZE
Definition: conflictstore.c:45
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8206
#define SCIPsetDebugMsg
Definition: set.h:1755
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:311
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8276
#define EVENTHDLR_DESC
Definition: conflictstore.c:50
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
int SCIPconflictstoreGetMaxPoolSize(SCIP_CONFLICTSTORE *conflictstore)
SCIP_RETCODE SCIPconflictstoreAddDualsolcons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Real scale, SCIP_Bool updateside, SCIP_Bool hasrelaxvar)
#define SCIP_EVENTTYPE_BESTSOLFOUND
Definition: type_event.h:96
void SCIPconsCapture(SCIP_CONS *cons)
Definition: cons.c:6183
#define BMSfreeMemoryNull(ptr)
Definition: memory.h:139
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6276
#define SCIP_Real
Definition: def.h:177
enum SCIP_ConflictType SCIP_CONFTYPE
Definition: type_conflict.h:56
SCIP_RETCODE SCIPconflictstoreAddConflict(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_CONS *cons, SCIP_CONFTYPE conftype, SCIP_Bool cutoffinvolved, SCIP_Real primalbound)
#define BMSallocMemory(ptr)
Definition: memory.h:111
#define SCIP_INVALID
Definition: def.h:197
internal methods for constraints and constraint handlers
void SCIPsortPtrReal(void **ptrarray, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
int SCIPconflictstoreGetNDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
#define SCIP_Longint
Definition: def.h:162
static SCIP_DECL_EVENTINITSOL(eventInitsolConflictstore)
Definition: conflictstore.c:72
SCIP_Real SCIPconflictstoreGetAvgNnzDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
SCIP_STAGE SCIPsetGetStage(SCIP_SET *set)
Definition: set.c:2982
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:430
void SCIPsortPtrRealRealBoolBool(void **ptrarray, SCIP_Real *realarray1, SCIP_Real *realarray2, SCIP_Bool *boolarray1, SCIP_Bool *boolarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define SCIP_ALLOC(x)
Definition: def.h:395
SCIP_RETCODE SCIPeventhdlrCreate(SCIP_EVENTHDLR **eventhdlr, SCIP_SET *set, const char *name, const char *desc, SCIP_DECL_EVENTCOPY((*eventcopy)), SCIP_DECL_EVENTFREE((*eventfree)), SCIP_DECL_EVENTINIT((*eventinit)), SCIP_DECL_EVENTEXIT((*eventexit)), SCIP_DECL_EVENTINITSOL((*eventinitsol)), SCIP_DECL_EVENTEXITSOL((*eventexitsol)), SCIP_DECL_EVENTDELETE((*eventdelete)), SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:114
SCIP_Bool SCIPisInRestart(SCIP *scip)
Definition: scip_solve.c:3677
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:451
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPconflictstoreGetConflicts(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS **conflicts, int conflictsize, int *nconflicts)
SCIP callable library.
static void adjustStorageSize(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set)