Scippy

SCIP

Solving Constraint Integer Programs

conflictstore.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file conflictstore.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for storing conflicts
28 * @author Jakob Witzig
29 */
30
31/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
32
33#include <assert.h>
34#include <string.h>
35
36#include "scip/conflictstore.h"
37#include "scip/cons.h"
38#include "scip/event.h"
39#include "scip/set.h"
40#include "scip/tree.h"
41#include "scip/misc.h"
42#include "scip/prob.h"
43#include "scip/reopt.h"
44#include "scip/scip.h"
45#include "scip/def.h"
46#include "scip/cons_linear.h"
48
49
50#define CONFLICTSTORE_DUALRAYSIZE 100 /* default size of conflict store */
51#define CONFLICTSTORE_DUALSOLSIZE 75 /* default size of conflict store */
52#define CONFLICTSTORE_MINSIZE 2000 /* default minimal size of a dynamic conflict store */
53#define CONFLICTSTORE_MAXSIZE 60000 /* maximal size of a dynamic conflict store (multiplied by 3) */
54#define CONFLICTSTORE_SIZE 10000 /* default size of conflict store */
55#define CONFLICTSTORE_SORTFREQ 20 /* frequency to resort the conflict array */
56
57/* event handler properties */
58#define EVENTHDLR_NAME "ConflictStore"
59#define EVENTHDLR_DESC "Solution event handler for conflict store."
60
61
62/* exec the event handler */
63static
64SCIP_DECL_EVENTEXEC(eventExecConflictstore)
65{/*lint --e{715}*/
66 assert(eventhdlr != NULL);
67 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
68 assert(event != NULL);
70
72 {
74 }
75
76 return SCIP_OKAY;
77}
78
79/** solving process initialization method of event handler (called when branch and bound process is about to begin) */
80static
81SCIP_DECL_EVENTINITSOL(eventInitsolConflictstore)
82{
83 SCIP_Bool cleanboundexceeding;
84
85 assert(scip != NULL);
86 assert(eventhdlr != NULL);
87 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
88
89 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/cleanboundexceedings", &cleanboundexceeding) );
90
91 if( !cleanboundexceeding )
92 return SCIP_OKAY;
93
95
96 return SCIP_OKAY;
97}
98
99/** solving process deinitialization method of event handler (called before branch and bound process data is freed) */
100static
101SCIP_DECL_EVENTEXITSOL(eventExitsolConflictstore)
102{
103 SCIP_Bool cleanboundexceeding;
104
105 assert(scip != NULL);
106 assert(eventhdlr != NULL);
107 assert(strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_NAME) == 0);
108
109 SCIP_CALL( SCIPgetBoolParam(scip, "conflict/cleanboundexceedings", &cleanboundexceeding) );
110
111 if( !cleanboundexceeding )
112 return SCIP_OKAY;
113
115
116 return SCIP_OKAY;
117}
118
119/* comparison method for constraints */
120static
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 */
172static
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 */
228static
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 */
289static
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 */
310static
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 */
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 */
369static
371 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
372 SCIP_SET* set, /**< global SCIP settings */
373 SCIP_STAT* stat, /**< dynamic SCIP statistics */
374 SCIP_PROB* transprob, /**< transformed problem, or NULL if delete = FALSE */
375 BMS_BLKMEM* blkmem, /**< block memory */
376 SCIP_REOPT* reopt, /**< reoptimization data */
377 int pos, /**< position to remove */
378 SCIP_Bool deleteconflict /**< should the dual ray be deleted? */
379 )
380{
381 SCIP_CONS* dualproof;
382 SCIP_Bool success;
383 int lastpos;
384 int nvars;
385
386 assert(conflictstore != NULL);
387
388 lastpos = conflictstore->ndualrayconfs-1;
389 dualproof = conflictstore->dualrayconfs[pos];
390 assert(dualproof != NULL);
391
392 /* decrease the number of non-zeros */
393 SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) );
394 assert(success);
395 conflictstore->nnzdualrays -= nvars;
396
397#ifdef SCIP_PRINT_DETAILS
398 SCIPsetDebugMsg(set, "-> remove dual proof (ray) at pos=%d age=%g nvars=%d\n", pos, SCIPconsGetAge(dualproof), nvars);
399#endif
400
401 /* remove conflict locks */
403
404 /* mark the constraint as deleted */
405 if( deleteconflict && !SCIPconsIsDeleted(dualproof) )
406 {
407 assert(transprob != NULL);
408 SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) );
409 }
410 SCIP_CALL( SCIPconsRelease(&dualproof, blkmem, set) );
411
412 /* replace with dual ray at the last position */
413 if( pos < lastpos )
414 {
415 conflictstore->dualrayconfs[pos] = conflictstore->dualrayconfs[lastpos];
416 conflictstore->drayrelaxonly[pos] = conflictstore->drayrelaxonly[lastpos];
417
418#ifndef NDEBUG
419 conflictstore->dualrayconfs[lastpos] = NULL;
420 conflictstore->drayrelaxonly[lastpos] = TRUE;
421#endif
422 }
423
424 /* decrease number of dual rays */
425 --conflictstore->ndualrayconfs;
426
427 return SCIP_OKAY;
428}
429
430/* removes proof based on a dual solution at position pos */
431static
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 */
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 */
500static
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 */
536static
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 */
574static
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 */
612static
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 */
713static
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 {
728 }
729 else if( conflictstore->norigconfs == conflictstore->origconflictsize )
730 {
731 int newsize = SCIPsetCalcMemGrowSize(set, conflictstore->origconflictsize+1);
732 SCIP_ALLOC( BMSreallocBlockMemoryArray(blkmem, &conflictstore->origconfs, conflictstore->origconflictsize, newsize) );
733 conflictstore->origconflictsize = newsize;
734 }
735
736 SCIPconsCapture(cons);
737 conflictstore->origconfs[conflictstore->norigconfs] = cons;
738 ++conflictstore->norigconfs;
739
740 return SCIP_OKAY;
741}
742
743
744/** creates conflict store */
746 SCIP_CONFLICTSTORE** conflictstore, /**< pointer to store conflict store */
747 SCIP_SET* set /**< global SCIP settings */
748 )
749{
750 assert(conflictstore != NULL);
751
752 SCIP_ALLOC( BMSallocMemory(conflictstore) );
753
754 (*conflictstore)->conflicts = NULL;
755 (*conflictstore)->confprimalbnds = NULL;
756 (*conflictstore)->dualprimalbnds = NULL;
757 (*conflictstore)->scalefactors = NULL;
758 (*conflictstore)->updateside = NULL;
759 (*conflictstore)->drayrelaxonly = NULL;
760 (*conflictstore)->dsolrelaxonly = NULL;
761 (*conflictstore)->dualrayconfs = NULL;
762 (*conflictstore)->dualsolconfs = NULL;
763 (*conflictstore)->origconfs = NULL;
764 (*conflictstore)->nnzdualrays = 0;
765 (*conflictstore)->nnzdualsols = 0;
766 (*conflictstore)->conflictsize = 0;
767 (*conflictstore)->origconflictsize = 0;
768 (*conflictstore)->nconflicts = 0;
769 (*conflictstore)->ndualrayconfs = 0;
770 (*conflictstore)->ndualsolconfs = 0;
771 (*conflictstore)->norigconfs = 0;
772 (*conflictstore)->ncbconflicts = 0;
773 (*conflictstore)->nconflictsfound = 0;
774 (*conflictstore)->initstoresize = -1;
775 (*conflictstore)->storesize = -1;
776 (*conflictstore)->maxstoresize = -1;
777 (*conflictstore)->ncleanups = 0;
778 (*conflictstore)->lastcutoffbound = SCIP_INVALID;
779 (*conflictstore)->lastnodenum = -1;
780 (*conflictstore)->eventhdlr = SCIPsetFindEventhdlr(set, EVENTHDLR_NAME);
781
782 /* create event handler for LP events */
783 if( (*conflictstore)->eventhdlr == NULL )
784 {
785 SCIP_CALL( SCIPeventhdlrCreate(&(*conflictstore)->eventhdlr, set, EVENTHDLR_NAME, EVENTHDLR_DESC, NULL, NULL,
786 NULL, NULL, eventInitsolConflictstore, eventExitsolConflictstore, NULL, eventExecConflictstore, NULL) );
787 SCIP_CALL( SCIPsetIncludeEventhdlr(set, (*conflictstore)->eventhdlr) );
788 }
789 assert((*conflictstore)->eventhdlr != NULL);
790
791 return SCIP_OKAY;
792}
793
794/** frees conflict store */
796 SCIP_CONFLICTSTORE** conflictstore, /**< pointer to store conflict store */
797 BMS_BLKMEM* blkmem, /**< block memory */
798 SCIP_SET* set, /**< global SCIP settings */
799 SCIP_STAT* stat, /**< dynamic SCIP statistics */
800 SCIP_REOPT* reopt /**< reoptimization data */
801 )
802{
803 assert(conflictstore != NULL);
804 assert(*conflictstore != NULL);
805
806 /* clear the storage */
807 SCIP_CALL( SCIPconflictstoreClear(*conflictstore, blkmem, set, stat, reopt) );
808
809 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->origconfs, (*conflictstore)->origconflictsize);
810 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->conflicts, (*conflictstore)->conflictsize);
811 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->confprimalbnds, (*conflictstore)->conflictsize);
812 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualrayconfs, CONFLICTSTORE_DUALRAYSIZE);
813 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->drayrelaxonly, CONFLICTSTORE_DUALRAYSIZE);
814 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualsolconfs, CONFLICTSTORE_DUALSOLSIZE);
815 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dualprimalbnds, CONFLICTSTORE_DUALSOLSIZE);
816 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->scalefactors, CONFLICTSTORE_DUALSOLSIZE);
817 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->updateside, CONFLICTSTORE_DUALSOLSIZE);
818 BMSfreeBlockMemoryArrayNull(blkmem, &(*conflictstore)->dsolrelaxonly, CONFLICTSTORE_DUALSOLSIZE);
819 BMSfreeMemoryNull(conflictstore);
820
821 return SCIP_OKAY;
822}
823
824/** clears conflict store */
826 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
827 BMS_BLKMEM* blkmem, /**< block memory */
828 SCIP_SET* set, /**< global SCIP settings */
829 SCIP_STAT* stat, /**< dynamic SCIP statistics */
830 SCIP_REOPT* reopt /**< reoptimization data */
831 )
832{
833 int i;
834
835 assert(conflictstore != NULL);
836
837 SCIPsetDebugMsg(set, "clearing conflict store: %d origconfs, %d conflicts, %d dual proofs\n",
838 conflictstore->norigconfs, conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs);
839
840 /* remove original constraints (if present) */
841 if( conflictstore->origconfs != NULL )
842 {
843 for( i = 0; i < conflictstore->norigconfs; i++ )
844 {
845 SCIP_CONS* conflict = conflictstore->origconfs[i];
846 SCIP_CALL( SCIPconsRelease(&conflict, blkmem, set) );
847 }
848 conflictstore->norigconfs = 0;
849 }
850
851 /* clean up storage of conflict constraints */
852 if( conflictstore->conflicts != NULL )
853 {
854 /* we traverse in reverse order to avoid swapping of pointers */
855 for( i = conflictstore->nconflicts-1; i >= 0; i--)
856 {
857 SCIP_CALL( delPosConflict(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
858 }
859 assert(conflictstore->nconflicts == 0);
860 }
861
862 /* clean up storage of proof constraints based on dual rays */
863 if( conflictstore->dualrayconfs != NULL )
864 {
865 /* we traverse in reverse order to avoid swapping of pointers */
866 for( i = conflictstore->ndualrayconfs-1; i >= 0; i-- )
867 {
868 SCIP_CALL( delPosDualray(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
869 }
870 assert(conflictstore->ndualrayconfs == 0);
871 }
872
873 /* clean up storage of proof constraints based on dual solutions */
874 if( conflictstore->dualsolconfs != NULL )
875 {
876 /* we traverse in reverse order to avoid swapping of pointers */
877 for( i = conflictstore->ndualsolconfs-1; i >= 0; i-- )
878 {
879 SCIP_CALL( delPosDualsol(conflictstore, set, stat, NULL, blkmem, reopt, i, FALSE) );
880 }
881 assert(conflictstore->ndualsolconfs == 0);
882 }
883
884 return SCIP_OKAY;
885}
886
887/** cleans up conflict store */
889 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
890 BMS_BLKMEM* blkmem, /**< block memory */
891 SCIP_SET* set, /**< global SCIP settings */
892 SCIP_STAT* stat, /**< dynamic SCIP statistics */
893 SCIP_PROB* transprob, /**< transformed problem */
894 SCIP_REOPT* reopt /**< reoptimization data */
895 )
896{
897 int ndelconfs;
898 int ndeldualray;
899 int ndeldualsol;
900
901 assert(conflictstore != NULL);
902
903 SCIPsetDebugMsg(set, "cleaning conflict store: %d conflicts, %d dual proofs\n",
904 conflictstore->nconflicts, conflictstore->ndualrayconfs + conflictstore->ndualsolconfs);
905
906 ndelconfs = 0;
907 ndeldualray = 0;
908 ndeldualsol = 0;
909
910 /* remove all conflicts that are marked as deleted or where the check flag has changed to TRUE.
911 *
912 * the latter case might happen during processing parallel constraints, e.g., cons_knapsack.c:detectRedundantConstraints().
913 * in that case, the conflict constraint should stay, e.g., it has the stricter capacity, and replaces a model
914 * constraint. hence, the conflict is now a constraint that is needed to stay correct. therefore, the conflictpool
915 * is not allowed to delete this constraint from the entire problem.
916 */
917 SCIP_CALL( cleanDeletedAndCheckedConflicts(conflictstore, set, stat, blkmem, reopt, &ndelconfs) );
918
919 /* remove all dual infeasibility proofs that are marked as deleted or where the check flag has changed to TRUE. */
920 SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeldualray) );
921
922 /* remove all dual bound exceeding proofs that are marked as deleted or where the check flag has changed to TRUE. */
923 SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeldualsol) );
924
925 /* don't update bound exceeding proofs after a restart
926 *
927 * TODO: check whether we want to delete bound exceeding proofs in general during a restart
928 */
929 if( SCIPisInRestart(set->scip) )
930 {
931 int i;
932
933 for( i = conflictstore->ndualrayconfs-1; i >= 0 ; i-- )
934 {
935 if( conflictstore->drayrelaxonly[i] )
936 {
937 SCIP_CALL( delPosDualray(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) );
938 }
939 }
940
941 for( i = conflictstore->ndualsolconfs-1; i >= 0 ; i-- )
942 {
943 if( conflictstore->dsolrelaxonly[i] )
944 {
945 SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) );
946 }
947 else
948 {
949 conflictstore->updateside[i] = FALSE;
950 }
951 }
952 }
953
954 return SCIP_OKAY;
955}
956
957/** adds a constraint to the pool of proof constraints based on dual rays
958 *
959 * @note this methods captures the constraint
960 */
962 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
963 SCIP_CONS* dualproof, /**< constraint based on a dual ray */
964 BMS_BLKMEM* blkmem, /**< block memory */
965 SCIP_SET* set, /**< global SCIP settings */
966 SCIP_STAT* stat, /**< dynamic SCIP statistics */
967 SCIP_PROB* transprob, /**< transformed problem */
968 SCIP_REOPT* reopt, /**< reoptimization data */
969 SCIP_Bool hasrelaxvar /**< does the dual proof contain at least one variable that exists in
970 * the current relaxation only? */
971 )
972{
973 int nvars;
974 SCIP_Bool success;
975
976 assert(conflictstore != NULL);
977 assert(conflictstore->ndualrayconfs <= CONFLICTSTORE_DUALRAYSIZE);
978
979 /* mark the constraint to be a conflict */
980 SCIPconsMarkConflict(dualproof);
981
982 /* create an array to store constraints based on dual rays */
983 if( conflictstore->dualrayconfs == NULL )
984 {
987 }
988
989 /* the store is full, we proceed as follows
990 *
991 * 1. check whether some constraints are marked as deleted and remove those
992 * 2. if no constraint is marked as deleted: remove the oldest
993 */
994 if( conflictstore->ndualrayconfs == CONFLICTSTORE_DUALRAYSIZE )
995 {
996 int ndeleted = 0;
997
998 /* remove all as deleted marked dual infeasibility proofs */
999 SCIP_CALL( cleanDeletedAndCheckedDualrayCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) );
1000
1001 /* if we could not remove a dual ray that is already marked as deleted we need to remove the oldest active one */
1002 if( ndeleted == 0 )
1003 {
1004 SCIP_Bool local = SCIPconsIsLocal(dualproof);
1005 int pos = 0;
1006
1007 /* sort dual rays */
1008 SCIPsortPtrBool((void**)conflictstore->dualrayconfs, conflictstore->drayrelaxonly, compareConss,
1009 conflictstore->ndualrayconfs);
1010 assert(SCIPsetIsGE(set, SCIPconsGetAge(conflictstore->dualrayconfs[0]),
1011 SCIPconsGetAge(conflictstore->dualrayconfs[conflictstore->ndualrayconfs-1])));
1012
1013 while( pos < conflictstore->ndualrayconfs-1 && local != SCIPconsIsLocal(conflictstore->dualrayconfs[pos]) )
1014 pos++;
1015
1016 /* we don't want to keep the dual proof */
1017 if( pos >= conflictstore->ndualrayconfs )
1018 {
1019 SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) );
1020 return SCIP_OKAY;
1021 }
1022
1023 SCIP_CALL( delPosDualray(conflictstore, set, stat, transprob, blkmem, reopt, pos, TRUE) );
1024 }
1025 }
1026
1027 /* add the new constraint based on a dual ray at the last position */
1028 SCIPconsCapture(dualproof);
1029 conflictstore->dualrayconfs[conflictstore->ndualrayconfs] = dualproof;
1030 conflictstore->drayrelaxonly[conflictstore->ndualrayconfs] = hasrelaxvar;
1031 ++conflictstore->ndualrayconfs;
1032
1033 /* add conflict locks */
1035
1036 /* increase the number of non-zeros */
1037 SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) );
1038 assert(success);
1039 conflictstore->nnzdualrays += nvars;
1040
1041 return SCIP_OKAY;
1042}
1043
1044/** adds a constraint to the pool of proof constraints based on dual solutions
1045 *
1046 * @note this methods captures the constraint
1047 */
1049 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1050 SCIP_CONS* dualproof, /**< constraint based on a dual solution */
1051 BMS_BLKMEM* blkmem, /**< block memory */
1052 SCIP_SET* set, /**< global SCIP settings */
1053 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1054 SCIP_PROB* transprob, /**< transformed problem */
1055 SCIP_REOPT* reopt, /**< reoptimization data */
1056 SCIP_Real scale, /**< scaling factor that needs to be considered when updating the side */
1057 SCIP_Bool updateside, /**< should the side be updated if a new incumbent is found */
1058 SCIP_Bool hasrelaxvar /**< does the dual proof contain at least one variable that exists in
1059 * the current relaxation only? */
1060 )
1061{
1062 int nvars;
1063 SCIP_Bool success;
1064
1065 assert(conflictstore != NULL);
1066 assert(conflictstore->ndualsolconfs <= CONFLICTSTORE_DUALSOLSIZE);
1067
1068 /* mark the constraint to be a conflict */
1069 SCIPconsMarkConflict(dualproof);
1070
1071 /* create an array to store constraints based on dual rays */
1072 if( conflictstore->dualsolconfs == NULL )
1073 {
1079 }
1080
1081 /* the store is full, we proceed as follows
1082 *
1083 * 1. check whether some constraints are marked as deleted and remove those
1084 * 2. if no constraint is marked as deleted: remove the oldest
1085 */
1086 if( conflictstore->ndualsolconfs == CONFLICTSTORE_DUALSOLSIZE )
1087 {
1088 int ndeleted = 0;
1089
1090 /* remove all as deleted marked dual bound exceeding proofs */
1091 SCIP_CALL( cleanDeletedAndCheckedDualsolCons(conflictstore, set, stat, blkmem, reopt, &ndeleted) );
1092
1093 /* if we could not remove a dual proof that is already marked as deleted we need to remove the oldest active one */
1094 if( ndeleted == 0 )
1095 {
1096 SCIP_Bool local = SCIPconsIsLocal(dualproof);
1097 int pos = 0;
1098
1099 /* sort dual rays */
1100 SCIPsortPtrRealRealBoolBool((void**)conflictstore->dualsolconfs, conflictstore->dualprimalbnds,
1101 conflictstore->scalefactors, conflictstore->updateside, conflictstore->dsolrelaxonly,
1102 compareConss, conflictstore->ndualsolconfs);
1103 assert(SCIPsetIsGE(set, SCIPconsGetAge(conflictstore->dualsolconfs[0]),
1104 SCIPconsGetAge(conflictstore->dualsolconfs[conflictstore->ndualsolconfs-1])));
1105
1106 while( pos < conflictstore->ndualsolconfs-1 && local != SCIPconsIsLocal(conflictstore->dualsolconfs[pos]) )
1107 pos++;
1108
1109 /* we don't want to keep the dual proof */
1110 if( pos >= conflictstore->ndualsolconfs )
1111 {
1112 SCIP_CALL( SCIPconsDelete(dualproof, blkmem, set, stat, transprob, reopt) );
1113 return SCIP_OKAY;
1114 }
1115
1116 SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, pos, TRUE) );
1117 }
1118 }
1119
1120 /* add the new constraint based on a dual solution at the last position */
1121 SCIPconsCapture(dualproof);
1122 conflictstore->dualsolconfs[conflictstore->ndualsolconfs] = dualproof;
1123 conflictstore->dualprimalbnds[conflictstore->ndualsolconfs] = SCIPgetCutoffbound(set->scip) - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0);
1124 conflictstore->scalefactors[conflictstore->ndualsolconfs] = scale;
1125 conflictstore->updateside[conflictstore->ndualsolconfs] = updateside;
1126 conflictstore->dsolrelaxonly[conflictstore->ndualsolconfs] = hasrelaxvar;
1127 ++conflictstore->ndualsolconfs;
1128
1129 /* add conflict locks */
1131
1132 /* increase the number of non-zeros */
1133 SCIP_CALL( SCIPconsGetNVars(dualproof, set, &nvars, &success) );
1134 assert(success);
1135 conflictstore->nnzdualsols += nvars;
1136
1137 return SCIP_OKAY;
1138}
1139
1140/** adds a conflict to the conflict store
1141 *
1142 * @note this method captures the constraint
1143 */
1145 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1146 BMS_BLKMEM* blkmem, /**< block memory */
1147 SCIP_SET* set, /**< global SCIP settings */
1148 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1149 SCIP_TREE* tree, /**< branch and bound tree (or NULL for an original constraint) */
1150 SCIP_PROB* transprob, /**< transformed problem (or NULL for an original constraint) */
1151 SCIP_REOPT* reopt, /**< reoptimization data */
1152 SCIP_CONS* cons, /**< constraint representing the conflict */
1153 SCIP_CONFTYPE conftype, /**< type of the conflict */
1154 SCIP_Bool cutoffinvolved, /**< is a cutoff bound involved in this conflict */
1155 SCIP_Real primalbound /**< primal bound the conflict depend on (or -SCIPinfinity) */
1156 )
1157{
1158 SCIP_Longint curnodenum;
1159 int nconflicts;
1160
1161 assert(conflictstore != NULL);
1162 assert(blkmem != NULL);
1163 assert(set != NULL);
1164 assert(stat != NULL);
1165 assert(tree != NULL || SCIPconsIsOriginal(cons));
1166 assert(transprob != NULL || SCIPconsIsOriginal(cons));
1167 assert(cons != NULL);
1168 assert(conftype != SCIP_CONFTYPE_BNDEXCEEDING || cutoffinvolved);
1169 assert(!cutoffinvolved || !SCIPsetIsInfinity(set, REALABS(primalbound)));
1170
1171 /* mark the constraint to be a conflict */
1173
1174 /* add the constraint to a special store */
1175 if( SCIPconsIsOriginal(cons) )
1176 {
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 */
1227
1228#ifdef SCIP_PRINT_DETAILS
1229 SCIPsetDebugMsg(set, "add conflict <%s> to conflict store at position %d\n", SCIPconsGetName(cons), conflictstore->nconflicts-1);
1230 SCIPsetDebugMsg(set, " -> conflict type: %d, cutoff involved = %u\n", conftype, cutoffinvolved);
1231 if( cutoffinvolved )
1232 SCIPsetDebugMsg(set, " -> current primal bound: %g\n", primalbound);
1233#endif
1234
1235 return SCIP_OKAY;
1236}
1237
1238/** deletes all conflicts depending on a cutoff bound larger than the given bound */
1240 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1241 SCIP_SET* set, /**< global SCIP settings */
1242 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1243 BMS_BLKMEM* blkmem, /**< block memory */
1244 SCIP_PROB* transprob, /**< transformed problem*/
1245 SCIP_REOPT* reopt, /**< reoptimization data */
1246 SCIP_Real cutoffbound /**< current cutoff bound */
1247 )
1248{
1249 SCIP_Real improvement;
1250 int ndelconfs;
1251 int nchgsides;
1252 int i;
1253
1254 assert(conflictstore != NULL);
1255 assert(set != NULL);
1256 assert(stat != NULL);
1257 assert(blkmem != NULL);
1258 assert(transprob != NULL);
1259
1260 /* return if we do not want to use the storage */
1261 if( set->conf_maxstoresize == 0 )
1262 return SCIP_OKAY;
1263
1264 /* return if we do not want to remove conflicts related to an older cutoff bound */
1265 if( !set->conf_cleanbnddepend )
1266 return SCIP_OKAY;
1267
1268 /* there is nothing to clean */
1269 if( conflictstore->ndualsolconfs == 0 && conflictstore->nconflicts == 0 )
1270 return SCIP_OKAY;
1271
1272 /* we can stop whenever we have found a new incumbent but the cutoff bound has not changed */
1273 if( conflictstore->lastcutoffbound != SCIP_INVALID && SCIPsetIsGE(set, cutoffbound, conflictstore->lastcutoffbound) ) /*lint !e777*/
1274 return SCIP_OKAY;
1275
1276 conflictstore->lastcutoffbound = cutoffbound;
1277
1278 /* calculate scalar to determine whether the old primal bound is worse enough to remove the conflict */
1279 if( SCIPsetIsPositive(set, cutoffbound) )
1280 improvement = (1 - set->conf_minimprove);
1281 else
1282 improvement = (1 + set->conf_minimprove);
1283
1284 /* remove all conflicts depending on a primalbound*improvement > cutoffbound
1285 *
1286 * note: we cannot remove conflicts that are marked as deleted because at this point in time we would destroy
1287 * the internal data structure
1288 */
1289 ndelconfs = 0;
1290 for( i = 0; i < conflictstore->nconflicts; )
1291 {
1292 assert(conflictstore->conflicts[i] != NULL);
1293
1294 /* check if the conflict depends on the cutoff bound */
1295 if( SCIPsetIsGT(set, improvement * conflictstore->confprimalbnds[i], cutoffbound) )
1296 {
1297 /* remove conflict at current position
1298 *
1299 * don't increase i because delPosConflict will swap the last pointer to the i-th position
1300 */
1301 SCIP_CALL( delPosConflict(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) );
1302 ++ndelconfs;
1303 }
1304 else
1305 /* increase i */
1306 ++i;
1307 }
1308 assert(conflictstore->ncbconflicts >= 0);
1309 assert(conflictstore->nconflicts >= 0);
1310
1311 SCIPsetDebugMsg(set, "-> removed %d/%d conflicts, %d depending on cutoff bound\n", ndelconfs,
1312 conflictstore->nconflicts+ndelconfs, ndelconfs);
1313
1314 ndelconfs = 0;
1315 nchgsides = 0;
1316 /* update all proof constraints based on a dual solution */
1317 for( i = 0; i < conflictstore->ndualsolconfs; )
1318 {
1319 SCIP_CONSHDLR* conshdlr;
1320 SCIP_CONS* dualproof;
1321
1322 dualproof = conflictstore->dualsolconfs[i];
1323 assert(dualproof != NULL);
1324
1325 if( SCIPconsIsDeleted(dualproof) )
1326 {
1327 ++i;
1328 continue;
1329 }
1330 if( !conflictstore->updateside[i] || SCIPsetIsLE(set, improvement * conflictstore->dualprimalbnds[i], cutoffbound) )
1331 {
1332 ++i;
1333 continue;
1334 }
1335 conshdlr = SCIPconsGetHdlr(dualproof);
1336 assert(conshdlr != NULL);
1337
1338 if( strcmp(SCIPconshdlrGetName(conshdlr), "linear") == 0 )
1339 {
1340 SCIP_Real rhs;
1341 SCIP_Real newside;
1342
1343 assert(SCIPsetIsGT(set, conflictstore->dualprimalbnds[i], cutoffbound));
1344
1345 rhs = SCIPgetRhsLinear(set->scip, dualproof);
1346
1347 if( !SCIPsetIsInfinity(set, rhs) )
1348 {
1349 assert(SCIPsetIsInfinity(set, -SCIPgetLhsLinear(set->scip, dualproof)));
1350 assert(SCIPsetIsPositive(set, conflictstore->scalefactors[i]));
1351
1352 /* get unscaled rhs */
1353 newside = rhs * conflictstore->scalefactors[i];
1354 newside -= conflictstore->dualprimalbnds[i];
1355 newside += cutoffbound - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0);
1356
1357 /* scale rhs */
1358 newside /= conflictstore->scalefactors[i];
1359
1360 SCIP_CALL( SCIPchgRhsLinear(set->scip, dualproof, newside) );
1361 }
1362 else
1363 {
1364 SCIP_Real lhs;
1365
1366 lhs = SCIPgetLhsLinear(set->scip, dualproof);
1367 assert(!SCIPsetIsInfinity(set, -lhs));
1368 assert(SCIPsetIsNegative(set, conflictstore->scalefactors[i]));
1369
1370 /* get unscaled lhs */
1371 newside = lhs * conflictstore->scalefactors[i];
1372 newside += conflictstore->dualprimalbnds[i];
1373 newside -= (cutoffbound - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0));
1374
1375 /* scale lhs */
1376 newside /= conflictstore->scalefactors[i];
1377
1378 SCIP_CALL( SCIPchgLhsLinear(set->scip, dualproof, newside) );
1379 }
1380
1381 ++nchgsides;
1382
1383 conflictstore->dualprimalbnds[i] = cutoffbound - (SCIPprobIsObjIntegral(transprob) ? SCIPsetCutoffbounddelta(set) : 0.0);
1384
1385 ++i;
1386 }
1387 else if( SCIPsetIsGT(set, improvement * conflictstore->dualprimalbnds[i], cutoffbound) )
1388 {
1389 /* remove conflict at current position
1390 *
1391 * don't increase i because delPosDualsol will swap the last pointer to the i-th position
1392 */
1393 SCIP_CALL( delPosDualsol(conflictstore, set, stat, transprob, blkmem, reopt, i, TRUE) );
1394 ++ndelconfs;
1395 }
1396 else
1397 /* increase i */
1398 ++i;
1399 }
1400
1401 SCIPsetDebugMsg(set, "-> changed %d sides of dual solution constraints\n", nchgsides);
1402 SCIPsetDebugMsg(set, "-> deleted %d dual solution constraints\n", ndelconfs);
1403
1404 return SCIP_OKAY;
1405}
1406
1407/** returns the maximal size of the conflict pool */
1409 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1410 )
1411{
1412 assert(conflictstore != NULL);
1413
1414 return MIN(conflictstore->storesize, conflictstore->maxstoresize);
1415}
1416
1417/** returns the initial size of the conflict pool */
1419 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1420 )
1421{
1422 assert(conflictstore != NULL);
1423
1424 return conflictstore->initstoresize;
1425}
1426
1427/** returns the number of stored conflicts on the conflict pool
1428 *
1429 * @note the number of active conflicts can be less
1430 */
1432 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1433 )
1434{
1435 assert(conflictstore != NULL);
1436
1437 return conflictstore->nconflicts;
1438}
1439
1440/** returns all active conflicts stored in the conflict store */
1442 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1443 SCIP_CONS** conflicts, /**< array to store conflicts */
1444 int conflictsize, /**< size of the conflict array */
1445 int* nconflicts /**< pointer to store the number of conflicts */
1446 )
1447{
1448 int i;
1449
1450 assert(conflictstore != NULL);
1451
1452 /* return if the allocated memory is obviously to small */
1453 if( conflictstore->nconflicts > conflictsize )
1454 {
1455 (*nconflicts) = conflictstore->nconflicts;
1456 return SCIP_OKAY;
1457 }
1458
1459 (*nconflicts) = 0;
1460 for( i = 0; i < conflictstore->nconflicts; i++ )
1461 {
1462 SCIP_CONS* conflict;
1463
1464 conflict = conflictstore->conflicts[i];
1465 assert(conflict != NULL);
1466
1467 /* skip deactivated and deleted constraints */
1468 if( !SCIPconsIsActive(conflict) || SCIPconsIsDeleted(conflict) )
1469 continue;
1470
1471 /* count exact number conflicts */
1472 if( *nconflicts > conflictsize )
1473 ++(*nconflicts);
1474 else
1475 {
1476 conflicts[*nconflicts] = conflict;
1477 ++(*nconflicts);
1478 }
1479 }
1480
1481 return SCIP_OKAY;
1482}
1483
1484/** transformes all original conflicts into transformed conflicts */
1486 SCIP_CONFLICTSTORE* conflictstore, /**< conflict store */
1487 BMS_BLKMEM* blkmem, /**< block memory */
1488 SCIP_SET* set, /**< global SCIP settings */
1489 SCIP_STAT* stat, /**< dynamic SCIP statistics */
1490 SCIP_TREE* tree, /**< branch and bound tree */
1491 SCIP_PROB* transprob, /**< transformed problem */
1492 SCIP_REOPT* reopt /**< reoptimization data */
1493 )
1494{
1495 int ntransconss;
1496 int i;
1497
1498 assert(conflictstore != NULL);
1499 assert(set != NULL);
1501
1502 /* return if no original constraints are stored */
1503 if( conflictstore->norigconfs == 0 )
1504 return SCIP_OKAY;
1505
1506 ntransconss = 0;
1507
1508 for( i = 0; i < conflictstore->norigconfs; i++ )
1509 {
1510 SCIP_CONS* transcons;
1511
1512 assert(conflictstore->origconfs[i] != NULL);
1513 assert(SCIPconsIsOriginal(conflictstore->origconfs[i]));
1514
1515 transcons = SCIPconsGetTransformed(conflictstore->origconfs[i]);
1516
1517 if( transcons != NULL )
1518 {
1519 SCIP_CALL( SCIPconflictstoreAddConflict(conflictstore, blkmem, set, stat, tree, transprob, reopt, transcons, \
1521
1522 ++ntransconss;
1523 }
1524
1525 SCIP_CALL( SCIPconsRelease(&conflictstore->origconfs[i], blkmem, set) );
1526 }
1527
1528 SCIPsetDebugMsg(set, "-> transform %d/%d conflicts into transformed space\n", ntransconss, conflictstore->norigconfs);
1529
1530 conflictstore->norigconfs = 0;
1531
1532 return SCIP_OKAY;
1533}
1534
1535/** returns the average number of non-zeros over all stored dual ray constraints */
1537 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1538 )
1539{
1540 assert(conflictstore != NULL);
1541
1542 if( conflictstore->ndualrayconfs == 0 )
1543 return 0.0;
1544 else
1545 return (SCIP_Real) conflictstore->nnzdualrays / ((SCIP_Real) conflictstore->ndualrayconfs);
1546}
1547
1548/** returns the number of all stored dual ray constraints */
1550 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1551 )
1552{
1553 assert(conflictstore != NULL);
1554
1555 return conflictstore->ndualrayconfs;
1556}
1557
1558/** returns the average number of non-zeros over all stored boundexceeding proofs */
1560 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1561 )
1562{
1563 assert(conflictstore != NULL);
1564 assert(conflictstore->ndualsolconfs >= 0);
1565
1566 if( conflictstore->ndualsolconfs == 0 )
1567 return 0.0;
1568 else
1569 return (SCIP_Real) conflictstore->nnzdualsols / ((SCIP_Real) conflictstore->ndualsolconfs);
1570}
1571
1572/** returns the number of all stored boundexceeding proofs */
1574 SCIP_CONFLICTSTORE* conflictstore /**< conflict store */
1575 )
1576{
1577 assert(conflictstore != NULL);
1578
1579 return conflictstore->ndualsolconfs;
1580}
1581
static SCIP_DECL_EVENTEXITSOL(eventExitsolConflictstore)
#define CONFLICTSTORE_DUALSOLSIZE
Definition: conflictstore.c:51
SCIP_RETCODE SCIPconflictstoreTransform(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_REOPT *reopt)
#define CONFLICTSTORE_DUALRAYSIZE
Definition: conflictstore.c:50
#define CONFLICTSTORE_MAXSIZE
Definition: conflictstore.c:53
static SCIP_RETCODE conflictstoreCleanUpStorage(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt)
SCIP_RETCODE SCIPconflictstoreAddDualraycons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Bool hasrelaxvar)
static SCIP_RETCODE conflictstoreAddOrigConflict(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, BMS_BLKMEM *blkmem, SCIP_CONS *cons)
static SCIP_RETCODE initConflictstore(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_PROB *transprob)
int SCIPconflictstoreGetNDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
SCIP_Real SCIPconflictstoreGetAvgNnzDualInfProofs(SCIP_CONFLICTSTORE *conflictstore)
SCIP_RETCODE SCIPconflictstoreCleanNewIncumbent(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Real cutoffbound)
static SCIP_RETCODE delPosConflict(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
static SCIP_RETCODE cleanDeletedAndCheckedDualsolCons(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelproofs)
static SCIP_RETCODE cleanDeletedAndCheckedConflicts(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelconfs)
static void adjustStorageSize(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set)
SCIP_RETCODE SCIPconflictstoreClear(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
int SCIPconflictstoreGetMaxPoolSize(SCIP_CONFLICTSTORE *conflictstore)
int SCIPconflictstoreGetNDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
static SCIP_RETCODE cleanDeletedAndCheckedDualrayCons(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int *ndelproofs)
SCIP_RETCODE SCIPconflictstoreFree(SCIP_CONFLICTSTORE **conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_REOPT *reopt)
static SCIP_DECL_EVENTINITSOL(eventInitsolConflictstore)
Definition: conflictstore.c:81
SCIP_RETCODE SCIPconflictstoreGetConflicts(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS **conflicts, int conflictsize, int *nconflicts)
#define EVENTHDLR_DESC
Definition: conflictstore.c:59
int SCIPconflictstoreGetNConflictsInStore(SCIP_CONFLICTSTORE *conflictstore)
SCIP_RETCODE SCIPconflictstoreClean(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt)
static SCIP_RETCODE conflictstoreEnsureMem(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, BMS_BLKMEM *blkmem, int num)
SCIP_Real SCIPconflictstoreGetAvgNnzDualBndProofs(SCIP_CONFLICTSTORE *conflictstore)
static SCIP_DECL_SORTPTRCOMP(compareConss)
#define CONFLICTSTORE_SORTFREQ
Definition: conflictstore.c:55
static SCIP_RETCODE delPosDualray(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
#define CONFLICTSTORE_MINSIZE
Definition: conflictstore.c:52
static SCIP_RETCODE delPosDualsol(SCIP_CONFLICTSTORE *conflictstore, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, BMS_BLKMEM *blkmem, SCIP_REOPT *reopt, int pos, SCIP_Bool deleteconflict)
SCIP_RETCODE SCIPconflictstoreAddDualsolcons(SCIP_CONFLICTSTORE *conflictstore, SCIP_CONS *dualproof, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_Real scale, SCIP_Bool updateside, SCIP_Bool hasrelaxvar)
#define EVENTHDLR_NAME
Definition: conflictstore.c:58
SCIP_RETCODE SCIPconflictstoreCreate(SCIP_CONFLICTSTORE **conflictstore, SCIP_SET *set)
SCIP_RETCODE SCIPconflictstoreAddConflict(SCIP_CONFLICTSTORE *conflictstore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_TREE *tree, SCIP_PROB *transprob, SCIP_REOPT *reopt, SCIP_CONS *cons, SCIP_CONFTYPE conftype, SCIP_Bool cutoffinvolved, SCIP_Real primalbound)
static SCIP_DECL_EVENTEXEC(eventExecConflictstore)
Definition: conflictstore.c:64
#define CONFLICTSTORE_SIZE
Definition: conflictstore.c:54
int SCIPconflictstoreGetInitPoolSize(SCIP_CONFLICTSTORE *conflictstore)
internal methods for storing conflicts
SCIP_RETCODE SCIPconsAddLocks(SCIP_CONS *cons, SCIP_SET *set, SCIP_LOCKTYPE locktype, int nlockspos, int nlocksneg)
Definition: cons.c:7378
void SCIPconsMarkConflict(SCIP_CONS *cons)
Definition: cons.c:7120
void SCIPconsCapture(SCIP_CONS *cons)
Definition: cons.c:6254
SCIP_RETCODE SCIPconsGetNVars(SCIP_CONS *cons, SCIP_SET *set, int *nvars, SCIP_Bool *success)
Definition: cons.c:6381
SCIP_RETCODE SCIPconsDelete(SCIP_CONS *cons, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_PROB *prob, SCIP_REOPT *reopt)
Definition: cons.c:6479
SCIP_RETCODE SCIPconsRelease(SCIP_CONS **cons, BMS_BLKMEM *blkmem, SCIP_SET *set)
Definition: cons.c:6266
SCIP_CONS * SCIPconsGetTransformed(SCIP_CONS *cons)
Definition: cons.c:6848
internal methods for constraints and constraint handlers
Constraint handler for linear constraints in their most general form, .
common defines and data types used in all packages of SCIP
#define NULL
Definition: def.h:267
#define SCIP_Longint
Definition: def.h:158
#define SCIP_INVALID
Definition: def.h:193
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_ALLOC(x)
Definition: def.h:385
#define SCIP_Real
Definition: def.h:173
#define SCIP_UNKNOWN
Definition: def.h:194
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPeventhdlrCreate(SCIP_EVENTHDLR **eventhdlr, SCIP_SET *set, const char *name, const char *desc, SCIP_DECL_EVENTCOPY((*eventcopy)), SCIP_DECL_EVENTFREE((*eventfree)), SCIP_DECL_EVENTINIT((*eventinit)), SCIP_DECL_EVENTEXIT((*eventexit)), SCIP_DECL_EVENTINITSOL((*eventinitsol)), SCIP_DECL_EVENTEXITSOL((*eventexitsol)), SCIP_DECL_EVENTDELETE((*eventdelete)), SCIP_DECL_EVENTEXEC((*eventexec)), SCIP_EVENTHDLRDATA *eventhdlrdata)
Definition: event.c:123
internal methods for managing events
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_RETCODE SCIPclearConflictStore(SCIP *scip, SCIP_EVENT *event)
Definition: scip_prob.c:3286
SCIP_RETCODE SCIPgetBoolParam(SCIP *scip, const char *name, SCIP_Bool *value)
Definition: scip_param.c:250
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPgetConsNVars(SCIP *scip, SCIP_CONS *cons, int *nvars, SCIP_Bool *success)
Definition: scip_cons.c:2622
SCIP_Real SCIPconsGetAge(SCIP_CONS *cons)
Definition: cons.c:8373
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8234
SCIP_Bool SCIPconsIsOriginal(SCIP_CONS *cons)
Definition: cons.c:8513
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8413
SCIP_Bool SCIPconsIsDeleted(SCIP_CONS *cons)
Definition: cons.c:8343
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8453
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
const char * SCIPeventhdlrGetName(SCIP_EVENTHDLR *eventhdlr)
Definition: event.c:324
SCIP_EVENTTYPE SCIPeventGetType(SCIP_EVENT *event)
Definition: event.c:1030
SCIP_RETCODE SCIPcatchEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int *filterpos)
Definition: scip_event.c:286
SCIP_RETCODE SCIPdropEvent(SCIP *scip, SCIP_EVENTTYPE eventtype, SCIP_EVENTHDLR *eventhdlr, SCIP_EVENTDATA *eventdata, int filterpos)
Definition: scip_event.c:320
SCIP_Longint SCIPnodeGetNumber(SCIP_NODE *node)
Definition: tree.c:7493
SCIP_Bool SCIPisInRestart(SCIP *scip)
Definition: scip_solve.c:3591
SCIP_Real SCIPgetCutoffbound(SCIP *scip)
void SCIPsortPtrRealRealBoolBool(void **ptrarray, SCIP_Real *realarray1, SCIP_Real *realarray2, SCIP_Bool *boolarray1, SCIP_Bool *boolarray2, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortPtrBool(void **ptrarray, SCIP_Bool *boolarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
void SCIPsortPtrReal(void **ptrarray, SCIP_Real *realarray, SCIP_DECL_SORTPTRCOMP((*ptrcomp)), int len)
#define BMSfreeBlockMemoryArrayNull(mem, ptr, num)
Definition: memory.h:468
#define BMSfreeMemoryNull(ptr)
Definition: memory.h:146
#define BMSallocBlockMemoryArray(mem, ptr, num)
Definition: memory.h:454
#define BMSreallocBlockMemoryArray(mem, ptr, oldnum, newnum)
Definition: memory.h:458
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
#define BMSallocMemory(ptr)
Definition: memory.h:118
internal miscellaneous methods
int SCIPprobGetNConss(SCIP_PROB *prob)
Definition: prob.c:2447
SCIP_Bool SCIPprobIsObjIntegral(SCIP_PROB *prob)
Definition: prob.c:2338
int SCIPprobGetNVars(SCIP_PROB *prob)
Definition: prob.c:2393
internal methods for storing and manipulating the main problem
data structures and methods for collecting reoptimization information
SCIP callable library.
SCIP_Bool SCIPsetIsGE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6293
SCIP_Bool SCIPsetIsPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6322
SCIP_Bool SCIPsetIsLE(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6257
SCIP_STAGE SCIPsetGetStage(SCIP_SET *set)
Definition: set.c:2952
SCIP_Real SCIPsetInfinity(SCIP_SET *set)
Definition: set.c:6064
SCIP_RETCODE SCIPsetGetIntParam(SCIP_SET *set, const char *name, int *value)
Definition: set.c:3137
SCIP_RETCODE SCIPsetIncludeEventhdlr(SCIP_SET *set, SCIP_EVENTHDLR *eventhdlr)
Definition: set.c:4729
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6199
SCIP_Bool SCIPsetIsGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6275
SCIP_Real SCIPsetCutoffbounddelta(SCIP_SET *set)
Definition: set.c:6164
SCIP_EVENTHDLR * SCIPsetFindEventhdlr(SCIP_SET *set, const char *name)
Definition: set.c:4752
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5764
SCIP_Bool SCIPsetIsNegative(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6333
internal methods for global SCIP settings
#define SCIPsetDebugMsg
Definition: set.h:1784
Definition: heur_padm.c:135
SCIP_NODE * SCIPtreeGetFocusNode(SCIP_TREE *tree)
Definition: tree.c:8360
internal methods for branch and bound tree
@ SCIP_CONFTYPE_BNDEXCEEDING
Definition: type_conflict.h:62
@ SCIP_CONFTYPE_UNKNOWN
Definition: type_conflict.h:59
enum SCIP_ConflictType SCIP_CONFTYPE
Definition: type_conflict.h:66
#define SCIP_EVENTTYPE_BESTSOLFOUND
Definition: type_event.h:105
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_PROBLEM
Definition: type_set.h:45
@ SCIP_STAGE_PRESOLVING
Definition: type_set.h:49
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
@ SCIP_STAGE_TRANSFORMING
Definition: type_set.h:46
@ SCIP_LOCKTYPE_CONFLICT
Definition: type_var.h:98