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 */
60 static
61 SCIP_DECL_HASHGETKEY(hashGetKeyCut)
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 */
74 static
75 SCIP_DECL_HASHKEYEQ(hashKeyEqCut)
76 { /*lint --e{715}*/
77  SCIP_ROW* row1;
78  SCIP_ROW* row2;
79  SCIP_Real row1scale;
80  SCIP_Real row2scale;
81  SCIP_SET* set;
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 
254 static
255 SCIP_DECL_HASHKEYVAL(hashKeyValCut)
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 */
290 static
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 */
320 static
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 */
346 static
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 */
369 static
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,
443  (set->misc_usesmalltables ? SCIP_HASHSIZE_CUTPOOLS_SMALL : SCIP_HASHSIZE_CUTPOOLS),
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 */
522 static
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);
997  SCIPconshdlrIncNCutsFound(conshdlr);
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 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
internal methods for separators
SCIP_Bool SCIProwIsRemovable(SCIP_ROW *row)
Definition: lp.c:17421
SCIP_ROW * row
int nunlinked
Definition: struct_lp.h:237
SCIP_Real SCIProwGetSolFeasibility(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_SOL *sol)
Definition: lp.c:6508
void SCIPcutpoolAddNCalls(SCIP_CUTPOOL *cutpool, SCIP_Longint ncalls)
Definition: cutpool.c:1180
SCIP_Bool SCIPsetIsInfinity(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6269
int SCIProwGetMaxidx(SCIP_ROW *row, SCIP_SET *set)
Definition: lp.c:6703
#define NULL
Definition: def.h:267
SCIP_HASHTABLE * hashtable
#define BMSfreeMemoryArrayNull(ptr)
Definition: memory.h:148
#define SCIP_HASHSIZE_CUTPOOLS
Definition: def.h:300
SCIP_SEPA * SCIProwGetOriginSepa(SCIP_ROW *row)
Definition: lp.c:17476
SCIP_Longint processedlp
SCIP_Real SCIProwGetMinval(SCIP_ROW *row, SCIP_SET *set)
Definition: lp.c:6687
SCIP_Longint nrootcalls
int * cols_index
Definition: struct_lp.h:228
SCIP_RETCODE SCIPhashtableInsert(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2547
SCIP_Bool SCIPsetIsFeasEQ(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6667
SCIP_CUT ** cuts
SCIP_Longint SCIPcutpoolGetNCutsFound(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1135
internal methods for clocks and timing issues
int SCIProwGetNNonz(SCIP_ROW *row)
Definition: lp.c:17213
void SCIProwCapture(SCIP_ROW *row)
Definition: lp.c:5339
const char * SCIProwGetName(SCIP_ROW *row)
Definition: lp.c:17351
SCIP_Longint SCIProwGetActiveLPCount(SCIP_ROW *row)
Definition: lp.c:17545
void SCIPclockStop(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:360
#define FALSE
Definition: def.h:94
SCIP_Longint processedlpsol
void SCIPclockStart(SCIP_CLOCK *clck, SCIP_SET *set)
Definition: clock.c:290
#define TRUE
Definition: def.h:93
SCIP_Real SCIPcutGetLPActivityQuot(SCIP_CUT *cut)
Definition: cutpool.c:406
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Longint SCIPcutpoolGetNCalls(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1115
SCIP_Real SCIProwGetLPEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_LP *lp)
Definition: lp.c:6808
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
int SCIPsetCalcMemGrowSize(SCIP_SET *set, int num)
Definition: set.c:5834
SCIP_Longint ncutsadded
SCIP_Longint SCIPcutpoolGetNCutsAdded(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1145
void SCIPsepaIncNCutsFoundAtNode(SCIP_SEPA *sepa)
Definition: sepa.c:1049
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:523
static SCIP_RETCODE cutFree(SCIP_CUT **cut, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: cutpool.c:347
#define BMSfreeMemory(ptr)
Definition: memory.h:145
SCIP_Longint processedlp
SCIP_RETCODE SCIPcutpoolFree(SCIP_CUTPOOL **cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: cutpool.c:468
int nlpcols
Definition: struct_lp.h:236
SCIP_LPSOLSTAT SCIPlpGetSolstat(SCIP_LP *lp)
Definition: lp.c:13103
internal methods for LP management
Definition: heur_padm.c:134
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
int SCIPsetGetSepaMaxcuts(SCIP_SET *set, SCIP_Bool root)
Definition: set.c:5987
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
Definition: lp.c:17523
void SCIPclockSetTime(SCIP_CLOCK *clck, SCIP_Real sec)
Definition: clock.c:539
int ncutpoolfails
Definition: struct_stat.h:220
SCIP_Real * vals
Definition: struct_lp.h:229
unsigned int fromcutpool
Definition: struct_lp.h:249
SCIP_Longint SCIPcutpoolGetNRootCalls(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1125
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
void SCIProwSort(SCIP_ROW *row)
Definition: lp.c:6016
#define SCIPerrorMessage
Definition: pub_message.h:64
SCIP_Longint lpcount
Definition: struct_stat.h:190
static SCIP_RETCODE cutCreate(SCIP_CUT **cut, BMS_BLKMEM *blkmem, SCIP_ROW *row)
Definition: cutpool.c:321
SCIP_COL ** cols
Definition: struct_lp.h:227
SCIP_Bool SCIProwIsLocal(SCIP_ROW *row)
Definition: lp.c:17401
static INLINE uint32_t SCIPrealHashCode(double x)
Definition: pub_misc.h:576
static SCIP_DECL_HASHKEYVAL(hashKeyValCut)
Definition: cutpool.c:255
SCIP_Real lhs
Definition: struct_lp.h:204
SCIP_Longint processedlpsol
int SCIPsepastoreGetNCuts(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1149
SCIP_Real SCIPclockGetTime(SCIP_CLOCK *clck)
Definition: clock.c:438
datastructures for storing cuts in a cut pool
int maxidx
Definition: struct_lp.h:243
SCIP_ROW * SCIPcutGetRow(SCIP_CUT *cut)
Definition: cutpool.c:382
internal methods for global SCIP settings
#define SCIP_CALL(x)
Definition: def.h:380
#define SCIPhashTwo(a, b)
Definition: pub_misc.h:551
void SCIPcutpoolAddNCutsAdded(SCIP_CUTPOOL *cutpool, SCIP_Longint ncutsadded)
Definition: cutpool.c:1216
SCIP_Real processedlpsolefficacy
void SCIPhashtableRemoveAll(SCIP_HASHTABLE *hashtable)
Definition: misc.c:2755
SCIP_RETCODE SCIPcutpoolClear(SCIP_CUTPOOL *cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: cutpool.c:494
SCIP_RETCODE SCIPhashtableRemove(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2677
SCIP_CUT ** SCIPcutpoolGetCuts(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1075
int SCIPcutpoolGetNCuts(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1085
internal methods for storing separated cuts
SCIP_Bool SCIProwIsModifiable(SCIP_ROW *row)
Definition: lp.c:17411
SCIP_RETCODE SCIProwRelease(SCIP_ROW **row, BMS_BLKMEM *blkmem, SCIP_SET *set, SCIP_LP *lp)
Definition: lp.c:5352
SCIP_RETCODE SCIPclockCreate(SCIP_CLOCK **clck, SCIP_CLOCKTYPE clocktype)
Definition: clock.c:170
void SCIPconshdlrIncNCutsFound(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4932
#define BMSfreeBlockMemory(mem, ptr)
Definition: memory.h:465
void SCIPsepaIncNCutsAdded(SCIP_SEPA *sepa, SCIP_Bool fromcutpool)
Definition: sepa.c:993
SCIP_Real bestefficacy
Definition: struct_stat.h:157
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:91
SCIP_Real minefficacyfac
Definition: struct_stat.h:158
SCIP_Bool SCIPcutpoolIsCutNew(SCIP_CUTPOOL *cutpool, SCIP_SET *set, SCIP_ROW *row)
Definition: cutpool.c:593
void SCIPclockFree(SCIP_CLOCK **clck)
Definition: clock.c:185
#define SCIP_HASHSIZE_CUTPOOLS_SMALL
Definition: def.h:303
#define MIN(x, y)
Definition: def.h:243
#define SCIPsetDebugMsg
Definition: set.h:1784
void SCIPcutpoolAddNRootCalls(SCIP_CUTPOOL *cutpool, SCIP_Longint nrootcalls)
Definition: cutpool.c:1192
int minidx
Definition: struct_lp.h:242
SCIP_RETCODE SCIPcutpoolCreate(SCIP_CUTPOOL **cutpool, BMS_BLKMEM *blkmem, SCIP_SET *set, int agelimit, SCIP_Bool globalcutpool)
Definition: cutpool.c:427
int SCIPsepastoreGetNCutsAdded(SCIP_SEPASTORE *sepastore)
Definition: sepastore.c:1160
unsigned int lpcolssorted
Definition: struct_lp.h:251
internal methods for storing cuts in a cut pool
void * SCIPhashtableRetrieve(SCIP_HASHTABLE *hashtable, void *key)
Definition: misc.c:2608
SCIP_Real SCIProwGetSolEfficacy(SCIP_ROW *row, SCIP_SET *set, SCIP_STAT *stat, SCIP_SOL *sol)
Definition: lp.c:6865
int firstunprocessedsol
SCIP_CLOCK * poolclock
SCIP_Bool SCIPsetIsFeasLT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6689
SCIP_CONSHDLR * SCIProwGetOriginConshdlr(SCIP_ROW *row)
Definition: lp.c:17456
SCIP_Longint maxncuts
void SCIPhashtableFree(SCIP_HASHTABLE **hashtable)
Definition: misc.c:2346
void SCIProwLock(SCIP_ROW *row)
Definition: lp.c:5378
SCIP_Real rhs
Definition: struct_lp.h:205
SCIP_Real constant
Definition: struct_lp.h:203
SCIP_Longint ncalls
void SCIPcutpoolAddNCutsFound(SCIP_CUTPOOL *cutpool, SCIP_Longint ncutsfound)
Definition: cutpool.c:1204
void SCIPcutpoolSetTime(SCIP_CUTPOOL *cutpool, SCIP_Real time)
Definition: cutpool.c:1168
#define MAX(x, y)
Definition: def.h:239
unsigned int inglobalcutpool
Definition: struct_lp.h:262
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:6254
#define SCIP_Real
Definition: def.h:173
internal methods for problem statistics
SCIP_Bool SCIPsetIsFeasPositive(SCIP_SET *set, SCIP_Real val)
Definition: set.c:6788
#define BMSallocMemory(ptr)
Definition: memory.h:118
#define SCIP_INVALID
Definition: def.h:193
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:127
internal methods for constraints and constraint handlers
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
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
#define SCIP_Longint
Definition: def.h:158
SCIP_Bool SCIPsetIsFeasGT(SCIP_SET *set, SCIP_Real val1, SCIP_Real val2)
Definition: set.c:6733
SCIP_Bool SCIPhashtableExists(SCIP_HASHTABLE *hashtable, void *element)
Definition: misc.c:2659
SCIP_Real SCIProwGetMaxval(SCIP_ROW *row, SCIP_SET *set)
Definition: lp.c:6671
#define BMSallocBlockMemory(mem, ptr)
Definition: memory.h:451
SCIP_Real SCIPcutpoolGetTime(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1105
SCIP_Bool globalcutpool
int SCIPcutGetAge(SCIP_CUT *cut)
Definition: cutpool.c:392
SCIP_Longint SCIPcutpoolGetMaxNCuts(SCIP_CUTPOOL *cutpool)
Definition: cutpool.c:1095
common defines and data types used in all packages of SCIP
struct BMS_BlkMem BMS_BLKMEM
Definition: memory.h:437
unsigned int validminmaxidx
Definition: struct_lp.h:254
#define SCIP_ALLOC(x)
Definition: def.h:391
unsigned int nonlpcolssorted
Definition: struct_lp.h:252
SCIP_Longint SCIProwGetNLPsAfterCreation(SCIP_ROW *row)
Definition: lp.c:17555
static SCIP_Bool cutIsAged(SCIP_CUT *cut, int agelimit)
Definition: cutpool.c:370
static SCIP_DECL_HASHGETKEY(hashGetKeyCut)
Definition: cutpool.c:61
void SCIPcutpoolAddMaxNCuts(SCIP_CUTPOOL *cutpool, SCIP_Longint ncuts)
Definition: cutpool.c:1156
static SCIP_DECL_HASHKEYEQ(hashKeyEqCut)
Definition: cutpool.c:75
static SCIP_RETCODE cutpoolEnsureCutsMem(SCIP_CUTPOOL *cutpool, SCIP_SET *set, int num)
Definition: cutpool.c:291
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 len
Definition: struct_lp.h:235
int age
Definition: struct_lp.h:247
void SCIProwUnlock(SCIP_ROW *row)
Definition: lp.c:5393