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