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