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