1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file   sepastore.c
26   	 * @ingroup OTHER_CFILES
27   	 * @brief  methods for storing separated cuts
28   	 * @author Tobias Achterberg
29   	 * @author Marc Pfetsch
30   	 * @author Leona Gottwald
31   	 */
32   	
33   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
34   	
35   	#include <assert.h>
36   	
37   	#include "scip/def.h"
38   	#include "scip/set.h"
39   	#include "scip/stat.h"
40   	#include "scip/lp.h"
41   	#include "scip/var.h"
42   	#include "scip/tree.h"
43   	#include "scip/reopt.h"
44   	#include "scip/sepastore.h"
45   	#include "scip/event.h"
46   	#include "scip/sepa.h"
47   	#include "scip/cons.h"
48   	#include "scip/debug.h"
49   	#include "scip/scip.h"
50   	#include "scip/cuts.h"
51   	#include "scip/cutsel.h"
52   	#include "scip/struct_event.h"
53   	#include "scip/struct_sepastore.h"
54   	#include "scip/misc.h"
55   	
56   	
57   	
58   	/*
59   	 * dynamic memory arrays
60   	 */
61   	
62   	/** resizes cuts and score arrays to be able to store at least num entries */
63   	static
64   	SCIP_RETCODE sepastoreEnsureCutsMem(
65   	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
66   	   SCIP_SET*             set,                /**< global SCIP settings */
67   	   int                   num                 /**< minimal number of slots in array */
68   	   )
69   	{
70   	   assert(sepastore != NULL);
71   	   assert(set != NULL);
72   	
73   	   if( num > sepastore->cutssize )
74   	   {
75   	      int newsize;
76   	
77   	      newsize = SCIPsetCalcMemGrowSize(set, num);
78   	      SCIP_ALLOC( BMSreallocMemoryArray(&sepastore->cuts, newsize) );
79   	      sepastore->cutssize = newsize;
80   	   }
81   	   assert(num <= sepastore->cutssize);
82   	
83   	   return SCIP_OKAY;
84   	}
85   	
86   	/** creates separation storage */
87   	SCIP_RETCODE SCIPsepastoreCreate(
88   	   SCIP_SEPASTORE**      sepastore,          /**< pointer to store separation storage */
89   	   BMS_BLKMEM*           blkmem,             /**< block memory */
90   	   SCIP_SET*             set                 /**< global SCIP settings */
91   	   )
92   	{
93   	   assert(sepastore != NULL);
94   	
95   	   SCIP_ALLOC( BMSallocMemory(sepastore) );
96   	
97   	   (*sepastore)->cuts = NULL;
98   	   (*sepastore)->cutssize = 0;
99   	   (*sepastore)->ncuts = 0;
100  	   (*sepastore)->nforcedcuts = 0;
101  	   (*sepastore)->ncutsadded = 0;
102  	   (*sepastore)->ncutsaddedviapool = 0;
103  	   (*sepastore)->ncutsaddeddirect = 0;
104  	   (*sepastore)->ncutsfoundround = 0;
105  	   (*sepastore)->ncutsapplied = 0;
106  	   (*sepastore)->initiallp = FALSE;
107  	   (*sepastore)->forcecuts = FALSE;
108  	
109  	   SCIP_CALL( SCIPrandomCreate(&(*sepastore)->randnumgen, blkmem, (unsigned int)SCIPsetInitializeRandomSeed(set, 0x5EED)) );
110  	
111  	   return SCIP_OKAY;
112  	}
113  	
114  	/** frees separation storage */
115  	SCIP_RETCODE SCIPsepastoreFree(
116  	   SCIP_SEPASTORE**      sepastore,          /**< pointer to store separation storage */
117  	   BMS_BLKMEM*           blkmem              /**< block memory */
118  	   )
119  	{
120  	   assert(sepastore != NULL);
121  	   assert(*sepastore != NULL);
122  	   assert((*sepastore)->ncuts == 0);
123  	
124  	   SCIPrandomFree(&(*sepastore)->randnumgen, blkmem);
125  	   BMSfreeMemoryArrayNull(&(*sepastore)->cuts);
126  	   BMSfreeMemory(sepastore);
127  	
128  	   return SCIP_OKAY;
129  	}
130  	
131  	/** informs separation storage that the setup of the initial LP starts now */
132  	void SCIPsepastoreStartInitialLP(
133  	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
134  	   )
135  	{
136  	   assert(sepastore != NULL);
137  	   assert(!sepastore->initiallp);
138  	   assert(sepastore->ncuts == 0);
139  	
140  	   sepastore->initiallp = TRUE;
141  	}
142  	
143  	/** informs separation storage that the setup of the initial LP is now finished */
144  	void SCIPsepastoreEndInitialLP(
145  	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
146  	   )
147  	{
148  	   assert(sepastore != NULL);
149  	   assert(sepastore->initiallp);
150  	   assert(sepastore->ncuts == 0);
151  	
152  	   sepastore->initiallp = FALSE;
153  	}
154  	
155  	/** informs separation storage that the following cuts should be used in any case */
156  	void SCIPsepastoreStartForceCuts(
157  	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
158  	   )
159  	{
160  	   assert(sepastore != NULL);
161  	   assert(!sepastore->forcecuts);
162  	
163  	   sepastore->forcecuts = TRUE;
164  	}
165  	
166  	/** informs separation storage that the following cuts should no longer be used in any case */
167  	void SCIPsepastoreEndForceCuts(
168  	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
169  	   )
170  	{
171  	   assert(sepastore != NULL);
172  	   assert(sepastore->forcecuts);
173  	
174  	   sepastore->forcecuts = FALSE;
175  	}
176  	
177  	/** checks cut for redundancy due to activity bounds */
178  	static
179  	SCIP_Bool sepastoreIsCutRedundant(
180  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
181  	   SCIP_SET*             set,                /**< global SCIP settings */
182  	   SCIP_STAT*            stat,               /**< problem statistics data */
183  	   SCIP_ROW*             cut                 /**< separated cut */
184  	   )
185  	{
186  	   SCIP_Real minactivity;
187  	   SCIP_Real maxactivity;
188  	   SCIP_Real lhs;
189  	   SCIP_Real rhs;
190  	
191  	   assert(sepastore != NULL);
192  	   assert(cut != NULL);
193  	
194  	   /* modifiable cuts cannot be declared redundant, since we don't know all coefficients */
195  	   if( SCIProwIsModifiable(cut) )
196  	      return FALSE;
197  	
198  	   /* check for activity redundancy */
199  	   lhs = SCIProwGetLhs(cut);
200  	   rhs = SCIProwGetRhs(cut);
201  	   minactivity = SCIProwGetMinActivity(cut, set, stat);
202  	   maxactivity = SCIProwGetMaxActivity(cut, set, stat);
203  	
204  	   if( (SCIPsetIsInfinity(set, -lhs) || SCIPsetIsLE(set, lhs, minactivity)) &&
205  	       (SCIPsetIsInfinity(set, rhs) || SCIPsetIsLE(set, maxactivity, rhs)) )
206  	   {
207  	      SCIPsetDebugMsg(set, "ignoring activity redundant cut <%s> (sides=[%g,%g], act=[%g,%g])\n",
208  	         SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
209  	      /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
210  	      return TRUE;
211  	   }
212  	
213  	   return FALSE;
214  	}
215  	
216  	/** checks cut for redundancy or infeasibility due to activity bounds */
217  	static
218  	SCIP_Bool sepastoreIsCutRedundantOrInfeasible(
219  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
220  	   SCIP_SET*             set,                /**< global SCIP settings */
221  	   SCIP_STAT*            stat,               /**< problem statistics data */
222  	   SCIP_ROW*             cut,                /**< separated cut */
223  	   SCIP_Bool*            infeasible          /**< pointer to store whether the cut has been detected to be infeasible */
224  	   )
225  	{
226  	   SCIP_Real minactivity;
227  	   SCIP_Real maxactivity;
228  	   SCIP_Real lhs;
229  	   SCIP_Real rhs;
230  	
231  	   assert(sepastore != NULL);
232  	   assert(cut != NULL);
233  	   assert(infeasible != NULL);
234  	
235  	   *infeasible = FALSE;
236  	
237  	   /* modifiable cuts cannot be declared redundant or infeasible, since we don't know all coefficients */
238  	   if( SCIProwIsModifiable(cut) )
239  	      return FALSE;
240  	
241  	   /* check for activity redundancy */
242  	   lhs = SCIProwGetLhs(cut);
243  	   rhs = SCIProwGetRhs(cut);
244  	   minactivity = SCIProwGetMinActivity(cut, set, stat);
245  	   maxactivity = SCIProwGetMaxActivity(cut, set, stat);
246  	
247  	   if( (SCIPsetIsInfinity(set, -lhs) || SCIPsetIsLE(set, lhs, minactivity)) &&
248  	       (SCIPsetIsInfinity(set, rhs) || SCIPsetIsLE(set, maxactivity, rhs)) )
249  	   {
250  	      SCIPsetDebugMsg(set, "ignoring activity redundant cut <%s> (sides=[%g,%g], act=[%g,%g])\n",
251  	         SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
252  	      /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
253  	      return TRUE;
254  	   }
255  	
256  	   if( (!SCIPsetIsInfinity(set,  rhs) && SCIPsetIsFeasPositive(set, minactivity - rhs)) ||
257  	       (!SCIPsetIsInfinity(set, -lhs) && SCIPsetIsFeasNegative(set, maxactivity - lhs)) )
258  	   {
259  	      SCIPsetDebugMsg(set, "cut <%s> is infeasible (sides=[%g,%g], act=[%g,%g])\n",
260  	         SCIProwGetName(cut), lhs, rhs, minactivity, maxactivity);
261  	      /*SCIPdebug(SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
262  	      *infeasible = TRUE;
263  	      return TRUE;
264  	   }
265  	
266  	   return FALSE;
267  	}
268  	
269  	/** checks whether a cut with only one variable can be applied as boundchange
270  	 *
271  	 *  This is the case if the bound change would prove infeasibility (w.r.t feastol), or if the new bound is at least
272  	 *  epsilon better than the old bound.  In the latter case, also the opposite bound has to be taken into account.
273  	 */
274  	static
275  	SCIP_Bool sepastoreIsBdchgApplicable(
276  	   SCIP_SET*             set,                /**< global SCIP settings */
277  	   SCIP_ROW*             cut                 /**< cut with a single variable */
278  	   )
279  	{
280  	   SCIP_COL** cols;
281  	   SCIP_Real* vals;
282  	   SCIP_VAR* var;
283  	   SCIP_Real lhs;
284  	   SCIP_Real rhs;
285  	   SCIP_Bool local;
286  	   SCIP_Real oldlb;
287  	   SCIP_Real oldub;
288  	
289  	   assert(set != NULL);
290  	   assert(cut != NULL);
291  	   assert(!SCIProwIsModifiable(cut));
292  	   assert(SCIProwGetNNonz(cut) == 1);
293  	
294  	   /* get the single variable and its coefficient of the cut */
295  	   cols = SCIProwGetCols(cut);
296  	   assert(cols != NULL);
297  	
298  	   var = SCIPcolGetVar(cols[0]);
299  	   vals = SCIProwGetVals(cut);
300  	   assert(vals != NULL);
301  	   assert(!SCIPsetIsZero(set, vals[0]));
302  	
303  	   /* if the coefficient is nearly zero, we better ignore this cut for numerical reasons */
304  	   if( SCIPsetIsFeasZero(set, vals[0]) )
305  	      return FALSE;
306  	
307  	   local = SCIProwIsLocal(cut);
308  	
309  	   oldlb = local ? SCIPvarGetLbLocal(var) : SCIPvarGetLbGlobal(var);
310  	   oldub = local ? SCIPvarGetUbLocal(var) : SCIPvarGetUbGlobal(var);
311  	
312  	   /* get the left hand side of the cut and convert it to a bound */
313  	   lhs = SCIProwGetLhs(cut);
314  	   if( !SCIPsetIsInfinity(set, -lhs) )
315  	   {
316  	      lhs -= SCIProwGetConstant(cut);
317  	      if( vals[0] > 0.0 )
318  	      {
319  	         /* coefficient is positive -> lhs corresponds to lower bound */
320  	         SCIP_Real newlb;
321  	
322  	         newlb = lhs/vals[0];
323  	         SCIPvarAdjustLb(var, set, &newlb);
324  	
325  	         /* bound changes that improve the bound sufficiently are applicable */
326  	         if( SCIPsetIsFeasGT(set, newlb, oldub) || SCIPsetIsGT(set, MIN(newlb, oldub), oldlb) )
327  	            return TRUE;
328  	      }
329  	      else
330  	      {
331  	         /* coefficient is negative -> lhs corresponds to upper bound */
332  	         SCIP_Real newub;
333  	
334  	         newub = lhs/vals[0];
335  	         SCIPvarAdjustUb(var, set, &newub);
336  	
337  	         /* bound changes that improve the bound sufficiently are applicable */
338  	         if( SCIPsetIsFeasLT(set, newub, oldlb) || SCIPsetIsLT(set, MAX(newub, oldlb), oldub) )
339  	            return TRUE;
340  	      }
341  	   }
342  	
343  	   /* get the right hand side of the cut and convert it to a bound */
344  	   rhs = SCIProwGetRhs(cut);
345  	   if( !SCIPsetIsInfinity(set, rhs) )
346  	   {
347  	      rhs -= SCIProwGetConstant(cut);
348  	      if( vals[0] > 0.0 )
349  	      {
350  	         /* coefficient is positive -> rhs corresponds to upper bound */
351  	         SCIP_Real newub;
352  	
353  	         newub = rhs/vals[0];
354  	         SCIPvarAdjustUb(var, set, &newub);
355  	
356  	         /* bound changes that improve the bound sufficiently are applicable */
357  	         if( SCIPsetIsFeasLT(set, newub, oldlb) || SCIPsetIsLT(set, MAX(newub, oldlb), oldub) )
358  	            return TRUE;
359  	      }
360  	      else
361  	      {
362  	         /* coefficient is negative -> rhs corresponds to lower bound */
363  	         SCIP_Real newlb;
364  	
365  	         newlb = rhs/vals[0];
366  	         SCIPvarAdjustLb(var, set, &newlb);
367  	
368  	         /* bound changes that improve the bound sufficiently are applicable */
369  	         if( SCIPsetIsFeasGT(set, newlb, oldub) || SCIPsetIsGT(set, MIN(newlb, oldub), oldlb) )
370  	            return TRUE;
371  	      }
372  	   }
373  	
374  	   return FALSE;
375  	}
376  	
377  	/** removes a non-forced cut from the separation storage */
378  	static
379  	SCIP_RETCODE sepastoreDelCut(
380  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
381  	   BMS_BLKMEM*           blkmem,             /**< block memory */
382  	   SCIP_SET*             set,                /**< global SCIP settings */
383  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
384  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global events */
385  	   SCIP_LP*              lp,                 /**< LP data */
386  	   int                   pos                 /**< position of cut to delete */
387  	   )
388  	{
389  	   assert(sepastore != NULL);
390  	   assert(sepastore->cuts != NULL);
391  	   assert(sepastore->nforcedcuts <= pos && pos < sepastore->ncuts);
392  	
393  	   /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
394  	   if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 )
395  	   {
396  	      SCIP_EVENT* event;
397  	
398  	      SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[pos]) );
399  	      SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
400  	   }
401  	
402  	   /* release the row */
403  	   if( !sepastore->initiallp )
404  	   {
405  	      sepastore->ncutsadded--;
406  	      if( sepastore->cuts[pos]->fromcutpool )
407  	         sepastore->ncutsaddedviapool--;
408  	      else
409  	         sepastore->ncutsaddeddirect--;
410  	
411  	      if( (SCIP_ROWORIGINTYPE) sepastore->cuts[pos]->origintype == SCIP_ROWORIGINTYPE_SEPA )
412  	      {
413  	         SCIP_SEPA* sepa;
414  	         sepa = SCIProwGetOriginSepa(sepastore->cuts[pos]);
415  	         SCIPsepaDecNCutsAdded(sepa, sepastore->cuts[pos]->fromcutpool);
416  	      }
417  	   }
418  	   SCIP_CALL( SCIProwRelease(&sepastore->cuts[pos], blkmem, set, lp) );
419  	
420  	   /* move last cut to the empty position */
421  	   sepastore->cuts[pos] = sepastore->cuts[sepastore->ncuts-1];
422  	   sepastore->ncuts--;
423  	
424  	   return SCIP_OKAY;
425  	}
426  	
427  	/** adds cut to separation storage and captures it */
428  	SCIP_RETCODE SCIPsepastoreAddCut(
429  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
430  	   BMS_BLKMEM*           blkmem,             /**< block memory */
431  	   SCIP_SET*             set,                /**< global SCIP settings */
432  	   SCIP_STAT*            stat,               /**< problem statistics data */
433  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
434  	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global events */
435  	   SCIP_LP*              lp,                 /**< LP data */
436  	   SCIP_ROW*             cut,                /**< separated cut */
437  	   SCIP_Bool             forcecut,           /**< should the cut be forced to enter the LP? */
438  	   SCIP_Bool             root,               /**< are we at the root node? */
439  	   SCIP_Bool*            infeasible          /**< pointer to store whether the cut is infeasible */
440  	   )
441  	{
442  	   SCIP_Bool redundant;
443  	   int pos;
444  	
445  	   assert(sepastore != NULL);
446  	   assert(sepastore->nforcedcuts <= sepastore->ncuts);
447  	   assert(set != NULL);
448  	   assert(cut != NULL);
449  	   assert(!SCIPsetIsInfinity(set, -SCIProwGetLhs(cut)) || !SCIPsetIsInfinity(set, SCIProwGetRhs(cut)));
450  	   assert(eventqueue != NULL);
451  	   assert(eventfilter != NULL);
452  	
453  	   /* debug: check cut for feasibility */
454  	   SCIP_CALL( SCIPdebugCheckRow(set, cut) ); /*lint !e506 !e774*/
455  	
456  	   /* the cut will be forced to enter the LP if the dual must be collected and the initial LP is being constructed */
457  	   forcecut = forcecut || (set->lp_alwaysgetduals && sepastore->initiallp);
458  	
459  	   /* in the root node, every local cut is a global cut, and global cuts are nicer in many ways ... */
460  	   if( root && SCIProwIsLocal(cut) )
461  	   {
462  	      SCIPsetDebugMsg(set, "change local flag of cut <%s> to FALSE due to addition in root node\n", SCIProwGetName(cut));
463  	
464  	      SCIP_CALL( SCIProwChgLocal(cut, FALSE) );
465  	
466  	      assert(!SCIProwIsLocal(cut));
467  	   }
468  	
469  	   /* check cut for redundancy or infeasibility */
470  	   redundant = sepastoreIsCutRedundantOrInfeasible(sepastore, set, stat, cut, infeasible);
471  	   /* Note that we add infeasible rows in any case, since we cannot be sure whether the return values are handled
472  	    * correctly. In this way, the LP becomes infeasible. */
473  	
474  	   /* in each separation round, make sure that at least one (even redundant) cut enters the LP to avoid cycling */
475  	   if( !forcecut && sepastore->ncuts > 0 && redundant )
476  	      return SCIP_OKAY;
477  	
478  	   /* if only one cut is currently present in sepastore, it could be redundant; in this case, it can now be removed
479  	    * again, because now a non redundant cut enters the sepastore */
480  	   if( sepastore->ncuts == 1 && sepastoreIsCutRedundant(sepastore, set, stat, sepastore->cuts[0]) )
481  	   {
482  	      /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
483  	      if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 )
484  	      {
485  	         SCIP_EVENT* event;
486  	
487  	         SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[0]) );
488  	         SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
489  	      }
490  	      /* update statistics of total number of found cuts */
491  	      if( !sepastore->initiallp )
492  	      {
493  	         sepastore->ncutsadded--;
494  	         if( sepastore->cuts[0]->fromcutpool )
495  	            sepastore->ncutsaddedviapool--;
496  	         else
497  	            sepastore->ncutsaddeddirect--;
498  	
499  	         if( (SCIP_ROWORIGINTYPE) sepastore->cuts[0]->origintype == SCIP_ROWORIGINTYPE_SEPA )
500  	         {
501  	            SCIP_SEPA* sepa;
502  	            sepa = SCIProwGetOriginSepa(sepastore->cuts[0]);
503  	            SCIPsepaDecNCutsAdded(sepa, sepastore->cuts[0]->fromcutpool);
504  	         }
505  	      }
506  	
507  	      SCIP_CALL( SCIProwRelease(&sepastore->cuts[0], blkmem, set, lp) );
508  	      sepastore->ncuts = 0;
509  	      sepastore->nforcedcuts = 0;
510  	   }
511  	
512  	   /* a cut is forced to enter the LP if
513  	    *  - we construct the initial LP, or
514  	    *  - it has infinite score factor, or
515  	    *  - it is a bound change that can be applied
516  	    * if it is a non-forced cut and no cuts should be added, abort
517  	    */
518  	   forcecut = forcecut || sepastore->initiallp || sepastore->forcecuts || (!SCIProwIsModifiable(cut) && SCIProwGetNNonz(cut) == 1 && sepastoreIsBdchgApplicable(set, cut));
519  	   if( !forcecut && SCIPsetGetSepaMaxcuts(set, root) == 0 )
520  	      return SCIP_OKAY;
521  	
522  	   /* get enough memory to store the cut */
523  	   SCIP_CALL( sepastoreEnsureCutsMem(sepastore, set, sepastore->ncuts+1) );
524  	   assert(sepastore->ncuts < sepastore->cutssize);
525  	
526  	   SCIPsetDebugMsg(set, "adding cut <%s> to separation storage of size %d (forcecut=%u, len=%d)\n",
527  	      SCIProwGetName(cut), sepastore->ncuts, forcecut, SCIProwGetNNonz(cut));
528  	   /*SCIP_CALL( SCIPprintRow(set->scip, cut, NULL) );*/
529  	
530  	   /* capture the cut */
531  	   SCIProwCapture(cut);
532  	
533  	   /* add cut to arrays */
534  	   if( forcecut )
535  	   {
536  	      /* make room at the beginning of the array for forced cut */
537  	      pos = sepastore->nforcedcuts;
538  	      sepastore->cuts[sepastore->ncuts] = sepastore->cuts[pos];
539  	      sepastore->nforcedcuts++;
540  	   }
541  	   else
542  	      pos = sepastore->ncuts;
543  	
544  	   sepastore->cuts[pos] = cut;
545  	
546  	   /* update statistics of total number of found cuts */
547  	   if( !sepastore->initiallp )
548  	   {
549  	      sepastore->ncutsadded++;
550  	      sepastore->ncutsfoundround++;
551  	      if( cut->fromcutpool )
552  	         sepastore->ncutsaddedviapool++;
553  	      else
554  	         sepastore->ncutsaddeddirect++;
555  	
556  	      if( (SCIP_ROWORIGINTYPE) cut->origintype == SCIP_ROWORIGINTYPE_SEPA )
557  	      {
558  	         SCIP_SEPA* sepa;
559  	
560  	         sepa = SCIProwGetOriginSepa(cut);
561  	         SCIPsepaIncNCutsAdded(sepa, cut->fromcutpool);
562  	      }
563  	   }
564  	   sepastore->ncuts++;
565  	
566  	   /* check, if the row addition to separation storage events are tracked if so, issue ROWADDEDSEPA event */
567  	   if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWADDEDSEPA) != 0 )
568  	   {
569  	      SCIP_EVENT* event;
570  	
571  	      SCIP_CALL( SCIPeventCreateRowAddedSepa(&event, blkmem, cut) );
572  	      SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
573  	   }
574  	
575  	   /* If the duals need to be collected, then the infeasible flag is set to FALSE. This ensures that the LP is solved */
576  	   if( set->lp_alwaysgetduals && sepastore->initiallp )
577  	      (*infeasible) = FALSE;
578  	
579  	   return SCIP_OKAY;
580  	}
581  	
582  	/** applies a lower bound change */
583  	static
584  	SCIP_RETCODE sepastoreApplyLb(
585  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
586  	   BMS_BLKMEM*           blkmem,             /**< block memory */
587  	   SCIP_SET*             set,                /**< global SCIP settings */
588  	   SCIP_STAT*            stat,               /**< problem statistics */
589  	   SCIP_PROB*            transprob,          /**< transformed problem */
590  	   SCIP_PROB*            origprob,           /**< original problem */
591  	   SCIP_TREE*            tree,               /**< branch and bound tree */
592  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
593  	   SCIP_LP*              lp,                 /**< LP data */
594  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
595  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
596  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
597  	   SCIP_VAR*             var,                /**< problem variable */
598  	   SCIP_Real             bound,              /**< new lower bound of variable */
599  	   SCIP_Bool             local,              /**< is it a local bound change? (otherwise global) */
600  	   SCIP_Bool*            applied,            /**< pointer to store whether the domain change was applied */
601  	   SCIP_Bool*            cutoff              /**< pointer to store TRUE, if an infeasibility has been detected */
602  	   )
603  	{
604  	   assert(sepastore != NULL);
605  	   assert(cutoff != NULL);
606  	   assert(applied != NULL);
607  	
608  	   /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */
609  	   SCIPvarAdjustLb(var, set, &bound);
610  	
611  	   if( local )
612  	   {
613  	      /* apply the local bound change or detect a cutoff */
614  	      if( SCIPsetIsGT(set, bound, SCIPvarGetLbLocal(var)) )
615  	      {
616  	         SCIPsetDebugMsg(set, " -> applying bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
617  	            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bound, SCIPvarGetUbLocal(var));
618  	
619  	         /* changing the lower bound to a value >= SCIPinfinity should result in a cutoff,
620  	          * since "infinite" values in solutions are reserved for another meaning
621  	          */
622  	         if( !SCIPsetIsInfinity(set, bound) && SCIPsetIsFeasLE(set, bound, SCIPvarGetUbLocal(var)) )
623  	         {
624  	            SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree,
625  	                  reopt, lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_LOWER, FALSE) );
626  	         }
627  	         else
628  	            *cutoff = TRUE;
629  	
630  	         *applied = TRUE;
631  	      }
632  	      else
633  	      {
634  	         SCIPsetDebugMsg(set, " -> ignoring bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
635  	            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), bound, SCIPvarGetUbLocal(var));
636  	      }
637  	   }
638  	   else
639  	   {
640  	      /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */
641  	      if( SCIPsetIsGT(set, bound, SCIPvarGetLbGlobal(var)) )
642  	      {
643  	         SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
644  	            SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), bound, SCIPvarGetUbGlobal(var));
645  	
646  	         /* changing the lower bound to a value >= SCIPinfinity should result in a cutoff,
647  	          * since "infinite" values in solutions are reserved for another meaning
648  	          */
649  	         if( !SCIPsetIsInfinity(set, bound) && SCIPsetIsFeasLE(set, bound, SCIPvarGetUbGlobal(var)) )
650  	         {
651  	            SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt,
652  	                  lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_LOWER, FALSE) );
653  	         }
654  	         else
655  	         {
656  	            /* we are done with solving since a global bound change is infeasible */
657  	            SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
658  	            *cutoff = TRUE;
659  	         }
660  	
661  	         *applied = TRUE;
662  	      }
663  	      else
664  	      {
665  	         SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
666  	            SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), bound, SCIPvarGetUbGlobal(var));
667  	      }
668  	   }
669  	
670  	   return SCIP_OKAY;
671  	}
672  	
673  	/** applies an upper bound change */
674  	static
675  	SCIP_RETCODE sepastoreApplyUb(
676  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
677  	   BMS_BLKMEM*           blkmem,             /**< block memory */
678  	   SCIP_SET*             set,                /**< global SCIP settings */
679  	   SCIP_STAT*            stat,               /**< problem statistics */
680  	   SCIP_PROB*            transprob,          /**< transformed problem */
681  	   SCIP_PROB*            origprob,           /**< original problem */
682  	   SCIP_TREE*            tree,               /**< branch and bound tree */
683  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
684  	   SCIP_LP*              lp,                 /**< LP data */
685  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
686  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
687  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
688  	   SCIP_VAR*             var,                /**< problem variable */
689  	   SCIP_Real             bound,              /**< new upper bound of variable */
690  	   SCIP_Bool             local,              /**< is it a local bound change? (otherwise global) */
691  	   SCIP_Bool*            applied,            /**< pointer to store whether the domain change was applied */
692  	   SCIP_Bool*            cutoff              /**< pointer to store TRUE, if an infeasibility has been detected */
693  	   )
694  	{
695  	   assert(sepastore != NULL);
696  	   assert(cutoff != NULL);
697  	   assert(applied != NULL);
698  	
699  	   /* adjust bound to the one that would be applied, so the SCIPsetIsGT check below is more reliable */
700  	   SCIPvarAdjustUb(var, set, &bound);
701  	
702  	   if( local )
703  	   {
704  	      /* apply the local bound change or detect a cutoff */
705  	      if( SCIPsetIsLT(set, bound, SCIPvarGetUbLocal(var)) )
706  	      {
707  	         SCIPsetDebugMsg(set, " -> applying bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
708  	            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var), bound);
709  	
710  	         /* changing the upper bound to a value <= -SCIPinfinity should result in a cutoff,
711  	          * since "infinite" values in solutions are reserved for another meaning
712  	          */
713  	         if( !SCIPsetIsInfinity(set, -bound) && SCIPsetIsFeasGE(set, bound, SCIPvarGetLbLocal(var)) )
714  	         {
715  	            SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetCurrentNode(tree), blkmem, set, stat, transprob, origprob, tree,
716  	                  reopt, lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_UPPER, FALSE) );
717  	         }
718  	         else
719  	            *cutoff = TRUE;
720  	
721  	         *applied = TRUE;
722  	      }
723  	      else
724  	      {
725  	         SCIPsetDebugMsg(set, " -> ignoring bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
726  	            SCIPvarGetName(var), SCIPvarGetLbLocal(var), SCIPvarGetUbLocal(var), SCIPvarGetLbLocal(var), bound);
727  	      }
728  	   }
729  	   else
730  	   {
731  	      /* apply the global bound change or detect a global cutoff which means we can cutoff the root node */
732  	      if( SCIPsetIsLT(set, bound, SCIPvarGetUbGlobal(var)) )
733  	      {
734  	         SCIPsetDebugMsg(set, " -> applying global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
735  	            SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), SCIPvarGetLbGlobal(var), bound);
736  	
737  	         /* changing the upper bound to a value <= -SCIPinfinity should result in a cutoff,
738  	          * since "infinite" values in solutions are reserved for another meaning
739  	          */
740  	         if( !SCIPsetIsInfinity(set, -bound) && SCIPsetIsFeasGE(set, bound, SCIPvarGetLbGlobal(var)) )
741  	         {
742  	            SCIP_CALL( SCIPnodeAddBoundchg(SCIPtreeGetRootNode(tree), blkmem, set, stat, transprob, origprob, tree, reopt,
743  	                  lp, branchcand, eventqueue, cliquetable, var, bound, SCIP_BOUNDTYPE_UPPER, FALSE) );
744  	         }
745  	         else
746  	         {
747  	            /* we are done with solving since a global bound change is infeasible */
748  	            SCIP_CALL( SCIPnodeCutoff(SCIPtreeGetRootNode(tree), set, stat, tree, transprob, origprob, reopt, lp, blkmem) );
749  	            *cutoff = TRUE;
750  	         }
751  	
752  	         *applied = TRUE;
753  	      }
754  	      else
755  	      {
756  	         SCIPsetDebugMsg(set, " -> ignoring global bound change: <%s>: [%.15g,%.15g] -> [%.15g,%.15g]\n",
757  	            SCIPvarGetName(var), SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var), SCIPvarGetLbGlobal(var), bound);
758  	      }
759  	   }
760  	
761  	   return SCIP_OKAY;
762  	}
763  	
764  	/** applies a cut that is a bound change directly as bound change instead of adding it as row to the LP */
765  	static
766  	SCIP_RETCODE sepastoreApplyBdchg(
767  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
768  	   BMS_BLKMEM*           blkmem,             /**< block memory */
769  	   SCIP_SET*             set,                /**< global SCIP settings */
770  	   SCIP_STAT*            stat,               /**< problem statistics */
771  	   SCIP_PROB*            transprob,          /**< transformed problem */
772  	   SCIP_PROB*            origprob,           /**< original problem */
773  	   SCIP_TREE*            tree,               /**< branch and bound tree */
774  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
775  	   SCIP_LP*              lp,                 /**< LP data */
776  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
777  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
778  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
779  	   SCIP_ROW*             cut,                /**< cut with a single variable */
780  	   SCIP_Bool*            applied,            /**< pointer to store whether the domain change was applied */
781  	   SCIP_Bool*            cutoff              /**< pointer to store whether an empty domain was created */
782  	   )
783  	{
784  	   SCIP_COL** cols;
785  	   SCIP_Real* vals;
786  	   SCIP_VAR* var;
787  	   SCIP_Real lhs;
788  	   SCIP_Real rhs;
789  	   SCIP_Bool local;
790  	
791  	   assert(sepastore != NULL);
792  	   assert(!SCIProwIsModifiable(cut));
793  	   assert(SCIProwGetNNonz(cut) == 1);
794  	   assert(cutoff != NULL);
795  	   assert(applied != NULL);
796  	
797  	   *applied = FALSE;
798  	   *cutoff = FALSE;
799  	
800  	   /* get the single variable and its coefficient of the cut */
801  	   cols = SCIProwGetCols(cut);
802  	   assert(cols != NULL);
803  	
804  	   var = SCIPcolGetVar(cols[0]);
805  	   vals = SCIProwGetVals(cut);
806  	   assert(vals != NULL);
807  	   assert(!SCIPsetIsZero(set, vals[0]));
808  	
809  	   /* if the coefficient is nearly zero, we better ignore this cut for numerical reasons */
810  	   if( SCIPsetIsFeasZero(set, vals[0]) )
811  	      return SCIP_OKAY;
812  	
813  	   local = SCIProwIsLocal(cut);
814  	
815  	   /* get the left hand side of the cut and convert it to a bound */
816  	   lhs = SCIProwGetLhs(cut);
817  	   if( !SCIPsetIsInfinity(set, -lhs) )
818  	   {
819  	      lhs -= SCIProwGetConstant(cut);
820  	      if( vals[0] > 0.0 )
821  	      {
822  	         /* coefficient is positive -> lhs corresponds to lower bound */
823  	         SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
824  	               cliquetable, var, lhs/vals[0], local, applied, cutoff) );
825  	      }
826  	      else
827  	      {
828  	         /* coefficient is negative -> lhs corresponds to upper bound */
829  	         SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
830  	               cliquetable, var, lhs/vals[0], local, applied, cutoff) );
831  	      }
832  	   }
833  	
834  	   /* get the right hand side of the cut and convert it to a bound */
835  	   rhs = SCIProwGetRhs(cut);
836  	   if( !SCIPsetIsInfinity(set, rhs) )
837  	   {
838  	      rhs -= SCIProwGetConstant(cut);
839  	      if( vals[0] > 0.0 )
840  	      {
841  	         /* coefficient is positive -> rhs corresponds to upper bound */
842  	         SCIP_CALL( sepastoreApplyUb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
843  	               cliquetable, var, rhs/vals[0], local, applied, cutoff) );
844  	      }
845  	      else
846  	      {
847  	         /* coefficient is negative -> rhs corresponds to lower bound */
848  	         SCIP_CALL( sepastoreApplyLb(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand, eventqueue,
849  	               cliquetable, var, rhs/vals[0], local, applied, cutoff) );
850  	      }
851  	   }
852  	
853  	   /* count the bound change as applied cut */
854  	   if( *applied && !sepastore->initiallp )
855  	      sepastore->ncutsapplied++;
856  	
857  	   return SCIP_OKAY;
858  	}
859  	
860  	/** applies the given cut to the LP and updates the orthogonalities and scores of remaining cuts */
861  	static
862  	SCIP_RETCODE sepastoreApplyCut(
863  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
864  	   BMS_BLKMEM*           blkmem,             /**< block memory */
865  	   SCIP_SET*             set,                /**< global SCIP settings */
866  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
867  	   SCIP_EVENTFILTER*     eventfilter,        /**< global event filter */
868  	   SCIP_LP*              lp,                 /**< LP data */
869  	   SCIP_ROW*             cut,                /**< cut to apply to the LP */
870  	   int                   depth,              /**< depth of current node */
871  	   int*                  ncutsapplied        /**< pointer to count the number of applied cuts */
872  	   )
873  	{
874  	   assert(sepastore != NULL);
875  	   assert(ncutsapplied != NULL);
876  	
877  	   /* a row could have been added twice to the separation store; add it only once! */
878  	   if( !SCIProwIsInLP(cut) )
879  	   {
880  	      /* add cut to the LP and capture it */
881  	      SCIP_CALL( SCIPlpAddRow(lp, blkmem, set, eventqueue, eventfilter, cut, depth) );
882  	
883  	      /* update statistics -> only if we are not in the initial lp (cuts are only counted if added during run) */
884  	      if( !sepastore->initiallp )
885  	      {
886  	         sepastore->ncutsapplied++;
887  	
888  	         /* increase count of applied cuts for origins of row */
889  	         /* TODO: adjust conshdlr statistics to mirror cut statistics */
890  	         switch ( (SCIP_ROWORIGINTYPE) cut->origintype )
891  	         {
892  	         case SCIP_ROWORIGINTYPE_CONSHDLR:
893  	            assert( cut->origin != NULL );
894  	            SCIPconshdlrIncNAppliedCuts((SCIP_CONSHDLR*) cut->origin);
895  	            break;
896  	         case SCIP_ROWORIGINTYPE_CONS:
897  	            assert( cut->origin != NULL );
898  	            SCIPconshdlrIncNAppliedCuts(SCIPconsGetHdlr((SCIP_CONS*)cut->origin));
899  	            break;
900  	         case SCIP_ROWORIGINTYPE_SEPA:
901  	            assert( cut->origin != NULL );
902  	            SCIPsepaIncNCutsApplied((SCIP_SEPA*)cut->origin, cut->fromcutpool);
903  	            break;
904  	         case SCIP_ROWORIGINTYPE_UNSPEC:
905  	         case SCIP_ROWORIGINTYPE_REOPT:
906  	            /* do nothing - cannot update statistics */
907  	            break;
908  	         default:
909  	            SCIPerrorMessage("unknown type of row origin.\n");
910  	            return SCIP_INVALIDDATA;
911  	         }
912  	      }
913  	
914  	      (*ncutsapplied)++;
915  	   }
916  	
917  	   return SCIP_OKAY;
918  	}
919  	
920  	/** adds cuts to the LP and clears separation storage */
921  	SCIP_RETCODE SCIPsepastoreApplyCuts(
922  	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
923  	   BMS_BLKMEM*           blkmem,             /**< block memory */
924  	   SCIP_SET*             set,                /**< global SCIP settings */
925  	   SCIP_STAT*            stat,               /**< problem statistics */
926  	   SCIP_PROB*            transprob,          /**< transformed problem */
927  	   SCIP_PROB*            origprob,           /**< original problem */
928  	   SCIP_TREE*            tree,               /**< branch and bound tree */
929  	   SCIP_REOPT*           reopt,              /**< reoptimization data structure */
930  	   SCIP_LP*              lp,                 /**< LP data */
931  	   SCIP_BRANCHCAND*      branchcand,         /**< branching candidate storage */
932  	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
933  	   SCIP_EVENTFILTER*     eventfilter,        /**< global event filter */
934  	   SCIP_CLIQUETABLE*     cliquetable,        /**< clique table data structure */
935  	   SCIP_Bool             root,               /**< are we at the root node? */
936  	   SCIP_EFFICIACYCHOICE  efficiacychoice,    /**< type of solution to base efficiacy computation on */
937  	   SCIP_Bool*            cutoff              /**< pointer to store whether an empty domain was created */
938  	   )
939  	{
940  	   SCIP_NODE* node;
941  	   int maxsepacuts;
942  	   int ncutsapplied;
943  	   int nselectedcuts;
944  	   int depth;
945  	   int i;
946  	
947  	   assert(sepastore != NULL);
948  	   assert(set != NULL);
949  	   assert(tree != NULL);
950  	   assert(lp != NULL);
951  	   assert(cutoff != NULL);
952  	
953  	   SCIP_UNUSED(efficiacychoice);
954  	
955  	   SCIPsetDebugMsg(set, "selecting from %d cuts\n", sepastore->ncuts);
956  	
957  	   /* get maximal number of cuts to add to the LP */
958  	   maxsepacuts = SCIPsetGetSepaMaxcuts(set, root);
959  	
960  	   /* if all cuts are forced cuts, no selection is required */
961  	   if( sepastore->nforcedcuts >= MIN(sepastore->ncuts, maxsepacuts) )
962  	   {
963  	      nselectedcuts = sepastore->nforcedcuts;
964  	   }
965  	   else
966  	   {
967  	      /* call cut selection algorithms */
968  	      nselectedcuts = 0;
969  	      SCIP_CALL( SCIPcutselsSelect(set, sepastore->cuts, sepastore->ncuts, sepastore->nforcedcuts, root, sepastore->initiallp, maxsepacuts,
970  	            &nselectedcuts) );
971  	      assert(nselectedcuts + sepastore->nforcedcuts <= maxsepacuts);
972  	
973  	      /* note that cut selector statistics are updated here also when in probing mode; this may lead to an offset with
974  	       * separator/constraint handler statistics */
975  	      /* @todo do not update cutselector statistics if SCIPtreeProbing(scip->tree) */
976  	      nselectedcuts += sepastore->nforcedcuts;
977  	   }
978  	
979  	   /*
980  	    * apply all selected cuts
981  	    */
982  	   ncutsapplied = 0;
983  	   *cutoff = FALSE;
984  	
985  	   node = SCIPtreeGetCurrentNode(tree);
986  	   assert(node != NULL);
987  	
988  	   /* get depth of current node */
989  	   depth = SCIPnodeGetDepth(node);
990  	
991  	   for( i = 0; i < nselectedcuts && !(*cutoff); i++ )
992  	   {
993  	      SCIP_ROW* cut;
994  	
995  	      cut = sepastore->cuts[i];
996  	
997  	      if( i < sepastore->nforcedcuts || SCIPsetIsFeasPositive(set, SCIProwGetLPEfficacy(cut, set, stat, lp)) )
998  	      {
999  	         SCIP_Bool applied = FALSE;
1000 	
1001 	         /* if the cut is a bound change (i.e. a row with only one variable), add it as bound change instead of LP row */
1002 	         if( !SCIProwIsModifiable(cut) && SCIProwGetNNonz(cut) == 1 )
1003 	         {
1004 	            SCIPsetDebugMsg(set, " -> applying forced cut <%s> as boundchange\n", SCIProwGetName(cut));
1005 	            SCIP_CALL( sepastoreApplyBdchg(sepastore, blkmem, set, stat, transprob, origprob, tree, reopt, lp, branchcand,
1006 	                  eventqueue, cliquetable, cut, &applied, cutoff) );
1007 	            assert(applied || !sepastoreIsBdchgApplicable(set, cut));
1008 	         }
1009 	
1010 	         if( !applied )
1011 	         {
1012 	            /* add cut to the LP and update orthogonalities */
1013 	            SCIPsetDebugMsg(set, " -> applying%s cut <%s>\n", (i < sepastore->nforcedcuts) ? " forced" : "", SCIProwGetName(cut));
1014 	            /*SCIPdebug( SCIProwPrint(cut, set->scip->messagehdlr, NULL));*/
1015 	            SCIP_CALL( sepastoreApplyCut(sepastore, blkmem, set, eventqueue, eventfilter, lp, cut, depth, &ncutsapplied) );
1016 	         }
1017 	      }
1018 	   }
1019 	
1020 	   /* clear the separation storage and reset statistics for separation round */
1021 	   SCIP_CALL( SCIPsepastoreClearCuts(sepastore, blkmem, set, eventqueue, eventfilter, lp) );
1022 	
1023 	   return SCIP_OKAY;
1024 	}
1025 	
1026 	/** clears the separation storage without adding the cuts to the LP */
1027 	SCIP_RETCODE SCIPsepastoreClearCuts(
1028 	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
1029 	   BMS_BLKMEM*           blkmem,             /**< block memory */
1030 	   SCIP_SET*             set,                /**< global SCIP settings */
1031 	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
1032 	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global events */
1033 	   SCIP_LP*              lp                  /**< LP data */
1034 	   )
1035 	{
1036 	   int c;
1037 	
1038 	   assert(sepastore != NULL);
1039 	
1040 	   SCIPsetDebugMsg(set, "clearing %d cuts\n", sepastore->ncuts);
1041 	
1042 	   /* release cuts */
1043 	   for( c = 0; c < sepastore->ncuts; ++c )
1044 	   {
1045 	      /* check, if the row deletions from separation storage events are tracked if so, issue ROWDELETEDSEPA event */
1046 	      if( eventfilter->len > 0 && (eventfilter->eventmask & SCIP_EVENTTYPE_ROWDELETEDSEPA) != 0 )
1047 	      {
1048 	         SCIP_EVENT* event;
1049 	
1050 	         SCIP_CALL( SCIPeventCreateRowDeletedSepa(&event, blkmem, sepastore->cuts[c]) );
1051 	         SCIP_CALL( SCIPeventqueueAdd(eventqueue, blkmem, set, NULL, NULL, NULL, eventfilter, &event) );
1052 	      }
1053 	
1054 	      SCIP_CALL( SCIProwRelease(&sepastore->cuts[c], blkmem, set, lp) );
1055 	   }
1056 	
1057 	   /* reset counters */
1058 	   sepastore->ncuts = 0;
1059 	   sepastore->nforcedcuts = 0;
1060 	   sepastore->ncutsfoundround = 0;
1061 	
1062 	   /* if we have just finished the initial LP construction, free the (potentially large) cuts array */
1063 	   if( sepastore->initiallp )
1064 	   {
1065 	      BMSfreeMemoryArrayNull(&sepastore->cuts);
1066 	      sepastore->cutssize = 0;
1067 	   }
1068 	
1069 	   return SCIP_OKAY;
1070 	}
1071 	
1072 	/** removes cuts that are inefficacious w.r.t. the current LP solution from separation storage without adding the cuts to the LP */
1073 	SCIP_RETCODE SCIPsepastoreRemoveInefficaciousCuts(
1074 	   SCIP_SEPASTORE*       sepastore,          /**< separation storage */
1075 	   BMS_BLKMEM*           blkmem,             /**< block memory */
1076 	   SCIP_SET*             set,                /**< global SCIP settings */
1077 	   SCIP_STAT*            stat,               /**< problem statistics data */
1078 	   SCIP_EVENTQUEUE*      eventqueue,         /**< event queue */
1079 	   SCIP_EVENTFILTER*     eventfilter,        /**< event filter for global events */
1080 	   SCIP_LP*              lp,                 /**< LP data */
1081 	   SCIP_Bool             root,               /**< are we at the root node? */
1082 	   SCIP_EFFICIACYCHOICE  efficiacychoice     /**< type of solution to base efficiacy computation on */
1083 	   )
1084 	{
1085 	   int cnt = 0;
1086 	   int c;
1087 	
1088 	   assert( sepastore != NULL );
1089 	
1090 	   /* check non-forced cuts only */
1091 	   c = sepastore->nforcedcuts;
1092 	   while( c < sepastore->ncuts )
1093 	   {
1094 	      SCIP_Real cutefficacy;
1095 	
1096 	      /* calculate cut's efficacy */
1097 	      switch ( efficiacychoice )
1098 	      {
1099 	         case SCIP_EFFICIACYCHOICE_LP:
1100 	            cutefficacy = SCIProwGetLPEfficacy(sepastore->cuts[c], set, stat, lp);
1101 	            break;
1102 	         case SCIP_EFFICIACYCHOICE_RELAX:
1103 	            cutefficacy = SCIProwGetRelaxEfficacy(sepastore->cuts[c], set, stat);
1104 	            break;
1105 	         case SCIP_EFFICIACYCHOICE_NLP:
1106 	            cutefficacy = SCIProwGetNLPEfficacy(sepastore->cuts[c], set, stat);
1107 	            break;
1108 	         default:
1109 	            SCIPerrorMessage("Invalid efficiacy choice.\n");
1110 	            return SCIP_INVALIDCALL;
1111 	      }
1112 	
1113 	      if( !SCIPsetIsEfficacious(set, root, cutefficacy) )
1114 	      {
1115 	         SCIP_CALL( sepastoreDelCut(sepastore, blkmem, set, eventqueue, eventfilter, lp, c) );
1116 	         ++cnt;
1117 	      }
1118 	      else
1119 	         ++c;
1120 	   }
1121 	   SCIPsetDebugMsg(set, "removed %d non-efficacious cuts\n", cnt);
1122 	
1123 	   return SCIP_OKAY;
1124 	}
1125 	
1126 	/** indicates whether a cut is applicable
1127 	 *
1128 	 *  A cut is applicable if it is modifiable, not a bound change, or a bound change that changes bounds by at least epsilon.
1129 	 */
1130 	SCIP_Bool SCIPsepastoreIsCutApplicable(
1131 	   SCIP_SET*             set,                /**< global SCIP settings */
1132 	   SCIP_ROW*             cut                 /**< cut to check */
1133 	   )
1134 	{
1135 	   return SCIProwIsModifiable(cut) || SCIProwGetNNonz(cut) != 1 || sepastoreIsBdchgApplicable(set, cut);
1136 	}
1137 	
1138 	/** get cuts in the separation storage */
1139 	SCIP_ROW** SCIPsepastoreGetCuts(
1140 	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
1141 	   )
1142 	{
1143 	   assert(sepastore != NULL);
1144 	
1145 	   return sepastore->cuts;
1146 	}
1147 	
1148 	/** get number of cuts in the separation storage */
1149 	int SCIPsepastoreGetNCuts(
1150 	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
1151 	   )
1152 	{
1153 	   assert(sepastore != NULL);
1154 	
1155 	   return sepastore->ncuts;
1156 	}
1157 	
1158 	/** gets the total number of cutting planes added to the separation storage;
1159 	 *  this is equal to the sum of added cuts directly and via the pool. */
1160 	int SCIPsepastoreGetNCutsAdded(
1161 	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
1162 	   )
1163 	{
1164 	   assert(sepastore != NULL);
1165 	
1166 	   return sepastore->ncutsadded;
1167 	}
1168 	
1169 	/** gets the number of cutting planes added to the separation storage from the cut pool */
1170 	int SCIPsepastoreGetNCutsAddedViaPool(
1171 	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
1172 	   )
1173 	{
1174 	   assert(sepastore != NULL);
1175 	
1176 	   return sepastore->ncutsaddedviapool;
1177 	}
1178 	
1179 	/** gets the number of cutting planes added to the separation storage directly */
1180 	int SCIPsepastoreGetNCutsAddedDirect(
1181 	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
1182 	   )
1183 	{
1184 	   assert(sepastore != NULL);
1185 	
1186 	   return sepastore->ncutsaddeddirect;
1187 	}
1188 	
1189 	/** get number of cuts found so far in current separation round */
1190 	int SCIPsepastoreGetNCutsFoundRound(
1191 	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
1192 	   )
1193 	{
1194 	   assert(sepastore != NULL);
1195 	
1196 	   return sepastore->ncutsfoundround;
1197 	}
1198 	
1199 	/** gets the total number of cutting planes applied to the LP */
1200 	int SCIPsepastoreGetNCutsApplied(
1201 	   SCIP_SEPASTORE*       sepastore           /**< separation storage */
1202 	   )
1203 	{
1204 	   assert(sepastore != NULL);
1205 	
1206 	   return sepastore->ncutsapplied;
1207 	}
1208