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   	/* #define SCIP_WRITEPROB */
25   	/* #define SCIP_OUTPUT */
26   	/**@file   sepa_cgmip.c
27   	 * @ingroup DEFPLUGINS_SEPA
28   	 * @brief  Chvatal-Gomory cuts computed via a sub-MIP
29   	 * @author Marc Pfetsch
30   	 *
31   	 * Separate Chvátal-Gomory cuts using a sub-MIP. The approach is based on the following papers.
32   	 *
33   	 * M. Fischetti and A. Lodi@n
34   	 * Optimizing over the first Chvátal closure,@n
35   	 * in: M. Jünger and V. Kaibel (eds.) Integer Programming and Combinatorial Optimization IPCO 2005,@n
36   	 * LNCS 3509, pp. 12-22. Springer, Berlin Heidelberg New York (2005)
37   	 *
38   	 * M. Fischetti and A. Lodi@n
39   	 * Optimizing over the first Chvátal closure,@n
40   	 * Mathematical Programming 110, 3-20 (2007)
41   	 *
42   	 * P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, and A. Lodi@n
43   	 * Projected Chvátal-Gomory cuts for mixed integer linear programs,@n
44   	 * Mathematical Programming 113, No. 2 (2008)
45   	 *
46   	 *
47   	 * There are several possibilities to generate the final cut:
48   	 *
49   	 * - The CMIR-routines of SCIP can be used (if @p usecmir is true). One can determine which bound is
50   	 *   used in the rounding operation (if @p cmirownbounds is true) or let SCIP choose the best. This
51   	 *   version is generally numerically the most stable.
52   	 * - If @p usestrongcg is true, we try to generate Strong-CG cuts (as done in sepa_strongcg.c).
53   	 * - One can directly generate the CG-cut as computed (if @p usecmir and @p usestrongcg are
54   	 *   false). The cut is not taken from the solution of the MIP, but is recomputed, and some care (but
55   	 *   not as much as in the first version) has been taken to create a valid cut.
56   	 *
57   	 * The computation time of the separation MIP is limited as follows:
58   	 * - There is a node limit (parameters @a minnodelimit and @a maxnodelimit).
59   	 * - There is a time limit (parameter @a timelimit).
60   	 * - If paramter @a earlyterm is true, the separation is run until the first cut that is violated is
61   	 *   found. (Note that these cuts are not necessarily added to the LP, because here also the norm of
62   	 *   the cuts are taken into account - which cannot easily be included into the separation subscip.)
63   	 *   Then the solution process is continued for a certain number of nodes.
64   	 *
65   	 * @todo Check whether one can weaken the conditions on the continuous variables.
66   	 * @todo Use pointers to originating separators to sort out cuts that should not be used.
67   	 *
68   	 * @warning This separator should be used carefully - it may require a long separation time.
69   	 */
70   	
71   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
72   	
73   	#include "blockmemshell/memory.h"
74   	#include "scip/cons_linear.h"
75   	#include "scip/cuts.h"
76   	#include "scip/pub_cons.h"
77   	#include "scip/pub_lp.h"
78   	#include "scip/pub_message.h"
79   	#include "scip/pub_misc.h"
80   	#include "scip/pub_sepa.h"
81   	#include "scip/pub_var.h"
82   	#include "scip/scip_branch.h"
83   	#include "scip/scip_cons.h"
84   	#include "scip/scip_copy.h"
85   	#include "scip/scip_cut.h"
86   	#include "scip/scip_general.h"
87   	#include "scip/scip_lp.h"
88   	#include "scip/scip_mem.h"
89   	#include "scip/scip_message.h"
90   	#include "scip/scip_numerics.h"
91   	#include "scip/scip_param.h"
92   	#include "scip/scip_prob.h"
93   	#include "scip/scip_randnumgen.h"
94   	#include "scip/scip_sepa.h"
95   	#include "scip/scip_sol.h"
96   	#include "scip/scip_solve.h"
97   	#include "scip/scip_solvingstats.h"
98   	#include "scip/scip_timing.h"
99   	#include "scip/scip_tree.h"
100  	#include "scip/scip_var.h"
101  	#include "scip/scipdefplugins.h"
102  	#include "scip/sepa_cgmip.h"
103  	#include <string.h>
104  	
105  	
106  	#define SEPA_NAME              "cgmip"
107  	#define SEPA_DESC              "Chvatal-Gomory cuts via MIPs separator"
108  	#define SEPA_PRIORITY             -1000
109  	#define SEPA_FREQ                    -1
110  	#define SEPA_MAXBOUNDDIST           0.0
111  	#define SEPA_USESSUBSCIP           TRUE /**< does the separator use a secondary SCIP instance? */
112  	#define SEPA_DELAY                FALSE /**< should separation method be delayed, if other separators found cuts? */
113  	
114  	#define DEFAULT_MAXROUNDS             5 /**< maximal number of separation rounds per node (-1: unlimited) */
115  	#define DEFAULT_MAXROUNDSROOT        50 /**< maximal number of separation rounds in the root node (-1: unlimited) */
116  	#define DEFAULT_MAXDEPTH             -1 /**< maximal depth at which the separator is applied */
117  	#define DEFAULT_DECISIONTREE      FALSE /**< Use decision tree to turn separation on/off? */
118  	#define DEFAULT_TIMELIMIT          1e20 /**< time limit for sub-MIP (set to infinity in order to be deterministic) */
119  	#define DEFAULT_MEMORYLIMIT        1e20 /**< memory limit for sub-MIP */
120  	#define DEFAULT_CUTCOEFBND       1000.0 /**< bounds on the values of the coefficients in the CG-cut */
121  	#define DEFAULT_MINNODELIMIT      500LL /**< minimum number of nodes considered for sub-MIP (-1: unlimited) */
122  	#define DEFAULT_MAXNODELIMIT     5000LL /**< maximum number of nodes considered for sub-MIP (-1: unlimited) */
123  	#define DEFAULT_ONLYACTIVEROWS    FALSE /**< Use only active rows to generate cuts? */
124  	#define DEFAULT_MAXROWAGE            -1 /**< maximal age of rows to consider if onlyactiverows is false */
125  	#define DEFAULT_ONLYRANKONE       FALSE /**< Separate rank 1 inequalities w.r.t. CG-MIP separator? */
126  	#define DEFAULT_ONLYINTVARS       FALSE /**< Generate cuts for problems with only integer variables? */
127  	#define DEFAULT_CONTCONVERT       FALSE /**< Convert some integral variables to be continuous to reduce the size of the sub-MIP? */
128  	#define DEFAULT_CONTCONVFRAC        0.1 /**< fraction of integral variables converted to be continuous (if contconvert) */
129  	#define DEFAULT_CONTCONVMIN         100 /**< minimum number of integral variables before some are converted to be continuous */
130  	#define DEFAULT_INTCONVERT        FALSE /**< Convert some integral variables attaining fractional values to have integral value? */
131  	#define DEFAULT_INTCONVFRAC         0.1 /**< fraction of fractional integral variables converted to have integral value (if intconvert) */
132  	#define DEFAULT_INTCONVMIN          100 /**< minimum number of integral variables before some are converted to have integral value */
133  	#define DEFAULT_SKIPMULTBOUNDS     TRUE /**< Skip the upper bounds on the multipliers in the sub-MIP? */
134  	#define DEFAULT_OBJLONE           FALSE /**< Should the objective of the sub-MIP only minimize the l1-norm of the multipliers? */
135  	#define DEFAULT_OBJWEIGHT         1e-03 /**< objective weight for artificial variables */
136  	#define DEFAULT_OBJWEIGHTSIZE      TRUE /**< Weight each row by its size? */
137  	#define DEFAULT_DYNAMICCUTS        TRUE /**< Should generated cuts be removed from the LP if they are no longer tight? */
138  	#define DEFAULT_USECMIR            TRUE /**< Use CMIR-generator (otherwise add cut directly)? */
139  	#define DEFAULT_USESTRONGCG       FALSE /**< Use strong CG-function to strengthen cut? */
140  	#define DEFAULT_CMIROWNBOUNDS     FALSE /**< Tell CMIR-generator which bounds to used in rounding? */
141  	#define DEFAULT_USECUTPOOL         TRUE /**< Use cutpool to store CG-cuts even if the are not efficient? */
142  	#define DEFAULT_PRIMALSEPARATION   TRUE /**< Only separate cuts that are tight for the best feasible solution? */
143  	#define DEFAULT_EARLYTERM          TRUE /**< Terminate separation if a violated (but possibly sub-optimal) cut has been found? */
144  	#define DEFAULT_ADDVIOLATIONCONS  FALSE /**< Add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?*/
145  	#define DEFAULT_ADDVIOLCONSHDLR   FALSE /**< Add constraint handler to filter out violated cuts? */
146  	#define DEFAULT_CONSHDLRUSENORM    TRUE /**< Should the violation constraint handler use the norm of a cut to check for feasibility? */
147  	#define DEFAULT_USEOBJUB          FALSE /**< Use upper bound on objective function (via primal solution)? */
148  	#define DEFAULT_USEOBJLB          FALSE /**< Use lower bound on objective function (via lower bound)? */
149  	#define DEFAULT_SUBSCIPFAST        TRUE /**< Should the settings for the sub-MIP be optimized for speed? */
150  	#define DEFAULT_OUTPUT            FALSE /**< Should information about the sub-MIP and cuts be displayed? */
151  	#define DEFAULT_RANDSEED            101 /**< start random seed for random number generation */
152  	#define DEFAULT_GENPRIMALSOLS     FALSE /**< Try to generate primal solutions from Gomory cuts? */
153  	
154  	
155  	#define NROWSTOOSMALL                 5 /**< only separate if the number of rows is larger than this number */
156  	#define NCOLSTOOSMALL                 5 /**< only separate if the number of columns is larger than this number */
157  	
158  	#define EPSILONVALUE              1e-03 /**< epsilon value needed to model strict-inequalities */
159  	#define BETAEPSILONVALUE          1e-02 /**< epsilon value for fracbeta - is larger than EPSILONVALUE for numerical stability */
160  	#define STALLNODELIMIT           1000LL /**< number of stalling nodes if earlyterm is true */
161  	#define CONSHDLRFULLNORM          FALSE /**< compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true) */
162  	#define MINEFFICACY                0.05 /**< minimum efficacy of a cut - compare set.c */
163  	#define MAXNSOLS                   1000 /**< maximal number of solutions stored in sub-SCIP */
164  	#define OBJWEIGHTRANGE             0.01 /**< maximal range of scaling of objective w.r.t. size of rows */
165  	
166  	/* parameters used for CMIR-generation (taken from sepa_gomory) */
167  	#define BOUNDSWITCH              0.9999
168  	#define USEVBDS                    TRUE
169  	#define POSTPROCESS                TRUE
170  	#define MINFRAC                  0.0009 /**< to allow a deviation of the same size as EPSILONVALUE */
171  	#define MAXFRAC                  0.9991 /**< to allow a deviation of the same size as EPSILONVALUE */
172  	#define FIXINTEGRALRHS            FALSE
173  	#define MAKECONTINTEGRAL          FALSE
174  	#define MAXWEIGHTRANGE            1e+05 /**< maximal valid range max(|weights|)/min(|weights|) of row weights */
175  	#define AWAY                      0.005 /**< minimal fractionality of a basic variable in order to try GMI cut */
176  	#define SEPARATEROWS               TRUE /**< Separate rows with integral slack? */
177  	
178  	#define MAXAGGRLEN(nvars)         nvars /**< currently very large to allow any generation; an alternative would be (0.1*(nvars)+1000) */
179  	
180  	/** separator data */
181  	struct SCIP_SepaData
182  	{
183  	   SCIP_RANDNUMGEN*      randnumgen;         /**< random number generator */
184  	   int                   maxrounds;          /**< maximal number of separation rounds per node (-1: unlimited) */
185  	   int                   maxroundsroot;      /**< maximal number of separation rounds in the root node (-1: unlimited) */
186  	   int                   maxdepth;           /**< maximal depth at which the separator is applied */
187  	   SCIP_Bool             decisiontree;       /**< Use decision tree to turn separation on/off? */
188  	   SCIP_Real             timelimit;          /**< time limit for subscip */
189  	   SCIP_Real             memorylimit;        /**< memory limit for subscip */
190  	   SCIP_Longint          minnodelimit;       /**< minimum number of nodes considered for sub-MIP (-1: unlimited) */
191  	   SCIP_Longint          maxnodelimit;       /**< maximum number of nodes considered for sub-MIP (-1: unlimited) */
192  	   SCIP_Real             cutcoefbnd;         /**< bounds on the values of the coefficients in the CG-cut */
193  	   SCIP_Bool             onlyactiverows;     /**< Use only active rows to generate cuts? */
194  	   int                   maxrowage;          /**< maximal age of rows to consider if onlyactiverows is false */
195  	   SCIP_Bool             onlyrankone;        /**< Separate only rank 1 inequalities w.r.t. CG-MIP separator? */
196  	   SCIP_Bool             onlyintvars;        /**< Generate cuts for problems with only integer variables? */
197  	   SCIP_Bool             allowlocal;         /**< Allow local cuts? */
198  	   SCIP_Bool             contconvert;        /**< Convert some integral variables to be continuous to reduce the size of the sub-MIP? */
199  	   SCIP_Real             contconvfrac;       /**< fraction of integral variables converted to be continuous (if contconvert) */
200  	   int                   contconvmin;        /**< minimum number of integral variables before some are converted to be continuous */
201  	   SCIP_Bool             intconvert;         /**< Convert some integral variables attaining fractional values to have integral value? */
202  	   SCIP_Real             intconvfrac;        /**< fraction of frac. integral variables converted to have integral value (if intconvert) */
203  	   int                   intconvmin;         /**< minimum number of integral variables before some are converted to have integral value */
204  	   SCIP_Bool             skipmultbounds;     /**< Skip the upper bounds on the multipliers in the sub-MIP? */
205  	   SCIP_Bool             objlone;            /**< Should the objective of the sub-MIP only minimize the l1-norm of the multipliers? */
206  	   SCIP_Real             objweight;          /**< objective weight for artificial variables */
207  	   SCIP_Bool             objweightsize;      /**< Weight each row by its size? */
208  	   SCIP_Bool             dynamiccuts;        /**< Should generated cuts be removed from the LP if they are no longer tight? */
209  	   SCIP_Bool             usecmir;            /**< Use CMIR-generator (otherwise add cut directly)? */
210  	   SCIP_Bool             usestrongcg;        /**< Use strong CG-function to strengthen cut? */
211  	   SCIP_Bool             cmirownbounds;      /**< Tell CMIR-generator which bounds to used in rounding? */
212  	   SCIP_Bool             usecutpool;         /**< Use cutpool to store CG-cuts even if the are not efficient? */
213  	   SCIP_Bool             primalseparation;   /**< Only separate cuts that are tight for the best feasible solution? */
214  	   SCIP_Bool             earlyterm;          /**< Terminate separation if a violated (but possibly sub-optimal) cut has been found? */
215  	   SCIP_Bool             addviolationcons;   /**< Add constraint to subscip that only allows violated cuts? */
216  	   SCIP_Bool             addviolconshdlr;    /**< Add constraint handler to filter out violated cuts? */
217  	   SCIP_Bool             conshdlrusenorm;    /**< Should the violation constraint handler use the cut-norm to check for feasibility? */
218  	   SCIP_Bool             useobjub;           /**< Use upper bound on objective function (via primal solution)? */
219  	   SCIP_Bool             useobjlb;           /**< Use lower bound on objective function (via lower bound)? */
220  	   SCIP_Bool             subscipfast;        /**< Should the settings for the sub-MIP be optimized for speed? */
221  	   SCIP_Bool             output;             /**< Should information about the sub-MIP and cuts be displayed? */
222  	   SCIP_Bool             genprimalsols;      /**< Try to generate primal solutions from Gomory cuts? */
223  	};
224  	
225  	
226  	/** what happens for columns in the LP */
227  	enum CGMIP_ColType
228  	{
229  	   colPresent    = 0,    /**< column is present in the separating MIP */
230  	   colContinuous = 1,    /**< column corresponds to a continuous variable */
231  	   colConverted  = 2,    /**< column is converted to be continuous */
232  	   colAtUb       = 3,    /**< variable corresponding to column was at it's upper bound and was complemented */
233  	   colAtLb       = 4     /**< variable corresponding to column was at it's lower bound (possibly complemented) */
234  	};
235  	typedef enum CGMIP_ColType CGMIP_COLTYPE;
236  	
237  	
238  	/** data for the sub-MIP */
239  	struct CGMIP_MIPData
240  	{
241  	   SCIP*                 subscip;            /**< pointer to (sub)SCIP data structure containing the auxiliary IP */
242  	   unsigned int          m;                  /**< number of constraints of subscip */
243  	   unsigned int          n;                  /**< number of variables of subscip */
244  	   unsigned int          nrows;              /**< number of rows of original LP */
245  	   unsigned int          ncols;              /**< number of columns of original LP */
246  	   unsigned int          ntotalrows;         /**< number of total rows used (possibly including objective rows) */
247  	
248  	   SCIP_VAR**            alpha;              /**< cut coefficient variable (NULL if not in separating MIP) */
249  	   SCIP_VAR*             beta;               /**< rhs of cut */
250  	   SCIP_VAR**            fracalpha;          /**< fractional part of lhs of cut (NULL if not present) */
251  	   SCIP_VAR*             fracbeta;           /**< fractional part of rhs of cut */
252  	   CGMIP_COLTYPE*        coltype;            /**< type for the columns */
253  	   SCIP_Bool*            iscomplemented;     /**< whether the variable was complemented */
254  	   SCIP_Bool*            isshifted;          /**< whether the variable was shifted to have 0 lower bound */
255  	
256  	   SCIP_VAR**            ylhs;               /**< auxiliary row variables for lhs (NULL if not present) */
257  	   SCIP_VAR**            yrhs;               /**< auxiliary row variables for rhs (NULL if not present) */
258  	
259  	   SCIP_VAR**            z;                  /**< auxiliary variables for upper bounds (NULL if not present) */
260  	
261  	   SCIP_Real*            lhs;                /**< transformed left hand sides */
262  	   SCIP_Real*            rhs;                /**< transformed left hand sides */
263  	
264  	   char                  normtype;           /**< type of norm to use for efficacy norm calculation */
265  	
266  	   /* additional redundant data */
267  	   SCIP_Bool             conshdlrusenorm;    /**< copy from sepadata */
268  	   SCIP_Bool             conshdlrfullnorm;   /**< compute real cut and compute norm for this (if addviolconshdlr and conshdlrusenorm are true) */
269  	   SCIP*                 scip;               /**< original SCIP */
270  	   SCIP_SEPA*            sepa;               /**< CG-cut separator */
271  	   SCIP_SEPADATA*        sepadata;           /**< CG-cut separator data */
272  	};
273  	typedef struct CGMIP_MIPData CGMIP_MIPDATA;
274  	
275  	
276  	/*
277  	 * constraint handler to filter out violated cuts
278  	 */
279  	
280  	/* constraint handler properties */
281  	#define CONSHDLR_NAME          "violatedCuts"
282  	#define CONSHDLR_DESC          "only allow solutions corresponding to violated cuts"
283  	
284  	/** constraint handler data */
285  	struct SCIP_ConshdlrData
286  	{
287  	   CGMIP_MIPDATA*        mipdata;            /**< data of separating sub-MIP */
288  	};
289  	
290  	/* temporary forward declaration */
291  	static
292  	SCIP_RETCODE computeCut(
293  	   SCIP*                 scip,               /**< original scip */
294  	   SCIP_SEPA*            sepa,               /**< separator */
295  	   CGMIP_MIPDATA*        mipdata,            /**< data for sub-MIP */
296  	   SCIP_SEPADATA*        sepadata,           /**< separator data */
297  	   SCIP_SOL*             sol,                /**< current solution for sub-MIP */
298  	   SCIP_Bool             usefrac,            /**< use fractional value of multipliers */
299  	   SCIP_Real*            cutcoefs,           /**< coefficients of the cut */
300  	   SCIP_Real*            cutrhs,             /**< rhs of the cut */
301  	   SCIP_Bool*            localrowsused,      /**< pointer to store whether local rows were used in summation */
302  	   SCIP_Bool*            localboundsused,    /**< pointer to store whether local bounds were used in summation */
303  	   int *                 cutrank,            /**< pointer to store the cut rank */
304  	   SCIP_Bool*            success             /**< whether we produced a valid cut */
305  	   );
306  	
307  	/** check whether cut corresponding to solution is violated */
308  	static
309  	SCIP_RETCODE solCutIsViolated(
310  	   SCIP*                 scip,               /**< SCIP data structure */
311  	   CGMIP_MIPDATA*        mipdata,            /**< data of separating sub-MIP */
312  	   SCIP_SOL*             sol,                /**< solution to be checked */
313  	   SCIP_Bool*            violated            /**< pointer to store if the cut is violated */
314  	   )
315  	{
316  	   SCIP_Real cutsqrnorm = 0.0;
317  	   SCIP* subscip;
318  	   SCIP_Real act;
319  	   SCIP_Real norm;
320  	   SCIP_Real val;
321  	   SCIP_VAR* var;
322  	   SCIP_Real rhs;
323  	   unsigned int j;
324  	   int len = 0;
325  	
326  	   assert( mipdata != NULL );
327  	   subscip = mipdata->subscip;
328  	   assert( subscip != NULL );
329  	   assert( violated != NULL );
330  	
331  	   /* initialize activity and norm */
332  	   act = 0.0;
333  	   norm = 1.0;
334  	   *violated = FALSE;
335  	
336  	   /* compute activity and norm  */
337  	   if ( mipdata->conshdlrusenorm )
338  	   {
339  	      /* check whether we should compute the full cut and then compute the norm */
340  	      if ( mipdata->conshdlrfullnorm )
341  	      {
342  	         SCIP_Real* cutcoefs;
343  	         SCIP_Bool localrowsused;
344  	         SCIP_Bool localboundsused;
345  	         SCIP_Bool success;
346  	         SCIP_VAR** vars;
347  	         int cutrank = 0;
348  	         int nvars;
349  	
350  	         /* get data */
351  	         SCIP_CALL( SCIPgetVarsData(mipdata->scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
352  	         assert(nvars >= 0);
353  	         SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
354  	
355  	         /* compute coefficients */
356  	         SCIP_CALL( computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, TRUE, cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) );
357  	
358  	         /* try again if cut was not valid */
359  	         if ( ! success )
360  	         {
361  	            SCIP_CALL( computeCut(mipdata->scip, mipdata->sepa, mipdata, mipdata->sepadata, sol, FALSE,
362  	                  cutcoefs, &rhs, &localrowsused, &localboundsused, &cutrank, &success) );
363  	
364  	            if ( ! success )
365  	               return SCIP_OKAY;
366  	         }
367  	
368  	#ifdef SCIP_MORE_DEBUG
369  	         for (j = 0; j < (unsigned int) nvars; ++j)
370  	         {
371  	            if ( ! SCIPisZero(scip, cutcoefs[j]) )
372  	               SCIPinfoMessage(scip, NULL, "+ %f x%d", cutcoefs[j], j);
373  	         }
374  	         SCIPinfoMessage(scip, NULL, "\n");
375  	#endif
376  	
377  	         /* compute activity and Euclidean norm (todo: use arbitrary norm) */
378  	         cutsqrnorm = 0.0;
379  	         for (j = 0; j < (unsigned int) nvars; ++j)
380  	         {
381  	            if ( ! SCIPisZero(scip, cutcoefs[j]) )
382  	            {
383  	               act += cutcoefs[j] * SCIPvarGetLPSol(vars[j]);
384  	               cutsqrnorm += SQR(cutcoefs[j]);
385  	            }
386  	         }
387  	         norm = SQRT(cutsqrnorm);
388  	
389  	         SCIPfreeBufferArray(scip, &cutcoefs);
390  	      }  /*lint !e438*/
391  	      else
392  	      {
393  	         switch ( mipdata->normtype )
394  	         {
395  	         case 'e':
396  	            cutsqrnorm = 0.0;
397  	            for (j = 0; j < mipdata->ncols; ++j)
398  	            {
399  	               var = mipdata->alpha[j];
400  	               if ( var == NULL )
401  	                  continue;
402  	
403  	               val = SCIPgetSolVal(subscip, sol, var);
404  	               if ( !SCIPisZero(scip, val) )
405  	               {
406  	                  act += val * SCIPvarGetObj(var);
407  	                  cutsqrnorm += SQR(val);
408  	               }
409  	            }
410  	            norm = SQRT(cutsqrnorm);
411  	            break;
412  	         case 'm':
413  	            for (j = 0; j < mipdata->ncols; ++j)
414  	            {
415  	               var = mipdata->alpha[j];
416  	               if ( var == NULL )
417  	                  continue;
418  	
419  	               val = SCIPgetSolVal(subscip, sol, var);
420  	               if ( !SCIPisZero(scip, val) )
421  	               {
422  	                  act += val * SCIPvarGetObj(var);
423  	                  if ( REALABS(val) > norm )
424  	                     norm = REALABS(val);
425  	               }
426  	            }
427  	            break;
428  	         case 's':
429  	            for (j = 0; j < mipdata->ncols; ++j)
430  	            {
431  	               var = mipdata->alpha[j];
432  	               if ( var == NULL )
433  	                  continue;
434  	
435  	               val = SCIPgetSolVal(subscip, sol, var);
436  	               if ( !SCIPisZero(scip, val) )
437  	               {
438  	                  act += val * SCIPvarGetObj(var);
439  	                  norm += REALABS(val);
440  	               }
441  	            }
442  	            break;
443  	         case 'd':
444  	            for (j = 0; j < mipdata->ncols; ++j)
445  	            {
446  	               var = mipdata->alpha[j];
447  	               if ( var == NULL )
448  	                  continue;
449  	
450  	               val = SCIPgetSolVal(subscip, sol, var);
451  	               if ( !SCIPisZero(scip, val) )
452  	               {
453  	                  act += val * SCIPvarGetObj(var);
454  	                  ++len;
455  	               }
456  	            }
457  	            if ( len > 0 )
458  	               norm = 1.0;
459  	            break;
460  	         default:
461  	            SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", mipdata->normtype);
462  	            return SCIP_INVALIDDATA;
463  	         }
464  	         /* get rhs */
465  	         rhs = SCIPgetSolVal(subscip, sol, mipdata->beta);
466  	      }
467  	
468  	      /* if norm is 0, the cut is trivial */
469  	      if ( SCIPisZero(subscip, norm) )
470  	         return SCIP_OKAY;
471  	   }
472  	   else
473  	   {
474  	      for (j = 0; j < mipdata->ncols; ++j)
475  	      {
476  	         var = mipdata->alpha[j];
477  	         if ( var == NULL )
478  	            continue;
479  	
480  	         val = SCIPgetSolVal(subscip, sol, var);
481  	         if ( !SCIPisZero(subscip, val) )
482  	            act += SCIPvarGetObj(var) * val;
483  	      }
484  	
485  	      /* get rhs */
486  	      rhs = SCIPgetSolVal(subscip, sol, mipdata->beta);
487  	   }
488  	
489  	#ifdef SCIP_DEBUG
490  	   if ( SCIPisEfficacious(subscip, (act - rhs)/norm) )
491  	   {
492  	      SCIPdebugMsg(scip, "Violated cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm);
493  	   }
494  	   else
495  	   {
496  	      SCIPdebugMsg(scip, "Rejected cut from solution - act: %f, rhs: %f, norm: %f, eff.: %f\n", act, rhs, norm, (act-rhs)/norm);
497  	   }
498  	#endif
499  	
500  	   *violated = SCIPisEfficacious(subscip, (act - rhs)/norm);
501  	
502  	   return SCIP_OKAY;
503  	}
504  	
505  	
506  	/** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
507  	static
508  	SCIP_DECL_CONSFREE(consFreeViolatedCuts)
509  	{  /*lint --e{715}*/
510  	   SCIP_CONSHDLRDATA* conshdlrdata;
511  	
512  	   assert( scip != NULL );
513  	   assert( conshdlr != NULL );
514  	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
515  	   assert( conshdlrdata != NULL );
516  	
517  	   SCIPfreeBlockMemory(scip, &conshdlrdata);
518  	
519  	   return SCIP_OKAY;
520  	}
521  	
522  	
523  	/** constraint enforcing method of constraint handler for LP solutions */
524  	static
525  	SCIP_DECL_CONSENFOLP(consEnfolpViolatedCuts)
526  	{  /*lint --e{715}*/
527  	   SCIP_CONSHDLRDATA* conshdlrdata;
528  	   SCIP_Bool violated;
529  	
530  	   assert( scip != NULL );
531  	   assert( conshdlr != NULL );
532  	   assert( result != NULL );
533  	
534  	   assert( SCIPgetNLPBranchCands(scip) == 0 );
535  	
536  	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
537  	   assert( conshdlrdata != NULL );
538  	
539  	   SCIP_CALL( solCutIsViolated(scip, conshdlrdata->mipdata, NULL, &violated) );
540  	
541  	   if ( violated )
542  	      *result = SCIP_FEASIBLE;
543  	   else
544  	      *result = SCIP_CUTOFF;  /* cutoff, since all integer variables are integer, but the solution is not feasible */
545  	
546  	   return SCIP_OKAY;
547  	}
548  	
549  	
550  	/** constraint enforcing method of constraint handler for pseudo solutions */
551  	static
552  	SCIP_DECL_CONSENFOPS(consEnfopsViolatedCuts)
553  	{  /*lint --e{715}*/
554  	   assert( result != NULL );
555  	
556  	   /* this function should better not be called, since we need an LP solution for the sub-MIP to
557  	    * make sense, because of the multiplier variables. We therefore return SCIP_FEASIBLE. */
558  	   *result = SCIP_FEASIBLE;
559  	
560  	   return SCIP_OKAY;
561  	}
562  	
563  	
564  	/** feasibility check method of constraint handler for integral solutions */
565  	static
566  	SCIP_DECL_CONSCHECK(consCheckViolatedCuts)
567  	{  /*lint --e{715}*/
568  	   SCIP_CONSHDLRDATA* conshdlrdata;
569  	   SCIP_Bool violated;
570  	
571  	   assert( scip != NULL );
572  	   assert( conshdlr != NULL );
573  	   assert( sol != NULL );
574  	   assert( result != NULL );
575  	
576  	   conshdlrdata = SCIPconshdlrGetData(conshdlr);
577  	   assert( conshdlrdata != NULL );
578  	
579  	   SCIP_CALL( solCutIsViolated(scip, conshdlrdata->mipdata, sol, &violated) );
580  	
581  	   if ( violated )
582  	      *result = SCIP_FEASIBLE;
583  	   else
584  	      *result = SCIP_INFEASIBLE;
585  	
586  	   return SCIP_OKAY;
587  	}
588  	
589  	
590  	/** variable rounding lock method of constraint handler */
591  	static
592  	SCIP_DECL_CONSLOCK(consLockViolatedCuts)
593  	{  /*lint --e{715}*/
594  	   /* do not lock variables */
595  	   return SCIP_OKAY;
596  	}
597  	
598  	
599  	/** creates the violated CG-cut constraint handler and includes it in SCIP */
600  	static
601  	SCIP_RETCODE SCIPincludeConshdlrViolatedCut(
602  	   SCIP*                 scip,               /**< SCIP data structure */
603  	   CGMIP_MIPDATA*        mipdata             /**< data of separating sub-MIP */
604  	   )
605  	{
606  	   SCIP_CONSHDLRDATA* conshdlrdata;
607  	   SCIP_CONSHDLR* conshdlr;
608  	
609  	   SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
610  	   conshdlrdata->mipdata = mipdata;
611  	
612  	   /* include constraint handler */
613  	   SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
614  	         -1000000, -1000000, 100, FALSE,
615  	         consEnfolpViolatedCuts, consEnfopsViolatedCuts, consCheckViolatedCuts, consLockViolatedCuts,
616  	         conshdlrdata) );
617  	
618  	   assert(conshdlr != NULL);
619  	
620  	   /* set non-fundamental callbacks via specific setter functions */
621  	   SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeViolatedCuts) );
622  	
623  	   return SCIP_OKAY;
624  	}
625  	
626  	
627  	/*
628  	 * local methods
629  	 */
630  	
631  	
632  	/** stores nonzero elements of dense coefficient vector as sparse vector and calculates activity and norm
633  	 *
634  	 *  copied from sepa_gomory.c
635  	 */
636  	static
637  	SCIP_RETCODE storeCutInArrays(
638  	   SCIP*                 scip,               /**< SCIP data structure */
639  	   int                   nvars,              /**< number of problem variables */
640  	   SCIP_Real*            cutcoefs,           /**< dense coefficient vector */
641  	   SCIP_Real*            varsolvals,         /**< dense variable LP solution vector */
642  	   char                  normtype,           /**< type of norm to use for efficacy norm calculation */
643  	   int*                  cutinds,            /**< array to store variables of sparse cut vector */
644  	   SCIP_Real*            cutvals,            /**< array to store coefficients of sparse cut vector */
645  	   int*                  cutlen,             /**< pointer to store number of nonzero entries in cut */
646  	   SCIP_Real*            cutact,             /**< pointer to store activity of cut */
647  	   SCIP_Real*            cutnorm             /**< pointer to store norm of cut vector */
648  	   )
649  	{
650  	   SCIP_Real val;
651  	   SCIP_Real cutsqrnorm;
652  	   SCIP_Real act;
653  	   SCIP_Real norm;
654  	   int len;
655  	   int v;
656  	
657  	   assert( nvars == 0 || cutcoefs != NULL );
658  	   assert( nvars == 0 || varsolvals != NULL );
659  	   assert( cutinds != NULL );
660  	   assert( cutvals != NULL );
661  	   assert( cutlen != NULL );
662  	   assert( cutact != NULL );
663  	   assert( cutnorm != NULL );
664  	
665  	   len = 0;
666  	   act = 0.0;
667  	   norm = 0.0;
668  	   switch ( normtype )
669  	   {
670  	   case 'e':
671  	      cutsqrnorm = 0.0;
672  	      for (v = 0; v < nvars; ++v)
673  	      {
674  	         val = cutcoefs[v];
675  	         if ( !SCIPisZero(scip, val) )
676  	         {
677  	            act += val * varsolvals[v];
678  	            cutsqrnorm += SQR(val);
679  	            cutinds[len] = v;
680  	            cutvals[len++] = val;
681  	         }
682  	      }
683  	      norm = SQRT(cutsqrnorm);
684  	      break;
685  	   case 'm':
686  	      for (v = 0; v < nvars; ++v)
687  	      {
688  	         val = cutcoefs[v];
689  	         if ( !SCIPisZero(scip, val) )
690  	         {
691  	            act += val * varsolvals[v];
692  	            if ( REALABS(val) > norm )
693  	               norm = REALABS(val);
694  	            cutinds[len] = v;
695  	            cutvals[len++] = val;
696  	         }
697  	      }
698  	      break;
699  	   case 's':
700  	      for (v = 0; v < nvars; ++v)
701  	      {
702  	         val = cutcoefs[v];
703  	         if ( !SCIPisZero(scip, val) )
704  	         {
705  	            act += val * varsolvals[v];
706  	            norm += REALABS(val);
707  	            cutinds[len] = v;
708  	            cutvals[len++] = val;
709  	         }
710  	      }
711  	      break;
712  	   case 'd':
713  	      for (v = 0; v < nvars; ++v)
714  	      {
715  	         val = cutcoefs[v];
716  	         if ( !SCIPisZero(scip, val) )
717  	         {
718  	            act += val * varsolvals[v];
719  	            cutinds[len] = v;
720  	            cutvals[len++] = val;
721  	         }
722  	      }
723  	      if ( len > 0 )
724  	         norm = 1.0;
725  	      break;
726  	   default:
727  	      SCIPerrorMessage("invalid efficacy norm parameter '%c'\n", normtype);
728  	      return SCIP_INVALIDDATA;
729  	   }
730  	
731  	   *cutlen = len;
732  	   *cutact = act;
733  	   *cutnorm = norm;
734  	
735  	   return SCIP_OKAY;
736  	}
737  	
738  	
739  	/** Compute lhs/rhs for transformed column
740  	 *
741  	 *  Consider a variable \f$x_j\f$ and some row of the original system:
742  	 *  \f[
743  	 *       \gamma \leq a^T x \leq \delta, \quad \ell_j \leq x_j \leq u_j.
744  	 *  \f]
745  	 *  We perform the transformation
746  	 *  \f[
747  	 *       x_i' = \left\{
748  	 *       \begin{array}{ll}
749  	 *         s + \frac{1}{\sigma}\, x_j & \mbox{if }i = j\\
750  	 *         x_i              & \mbox{otherwise},
751  	 *       \end{array}
752  	 *       \right.
753  	 *  \f]
754  	 *  where \f$s\f$ is the offset value and \f$\sigma\f$ is a scaling factor. The new system is
755  	 *  \f[
756  	 *     \gamma + \sigma\, a_j\,s \leq \sum_{i \neq j} a_i\, x_i' + \sigma a_j\, x_j' \leq \delta + \sigma\, a_j\, s
757  	 *  \f]
758  	 *  with bounds
759  	 *  \f[
760  	 *     \frac{1}{\sigma} \ell_j + s \leq x_j' \leq \frac{1}{\sigma} u_j + s, \qquad \mbox{ if }\sigma > 0
761  	 *  \f]
762  	 *  and
763  	 *  \f[
764  	 *     \frac{1}{\sigma} u_j + s \leq x_j' \leq \frac{1}{\sigma} \ell_j + s, \qquad \mbox{ if }\sigma < 0.
765  	 *  \f]
766  	 *
767  	 *  This can be used as follows:
768  	 *
769  	 *  - If \f$x_j \geq \ell_j\f$ has a (nonzero) lower bound, one can use \f$s = -\ell_j\f$, \f$\sigma = 1\f$,
770  	 *    and obtain \f$\gamma - a_j\,\ell_j \leq a^T x' \leq \delta - a_j\,\ell_j\f$, \f$0 \leq x_j' \leq u_j - \ell_j\f$.
771  	 *
772  	 *  - If \f$x_j \leq u_j\f$ has a (nonzero) upper bound, one can use \f$s = u_j\f$, \f$\sigma = -1\f$,
773  	 *    and obtain \f$\gamma - a_j\,u_j \leq \sum_{i \neq j} a_i\, x_i' - a_j\, x_j' \leq \delta - a_j\, u_j\f$,
774  	 *    \f$0 \leq x_j' \leq u_j - \ell_j\f$.
775  	 */
776  	static
777  	SCIP_RETCODE transformColumn(
778  	   SCIP*                 scip,               /**< SCIP data structure */
779  	   SCIP_SEPADATA*        sepadata,           /**< separator data */
780  	   CGMIP_MIPDATA*        mipdata,            /**< data for sub-MIP */
781  	   SCIP_COL*             col,                /**< column that should be complemented */
782  	   SCIP_Real             offset,             /**< offset by which column should be shifted */
783  	   SCIP_Real             sigma,              /**< scaling factor */
784  	   SCIP_Real*            lhs,                /**< array of lhs of rows */
785  	   SCIP_Real*            rhs,                /**< array rhs of rows */
786  	   SCIP_Real*            lb,                 /**< pointer to lb of column */
787  	   SCIP_Real*            ub,                 /**< pointer to ub of column */
788  	   SCIP_Real*            primsol             /**< pointer to solution value */
789  	   )
790  	{
791  	   SCIP_ROW** colrows;
792  	   SCIP_Real* colvals;
793  	   int pos, i;
794  	
795  	   assert( scip != NULL );
796  	   assert( lhs != NULL );
797  	   assert( rhs != NULL );
798  	   assert( col != NULL );
799  	
800  	   colrows = SCIPcolGetRows(col);
801  	   colvals = SCIPcolGetVals(col);
802  	   assert( SCIPcolGetNLPNonz(col) == 0 || colrows != NULL );
803  	   assert( SCIPcolGetNLPNonz(col) == 0 || colvals != NULL );
804  	   assert( ! SCIPisZero(scip, sigma) );
805  	
806  	   /* loop through rows that contain column */
807  	   for (i = 0; i < SCIPcolGetNLPNonz(col); ++i)
808  	   {
809  	      SCIP_ROW* row;
810  	
811  	      row = colrows[i];
812  	      assert( row != NULL );
813  	
814  	      /* skip modifiable rows and local rows, unless allowed */
815  	      if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
816  	         continue;
817  	
818  	      pos = SCIProwGetLPPos(row);
819  	      assert( 0 <= pos && pos < (int) mipdata->nrows );
820  	
821  	      assert( ! SCIPisInfinity(scip, lhs[pos]) );
822  	      if ( ! SCIPisInfinity(scip, -lhs[pos]) )
823  	         lhs[pos] += sigma * colvals[i] * offset;
824  	
825  	      assert( ! SCIPisInfinity(scip, -rhs[pos]) );
826  	      if ( ! SCIPisInfinity(scip, rhs[pos]) )
827  	         rhs[pos] += sigma * colvals[i] * offset;
828  	   }
829  	
830  	   /* check objective function */
831  	   if ( sepadata->useobjub || sepadata->useobjlb )
832  	   {
833  	      assert( SCIPisEQ(scip, SCIPcolGetObj(col), SCIPvarGetObj(SCIPcolGetVar(col))) );
834  	      assert( mipdata->ntotalrows == mipdata->nrows + 1 );
835  	
836  	      if ( ! SCIPisInfinity(scip, -lhs[mipdata->nrows]) )
837  	         lhs[mipdata->nrows] += sigma * SCIPcolGetObj(col) * offset;
838  	
839  	      if ( ! SCIPisInfinity(scip, rhs[mipdata->nrows]) )
840  	         rhs[mipdata->nrows] += sigma * SCIPcolGetObj(col) * offset;
841  	   }
842  	
843  	   /* correct lower and upper bounds and solution */
844  	   if ( SCIPisNegative(scip, sigma) )
845  	   {
846  	      SCIP_Real l;
847  	
848  	      assert( ! SCIPisInfinity(scip, -*ub) );
849  	      if ( ! SCIPisInfinity(scip, *ub) )
850  	         l = *ub/sigma + offset;
851  	      else
852  	         l = -SCIPinfinity(scip);
853  	
854  	      assert( ! SCIPisInfinity(scip, *lb) );
855  	      if ( ! SCIPisInfinity(scip, -*lb) )
856  	         *ub = *lb/sigma + offset;
857  	      else
858  	         *ub = SCIPinfinity(scip);
859  	      *lb = l;
860  	   }
861  	   else
862  	   {
863  	      assert( ! SCIPisInfinity(scip, *lb) );
864  	      if ( ! SCIPisInfinity(scip, -*lb) )
865  	         *lb = *lb/sigma + offset;
866  	      assert( ! SCIPisInfinity(scip, -*ub) );
867  	      if ( ! SCIPisInfinity(scip, *ub) )
868  	         *ub = *ub/sigma + offset;
869  	   }
870  	   *primsol = *primsol/sigma + offset;
871  	
872  	   return SCIP_OKAY;
873  	}
874  	
875  	
876  	/** compute objective coefficient for rows that are weighted by size
877  	 *
878  	 *  The objective is computed by multiplying a default value by
879  	 *  \f[
880  	 *  1 - (r_{\mbox{max}} - r) \frac{1 - a}{r_{\mbox{max}} - r_{\mbox{min}}},
881  	 *  \f]
882  	 *  where \f$r\f$ is the size of the current row, \f$a \in [0,1]\f$ is a parameter, and \f$r_{\mbox{max}}\f$ and
883  	 *  \f$r_{\mbox{min}}\f$ are the maximal and minimal size of a row, respectively.
884  	 *
885  	 *  Thus, if \f$r = r_{\mbox{max}}\f$, we get 1 and if \f$r = r_{\mbox{min}}\f$, we get \f$a\f$.
886  	 */
887  	static
888  	SCIP_Real computeObjWeightSize(
889  	   int                   rowsize,            /**< size of current row */
890  	   int                   minrowsize,         /**< maximal size of rows */
891  	   int                   maxrowsize          /**< minimal size of rows */
892  	   )
893  	{
894  	   SCIP_Real a;
895  	
896  	   assert( maxrowsize > 0 );
897  	   assert( minrowsize < INT_MAX );
898  	   assert( minrowsize <= maxrowsize );
899  	   assert( minrowsize <= rowsize && rowsize <= maxrowsize );
900  	
901  	   if ( minrowsize == maxrowsize )
902  	      return 1.0;
903  	
904  	   a = (1.0 - OBJWEIGHTRANGE)/((SCIP_Real) (maxrowsize - minrowsize));
905  	
906  	   return 1.0 - a * ((SCIP_Real) (maxrowsize - rowsize));
907  	}
908  	
909  	
910  	/** Creates a subscip representing the separating MIP.
911  	 *
912  	 *  Let the constraints of the original MIP be of the following form:
913  	 *  \f[
914  	 *    \begin{array}{l@{\;}ll}
915  	 *      a \leq A x + & C r & \leq b\\
916  	 *      \ell \leq x & & \leq u\\
917  	 *      c \leq & r & \leq d\\
918  	 *      x \in Z^n.
919  	 *    \end{array}
920  	 *  \f]
921  	 *  Here, some of the bounds may have value \f$\infty\f$ or \f$-\infty\f$.  Written in
922  	 *  \f$\leq\f$-form this becomes:
923  	 *  \f[
924  	 *    \begin{array}{r@{\;}l}
925  	 *      \tilde{A} x + \tilde{C} r & \leq \tilde{b}\\
926  	 *      -x & \leq -\ell\\
927  	 *      x & \leq u\\
928  	 *      -r & \leq -c\\
929  	 *      r & \leq d\\
930  	 *      x \in Z^n,
931  	 *    \end{array}
932  	 *  \f]
933  	 *  where we use
934  	 *  \f[
935  	 *    \tilde{A} =
936  	 *    \left[
937  	 *    \begin{array}{r}
938  	 *      -A \\
939  	 *      A
940  	 *    \end{array}
941  	 *    \right],
942  	 *    \quad
943  	 *    \tilde{C} =
944  	 *    \left[
945  	 *    \begin{array}{r}
946  	 *      - C\\
947  	 *      C
948  	 *    \end{array}
949  	 *    \right]
950  	 *    \qquad\mbox{ and }\qquad
951  	 *    \tilde{b} =
952  	 *    \left[
953  	 *    \begin{array}{r}
954  	 *      -a\\
955  	 *      b
956  	 *    \end{array}
957  	 *    \right].
958  	 *  \f]
959  	 *  For the moment we assume that \f$c = 0\f$, i.e., the lower bounds on the continuous variables
960  	 *  are 0.  To obtain a Chv&aacute;tal-Gomory cut we have to find nonnegative multipliers \f$y\f$,
961  	 *  \f$\underline{z}\f$, and \f$\overline{z}\f$ such that
962  	 *  \f[
963  	 *      y^T \tilde{A} - \underline{z}^T + \overline{z}^T  \in Z \qquad\mbox{ and }\qquad
964  	 *      y^T \tilde{C} \geq 0.
965  	 *  \f]
966  	 *  Note that we use zero multipliers for the bounds on the continuous variables \f$r\f$. Moreover,
967  	 *  if some bounds are infinity, the corresponding multipliers are assumed to be 0. From these
968  	 *  conditions, we obtain
969  	 *  \f[
970  	 *      (y^T \tilde{A} - \underline{z}^T + \overline{z}^T)\, x +
971  	 *      y^T \tilde{C} \, r \leq
972  	 *      y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u.
973  	 *  \f]
974  	 *  Because \f$r \geq 0\f$, we can ignore the term \f$y^T \tilde{C} \, r \geq 0\f$ and obtain the
975  	 *  following cut:
976  	 *  \f[
977  	 *      (y^T \tilde{A} - \underline{z}^T + \overline{z}^T )\, x \leq
978  	 *      \lfloor y^T \tilde{b} - \underline{z}^T \ell + \overline{z}^T u \rfloor.
979  	 *  \f]
980  	 *  Assume that \f$\ell = 0\f$ for the meantime. Then the cut can be written as:
981  	 *  \f[
982  	 *      \lfloor y^T \tilde{A} + \overline{z}^T \rfloor \, x \leq
983  	 *      \lfloor y^T \tilde{b} + \overline{z}^T u \rfloor.
984  	 *  \f]
985  	 *
986  	 *  Following Fischetti and Lodi [2005], let \f$(x^*,r^*)\f$ be a fractional solution of the above
987  	 *  original system.  The separating MIP created below is
988  	 *  \f[
989  	 *    \begin{array}{rlr@{\;}l}
990  	 *       \max & (x^*)^T \alpha - \beta - w^T y \\
991  	 *            & f = \tilde{A}^T y + \overline{z} - \alpha \\
992  	 *            & \tilde{f} = \tilde{b}^T y + u^T \overline{z} - \beta\\
993  	 *            & \tilde{C}^T y \geq 0\\
994  	 *            & 0 \leq f \leq 1 - \epsilon \\
995  	 *            & 0 \leq \tilde{f} \leq 1 - \epsilon\\
996  	 *            & 0 \leq y, \overline{z} \leq 1 - \epsilon.\\
997  	 *            & \alpha \in Z^m, \beta \in Z.
998  	 *    \end{array}
999  	 *  \f]
1000 	 *  Here, \f$w\f$ is a weight vector; it's idea is to make the sum over all components of \f$y\f$ as
1001 	 *  small as possible, in order to generate sparse cuts.
1002 	 *
1003 	 *  We perform the following additional computations:
1004 	 *
1005 	 *  - If the lower bounds on \f$x_i\f$ or \f$r_j\f$ are finite, we shift the variable to have a zero
1006 	 *    lower bound, i.e., we replace it by \f$x_i - \ell_i\f$ (or \f$r_j - u_j\f$). This is helpful in
1007 	 *    several ways: As seen above, the resulting inequalities/formulations simplify. Moreover, it
1008 	 *    allows to drop a variable if \f$x^*_i = 0\f$, see the next comment. If the lower bounds are not
1009 	 *    finite, but the upper bounds are finite, we can complement the variable. If the variables are
1010 	 *    free, the above formulation changes as follows: For free continuous variables, we require
1011 	 *    \f$\tilde{C}^T y = 0\f$. For a free integer variable \f$x_j\f$ (which rarely occurs in
1012 	 *    practice), we require \f$f_j = 0\f$, i.e., we force that \f$(\tilde{A}^T y + \overline{z})_j =
1013 	 *    \alpha_j\f$.
1014 	 *
1015 	 *  - If \f$x^*_j = 0 = \ell_j\f$ (after the above preprocessing), we drop variable \f$\alpha_j\f$
1016 	 *    from the formulation. Let \f$(\alpha^*, \beta^*, y^*, \overline{z}^*)\f$ be an
1017 	 *    optimal solution to the separating MIP. Then we can compute \f$\alpha_j =
1018 	 *    \lfloor(\tilde{A}_j^T y^* + \overline{z}^*)\rfloor\f$.
1019 	 *
1020 	 *  - If \f$x^*_i = u_i\f$, we complement the variable and drop it from the formulation, since the
1021 	 *    lower bound is 0 afterwards.
1022 	 *
1023 	 *  - If a variable has been shifted or complemented, we have to recompute \f$\beta\f$ with the
1024 	 *    original lhs/rhs.
1025 	 *
1026 	 *  - If a continuous variable \f$r_j\f$ is free, we have to force equality for the corresponding components in
1027 	 *    \f$y^T \tilde{C} \, r \geq 0\f$.
1028 	 *
1029 	 *  - If an integer variable \f$x_i\f$ is free, we are not allowed to round the cut down. In this
1030 	 *    case, the combintation of rows and bounds has to be integral. We force this by requiring that
1031 	 *    \f$f_i = 0\f$.
1032 	 *
1033 	 *  - If @p contconvert is true, some integral variables are randomly treated as if they were
1034 	 *    continuous. This has the effect that in the resulting cut the corresponding coefficient has
1035 	 *    value 0. This makes the cuts more sparse. Moreover, the separation problems should become
1036 	 *    easier.
1037 	 *
1038 	 *  - If required, i.e., parameter @p primalseparation is true, we force a primal separation step. For
1039 	 *    this we require that the cut is tight at the currently best solution. To get reliable solutions
1040 	 *    we relax equality by EPSILONVALUE.
1041 	 *
1042 	 *  - If required (via parameters @p useobjub or @p useobjlb), we add a row corresponding to the objective function with
1043 	 *    respect to the current lower and upper bounds.
1044 	 */
1045 	static
1046 	SCIP_RETCODE createSubscip(
1047 	   SCIP*                 origscip,           /**< SCIP data structure */
1048 	   SCIP_SEPA*            sepa,               /**< separator */
1049 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
1050 	   CGMIP_MIPDATA*        mipdata             /**< data for sub-MIP */
1051 	   )
1052 	{
1053 	   SCIP* subscip;
1054 	   SCIP_COL** cols;
1055 	   SCIP_ROW** rows;
1056 	   SCIP_Real* lhs;
1057 	   SCIP_Real* rhs;
1058 	   SCIP_Real* lb;
1059 	   SCIP_Real* ub;
1060 	   SCIP_Real* primsol;
1061 	   SCIP_Real multvarub;
1062 	
1063 	   unsigned int cnt;
1064 	   unsigned int ucnt;
1065 	   unsigned int nshifted;
1066 	   unsigned int ncomplemented;
1067 	#ifndef NDEBUG
1068 	   unsigned int ncontconverted = 0;
1069 	   unsigned int nintconverted = 0;
1070 	#endif
1071 	   unsigned int nlbounds;
1072 	   unsigned int nubounds;
1073 	
1074 	   SCIP_VAR** consvars;
1075 	   SCIP_Real* consvals;
1076 	   SCIP_CONS* cons;
1077 	   int nconsvars;
1078 	   char name[SCIP_MAXSTRLEN];
1079 	
1080 	   int ncols;
1081 	   int nrows;
1082 	   int ntotalrows;
1083 	   int maxrowsize = 0;
1084 	   int minrowsize = INT_MAX;
1085 	   int i, j;
1086 	
1087 	   assert( origscip != NULL );
1088 	   assert( sepadata != NULL );
1089 	
1090 	   assert( mipdata->subscip == NULL );
1091 	
1092 	   SCIP_CALL( SCIPgetLPColsData(origscip, &cols, &ncols) );
1093 	   SCIP_CALL( SCIPgetLPRowsData(origscip, &rows, &nrows) );
1094 	   assert( ncols > 0 && nrows > 0 );
1095 	
1096 	   mipdata->m = 0;
1097 	   mipdata->n = 0;
1098 	   mipdata->nrows = (unsigned int) nrows;
1099 	   mipdata->ncols = (unsigned int) ncols;
1100 	   mipdata->ntotalrows = mipdata->nrows;
1101 	
1102 	   if ( sepadata->useobjub || sepadata->useobjlb )
1103 	      mipdata->ntotalrows = mipdata->nrows + 1;
1104 	
1105 	   assert(mipdata->ntotalrows <= INT_MAX);
1106 	   ntotalrows = (int) mipdata->ntotalrows;
1107 	
1108 	   /* copy value */
1109 	   mipdata->conshdlrusenorm = sepadata->conshdlrusenorm;
1110 	
1111 	   /* create subscip */
1112 	   SCIP_CALL( SCIPcreate( &(mipdata->subscip) ) );
1113 	   subscip = mipdata->subscip;
1114 	   SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
1115 	
1116 	   /* add violation constraint handler if requested */
1117 	   if ( sepadata->addviolconshdlr )
1118 	   {
1119 	      SCIP_CALL( SCIPincludeConshdlrViolatedCut(subscip, mipdata) );
1120 	   }
1121 	
1122 	   (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sepa_cgmip separating MIP (%s)", SCIPgetProbName(origscip));
1123 	   SCIP_CALL( SCIPcreateProb(subscip, name, NULL, NULL , NULL , NULL , NULL , NULL , NULL) );
1124 	   SCIPsetSubscipDepth(subscip, SCIPgetSubscipDepth(origscip) + 1);
1125 	   SCIP_CALL( SCIPsetObjsense(subscip, SCIP_OBJSENSE_MAXIMIZE) );
1126 	
1127 	   /* alloc memory for subscipdata elements */
1128 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->alpha), ncols) );
1129 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->fracalpha), ncols) );
1130 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->coltype), ncols) );
1131 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->iscomplemented), ncols) );
1132 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->isshifted), ncols) );
1133 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->ylhs), ntotalrows) );
1134 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->yrhs), ntotalrows) );
1135 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->z), 2*ncols) );
1136 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->lhs), ntotalrows) );
1137 	   SCIP_CALL( SCIPallocBlockMemoryArray(origscip, &(mipdata->rhs), ntotalrows) );
1138 	   lhs = mipdata->lhs;
1139 	   rhs = mipdata->rhs;
1140 	
1141 	   /* get temporary storage */
1142 	   SCIP_CALL( SCIPallocBufferArray(origscip, &lb, ncols) );
1143 	   SCIP_CALL( SCIPallocBufferArray(origscip, &ub, ncols) );
1144 	   SCIP_CALL( SCIPallocBufferArray(origscip, &primsol, ncols) );
1145 	
1146 	   /* store lhs/rhs for complementing (see below) and compute maximal nonzeros of candidate rows */
1147 	   for (i = 0; i < nrows; ++i)
1148 	   {
1149 	      SCIP_Real val;
1150 	      SCIP_ROW* row;
1151 	
1152 	      row = rows[i];
1153 	      assert( row != NULL );
1154 	
1155 	      val = SCIProwGetLhs(row) - SCIProwGetConstant(row);
1156 	      if ( SCIProwIsIntegral(row) )
1157 	         val = SCIPfeasCeil(origscip, val); /* row is integral: round left hand side up */
1158 	      lhs[i] = val;
1159 	
1160 	      val = SCIProwGetRhs(row) - SCIProwGetConstant(row);
1161 	      if ( SCIProwIsIntegral(row) )
1162 	         val = SCIPfeasFloor(origscip, val); /* row is integral: round right hand side down */
1163 	      rhs[i] = val;
1164 	
1165 	      /* skip modifiable rows and local rows, unless allowed */
1166 	      if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1167 	         continue;
1168 	
1169 	      /* skip rows that not have been active for a longer time */
1170 	      if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage )
1171 	         continue;
1172 	
1173 	      /* check whether we want to skip cuts produced by the CGMIP separator */
1174 	      if ( sepadata->onlyrankone )
1175 	      {
1176 	         if ( SCIProwGetOriginSepa(row) == sepa )
1177 	            continue;
1178 	      }
1179 	
1180 	      /* determine maximal row size: */
1181 	      val = SCIPgetRowLPActivity(origscip, row);
1182 	      if ( ! SCIPisInfinity(origscip, REALABS(lhs[i])) )
1183 	      {
1184 	         if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetLhs(row)) )
1185 	         {
1186 	            if ( SCIProwGetNLPNonz(row) > maxrowsize )
1187 	               maxrowsize = SCIProwGetNLPNonz(row);
1188 	            if ( SCIProwGetNLPNonz(row) < minrowsize )
1189 	               minrowsize = SCIProwGetNLPNonz(row);
1190 	         }
1191 	      }
1192 	      else
1193 	      {
1194 	         if ( ! SCIPisInfinity(origscip, rhs[i]) )
1195 	         {
1196 	            if ( ! sepadata->onlyactiverows || SCIPisFeasEQ(origscip, val, SCIProwGetRhs(row)) )
1197 	            {
1198 	               if ( SCIProwGetNLPNonz(row) > maxrowsize )
1199 	                  maxrowsize = SCIProwGetNLPNonz(row);
1200 	               if ( SCIProwGetNLPNonz(row) < minrowsize )
1201 	                  minrowsize = SCIProwGetNLPNonz(row);
1202 	            }
1203 	         }
1204 	      }
1205 	   }
1206 	   assert( maxrowsize > 0 );
1207 	   assert( minrowsize < INT_MAX );
1208 	
1209 	   /* add cuts for objective function if required */
1210 	   if ( sepadata->useobjub )
1211 	   {
1212 	      assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1213 	      rhs[mipdata->nrows] = SCIPgetUpperbound(origscip);
1214 	      assert( ! SCIPisObjIntegral(origscip) || SCIPisFeasIntegral(origscip, SCIPgetUpperbound(origscip)) );
1215 	
1216 	      if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize )
1217 	         maxrowsize = SCIPgetNObjVars(origscip);
1218 	      if ( ! SCIPisInfinity(origscip, SCIPgetUpperbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize )
1219 	         minrowsize = SCIPgetNObjVars(origscip);
1220 	   }
1221 	   if ( sepadata->useobjlb )
1222 	   {
1223 	      assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1224 	
1225 	      if ( SCIPisObjIntegral(origscip) )
1226 	         lhs[mipdata->nrows] = SCIPfeasCeil(origscip, SCIPgetLowerbound(origscip));
1227 	      else
1228 	         lhs[mipdata->nrows] = SCIPgetLowerbound(origscip);
1229 	
1230 	      if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) > maxrowsize )
1231 	         maxrowsize = SCIPgetNObjVars(origscip);
1232 	      if ( ! SCIPisInfinity(origscip, -SCIPgetLowerbound(origscip)) && SCIPgetNObjVars(origscip) < minrowsize )
1233 	         minrowsize = SCIPgetNObjVars(origscip);
1234 	   }
1235 	
1236 	   /* store lb/ub for complementing and perform preprocessing */
1237 	   nshifted = 0;
1238 	   ncomplemented = 0;
1239 	   nlbounds = 0;
1240 	   nubounds = 0;
1241 	   for (j = 0; j < ncols; ++j)
1242 	   {
1243 	      SCIP_COL* col;
1244 	      SCIP_VAR* var;
1245 	
1246 	      col = cols[j];
1247 	      assert( col != NULL );
1248 	      var = SCIPcolGetVar(col);
1249 	      assert( var != NULL );
1250 	
1251 	      primsol[j] = SCIPcolGetPrimsol(col);
1252 	      assert( SCIPisEQ(origscip, SCIPgetVarSol(origscip, var), primsol[j]) );
1253 	
1254 	      lb[j] = SCIPvarGetLbGlobal(var);
1255 	      assert( SCIPisEQ(origscip, SCIPvarGetLbLocal(var), SCIPcolGetLb(col)) );
1256 	
1257 	      /* if allowed, try to use stronger local bound */
1258 	      if ( sepadata->allowlocal && SCIPisGT(origscip, SCIPvarGetLbLocal(var), lb[j]) )
1259 	         lb[j] = SCIPvarGetLbLocal(var);
1260 	
1261 	      ub[j] = SCIPvarGetUbGlobal(var);
1262 	      assert( SCIPisEQ(origscip, SCIPvarGetUbLocal(var), SCIPcolGetUb(col)) );
1263 	
1264 	      /* if allowed, try to use stronger local bound */
1265 	      if ( sepadata->allowlocal && SCIPisLT(origscip, SCIPvarGetUbLocal(var), ub[j]) )
1266 	         ub[j] = SCIPvarGetUbLocal(var);
1267 	
1268 	      mipdata->coltype[j] = colPresent;
1269 	      mipdata->iscomplemented[j] = FALSE;
1270 	      mipdata->isshifted[j] = FALSE;
1271 	
1272 	      /* check status of column/variable */
1273 	      if ( SCIPcolIsIntegral(col) )
1274 	      {
1275 	         /* integral variables taking integral values are not interesting - will be substituted out below */
1276 	         if ( ! SCIPisFeasIntegral(origscip, primsol[j]) )
1277 	         {
1278 	            /* possibly convert fractional integral variables to take integral values */
1279 	            if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
1280 	            {
1281 	               /* randomly convert variables */
1282 	               if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->intconvfrac )
1283 	               {
1284 	                  assert( ! SCIPisInfinity(origscip, ub[j]) || ! SCIPisInfinity(origscip, -lb[j]) );
1285 	
1286 	                  /* if both bounds are finite, take the closer one */
1287 	                  if ( ! SCIPisInfinity(origscip, ub[j]) && ! SCIPisInfinity(origscip, -lb[j]) )
1288 	                  {
1289 	                     assert( SCIPisFeasIntegral(origscip, ub[j]) );
1290 	                     assert( SCIPisFeasIntegral(origscip, lb[j]) );
1291 	                     assert( SCIPisFeasLT(origscip, primsol[j], ub[j]) );
1292 	                     assert( SCIPisFeasGT(origscip, primsol[j], lb[j]) );
1293 	                     if ( ub[j] - primsol[j] < primsol[j] - lb[j] )
1294 	                        primsol[j] = ub[j];
1295 	                     else
1296 	                        primsol[j] = lb[j];
1297 	#ifndef NDEBUG
1298 	                     ++nintconverted;
1299 	#endif
1300 	                  }
1301 	                  else
1302 	                  {
1303 	                     /* if only lower bound is finite */
1304 	                     if ( ! SCIPisInfinity(origscip, -lb[j]) )
1305 	                     {
1306 	                        assert( SCIPisFeasIntegral(origscip, lb[j]) );
1307 	                        primsol[j] = lb[j];
1308 	#ifndef NDEBUG
1309 	                        ++nintconverted;
1310 	#endif
1311 	                     }
1312 	                     else
1313 	                     {
1314 	                        assert( ! SCIPisInfinity(origscip, ub[j]) );
1315 	                        assert( SCIPisFeasIntegral(origscip, ub[j]) );
1316 	                        primsol[j] = ub[j];
1317 	#ifndef NDEBUG
1318 	                        ++nintconverted;
1319 	#endif
1320 	                     }
1321 	                  }
1322 	               }
1323 	            }
1324 	         }
1325 	
1326 	         /* integral variables taking integral values are not interesting - will be substituted out below */
1327 	         if ( ! SCIPisFeasIntegral(origscip, primsol[j]) )
1328 	         {
1329 	            /* possibly convert integral variables to be continuous */
1330 	            if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
1331 	            {
1332 	               /* randomly convert variables */
1333 	               if ( SCIPrandomGetReal(sepadata->randnumgen, 0.0, 1.0) <= sepadata->contconvfrac )
1334 	               {
1335 	                  /* preprocessing is also performed for converted columns */
1336 	                  mipdata->coltype[j] = colConverted;
1337 	#ifndef NDEBUG
1338 	                  ++ncontconverted;
1339 	#endif
1340 	               }
1341 	            }
1342 	         }
1343 	      }
1344 	      else
1345 	      {
1346 	         /* detect continuous variables, but perform preprocessing for them */
1347 	         mipdata->coltype[j] = colContinuous;
1348 	      }
1349 	
1350 	      /* if integer variable is at its upper bound -> complementing (this also generates a 0 lower bound) */
1351 	      if ( mipdata->coltype[j] == colPresent && SCIPisFeasEQ(origscip, primsol[j], ub[j]) )
1352 	      {
1353 	         assert( ! SCIPisInfinity(origscip, ub[j]) );
1354 	         SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1355 	         mipdata->iscomplemented[j] = TRUE;
1356 	         mipdata->coltype[j] = colAtUb;
1357 	         ++nubounds;
1358 	      }
1359 	      else
1360 	      {
1361 	         /* if a variable has a finite nonzero lower bound -> shift */
1362 	         if ( ! SCIPisInfinity(origscip, -lb[j]) )
1363 	         {
1364 	            if ( ! SCIPisZero(origscip, lb[j]) )
1365 	            {
1366 	               SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, -lb[j], 1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1367 	               assert( SCIPisZero(origscip, lb[j]) );
1368 	               mipdata->isshifted[j] = TRUE;
1369 	               ++nshifted;
1370 	            }
1371 	
1372 	            /* if integer variable is at its lower bound */
1373 	            if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) )
1374 	            {
1375 	               mipdata->coltype[j] = colAtLb;
1376 	               ++nlbounds;
1377 	            }
1378 	         }
1379 	         else
1380 	         {
1381 	            /* lower bound is minus-infinity -> check whether upper bound is finite */
1382 	            if ( ! SCIPisInfinity(origscip, ub[j]) )
1383 	            {
1384 	               /* complement variable */
1385 	               SCIP_CALL( transformColumn(origscip, sepadata, mipdata, col, ub[j], -1.0, lhs, rhs, &(lb[j]), &(ub[j]), &(primsol[j])) );
1386 	               assert( SCIPisZero(origscip, lb[j]) );
1387 	               mipdata->iscomplemented[j] = TRUE;
1388 	               ++ncomplemented;
1389 	
1390 	               /* if integer variable is at its lower bound */
1391 	               if ( mipdata->coltype[j] == colPresent && SCIPisZero(origscip, primsol[j]) )
1392 	               {
1393 	                  mipdata->coltype[j] = colAtLb;
1394 	                  ++nlbounds;
1395 	               }
1396 	            }
1397 	         }
1398 	      }
1399 	
1400 	      assert( SCIPisFeasLE(origscip, lb[j], primsol[j]) );
1401 	      assert( SCIPisFeasLE(origscip, primsol[j], ub[j]) );
1402 	   }
1403 	
1404 	#ifndef NDEBUG
1405 	   if ( sepadata->intconvert && ncols >= sepadata->intconvmin )
1406 	   {
1407 	      SCIPdebugMsg(origscip, "Converted %u fractional integral variables to have integral value.\n", nintconverted);
1408 	   }
1409 	   if ( sepadata->contconvert && ncols >= sepadata->contconvmin )
1410 	   {
1411 	      SCIPdebugMsg(origscip, "Converted %u integral variables to be continuous.\n", ncontconverted);
1412 	   }
1413 	#endif
1414 	   SCIPdebugMsg(origscip, "Original variables: %d integral, %d continuous, %u shifted, %u complemented, %u at lb, %u at ub\n",
1415 	      SCIPgetNBinVars(origscip) + SCIPgetNIntVars(origscip) + SCIPgetNImplVars(origscip), SCIPgetNContVars(origscip),
1416 	      nshifted, ncomplemented, nlbounds, nubounds);
1417 	
1418 	   /* prepare upper bound on y-variables */
1419 	   if ( sepadata->skipmultbounds )
1420 	      multvarub = SCIPinfinity(origscip);
1421 	   else
1422 	      multvarub = 1.0 - EPSILONVALUE;
1423 	
1424 	   /* create artificial variables for row combinations (y-variables) */
1425 	   cnt = 0;
1426 	   for (i = 0; i < nrows; ++i)
1427 	   {
1428 	      SCIP_ROW* row;
1429 	
1430 	      row = rows[i];
1431 	      assert( row != NULL );
1432 	
1433 	      mipdata->ylhs[i] = NULL;
1434 	      mipdata->yrhs[i] = NULL;
1435 	
1436 	      /* skip modifiable rows and local rows, unless allowed */
1437 	      if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1438 	         continue;
1439 	
1440 	      /* skip rows that not have been active for a longer time */
1441 	      if ( ! sepadata->onlyactiverows && sepadata->maxrowage > 0 && SCIProwGetAge(row) > sepadata->maxrowage )
1442 	         continue;
1443 	
1444 	      /* check whether we want to skip cuts produced by the CGMIP separator */
1445 	      if ( sepadata->onlyrankone )
1446 	      {
1447 	         if ( SCIProwGetOriginSepa(row) == sepa )
1448 	            continue;
1449 	      }
1450 	
1451 	      /* if we have an equation */
1452 	      if ( SCIPisEQ(origscip, lhs[i], rhs[i]) )
1453 	      {
1454 	         SCIP_Real weight = -sepadata->objweight;
1455 	
1456 	         assert( ! SCIPisInfinity(origscip, rhs[i]) );
1457 	         assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) ); /* equations should always be active */
1458 	         assert( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) );
1459 	
1460 	         if ( sepadata->objweightsize )
1461 	            weight = - sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1462 	
1463 	         /* create two variables for each equation */
1464 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq1_%d", i);
1465 	         SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub,
1466 	               weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1467 	         SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) );
1468 	         ++cnt;
1469 	
1470 	#ifdef SCIP_MORE_DEBUG
1471 	         SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row));
1472 	#endif
1473 	
1474 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yeq2_%d", i);
1475 	         SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub,
1476 	               weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1477 	         SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) );
1478 	         ++cnt;
1479 	
1480 	#ifdef SCIP_MORE_DEBUG
1481 	         SCIPdebugMsg(origscip, "Created variable <%s> for equation <%s>.\n", name, SCIProwGetName(row));
1482 	#endif
1483 	      }
1484 	      else
1485 	      {
1486 	         /* create variable for lhs of row if necessary */
1487 	         if ( ! SCIPisInfinity(origscip, -lhs[i]) )
1488 	         {
1489 	            SCIP_Bool isactive = FALSE;
1490 	            SCIP_Real weight = 0.0;
1491 	
1492 	            /* if the row is active, use objective weight equal to -sepadata->objweight */
1493 	            if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetLhs(row)) )
1494 	            {
1495 	               isactive = TRUE;
1496 	               if ( sepadata->objweightsize )
1497 	                  weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1498 	               else
1499 	                  weight = -sepadata->objweight;
1500 	            }
1501 	
1502 	            if ( ! sepadata->onlyactiverows || isactive )
1503 	            {
1504 	               /* add variable */
1505 	               (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ylhs_%d", i);
1506 	               SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[i]), name, 0.0, multvarub,
1507 	                     weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1508 	               SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[i]) );
1509 	               ++cnt;
1510 	
1511 	#ifdef SCIP_MORE_DEBUG
1512 	               SCIPdebugMsg(origscip, "Created variable <%s> for >= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight);
1513 	#endif
1514 	            }
1515 	         }
1516 	
1517 	         /* create variable for rhs of row if necessary */
1518 	         if ( ! SCIPisInfinity(origscip, rhs[i]) )
1519 	         {
1520 	            SCIP_Bool isactive = FALSE;
1521 	            SCIP_Real weight = 0.0;
1522 	
1523 	            /* if the row is active, use objective weight equal to -sepadata->objweight */
1524 	            if ( SCIPisFeasEQ(origscip, SCIPgetRowLPActivity(origscip, row), SCIProwGetRhs(row)) )
1525 	            {
1526 	               isactive = TRUE;
1527 	               if ( sepadata->objweightsize )
1528 	                  weight = -sepadata->objweight * computeObjWeightSize(SCIProwGetNLPNonz(row), minrowsize, maxrowsize);
1529 	               else
1530 	                  weight = -sepadata->objweight;
1531 	            }
1532 	
1533 	            if ( ! sepadata->onlyactiverows || isactive )
1534 	            {
1535 	               (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yrhs_%d", i);
1536 	               SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[i]), name, 0.0, multvarub,
1537 	                     weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1538 	               SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[i]) );
1539 	               ++cnt;
1540 	
1541 	#ifdef SCIP_MORE_DEBUG
1542 	               SCIPdebugMsg(origscip, "Created variable <%s> for <= inequality <%s> (weight: %f).\n", name, SCIProwGetName(row), weight);
1543 	#endif
1544 	            }
1545 	         }
1546 	      }
1547 	   }
1548 	   assert( (int) cnt <= 2 * nrows );
1549 	   mipdata->n += cnt;
1550 	
1551 	   /* create artificial variables for objective function (if required) (y-variables) */
1552 	   if ( sepadata->useobjub || sepadata->useobjlb )
1553 	   {
1554 	      SCIP_Real weight = 0.0;
1555 	
1556 	      assert( mipdata->ntotalrows == mipdata->nrows + 1 );
1557 	      mipdata->ylhs[mipdata->nrows] = NULL;
1558 	      mipdata->yrhs[mipdata->nrows] = NULL;
1559 	      cnt = 0;
1560 	
1561 	      if ( sepadata->objweightsize )
1562 	         weight = -sepadata->objweight * computeObjWeightSize(SCIPgetNObjVars(origscip), minrowsize, maxrowsize);
1563 	      else
1564 	         weight = -sepadata->objweight;
1565 	
1566 	      /* create variable for upper objective bound if necessary */
1567 	      if ( sepadata->useobjub && ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) )
1568 	      {
1569 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjub");
1570 	         SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->yrhs[mipdata->nrows]), name, 0.0, multvarub,
1571 	               weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1572 	         SCIP_CALL( SCIPaddVar(subscip, mipdata->yrhs[mipdata->nrows]) );
1573 	         ++cnt;
1574 	
1575 	#ifdef SCIP_MORE_DEBUG
1576 	         SCIPdebugMsg(origscip, "Created variable <%s> for upper bound on objective (weight: %f).\n", name, weight);
1577 	#endif
1578 	      }
1579 	
1580 	      /* create variable for lower bound objective if necessary */
1581 	      if ( sepadata->useobjlb && ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) )
1582 	      {
1583 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "yobjlb");
1584 	         SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->ylhs[mipdata->nrows]), name, 0.0, multvarub,
1585 	               weight, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1586 	         SCIP_CALL( SCIPaddVar(subscip, mipdata->ylhs[mipdata->nrows]) );
1587 	         ++cnt;
1588 	
1589 	#ifdef SCIP_MORE_DEBUG
1590 	         SCIPdebugMsg(origscip, "Created variable <%s> for lower bound on objective (weight: %f).\n", name, weight);
1591 	#endif
1592 	      }
1593 	
1594 	      assert( (int) cnt <= 2 * ntotalrows );
1595 	      mipdata->n += cnt;
1596 	   }
1597 	
1598 	   /* create alpha, bound, and fractional variables */
1599 	   cnt = 0;
1600 	   ucnt = 0;
1601 	   for (j = 0; j < ncols; ++j)
1602 	   {
1603 	      mipdata->z[j] = NULL;
1604 	      mipdata->alpha[j] = NULL;
1605 	      mipdata->fracalpha[j] = NULL;
1606 	
1607 	      if ( mipdata->coltype[j] == colPresent )
1608 	      {
1609 	         SCIP_Real obj;
1610 	
1611 	         if ( sepadata->objlone )
1612 	            obj = 0.0;
1613 	         else
1614 	            obj = primsol[j];
1615 	
1616 	         /* create alpha variables */
1617 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j);
1618 	         SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->alpha[j]), name, -sepadata->cutcoefbnd, sepadata->cutcoefbnd, obj,
1619 	               SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1620 	         SCIP_CALL( SCIPaddVar(subscip, mipdata->alpha[j]) );
1621 	         ++cnt;
1622 	
1623 	         /* create fractional variables */
1624 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "f_%d", j);
1625 	         if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) )
1626 	         {
1627 	            /* fix fractional value to be zero for free original variables */
1628 	            SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 0.0, 0.0,
1629 	                  SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1630 	         }
1631 	         else
1632 	         {
1633 	            /* fractional value in [0, 1) for variables with finite bounds */
1634 	            SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracalpha[j]), name, 0.0, 1.0-EPSILONVALUE, 0.0,
1635 	                  SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1636 	         }
1637 	         SCIP_CALL( SCIPaddVar(subscip, mipdata->fracalpha[j]) );
1638 	         ++cnt;
1639 	
1640 	         /* create variables for upper bounds */
1641 	         if ( ! SCIPisInfinity(origscip, ub[j]) )
1642 	         {
1643 	            (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "zub_%d", j);
1644 	            SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->z[j]), name, 0.0, multvarub,
1645 	                  0.0, SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1646 	            SCIP_CALL( SCIPaddVar(subscip, mipdata->z[j]) );
1647 	            ++ucnt;
1648 	         }
1649 	      }
1650 	   }
1651 	   assert( (int) cnt <= 2 * ncols );
1652 	   assert( (int) ucnt <= ncols );
1653 	
1654 	   /* create variable for the rhs of the cut */
1655 	   if ( sepadata->objlone )
1656 	   {
1657 	      SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, 0.0,
1658 	            SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1659 	   }
1660 	   else
1661 	   {
1662 	      SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->beta), "beta", -sepadata->cutcoefbnd, sepadata->cutcoefbnd, -1.0,
1663 	            SCIP_VARTYPE_INTEGER, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1664 	   }
1665 	   SCIP_CALL( SCIPaddVar(subscip, mipdata->beta) );
1666 	
1667 	   /* create fractional variable for the rhs */
1668 	   SCIP_CALL( SCIPcreateVar(subscip, &(mipdata->fracbeta), "fracbeta", 0.0, 1.0-BETAEPSILONVALUE, 0.0,
1669 	         SCIP_VARTYPE_CONTINUOUS, TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
1670 	   SCIP_CALL( SCIPaddVar(subscip, mipdata->fracbeta) );
1671 	   mipdata->n += cnt + ucnt + 2;
1672 	
1673 	   /* get temporary storage */
1674 	   SCIP_CALL( SCIPallocBufferArray(origscip, &consvals, (int) mipdata->n) );
1675 	   SCIP_CALL( SCIPallocBufferArray(origscip, &consvars, (int) mipdata->n) );
1676 	
1677 	   /* create constraints for alpha variables of CG-cut */
1678 	   cnt = 0;
1679 	   for (j = 0; j < ncols; ++j)
1680 	   {
1681 	      SCIP_ROW** colrows;
1682 	      SCIP_Real* colvals;
1683 	
1684 	      /* create ordinary part for all selected variables */
1685 	      if ( mipdata->coltype[j] == colPresent )
1686 	      {
1687 	         SCIP_Real sigma;
1688 	
1689 	         assert( cols[j] != NULL );
1690 	         colrows = SCIPcolGetRows(cols[j]);
1691 	         colvals = SCIPcolGetVals(cols[j]);
1692 	         nconsvars = 0;
1693 	
1694 	         if ( mipdata->iscomplemented[j] )
1695 	            sigma = -1.0;
1696 	         else
1697 	            sigma = 1.0;
1698 	
1699 	         /* add part for columns */
1700 	         for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i)
1701 	         {
1702 	            SCIP_ROW* row;
1703 	            int pos;
1704 	
1705 	            row = colrows[i];
1706 	            assert( row != NULL );
1707 	
1708 	            /* skip modifiable rows and local rows, unless allowed */
1709 	            if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1710 	               continue;
1711 	
1712 	            pos = SCIProwGetLPPos(row);
1713 	            assert( 0 <= pos && pos < nrows );
1714 	
1715 	            if ( mipdata->ylhs[pos] != NULL )
1716 	            {
1717 	               consvars[nconsvars] = mipdata->ylhs[pos];
1718 	               consvals[nconsvars] = -sigma * colvals[i];
1719 	               ++nconsvars;
1720 	            }
1721 	            if ( mipdata->yrhs[pos] != NULL )
1722 	            {
1723 	               consvars[nconsvars] = mipdata->yrhs[pos];
1724 	               consvals[nconsvars] = sigma * colvals[i];
1725 	               ++nconsvars;
1726 	            }
1727 	            assert( nconsvars <= (int) mipdata->n );
1728 	         }
1729 	         /* add part for upper bounds */
1730 	         if ( mipdata->z[j] != NULL )
1731 	         {
1732 	            assert( ! SCIPisInfinity(origscip, ub[j]) );
1733 	            consvars[nconsvars] = mipdata->z[j];
1734 	            consvals[nconsvars] = 1.0;
1735 	            ++nconsvars;
1736 	         }
1737 	         assert( nconsvars <= (int) mipdata->n );
1738 	
1739 	         /* add alpha variable */
1740 	         consvars[nconsvars] = mipdata->alpha[j];
1741 	         consvals[nconsvars] = -1.0;
1742 	         ++nconsvars;
1743 	         assert( nconsvars <= (int) mipdata->n );
1744 	
1745 	         /* add fractional-alpha variable */
1746 	         consvars[nconsvars] = mipdata->fracalpha[j];
1747 	         consvals[nconsvars] = -1.0;
1748 	         ++nconsvars;
1749 	         assert( nconsvars <= (int) mipdata->n );
1750 	
1751 	         /* check for lower and upper objective bounds */
1752 	         if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) )
1753 	         {
1754 	            /* add lower objective bound */
1755 	            if ( mipdata->ylhs[mipdata->nrows] != NULL )
1756 	            {
1757 	               assert( sepadata->useobjlb );
1758 	               consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1759 	               consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]);
1760 	               ++nconsvars;
1761 	            }
1762 	
1763 	            /* add upper objective bound */
1764 	            if ( mipdata->yrhs[mipdata->nrows] != NULL )
1765 	            {
1766 	               assert( sepadata->useobjub );
1767 	               consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1768 	               consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]);
1769 	               ++nconsvars;
1770 	            }
1771 	         }
1772 	
1773 	         /* add linear constraint */
1774 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "alpha_%d", j);
1775 	         SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, 0.0,
1776 	               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1777 	         SCIP_CALL( SCIPaddCons(subscip, cons) );
1778 	         SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1779 	         ++cnt;
1780 	      }
1781 	      /* generate part that makes sure that cut is valid for continuous variables */
1782 	      else if ( mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted )
1783 	      {
1784 	         SCIP_Real sigma;
1785 	         SCIP_Real r;
1786 	
1787 	         assert( cols[j] != NULL );
1788 	         colrows = SCIPcolGetRows(cols[j]);
1789 	         colvals = SCIPcolGetVals(cols[j]);
1790 	         nconsvars = 0;
1791 	
1792 	         if ( mipdata->iscomplemented[j] )
1793 	            sigma = -1.0;
1794 	         else
1795 	            sigma = 1.0;
1796 	
1797 	         /* add part for columns */
1798 	         for (i = 0; i < SCIPcolGetNLPNonz(cols[j]); ++i)
1799 	         {
1800 	            SCIP_ROW* row;
1801 	            int pos;
1802 	
1803 	            row = colrows[i];
1804 	            assert( row != NULL );
1805 	
1806 	            /* skip modifiable rows and local rows, unless allowed */
1807 	            if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
1808 	               continue;
1809 	
1810 	            pos = SCIProwGetLPPos(row);
1811 	            assert( 0 <= pos && pos < nrows );
1812 	
1813 	            if ( mipdata->ylhs[pos] != NULL )
1814 	            {
1815 	               consvars[nconsvars] = mipdata->ylhs[pos];
1816 	               consvals[nconsvars] = -sigma * colvals[i];
1817 	               ++nconsvars;
1818 	            }
1819 	            if ( mipdata->yrhs[pos] != NULL )
1820 	            {
1821 	               consvars[nconsvars] = mipdata->yrhs[pos];
1822 	               consvals[nconsvars] = sigma * colvals[i];
1823 	               ++nconsvars;
1824 	            }
1825 	            assert( nconsvars <= (int) mipdata->n );
1826 	         }
1827 	
1828 	         /* check for lower and upper objective bounds */
1829 	         if ( (sepadata->useobjub || sepadata->useobjlb) && ! SCIPisZero(origscip, SCIPcolGetObj(cols[j])) )
1830 	         {
1831 	            /* add lower objective bound */
1832 	            if ( mipdata->ylhs[mipdata->nrows] )
1833 	            {
1834 	               assert( sepadata->useobjlb );
1835 	               consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1836 	               consvals[nconsvars] = -sigma * SCIPcolGetObj(cols[j]);
1837 	               ++nconsvars;
1838 	            }
1839 	
1840 	            /* add upper objective bound */
1841 	            if ( mipdata->yrhs[mipdata->nrows] )
1842 	            {
1843 	               assert( sepadata->useobjub );
1844 	               consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1845 	               consvals[nconsvars] = sigma * SCIPcolGetObj(cols[j]);
1846 	               ++nconsvars;
1847 	            }
1848 	         }
1849 	
1850 	         /* add linear constraint */
1851 	         (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cont_%d", j);
1852 	
1853 	         /* for free continuous variables require equality */
1854 	         r = SCIPinfinity(subscip);
1855 	         if ( SCIPisInfinity(origscip, -lb[j]) && SCIPisInfinity(origscip, ub[j]) )
1856 	            r = 0.0;
1857 	         else
1858 	            assert( SCIPisZero(origscip, lb[j]) );
1859 	
1860 	         SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, name, nconsvars, consvars, consvals, 0.0, r,
1861 	               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1862 	         SCIP_CALL( SCIPaddCons(subscip, cons) );
1863 	         SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1864 	         ++cnt;
1865 	      }
1866 	   }
1867 	   assert( (int) cnt <= ncols );
1868 	   mipdata->m += cnt;
1869 	
1870 	   /* create constraints for rhs of cut */
1871 	   nconsvars = 0;
1872 	
1873 	   /* first for the rows */
1874 	   for (i = 0; i < nrows; ++i)
1875 	   {
1876 	      assert( rows[i] != NULL );
1877 	
1878 	      /* skip modifiable rows and local rows, unless allowed */
1879 	      if ( SCIProwIsModifiable(rows[i]) || (SCIProwIsLocal(rows[i]) && !sepadata->allowlocal) )
1880 	         continue;
1881 	
1882 	      /* if lhs is there */
1883 	      if ( mipdata->ylhs[i] != NULL && ! SCIPisZero(origscip, lhs[i]) )
1884 	      {
1885 	         assert( ! SCIPisInfinity(origscip, -lhs[i]) );
1886 	         consvars[nconsvars] = mipdata->ylhs[i];
1887 	         consvals[nconsvars] = -lhs[i];
1888 	         ++nconsvars;
1889 	      }
1890 	      /* if rhs is there */
1891 	      if ( mipdata->yrhs[i] != NULL && ! SCIPisZero(origscip, rhs[i]) )
1892 	      {
1893 	         assert( ! SCIPisInfinity(origscip, rhs[i]) );
1894 	         consvars[nconsvars] = mipdata->yrhs[i];
1895 	         consvals[nconsvars] = rhs[i];
1896 	         ++nconsvars;
1897 	      }
1898 	      assert( nconsvars <= (int) mipdata->n );
1899 	   }
1900 	
1901 	   if ( sepadata->useobjub || sepadata->useobjlb )
1902 	   {
1903 	      /* add lower objective bound */
1904 	      if ( mipdata->ylhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, lhs[mipdata->nrows]) )
1905 	      {
1906 	         assert( sepadata->useobjlb );
1907 	         assert( ! SCIPisInfinity(origscip, -lhs[mipdata->nrows]) );
1908 	         consvars[nconsvars] = mipdata->ylhs[mipdata->nrows];
1909 	         consvals[nconsvars] = -lhs[mipdata->nrows];
1910 	         ++nconsvars;
1911 	      }
1912 	
1913 	      /* add upper objective bound */
1914 	      if ( mipdata->yrhs[mipdata->nrows] != NULL && ! SCIPisZero(origscip, rhs[mipdata->nrows]) )
1915 	      {
1916 	         assert( sepadata->useobjub );
1917 	         assert( ! SCIPisInfinity(origscip, rhs[mipdata->nrows]) );
1918 	         consvars[nconsvars] = mipdata->yrhs[mipdata->nrows];
1919 	         consvals[nconsvars] = rhs[mipdata->nrows];
1920 	         ++nconsvars;
1921 	      }
1922 	      assert( nconsvars <= (int) mipdata->n );
1923 	   }
1924 	
1925 	   /* next for the columns */
1926 	   for (j = 0; j < ncols; ++j)
1927 	   {
1928 	      /* if ub is there */
1929 	      if ( mipdata->z[j] != NULL && ! SCIPisZero(origscip, ub[j]) )
1930 	      {
1931 	         assert( mipdata->coltype[j] == colPresent );
1932 	         assert( ! SCIPisInfinity(origscip, ub[j]) );
1933 	         consvars[nconsvars] = mipdata->z[j];
1934 	         consvals[nconsvars] = ub[j];
1935 	         ++nconsvars;
1936 	         assert( nconsvars <= (int) mipdata->n );
1937 	      }
1938 	   }
1939 	   /* add beta variable */
1940 	   consvars[nconsvars] = mipdata->beta;
1941 	   consvals[nconsvars] = -1.0;
1942 	   ++nconsvars;
1943 	
1944 	   /* add fractional-beta variable */
1945 	   consvars[nconsvars] = mipdata->fracbeta;
1946 	   consvals[nconsvars] = -1.0;
1947 	   ++nconsvars;
1948 	   assert( nconsvars <= (int) mipdata->n );
1949 	
1950 	   /* add linear constraint */
1951 	   SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "beta", nconsvars, consvars, consvals, 0.0, 0.0,
1952 	         TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1953 	   SCIP_CALL( SCIPaddCons(subscip, cons) );
1954 	   SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1955 	   ++mipdata->m;
1956 	
1957 	   /* add primal separation constraint if required */
1958 	   if ( sepadata->primalseparation )
1959 	   {
1960 	      SCIP_SOL* bestsol;
1961 	      bestsol = SCIPgetBestSol(origscip);
1962 	      if ( bestsol != NULL )
1963 	      {
1964 	         nconsvars = 0;
1965 	         for (j = 0; j < ncols; ++j)
1966 	         {
1967 	            if ( mipdata->alpha[j] != NULL )
1968 	            {
1969 	               SCIP_Real val;
1970 	               assert( mipdata->coltype[j] == colPresent );
1971 	
1972 	               val = SCIPgetSolVal(origscip, bestsol, SCIPcolGetVar(cols[j]));
1973 	               consvars[nconsvars] = mipdata->alpha[j];
1974 	               consvals[nconsvars] = val;
1975 	               ++nconsvars;
1976 	               assert( nconsvars <= (int) mipdata->n );
1977 	            }
1978 	         }
1979 	         consvars[nconsvars] = mipdata->beta;
1980 	         consvals[nconsvars] = -1.0;
1981 	         ++nconsvars;
1982 	
1983 	         /* add linear constraint - allow slight deviation from equality */
1984 	         SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "primalseparation", nconsvars, consvars, consvals, -EPSILONVALUE, EPSILONVALUE,
1985 	               TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
1986 	         SCIP_CALL( SCIPaddCons(subscip, cons) );
1987 	         SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
1988 	         ++mipdata->m;
1989 	      }
1990 	   }
1991 	
1992 	   /* add constraint to force violated cuts if required */
1993 	   if ( sepadata->addviolationcons )
1994 	   {
1995 	      nconsvars = 0;
1996 	      for (j = 0; j < ncols; ++j)
1997 	      {
1998 	         if ( mipdata->alpha[j] != NULL )
1999 	         {
2000 	            consvars[nconsvars] = mipdata->alpha[j];
2001 	            consvals[nconsvars] = primsol[j];
2002 	            ++nconsvars;
2003 	            assert( nconsvars <= (int) mipdata->n );
2004 	         }
2005 	      }
2006 	      consvars[nconsvars] = mipdata->beta;
2007 	      consvals[nconsvars] = -1.0;
2008 	      ++nconsvars;
2009 	
2010 	      /* add linear constraint - allow slight deviation from equality */
2011 	      SCIP_CALL( SCIPcreateConsLinear(subscip, &cons, "violationConstraint", nconsvars, consvars, consvals, MINEFFICACY, SCIPinfinity(subscip),
2012 	            TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2013 	      SCIP_CALL( SCIPaddCons(subscip, cons) );
2014 	      SCIP_CALL( SCIPreleaseCons(subscip, &cons) );
2015 	      ++mipdata->m;
2016 	   }
2017 	
2018 	   SCIPdebugMsg(origscip, "Subscip has %u vars (%d integral, %d continuous), %u conss.\n",
2019 	      mipdata->n, SCIPgetNIntVars(subscip), SCIPgetNContVars(subscip), mipdata->m);
2020 	
2021 	   /* free temporary memory */
2022 	   SCIPfreeBufferArray(origscip, &consvars);
2023 	   SCIPfreeBufferArray(origscip, &consvals);
2024 	
2025 	   SCIPfreeBufferArray(origscip, &primsol);
2026 	   SCIPfreeBufferArray(origscip, &lb);
2027 	   SCIPfreeBufferArray(origscip, &ub);
2028 	
2029 	   /* SCIPdebug( SCIP_CALL( SCIPprintOrigProblem(subscip, NULL, NULL, FALSE) ) ); */
2030 	
2031 	#ifdef SCIP_WRITEPROB
2032 	   {
2033 	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.lp",
2034 	         sepadata->objlone ? "_l1" : "",
2035 	         sepadata->addviolationcons ? "_vc" : "",
2036 	         sepadata->skipmultbounds ? "_ub" : "",
2037 	         sepadata->primalseparation ? "_ps" : "",
2038 	         SCIPgetProbName(origscip));
2039 	      SCIP_CALL( SCIPwriteOrigProblem(subscip, name, "lp", FALSE) );
2040 	      SCIPinfoMessage(origscip, NULL, "Wrote subscip to file <%s>.\n", name);
2041 	   }
2042 	#endif
2043 	
2044 	   return SCIP_OKAY;
2045 	}
2046 	
2047 	
2048 	/** sets parameters for subscip */
2049 	static
2050 	SCIP_RETCODE subscipSetParams(
2051 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
2052 	   CGMIP_MIPDATA*        mipdata             /**< data for sub-MIP */
2053 	   )
2054 	{
2055 	   SCIP* subscip;
2056 	
2057 	   assert( sepadata != NULL );
2058 	   assert( mipdata != NULL );
2059 	
2060 	   subscip = mipdata->subscip;
2061 	   assert( subscip != NULL );
2062 	
2063 	   /* set objective limit, if no corresponding constraint has been added */
2064 	   if ( ! sepadata->addviolationcons && ! sepadata->addviolconshdlr )
2065 	   {
2066 	      SCIP_CALL( SCIPsetObjlimit(subscip, MINEFFICACY) );
2067 	   }
2068 	
2069 	   /* do not abort subscip on CTRL-C */
2070 	   SCIP_CALL( SCIPsetBoolParam(subscip, "misc/catchctrlc", FALSE) );
2071 	
2072 	   /* disable memory saving mode: this is likely to result in the maximal depth being reached. This is because DFS
2073 	    * results in a repeated branching on the alpha-variables, which often have large bounds resulting in deep levels of
2074 	    * the tree. */
2075 	   SCIP_CALL( SCIPsetRealParam(subscip, "memory/savefac", 1.0) );
2076 	
2077 	   /* set number of solutions stored */
2078 	   SCIP_CALL( SCIPsetIntParam(subscip, "limits/maxsol", MAXNSOLS) );
2079 	
2080 	   /* determine output to console */
2081 	#ifdef SCIP_OUTPUT
2082 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2083 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) );
2084 	   SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) );
2085 	#else
2086 	   if ( sepadata->output )
2087 	   {
2088 	      SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 5) );
2089 	      SCIP_CALL( SCIPsetIntParam(subscip, "display/freq", 1000) );
2090 	      SCIP_CALL( SCIPsetIntParam(subscip, "display/nsols/active", 2) );
2091 	   }
2092 	   else
2093 	   {
2094 	      SCIP_CALL( SCIPsetIntParam(subscip, "display/verblevel", 0) );
2095 	   }
2096 	#endif
2097 	
2098 	   if ( sepadata->subscipfast )
2099 	   {
2100 	      /* forbid recursive call of plugins solving subMIPs (also disables CG-separation) */
2101 	#ifdef SCIP_OUTPUT
2102 	      SCIP_CALL( SCIPsetSubscipsOff(subscip, FALSE) );
2103 	#else
2104 	      SCIP_CALL( SCIPsetSubscipsOff(subscip, TRUE) ); /* quiet */
2105 	#endif
2106 	   }
2107 	   else
2108 	   {
2109 	      /* avoid recursive call */
2110 	      if ( ! SCIPisParamFixed(subscip, "separating/cgmip/freq") )
2111 	      {
2112 	         SCIP_CALL( SCIPsetIntParam(subscip, "separating/cgmip/freq", -1) );
2113 	      }
2114 	   }
2115 	
2116 	#ifdef SCIP_DISABLED_CODE
2117 	   /* the following possibly helps to improve performance (untested) */
2118 	   SCIP_CALL( SCIPsetEmphasis(subscip, SCIP_PARAMEMPHASIS_FEASIBILITY, TRUE) );
2119 	#else
2120 	
2121 	   /* zirounding is often successful, so allow it some more calls */
2122 	   if ( ! SCIPisParamFixed(subscip, "heuristics/zirounding/minstopncalls") )
2123 	   {
2124 	      SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/zirounding/minstopncalls", 10000) );
2125 	   }
2126 	
2127 	   if ( sepadata->subscipfast )
2128 	   {
2129 	      /* set other heuristics */
2130 	      if ( ! SCIPisParamFixed(subscip, "heuristics/shifting/freq") )
2131 	      {
2132 	         SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/shifting/freq", 3) );
2133 	      }
2134 	      if ( ! SCIPisParamFixed(subscip, "heuristics/simplerounding/freq") )
2135 	      {
2136 	         SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/simplerounding/freq", 1) );
2137 	      }
2138 	      if ( ! SCIPisParamFixed(subscip, "heuristics/rounding/freq") )
2139 	      {
2140 	         SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rounding/freq", 1) );
2141 	      }
2142 	      if ( ! SCIPisParamFixed(subscip, "heuristics/oneopt/freq") )
2143 	      {
2144 	         SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/oneopt/freq", 1) );
2145 	      }
2146 	
2147 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/pscostdiving/freq", 1) ); */
2148 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/feaspump/freq", 3) ); */
2149 	
2150 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/coefdiving/freq", -1) ); */
2151 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/fracdiving/freq", -1) ); */
2152 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/guideddiving/freq", -1) ); */
2153 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/linesearchdiving/freq", -1) ); */
2154 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/objpscostdiving/freq", -1) ); */
2155 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/rootsoldiving/freq", -1) ); */
2156 	      /*     SCIP_CALL( SCIPsetIntParam(subscip, "heuristics/veclendiving/freq", -1) ); */
2157 	
2158 	      /* use fast presolving */
2159 	      SCIP_CALL( SCIPsetPresolving(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2160 	
2161 	      /* disable conflict analysis */
2162 	      /*     SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/useprop", FALSE) ); */
2163 	      /*     SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useinflp", 'o') ); */
2164 	      /*     SCIP_CALL( SCIPsetCharParam(subscip, "conflict/useboundlp", 'o') ); */
2165 	      /*     SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usesb", FALSE) ); */
2166 	      /*     SCIP_CALL( SCIPsetBoolParam(subscip, "conflict/usepseudo", FALSE) ); */
2167 	
2168 	      /* use fast separation */
2169 	      SCIP_CALL( SCIPsetSeparating(subscip, SCIP_PARAMSETTING_FAST, TRUE) );
2170 	   }
2171 	#endif
2172 	
2173 	#ifdef SCIP_WRITEPROB
2174 	   {
2175 	      char name[SCIP_MAXSTRLEN];
2176 	
2177 	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgsepa%s%s%s%s_%s.set",
2178 	         sepadata->objlone ? "_l1" : "",
2179 	         sepadata->addviolationcons ? "_vc" : "",
2180 	         sepadata->skipmultbounds ? "_ub" : "",
2181 	         sepadata->primalseparation ? "_ps" : "",
2182 	         SCIPgetProbName(mipdata->scip));
2183 	      SCIP_CALL( SCIPwriteParams(subscip, name, TRUE, FALSE) );
2184 	      SCIPinfoMessage(mipdata->scip, NULL, "Wrote settings to file <%s>.\n", name);
2185 	   }
2186 	#endif
2187 	
2188 	   return SCIP_OKAY;
2189 	}
2190 	
2191 	
2192 	/** try to convert fractional gomory cuts to primal solutions of CG-MIP */
2193 	static
2194 	SCIP_RETCODE createCGMIPprimalsols(
2195 	   SCIP*                 scip,               /**< original SCIP data structure */
2196 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
2197 	   CGMIP_MIPDATA*        mipdata             /**< data for sub-MIP */
2198 	   )
2199 	{
2200 	   SCIP_VAR** vars;
2201 	   SCIP_ROW** rows;
2202 	   SCIP_COL** cols;
2203 	   SCIP_Real* binvrow;
2204 	   SCIP_Real* cutcoefs;
2205 	   int* basisind;
2206 	   int nvars;
2207 	   int nrows;
2208 	   int ncols;
2209 	   int ngen = 0;
2210 	   int ntried = 0;
2211 	   int i;
2212 	
2213 	   assert( scip != NULL );
2214 	   assert( sepadata != NULL );
2215 	   assert( mipdata != NULL );
2216 	
2217 	   /* get variables */
2218 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2219 	
2220 	   /* get rows and columns */
2221 	   SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
2222 	   SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2223 	   assert( ncols <= nvars );
2224 	
2225 	   /* get storage */
2226 	   SCIP_CALL( SCIPallocBufferArray(scip, &basisind, nrows) );
2227 	   SCIP_CALL( SCIPallocBufferArray(scip, &binvrow, nrows) );
2228 	   SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, ncols) );
2229 	
2230 	   /* get basis indices */
2231 	   SCIP_CALL( SCIPgetLPBasisInd(scip, basisind) );
2232 	
2233 	   /* loop through rows */
2234 	   for (i = 0; i < nrows; ++i)
2235 	   {
2236 	      SCIP_Bool tryrow = FALSE;
2237 	      SCIP_Real primsol = SCIP_INVALID;
2238 	      int c;
2239 	      int r;
2240 	
2241 	      c = basisind[i];
2242 	      assert( c < ncols );
2243 	
2244 	      if ( c >= 0 )
2245 	      {
2246 	         SCIP_VAR* var;
2247 	
2248 	         var = SCIPcolGetVar(cols[c]);
2249 	
2250 	         if ( SCIPvarGetType(var) != SCIP_VARTYPE_CONTINUOUS )
2251 	         {
2252 	            primsol = SCIPcolGetPrimsol(cols[c]);
2253 	            assert( SCIPgetVarSol(scip, var) == primsol ); /*lint !e777*/
2254 	
2255 	            if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY )
2256 	               tryrow = TRUE;
2257 	         }
2258 	      }
2259 	#if ( SEPARATEROWS == TRUE )
2260 	      else
2261 	      {
2262 	         SCIP_ROW* row;
2263 	
2264 	         assert(0 <= -c-1 && -c-1 < nrows);
2265 	
2266 	         row = rows[-c-1];
2267 	
2268 	         if ( SCIProwIsIntegral(row) && ! SCIProwIsModifiable(row) )
2269 	         {
2270 	            /* Compute value of the slack variable (we only care about the correct fractionality) */
2271 	            if ( SCIPisInfinity(scip, SCIProwGetRhs(row)) )
2272 	               primsol = SCIProwGetLhs(row) - SCIPgetRowLPActivity(scip, row);
2273 	            else
2274 	               primsol = SCIProwGetRhs(row) - SCIPgetRowLPActivity(scip, row);
2275 	
2276 	            if ( SCIPfeasFrac(scip, primsol) >= AWAY && SCIPfeasFrac(scip, primsol) <= 1 - AWAY )
2277 	               tryrow = TRUE;
2278 	         }
2279 	      }
2280 	#endif
2281 	
2282 	      if ( tryrow )
2283 	      {
2284 	         SCIP_Bool success;
2285 	         SCIP_SOL* sol;
2286 	         SCIP_Real cutrhs = 0.0;
2287 	         SCIP_ROW* row;
2288 	         SCIP_Real val;
2289 	         int j;
2290 	
2291 	         assert( primsol != SCIP_INVALID );  /*lint !e777*/
2292 	
2293 	         /* get the row of B^-1 for this basic integer variable with fractional solution value */
2294 	         SCIP_CALL( SCIPgetLPBInvRow(scip, i, binvrow, NULL, NULL) );
2295 	
2296 	         /* clear cutcoefs */
2297 	         BMSclearMemoryArray(cutcoefs, ncols);
2298 	
2299 	         /* create solution */
2300 	         SCIP_CALL( SCIPcreateSol(mipdata->subscip, &sol, NULL) );
2301 	
2302 	         /* add values of multipliers to solution and compute coefficients */
2303 	         for (r = 0; r < nrows; ++r)
2304 	         {
2305 	            SCIP_COL** rowcols;
2306 	            SCIP_Real* rowvals;
2307 	            SCIP_Real binvval;
2308 	            SCIP_Real weight;
2309 	
2310 	            row = rows[r];
2311 	            assert( row != NULL );
2312 	
2313 	            binvval = binvrow[r];
2314 	            binvval = SCIPfrac(scip, binvval);  /* can always take fractional value */
2315 	            if ( ! SCIPisFeasZero(scip, binvval) )
2316 	            {
2317 	               SCIP_Real lhs;
2318 	               SCIP_Real rhs;
2319 	               SCIP_Bool uselhs;
2320 	
2321 	               lhs = SCIProwGetLhs(row);
2322 	               rhs = SCIProwGetRhs(row);
2323 	
2324 	               if ( ! SCIPisEQ(scip, lhs, rhs) )
2325 	               {
2326 	                  SCIP_BASESTAT stat;
2327 	
2328 	                  stat = SCIProwGetBasisStatus(row);
2329 	
2330 	                  if ( stat == SCIP_BASESTAT_LOWER )
2331 	                  {
2332 	                     assert( ! SCIPisInfinity(scip, -lhs) );
2333 	                     uselhs = TRUE;
2334 	                  }
2335 	                  else if ( stat == SCIP_BASESTAT_UPPER )
2336 	                  {
2337 	                     assert( ! SCIPisInfinity(scip, rhs) );
2338 	                     uselhs = FALSE;
2339 	                  }
2340 	                  else if ( SCIPisInfinity(scip, rhs) )
2341 	                     uselhs = TRUE;
2342 	                  else
2343 	                     uselhs = FALSE;
2344 	               }
2345 	               else if ( binvval < 0.0 )
2346 	                  uselhs = TRUE;
2347 	               else
2348 	                  uselhs = FALSE;
2349 	
2350 	               if ( uselhs )
2351 	               {
2352 	                  assert( mipdata->ylhs[r] != NULL );
2353 	                  SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->ylhs[r], fabs(binvval)) );
2354 	                  weight = -fabs(binvval);
2355 	               }
2356 	               else
2357 	               {
2358 	                  assert( mipdata->yrhs[r] != NULL );
2359 	                  SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->yrhs[r], fabs(binvval)) );
2360 	                  weight = fabs(binvval);
2361 	               }
2362 	
2363 	               /* update cut coefficients */
2364 	               rowcols = SCIProwGetCols(row);
2365 	               rowvals = SCIProwGetVals(row);
2366 	
2367 	               /* add the row coefficients to the sum */
2368 	               for (j = 0; j < SCIProwGetNLPNonz(row); ++j)
2369 	               {
2370 	                  int idx;
2371 	
2372 	                  assert( rowcols[j] != NULL );
2373 	
2374 	                  idx = SCIPcolGetLPPos(rowcols[j]);
2375 	                  assert( 0 <= idx && idx < ncols );
2376 	
2377 	                  cutcoefs[idx] += weight * rowvals[j];
2378 	               }
2379 	
2380 	               /* compute rhs */
2381 	               if ( uselhs )
2382 	               {
2383 	                  assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
2384 	                  val = mipdata->lhs[r];
2385 	               }
2386 	               else
2387 	               {
2388 	                  assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
2389 	                  val = mipdata->rhs[r];
2390 	               }
2391 	               cutrhs += weight * val;
2392 	            }
2393 	         }
2394 	
2395 	         /* fill in values of cut */
2396 	         for (c = 0; c < ncols; ++c)
2397 	         {
2398 	            if ( mipdata->coltype[c] != colPresent )
2399 	               continue;
2400 	
2401 	            val = SCIPfloor(scip, cutcoefs[c]);
2402 	            if ( mipdata->iscomplemented[c] )
2403 	               val = -val;
2404 	            if ( ! SCIPisFeasZero(scip, val) )
2405 	            {
2406 	               SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->alpha[c], val) );
2407 	            }
2408 	            val = SCIPfeasFrac(scip, cutcoefs[c]);
2409 	            if ( ! SCIPisFeasZero(scip, val) )
2410 	            {
2411 	               SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracalpha[c], val) );
2412 	            }
2413 	         }
2414 	
2415 	         if ( ! SCIPisFeasZero(scip, SCIPfloor(scip, cutrhs)) )
2416 	         {
2417 	            SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->beta, SCIPfloor(scip, cutrhs)) );
2418 	         }
2419 	         if ( ! SCIPisFeasZero(scip, SCIPfeasFrac(scip, cutrhs)) )
2420 	         {
2421 	            SCIP_CALL( SCIPsetSolVal(mipdata->subscip, sol, mipdata->fracbeta, SCIPfeasFrac(scip, cutrhs)) );
2422 	         }
2423 	
2424 	         SCIP_CALL( SCIPtrySolFree(mipdata->subscip, &sol, FALSE, FALSE, TRUE, TRUE, TRUE, &success) );
2425 	         ++ntried;
2426 	         if ( success )
2427 	            ++ngen;
2428 	      }
2429 	   }
2430 	
2431 	   SCIPfreeBufferArray(scip, &cutcoefs);
2432 	   SCIPfreeBufferArray(scip, &binvrow);
2433 	   SCIPfreeBufferArray(scip, &basisind);
2434 	
2435 	   SCIPdebugMsg(scip, "Created %d primal solutions for CG-MIP from tableau cuts (tried: %d).\n", ngen, ntried);
2436 	
2437 	   return SCIP_OKAY;
2438 	}
2439 	
2440 	
2441 	/** solve subscip */
2442 	static
2443 	SCIP_RETCODE solveSubscip(
2444 	   SCIP*                 origscip,           /**< SCIP data structure */
2445 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
2446 	   CGMIP_MIPDATA*        mipdata,            /**< data for sub-MIP */
2447 	   SCIP_Bool*            success             /**< if setting was successful -> stop */
2448 	   )
2449 	{
2450 	   SCIP* subscip;
2451 	   SCIP_RETCODE retcode;
2452 	   SCIP_STATUS status;
2453 	   SCIP_Real timelimit;
2454 	   SCIP_Real memorylimit;
2455 	   SCIP_Longint nodelimit;
2456 	
2457 	   assert( origscip != NULL );
2458 	   assert( sepadata != NULL );
2459 	   assert( mipdata != NULL );
2460 	   assert( success != NULL );
2461 	
2462 	   *success = TRUE;
2463 	
2464 	   subscip = mipdata->subscip;
2465 	
2466 	   SCIP_CALL( SCIPcheckCopyLimits(origscip, success) );
2467 	
2468 	   if ( ! (*success) )
2469 	      return SCIP_OKAY;
2470 	
2471 	   /* @todo Check whether copying the parameters is useful */
2472 	   /* SCIP_CALL( SCIPcopyLimits(origscip, subscip) ); */
2473 	
2474 	   /* determine time limit */
2475 	   SCIP_CALL( SCIPgetRealParam(origscip, "limits/time", &timelimit) );
2476 	   if ( sepadata->timelimit < timelimit )
2477 	      timelimit = sepadata->timelimit;
2478 	
2479 	   if ( ! SCIPisInfinity(origscip, timelimit) )
2480 	   {
2481 	      timelimit -= SCIPgetSolvingTime(origscip);
2482 	      if ( timelimit > 0.0 )
2483 	      {
2484 	         SCIP_CALL( SCIPsetRealParam(subscip, "limits/time", timelimit) );
2485 	      }
2486 	      else
2487 	      {
2488 	         SCIPdebugMsg(origscip, "Reached timelimit.\n");
2489 	         *success = FALSE;
2490 	         return SCIP_OKAY;
2491 	      }
2492 	   }
2493 	
2494 	   /* determine memory limit */
2495 	   SCIP_CALL( SCIPgetRealParam(origscip, "limits/memory", &memorylimit) );
2496 	   if ( sepadata->memorylimit < memorylimit )
2497 	      memorylimit = sepadata->memorylimit;
2498 	
2499 	   if ( ! SCIPisInfinity(origscip, memorylimit) )
2500 	   {
2501 	      /* substract the memory already used by the main SCIP and the estimated memory usage of external software */
2502 	      memorylimit -= SCIPgetMemUsed(origscip)/1048576.0;
2503 	      memorylimit -= SCIPgetMemExternEstim(origscip)/1048576.0;
2504 	      if ( memorylimit > 0.0 )
2505 	      {
2506 	         SCIP_CALL( SCIPsetRealParam(subscip, "limits/memory", memorylimit) );
2507 	      }
2508 	      else
2509 	      {
2510 	         SCIPdebugMsg(origscip, "Reached memorylimit.\n");
2511 	         *success = TRUE;
2512 	         return SCIP_OKAY;
2513 	      }
2514 	   }
2515 	
2516 	   /* set node limit for subproblem */
2517 	   if ( sepadata->minnodelimit < 0 || sepadata->maxnodelimit < 0 )
2518 	      nodelimit = SCIP_LONGINT_MAX;
2519 	   else
2520 	   {
2521 	      assert( sepadata->minnodelimit >= 0 && sepadata->maxnodelimit >= 0 );
2522 	      nodelimit = SCIPgetNLPIterations(origscip);
2523 	      nodelimit = MAX(sepadata->minnodelimit, nodelimit);
2524 	      nodelimit = MIN(sepadata->maxnodelimit, nodelimit);
2525 	   }
2526 	   assert( nodelimit >= 0 );
2527 	   SCIP_CALL( SCIPsetLongintParam(subscip, "limits/nodes", nodelimit) );
2528 	
2529 	   /* try to create primal solutions of CG-MIP problem via tableau cuts */
2530 	   if ( sepadata->genprimalsols )
2531 	   {
2532 	      SCIP_CALL( SCIPtransformProb(subscip) );
2533 	      SCIP_CALL( createCGMIPprimalsols(origscip, sepadata, mipdata) );
2534 	   }
2535 	
2536 	   SCIPdebugMsg(origscip, "Solving sub-SCIP (time limit: %f  mem limit: %f  node limit: %" SCIP_LONGINT_FORMAT ") ...\n", timelimit, memorylimit, nodelimit);
2537 	
2538 	   /* disable statistic timing inside sub SCIP */
2539 	   if ( ! sepadata->output )
2540 	   {
2541 	      SCIP_CALL( SCIPsetBoolParam(subscip, "timing/statistictiming", FALSE) );
2542 	   }
2543 	
2544 	   /* check whether we want a complete solve */
2545 	   if ( ! sepadata->earlyterm )
2546 	   {
2547 	      retcode = SCIPsolve(subscip);
2548 	      SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n",
2549 	         SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit);
2550 	
2551 	      /* errors in solving the subproblem should not kill the overall solving process;
2552 	       * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2553 	      if ( retcode != SCIP_OKAY )
2554 	      {
2555 	#ifndef NDEBUG
2556 	         SCIP_CALL( retcode );
2557 	#endif
2558 	         SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2559 	         *success = FALSE;
2560 	         return SCIP_OKAY;
2561 	      }
2562 	
2563 	      status = SCIPgetStatus(subscip);
2564 	
2565 	#ifdef SCIP_OUTPUT
2566 	      SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2567 	#else
2568 	      if ( sepadata->output )
2569 	      {
2570 	         SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2571 	      }
2572 	#endif
2573 	
2574 	      /* if the problem is infeasible (can happen because of violation constraint) */
2575 	      if ( status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD )
2576 	      {
2577 	         SCIPdebugMsg(origscip, "CG-MIP separation problem infeasible.\n");
2578 	         *success = FALSE;
2579 	         return SCIP_OKAY;
2580 	      }
2581 	
2582 	      /* if the solution ran into the time limit */
2583 	      if ( status == SCIP_STATUS_TIMELIMIT )
2584 	      {
2585 	         SCIPdebugMsg(origscip, "CG-MIP separation problem ran into time limit.\n");
2586 	         *success = FALSE;
2587 	         return SCIP_OKAY;
2588 	      }
2589 	
2590 	      /* if the solution process was terminated */
2591 	      if ( status == SCIP_STATUS_USERINTERRUPT )
2592 	      {
2593 	         SCIPdebugMsg(origscip, "CG-MIP separation problem stopped by user interrupt.\n");
2594 	         *success = FALSE;
2595 	         return SCIP_OKAY;
2596 	      }
2597 	
2598 	      /* all other statuses except optimal or node limit are invalid */
2599 	      if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_NODELIMIT )
2600 	      {
2601 	         SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2602 	         return SCIP_ERROR;
2603 	      }
2604 	   }
2605 	   else
2606 	   {
2607 	      /* otherwise we want a heuristic solve */
2608 	
2609 	      /* -> solve until first solution is found */
2610 	      SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", 1) );
2611 	      retcode = SCIPsolve(subscip);
2612 	      SCIP_CALL( SCIPsetIntParam(subscip, "limits/bestsol", -1) );
2613 	
2614 	      /* errors in solving the subproblem should not kill the overall solving process;
2615 	       * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2616 	      if ( retcode != SCIP_OKAY )
2617 	      {
2618 	#ifndef NDEBUG
2619 	         SCIP_CALL( retcode );
2620 	#endif
2621 	         SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2622 	         *success = FALSE;
2623 	         return SCIP_OKAY;
2624 	      }
2625 	
2626 	      status = SCIPgetStatus(subscip);
2627 	
2628 	      /* if the solution process was terminated or the problem is infeasible (can happen because of violation constraint) */
2629 	      if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_NODELIMIT ||
2630 	           status == SCIP_STATUS_INFEASIBLE || status == SCIP_STATUS_INFORUNBD || status == SCIP_STATUS_MEMLIMIT )
2631 	      {
2632 	         /* output statistics before stopping */
2633 	#ifdef SCIP_OUTPUT
2634 	         SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2635 	#else
2636 	         if ( sepadata->output )
2637 	         {
2638 	            SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2639 	         }
2640 	#endif
2641 	         *success = FALSE;
2642 	         return SCIP_OKAY;
2643 	      }
2644 	
2645 	      /* all other statuses except optimal or bestsollimit are invalid - (problem cannot be infeasible) */
2646 	      if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_BESTSOLLIMIT )
2647 	      {
2648 	         SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2649 	         return SCIP_ERROR;
2650 	      }
2651 	
2652 	      /* solve some more, if a feasible solution was found */
2653 	      if ( status == SCIP_STATUS_BESTSOLLIMIT )
2654 	      {
2655 	         SCIPdebugMsg(origscip, "Continue solving separation problem (current time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ") ...\n",
2656 	            SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip));
2657 	
2658 	         SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", STALLNODELIMIT) );
2659 	         retcode = SCIPsolve(subscip);
2660 	         SCIP_CALL( SCIPsetLongintParam(subscip, "limits/stallnodes", -1LL) );
2661 	
2662 	         SCIPdebugMsg(origscip, "Finished solving CG-MIP (dualbound: %g, solving time: %.2f, nodes: %" SCIP_LONGINT_FORMAT ", nodelimit: %" SCIP_LONGINT_FORMAT").\n",
2663 	            SCIPgetDualbound(subscip), SCIPgetSolvingTime(subscip), SCIPgetNNodes(subscip), nodelimit);
2664 	
2665 	         /* errors in solving the subproblem should not kill the overall solving process;
2666 	          * hence, the return code is caught and a warning is printed, only in debug mode, SCIP will stop. */
2667 	         if ( retcode != SCIP_OKAY )
2668 	         {
2669 	#ifndef NDEBUG
2670 	            SCIP_CALL( retcode );
2671 	#endif
2672 	            SCIPwarningMessage(origscip, "Error while solving subproblem in CGMIP separator; sub-SCIP terminated with code <%d>\n", retcode);
2673 	            *success = FALSE;
2674 	            return SCIP_OKAY;
2675 	         }
2676 	
2677 	         status = SCIPgetStatus(subscip);
2678 	         assert( status != SCIP_STATUS_BESTSOLLIMIT );
2679 	
2680 	#ifdef SCIP_OUTPUT
2681 	         SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2682 	#else
2683 	         if ( sepadata->output )
2684 	         {
2685 	            SCIP_CALL( SCIPprintStatistics(subscip, NULL) );
2686 	         }
2687 	#endif
2688 	
2689 	         /* if the solution process was terminated */
2690 	         if ( status == SCIP_STATUS_TIMELIMIT || status == SCIP_STATUS_USERINTERRUPT || status == SCIP_STATUS_MEMLIMIT )
2691 	         {
2692 	            *success = FALSE;
2693 	            return SCIP_OKAY;
2694 	         }
2695 	
2696 	         /* all other statuses except optimal or bestsollimit are invalid */
2697 	         if ( status != SCIP_STATUS_OPTIMAL && status != SCIP_STATUS_STALLNODELIMIT && status != SCIP_STATUS_NODELIMIT )
2698 	         {
2699 	            SCIPerrorMessage("Solution of subscip for CG-separation returned with invalid status %d.\n", status);
2700 	            return SCIP_ERROR;
2701 	         }
2702 	      }
2703 	   }
2704 	
2705 	   return SCIP_OKAY;
2706 	}
2707 	
2708 	/** Computes cut from the given multipliers
2709 	 *
2710 	 *  When computing the cut, we take the fractional part of the multipliers. This is known to produce stronger cuts in
2711 	 *  the pure integer case, since the cut is the sum of the one using fractional parts and integer multiples of the
2712 	 *  original constraints. However, if there are continuous variables, the resulting cut might not be valid. This is
2713 	 *  checked and returned.
2714 	 *
2715 	 *  Moreover, the cut computed here in general will not be the same as the one computed with the
2716 	 *  sub-MIP, because of numerical differences. Here, we only combine rows whose corresponding
2717 	 *  multiplier is positive w.r.t. the feasibility tolerance. In the sub-MIP, however, the rows are
2718 	 *  combined in any case. This makes a difference, if the coefficients in the matrix are large and
2719 	 *  hence yield a value that is larger than the tolerance.
2720 	 *
2721 	 *  Because of the transformations we have the following:
2722 	 *
2723 	 *  If variable \f$x_j\f$ was complemented, we have \f$x'_j = u_j - x_j\f$. If in the transformed
2724 	 *  system the lower bound is used, its corresponding multiplier is \f$y^T A'_j - \lfloor y^T A'_j
2725 	 *  \rfloor\f$, which corresponds to
2726 	 *  \f[
2727 	 *      y^T A'_j - \lfloor y^T A'_j \rfloor = - y^T A_j - \lfloor - y^T A_j \rfloor = - y^T A_j + \lceil y^T A_j \rceil
2728 	 *  \f]
2729 	 *  in the original system.
2730 	 *
2731 	 *  If such a variable was at its upper bound before the transformation, it is at its lower bound
2732 	 *  afterwards. Hence, its contribution to the cut is 0.
2733 	 *
2734 	 *  Note that if the original LP-solution does not satisfy some of the rows with equality, the
2735 	 *  violation of the cut might be smaller than what is computed with the reduced sub-MIP.
2736 	 *
2737 	 *  Furthermore, note that if continuous variables have been shifted, the computed violation may be
2738 	 *  different as well, because the necessary changes in the lhs/rhs are not used here anymore.
2739 	 *
2740 	 *  @todo Check if cut is correct if continuous variables have been shifted.
2741 	 */
2742 	static
2743 	SCIP_RETCODE computeCut(
2744 	   SCIP*                 scip,               /**< original scip */
2745 	   SCIP_SEPA*            sepa,               /**< separator */
2746 	   CGMIP_MIPDATA*        mipdata,            /**< data for sub-MIP */
2747 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
2748 	   SCIP_SOL*             sol,                /**< current solution for sub-MIP */
2749 	   SCIP_Bool             usefrac,            /**< use fractional value of multipliers */
2750 	   SCIP_Real*            cutcoefs,           /**< coefficients of the cut */
2751 	   SCIP_Real*            cutrhs,             /**< rhs of the cut */
2752 	   SCIP_Bool*            localrowsused,      /**< pointer to store whether local rows were used in summation */
2753 	   SCIP_Bool*            localboundsused,    /**< pointer to store whether local bounds were used in summation */
2754 	   int*                  cutrank,            /**< pointer to store the cut rank */
2755 	   SCIP_Bool*            success             /**< whether we produced a valid cut */
2756 	   )
2757 	{
2758 	   SCIP* subscip;
2759 	   SCIP_VAR** vars;
2760 	   SCIP_ROW** rows;
2761 	   SCIP_COL** cols;
2762 	   SCIP_Real val;
2763 	   SCIP_Real maxabsweight;
2764 	   int nvars;
2765 	   int ncols;
2766 	   int nrows;
2767 	   int i;
2768 	   int j;
2769 	
2770 	   assert( scip != NULL );
2771 	   assert( mipdata != NULL );
2772 	   assert( sepadata != NULL );
2773 	   assert( cutcoefs != NULL );
2774 	   assert( cutrhs != NULL );
2775 	   assert( localrowsused != NULL );
2776 	   assert( localboundsused != NULL );
2777 	   assert( cutrank != NULL );
2778 	   assert( success != NULL );
2779 	
2780 	   /* initialize */
2781 	   *localrowsused = FALSE;
2782 	   *localboundsused = FALSE;
2783 	   *cutrank = 0;
2784 	   *success = TRUE;
2785 	
2786 	   subscip = mipdata->subscip;
2787 	   assert( subscip != NULL );
2788 	
2789 	   /* get data */
2790 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2791 	   SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
2792 	   SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
2793 	   assert( nrows == (int) mipdata->nrows );
2794 	   assert( ncols == (int) mipdata->ncols );
2795 	
2796 	   BMSclearMemoryArray(cutcoefs, nvars);
2797 	   *cutrhs = 0.0;
2798 	
2799 	   /* find maximal absolute weight */
2800 	   maxabsweight = 0.0;
2801 	   for (i = 0; i < nrows; ++i)
2802 	   {
2803 	      SCIP_ROW* row;
2804 	      SCIP_Real absweight = 0.0;
2805 	
2806 	      row = rows[i];
2807 	      assert( row != NULL );
2808 	
2809 	      /* skip modifiable rows and local rows, unless allowed */
2810 	      if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && !sepadata->allowlocal) )
2811 	      {
2812 	         assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
2813 	         continue;
2814 	      }
2815 	
2816 	      /* get weight from solution (take larger of the values of lhs/rhs) */
2817 	      if ( mipdata->ylhs[i] != NULL )
2818 	      {
2819 	         val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]);
2820 	
2821 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2822 	         if ( usefrac )
2823 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
2824 	
2825 	         if ( SCIPisFeasPositive(scip, val) )
2826 	            absweight = val;
2827 	
2828 	         assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa );
2829 	      }
2830 	      if ( mipdata->yrhs[i] != NULL )
2831 	      {
2832 	         val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]);
2833 	
2834 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2835 	         if ( usefrac )
2836 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
2837 	
2838 	         /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2839 	         if ( SCIPisFeasGT(scip, val, absweight) )
2840 	            absweight = val;
2841 	
2842 	         assert( ! sepadata->onlyrankone || SCIProwGetOriginSepa(row) != sepa );
2843 	      }
2844 	      assert( ! SCIPisNegative(scip, absweight) );
2845 	
2846 	      if ( absweight > maxabsweight )
2847 	         maxabsweight = absweight;
2848 	   }
2849 	
2850 	   /* get weight from objective cuts */
2851 	   if ( sepadata->useobjub || sepadata->useobjlb )
2852 	   {
2853 	      SCIP_Real absweight = 0.0;
2854 	
2855 	      assert( mipdata->ntotalrows == mipdata->nrows + 1 );
2856 	
2857 	      if ( mipdata->ylhs[mipdata->nrows] != NULL )
2858 	      {
2859 	         val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
2860 	         if ( usefrac )
2861 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
2862 	
2863 	         if ( SCIPisFeasPositive(scip, val) )
2864 	            absweight = val;
2865 	      }
2866 	      if ( mipdata->yrhs[mipdata->nrows] != NULL )
2867 	      {
2868 	         val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
2869 	         if ( usefrac )
2870 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
2871 	
2872 	         /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2873 	         if ( SCIPisFeasGT(scip, val, absweight) )
2874 	            absweight = val;
2875 	      }
2876 	
2877 	      if ( absweight > maxabsweight )
2878 	         maxabsweight = absweight;
2879 	   }
2880 	
2881 	   /* calculate the row summation */
2882 	   for (i = 0; i < nrows; ++i)
2883 	   {
2884 	      SCIP_ROW* row;
2885 	      SCIP_Real weight;
2886 	      SCIP_Real absweight;
2887 	      SCIP_Bool uselhs;
2888 	
2889 	      row = rows[i];
2890 	      assert( row != NULL );
2891 	
2892 	      /* skip modifiable rows and local rows, unless allowed */
2893 	      if ( SCIProwIsModifiable(row) || (SCIProwIsLocal(row) && ! sepadata->allowlocal) )
2894 	      {
2895 	         assert( mipdata->ylhs[i] == NULL && mipdata->yrhs[i] == NULL );
2896 	         continue;
2897 	      }
2898 	
2899 	      /* get weight from solution */
2900 	      weight = 0.0;
2901 	      uselhs = FALSE;
2902 	      if ( mipdata->ylhs[i] != NULL )
2903 	      {
2904 	         val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[i]);
2905 	         assert( ! SCIPisFeasNegative(subscip, val) );
2906 	
2907 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2908 	         if ( usefrac )
2909 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
2910 	
2911 	         if ( SCIPisFeasPositive(scip, val) )
2912 	         {
2913 	            uselhs = TRUE;
2914 	            weight = -val;
2915 	         }
2916 	      }
2917 	      if ( mipdata->yrhs[i] != NULL )
2918 	      {
2919 	         val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[i]);
2920 	         assert( ! SCIPisFeasNegative(subscip, val) );
2921 	
2922 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
2923 	         if ( usefrac )
2924 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
2925 	
2926 	         /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
2927 	         if ( SCIPisFeasGT(scip, val, REALABS(weight)) )
2928 	         {
2929 	            uselhs = FALSE;
2930 	            weight = val;
2931 	         }
2932 	      }
2933 	
2934 	      /* add row if weight is nonzero and lies within range */
2935 	      absweight = REALABS(weight);
2936 	      if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight )
2937 	      {
2938 	         SCIP_COL** rowcols;
2939 	         SCIP_Real* rowvals;
2940 	
2941 	         rowcols = SCIProwGetCols(row);
2942 	         rowvals = SCIProwGetVals(row);
2943 	
2944 	         /* add the row coefficients to the sum */
2945 	         for (j = 0; j < SCIProwGetNLPNonz(row); ++j)
2946 	         {
2947 	            SCIP_VAR* var;
2948 	            int idx;
2949 	
2950 	            assert( rowcols[j] != NULL );
2951 	            var = SCIPcolGetVar(rowcols[j]);
2952 	
2953 	            assert( var != NULL );
2954 	            assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
2955 	            assert( SCIPvarGetCol(var) == rowcols[j] );
2956 	
2957 	            idx = SCIPvarGetProbindex(var);
2958 	            assert( 0 <= idx && idx < nvars );
2959 	
2960 	            cutcoefs[idx] += weight * rowvals[j];
2961 	         }
2962 	
2963 	         /* compute rhs */
2964 	         if ( uselhs )
2965 	         {
2966 	            assert( ! SCIPisInfinity(scip, -SCIProwGetLhs(row)) );
2967 	            val = SCIProwGetLhs(row) - SCIProwGetConstant(row);
2968 	            if ( SCIProwIsIntegral(row) )
2969 	               val = SCIPfeasCeil(scip, val); /* row is integral: round left hand side up */
2970 	         }
2971 	         else
2972 	         {
2973 	            assert( ! SCIPisInfinity(scip, SCIProwGetRhs(row)) );
2974 	            val = SCIProwGetRhs(row) - SCIProwGetConstant(row);
2975 	            if ( SCIProwIsIntegral(row) )
2976 	               val = SCIPfeasFloor(scip, val); /* row is integral: round right hand side down */
2977 	         }
2978 	         *cutrhs += weight * val;
2979 	
2980 	         *localrowsused = *localrowsused || SCIProwIsLocal(row);
2981 	
2982 	         if ( SCIProwGetRank(row) > *cutrank )
2983 	            *cutrank = SCIProwGetRank(row);
2984 	      }
2985 	   }
2986 	   /* add 1 to cutrank */
2987 	   ++(*cutrank);
2988 	
2989 	   /* get weight from objective bounds */
2990 	   if ( sepadata->useobjub || sepadata->useobjlb )
2991 	   {
2992 	      SCIP_Real weight = 0.0;
2993 	      SCIP_Bool uselhs = FALSE;
2994 	      SCIP_Real absweight;
2995 	
2996 	      assert( mipdata->ntotalrows == mipdata->nrows + 1 );
2997 	
2998 	      if ( mipdata->ylhs[mipdata->nrows] != NULL )
2999 	      {
3000 	         val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[mipdata->nrows]);
3001 	         assert( ! SCIPisFeasNegative(subscip, val) );
3002 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3003 	         if ( usefrac )
3004 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
3005 	
3006 	         if ( SCIPisFeasPositive(scip, val) )
3007 	         {
3008 	            uselhs = TRUE;
3009 	            weight = -val;
3010 	         }
3011 	      }
3012 	      if ( mipdata->yrhs[mipdata->nrows] != NULL )
3013 	      {
3014 	         val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[mipdata->nrows]);
3015 	         assert( ! SCIPisFeasNegative(subscip, val) );
3016 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3017 	         if ( usefrac )
3018 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
3019 	
3020 	         /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3021 	         if ( SCIPisFeasGT(scip, val, REALABS(weight)) )
3022 	         {
3023 	            uselhs = FALSE;
3024 	            weight = val;
3025 	         }
3026 	      }
3027 	
3028 	      /* add objective row if weight is nonzero and lies within range */
3029 	      absweight = REALABS(weight);
3030 	      if ( ! SCIPisSumZero(scip, weight) && absweight * MAXWEIGHTRANGE >= maxabsweight )
3031 	      {
3032 	         SCIP_Real obj = 0.0;
3033 	         int idx;
3034 	
3035 	         /* add the objective row coefficients to the sum */
3036 	         for (j = 0; j < ncols; ++j)
3037 	         {
3038 	            assert( cols[j] != NULL );
3039 	
3040 	            obj = SCIPcolGetObj(cols[j]);
3041 	            if ( ! SCIPisZero(scip, obj) )
3042 	            {
3043 	               idx = SCIPvarGetProbindex( SCIPcolGetVar(cols[j]) );
3044 	               assert( 0 <= idx && idx < nvars );
3045 	               cutcoefs[idx] += weight * obj;
3046 	            }
3047 	         }
3048 	
3049 	         /* compute rhs */
3050 	         if ( uselhs )
3051 	         {
3052 	            val = SCIPgetLowerbound(scip);
3053 	            assert( ! SCIPisInfinity(scip, -val) );
3054 	            if ( SCIPisObjIntegral(scip) )
3055 	               val = SCIPfeasCeil(scip, val); /* objective is integral: round left hand side up */
3056 	         }
3057 	         else
3058 	         {
3059 	            val = SCIPgetUpperbound(scip);
3060 	            assert( ! SCIPisInfinity(scip, val) );
3061 	            if ( SCIPisObjIntegral(scip) )
3062 	               val = SCIPfeasFloor(scip, val); /* objective is integral: round right hand side down */
3063 	         }
3064 	         *cutrhs += weight * val;
3065 	      }
3066 	   }
3067 	
3068 	   /* add upper bounds */
3069 	   for (j = 0; j < ncols; ++j)
3070 	   {
3071 	      assert( cols[j] != NULL );
3072 	      if ( mipdata->z[j] != NULL )
3073 	      {
3074 	         assert( mipdata->coltype[j] == colPresent );
3075 	
3076 	         val = SCIPgetSolVal(subscip, sol, mipdata->z[j]);
3077 	         assert( ! SCIPisFeasNegative(subscip, val) );
3078 	
3079 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3080 	         if ( usefrac )
3081 	            val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
3082 	
3083 	         /* if a bound has been used */
3084 	         if ( SCIPisSumPositive(subscip, val) )
3085 	         {
3086 	            SCIP_VAR* var;
3087 	            int idx;
3088 	
3089 	            var = SCIPcolGetVar(cols[j]);
3090 	
3091 	            assert( var != NULL );
3092 	            assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3093 	            assert( SCIPvarIsIntegral(var) );
3094 	            assert( SCIPvarGetCol(var) == cols[j] );
3095 	
3096 	            idx = SCIPvarGetProbindex(var);
3097 	            assert( 0 <= idx && idx < nvars );
3098 	
3099 	            /* check whether variable is complemented */
3100 	            if ( mipdata->iscomplemented[j] )
3101 	            {
3102 	               SCIP_Real lbnd;
3103 	               lbnd = SCIPvarGetLbGlobal(var);
3104 	               assert( ! SCIPisInfinity(scip, -lbnd) );
3105 	               assert( SCIPisIntegral(scip, lbnd) );
3106 	               assert( SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPcolGetLb(cols[j])) );
3107 	
3108 	               /* variable should not be free */
3109 	               assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
3110 	
3111 	               /* if allowed, try to use stronger local bound */
3112 	               if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd )
3113 	               {
3114 	                  lbnd = SCIPvarGetLbLocal(var);
3115 	                  assert( SCIPisIntegral(scip, lbnd) );
3116 	                  *localboundsused = TRUE;
3117 	               }
3118 	
3119 	               cutcoefs[idx] -= val;
3120 	               *cutrhs -= lbnd * val;
3121 	            }
3122 	            else
3123 	            {
3124 	               SCIP_Real ubnd;
3125 	               ubnd = SCIPvarGetUbGlobal(var);
3126 	               assert( ! SCIPisInfinity(scip, ubnd) );
3127 	               assert( SCIPisIntegral(scip, ubnd) );
3128 	               assert( SCIPisEQ(scip, SCIPvarGetUbLocal(var), SCIPcolGetUb(cols[j])) );
3129 	
3130 	               /* if allowed, try to use stronger local bound */
3131 	               if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd )
3132 	               {
3133 	                  ubnd = SCIPvarGetUbLocal(var);
3134 	                  assert( SCIPisIntegral(scip, ubnd) );
3135 	                  *localboundsused = TRUE;
3136 	               }
3137 	
3138 	               cutcoefs[idx] += val;
3139 	               *cutrhs += ubnd * val;
3140 	            }
3141 	         }
3142 	      }
3143 	   }
3144 	
3145 	   /* check lower bounds for integral variables */
3146 	   for (j = 0; j < nvars; ++j)
3147 	   {
3148 	      SCIP_VAR* var;
3149 	      int pos;
3150 	
3151 	      var = vars[j];
3152 	      assert( var != NULL );
3153 	      pos = SCIPcolGetLPPos(SCIPvarGetCol(var));
3154 	
3155 	      /* a variable may have status COLUMN, but the corresponding column may not (yet) be in the LP */
3156 	      if ( pos >= 0 && mipdata->coltype[pos] != colContinuous && mipdata->coltype[pos] != colConverted )
3157 	      {
3158 	         assert( pos < ncols );
3159 	         assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3160 	         assert( SCIPvarIsIntegral(var) );
3161 	
3162 	         /* check whether variable is complemented */
3163 	         if ( mipdata->iscomplemented[pos] )
3164 	         {
3165 	            assert( ! mipdata->isshifted[pos] );
3166 	            /* if the variable is complemented, the multiplier for the upper bound arises from the
3167 	               lower bound multiplier for the transformed problem - because of the minus-sign in the
3168 	               transformation this yields a round-up operation. */
3169 	            val = SCIPfeasCeil(scip, cutcoefs[j]) - cutcoefs[j];
3170 	            assert( ! SCIPisFeasNegative(scip, val) );
3171 	
3172 	            /* only if variable needs to be rounded */
3173 	            if ( SCIPisSumPositive(scip, val) )
3174 	            {
3175 	               SCIP_Real ubnd;
3176 	               ubnd = SCIPvarGetUbGlobal(var);
3177 	               assert( ! SCIPisInfinity(scip, ubnd) );
3178 	               assert( SCIPisIntegral(scip, ubnd) );
3179 	
3180 	               /* variable should not be free */
3181 	               assert( ! SCIPisInfinity(scip, -SCIPvarGetLbGlobal(var)) || ! SCIPisInfinity(scip, ubnd) );
3182 	
3183 	               /* if allowed, try to use stronger local bound */
3184 	               if ( sepadata->allowlocal && SCIPvarGetUbLocal(var) + 0.5 < ubnd )
3185 	               {
3186 	                  ubnd = SCIPvarGetUbLocal(var);
3187 	                  assert( SCIPisIntegral(scip, ubnd) );
3188 	                  *localboundsused = TRUE;
3189 	               }
3190 	
3191 	               /* round cut coefficients, i.e., add val to cutcoefs[j] */
3192 	               cutcoefs[j] = SCIPfeasCeil(scip, cutcoefs[j]);
3193 	
3194 	               /* correct rhs */
3195 	               if ( ! SCIPisSumZero(scip, ubnd) )
3196 	                  *cutrhs += ubnd * val;
3197 	            }
3198 	         }
3199 	         else
3200 	         {
3201 	            /* compute multiplier for lower bound: */
3202 	            val = cutcoefs[j] - SCIPfeasFloor(scip, cutcoefs[j]);
3203 	            assert( ! SCIPisFeasNegative(scip, val) );
3204 	
3205 	            /* only if variable needs to be rounded */
3206 	            if ( SCIPisSumPositive(scip, val) )
3207 	            {
3208 	               SCIP_Real lbnd;
3209 	               lbnd = SCIPvarGetLbGlobal(var);
3210 	               assert( ! SCIPisInfinity(scip, -lbnd) );
3211 	               assert( SCIPisIntegral(scip, lbnd) );
3212 	
3213 	               /* variable should not be free */
3214 	               assert( ! SCIPisInfinity(scip, -lbnd) || ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) );
3215 	
3216 	               /* if allowed, try to use stronger local bound */
3217 	               if ( sepadata->allowlocal && SCIPvarGetLbLocal(var) - 0.5 > lbnd )
3218 	               {
3219 	                  lbnd = SCIPvarGetLbLocal(var);
3220 	                  assert( SCIPisIntegral(scip, lbnd) );
3221 	                  *localboundsused = TRUE;
3222 	               }
3223 	
3224 	               /* round cut coefficients, i.e., subtract val from cutcoefs[j] */
3225 	               cutcoefs[j] = SCIPfeasFloor(scip, cutcoefs[j]);
3226 	
3227 	               /* correct rhs */
3228 	               if ( ! SCIPisSumZero(scip, lbnd) )
3229 	                  *cutrhs -= lbnd * val;
3230 	            }
3231 	         }
3232 	      }
3233 	      else
3234 	      {
3235 	         /* force coefficients of all continuous variables or of variables not in the lp to zero */
3236 	         assert( pos == -1 || mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted );
3237 	
3238 	         /* check whether all coefficients for continuous or converted variables are nonnegative */
3239 	         if ( pos >= 0 )
3240 	         {
3241 	            if ( SCIPisFeasNegative(scip, cutcoefs[j]) )
3242 	            {
3243 	               *success = FALSE;
3244 	               break;
3245 	            }
3246 	         }
3247 	
3248 	         cutcoefs[j] = 0.0;
3249 	      }
3250 	   }
3251 	
3252 	   /* round rhs */
3253 	   *cutrhs = SCIPfeasFloor(scip, *cutrhs);
3254 	
3255 	   return SCIP_OKAY;
3256 	}
3257 	
3258 	/** Create CG-cut directly from solution of sub-MIP */
3259 	static
3260 	SCIP_RETCODE createCGCutDirect(
3261 	   SCIP*                 scip,               /**< SCIP data structure */
3262 	   SCIP_SEPA*            sepa,               /**< separator */
3263 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
3264 	   CGMIP_MIPDATA*        mipdata,            /**< data for sub-MIP */
3265 	   SCIP_SOL*             sol,                /**< solution of sub-MIP */
3266 	   SCIP_Real*            cutcoefs,           /**< cut coefficients */
3267 	   int*                  cutinds,            /**< problem indices of variables appearing in cut */
3268 	   SCIP_Real*            cutvals,            /**< values of variables in cut */
3269 	   SCIP_Real*            varsolvals,         /**< solution value of variables */
3270 	   SCIP_Real*            weights,            /**< weights to compute cmir cut */
3271 	   int*                  nprevrows,          /**< number of previously generated rows */
3272 	   SCIP_ROW**            prevrows,           /**< previously generated rows */
3273 	   SCIP_Bool*            cutoff,             /**< whether a cutoff has been detected */
3274 	   unsigned int*         ngen                /**< number of generated cuts */
3275 	   )
3276 	{
3277 	   char name[SCIP_MAXSTRLEN];
3278 	   SCIP_Bool cutislocal;
3279 	   SCIP_Bool localrowsused;
3280 	   SCIP_Bool localboundsused;
3281 	   SCIP_Real cutrhs;
3282 	   SCIP_Real cutact;
3283 	   SCIP_Bool success;
3284 	   SCIP_VAR** vars;
3285 	   int cutrank = 0;
3286 	   int nvars;
3287 	   int k;
3288 	
3289 	   assert( scip != NULL );
3290 	   assert( sepadata != NULL );
3291 	   assert( mipdata != NULL );
3292 	   assert( sol != NULL );
3293 	   assert( cutcoefs != NULL );
3294 	   assert( cutinds != NULL );
3295 	   assert( cutvals != NULL );
3296 	   assert( varsolvals != NULL );
3297 	   assert( weights != NULL );
3298 	   assert( nprevrows != NULL );
3299 	   assert( prevrows != NULL );
3300 	   assert( cutoff != NULL );
3301 	   assert( ngen != NULL );
3302 	
3303 	   /* get variable data */
3304 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3305 	
3306 	   cutrhs = 0.0;
3307 	   localrowsused = FALSE;
3308 	   localboundsused = FALSE;
3309 	   *cutoff = FALSE;
3310 	   success = TRUE;
3311 	
3312 	   /* compute coefficients */
3313 	   SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, TRUE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
3314 	   cutislocal = localrowsused || localboundsused;
3315 	
3316 	   /* Take next solution if cut was not valid - this can easily happen for mixed-integer problems, see function computeCut(). */
3317 	   if ( ! success )
3318 	   {
3319 	      /* try again without using fractional value */
3320 	      SCIP_CALL( computeCut(scip, sepa, mipdata, sepadata, sol, FALSE, cutcoefs, &cutrhs, &localrowsused, &localboundsused, &cutrank, &success) );
3321 	      cutislocal = localrowsused || localboundsused;
3322 	
3323 	      if ( ! success )
3324 	      {
3325 	         SCIPdebugMsg(scip, "cut not valid - skipping ...\n");
3326 	         return SCIP_OKAY;
3327 	      }
3328 	   }
3329 	
3330 	   /* compute activity */
3331 	   cutact = 0.0;
3332 	   for (k = 0; k < nvars; ++k)
3333 	      cutact += cutcoefs[k] * varsolvals[k];
3334 	
3335 	#ifdef SCIP_DISABLED_CODE
3336 	   /* the following test should be treated with care because of numerical differences - see computeCut() */
3337 	   {
3338 	      /* check for correctness of computed values */
3339 	      SCIP* subscip;
3340 	      SCIP_Real obj = 0.0;
3341 	      SCIP_Real val;
3342 	      SCIP_Bool contVarShifted = FALSE;
3343 	      unsigned int j;
3344 	      SCIP_COL** cols;
3345 	      int ncols;
3346 	
3347 	      subscip = mipdata->subscip;
3348 	      assert( subscip != NULL );
3349 	
3350 	      SCIP_CALL( SCIPprintSol(subscip, sol, NULL, FALSE) );
3351 	
3352 	      SCIP_CALL( SCIPgetLPColsData(scip, &cols, &ncols) );
3353 	      for (j = 0; j < mipdata->ncols; ++j)
3354 	      {
3355 	         if ( mipdata->coltype[j] == colPresent )
3356 	         {
3357 	            int idx;
3358 	            assert( mipdata->alpha[j] != NULL );
3359 	            val = SCIPgetSolVal(subscip, sol, mipdata->alpha[j]);
3360 	            assert( SCIPisFeasIntegral(subscip, val) );
3361 	            idx = SCIPvarGetProbindex(SCIPcolGetVar(cols[j]));
3362 	            assert( SCIPisFeasEQ(scip, val, cutcoefs[idx]) );
3363 	            obj += val * SCIPvarGetObj(mipdata->alpha[j]);
3364 	         }
3365 	         else
3366 	         {
3367 	            if ( (mipdata->coltype[j] == colContinuous || mipdata->coltype[j] == colConverted) && mipdata->isshifted[j] )
3368 	               contVarShifted = TRUE;
3369 	         }
3370 	      }
3371 	      assert( mipdata->beta != NULL );
3372 	      val = SCIPgetSolVal(subscip, sol, mipdata->beta);
3373 	      assert( SCIPisFeasIntegral(subscip, val) );
3374 	      obj += val * SCIPvarGetObj(mipdata->beta);
3375 	      assert( contVarShifted || SCIPisFeasEQ(scip, obj, cutact - cutrhs) );
3376 	   }
3377 	#endif
3378 	
3379 	   /* if successful, convert dense cut into sparse row, and add the row as a cut */
3380 	   if ( SCIPisFeasGT(scip, cutact, cutrhs) )
3381 	   {
3382 	      SCIP_Real cutnorm;
3383 	      int cutlen;
3384 	
3385 	      /* store the cut as sparse row, calculate activity and norm of cut */
3386 	      SCIP_CALL( storeCutInArrays(scip, nvars, cutcoefs, varsolvals, mipdata->normtype,
3387 	            cutinds, cutvals, &cutlen, &cutact, &cutnorm) );
3388 	
3389 	      SCIPdebugMsg(scip, "act=%f, rhs=%f, norm=%f, eff=%f\n", cutact, cutrhs, cutnorm, (cutact - cutrhs)/cutnorm);
3390 	
3391 	      /* if norm is 0, the cut is trivial */
3392 	      if ( SCIPisPositive(scip, cutnorm) )
3393 	      {
3394 	         SCIP_Bool violated = SCIPisEfficacious(scip, (cutact - cutrhs)/cutnorm);
3395 	
3396 	         if ( violated || (sepadata->usecutpool && ! cutislocal ) )
3397 	         {
3398 	            SCIP_ROW* cut;
3399 	
3400 	            /* create the cut */
3401 	            (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3402 	            SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3403 	            SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3404 	
3405 	            for (k = 0; k < cutlen; ++k)
3406 	            {
3407 	               SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutvals[k]) );
3408 	            }
3409 	
3410 	            /* set cut rank */
3411 	            SCIProwChgRank(cut, cutrank);
3412 	
3413 	            SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3414 	
3415 	            /*SCIPdebug( SCIP_CALL( SCIPprintRow(scip, cut, NULL) ) );*/
3416 	
3417 	            /* add cut to pool */
3418 	            if ( ! cutislocal )
3419 	            {
3420 	               assert( violated || sepadata->usecutpool );
3421 	               SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3422 	            }
3423 	
3424 	            /* add cut if it is violated */
3425 	            if ( violated )
3426 	            {
3427 	               /* check whether cut has been found before - may happened due to projection */
3428 	               for (k = 0; k < *nprevrows; ++k)
3429 	               {
3430 	                  SCIP_Real parval;
3431 	
3432 	                  assert( prevrows[k] != NULL );
3433 	                  parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3434 	                  /* exit if row is parallel to existing cut and rhs is not better */
3435 	                  if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3436 	                     break;
3437 	               }
3438 	
3439 	               /* if cut is new */
3440 	               if ( k >= *nprevrows )
3441 	               {
3442 	                  prevrows[*nprevrows] = cut;
3443 	                  ++(*nprevrows);
3444 	
3445 	                  SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, min=%f, max=%f (range=%f)\n",
3446 	                     name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3447 	                     SCIPgetCutEfficacy(scip, NULL, cut),
3448 	                     SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3449 	                     SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3450 	#ifdef SCIP_DEBUG
3451 	                  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3452 	#else
3453 	                  if ( sepadata->output )
3454 	                  {
3455 	                     SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3456 	                  }
3457 	#endif
3458 	                  SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3459 	                  ++(*ngen);
3460 	               }
3461 	               else
3462 	               {
3463 	                  SCIPdebugMsg(scip, "Cut already exists.\n");
3464 	                  /* release the row */
3465 	                  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3466 	               }
3467 	            }
3468 	            else
3469 	            {
3470 	               /* release the row */
3471 	               SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3472 	            }
3473 	         }
3474 	      }
3475 	   }
3476 	
3477 	   return SCIP_OKAY;
3478 	}
3479 	
3480 	
3481 	/** create CG-cut via CMIR-function */
3482 	static
3483 	SCIP_RETCODE createCGCutCMIR(
3484 	   SCIP*                 scip,               /**< SCIP data structure */
3485 	   SCIP_SEPA*            sepa,               /**< separator */
3486 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
3487 	   CGMIP_MIPDATA*        mipdata,            /**< data for sub-MIP */
3488 	   SCIP_SOL*             sol,                /**< solution of sub-MIP */
3489 	   SCIP_AGGRROW*         aggrrow,            /**< aggregation row to use for creating MIR cut */
3490 	   SCIP_Real*            cutcoefs,           /**< cut coefficients */
3491 	   int*                  cutinds,            /**< problem indices of variables appearing in cut */
3492 	   SCIP_Real*            cutvals,            /**< values of variables in cut */
3493 	   SCIP_Real*            varsolvals,         /**< solution value of variables */
3494 	   SCIP_Real*            weights,            /**< weights to compute cmir cut */
3495 	   int*                  boundsfortrans,     /**< bounds for cmir function of NULL */
3496 	   SCIP_BOUNDTYPE*       boundtypesfortrans, /**< type of bounds for cmir function or NULL */
3497 	   int*                  nprevrows,          /**< number of previously generated rows */
3498 	   SCIP_ROW**            prevrows,           /**< previously generated rows */
3499 	   SCIP_Bool*            cutoff,             /**< whether a cutoff has been detected */
3500 	   unsigned int*         ngen                /**< number of generated cuts */
3501 	   )
3502 	{
3503 	   char name[SCIP_MAXSTRLEN];
3504 	   SCIP_Longint maxdnom;
3505 	   SCIP_Bool cutislocal;
3506 	   SCIP_Real maxscale;
3507 	   SCIP_Real cutrhs;
3508 	   SCIP_Real cutefficacy;
3509 	   SCIP_Bool success;
3510 	   SCIP_ROW** rows;
3511 	   SCIP_VAR** vars;
3512 	   SCIP* subscip;
3513 	   int nrows;
3514 	   int nvars;
3515 	   int k;
3516 	   int cutrank;
3517 	   int cutnnz;
3518 	
3519 	   assert( scip != NULL );
3520 	   assert( sepadata != NULL );
3521 	   assert( mipdata != NULL );
3522 	   assert( sol != NULL );
3523 	   assert( cutcoefs != NULL );
3524 	   assert( cutinds != NULL );
3525 	   assert( cutvals != NULL );
3526 	   assert( varsolvals != NULL );
3527 	   assert( weights != NULL );
3528 	   assert( nprevrows != NULL );
3529 	   assert( prevrows != NULL );
3530 	   assert( cutoff != NULL );
3531 	   assert( ngen != NULL );
3532 	
3533 	   *cutoff = FALSE;
3534 	   subscip = mipdata->subscip;
3535 	   assert( subscip != NULL );
3536 	
3537 	   SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
3538 	   assert( nrows > 0 );
3539 	   assert( (int) mipdata->nrows == nrows );
3540 	
3541 	   /* @todo more advanced settings - compare sepa_gomory.c */
3542 	   maxdnom = (SCIP_Longint) sepadata->cutcoefbnd+1;
3543 	   maxscale = 10000.0;
3544 	
3545 	   /* get variable data */
3546 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3547 	
3548 	   /* generate weights */
3549 	   for (k = 0; k < nrows; ++k)
3550 	   {
3551 	      SCIP_Real val;
3552 	
3553 	      weights[k] = 0;
3554 	      if ( mipdata->ylhs[k] != NULL )
3555 	      {
3556 	         assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3557 	
3558 	         val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]);
3559 	         assert( ! SCIPisFeasNegative(subscip, val) );
3560 	
3561 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3562 	         val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
3563 	
3564 	         if ( SCIPisFeasPositive(subscip, val) )
3565 	            weights[k] = -val;
3566 	      }
3567 	
3568 	      if ( mipdata->yrhs[k] != NULL )
3569 	      {
3570 	         assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3571 	
3572 	         val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]);
3573 	         assert( ! SCIPisFeasNegative(subscip, val) );
3574 	
3575 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3576 	         val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
3577 	
3578 	         /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3579 	         if ( SCIPisFeasGT(scip, val, ABS(weights[k])) )
3580 	            weights[k] = val;
3581 	      }
3582 	   }
3583 	
3584 	   /* set up data for bounds to use */
3585 	   if ( sepadata->cmirownbounds )
3586 	   {
3587 	      int typefortrans;
3588 	
3589 	      assert( boundsfortrans != NULL );
3590 	      assert( boundtypesfortrans != NULL );
3591 	
3592 	      if ( sepadata->allowlocal )
3593 	         typefortrans = -2;
3594 	      else
3595 	         typefortrans = -1;
3596 	
3597 	      /* check all variables */
3598 	      for (k = 0; k < nvars; ++k)
3599 	      {
3600 	         int pos;
3601 	         SCIP_VAR* var;
3602 	
3603 	         var = vars[k];
3604 	         assert( var != NULL );
3605 	         pos = SCIPcolGetLPPos(SCIPvarGetCol(var));
3606 	
3607 	         if ( pos < 0 )
3608 	            continue;
3609 	
3610 	         assert( pos < (int) mipdata->ncols );
3611 	         assert( SCIPvarGetStatus(var) == SCIP_VARSTATUS_COLUMN );
3612 	
3613 	         boundsfortrans[k] = typefortrans;
3614 	         boundtypesfortrans[k] = SCIP_BOUNDTYPE_LOWER;
3615 	
3616 	         if ( mipdata->coltype[pos] == colContinuous || mipdata->coltype[pos] == colConverted )
3617 	         {
3618 	            assert( SCIPvarIsIntegral(var) || mipdata->coltype[pos] != colContinuous );
3619 	            continue;
3620 	         }
3621 	
3622 	         /* check upper bound */
3623 	         if ( mipdata->z[pos] != NULL && SCIPisSumPositive(subscip, SCIPgetSolVal(subscip, sol, mipdata->z[pos])) )
3624 	         {
3625 	            /* check whether variable is complemented */
3626 	            if ( ! mipdata->iscomplemented[pos] )
3627 	               boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER;
3628 	            /* otherwise use lower bound */
3629 	         }
3630 	         else
3631 	         {
3632 	            /* check whether variable is complemented */
3633 	            if ( mipdata->iscomplemented[pos] )
3634 	               boundtypesfortrans[k] = SCIP_BOUNDTYPE_UPPER;
3635 	            /* otherwise use lower bound */
3636 	         }
3637 	      }
3638 	   }
3639 	
3640 	   /* create a MIR cut using the above calculated weights */
3641 	   cutefficacy = -1.0;
3642 	   cutrhs = -1.0;
3643 	   SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE,
3644 	         sepadata->allowlocal, 2, (int) MAXAGGRLEN(nvars), &success) );
3645 	
3646 	   if ( ! success )
3647 	      return SCIP_OKAY;
3648 	
3649 	   SCIP_CALL( SCIPcalcMIR(scip, NULL, POSTPROCESS, BOUNDSWITCH, USEVBDS, sepadata->allowlocal, FIXINTEGRALRHS, boundsfortrans,
3650 	         boundtypesfortrans, MINFRAC, MAXFRAC, 1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy,
3651 	         &cutrank, &cutislocal, &success) );
3652 	
3653 	   assert( sepadata->allowlocal || !cutislocal );
3654 	   SCIPdebugMsg(scip, "CMIR: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
3655 	      SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs);
3656 	
3657 	   /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is
3658 	    * not violated we might store non-local cuts in the pool. */
3659 	   if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
3660 	   {
3661 	      SCIP_ROW* cut;
3662 	
3663 	      /* create the cut */
3664 	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3665 	      SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3666 	
3667 	      SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3668 	
3669 	      for (k = 0; k < cutnnz; ++k)
3670 	      {
3671 	         SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) );
3672 	      }
3673 	
3674 	      assert( success );
3675 	
3676 	      /* set cut rank */
3677 	      SCIProwChgRank(cut, cutrank);
3678 	
3679 	#ifdef SCIP_DEBUG
3680 	      SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3681 	#else
3682 	      if ( sepadata->output )
3683 	      {
3684 	         SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3685 	      }
3686 	#endif
3687 	
3688 	      /* try to scale the cut to integral values */
3689 	      SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
3690 	            maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
3691 	
3692 	      /* if the cut could be made integral */
3693 	      if ( success )
3694 	      {
3695 	         SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3696 	
3697 	         /* add cut to pool */
3698 	         if ( ! cutislocal )
3699 	         {
3700 	            assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool );
3701 	            SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3702 	         }
3703 	
3704 	         if ( ! SCIPisCutEfficacious(scip, NULL, cut) )
3705 	         {
3706 	            SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
3707 	               name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3708 	               SCIPgetCutEfficacy(scip, NULL, cut));
3709 	
3710 	            /* release the row */
3711 	            SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3712 	         }
3713 	         else
3714 	         {
3715 	            /* check whether cut has been found before - may happend due to projection */
3716 	            for (k = 0; k < *nprevrows; ++k)
3717 	            {
3718 	               SCIP_Real parval;
3719 	
3720 	               assert( prevrows[k] != NULL );
3721 	               parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3722 	               /* exit if row is parallel to existing cut and rhs is not better */
3723 	               if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3724 	                  break;
3725 	            }
3726 	
3727 	            /* if cut is new */
3728 	            if ( k >= *nprevrows )
3729 	            {
3730 	               prevrows[*nprevrows] = cut;
3731 	               ++(*nprevrows);
3732 	
3733 	               SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
3734 	                  name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3735 	                  SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut),
3736 	                  SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3737 	                  SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3738 	#ifdef SCIP_OUTPUT
3739 	               SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3740 	#else
3741 	               if ( sepadata->output )
3742 	               {
3743 	                  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3744 	               }
3745 	#endif
3746 	               SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3747 	               ++(*ngen);
3748 	            }
3749 	            else
3750 	            {
3751 	               SCIPdebugMsg(scip, "Cut already exists.\n");
3752 	               /* release the row */
3753 	               SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3754 	            }
3755 	         }
3756 	      }
3757 	      else
3758 	      {
3759 	         SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
3760 	            name, cutefficacy, cutrhs);
3761 	
3762 	         /* release the row */
3763 	         SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3764 	      }
3765 	   }
3766 	
3767 	   return SCIP_OKAY;
3768 	}
3769 	
3770 	
3771 	/** create CG-cut via strong-CG-function */
3772 	static
3773 	SCIP_RETCODE createCGCutStrongCG(
3774 	   SCIP*                 scip,               /**< SCIP data structure */
3775 	   SCIP_SEPA*            sepa,               /**< separator */
3776 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
3777 	   CGMIP_MIPDATA*        mipdata,            /**< data for sub-MIP */
3778 	   SCIP_SOL*             sol,                /**< solution of sub-MIP */
3779 	   SCIP_AGGRROW*         aggrrow,            /**< aggregation row to use for creating MIR cut */
3780 	   SCIP_Real*            cutcoefs,           /**< cut coefficients */
3781 	   int*                  cutinds,            /**< problem indices of variables appearing in cut */
3782 	   SCIP_Real*            cutvals,            /**< values of variables in cut */
3783 	   SCIP_Real*            varsolvals,         /**< solution value of variables */
3784 	   SCIP_Real*            weights,            /**< weights to compute cmir cut */
3785 	   int*                  nprevrows,          /**< number of previously generated rows */
3786 	   SCIP_ROW**            prevrows,           /**< previously generated rows */
3787 	   SCIP_Bool*            cutoff,             /**< whether a cutoff has been detected */
3788 	   unsigned int*         ngen                /**< number of generated cuts */
3789 	   )
3790 	{
3791 	   char name[SCIP_MAXSTRLEN];
3792 	   SCIP_Longint maxdnom;
3793 	   SCIP_Bool cutislocal;
3794 	   SCIP_Real maxscale;
3795 	   SCIP_Real cutrhs;
3796 	   SCIP_Real cutefficacy;
3797 	   SCIP_Bool success;
3798 	   SCIP_ROW** rows;
3799 	   SCIP_VAR** vars;
3800 	   SCIP* subscip;
3801 	   int nrows;
3802 	   int nvars;
3803 	   int k;
3804 	   int cutrank;
3805 	   int cutnnz;
3806 	
3807 	   assert( scip != NULL );
3808 	   assert( sepadata != NULL );
3809 	   assert( mipdata != NULL );
3810 	   assert( sol != NULL );
3811 	   assert( cutcoefs != NULL );
3812 	   assert( cutinds != NULL );
3813 	   assert( cutvals != NULL );
3814 	   assert( varsolvals != NULL );
3815 	   assert( weights != NULL );
3816 	   assert( nprevrows != NULL );
3817 	   assert( prevrows != NULL );
3818 	   assert( cutoff != NULL );
3819 	   assert( ngen != NULL );
3820 	
3821 	   *cutoff = FALSE;
3822 	   subscip = mipdata->subscip;
3823 	   assert( subscip != NULL );
3824 	
3825 	   SCIP_CALL( SCIPgetLPRowsData(scip, &rows, &nrows) );
3826 	   assert( nrows > 0 );
3827 	   assert( (int) mipdata->nrows == nrows );
3828 	
3829 	   /* @todo more advanced settings - compare sepa_gomory.c */
3830 	   maxdnom = (SCIP_Longint) sepadata->cutcoefbnd + 1;
3831 	   maxscale = 10000.0;
3832 	
3833 	   /* get variable data */
3834 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3835 	
3836 	   /* generate weights */
3837 	   for (k = 0; k < nrows; ++k)
3838 	   {
3839 	      SCIP_Real val;
3840 	
3841 	      weights[k] = 0;
3842 	      if ( mipdata->ylhs[k] != NULL )
3843 	      {
3844 	         assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3845 	
3846 	         val = SCIPgetSolVal(subscip, sol, mipdata->ylhs[k]);
3847 	         assert( ! SCIPisFeasNegative(subscip, val) );
3848 	
3849 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3850 	         val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
3851 	
3852 	         if ( SCIPisFeasPositive(subscip, val) )
3853 	            weights[k] = -val;
3854 	      }
3855 	
3856 	      if ( mipdata->yrhs[k] != NULL )
3857 	      {
3858 	         assert( !SCIProwIsModifiable(rows[k]) && (!SCIProwIsLocal(rows[k]) || sepadata->allowlocal) );
3859 	
3860 	         val = SCIPgetSolVal(subscip, sol, mipdata->yrhs[k]);
3861 	         assert( ! SCIPisFeasNegative(subscip, val) );
3862 	
3863 	         assert( sepadata->skipmultbounds || SCIPisFeasLT(subscip, val, 1.0) );
3864 	         val = SCIPfrac(scip, val);  /* take fractional value if variable has no upper bounds */
3865 	
3866 	         /* in a suboptimal solution both values may be positive - take the one with larger absolute value */
3867 	         if ( SCIPisFeasGT(scip, val, ABS(weights[k])) )
3868 	            weights[k] = val;
3869 	      }
3870 	   }
3871 	
3872 	   /* create a strong CG cut out of the weighted LP rows using the B^-1 row as weights */
3873 	   cutefficacy = -1.0;
3874 	   cutrhs = -1.0;
3875 	   SCIP_CALL( SCIPaggrRowSumRows(scip, aggrrow, weights, NULL, -1, FALSE,
3876 	         sepadata->allowlocal, 1, (int) MAXAGGRLEN(nvars), &success) );
3877 	
3878 	   if ( ! success )
3879 	      return SCIP_OKAY;
3880 	
3881 	   SCIP_CALL( SCIPcalcStrongCG(scip, NULL, POSTPROCESS, BOUNDSWITCH, USEVBDS, sepadata->allowlocal, MINFRAC, MAXFRAC,
3882 	         1.0, aggrrow, cutcoefs, &cutrhs, cutinds, &cutnnz, &cutefficacy, &cutrank, &cutislocal, &success) );
3883 	
3884 	   assert( sepadata->allowlocal || !cutislocal );
3885 	   SCIPdebugMsg(scip, "Strong-CG: success = %u, cut is%sefficacious (cutefficacy: %g, cutrhs: %g)\n", success,
3886 	      SCIPisEfficacious(scip, cutefficacy) ? " " : " not ", cutefficacy, cutrhs);
3887 	
3888 	   /* If successful, convert dense cut into sparse row, and add the row as a cut only if the cut if violated - if it is
3889 	    * not violated we might store non-local cuts in the pool. */
3890 	   if ( success && (SCIPisEfficacious(scip, cutefficacy) || (sepadata->usecutpool && ! cutislocal)) )
3891 	   {
3892 	      SCIP_ROW* cut;
3893 	
3894 	      /* create the cut */
3895 	      (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "cgcut%" SCIP_LONGINT_FORMAT "_%u", SCIPgetNLPs(scip), *ngen);
3896 	      SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, name, -SCIPinfinity(scip), cutrhs, cutislocal, FALSE, sepadata->dynamiccuts) );
3897 	
3898 	      SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
3899 	
3900 	      for (k = 0; k < cutnnz; ++k)
3901 	      {
3902 	         SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[cutinds[k]], cutcoefs[k]) );
3903 	      }
3904 	
3905 	      assert( success );
3906 	
3907 	      /* set cut rank */
3908 	      SCIProwChgRank(cut, cutrank);
3909 	
3910 	#ifdef SCIP_DEBUG
3911 	      SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3912 	#else
3913 	      if ( sepadata->output )
3914 	      {
3915 	         SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3916 	      }
3917 	#endif
3918 	
3919 	      /* try to scale the cut to integral values */
3920 	      SCIP_CALL( SCIPmakeRowIntegral(scip, cut, -SCIPepsilon(scip), SCIPsumepsilon(scip),
3921 	            maxdnom, maxscale, MAKECONTINTEGRAL, &success) );
3922 	
3923 	      /* if the cut could be made integral */
3924 	      if ( success )
3925 	      {
3926 	         SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
3927 	
3928 	         /* add cut to pool */
3929 	         if ( ! cutislocal )
3930 	         {
3931 	            assert( SCIPisEfficacious(scip, cutefficacy) || sepadata->usecutpool );
3932 	            SCIP_CALL( SCIPaddPoolCut(scip, cut) );
3933 	         }
3934 	
3935 	         if ( ! SCIPisCutEfficacious(scip, NULL, cut) )
3936 	         {
3937 	            SCIPdebugMsg(scip, " -> CG-cut <%s> no longer efficacious: act=%f, rhs=%f, norm=%f, eff=%f\n",
3938 	               name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3939 	               SCIPgetCutEfficacy(scip, NULL, cut));
3940 	
3941 	            /* release the row */
3942 	            SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3943 	         }
3944 	         else
3945 	         {
3946 	            /* check whether cut has been found before - may happend due to projection */
3947 	            for (k = 0; k < *nprevrows; ++k)
3948 	            {
3949 	               SCIP_Real parval;
3950 	
3951 	               assert( prevrows[k] != NULL );
3952 	               parval = SCIProwGetParallelism(cut, prevrows[k], 'e');
3953 	               /* exit if row is parallel to existing cut and rhs is not better */
3954 	               if ( SCIPisEQ(scip, parval, 1.0) && SCIPisGE(scip, cutrhs, SCIProwGetRhs(prevrows[k])) )
3955 	                  break;
3956 	            }
3957 	
3958 	            /* if cut is new */
3959 	            if ( k >= *nprevrows )
3960 	            {
3961 	               prevrows[*nprevrows] = cut;
3962 	               ++(*nprevrows);
3963 	
3964 	               SCIPdebugMsg(scip, " -> CG-cut <%s>: act=%f, rhs=%f, norm=%f, eff=%f, rank=%d, min=%f, max=%f (range=%f)\n",
3965 	                  name, SCIPgetRowLPActivity(scip, cut), SCIProwGetRhs(cut), SCIProwGetNorm(cut),
3966 	                  SCIPgetCutEfficacy(scip, NULL, cut), SCIProwGetRank(cut),
3967 	                  SCIPgetRowMinCoef(scip, cut), SCIPgetRowMaxCoef(scip, cut),
3968 	                  SCIPgetRowMaxCoef(scip, cut)/SCIPgetRowMinCoef(scip, cut));
3969 	#ifdef SCIP_OUTPUT
3970 	               SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3971 	#else
3972 	               if ( sepadata->output )
3973 	               {
3974 	                  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
3975 	               }
3976 	#endif
3977 	               SCIP_CALL( SCIPaddRow(scip, cut, FALSE, cutoff) );
3978 	               ++(*ngen);
3979 	            }
3980 	            else
3981 	            {
3982 	               SCIPdebugMsg(scip, "Cut already exists.\n");
3983 	               /* release the row */
3984 	               SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3985 	            }
3986 	         }
3987 	      }
3988 	      else
3989 	      {
3990 	         SCIPdebugMsg(scip, " -> CG-cut <%s> could not be scaled to integral coefficients: rhs=%f, eff=%f\n",
3991 	            name, cutefficacy, cutrhs);
3992 	
3993 	         /* release the row */
3994 	         SCIP_CALL( SCIPreleaseRow(scip, &cut) );
3995 	      }
3996 	   }
3997 	
3998 	   return SCIP_OKAY;
3999 	}
4000 	
4001 	
4002 	/** Create CG-cuts from solutions of sub-MIP */
4003 	static
4004 	SCIP_RETCODE createCGCuts(
4005 	   SCIP*                 scip,               /**< SCIP data structure */
4006 	   SCIP_SEPA*            sepa,               /**< separator */
4007 	   SCIP_SEPADATA*        sepadata,           /**< separator data */
4008 	   CGMIP_MIPDATA*        mipdata,            /**< data for sub-MIP */
4009 	   SCIP_Bool*            cutoff,             /**< whether a cutoff has been detected */
4010 	   unsigned int*         ngen                /**< number of generated cuts */
4011 	   )
4012 	{
4013 	   SCIP_BOUNDTYPE* boundtypesfortrans;
4014 	   SCIP_STAGE stage;
4015 	   SCIP_AGGRROW* aggrrow = NULL;
4016 	   SCIP_Real* varsolvals;
4017 	   SCIP_Real* weights;
4018 	   int* cutinds;
4019 	   SCIP_Real* cutvals;
4020 	   SCIP_Real* cutcoefs;
4021 	   SCIP_ROW** prevrows;
4022 	   SCIP_SOL** sols;
4023 	   SCIP_VAR** vars;
4024 	   SCIP* subscip;
4025 	   int* boundsfortrans;
4026 	   int nprevrows;
4027 	   int ntotalrows;
4028 	   int nsols;
4029 	   int nvars;
4030 	   int k;
4031 	   int s;
4032 	
4033 	   assert( scip != NULL );
4034 	   assert( sepadata != NULL );
4035 	   assert( mipdata != NULL );
4036 	   assert( cutoff != NULL );
4037 	   assert( ngen != NULL );
4038 	
4039 	   subscip = mipdata->subscip;
4040 	   assert( subscip != NULL );
4041 	
4042 	   *cutoff = FALSE;
4043 	   *ngen = 0;
4044 	
4045 	   /* check if solving was successful and get solutions */
4046 	   stage = SCIPgetStage(subscip);
4047 	   if ( stage == SCIP_STAGE_SOLVING || stage == SCIP_STAGE_SOLVED )
4048 	      nsols = SCIPgetNSols(subscip);
4049 	   else
4050 	      nsols = 0;
4051 	
4052 	   /* only if solutions have been found */
4053 	   if ( nsols == 0 )
4054 	      return SCIP_OKAY;
4055 	
4056 	   SCIPdebugMsg(scip, "Generating CG-cuts from %d sols (cmir: %u, strong-cg: %u) ...\n", nsols, sepadata->usecmir, sepadata->usestrongcg);
4057 	
4058 	   sols = SCIPgetSols(subscip);
4059 	
4060 	   /* get variable data */
4061 	   SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
4062 	
4063 	   /* allocate temporary memory */
4064 	   assert(mipdata->ntotalrows <= INT_MAX);
4065 	   ntotalrows = (int)mipdata->ntotalrows;
4066 	   assert( ntotalrows >= SCIPgetNLPRows(scip) && ntotalrows <= SCIPgetNLPRows(scip) + 1 );
4067 	   SCIP_CALL( SCIPallocBufferArray(scip, &cutcoefs, nvars) );
4068 	   SCIP_CALL( SCIPallocBufferArray(scip, &varsolvals, nvars) );
4069 	   SCIP_CALL( SCIPallocBufferArray(scip, &cutinds, nvars) );
4070 	   SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars) );
4071 	   SCIP_CALL( SCIPallocBufferArray(scip, &weights, ntotalrows) );
4072 	   SCIP_CALL( SCIPallocBufferArray(scip, &prevrows, 2 * nsols) );
4073 	
4074 	   if ( sepadata->usecmir || sepadata->usestrongcg )
4075 	   {
4076 	      SCIP_CALL( SCIPaggrRowCreate(scip, &aggrrow) );
4077 	   }
4078 	
4079 	   /* prepare arrays for bound information, if requested */
4080 	   if ( sepadata->usecmir && sepadata->cmirownbounds )
4081 	   {
4082 	      SCIP_CALL( SCIPallocBufferArray(scip, &boundsfortrans, nvars) );
4083 	      SCIP_CALL( SCIPallocBufferArray(scip, &boundtypesfortrans, nvars) );
4084 	   }
4085 	   else
4086 	   {
4087 	      boundsfortrans = NULL;
4088 	      boundtypesfortrans = NULL;
4089 	   }
4090 	
4091 	   /* get solution values */
4092 	   for (k = 0; k < nvars; ++k)
4093 	   {
4094 	      if ( SCIPvarGetStatus(vars[k]) == SCIP_VARSTATUS_COLUMN )
4095 	         varsolvals[k] = SCIPvarGetLPSol(vars[k]);
4096 	      else
4097 	         varsolvals[k] = 0.0;
4098 	   }
4099 	
4100 	   /* loop through solutions found */
4101 	   nprevrows = 0;
4102 	   for (s = 0; s < nsols; ++s)
4103 	   {
4104 	      SCIP_SOL* sol;
4105 	      sol = sols[s];
4106 	
4107 	      /* generate cuts by the C-MIR and/or Strong-CG functions */
4108 	      if ( sepadata->usecmir )
4109 	      {
4110 	         SCIP_CALL( createCGCutCMIR(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
4111 	               boundsfortrans, boundtypesfortrans, &nprevrows, prevrows, cutoff, ngen) );
4112 	      }
4113 	
4114 	      if ( sepadata->usestrongcg )
4115 	      {
4116 	         SCIP_CALL( createCGCutStrongCG(scip, sepa, sepadata, mipdata, sol, aggrrow, cutcoefs, cutinds, cutvals, varsolvals, weights,
4117 	               &nprevrows, prevrows, cutoff, ngen) );
4118 	      }
4119 	
4120 	      if ( ! sepadata->usecmir && ! sepadata->usestrongcg )
4121 	      {
4122 	         SCIP_CALL( createCGCutDirect(scip, sepa, sepadata, mipdata, sol, cutcoefs, cutinds, cutvals, varsolvals, weights,
4123 	               &nprevrows, prevrows, cutoff, ngen) );
4124 	
4125 	         assert(! sepadata->usecmir && ! sepadata->usestrongcg);
4126 	      }
4127 	   }
4128 	   assert( nprevrows <= 2 * nsols );
4129 	   assert( sepadata->usecmir || nprevrows <= nsols );
4130 	   assert( sepadata->usestrongcg || nprevrows <= nsols );
4131 	
4132 	   /* release rows */
4133 	   for (k = 0; k < nprevrows; ++k)
4134 	   {
4135 	      SCIP_CALL( SCIPreleaseRow(scip, &(prevrows[k])) );
4136 	   }
4137 	
4138 	   if ( sepadata->usecmir || sepadata->usestrongcg )
4139 	      SCIPaggrRowFree(scip, &aggrrow);
4140 	
4141 	   /* free temporary memory */
4142 	   SCIPfreeBufferArrayNull(scip, &boundsfortrans);
4143 	   SCIPfreeBufferArrayNull(scip, &boundtypesfortrans);
4144 	
4145 	   SCIPfreeBufferArray(scip, &prevrows);
4146 	   SCIPfreeBufferArray(scip, &weights);
4147 	   SCIPfreeBufferArray(scip, &cutvals);
4148 	   SCIPfreeBufferArray(scip, &cutinds);
4149 	   SCIPfreeBufferArray(scip, &varsolvals);
4150 	   SCIPfreeBufferArray(scip, &cutcoefs);
4151 	
4152 	   return SCIP_OKAY;
4153 	}
4154 	
4155 	
4156 	/** frees "subscip" data */
4157 	static
4158 	SCIP_RETCODE freeSubscip(
4159 	   SCIP*                 scip,               /**< SCIP data structure */
4160 	   SCIP_SEPA*            sepa,               /**< separator data */
4161 	   CGMIP_MIPDATA*        mipdata             /**< data for sub-MIP */
4162 	   )
4163 	{
4164 	   SCIP_SEPADATA* sepadata;
4165 	   unsigned int i, j;
4166 	   SCIP* subscip;
4167 	
4168 	   assert( scip != NULL );
4169 	   assert( sepa != NULL );
4170 	   assert( mipdata != NULL );
4171 	
4172 	   /* free separator data */
4173 	   sepadata = SCIPsepaGetData(sepa);
4174 	   assert( sepadata != NULL );
4175 	
4176 	   SCIPdebugMsg(scip, "Freeing subscip ...\n");
4177 	
4178 	   subscip = mipdata->subscip;
4179 	   assert( subscip != NULL );
4180 	
4181 	   for (j = 0; j < mipdata->ncols; ++j)
4182 	   {
4183 	      if ( mipdata->coltype[j] == colPresent )
4184 	      {
4185 	         assert( mipdata->alpha[j] != NULL );
4186 	         SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->alpha[j])) );
4187 	         SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracalpha[j])) );
4188 	      }
4189 	   }
4190 	   SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->beta)) );
4191 	   SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->fracbeta)) );
4192 	
4193 	   for (i = 0; i < mipdata->nrows; ++i)
4194 	   {
4195 	      if ( mipdata->ylhs[i] != NULL )
4196 	      {
4197 	         SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[i])) );
4198 	      }
4199 	      if ( mipdata->yrhs[i] != NULL )
4200 	      {
4201 	         SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[i])) );
4202 	      }
4203 	   }
4204 	
4205 	   if ( sepadata->useobjub || sepadata->useobjlb )
4206 	   {
4207 	      if ( mipdata->yrhs[mipdata->nrows] )
4208 	      {
4209 	         SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->yrhs[mipdata->nrows])) );
4210 	      }
4211 	      if ( mipdata->ylhs[mipdata->nrows] )
4212 	      {
4213 	         SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->ylhs[mipdata->nrows])) );
4214 	      }
4215 	   }
4216 	
4217 	   for (j = 0; j < mipdata->ncols; ++j)
4218 	   {
4219 	      if ( mipdata->z[j] != NULL )
4220 	      {
4221 	         SCIP_CALL( SCIPreleaseVar(subscip, &(mipdata->z[j])) );
4222 	      }
4223 	   }
4224 	
4225 	   SCIP_CALL( SCIPfree(&(mipdata->subscip)) );
4226 	
4227 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->rhs), mipdata->ntotalrows);
4228 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->lhs), mipdata->ntotalrows);
4229 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->z), 2*mipdata->ncols); /*lint !e647*/
4230 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->yrhs), mipdata->ntotalrows);
4231 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->ylhs), mipdata->ntotalrows);
4232 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->isshifted), mipdata->ncols);
4233 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->iscomplemented), mipdata->ncols);
4234 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->coltype), mipdata->ncols);
4235 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->fracalpha), mipdata->ncols);
4236 	   SCIPfreeBlockMemoryArray(scip, &(mipdata->alpha), mipdata->ncols);
4237 	
4238 	   return SCIP_OKAY;
4239 	}
4240 	
4241 	
4242 	/*
4243 	 * Callback methods
4244 	 */
4245 	
4246 	
4247 	/** initialization method of separator (called after problem was transformed) */
4248 	static
4249 	SCIP_DECL_SEPAINIT(sepaInitCGMIP)
4250 	{
4251 	   SCIP_SEPADATA* sepadata;
4252 	
4253 	   sepadata = SCIPsepaGetData(sepa);
4254 	   assert(sepadata != NULL);
4255 	
4256 	   /* create and initialize random number generator */
4257 	   SCIP_CALL( SCIPcreateRandom(scip, &sepadata->randnumgen, DEFAULT_RANDSEED, TRUE) );
4258 	
4259 	   return SCIP_OKAY;
4260 	}
4261 	
4262 	/** deinitialization method of separator (called before transformed problem is freed) */
4263 	static
4264 	SCIP_DECL_SEPAEXIT(sepaExitCGMIP)
4265 	{  /*lint --e{715}*/
4266 	   SCIP_SEPADATA* sepadata;
4267 	
4268 	   sepadata = SCIPsepaGetData(sepa);
4269 	   assert(sepadata != NULL);
4270 	
4271 	   SCIPfreeRandom(scip, &sepadata->randnumgen);
4272 	
4273 	   return SCIP_OKAY;
4274 	}
4275 	
4276 	/** copy method for separator plugins (called when SCIP copies plugins) */
4277 	static
4278 	SCIP_DECL_SEPACOPY(sepaCopyCGMIP)
4279 	{  /*lint --e{715}*/
4280 	   assert( scip != NULL );
4281 	   assert( sepa != NULL );
4282 	   assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4283 	
4284 	   /* call inclusion method of constraint handler */
4285 	   SCIP_CALL( SCIPincludeSepaCGMIP(scip) );
4286 	
4287 	   return SCIP_OKAY;
4288 	}
4289 	
4290 	
4291 	/** destructor of separator to free user data (called when SCIP is exiting) */
4292 	static
4293 	SCIP_DECL_SEPAFREE(sepaFreeCGMIP)
4294 	{  /*lint --e{715}*/
4295 	   SCIP_SEPADATA* sepadata;
4296 	
4297 	   assert( scip != NULL );
4298 	   assert( sepa != NULL );
4299 	   assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4300 	
4301 	   /* free separator data */
4302 	   sepadata = SCIPsepaGetData(sepa);
4303 	   assert( sepadata != NULL );
4304 	
4305 	   SCIPfreeBlockMemory(scip, &sepadata);
4306 	
4307 	   SCIPsepaSetData(sepa, NULL);
4308 	
4309 	   return SCIP_OKAY;
4310 	}
4311 	
4312 	
4313 	/** LP solution separation method of separator */
4314 	static
4315 	SCIP_DECL_SEPAEXECLP(sepaExeclpCGMIP)
4316 	{  /*lint --e{715}*/
4317 	   SCIP_SEPADATA* sepadata;
4318 	   CGMIP_MIPDATA* mipdata;
4319 	
4320 	   int ncalls;
4321 	   int ncols;
4322 	   int nrows;
4323 	   unsigned int ngen = 0;
4324 	   SCIP_Bool success;
4325 	   SCIP_Bool cutoff = FALSE;
4326 	
4327 	   assert( scip != NULL );
4328 	   assert( sepa != NULL );
4329 	   assert( strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0 );
4330 	   assert( result != NULL );
4331 	
4332 	   *result = SCIP_DIDNOTRUN;
4333 	
4334 	   sepadata = SCIPsepaGetData(sepa);
4335 	   assert(sepadata != NULL);
4336 	
4337 	   /* only call separator, if we are not close to terminating */
4338 	   if ( SCIPisStopped(scip) )
4339 	      return SCIP_OKAY;
4340 	
4341 	   /* only call separator up to a maximum depth */
4342 	   if ( sepadata->maxdepth >= 0 && depth > sepadata->maxdepth )
4343 	      return SCIP_OKAY;
4344 	
4345 	   /* only call separator a given number of times at each node */
4346 	   ncalls = SCIPsepaGetNCallsAtNode(sepa);
4347 	   if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
4348 	      || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
4349 	      return SCIP_OKAY;
4350 	
4351 	   /* only call separator, if an optimal LP solution is at hand */
4352 	   if ( SCIPgetLPSolstat(scip) != SCIP_LPSOLSTAT_OPTIMAL )
4353 	      return SCIP_OKAY;
4354 	
4355 	   /* skip separation if there are continuous variables, but only integers required */
4356 	   if ( SCIPgetNContVars(scip) > 0 && sepadata->onlyintvars )
4357 	      return SCIP_OKAY;
4358 	
4359 	   /* only call separator, if there are fractional variables */
4360 	   if ( SCIPgetNLPBranchCands(scip) == 0 )
4361 	      return SCIP_OKAY;
4362 	
4363 	   /* check for parameters */
4364 	   if ( ( sepadata->useobjub || sepadata->useobjlb ) && ( sepadata->usecmir || sepadata->usestrongcg ) )
4365 	   {
4366 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL,
4367 	         "WARNING - sepa_cgmip: Using objective function bounds and CMIR or Strong-CG functions is useless. Turning off usage of objective function bounds.\n");
4368 	      SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjub", FALSE) );
4369 	      SCIP_CALL( SCIPsetBoolParam(scip, "separating/cgmip/useobjlb", FALSE) );
4370 	   }
4371 	   sepadata->allowlocal = allowlocal;
4372 	
4373 	   /* get LP data */
4374 	   ncols = SCIPgetNLPCols(scip);
4375 	   nrows = SCIPgetNLPRows(scip);
4376 	   if ( ncols <= NCOLSTOOSMALL || nrows <= NROWSTOOSMALL )
4377 	      return SCIP_OKAY;
4378 	
4379 	   /* determine whether we should run the separation based on a decision tree */
4380 	   if ( sepadata->decisiontree )
4381 	   {
4382 	      SCIP_Bool separate;
4383 	      SCIP_Real firstlptime;
4384 	
4385 	      separate = FALSE;
4386 	      firstlptime = SCIPgetFirstLPTime(scip);
4387 	
4388 	      if ( nrows <= 136 && firstlptime <= 0.05 && ncols <= 143 )
4389 	         separate = TRUE;
4390 	      else if ( nrows <= 136 && 0.05 < firstlptime && firstlptime <= 0.15 && ncols <= 143 )
4391 	         separate = TRUE;
4392 	      else if ( 136 < nrows && nrows <= 332 && ncols <= 143 )
4393 	         separate = TRUE;
4394 	      else if ( 136 < nrows && nrows <= 332 && 655 < ncols && ncols <= 1290 )
4395 	         separate = TRUE;
4396 	      else if ( 333 < nrows && nrows <= 874 && 0.15 < firstlptime && firstlptime <= 0.25 && 2614 < ncols && ncols <= 5141 )
4397 	         separate = TRUE;
4398 	      else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 143 < ncols && ncols <= 265 )
4399 	         separate = TRUE;
4400 	      else if ( 875 < nrows && nrows <= 1676 && firstlptime <= 0.05 && 265 < ncols && ncols <= 654 )
4401 	         separate = TRUE;
4402 	      else if ( 875 < nrows && nrows <= 1676 && 0.05 < firstlptime && firstlptime <= 0.15 )
4403 	         separate = TRUE;
4404 	      else if ( 875 < nrows && nrows <= 1676 &&  0.15 < firstlptime && firstlptime <= 0.25 && 1291 < ncols && ncols <= 2613 )
4405 	         separate = TRUE;
4406 	      else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 655 < ncols && ncols <= 1290 )
4407 	         separate = TRUE;
4408 	      else if ( nrows > 8146 && 0.75 < firstlptime && firstlptime <= 6.25 && 1291 < ncols && ncols <= 2613 )
4409 	         separate = TRUE;
4410 	      else if ( nrows > 8146 && firstlptime > 6.25 )
4411 	         separate = TRUE;
4412 	
4413 	      if ( ! separate )
4414 	      {
4415 	         return SCIP_OKAY;
4416 	      }
4417 	   }
4418 	
4419 	   /* preceed with separation */
4420 	   *result = SCIP_DIDNOTFIND;
4421 	
4422 	   SCIPdebugMsg(scip, "separating CG-cuts via sub-MIPs: %d cols, %d rows\n", ncols, nrows);
4423 	
4424 	   /* prepare data */
4425 	   SCIP_CALL( SCIPallocBlockMemory(scip, &mipdata) );
4426 	   mipdata->subscip = NULL;
4427 	   mipdata->alpha = NULL;
4428 	   mipdata->fracalpha = NULL;
4429 	   mipdata->beta = NULL;
4430 	   mipdata->fracbeta = NULL;
4431 	   mipdata->coltype = NULL;
4432 	   mipdata->iscomplemented = NULL;
4433 	   mipdata->isshifted = NULL;
4434 	   mipdata->ylhs = NULL;
4435 	   mipdata->yrhs = NULL;
4436 	   mipdata->z = NULL;
4437 	   mipdata->lhs = NULL;
4438 	   mipdata->rhs = NULL;
4439 	   mipdata->normtype = ' ';
4440 	
4441 	   mipdata->conshdlrfullnorm = CONSHDLRFULLNORM;
4442 	   mipdata->scip = scip;
4443 	   mipdata->sepa = sepa;
4444 	   mipdata->sepadata = sepadata;
4445 	
4446 	   /* get the type of norm to use for efficacy calculations */
4447 	   SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &mipdata->normtype) );
4448 	
4449 	   /* create subscip */
4450 	   SCIP_CALL( createSubscip(scip, sepa, sepadata, mipdata) );
4451 	
4452 	   /* set parameters */
4453 	   SCIP_CALL( subscipSetParams(sepadata, mipdata) );
4454 	
4455 	   if ( ! SCIPisStopped(scip) )
4456 	   {
4457 	      /* solve subscip */
4458 	      SCIP_CALL( solveSubscip(scip, sepadata, mipdata, &success) );
4459 	
4460 	      /* preceed if solution was successful */
4461 	      if ( success && ! SCIPisStopped(scip) )
4462 	      {
4463 	         SCIP_CALL( createCGCuts(scip, sepa, sepadata, mipdata, &cutoff, &ngen) );
4464 	      }
4465 	   }
4466 	
4467 	   SCIP_CALL( freeSubscip(scip, sepa, mipdata) );
4468 	   SCIPfreeBlockMemory(scip, &mipdata);
4469 	
4470 	   SCIPdebugMsg(scip, "Found %u CG-cuts.\n", ngen);
4471 	
4472 	   if ( cutoff )
4473 	      *result = SCIP_CUTOFF;
4474 	   else if ( ngen > 0 )
4475 	      *result = SCIP_SEPARATED;
4476 	
4477 	#ifdef SCIP_OUTPUT
4478 	   /* SCIP_CALL( SCIPwriteLP(scip, "cuts.lp") ); */
4479 	   /* SCIP_CALL( SCIPwriteMIP(scip, "cuts.lp", FALSE, TRUE) ); */
4480 	#endif
4481 	
4482 	   return SCIP_OKAY;
4483 	}
4484 	
4485 	/*
4486 	 * separator specific interface methods
4487 	 */
4488 	
4489 	/** creates the CGMIP MIR cut separator and includes it in SCIP */
4490 	SCIP_RETCODE SCIPincludeSepaCGMIP(
4491 	   SCIP*                 scip                /**< SCIP data structure */
4492 	   )
4493 	{
4494 	   SCIP_SEPADATA* sepadata;
4495 	   SCIP_SEPA* sepa = NULL;
4496 	
4497 	   /* create separator data */
4498 	   SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
4499 	
4500 	   /* include separator */
4501 	   SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
4502 	         SEPA_USESSUBSCIP, SEPA_DELAY, sepaExeclpCGMIP, NULL, sepadata) );
4503 	   assert(sepa != NULL);
4504 	
4505 	   SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyCGMIP) );
4506 	   SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeCGMIP) );
4507 	   SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitCGMIP) );
4508 	   SCIP_CALL( SCIPsetSepaExit(scip, sepa, sepaExitCGMIP) );
4509 	
4510 	   /* add separator parameters */
4511 	   SCIP_CALL( SCIPaddIntParam(scip,
4512 	         "separating/" SEPA_NAME "/maxrounds",
4513 	         "maximal number of cgmip separation rounds per node (-1: unlimited)",
4514 	         &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
4515 	
4516 	   SCIP_CALL( SCIPaddIntParam(scip,
4517 	         "separating/" SEPA_NAME "/maxroundsroot",
4518 	         "maximal number of cgmip separation rounds in the root node (-1: unlimited)",
4519 	         &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
4520 	
4521 	   SCIP_CALL( SCIPaddIntParam(scip,
4522 	         "separating/" SEPA_NAME "/maxdepth",
4523 	         "maximal depth at which the separator is applied (-1: unlimited)",
4524 	         &sepadata->maxdepth, FALSE, DEFAULT_MAXDEPTH, -1, INT_MAX, NULL, NULL) );
4525 	
4526 	   SCIP_CALL( SCIPaddBoolParam(scip,
4527 	         "separating/" SEPA_NAME "/decisiontree",
4528 	         "Use decision tree to turn separation on/off?",
4529 	         &sepadata->decisiontree, FALSE, DEFAULT_DECISIONTREE, NULL, NULL) );
4530 	
4531 	   SCIP_CALL( SCIPaddRealParam(scip,
4532 	         "separating/" SEPA_NAME "/timelimit",
4533 	         "time limit for sub-MIP",
4534 	         &sepadata->timelimit, TRUE, DEFAULT_TIMELIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4535 	
4536 	   SCIP_CALL( SCIPaddRealParam(scip,
4537 	         "separating/" SEPA_NAME "/memorylimit",
4538 	         "memory limit for sub-MIP",
4539 	         &sepadata->memorylimit, TRUE, DEFAULT_MEMORYLIMIT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4540 	
4541 	   SCIP_CALL( SCIPaddLongintParam(scip,
4542 	         "separating/" SEPA_NAME "/minnodelimit",
4543 	         "minimum number of nodes considered for sub-MIP (-1: unlimited)",
4544 	         &sepadata->minnodelimit, FALSE, DEFAULT_MINNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
4545 	
4546 	   SCIP_CALL( SCIPaddLongintParam(scip,
4547 	         "separating/" SEPA_NAME "/maxnodelimit",
4548 	         "maximum number of nodes considered for sub-MIP (-1: unlimited)",
4549 	         &sepadata->maxnodelimit, FALSE, DEFAULT_MAXNODELIMIT, -1LL, SCIP_LONGINT_MAX, NULL, NULL) );
4550 	
4551 	   SCIP_CALL( SCIPaddRealParam(scip,
4552 	         "separating/" SEPA_NAME "/cutcoefbnd",
4553 	         "bounds on the values of the coefficients in the CG-cut",
4554 	         &sepadata->cutcoefbnd, TRUE, DEFAULT_CUTCOEFBND, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4555 	
4556 	   SCIP_CALL( SCIPaddBoolParam(scip,
4557 	         "separating/" SEPA_NAME "/onlyactiverows",
4558 	         "Use only active rows to generate cuts?",
4559 	         &sepadata->onlyactiverows, FALSE, DEFAULT_ONLYACTIVEROWS, NULL, NULL) );
4560 	
4561 	   SCIP_CALL( SCIPaddIntParam(scip,
4562 	         "separating/" SEPA_NAME "/maxrowage",
4563 	         "maximal age of rows to consider if onlyactiverows is false",
4564 	         &sepadata->maxrowage, FALSE, DEFAULT_MAXROWAGE, -1, INT_MAX, NULL, NULL) );
4565 	
4566 	   SCIP_CALL( SCIPaddBoolParam(scip,
4567 	         "separating/" SEPA_NAME "/onlyrankone",
4568 	         "Separate only rank 1 inequalities w.r.t. CG-MIP separator?",
4569 	         &sepadata->onlyrankone, FALSE, DEFAULT_ONLYRANKONE, NULL, NULL) );
4570 	
4571 	   SCIP_CALL( SCIPaddBoolParam(scip,
4572 	         "separating/" SEPA_NAME "/onlyintvars",
4573 	         "Generate cuts for problems with only integer variables?",
4574 	         &sepadata->onlyintvars, FALSE, DEFAULT_ONLYINTVARS, NULL, NULL) );
4575 	
4576 	   SCIP_CALL( SCIPaddBoolParam(scip,
4577 	         "separating/" SEPA_NAME "/contconvert",
4578 	         "Convert some integral variables to be continuous to reduce the size of the sub-MIP?",
4579 	         &sepadata->contconvert, FALSE, DEFAULT_CONTCONVERT, NULL, NULL) );
4580 	
4581 	   SCIP_CALL( SCIPaddRealParam(scip,
4582 	         "separating/" SEPA_NAME "/contconvfrac",
4583 	         "fraction of integral variables converted to be continuous (if contconvert)",
4584 	         &sepadata->contconvfrac, FALSE, DEFAULT_CONTCONVFRAC, 0.0, 1.0, NULL, NULL) );
4585 	
4586 	   SCIP_CALL( SCIPaddIntParam(scip,
4587 	         "separating/" SEPA_NAME "/contconvmin",
4588 	         "minimum number of integral variables before some are converted to be continuous",
4589 	         &sepadata->contconvmin, FALSE, DEFAULT_CONTCONVMIN, -1, INT_MAX, NULL, NULL) );
4590 	
4591 	   SCIP_CALL( SCIPaddBoolParam(scip,
4592 	         "separating/" SEPA_NAME "/intconvert",
4593 	         "Convert some integral variables attaining fractional values to have integral value?",
4594 	         &sepadata->intconvert, FALSE, DEFAULT_INTCONVERT, NULL, NULL) );
4595 	
4596 	   SCIP_CALL( SCIPaddRealParam(scip,
4597 	         "separating/" SEPA_NAME "/intconvfrac",
4598 	         "fraction of frac. integral variables converted to have integral value (if intconvert)",
4599 	         &sepadata->intconvfrac, FALSE, DEFAULT_INTCONVFRAC, 0.0, 1.0, NULL, NULL) );
4600 	
4601 	   SCIP_CALL( SCIPaddIntParam(scip,
4602 	         "separating/" SEPA_NAME "/intconvmin",
4603 	         "minimum number of integral variables before some are converted to have integral value",
4604 	         &sepadata->intconvmin, FALSE, DEFAULT_INTCONVMIN, -1, INT_MAX, NULL, NULL) );
4605 	
4606 	   SCIP_CALL( SCIPaddBoolParam(scip,
4607 	         "separating/" SEPA_NAME "/skipmultbounds",
4608 	         "Skip the upper bounds on the multipliers in the sub-MIP?",
4609 	         &sepadata->skipmultbounds, FALSE, DEFAULT_SKIPMULTBOUNDS, NULL, NULL) );
4610 	
4611 	   SCIP_CALL( SCIPaddBoolParam(scip,
4612 	         "separating/" SEPA_NAME "/objlone",
4613 	         "Should the objective of the sub-MIP minimize the l1-norm of the multipliers?",
4614 	         &sepadata->objlone, FALSE, DEFAULT_OBJLONE, NULL, NULL) );
4615 	
4616 	   SCIP_CALL( SCIPaddRealParam(scip,
4617 	         "separating/" SEPA_NAME "/objweight",
4618 	         "weight used for the row combination coefficient in the sub-MIP objective",
4619 	         &sepadata->objweight, TRUE, DEFAULT_OBJWEIGHT, 0.0, SCIP_REAL_MAX, NULL, NULL) );
4620 	
4621 	   SCIP_CALL( SCIPaddBoolParam(scip,
4622 	         "separating/" SEPA_NAME "/objweightsize",
4623 	         "Weight each row by its size?",
4624 	         &sepadata->objweightsize, FALSE, DEFAULT_OBJWEIGHTSIZE, NULL, NULL) );
4625 	
4626 	   SCIP_CALL( SCIPaddBoolParam(scip,
4627 	         "separating/" SEPA_NAME "/dynamiccuts",
4628 	         "should generated cuts be removed from the LP if they are no longer tight?",
4629 	         &sepadata->dynamiccuts, FALSE, DEFAULT_DYNAMICCUTS, NULL, NULL) );
4630 	
4631 	   SCIP_CALL( SCIPaddBoolParam(scip,
4632 	         "separating/" SEPA_NAME "/usecmir",
4633 	         "use CMIR-generator (otherwise add cut directly)?",
4634 	         &sepadata->usecmir, FALSE, DEFAULT_USECMIR, NULL, NULL) );
4635 	
4636 	   SCIP_CALL( SCIPaddBoolParam(scip,
4637 	         "separating/" SEPA_NAME "/usestrongcg",
4638 	         "use strong CG-function to strengthen cut?",
4639 	         &sepadata->usestrongcg, FALSE, DEFAULT_USESTRONGCG, NULL, NULL) );
4640 	
4641 	   SCIP_CALL( SCIPaddBoolParam(scip,
4642 	         "separating/" SEPA_NAME "/cmirownbounds",
4643 	         "tell CMIR-generator which bounds to used in rounding?",
4644 	         &sepadata->cmirownbounds, FALSE, DEFAULT_CMIROWNBOUNDS, NULL, NULL) );
4645 	
4646 	   SCIP_CALL( SCIPaddBoolParam(scip,
4647 	         "separating/" SEPA_NAME "/usecutpool",
4648 	         "use cutpool to store CG-cuts even if the are not efficient?",
4649 	         &sepadata->usecutpool, FALSE, DEFAULT_USECUTPOOL, NULL, NULL) );
4650 	
4651 	   SCIP_CALL( SCIPaddBoolParam(scip,
4652 	         "separating/" SEPA_NAME "/primalseparation",
4653 	         "only separate cuts that are tight for the best feasible solution?",
4654 	         &sepadata->primalseparation, FALSE, DEFAULT_PRIMALSEPARATION, NULL, NULL) );
4655 	
4656 	   SCIP_CALL( SCIPaddBoolParam(scip,
4657 	         "separating/" SEPA_NAME "/earlyterm",
4658 	         "terminate separation if a violated (but possibly sub-optimal) cut has been found?",
4659 	         &sepadata->earlyterm, FALSE, DEFAULT_EARLYTERM, NULL, NULL) );
4660 	
4661 	   SCIP_CALL( SCIPaddBoolParam(scip,
4662 	         "separating/" SEPA_NAME "/addviolationcons",
4663 	         "add constraint to subscip that only allows violated cuts (otherwise add obj. limit)?",
4664 	         &sepadata->addviolationcons, FALSE, DEFAULT_ADDVIOLATIONCONS, NULL, NULL) );
4665 	
4666 	   SCIP_CALL( SCIPaddBoolParam(scip,
4667 	         "separating/" SEPA_NAME "/addviolconshdlr",
4668 	         "add constraint handler to filter out violated cuts?",
4669 	         &sepadata->addviolconshdlr, FALSE, DEFAULT_ADDVIOLCONSHDLR, NULL, NULL) );
4670 	
4671 	   SCIP_CALL( SCIPaddBoolParam(scip,
4672 	         "separating/" SEPA_NAME "/conshdlrusenorm",
4673 	         "should the violation constraint handler use the norm of a cut to check for feasibility?",
4674 	         &sepadata->conshdlrusenorm, FALSE, DEFAULT_CONSHDLRUSENORM, NULL, NULL) );
4675 	
4676 	   SCIP_CALL( SCIPaddBoolParam(scip,
4677 	         "separating/" SEPA_NAME "/useobjub",
4678 	         "Use upper bound on objective function (via primal solution)?",
4679 	         &sepadata->useobjub, FALSE, DEFAULT_USEOBJUB, NULL, NULL) );
4680 	
4681 	   SCIP_CALL( SCIPaddBoolParam(scip,
4682 	         "separating/" SEPA_NAME "/useobjlb",
4683 	         "Use lower bound on objective function (via primal solution)?",
4684 	         &sepadata->useobjlb, FALSE, DEFAULT_USEOBJLB, NULL, NULL) );
4685 	
4686 	   SCIP_CALL( SCIPaddBoolParam(scip,
4687 	         "separating/" SEPA_NAME "/subscipfast",
4688 	         "Should the settings for the sub-MIP be optimized for speed?",
4689 	         &sepadata->subscipfast, FALSE, DEFAULT_SUBSCIPFAST, NULL, NULL) );
4690 	
4691 	   SCIP_CALL( SCIPaddBoolParam(scip,
4692 	         "separating/" SEPA_NAME "/output",
4693 	         "Should information about the sub-MIP and cuts be displayed?",
4694 	         &sepadata->output, FALSE, DEFAULT_OUTPUT, NULL, NULL) );
4695 	
4696 	   SCIP_CALL( SCIPaddBoolParam(scip,
4697 	         "separating/" SEPA_NAME "/genprimalsols",
4698 	         "Try to generate primal solutions from Gomory cuts?",
4699 	         &sepadata->genprimalsols, FALSE, DEFAULT_GENPRIMALSOLS, NULL, NULL) );
4700 	
4701 	   return SCIP_OKAY;
4702 	}
4703