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