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"
47 #include "scip/struct_conflictstore.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);
69 assert(SCIPeventGetType(event) & SCIP_EVENTTYPE_BESTSOLFOUND);
70
71 if( SCIPgetStage(scip) == SCIP_STAGE_PRESOLVING || SCIPgetStage(scip) == SCIP_STAGE_SOLVING )
72 {
73 SCIP_CALL( SCIPclearConflictStore(scip, event) );
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
94 SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, eventhdlr, NULL, NULL) );
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
114 SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, eventhdlr, NULL, -1) );
115
116 return SCIP_OKAY;
117 }
118
119 /* comparison method for constraints */
120 static
121 SCIP_DECL_SORTPTRCOMP(compareConss)
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
173 SCIP_RETCODE initConflictstore(
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
229 SCIP_RETCODE conflictstoreEnsureMem(
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
290 void adjustStorageSize(
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
311 SCIP_RETCODE delPosConflict(
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
370 SCIP_RETCODE delPosDualray(
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 */
(1) Event cond_false: |
Condition "(_restat_ = SCIPconsGetNVars(dualproof, set, &nvars, &success)) != SCIP_OKAY", taking false branch. |
(2) Event if_end: |
End of if statement. |
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 */
(3) Event cond_false: |
Condition "(_restat_ = SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, -1, 0)) != SCIP_OKAY", taking false branch. |
(4) Event if_end: |
End of if statement. |
402 SCIP_CALL( SCIPconsAddLocks(dualproof, set, SCIP_LOCKTYPE_CONFLICT, -1, 0) );
403
404 /* mark the constraint as deleted */
(5) Event cond_true: |
Condition "deleteconflict", taking true branch. |
(6) Event cond_true: |
Condition "!dualproof->deleted", taking true branch. |
405 if( deleteconflict && !SCIPconsIsDeleted(dualproof) )
406 {
407 assert(transprob != NULL);
(7) Event deref_parm_in_call: |
Function "SCIPconsDelete" dereferences "reopt". [details] |
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
432 SCIP_RETCODE delPosDualsol(
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
501 SCIP_RETCODE cleanDeletedAndCheckedConflicts(
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
537 SCIP_RETCODE cleanDeletedAndCheckedDualrayCons(
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
575 SCIP_RETCODE cleanDeletedAndCheckedDualsolCons(
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
613 SCIP_RETCODE conflictstoreCleanUpStorage(
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
714 SCIP_RETCODE conflictstoreAddOrigConflict(
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 {
726 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->origconfs, CONFLICTSTORE_MINSIZE) );
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 */
745 SCIP_RETCODE SCIPconflictstoreCreate(
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 */
795 SCIP_RETCODE SCIPconflictstoreFree(
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 */
825 SCIP_RETCODE SCIPconflictstoreClear(
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 */
888 SCIP_RETCODE SCIPconflictstoreClean(
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
(1) Event cond_false: |
Condition "0", taking false branch. |
903 SCIPsetDebugMsg(set, "cleaning conflict store: %d conflicts, %d dual proofs\n",
(2) Event loop_end: |
Reached end of loop. |
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 */
(3) Event cond_false: |
Condition "(_restat_ = cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs)) != SCIP_OKAY", taking false branch. |
(4) Event if_end: |
End of if statement. |
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. */
(5) Event cond_false: |
Condition "(_restat_ = cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeldualray)) != SCIP_OKAY", taking false branch. |
(6) Event if_end: |
End of if statement. |
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. */
(7) Event cond_false: |
Condition "(_restat_ = cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeldualsol)) != SCIP_OKAY", taking false branch. |
(8) Event if_end: |
End of if statement. |
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 */
(9) Event cond_true: |
Condition "SCIPisInRestart(set->scip)", taking true branch. |
929 if( SCIPisInRestart(set->scip) )
930 {
931 int i;
932
(10) Event cond_true: |
Condition "i >= 0", taking true branch. |
933 for( i = conflictstore->ndualrayconfs-1; i >= 0 ; i-- )
934 {
(11) Event cond_true: |
Condition "conflictstore->drayrelaxonly[i]", taking true branch. |
935 if( conflictstore->drayrelaxonly[i] )
936 {
(12) Event deref_parm_in_call: |
Function "delPosDualray" dereferences "reopt". [details] |
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 */
961 SCIP_RETCODE SCIPconflictstoreAddDualraycons(
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 {
985 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE) );
986 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->drayrelaxonly, CONFLICTSTORE_DUALRAYSIZE) );
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 */
1048 SCIP_RETCODE SCIPconflictstoreAddDualsolcons(
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 {
1074 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE) );
1075 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE) );
1076 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->scalefactors, CONFLICTSTORE_DUALSOLSIZE) );
1077 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->updateside, CONFLICTSTORE_DUALSOLSIZE) );
1078 SCIP_ALLOC( BMSallocBlockMemoryArray(blkmem, &conflictstore->dsolrelaxonly, CONFLICTSTORE_DUALSOLSIZE) );
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 */
1144 SCIP_RETCODE SCIPconflictstoreAddConflict(
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 */
1239 SCIP_RETCODE SCIPconflictstoreCleanNewIncumbent(
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 */
1408 int SCIPconflictstoreGetMaxPoolSize(
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 */
1418 int SCIPconflictstoreGetInitPoolSize(
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 */
1431 int SCIPconflictstoreGetNConflictsInStore(
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 */
1441 SCIP_RETCODE SCIPconflictstoreGetConflicts(
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 */
1485 SCIP_RETCODE SCIPconflictstoreTransform(
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, \
1520 SCIP_CONFTYPE_UNKNOWN, FALSE, -SCIPsetInfinity(set)) );
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 */
1536 SCIP_Real SCIPconflictstoreGetAvgNnzDualInfProofs(
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 */
1549 int SCIPconflictstoreGetNDualInfProofs(
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 */
1559 SCIP_Real SCIPconflictstoreGetAvgNnzDualBndProofs(
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 */
1573 int SCIPconflictstoreGetNDualBndProofs(
1574 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1575 )
1576 {
1577 assert(conflictstore != NULL);
1578
1579 return conflictstore->ndualsolconfs;
1580 }
1581
1582