Scippy

SCIP

Solving Constraint Integer Programs

cutpool.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 cutpool.c
26 * @ingroup OTHER_CFILES
27 * @brief methods for storing cuts in a cut pool
28 * @author Tobias Achterberg
29 * @author Stefan Heinz
30 * @author Gerald Gamrath
31 * @author Marc Pfetsch
32 * @author Kati Wolter
33 */
34
35/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
36
37#include <assert.h>
38
39#include "scip/def.h"
40#include "scip/set.h"
41#include "scip/stat.h"
42#include "scip/clock.h"
43#include "scip/lp.h"
44#include "scip/cons.h"
45#include "scip/sepa.h"
46#include "scip/sepastore.h"
47#include "scip/cutpool.h"
48#include "scip/pub_message.h"
49#include "scip/pub_misc.h"
50
51#include "scip/struct_cutpool.h"
52
53
54
55/*
56 * Hash functions
57 */
58
59/** gets the hash key of a cut */
60static
62{ /*lint --e{715}*/
63 SCIP_CUT* cut;
64
65 cut = (SCIP_CUT*)elem;
66 assert(cut != NULL);
67 assert(cut->row != NULL);
68
69 /* the key of a cut is the row */
70 return cut->row;
71}
72
73/** returns TRUE iff both cuts are identical */
74static
76{ /*lint --e{715}*/
77 SCIP_ROW* row1;
78 SCIP_ROW* row2;
79 SCIP_Real row1scale;
80 SCIP_Real row2scale;
82
83 row1 = (SCIP_ROW*)key1;
84 row2 = (SCIP_ROW*)key2;
85 assert(row1 != NULL);
86 assert(row2 != NULL);
87
88 /* return true if the row is the same */
89 if( row1 == row2 )
90 return TRUE;
91
92 assert(row1->validminmaxidx);
93 assert(row2->validminmaxidx);
94
95 /* compare the trivial characteristics of the rows */
96 if( row1->len != row2->len
97 || row1->minidx != row2->minidx
98 || row1->maxidx != row2->maxidx
99 )
100 return FALSE;
101
102 set = (SCIP_SET*) userptr;
103
104 /* set scale for the rows such that the largest absolute coefficient is 1.0 */
105 row1scale = 1.0 / SCIProwGetMaxval(row1, set);
106 row2scale = 1.0 / SCIProwGetMaxval(row2, set);
107
108 /* check if scaled min value is feas equal first */
109 if( !SCIPsetIsFeasEQ(set, row1scale * SCIProwGetMinval(row1, set),
110 row2scale * SCIProwGetMinval(row2, set)) )
111 return FALSE;
112
113 SCIProwSort(row1);
114 assert(row1->lpcolssorted);
115 assert(row1->nonlpcolssorted);
116
117 SCIProwSort(row2);
118 assert(row2->lpcolssorted);
119 assert(row2->nonlpcolssorted);
120
121 /* currently we are only handling rows which are completely linked or not linked at all */
122 assert(row1->nunlinked == 0 || row1->nlpcols == 0);
123 assert(row2->nunlinked == 0 || row2->nlpcols == 0);
124
125 /* set scale sign such that the rows are of the form ax <= b */
126 if( SCIPsetIsInfinity(set, row1->rhs) )
127 row1scale = -row1scale;
128 if( SCIPsetIsInfinity(set, row2->rhs) )
129 row2scale = -row2scale;
130
131 /* both rows have LP columns, or none of them has, or one has only LP colums and the other only non-LP columns,
132 * so we can rely on the sorting of the columns
133 */
134 if( (row1->nlpcols == 0) == (row2->nlpcols == 0)
135 || (row1->nlpcols == 0 && row2->nlpcols == row2->len)
136 || (row1->nlpcols == row1->len && row2->nlpcols == 0) )
137 {
138 int i;
139
140 if( (row1->nlpcols == 0) == (row2->nlpcols == 0) )
141 {
142#ifndef NDEBUG
143 /* in debug mode, we check that we can rely on the partition into LP columns and non-LP columns */
144 int i2;
145
146 i = 0;
147 i2 = row2->nlpcols;
148 while( i < row1->nlpcols && i2 < row2->len )
149 {
150 assert(row1->cols[i] != row2->cols[i2]);
151 if( row1->cols_index[i] < row2->cols_index[i2] )
152 ++i;
153 else
154 {
155 assert(row1->cols_index[i] > row2->cols_index[i2]);
156 ++i2;
157 }
158 }
159 assert(i == row1->nlpcols || i2 == row2->len);
160
161 i = row1->nlpcols;
162 i2 = 0;
163 while( i < row1->len && i2 < row2->nlpcols )
164 {
165 assert(row1->cols[i] != row2->cols[i2]);
166 if( row1->cols_index[i] < row2->cols_index[i2] )
167 ++i;
168 else
169 {
170 assert(row1->cols_index[i] > row2->cols_index[i2]);
171 ++i2;
172 }
173 }
174 assert(i == row1->len || i2 == row2->nlpcols);
175#endif
176
177 /* both rows are linked and the number of lpcolumns is not equal so they cannot be equal */
178 if( row1->nlpcols != row2->nlpcols )
179 return FALSE;
180 }
181
182 /* compare the columns of the rows */
183 for( i = 0; i < row1->len; ++i )
184 {
185 if( row1->cols_index[i] != row2->cols_index[i] )
186 return FALSE;
187 }
188
189 /* compare the coefficients of the rows */
190 for( i = 0; i < row1->len; ++i )
191 {
192 if( !SCIPsetIsFeasEQ(set, row1scale * row1->vals[i], row2scale * row2->vals[i]) )
193 return FALSE;
194 }
195 }
196 /* one row has LP columns, but the other not, that could be because the one without was just created and isn't
197 * linked yet; in this case, one column could be an LP column in one row and a non-LP column in the other row, so we
198 * cannot rely on the partition; thus, we iteratively check whether the next column of row1 is either the next LP
199 * column of row2 or the next non-LP column of row2 and the coefficients are equal
200 */
201 else
202 {
203 int i1;
204 int ilp;
205 int inlp;
206
207 /* ensure that row1 is the row without LP columns, switch the rows, if neccessary */
208 if( row2->nlpcols == 0 )
209 {
210 SCIP_ROW* tmprow;
211 SCIP_Real tmpscale;
212
213 tmprow = row2;
214 row2 = row1;
215 row1 = tmprow;
216
217 tmpscale = row2scale;
218 row2scale = row1scale;
219 row1scale = tmpscale;
220 }
221 assert(row1->nlpcols == 0 && row2->nlpcols > 0);
222
223 ilp = 0;
224 inlp = row2->nlpcols;
225
226 /* compare the columns and coefficients of the rows */
227 for( i1 = 0; i1 < row1->len; ++i1 )
228 {
229 /* current column of row1 is the current LP column of row2, check the coefficient */
230 if( ilp < row2->nlpcols && row1->cols[i1] == row2->cols[ilp] )
231 {
232 if( !SCIPsetIsFeasEQ(set, row1scale * row1->vals[i1], row2scale * row2->vals[ilp]) )
233 return FALSE;
234 else
235 ++ilp;
236 }
237 /* current column of row1 is the current non-LP column of row2, check the coefficient */
238 else if( inlp < row2->len && row1->cols[i1] == row2->cols[inlp] )
239 {
240 if( !SCIPsetIsFeasEQ(set, row1scale * row1->vals[i1], row2scale * row2->vals[inlp]) )
241 return FALSE;
242 else
243 ++inlp;
244 }
245 /* current column of row1 is neither the current LP column of row2, nor the current non-LP column of row 2 */
246 else
247 return FALSE;
248 }
249 }
250
251 return TRUE;
252}
253
254static
256{ /*lint --e{715}*/
257 SCIP_ROW* row;
258 int i;
259 SCIP_Real scale;
260 SCIP_SET* set;
261 uint64_t hash;
262
263 set = (SCIP_SET*) userptr;
264 row = (SCIP_ROW*)key;
265 assert(row != NULL);
266 assert(row->len > 0);
267
268 scale = 1.0 / SCIProwGetMaxval(row, set);
269 if( SCIPsetIsInfinity(set, row->rhs) )
270 scale = -scale;
271
272 hash = (uint64_t) (long) row->len;
273
274 for( i = 0; i < row->len; ++i )
275 {
276 SCIP_Real val = scale * row->vals[i];
277
278 hash += SCIPhashTwo(SCIPrealHashCode(val), row->cols_index[i]);
279 }
280
281 return hash;
282}
283
284
285/*
286 * dynamic memory arrays
287 */
288
289/** resizes cuts array to be able to store at least num entries */
290static
292 SCIP_CUTPOOL* cutpool, /**< cut pool */
293 SCIP_SET* set, /**< global SCIP settings */
294 int num /**< minimal number of slots in array */
295 )
296{
297 assert(cutpool != NULL);
298 assert(set != NULL);
299
300 if( num > cutpool->cutssize )
301 {
302 int newsize;
303
304 newsize = SCIPsetCalcMemGrowSize(set, num);
305 SCIP_ALLOC( BMSreallocMemoryArray(&cutpool->cuts, newsize) );
306 cutpool->cutssize = newsize;
307 }
308 assert(num <= cutpool->cutssize);
309
310 return SCIP_OKAY;
311}
312
313
314
315/*
316 * Cut methods
317 */
318
319/** creates a cut and captures the row */
320static
322 SCIP_CUT** cut, /**< pointer to store the cut */
323 BMS_BLKMEM* blkmem, /**< block memory */
324 SCIP_ROW* row /**< row this cut represents */
325 )
326{
327 assert(cut != NULL);
328 assert(blkmem != NULL);
329 assert(row != NULL);
330
331 /* allocate cut memory */
332 SCIP_ALLOC( BMSallocBlockMemory(blkmem, cut) );
333 (*cut)->row = row;
334 (*cut)->age = 0;
335 (*cut)->processedlp = -1;
336 (*cut)->processedlpsol = -1;
337 (*cut)->pos = -1;
338
339 /* capture row */
340 SCIProwCapture(row);
341
342 return SCIP_OKAY;
343}
344
345/** frees a cut and releases the row */
346static
348 SCIP_CUT** cut, /**< pointer to store the cut */
349 BMS_BLKMEM* blkmem, /**< block memory */
350 SCIP_SET* set, /**< global SCIP settings */
351 SCIP_LP* lp /**< current LP data */
352 )
353{
354 assert(cut != NULL);
355 assert(*cut != NULL);
356 assert((*cut)->row != NULL);
357 assert(blkmem != NULL);
358
359 /* release row */
360 SCIP_CALL( SCIProwRelease(&(*cut)->row, blkmem, set, lp) );
361
362 /* free cut memory */
363 BMSfreeBlockMemory(blkmem, cut);
364
365 return SCIP_OKAY;
366}
367
368/** returns whether the cut's age exceeds the age limit */
369static
371 SCIP_CUT* cut, /**< cut to check */
372 int agelimit /**< maximum age a cut can reach before it is deleted from the pool, or -1 */
373 )
374{
375 assert(cut != NULL);
376
377 /* since agelimit can be -1 cast to unsigned before comparison, then it is the maximum unsigned value in that case */
378 return (unsigned int)cut->age > (unsigned int)agelimit;
379}
380
381/** gets the row of the cut */
383 SCIP_CUT* cut /**< cut */
384 )
385{
386 assert(cut != NULL);
387
388 return cut->row;
389}
390
391/** gets the age of the cut: the number of consecutive cut pool separation rounds where the cut was neither in the LP nor violated */
393 SCIP_CUT* cut /**< cut */
394 )
395{
396 assert(cut != NULL);
397
398 return cut->age;
399}
400
401/** returns the ratio of LPs where the row belonging to this cut was active in an LP solution, i.e.
402 * where the age of its row has not been increased
403 *
404 * @see SCIPcutGetAge() to get the age of a cut
405 */
407 SCIP_CUT* cut /**< cut */
408 )
409{
410 SCIP_Longint nlpsaftercreation;
411 SCIP_Longint activeinlpcounter;
412
413 assert(cut != NULL);
414 assert(cut->row != NULL);
415
416 nlpsaftercreation = SCIProwGetNLPsAfterCreation(cut->row);
417 activeinlpcounter = SCIProwGetActiveLPCount(cut->row);
418
419 return (nlpsaftercreation > 0 ? activeinlpcounter / (SCIP_Real)nlpsaftercreation : 0.0);
420}
421
422/*
423 * Cutpool methods
424 */
425
426/** creates cut pool */
428 SCIP_CUTPOOL** cutpool, /**< pointer to store cut pool */
429 BMS_BLKMEM* blkmem, /**< block memory */
430 SCIP_SET* set, /**< global SCIP settings */
431 int agelimit, /**< maximum age a cut can reach before it is deleted from the pool */
432 SCIP_Bool globalcutpool /**< is this the global cut pool of SCIP? */
433 )
434{
435 assert(cutpool != NULL);
436 assert(agelimit >= -1);
437
438 SCIP_ALLOC( BMSallocMemory(cutpool) );
439
440 SCIP_CALL( SCIPclockCreate(&(*cutpool)->poolclock, SCIP_CLOCKTYPE_DEFAULT) );
441
442 SCIP_CALL( SCIPhashtableCreate(&(*cutpool)->hashtable, blkmem,
444 hashGetKeyCut, hashKeyEqCut, hashKeyValCut, (void*) set) );
445
446 (*cutpool)->cuts = NULL;
447 (*cutpool)->cutssize = 0;
448 (*cutpool)->ncuts = 0;
449 (*cutpool)->nremovablecuts = 0;
450 (*cutpool)->agelimit = agelimit;
451 (*cutpool)->processedlp = -1;
452 (*cutpool)->processedlpsol = -1;
453 (*cutpool)->processedlpefficacy = SCIP_INVALID;
454 (*cutpool)->processedlpsolefficacy = SCIP_INVALID;
455 (*cutpool)->firstunprocessed = 0;
456 (*cutpool)->firstunprocessedsol = 0;
457 (*cutpool)->maxncuts = 0;
458 (*cutpool)->ncalls = 0;
459 (*cutpool)->nrootcalls = 0;
460 (*cutpool)->ncutsfound = 0;
461 (*cutpool)->ncutsadded = 0;
462 (*cutpool)->globalcutpool = globalcutpool;
463
464 return SCIP_OKAY;
465}
466
467/** frees cut pool */
469 SCIP_CUTPOOL** cutpool, /**< pointer to store cut pool */
470 BMS_BLKMEM* blkmem, /**< block memory */
471 SCIP_SET* set, /**< global SCIP settings */
472 SCIP_LP* lp /**< current LP data */
473 )
474{
475 assert(cutpool != NULL);
476 assert(*cutpool != NULL);
477
478 /* remove all cuts from the pool */
479 SCIP_CALL( SCIPcutpoolClear(*cutpool, blkmem, set, lp) );
480
481 /* free clock */
482 SCIPclockFree(&(*cutpool)->poolclock);
483
484 /* free hash table */
485 SCIPhashtableFree(&(*cutpool)->hashtable);
486
487 BMSfreeMemoryArrayNull(&(*cutpool)->cuts);
488 BMSfreeMemory(cutpool);
489
490 return SCIP_OKAY;
491}
492
493/** removes all rows from the cut pool */
495 SCIP_CUTPOOL* cutpool, /**< cut pool */
496 BMS_BLKMEM* blkmem, /**< block memory */
497 SCIP_SET* set, /**< global SCIP settings */
498 SCIP_LP* lp /**< current LP data */
499 )
500{
501 int i;
502
503 assert(cutpool != NULL);
504
505 /* free cuts */
507 for( i = 0; i < cutpool->ncuts; ++i )
508 {
509 if( cutpool->globalcutpool )
510 cutpool->cuts[i]->row->inglobalcutpool = FALSE;
511 SCIProwUnlock(cutpool->cuts[i]->row);
512 SCIP_CALL( cutFree(&cutpool->cuts[i], blkmem, set, lp) );
513 }
514
515 cutpool->ncuts = 0;
516 cutpool->nremovablecuts = 0;
517
518 return SCIP_OKAY;
519}
520
521/** removes the cut from the cut pool */
522static
524 SCIP_CUTPOOL* cutpool, /**< cut pool */
525 BMS_BLKMEM* blkmem, /**< block memory */
526 SCIP_SET* set, /**< global SCIP settings */
527 SCIP_STAT* stat, /**< problem statistics data */
528 SCIP_LP* lp, /**< current LP data */
529 SCIP_CUT* cut /**< cut to remove */
530 )
531{
532 int pos;
533
534 assert(cutpool != NULL);
535 assert(cutpool->firstunprocessed <= cutpool->ncuts);
536 assert(cutpool->firstunprocessedsol <= cutpool->ncuts);
537 assert(blkmem != NULL);
538 assert(stat != NULL);
539 assert(cutpool->processedlp <= stat->lpcount);
540 assert(cutpool->processedlpsol <= stat->lpcount);
541 assert(cut != NULL);
542 assert(cut->row != NULL);
543
544 pos = cut->pos;
545 assert(0 <= pos && pos < cutpool->ncuts);
546 assert(cutpool->cuts[pos] == cut);
547
548 /* decrease the number of removable cuts counter (row might have changed its removable status -> counting might not
549 * be correct
550 */
551 if( SCIProwIsRemovable(cut->row) && cutpool->nremovablecuts > 0 )
552 cutpool->nremovablecuts--;
553
554 /* if this is the global cut pool of SCIP, mark the row to not be member anymore */
555 if( cutpool->globalcutpool )
556 {
557 assert(cut->row->inglobalcutpool);
558 cut->row->inglobalcutpool = FALSE;
559 }
560
561 /* remove the cut from the hash table */
562 assert(SCIPhashtableExists(cutpool->hashtable, (void*)cut));
563 SCIP_CALL( SCIPhashtableRemove(cutpool->hashtable, (void*)cut) );
564 assert(! SCIPhashtableExists(cutpool->hashtable, (void*)cut));
565
566 /* unlock the row */
567 SCIProwUnlock(cut->row);
568
569 /* free the cut */
570 SCIP_CALL( cutFree(&cutpool->cuts[pos], blkmem, set, lp) );
571
572 --cutpool->ncuts;
573 cutpool->firstunprocessed = MIN(cutpool->firstunprocessed, cutpool->ncuts);
574 cutpool->firstunprocessedsol = MIN(cutpool->firstunprocessedsol, cutpool->ncuts);
575
576 /* move the last cut of the pool to the free position */
577 if( pos < cutpool->ncuts )
578 {
579 cutpool->cuts[pos] = cutpool->cuts[cutpool->ncuts];
580 cutpool->cuts[pos]->pos = pos;
581 assert(cutpool->cuts[pos]->processedlp <= stat->lpcount);
582 assert(cutpool->cuts[pos]->processedlpsol <= stat->lpcount);
583 if( cutpool->cuts[pos]->processedlp < stat->lpcount )
584 cutpool->firstunprocessed = MIN(cutpool->firstunprocessed, pos);
585 if( cutpool->cuts[pos]->processedlpsol < stat->lpcount )
586 cutpool->firstunprocessedsol = MIN(cutpool->firstunprocessedsol, pos);
587 }
588
589 return SCIP_OKAY;
590}
591
592/** checks if cut is already existing */
594 SCIP_CUTPOOL* cutpool, /**< cut pool */
595 SCIP_SET* set, /**< global SCIP settings */
596 SCIP_ROW* row /**< cutting plane to add */
597 )
598{
599 SCIP_CUT* othercut;
600 assert(cutpool != NULL);
601 assert(row != NULL);
602
603 if( row->len == 0 )
604 {
605 /* trivial cut is only new if it proves infeasibility */
606 return SCIPsetIsFeasLT(set, row->constant, row->lhs) || SCIPsetIsFeasGT(set, row->constant, row->rhs);
607 }
608
609 othercut = (SCIP_CUT*)SCIPhashtableRetrieve(cutpool->hashtable, (void*)row);
610 /* check in hash table, if cut already exists in the pool */
611 if( othercut == NULL )
612 {
613 return TRUE;
614 }
615 else if( othercut->row != row )
616 {
617 SCIP_ROW* otherrow = othercut->row;
618 SCIP_Real otherrhs;
619 SCIP_Real rhs;
620 SCIP_Real scale;
621 SCIP_Real otherscale;
622
623 /* since we are comparing the improvement with an absolute value, we apply a
624 * scale to both rows such that the max absolute value is 1.0.
625 * Then bring the cut into the form ax <= b
626 */
627 scale = 1.0 / SCIProwGetMaxval(row, set);
628 otherscale = 1.0 / SCIProwGetMaxval(otherrow, set);
629
630 if( SCIPsetIsInfinity(set, otherrow->rhs) )
631 {
632 otherrhs = otherscale * (otherrow->constant - otherrow->lhs);
633 }
634 else
635 {
636 otherrhs = otherscale * (otherrow->rhs - otherrow->constant);
637 }
638
639 if( SCIPsetIsInfinity(set, row->rhs) )
640 {
641 rhs = scale * (row->constant - row->lhs);
642 }
643 else
644 {
645 rhs = scale * (row->rhs - row->constant);
646 }
647
648 if( SCIPsetIsFeasLT(set, rhs, otherrhs) )
649 return TRUE;
650 }
651
652 return FALSE;
653}
654
655/** if not already existing, adds row to cut pool and captures it */
657 SCIP_CUTPOOL* cutpool, /**< cut pool */
658 BMS_BLKMEM* blkmem, /**< block memory */
659 SCIP_SET* set, /**< global SCIP settings */
660 SCIP_STAT* stat, /**< problem statistics data */
661 SCIP_LP* lp, /**< current LP data */
662 SCIP_ROW* row /**< cutting plane to add */
663 )
664{
665 SCIP_CUT* othercut;
666 assert(cutpool != NULL);
667 assert(row != NULL);
668
669 if( row->len == 0 )
670 return SCIP_OKAY;
671
672 if( !row->validminmaxidx )
673 {
674 /* only called to ensure that minidx and maxidx are up to date */
675 (void) SCIProwGetMaxidx(row, set);
676 }
677 assert(row->validminmaxidx);
678
679 othercut = (SCIP_CUT*)SCIPhashtableRetrieve(cutpool->hashtable, (void*)row);
680 /* check in hash table, if cut already exists in the pool */
681 if( othercut == NULL )
682 {
683 SCIP_CALL( SCIPcutpoolAddNewRow(cutpool, blkmem, set, stat, lp, row) );
684 }
685 else
686 {
687 SCIP_ROW* otherrow = othercut->row;
688 SCIP_Real otherrhs;
689 SCIP_Real rhs;
690 SCIP_Real scale;
691 SCIP_Real otherscale;
692
693 /* since we are comparing the improvement with an absolute value, we apply a
694 * scale to both rows such that the max absolute value is 1.0.
695 * Then bring the cut into the form ax <= b
696 */
697 scale = 1.0 / SCIProwGetMaxval(row, set);
698 otherscale = 1.0 / SCIProwGetMaxval(otherrow, set);
699
700 if( SCIPsetIsInfinity(set, otherrow->rhs) )
701 {
702 otherrhs = otherscale * (otherrow->constant - otherrow->lhs);
703 }
704 else
705 {
706 otherrhs = otherscale * (otherrow->rhs - otherrow->constant);
707 }
708
709 if( SCIPsetIsInfinity(set, row->rhs) )
710 {
711 rhs = scale * (row->constant - row->lhs);
712 }
713 else
714 {
715 rhs = scale * (row->rhs - row->constant);
716 }
717
718 if( SCIPsetIsFeasLT(set, rhs, otherrhs) )
719 {
720 SCIP_CALL( cutpoolDelCut(cutpool, blkmem, set, stat, lp, othercut) );
721
722 /* use recursion, since in rare cases new cut might compare equal to multiple other cuts
723 * that do not compare equal themselve due to non-transitivity of epsilon comparisons
724 */
725 SCIP_CALL( SCIPcutpoolAddRow(cutpool, blkmem, set, stat, lp, row) );
726 }
727 }
728
729 return SCIP_OKAY;
730}
731
732/** adds row to cut pool and captures it; doesn't check for multiple cuts */
734 SCIP_CUTPOOL* cutpool, /**< cut pool */
735 BMS_BLKMEM* blkmem, /**< block memory */
736 SCIP_SET* set, /**< global SCIP settings */
737 SCIP_STAT* stat, /**< problem statistics data */
738 SCIP_LP* lp, /**< current LP data */
739 SCIP_ROW* row /**< cutting plane to add */
740 )
741{
742 SCIP_Real thisefficacy;
743 SCIP_CUT* cut;
744
745 assert(cutpool != NULL);
746 assert(row != NULL);
747
748 /* check, if row is modifiable or local */
749 if( SCIProwIsModifiable(row) )
750 {
751 SCIPerrorMessage("cannot store modifiable row <%s> in a cut pool\n", SCIProwGetName(row));
752 return SCIP_INVALIDDATA;
753 }
754 if( SCIProwIsLocal(row) )
755 {
756 SCIPerrorMessage("cannot store locally valid row <%s> in a cut pool\n", SCIProwGetName(row));
757 return SCIP_INVALIDDATA;
758 }
759
760 assert(! row->inglobalcutpool);
761
762 if( !row->validminmaxidx )
763 {
764 /* only called to ensure that minidx and maxidx are up-to-date */
765 (void) SCIProwGetMaxidx(row, set);
766 }
767 assert(row->validminmaxidx);
768
769 /* create the cut */
770 SCIP_CALL( cutCreate(&cut, blkmem, row) );
771 cut->pos = cutpool->ncuts;
772
773 /* add cut to the pool */
774 SCIP_CALL( cutpoolEnsureCutsMem(cutpool, set, cutpool->ncuts+1) );
775 cutpool->cuts[cutpool->ncuts] = cut;
776 cutpool->ncuts++;
777 cutpool->ncutsfound++;
778 cutpool->maxncuts = MAX(cutpool->maxncuts, cutpool->ncuts);
779 if( SCIProwIsRemovable(row) )
780 cutpool->nremovablecuts++;
781
782 assert(!SCIPhashtableExists(cutpool->hashtable, (void*)cut));
783
784 /* insert cut in the hash table */
785 SCIP_CALL( SCIPhashtableInsert(cutpool->hashtable, (void*)cut) );
786
787 assert(SCIPhashtableExists(cutpool->hashtable, (void*)cut));
788
790 {
791 thisefficacy = SCIProwGetLPEfficacy(row, set, stat, lp);
792 stat->bestefficacy = MAX(thisefficacy, stat->bestefficacy);
793 }
794
795 /* if this is the global cut pool of SCIP, mark the row to be member of the pool */
796 if( cutpool->globalcutpool )
797 row->inglobalcutpool = TRUE;
798
799 /* lock the row */
800 SCIProwLock(row);
801
802 return SCIP_OKAY;
803}
804
805/** removes the LP row from the cut pool */
807 SCIP_CUTPOOL* cutpool, /**< cut pool */
808 BMS_BLKMEM* blkmem, /**< block memory */
809 SCIP_SET* set, /**< global SCIP settings */
810 SCIP_STAT* stat, /**< problem statistics data */
811 SCIP_LP* lp, /**< current LP data */
812 SCIP_ROW* row /**< row to remove */
813 )
814{
815 SCIP_CUT* cut;
816
817 assert(cutpool != NULL);
818 assert(row != NULL);
819
820 /* find the cut in hash table */
821 cut = (SCIP_CUT*)SCIPhashtableRetrieve(cutpool->hashtable, (void*)row);
822 if( cut == NULL )
823 {
824 SCIPerrorMessage("row <%s> is not existing in cutpool %p\n", SCIProwGetName(row), (void*)cutpool);
825 return SCIP_INVALIDDATA;
826 }
827
828 SCIP_CALL( cutpoolDelCut(cutpool, blkmem, set, stat, lp, cut) );
829
830 return SCIP_OKAY;
831}
832
833
834/** separates cuts of the cut pool */
836 SCIP_CUTPOOL* cutpool, /**< cut pool */
837 BMS_BLKMEM* blkmem, /**< block memory */
838 SCIP_SET* set, /**< global SCIP settings */
839 SCIP_STAT* stat, /**< problem statistics data */
840 SCIP_EVENTQUEUE* eventqueue, /**< event queue */
841 SCIP_EVENTFILTER* eventfilter, /**< event filter for global events */
842 SCIP_LP* lp, /**< current LP data */
843 SCIP_SEPASTORE* sepastore, /**< separation storage */
844 SCIP_SOL* sol, /**< solution to be separated (or NULL for LP-solution) */
845 SCIP_Bool cutpoolisdelayed, /**< is the cutpool delayed (count cuts found)? */
846 SCIP_Bool root, /**< are we at the root node? */
847 SCIP_RESULT* result /**< pointer to store the result of the separation call */
848 )
849{
850 SCIP_CUT* cut;
851 SCIP_Bool found;
852 SCIP_Bool cutoff;
853 SCIP_Real minefficacy;
854 SCIP_Bool retest;
855 int firstunproc;
856 int oldncutsadded;
857 int oldncutsfound;
858 int nefficaciouscuts;
859 int c;
860
861 assert(cutpool != NULL);
862 assert(stat != NULL);
863 assert(cutpool->processedlp <= stat->lpcount);
864 assert(cutpool->processedlpsol <= stat->lpcount);
865 assert(cutpool->firstunprocessed <= cutpool->ncuts);
866 assert(cutpool->firstunprocessedsol <= cutpool->ncuts);
867 assert(result != NULL);
868
869 *result = SCIP_DIDNOTRUN;
870
871 /* don't separate cut pool in the root node, if there are no removable cuts */
872 if( root && cutpool->nremovablecuts == 0 )
873 return SCIP_OKAY;
874
875 if ( sol == NULL )
876 {
877 if( cutpool->processedlp < stat->lpcount )
878 cutpool->firstunprocessed = 0;
879 if( cutpool->firstunprocessed == cutpool->ncuts )
880 return SCIP_OKAY;
881 firstunproc = cutpool->firstunprocessed;
882 }
883 else
884 {
885 if( cutpool->processedlpsol < stat->lpcount )
886 cutpool->firstunprocessedsol = 0;
887 if( cutpool->firstunprocessedsol == cutpool->ncuts )
888 return SCIP_OKAY;
889 firstunproc = cutpool->firstunprocessedsol;
890 }
891
892 *result = SCIP_DIDNOTFIND;
893 cutpool->ncalls++;
894 if( root )
895 cutpool->nrootcalls++;
896 found = FALSE;
897 if( set->sepa_filtercutpoolrel )
898 minefficacy = stat->bestefficacy * stat->minefficacyfac;
899 else
900 minefficacy = root ? set->sepa_minefficacyroot : set->sepa_minefficacy;
901
902 if( sol == NULL )
903 {
904 retest = cutpool->processedlpefficacy > minefficacy;
905 cutpool->processedlpefficacy = minefficacy;
906 }
907 else
908 {
909 retest = cutpool->processedlpsolefficacy > minefficacy;
910 cutpool->processedlpsolefficacy = minefficacy;
911 }
912
913 SCIPsetDebugMsg(set, "separating%s cut pool %p with %d cuts, beginning with cut %d\n", ( sol == NULL ) ? "" : " solution from", (void*)cutpool, cutpool->ncuts, firstunproc);
914
915 /* start timing */
916 SCIPclockStart(cutpool->poolclock, set);
917
918 /* remember the current total number of found cuts */
919 oldncutsfound = SCIPsepastoreGetNCuts(sepastore);
920 oldncutsadded = SCIPsepastoreGetNCutsAdded(sepastore);
921 nefficaciouscuts = 0;
922
923 /* process all unprocessed cuts in the pool */
924 cutoff = FALSE;
925 for( c = firstunproc; c < cutpool->ncuts; ++c )
926 {
927 SCIP_Longint proclp;
928
929 cut = cutpool->cuts[c];
930 assert(cut != NULL);
931 assert(cut->processedlp <= stat->lpcount);
932 assert(cut->processedlpsol <= stat->lpcount);
933 assert(cut->pos == c);
934
935 proclp = ( sol == NULL ) ? cut->processedlp : cut->processedlpsol;
936
937 if( retest || proclp < stat->lpcount )
938 {
939 SCIP_ROW* row;
940
941 if ( sol == NULL )
942 cut->processedlp = stat->lpcount;
943 else
944 cut->processedlpsol = stat->lpcount;
945
946 row = cut->row;
947 if( !SCIProwIsInLP(row) )
948 {
949 SCIP_Real efficacy;
950
951 /* if the cut is a bound change (i.e. a row with only one variable), add it as bound change instead of LP
952 * row; hence, we want to remove the bound change cut from the SCIP cut pool
953 */
954 if( !SCIProwIsModifiable(row) && SCIProwGetNNonz(row) == 1 )
955 {
956 /* insert bound change cut into separation store which will force that cut;
957 * fromcutpool is set for consistency.
958 */
959 row->fromcutpool = TRUE;
960 SCIP_CALL( SCIPsepastoreAddCut(sepastore, blkmem, set, stat, eventqueue, eventfilter, lp, row, FALSE, root, &cutoff) );
961 SCIP_CALL( cutpoolDelCut(cutpool, blkmem, set, stat, lp, cut) );
962
963 if ( cutoff )
964 break;
965
966 continue;
967 }
968
969 efficacy = sol == NULL ? SCIProwGetLPEfficacy(row, set, stat, lp) : SCIProwGetSolEfficacy(row, set, stat, sol);
970 if( SCIPsetIsFeasPositive(set, efficacy) )
971 ++nefficaciouscuts;
972
973 if( efficacy >= minefficacy )
974 {
975 /* insert cut in separation storage */
976 row->fromcutpool = TRUE;
977 SCIPsetDebugMsg(set, " -> separated cut <%s> from the cut pool (feasibility: %g)\n",
978 SCIProwGetName(row), ( sol == NULL ) ? SCIProwGetLPFeasibility(row, set, stat, lp) : SCIProwGetSolFeasibility(row, set, stat, sol) );
979 SCIP_CALL( SCIPsepastoreAddCut(sepastore, blkmem, set, stat, eventqueue, eventfilter, lp, row, FALSE, root, &cutoff) );
980
981 /* count cuts */
982 if ( cutpoolisdelayed )
983 {
984 if ( SCIProwGetOriginSepa(row) != NULL )
985 {
986 SCIP_SEPA* sepa;
987
988 sepa = SCIProwGetOriginSepa(row);
991 }
992 else if ( SCIProwGetOriginConshdlr(row) != NULL )
993 {
994 SCIP_CONSHDLR* conshdlr;
995
996 conshdlr = SCIProwGetOriginConshdlr(row);
998 }
999 }
1000
1001 found = TRUE;
1002 cut->age = 0;
1003
1004 if ( cutoff )
1005 break;
1006 }
1007 else
1008 {
1009 cut->age++;
1010 if( cutIsAged(cut, cutpool->agelimit) )
1011 {
1012 SCIP_CALL( cutpoolDelCut(cutpool, blkmem, set, stat, lp, cut) );
1013 }
1014 }
1015 }
1016 }
1017 }
1018
1019 if ( sol == NULL )
1020 {
1021 cutpool->processedlp = stat->lpcount;
1022 cutpool->firstunprocessed = cutpool->ncuts;
1023 }
1024 else
1025 {
1026 cutpool->processedlpsol = stat->lpcount;
1027 cutpool->firstunprocessedsol = cutpool->ncuts;
1028 }
1029 /* update the number of found and added cuts */
1030 cutpool->ncutsadded += SCIPsepastoreGetNCutsAdded(sepastore) - oldncutsadded; /*lint !e776*/
1031
1032 /* check whether efficacy threshold should be tightened or relaxed */
1033 if( set->sepa_filtercutpoolrel && nefficaciouscuts > 0 )
1034 {
1035 int maxncuts = SCIPsetGetSepaMaxcuts(set, root);
1036 int ncuts = SCIPsepastoreGetNCuts(sepastore) - oldncutsfound;
1037
1038 maxncuts = MIN(maxncuts, nefficaciouscuts);
1039
1040 if( ncuts > (0.5 * maxncuts) )
1041 {
1042 stat->ncutpoolfails = MIN(stat->ncutpoolfails - 1, -1);
1043 }
1044 else if( ncuts == 0 || (ncuts < (0.05 * maxncuts)) )
1045 {
1046 stat->ncutpoolfails = MAX(stat->ncutpoolfails + 1, 1);
1047 }
1048
1049 if( stat->ncutpoolfails == (root ? 2 : 10) )
1050 {
1051 cutpool->firstunprocessed = 0;
1052 cutpool->firstunprocessedsol = 0;
1053 stat->minefficacyfac *= 0.5;
1054 stat->ncutpoolfails = 0;
1055 }
1056 else if( stat->ncutpoolfails == -2 )
1057 {
1058 stat->minefficacyfac *= 1.2;
1059 stat->ncutpoolfails = 0;
1060 }
1061 }
1062
1063 /* stop timing */
1064 SCIPclockStop(cutpool->poolclock, set);
1065
1066 if ( cutoff )
1067 *result = SCIP_CUTOFF;
1068 else if( found )
1069 *result = SCIP_SEPARATED;
1070
1071 return SCIP_OKAY;
1072}
1073
1074/** gets array of cuts in the cut pool */
1076 SCIP_CUTPOOL* cutpool /**< cut pool */
1077 )
1078{
1079 assert(cutpool != NULL);
1080
1081 return cutpool->cuts;
1082}
1083
1084/** gets number of cuts in the cut pool */
1086 SCIP_CUTPOOL* cutpool /**< cut pool */
1087 )
1088{
1089 assert(cutpool != NULL);
1090
1091 return cutpool->ncuts;
1092}
1093
1094/** gets maximum number of cuts that were stored in the cut pool at the same time */
1096 SCIP_CUTPOOL* cutpool /**< cut pool */
1097 )
1098{
1099 assert(cutpool != NULL);
1100
1101 return cutpool->maxncuts;
1102}
1103
1104/** gets time in seconds used for separating cuts from the pool */
1106 SCIP_CUTPOOL* cutpool /**< cut pool */
1107 )
1108{
1109 assert(cutpool != NULL);
1110
1111 return SCIPclockGetTime(cutpool->poolclock);
1112}
1113
1114/** get number of times the cut pool was separated */
1116 SCIP_CUTPOOL* cutpool /**< cut pool */
1117 )
1118{
1119 assert(cutpool != NULL);
1120
1121 return cutpool->ncalls;
1122}
1123
1124/** get number of times the cut pool was separated at the root */
1126 SCIP_CUTPOOL* cutpool /**< cut pool */
1127 )
1128{
1129 assert(cutpool != NULL);
1130
1131 return cutpool->nrootcalls;
1132}
1133
1134/** get total number of cuts that were added to the cut pool */
1136 SCIP_CUTPOOL* cutpool /**< cut pool */
1137 )
1138{
1139 assert(cutpool != NULL);
1140
1141 return cutpool->ncutsfound;
1142}
1143
1144/** get total number of cuts that were added from the cut pool to sepastore */
1146 SCIP_CUTPOOL* cutpool /**< cut pool */
1147 )
1148{
1149 assert(cutpool != NULL);
1150
1151 return cutpool->ncutsadded;
1152}
1153
1154/** adds the maximum number of cuts that were stored in the pool;
1155 * this is primarily used to keep statistics when SCIP performs a restart */
1157 SCIP_CUTPOOL* cutpool, /**< cut pool */
1158 SCIP_Longint ncuts /**< number of cuts to add */
1159 )
1160{
1161 assert(cutpool != NULL);
1162
1163 cutpool->maxncuts += ncuts;
1164}
1165
1166/** sets time in seconds used for separating cuts from the pool;
1167 * this is primarily used to keep statistics when SCIP performs a restart */
1169 SCIP_CUTPOOL* cutpool, /**< cut pool */
1170 SCIP_Real time /**< poolclock time */
1171 )
1172{
1173 assert(cutpool != NULL);
1174
1175 SCIPclockSetTime(cutpool->poolclock, time);
1176}
1177
1178/** adds the number of times the cut pool was separated;
1179 * this is primarily used to keep statistics when SCIP performs a restart */
1181 SCIP_CUTPOOL* cutpool, /**< cut pool */
1182 SCIP_Longint ncalls /**< ncalls */
1183 )
1184{
1185 assert(cutpool != NULL);
1186
1187 cutpool->ncalls += ncalls;
1188}
1189
1190/** adds the number of times the cut pool was separated at the root;
1191 * this is primarily used to keep statistics when SCIP performs a restart */
1193 SCIP_CUTPOOL* cutpool, /**< cut pool */
1194 SCIP_Longint nrootcalls /**< nrootcalls */
1195 )
1196{
1197 assert(cutpool != NULL);
1198
1199 cutpool->nrootcalls += nrootcalls;
1200}
1201
1202/** adds the total number of cuts that were added to the pool;
1203 * this is primarily used to keep statistics when SCIP performs a restart */
1205 SCIP_CUTPOOL* cutpool, /**< cut pool */
1206 SCIP_Longint ncutsfound /**< total number of cuts added to cut pool */
1207 )
1208{
1209 assert(cutpool != NULL);
1210
1211 cutpool->ncutsfound += ncutsfound;
1212}
1213
1214/** adds the total number of cuts that were separated from the pool;
1215 * this is primarily used to keep statistics when SCIP performs a restart */
1217 SCIP_CUTPOOL* cutpool, /**< cut pool */
1218 SCIP_Longint ncutsadded /**< total number of cuts added from cut pool to sepastore */
1219 )
1220{
1221 assert(cutpool != NULL);
1222
1223 cutpool->ncutsadded += ncutsadded;
1224}
void SCIPclockSetTime(SCIP_CLOCK *clck, SCIP_Real sec)
Definition: clock.c:539
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:360
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:290
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:438
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:185
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:170
internal methods for clocks and timing issues
void SCIPconshdlrIncNCutsFound(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4930
internal methods for constraints and constraint handlers
void SCIPcutpoolAddNCutsFound(SCIP_CUTPOOL *cutpool, SCIP_Longint ncutsfound)
Definition: cutpool.c:1204
static SCIP_Bool cutIsAged(SCIP_CUT *cut, int agelimit)
Definition: cutpool.c:370
void SCIPcutpoolSetTime(SCIP_CUTPOOL *cutpool, SCIP_Real time)
Definition: cutpool.c:1168
SCIP_RETCODE SCIPcutpoolSeparate(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_SEPASTORE *sepastore, SCIP_SOL *sol, SCIP_Bool cutpoolisdelayed, SCIP_Bool root, SCIP_RESULT *result)
Definition: cutpool.c:835
SCIP_RETCODE SCIPcutpoolDelRow(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_ROW *row)
Definition: cutpool.c:806
static SCIP_RETCODE cutCreate(SCIP_CUT **cut, BMS_BLKMEM *blkmem, SCIP_ROW *row)
Definition: cutpool.c:321
SCIP_RETCODE SCIPcutpoolCreate(SCIP_CUTPOOL **cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, int agelimit, SCIP_Bool globalcutpool)
Definition: cutpool.c:427
SCIP_RETCODE SCIPcutpoolAddRow(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_ROW *row)
Definition: cutpool.c:656
static SCIP_DECL_HASHKEYEQ(hashKeyEqCut)
Definition: cutpool.c:75
SCIP_RETCODE SCIPcutpoolAddNewRow(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_ROW *row)
Definition: cutpool.c:733
SCIP_RETCODE SCIPcutpoolFree(SCIP_CUTPOOL **cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: cutpool.c:468
void SCIPcutpoolAddNCalls(SCIP_CUTPOOL *cutpool, SCIP_Longint ncalls)
Definition: cutpool.c:1180
static SCIP_DECL_HASHKEYVAL(hashKeyValCut)
Definition: cutpool.c:255
static SCIP_RETCODE cutFree(SCIP_CUT **cut, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: cutpool.c:347
void SCIPcutpoolAddMaxNCuts(SCIP_CUTPOOL *cutpool, SCIP_Longint ncuts)
Definition: cutpool.c:1156
static SCIP_DECL_HASHGETKEY(hashGetKeyCut)
Definition: cutpool.c:61
static SCIP_RETCODE cutpoolEnsureCutsMem(SCIP_CUTPOOL *cutpool, SCIP_SET *set, int num)
Definition: cutpool.c:291
void SCIPcutpoolAddNCutsAdded(SCIP_CUTPOOL *cutpool, SCIP_Longint ncutsadded)
Definition: cutpool.c:1216
void SCIPcutpoolAddNRootCalls(SCIP_CUTPOOL *cutpool, SCIP_Longint nrootcalls)
Definition: cutpool.c:1192
SCIP_Bool SCIPcutpoolIsCutNew(SCIP_CUTPOOL *cutpool, SCIP_SET *set, SCIP_ROW *row)
Definition: cutpool.c:593
static SCIP_RETCODE cutpoolDelCut(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp, SCIP_CUT *cut)
Definition: cutpool.c:523
SCIP_RETCODE SCIPcutpoolClear(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: cutpool.c:494
internal methods for storing cuts in a cut pool
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_HASHSIZE_CUTPOOLS
Definition: def.h:300
#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 TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIP_HASHSIZE_CUTPOOLS_SMALL
Definition: def.h:303
#define SCIP_CALL(x)
Definition: def.h:374
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2659
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:551
SCIP_RETCODE SCIPhashtableCreate(SCIP_HASHTABLE **hashtable, BMS_BLKMEM *blkmem, int tablesize, SCIP_DECL_HASHGETKEY((*hashgetkey)), SCIP_DECL_HASHKEYEQ((*hashkeyeq)), SCIP_DECL_HASHKEYVAL((*hashkeyval)), void *userptr)
Definition: misc.c:2296
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2755
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:576
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2677
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
SCIP_CUT ** SCIPcutpoolGetCuts(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1075
SCIP_Longint SCIPcutpoolGetNRootCalls(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1125
SCIP_Longint SCIPcutpoolGetNCutsFound(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1135
SCIP_Real SCIPcutGetLPActivityQuot(SCIP_CUT *cut)
Definition: cutpool.c:406
SCIP_Real SCIPcutpoolGetTime(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1105
int SCIPcutpoolGetNCuts(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1085
SCIP_Longint SCIPcutpoolGetMaxNCuts(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1095
SCIP_ROW * SCIPcutGetRow(SCIP_CUT *cut)
Definition: cutpool.c:382
SCIP_Longint SCIPcutpoolGetNCalls(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1115
int SCIPcutGetAge(SCIP_CUT *cut)
Definition: cutpool.c:392
SCIP_Longint SCIPcutpoolGetNCutsAdded(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1145
void SCIProwSort(SCIP_ROW *row)
Definition: lp.c:6016
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17411
SCIP_Longint SCIProwGetActiveLPCount(SCIP_ROW *row)
Definition: lp.c:17545
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
SCIP_CONSHDLR * SCIProwGetOriginConshdlr(SCIP_ROW *row)
Definition: lp.c:17456
SCIP_Longint SCIProwGetNLPsAfterCreation(SCIP_ROW *row)
Definition: lp.c:17555
void SCIProwLock(SCIP_ROW *row)
Definition: lp.c:5378
SCIP_Bool SCIProwIsRemovable(SCIP_ROW *row)
Definition: lp.c:17421
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:17476
void SCIProwUnlock(SCIP_ROW *row)
Definition: lp.c:5393
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17523
SCIP_Real SCIProwGetMaxval(SCIP_ROW *row, SCIP_SET *set)
Definition: lp.c:6671
SCIP_Real SCIProwGetLPFeasibility(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:6254
void SCIProwCapture(SCIP_ROW *row)
Definition: lp.c:5339
SCIP_Real SCIProwGetSolFeasibility(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_SOL *sol)
Definition: lp.c:6508
SCIP_Real SCIProwGetSolEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_SOL *sol)
Definition: lp.c:6865
int SCIProwGetMaxidx(SCIP_ROW *row, SCIP_SET *set)
Definition: lp.c:6703
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13103
SCIP_Real SCIProwGetMinval(SCIP_ROW *row, SCIP_SET *set)
Definition: lp.c:6687
SCIP_Real SCIProwGetLPEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:6808
SCIP_RETCODE SCIProwRelease(SCIP_ROW **row, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: lp.c:5352
internal methods for LP management
#define BMSfreeMemory(ptr)
Definition: memory.h:145
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:465
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:451
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:127
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:148
#define BMSallocMemory(ptr)
Definition: memory.h:118
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
void SCIPsepaIncNCutsAdded(SCIP_SEPA *sepa, SCIP_Bool fromcutpool)
Definition: sepa.c:993
void SCIPsepaIncNCutsFoundAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:1049
internal methods for separators
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1149
SCIP_RETCODE SCIPsepastoreAddCut(SCIP_SEPASTORE *sepastore, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_STAT *stat, SCIP_EVENTQUEUE *eventqueue, SCIP_EVENTFILTER *eventfilter, SCIP_LP *lp, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool root, SCIP_Bool *infeasible)
Definition: sepastore.c:428
int SCIPsepastoreGetNCutsAdded(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1160
internal methods for storing separated cuts
SCIP_Bool SCIPsetIsFeasPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6718
int SCIPsetGetSepaMaxcuts(SCIP_SET *set, SCIP_Bool root)
Definition: set.c:5917
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6663
SCIP_Bool SCIPsetIsFeasEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6597
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6619
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6199
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5764
internal methods for global SCIP settings
#define SCIPsetDebugMsg
Definition: set.h:1784
internal methods for problem statistics
SCIP_Longint processedlp
SCIP_Longint processedlpsol
SCIP_ROW * row
SCIP_Longint ncalls
SCIP_Longint ncutsfound
SCIP_Longint ncutsadded
SCIP_Longint processedlpsol
SCIP_Real processedlpsolefficacy
SCIP_Real processedlpefficacy
SCIP_Longint processedlp
SCIP_CUT ** cuts
SCIP_Longint maxncuts
int firstunprocessedsol
SCIP_CLOCK * poolclock
SCIP_Longint nrootcalls
SCIP_HASHTABLE * hashtable
SCIP_Bool globalcutpool
int nlpcols
Definition: struct_lp.h:236
unsigned int lpcolssorted
Definition: struct_lp.h:251
unsigned int inglobalcutpool
Definition: struct_lp.h:262
SCIP_Real rhs
Definition: struct_lp.h:205
int nunlinked
Definition: struct_lp.h:237
unsigned int nonlpcolssorted
Definition: struct_lp.h:252
SCIP_Real * vals
Definition: struct_lp.h:229
unsigned int validminmaxidx
Definition: struct_lp.h:254
SCIP_Real lhs
Definition: struct_lp.h:204
int maxidx
Definition: struct_lp.h:243
SCIP_COL ** cols
Definition: struct_lp.h:227
SCIP_Real constant
Definition: struct_lp.h:203
int * cols_index
Definition: struct_lp.h:228
int minidx
Definition: struct_lp.h:242
int age
Definition: struct_lp.h:247
unsigned int fromcutpool
Definition: struct_lp.h:249
int len
Definition: struct_lp.h:235
SCIP_Real minefficacyfac
Definition: struct_stat.h:158
SCIP_Longint lpcount
Definition: struct_stat.h:190
int ncutpoolfails
Definition: struct_stat.h:220
SCIP_Real bestefficacy
Definition: struct_stat.h:157
datastructures for storing cuts in a cut pool
Definition: heur_padm.c:135
@ SCIP_CLOCKTYPE_DEFAULT
Definition: type_clock.h:43
@ SCIP_LPSOLSTAT_OPTIMAL
Definition: type_lp.h:43
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SEPARATED
Definition: type_result.h:49
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_INVALIDDATA
Definition: type_retcode.h:52
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63