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   sepa_mixing.c
26   	 * @ingroup DEFPLUGINS_SEPA
27   	 * @brief  mixing/star inequality separator
28   	 * @author Weikun Chen
29   	 * @author Marc Pfetsch
30   	 *
31   	 * This separator generates cuts based on the mixing set
32   	 * \f[
33   	 * X = \{ (x,y) \in \{0,1\}^{N \cup M} \times \mathbb{R} \, : \,  y \geq a_i x_i, \, \textrm{for} \, i \in N, \,
34   	 *                           y \leq u -  a_i x_i, \, \textrm{for} \, i \in M, \, 0 \leq y \leq u  \},
35   	 * \f]
36   	 * where \f$0 \leq a_i \leq u\f$ for all \f$i\f$. This information can be obtained directly from the variable bounds data
37   	 * structure. The separator will generate three classes of cuts.
38   	 *
39   	 * VLB: Let \f$T\f$ be a subset of \f$N\f$, wlog, \f$T = \{1,\ldots,r\}\f$ with \f$a_1 \leq a_2 \leq \ldots \leq a_r\f$.
40   	 * Let \f$a_0 = 0\f$. The mixing/star VLB cut is of the form \f$ y \geq \sum_{i=1}^r (a_i - a_{i-1})x_i \f$.
41   	 *
42   	 * VUB: Let \f$T\f$ be a subset of \f$M\f$, wlog, \f$T = \{1,\ldots,r\}\f$ with \f$a_1 \leq a_2 \leq \ldots \leq a_r\f$.
43   	 * Let \f$a_0 = 0\f$. The mixing/star VUB cut is of the form \f$ y \leq u - \sum_{i=1}^r (a_i - a_{i-1})x_i \f$.
44   	 *
45   	 * CONFLICT: Consider \f$i \in N\f$ and \f$j \in M\f$ with \f$a_i + a_j > u\f$. The conflict cut is
46   	 * \f$x_i + x_j \leq 1\f$.
47   	 *
48   	 * A small example is described in the following to see the generated cuts.
49   	 * \f[
50   	 * Y = \{ (x,y) \in \{0,1\}^{4} \times \mathbb{R} \, : \, y \geq 2x_1, \, y \geq 3x_2, \, y \leq 4 - x_3, \,
51   	 *                           y \leq 4 - 2 x_4, \, 0 \leq y \leq 4 \}.
52   	 * \f]
53   	 * In this small example, the mixing/star cuts \f$y \geq 2x_1 + x_2\f$ (VLB) and \f$y \leq 4 - x_3 - x_4\f$ (VUB) will be
54   	 * considered to be generated. Besides the mixing cuts, we also consider the conflict cut \f$x_1 + x_3 \leq 1\f$ (CONFLICT).
55   	 *
56   	 *
57   	 * For an overview see:
58   	 * Atamturk, A., Nemhauser, G.L. and Savelsbergh, M.W.,@n
59   	 * The mixed vertex packing problem.@n
60   	 * Mathematical Programming, 89(1), 35-53, 2000.
61   	 *
62   	 * Some remarks:
63   	 * - Besides the mixing inequality, we also add the conflict inequality.
64   	 * - Currently, the performance is bad on the neos-565672 instance.
65   	 *   The reason is that, after adding the separator, SCIP spends a lot of time at the stage of cutting plane generation.
66   	 * - We do not consider sparsity of the cuts as we aim to find a most violated cut.
67   	 * - Besides the most violated cut we consider, we also add an additional variable to make the cut be the strongest one,
68   	 *   even the additional variable does not contribute any to the violation.
69   	 *
70   	 */
71   	
72   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
73   	
74   	#include "blockmemshell/memory.h"
75   	#include "scip/pub_implics.h"
76   	#include "scip/pub_lp.h"
77   	#include "scip/pub_message.h"
78   	#include "scip/pub_misc.h"
79   	#include "scip/pub_sepa.h"
80   	#include "scip/pub_var.h"
81   	#include "scip/scip_branch.h"
82   	#include "scip/scip_cut.h"
83   	#include "scip/scip_lp.h"
84   	#include "scip/scip_mem.h"
85   	#include "scip/scip_message.h"
86   	#include "scip/scip_numerics.h"
87   	#include "scip/scip_param.h"
88   	#include "scip/scip_prob.h"
89   	#include "scip/scip_sepa.h"
90   	#include "scip/scip_sol.h"
91   	#include "scip/scip_solvingstats.h"
92   	#include "scip/scip_var.h"
93   	#include "scip/sepa_mixing.h"
94   	#include "scip/scip_tree.h"
95   	#include "scip/sepa_mixing.h"
96   	#include <string.h>
97   	
98   	
99   	#define SEPA_NAME              "mixing"
100  	#define SEPA_DESC              "mixing inequality separator"
101  	#define DEFAULT_MAXROUNDS            -1 /**< maximal number of mixing separation rounds per node (-1: unlimited) */
102  	#define DEFAULT_MAXROUNDSROOT        -1 /**< maximal number of mixing separation rounds in the root node (-1: unlimited) */
103  	#define SEPA_PRIORITY               -50
104  	#define SEPA_FREQ                    10
105  	#define SEPA_MAXBOUNDDIST           1.0
106  	#define SEPA_USESSUBSCIP          FALSE /**< does the separator use a secondary SCIP instance? */
107  	#define SEPA_DELAY                FALSE /**< should separation method be delayed, if other separators found cuts? */
108  	
109  	#define DEFAULT_USELOCALBOUNDS    FALSE /**< should local bounds be used? */
110  	#define DEFAULT_ISCUTSONINTS      FALSE /**< should general/implicit integer variables be used to generate cuts? */
111  	#define DEFAULT_MAXNUNSUCCESSFUL     10 /**< maximal number of consecutive unsuccessful iterations */
112  	
113  	/** separator-specific data for the mixing separator */
114  	struct SCIP_SepaData
115  	{
116  	   SCIP_Bool             uselocalbounds;     /**< should local bounds be used? */
117  	   SCIP_Bool             iscutsonints;       /**< should general/implicit integer variables be used to generate cuts? */
118  	   int                   maxrounds;          /**< maximal number of mixing separation rounds per node (-1: unlimited) */
119  	   int                   maxroundsroot;      /**< maximal number of mixing separation rounds in the root node (-1: unlimited) */
120  	   int                   nunsuccessful;      /**< number of consecutive unsuccessful iterations */
121  	   int                   maxnunsuccessful;   /**< maximal number of consecutive unsuccessful iterations */
122  	};
123  	
124  	/*
125  	 * local methods
126  	 */
127  	
128  	/** adds the given cut */
129  	static
130  	SCIP_RETCODE addCut(
131  	   SCIP*                 scip,               /**< SCIP data structure */
132  	   SCIP_SEPA*            sepa,               /**< separator */
133  	   SCIP_SOL*             sol,                /**< the solution that should be separated, or NULL for LP solution */
134  	   SCIP_Real*            cutcoefs,           /**< coefficients of active variables in cut */
135  	   int*                  cutinds,            /**< problem indices of variables in cut */
136  	   int                   cutnnz,             /**< number of non-zeros in cut */
137  	   SCIP_Real             cutrhs,             /**< right hand side of cut */
138  	   SCIP_Bool             cutislocal,         /**< Is the cut only locally valid? */
139  	   SCIP_Bool*            cutoff,             /**< pointer to store whether a cutoff has been detected */
140  	   int*                  ncuts               /**< pointer to update number of cuts added */
141  	   )
142  	{
143  	   char cutname[SCIP_MAXSTRLEN];
144  	   SCIP_VAR** vars;
145  	   SCIP_ROW* cut;
146  	   int v;
147  	
148  	   assert(cutcoefs != NULL);
149  	   assert(cutinds != NULL);
150  	   assert(ncuts != NULL);
151  	   assert(cutoff != NULL);
152  	
153  	   *cutoff = FALSE;
154  	
155  	   /* get active problem variables */
156  	   vars = SCIPgetVars(scip);
157  	
158  	   /* construct cut name */
159  	   (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "mix%" SCIP_LONGINT_FORMAT "_x%d", SCIPgetNLPs(scip), *ncuts);
160  	
161  	   /* create empty cut */
162  	   SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), cutrhs,
163  	         cutislocal, FALSE, TRUE) );
164  	
165  	   /* cache the row extension and only flush them if the cut gets added */
166  	   SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
167  	
168  	   /* collect all non-zero coefficients */
169  	   for( v = 0; v < cutnnz; ++v )
170  	   {
171  	      SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[v]], cutcoefs[v]) );
172  	   }
173  	
174  	   /* flush all changes before adding the cut */
175  	   SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
176  	
177  	   if( SCIPisCutEfficacious(scip, sol, cut) )
178  	   {
179  	      /* set cut rank */
180  	      SCIProwChgRank(cut, 1);
181  	
182  	#ifdef SCIP_DEBUG
183  	      SCIPdebugMsg(scip, "-> found cut (eff: %f): ", SCIPgetCutEfficacy(scip, sol, cut));
184  	      SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
185  	#endif
186  	
187  	      if( cutislocal )
188  	      {
189  	         /* local cuts are added to the sepastore */
190  	         SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
191  	      }
192  	      else
193  	      {
194  	         SCIP_CALL( SCIPaddPoolCut(scip, cut) );
195  	      }
196  	      (*ncuts)++;
197  	   }
198  	
199  	   /* release the row */
200  	   SCIP_CALL( SCIPreleaseRow(scip, &cut) );
201  	
202  	   return SCIP_OKAY;
203  	}
204  	
205  	/** searches and adds mixing cuts that are violated by the given solution value array
206  	 *
207  	 *  This function implements a separation heuristic that runs in linear time in comparison to the quadratic exact
208  	 *  algorithm in Atamturk et al.:
209  	 *  - Lower and upper bounds are considered separately. Then possible conflict cuts.
210  	 *  - Variable lower/upper bounds data are collected, i.e., the corresponding binary variables and coefficients.
211  	 *  - These lists are sorted non-increasingly according to the solution values.
212  	 *  - Then binary variables are added in turn as long as their coefficients increase in order to make the coefficients
213  	 *    nonnegative.  This clearly makes the cuts heuristic, since it is order dependent, but also sparser.
214  	 *  - The procedure stops as soon as it reaches 0 solution values.
215  	 *  - If the cut is efficious it is added.
216  	 *
217  	 *  @todo Check whether one wants to sort according to the quotient of solution values and coefficients to increase the
218  	 *  chance of having smaller coefficients in the front.
219  	 */
220  	static
221  	SCIP_RETCODE separateCuts(
222  	   SCIP*                 scip,               /**< SCIP data structure */
223  	   SCIP_SEPA*            sepa,               /**< separator */
224  	   SCIP_SOL*             sol,                /**< the solution that should be separated, or NULL for LP solution */
225  	   SCIP_Bool*            cutoff,             /**< whether a cutoff has been detected */
226  	   int*                  ncuts               /**< pointer to store the number of generated cuts */
227  	   )
228  	{
229  	   SCIP_SEPADATA* sepadata;
230  	   SCIP_VAR* var;
231  	   SCIP_VAR** vars;
232  	   SCIP_Real* vlbmixcoefs;
233  	   SCIP_Real* vlbmixsols;
234  	   SCIP_Real* vubmixcoefs;
235  	   SCIP_Real* vubmixsols;
236  	   SCIP_Real* cutcoefs;
237  	   SCIP_Real cutrhs;
238  	   int* vlbmixinds;
239  	   int* vubmixinds;
240  	   int* cutinds;
241  	   int* vlbmixsigns;
242  	   int* vubmixsigns;
243  	   int firstvar;
244  	   int nmaxvars;
245  	   int nvars;
246  	   int i;
247  	   int k;
248  	
249  	   assert(sepa != NULL);
250  	   assert(cutoff != NULL);
251  	   assert(ncuts != NULL);
252  	
253  	   *cutoff = FALSE;
254  	   *ncuts = 0;
255  	
256  	   /* exit if there are no binary variables - ignore integer variables that have 0/1 bounds */
257  	   nmaxvars = SCIPgetNBinVars(scip);
258  	   if( nmaxvars <= 0 )
259  	      return SCIP_OKAY;
260  	
261  	   sepadata = SCIPsepaGetData(sepa);
262  	   assert(sepadata != NULL);
263  	
264  	   /* get the index of the first considered variable */
265  	   if( sepadata->iscutsonints )
266  	   {
267  	      /* generate cuts based on all nonbinary variabels */
268  	      firstvar = SCIPgetNBinVars(scip);
269  	   }
270  	   else
271  	   {
272  	      /* only generate cuts based on continuous variables */
273  	      firstvar = SCIPgetNBinVars(scip) + SCIPgetNIntVars(scip) + SCIPgetNImplVars(scip);
274  	   }
275  	   nvars = SCIPgetNVars(scip);
276  	   if( firstvar == nvars )
277  	      return SCIP_OKAY;
278  	
279  	   vars = SCIPgetVars(scip);
280  	
281  	   /* allocate temporary memory */
282  	   SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixcoefs, nmaxvars) );
283  	   SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixsols, nmaxvars) );
284  	   SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixinds, nmaxvars) );
285  	   SCIP_CALL( SCIPallocBufferArray(scip, &vlbmixsigns, nmaxvars) );
286  	   SCIP_CALL( SCIPallocBufferArray(scip, &vubmixcoefs, nmaxvars) );
287  	   SCIP_CALL( SCIPallocBufferArray(scip, &vubmixsols, nmaxvars) );
288  	   SCIP_CALL( SCIPallocBufferArray(scip, &vubmixinds, nmaxvars) );
289  	   SCIP_CALL( SCIPallocBufferArray(scip, &vubmixsigns, nmaxvars) );
290  	   SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nmaxvars + 1) );
291  	   SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nmaxvars + 1) );
292  	
293  	   for( i = firstvar; i < nvars; i++ )
294  	   {
295  	      SCIP_VAR** vlbvars;
296  	      SCIP_Real* vlbcoefs;
297  	      SCIP_Real* vlbconsts;
298  	      SCIP_VAR** vubvars;
299  	      SCIP_Real* vubcoefs;
300  	      SCIP_Real* vubconsts;
301  	      SCIP_Real maxabscoef;
302  	      SCIP_Real activity;
303  	      SCIP_Real lastcoef;
304  	      SCIP_Real varsolval;
305  	      SCIP_Real lb = SCIP_INVALID;
306  	      SCIP_Real ub = SCIP_INVALID;
307  	      SCIP_Bool islocallb = FALSE;  /* Is it a local lower bound or global lower bound? */
308  	      SCIP_Bool islocalub = FALSE;  /* Is it a local upper bound or global upper bound? */
309  	      SCIP_Bool cutislocal; /* Is it a local cut or global cut? */
310  	      int vlbmixsize = 0;
311  	      int vubmixsize = 0;
312  	      int cutnnz = 0;
313  	      int maxabsind;
314  	      int maxabssign;
315  	      int nvlb;
316  	      int nvub;
317  	      int j;
318  	
319  	      var = vars[i];
320  	      assert( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY );
321  	
322  	      if( SCIPvarGetProbindex(var) < 0 )
323  	         continue;
324  	
325  	      nvlb = SCIPvarGetNVlbs(var);
326  	      nvub = SCIPvarGetNVubs(var);
327  	
328  	      if( nvlb == 0 && nvub == 0 )
329  	         continue;
330  	
331  	      /* skip lower bound if the LP solution value is equal to the upper bound of the continuous variable */
332  	      varsolval = SCIPgetSolVal(scip, sol, var);
333  	      if( SCIPisFeasEQ(scip, SCIPvarGetUbLocal(var), varsolval) )
334  	         goto VUB;
335  	
336  	      if( nvlb == 0 )
337  	         goto VUB;
338  	
339  	      /* get variable lower variable bounds information */
340  	      vlbvars = SCIPvarGetVlbVars(var);
341  	      vlbcoefs = SCIPvarGetVlbCoefs(var);
342  	      vlbconsts = SCIPvarGetVlbConstants(var);
343  	
344  	      maxabscoef = 0.0;
345  	      maxabsind = -1;
346  	      maxabssign = 0;
347  	
348  	      lb = SCIPvarGetLbGlobal(var);
349  	      if( sepadata->uselocalbounds && SCIPisLT(scip, lb, SCIPvarGetLbLocal(var)) )
350  	      {
351  	         /* this is a lcoal cut */
352  	         islocallb = TRUE;
353  	         lb = SCIPvarGetLbLocal(var);
354  	      }
355  	
356  	#ifdef SCIP_DEBUG
357  	      for( j = 0; j < nvlb; j++ )
358  	      {
359  	         SCIP_Real tmplb;
360  	
361  	         if( SCIPvarIsBinary(vlbvars[j]) && SCIPvarGetProbindex(vlbvars[j]) >= 0 )
362  	         {
363  	            tmplb = (vlbcoefs[j] > 0) ? vlbconsts[j] : (vlbconsts[j] + vlbcoefs[j]);
364  	            assert( SCIPisFeasLE(scip, tmplb, lb) );
365  	         }
366  	      }
367  	#endif
368  	
369  	      assert( SCIPisFeasLE(scip, lb, SCIPvarGetUbLocal(var)) );
370  	
371  	      /* extract the useful variable bounds information (binary and nonredundant) */
372  	      for( j = 0; j < nvlb; j++ )
373  	      {
374  	         /* consider only active and binary variables */
375  	         if( SCIPvarIsBinary(vlbvars[j]) && SCIPvarGetProbindex(vlbvars[j]) >= 0 )
376  	         {
377  	            SCIP_Real maxactivity;
378  	            SCIP_Real coef;
379  	
380  	            maxactivity = (vlbcoefs[j] > 0) ? (vlbconsts[j] + vlbcoefs[j]) : vlbconsts[j];
381  	
382  	            /* skip redundant variable bound constraints */
383  	            if( SCIPisFeasLE(scip, maxactivity, lb) )
384  	               continue;
385  	
386  	            if( vlbcoefs[j] > 0 )
387  	            {
388  	               coef = maxactivity - lb;
389  	               vlbmixsigns[vlbmixsize] = 0;
390  	            }
391  	            else
392  	            {
393  	               coef = lb - maxactivity;
394  	               vlbmixsigns[vlbmixsize] = 1;
395  	            }
396  	            assert(vlbmixsize <= nvars);
397  	
398  	            vlbmixcoefs[vlbmixsize] = REALABS(coef);
399  	            vlbmixinds[vlbmixsize] = SCIPvarGetProbindex(vlbvars[j]);
400  	            vlbmixsols[vlbmixsize] = (! vlbmixsigns[vlbmixsize]) ? SCIPgetSolVal(scip, sol, vlbvars[j]) : (1.0 - SCIPgetSolVal(scip, sol, vlbvars[j]));
401  	
402  	            /* update the maximal coefficient if needed */
403  	            if( maxabscoef < vlbmixcoefs[vlbmixsize] )
404  	            {
405  	               maxabscoef = vlbmixcoefs[vlbmixsize];
406  	               maxabsind = vlbmixinds[vlbmixsize];
407  	               maxabssign = vlbmixsigns[vlbmixsize];
408  	            }
409  	
410  	            ++vlbmixsize;
411  	
412  	            /* stop if size is exceeded; possibly ignore redundant variable bounds */
413  	            if( vlbmixsize >= nmaxvars )
414  	               break;
415  	         }
416  	      }
417  	      assert( vlbmixsize <= nmaxvars );
418  	
419  	      /* stop if no variable lower bounds information exists */
420  	      if( vlbmixsize == 0 )
421  	         goto VUB;
422  	
423  	      /* stop if the current solution value of the transformed continuous variable is larger than the maximal coefficient */
424  	      if( SCIPisFeasGT(scip, varsolval - lb, maxabscoef) )
425  	         goto VUB;
426  	
427  	      /* sort the solution values in non-increasing order */
428  	      SCIPsortDownRealRealIntInt(vlbmixsols, vlbmixcoefs, vlbmixinds, vlbmixsigns, vlbmixsize);
429  	
430  	      /* add the continuous variable */
431  	      cutcoefs[cutnnz] = -1;
432  	      cutinds[cutnnz] = SCIPvarGetProbindex(var);
433  	      cutrhs = -lb;
434  	      cutnnz++;
435  	
436  	      activity = -(varsolval - lb);
437  	      lastcoef = 0.0;
438  	
439  	      /* loop over the variables and add the variable to the cut if its coefficient is larger than that of the last variable */
440  	      for( j = 0; j < vlbmixsize; j++ )
441  	      {
442  	         SCIP_Real solval;
443  	
444  	         solval = vlbmixsols[j];
445  	
446  	         /* stop if we can not find a violated cut or we reached 0 solution values */
447  	         if( activity + solval * (maxabscoef - lastcoef) < 0.0 || SCIPisFeasZero(scip, solval) )
448  	            break;
449  	         else
450  	         {
451  	            /* skip if we have already added a variable with bigger coefficient */
452  	            if( SCIPisLE(scip, vlbmixcoefs[j], lastcoef) )
453  	               continue;
454  	            else
455  	            {
456  	               activity += (vlbmixcoefs[j] - lastcoef) * solval;
457  	               if( vlbmixsigns[j] )
458  	               {
459  	                  cutcoefs[cutnnz] = lastcoef - vlbmixcoefs[j];
460  	                  cutrhs -= vlbmixcoefs[j] - lastcoef;
461  	               }
462  	               else
463  	                  cutcoefs[cutnnz] = vlbmixcoefs[j] - lastcoef;
464  	               cutinds[cutnnz++] = vlbmixinds[j];
465  	               lastcoef = vlbmixcoefs[j];
466  	            }
467  	         }
468  	      }
469  	
470  	      /* add the variable with maximal coefficient to make sure the cut is strong enough */
471  	      if( SCIPisGT(scip, maxabscoef, lastcoef) )
472  	      {
473  	         /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */
474  	         if( maxabssign )
475  	         {
476  	            cutcoefs[cutnnz] = lastcoef - maxabscoef;
477  	            cutrhs -= maxabscoef - lastcoef;
478  	         }
479  	         else
480  	            cutcoefs[cutnnz] = maxabscoef - lastcoef;
481  	         cutinds[cutnnz++] = maxabsind;
482  	      }
483  	      assert( cutnnz <= nmaxvars + 1 );
484  	
485  	      /* add the cut if the violtion is good enough and the number of nonzero coefficients is larger than 2 */
486  	      if( SCIPisEfficacious(scip, activity) && cutnnz > 2 )
487  	      {
488  	         SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, islocallb, cutoff, ncuts) );
489  	      }
490  	
491  	   VUB:
492  	      if( nvub == 0 )
493  	         goto CONFLICT;
494  	
495  	      /* get variable upper bounds information */
496  	      vubvars = SCIPvarGetVubVars(var);
497  	      vubcoefs = SCIPvarGetVubCoefs(var);
498  	      vubconsts = SCIPvarGetVubConstants(var);
499  	
500  	      maxabscoef = 0.0;
501  	      maxabsind = -1;
502  	      maxabssign = 0;
503  	
504  	      /* stop if the lower bound is equal to the solution value of the continuous variable */
505  	      if( SCIPisFeasEQ(scip, SCIPvarGetLbLocal(var), varsolval) )
506  	         goto CONFLICT;
507  	
508  	      ub = SCIPvarGetUbGlobal(var);
509  	      if( sepadata->uselocalbounds && SCIPisGT(scip, ub, SCIPvarGetUbLocal(var)) )
510  	      {
511  	         /* this is a lcoal cut */
512  	         islocalub = TRUE;
513  	         ub = SCIPvarGetUbLocal(var);
514  	      }
515  	
516  	#ifdef SCIP_DEBUG
517  	      for( j = 0; j < nvub; j++ )
518  	      {
519  	         SCIP_Real tmpub;
520  	
521  	         if( SCIPvarIsBinary(vubvars[j]) && SCIPvarGetProbindex(vubvars[j]) >= 0 )
522  	         {
523  	            tmpub = (vubcoefs[j] < 0) ? vubconsts[j] : (vubconsts[j] + vubcoefs[j]);
524  	            assert( SCIPisFeasGE(scip, tmpub, ub) );
525  	         }
526  	      }
527  	#endif
528  	
529  	      assert( SCIPisFeasLE(scip, SCIPvarGetLbLocal(var), ub) );
530  	
531  	      /* extract the useful variable bounds information (binary and nonredundant) */
532  	      for( j = 0; j < nvub; j++ )
533  	      {
534  	         /* consider only active and binary variables */
535  	         if( SCIPvarIsBinary(vubvars[j]) && SCIPvarGetProbindex(vubvars[j]) >= 0 )
536  	         {
537  	            SCIP_Real minactivity;
538  	            SCIP_Real coef;
539  	
540  	            minactivity = (vubcoefs[j] < 0) ? (vubconsts[j] + vubcoefs[j]) : vubconsts[j];
541  	
542  	            /* skip redundant variable bound constraints */
543  	            if( SCIPisFeasLE(scip, ub, minactivity) )
544  	               continue;
545  	
546  	            if( vubcoefs[j] > 0 )
547  	            {
548  	               coef = ub - minactivity;
549  	               vubmixsigns[vubmixsize] = 1;
550  	            }
551  	            else
552  	            {
553  	               coef = minactivity - ub;
554  	               vubmixsigns[vubmixsize] = 0;
555  	            }
556  	
557  	            vubmixcoefs[vubmixsize] = REALABS(coef);
558  	            vubmixinds[vubmixsize] = SCIPvarGetProbindex(vubvars[j]);
559  	            vubmixsols[vubmixsize] = (! vubmixsigns[vubmixsize]) ? SCIPgetSolVal(scip, sol, vubvars[j]): (1.0 - SCIPgetSolVal(scip, sol, vubvars[j]));
560  	
561  	            /* update the maximal coefficient if needed */
562  	            if( maxabscoef < vubmixcoefs[vubmixsize] )
563  	            {
564  	               maxabscoef = vubmixcoefs[vubmixsize];
565  	               maxabsind = vubmixinds[vubmixsize];
566  	               maxabssign = vubmixsigns[vubmixsize];
567  	            }
568  	
569  	            ++vubmixsize;
570  	
571  	            /* stop if size is exceeded; possibly ignore redundant variable bounds */
572  	            if( vubmixsize >= nmaxvars )
573  	               break;
574  	         }
575  	      }
576  	      assert( vubmixsize <= nmaxvars );
577  	
578  	      /* stop if no variable upper bounds information exists */
579  	      if( vubmixsize == 0 )
580  	         goto CONFLICT;
581  	
582  	      /* stop if the current solution value of transformed continuous variable is larger than the maximal coefficient */
583  	      if( SCIPisFeasGT(scip, ub - varsolval, maxabscoef) )
584  	         goto CONFLICT;
585  	
586  	      /* sort the solution values in non-increasing order */
587  	      SCIPsortDownRealRealIntInt(vubmixsols, vubmixcoefs, vubmixinds, vubmixsigns, vubmixsize);
588  	
589  	      /* add the continuous variables */
590  	      cutnnz = 0;
591  	      cutcoefs[cutnnz] = 1;
592  	      cutinds[cutnnz] = SCIPvarGetProbindex(var);
593  	      cutrhs = ub;
594  	      cutnnz++;
595  	
596  	      activity = varsolval - ub;
597  	      lastcoef = 0.0;
598  	
599  	      for( j = 0; j < vubmixsize; j++ )
600  	      {
601  	         SCIP_Real solval;
602  	
603  	         solval = vubmixsols[j];
604  	
605  	         /* stop if we can not find a violated cut or we reached 0 solution values */
606  	         if( activity + solval * (maxabscoef - lastcoef) < 0.0 || SCIPisFeasZero(scip, solval) )
607  	            break;
608  	         else
609  	         {
610  	            /* skip if we have already added a variable with bigger coefficient */
611  	            if( SCIPisLE(scip, vubmixcoefs[j], lastcoef) )
612  	               continue;
613  	            else
614  	            {
615  	               activity += (vubmixcoefs[j] - lastcoef) * solval;
616  	               if( vubmixsigns[j] )
617  	               {
618  	                  cutcoefs[cutnnz] = lastcoef - vubmixcoefs[j];
619  	                  cutrhs -= vubmixcoefs[j] - lastcoef;
620  	               }
621  	               else
622  	                  cutcoefs[cutnnz] = vubmixcoefs[j] - lastcoef;
623  	               cutinds[cutnnz++] = vubmixinds[j];
624  	               lastcoef = vubmixcoefs[j];
625  	            }
626  	         }
627  	      }
628  	
629  	      /* add the variable with maximal coefficient if needed */
630  	      if( SCIPisGT(scip, maxabscoef, lastcoef) )
631  	      {
632  	         /* do not update activity: either the corresponding solval is 0.0 or the cut will not become efficious */
633  	         if( maxabssign )
634  	         {
635  	            cutcoefs[cutnnz] = lastcoef - maxabscoef;
636  	            cutrhs -= maxabscoef - lastcoef;
637  	         }
638  	         else
639  	            cutcoefs[cutnnz] = maxabscoef - lastcoef;
640  	         cutinds[cutnnz++] = maxabsind;
641  	      }
642  	      assert( cutnnz <= nmaxvars + 1 );
643  	
644  	      /* add the cut if the violtion is good enough and the number of nonzero coefficients is larger than 2 */
645  	      if( SCIPisEfficacious(scip, activity) && cutnnz > 2 )
646  	      {
647  	         SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, islocalub, cutoff, ncuts) );
648  	      }
649  	
650  	   CONFLICT:
651  	      /* combine the variable lower bounds information and upper bounds information together to generate cuts */
652  	      /* stop if no useful variable lower (or upper) bounds information exists */
653  	      if( vlbmixsize == 0 || vubmixsize == 0 )
654  	         continue;
655  	
656  	      assert( lb != SCIP_INVALID ); /*lint !e777*/
657  	      assert( ub != SCIP_INVALID ); /*lint !e777*/
658  	
659  	      cutislocal = islocallb || islocalub;
660  	      for( j = 0; j < vlbmixsize; j++ )
661  	      {
662  	         SCIP_Real solval;
663  	
664  	         solval = vlbmixsols[j];
665  	
666  	         /* stop if no violated cut exists */
667  	         if( ! SCIPisEfficacious(scip, solval + vubmixsols[0] - 1.0) )
668  	            break;
669  	
670  	         for( k = 0; k < vubmixsize; k++ )
671  	         {
672  	            /* only consider the inequality if its violation is good enough */
673  	            if( SCIPisEfficacious(scip, solval + vubmixsols[k] - 1.0) )
674  	            {
675  	               SCIP_Real tmp;
676  	
677  	               tmp = lb + vlbmixcoefs[j] + vubmixcoefs[k] - ub;
678  	
679  	               /* add the cut if it is valid */
680  	               if( SCIPisEfficacious(scip, tmp) )
681  	               {
682  	                  cutnnz = 2;
683  	                  cutrhs = 1.0;
684  	                  cutcoefs[0] = vlbmixsigns[j] ? -1.0 : 1.0;
685  	                  cutcoefs[1] = vubmixsigns[k] ? -1.0 : 1.0;
686  	                  cutinds[0] = vlbmixinds[j];
687  	                  cutinds[1] = vubmixinds[k];
688  	                  cutrhs = vlbmixsigns[j] ? (cutrhs - 1.0) : cutrhs;
689  	                  cutrhs = vubmixsigns[k] ? (cutrhs - 1.0) : cutrhs;
690  	                  SCIP_CALL( addCut(scip, sepa, sol, cutcoefs, cutinds, cutnnz, cutrhs, cutislocal, cutoff, ncuts) );
691  	               }
692  	            }
693  	            else
694  	               break;
695  	         }
696  	      }
697  	   }
698  	
699  	   /* free temporary memory */
700  	   SCIPfreeBufferArray(scip, &cutinds);
701  	   SCIPfreeBufferArray(scip, &cutcoefs);
702  	   SCIPfreeBufferArray(scip, &vubmixsigns);
703  	   SCIPfreeBufferArray(scip, &vubmixinds);
704  	   SCIPfreeBufferArray(scip, &vubmixsols);
705  	   SCIPfreeBufferArray(scip, &vubmixcoefs);
706  	   SCIPfreeBufferArray(scip, &vlbmixsigns);
707  	   SCIPfreeBufferArray(scip, &vlbmixinds);
708  	   SCIPfreeBufferArray(scip, &vlbmixsols);
709  	   SCIPfreeBufferArray(scip, &vlbmixcoefs);
710  	
711  	   return SCIP_OKAY;
712  	}
713  	
714  	
715  	/*
716  	 * Callback methods of separator
717  	 */
718  	
719  	/** copy method for separator plugins (called when SCIP copies plugins) */
720  	static
721  	SCIP_DECL_SEPACOPY(sepaCopyMixing)
722  	{  /*lint --e{715}*/
723  	   assert(scip != NULL);
724  	   assert(sepa != NULL);
725  	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
726  	
727  	   /* call inclusion method of separator */
728  	   SCIP_CALL( SCIPincludeSepaMixing(scip) );
729  	
730  	   return SCIP_OKAY;
731  	}
732  	
733  	/** destructor of separator to free user data (called when SCIP is exiting) */
734  	static
735  	SCIP_DECL_SEPAFREE(sepaFreeMixing)
736  	{  /*lint --e{715}*/
737  	   SCIP_SEPADATA* sepadata;
738  	
739  	   assert(scip != NULL);
740  	   assert(sepa != NULL);
741  	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
742  	
743  	   /* get separation data and free it */
744  	   sepadata = SCIPsepaGetData(sepa);
745  	   assert(sepadata != NULL);
746  	   SCIPfreeBlockMemory(scip, &sepadata);
747  	
748  	   /* reset data pointer to NULL */
749  	   SCIPsepaSetData(sepa, NULL);
750  	
751  	   return SCIP_OKAY;
752  	}
753  	
754  	
755  	/** LP solution separation method of separator */
756  	static
757  	SCIP_DECL_SEPAEXECLP(sepaExeclpMixing)
758  	{  /*lint --e{715}*/
759  	   SCIP_SEPADATA* sepadata;
760  	   SCIP_Bool cutoff;
761  	   int nbinvars;
762  	   int nvars;
763  	   int ncuts;
764  	   int ncalls;
765  	
766  	   assert(sepa != NULL);
767  	   assert(scip != NULL);
768  	   assert(result != NULL);
769  	
770  	   *result = SCIP_DIDNOTRUN;
771  	   ncalls = SCIPsepaGetNCallsAtNode(sepa);
772  	   sepadata = SCIPsepaGetData(sepa);
773  	   assert(sepadata != NULL);
774  	
775  	   /* only call the mixing cut separator a given number of times at each node */
776  	   if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
777  	      || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
778  	      return SCIP_OKAY;
779  	
780  	   /* gets numver of active problem variables and number of binary variables */
781  	   SCIP_CALL( SCIPgetVarsData(scip, NULL, &nvars, &nbinvars, NULL, NULL, NULL) );
782  	
783  	   /* if all the active problem variables are binary, stop */
784  	   if( nvars == nbinvars )
785  	      return SCIP_OKAY;
786  	
787  	   /* call the cut separation */
788  	   SCIP_CALL( separateCuts(scip, sepa, NULL, &cutoff, &ncuts) );
789  	
790  	   /* adjust result code */
791  	   if( cutoff )
792  	      *result = SCIP_CUTOFF;
793  	   else if( ncuts > 0 )
794  	   {
795  	      SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts);
796  	      *result = SCIP_SEPARATED;
797  	   }
798  	   else
799  	      *result = SCIP_DIDNOTFIND;
800  	
801  	   return SCIP_OKAY;
802  	}
803  	
804  	/** arbitrary primal solution separation method of separator */
805  	static
806  	SCIP_DECL_SEPAEXECSOL(sepaExecSolMixing)
807  	{  /*lint --e{715}*/
808  	   SCIP_SEPADATA* sepadata;
809  	   SCIP_Bool cutoff;
810  	   int nbinvars;
811  	   int nvars;
812  	   int ncuts;
813  	   int ncalls;
814  	
815  	   assert(sepa != NULL);
816  	   assert(scip != NULL);
817  	   assert(result != NULL);
818  	
819  	   *result = SCIP_DIDNOTRUN;
820  	   sepadata = SCIPsepaGetData(sepa);
821  	   assert(sepadata != NULL);
822  	
823  	   /* do not run if we have reached the maximal number of consecutive unsuccessful calls */
824  	   if( sepadata->nunsuccessful >= sepadata->maxnunsuccessful )
825  	      return SCIP_OKAY;
826  	
827  	   /* only call the mixing cut separator a given number of times at each node */
828  	   ncalls = SCIPsepaGetNCallsAtNode(sepa);
829  	   if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
830  	      || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
831  	      return SCIP_OKAY;
832  	
833  	   /* gets numver of active problem variables and number of binary variables */
834  	   nvars = SCIPgetNVars(scip);
835  	   nbinvars = SCIPgetNBinVars(scip);
836  	
837  	   /* if all the active problem variables are binary, stop */
838  	   if( nvars == nbinvars )
839  	      return SCIP_OKAY;
840  	
841  	   /* call the cut separation */
842  	   SCIP_CALL( separateCuts(scip, sepa, sol, &cutoff, &ncuts) );
843  	
844  	   /* adjust result code */
845  	   if( cutoff )
846  	   {
847  	      sepadata->nunsuccessful = 0;
848  	      *result = SCIP_CUTOFF;
849  	   }
850  	   else if( ncuts > 0 )
851  	   {
852  	      SCIPdebugMsg(scip, "mixing separator generated %d cuts.\n", ncuts);
853  	      sepadata->nunsuccessful = 0;
854  	      *result = SCIP_SEPARATED;
855  	   }
856  	   else
857  	   {
858  	      ++sepadata->nunsuccessful;
859  	      *result = SCIP_DIDNOTFIND;
860  	   }
861  	
862  	   return SCIP_OKAY;
863  	}
864  	
865  	
866  	/*
867  	 * separator specific interface methods
868  	 */
869  	
870  	/** creates the mixing separator and includes it in SCIP */
871  	SCIP_RETCODE SCIPincludeSepaMixing(
872  	   SCIP*                 scip                /**< SCIP data structure */
873  	   )
874  	{
875  	   SCIP_SEPADATA* sepadata;
876  	   SCIP_SEPA* sepa;
877  	
878  	   /* create mixing separator data */
879  	   SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
880  	   assert(sepadata != NULL);
881  	   sepadata->nunsuccessful = 0;
882  	
883  	   /* include separator */
884  	   SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
885  	         SEPA_USESSUBSCIP, SEPA_DELAY,
886  	         sepaExeclpMixing, sepaExecSolMixing,
887  	         sepadata) );
888  	   assert(sepa != NULL);
889  	
890  	   /* set non-NULL pointers to callback methods */
891  	   SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyMixing) );
892  	   SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeMixing) );
893  	
894  	   /* add separator parameters */
895  	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/mixing/uselocalbounds",
896  	         "Should local bounds be used?",
897  	         &sepadata->uselocalbounds, TRUE, DEFAULT_USELOCALBOUNDS, NULL, NULL) );
898  	
899  	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/mixing/iscutsonints",
900  	         "Should general integer variables be used to generate cuts?",
901  	         &sepadata->iscutsonints, TRUE, DEFAULT_ISCUTSONINTS, NULL, NULL) );
902  	
903  	   SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxrounds",
904  	         "maximal number of mixing separation rounds per node (-1: unlimited)",
905  	         &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
906  	
907  	   SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxroundsroot",
908  	         "maximal number of mixing separation rounds in the root node (-1: unlimited)",
909  	         &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
910  	
911  	   SCIP_CALL( SCIPaddIntParam(scip, "separating/mixing/maxnunsuccessful",
912  	         "maximal number of consecutive unsuccessful iterations",
913  	         &sepadata->maxnunsuccessful, FALSE, DEFAULT_MAXNUNSUCCESSFUL, -1, INT_MAX, NULL, NULL) );
914  	
915  	   return SCIP_OKAY;
916  	}
917