1    	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2    	/*                                                                           */
3    	/*                  This file is part of the program and library             */
4    	/*         SCIP --- Solving Constraint Integer Programs                      */
5    	/*                                                                           */
6    	/*  Copyright (c) 2002-2023 Zuse Institute Berlin (ZIB)                      */
7    	/*                                                                           */
8    	/*  Licensed under the Apache License, Version 2.0 (the "License");          */
9    	/*  you may not use this file except in compliance with the License.         */
10   	/*  You may obtain a copy of the License at                                  */
11   	/*                                                                           */
12   	/*      http://www.apache.org/licenses/LICENSE-2.0                           */
13   	/*                                                                           */
14   	/*  Unless required by applicable law or agreed to in writing, software      */
15   	/*  distributed under the License is distributed on an "AS IS" BASIS,        */
16   	/*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17   	/*  See the License for the specific language governing permissions and      */
18   	/*  limitations under the License.                                           */
19   	/*                                                                           */
20   	/*  You should have received a copy of the Apache-2.0 license                */
21   	/*  along with SCIP; see the file LICENSE. If not visit scipopt.org.         */
22   	/*                                                                           */
23   	/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24   	
25   	/**@file   sepa_oddcycle.c
26   	 * @ingroup DEFPLUGINS_SEPA
27   	 * @brief  oddcycle separator
28   	 * @author Robert Waniek
29   	 * @author Marc Pfetsch
30   	 *
31   	 * We separate odd cycle inequalities in the implication graph. Implemented are the classic method
32   	 * by Groetschel, Lovasz, and Schrijver (GLS) and the levelgraph method by Hoffman and Padberg (HP)
33   	 *
34   	 * Odd cycle inequalities are lifted by a heuristic method based on an idea from Alvarez-Valdes,
35   	 * Parreno, and Tamarit.
36   	 *
37   	 * Some part of this code is based on the odd cycle separator of the program colorbitopt by Marc
38   	 * Pfetsch.
39   	 */
40   	
41   	/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
42   	
43   	#include <assert.h>
44   	#include <string.h>
45   	
46   	#include "blockmemshell/memory.h"
47   	#include "dijkstra/dijkstra.h"
48   	#include "scip/pub_implics.h"
49   	#include "scip/pub_lp.h"
50   	#include "scip/pub_message.h"
51   	#include "scip/pub_misc.h"
52   	#include "scip/pub_misc_sort.h"
53   	#include "scip/pub_sepa.h"
54   	#include "scip/pub_tree.h"
55   	#include "scip/pub_var.h"
56   	#include "scip/scip_branch.h"
57   	#include "scip/scip_cut.h"
58   	#include "scip/scip_general.h"
59   	#include "scip/scip_lp.h"
60   	#include "scip/scip_mem.h"
61   	#include "scip/scip_message.h"
62   	#include "scip/scip_numerics.h"
63   	#include "scip/scip_param.h"
64   	#include "scip/scip_prob.h"
65   	#include "scip/scip_sepa.h"
66   	#include "scip/scip_sol.h"
67   	#include "scip/scip_solvingstats.h"
68   	#include "scip/scip_tree.h"
69   	#include "scip/scip_var.h"
70   	#include "scip/sepa_oddcycle.h"
71   	#include <string.h>
72   	
73   	#define SEPA_NAME              "oddcycle"
74   	#define SEPA_DESC              "odd cycle separator"
75   	#define SEPA_PRIORITY            -15000
76   	#define SEPA_FREQ                    -1
77   	#define SEPA_MAXBOUNDDIST           1.0
78   	#define SEPA_USESSUBSCIP          FALSE      /**< does the separator use a secondary SCIP instance? */
79   	#define SEPA_DELAY                FALSE      /**< should separation method be delayed, if other separators found cuts? */
80   	
81   	
82   	/* default values for separator settings */
83   	#define DEFAULT_SCALEFACTOR        1000      /**< factor for scaling of the arc-weights in the Dijkstra algorithm */
84   	#define DEFAULT_USEGLS             TRUE      /**< use GLS method, otherwise HP method */
85   	#define DEFAULT_LIFTODDCYCLES     FALSE      /**< lift odd cycle cuts */
86   	#define DEFAULT_REPAIRCYCLES       TRUE      /**< try to repair violated cycles in which a variable and its negated appear */
87   	#define DEFAULT_ADDSELFARCS        TRUE      /**< add links between a variable and its negated */
88   	#define DEFAULT_INCLUDETRIANGLES   TRUE      /**< separate triangles (3-cliques) found as 3-cycles or repaired larger cycles */
89   	#define DEFAULT_MULTIPLECUTS      FALSE      /**< still try variable as start, even if it is already covered by a cut */
90   	#define DEFAULT_ALLOWMULTIPLECUTS  TRUE      /**< allow another inequality to use variable, even if it is already covered */
91   	#define DEFAULT_LPLIFTCOEF        FALSE      /**< TRUE: choose lifting candidate with highest value of coefficient*lpvalue
92   	                                              *   FALSE: choose lifting candidate with highest coefficient */
93   	#define DEFAULT_RECALCLIFTCOEF     TRUE      /**< whether lifting coefficients should be recomputed */
94   	#define DEFAULT_MAXSEPACUTS        5000      /**< maximal number of oddcycle cuts separated per separation round */
95   	#define DEFAULT_MAXSEPACUTSROOT    5000      /**< maximal number of oddcycle cuts separated per separation round in root node */
96   	#define DEFAULT_PERCENTTESTVARS       0      /**< percent of variables to try the chosen method on [0-100] */
97   	#define DEFAULT_OFFSETTESTVARS      100      /**< offset of variables to try the chosen method on */
98   	#define DEFAULT_MAXCUTSROOT           1      /**< maximal number of oddcycle cuts generated per root of the levelgraph */
99   	#define DEFAULT_SORTSWITCH            3      /**< unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4) */
100  	#define DEFAULT_MAXREFERENCE          0      /**< minimal weight on an edge (in level graph or Dijkstra graph) */
101  	#define DEFAULT_MAXROUNDS            10      /**< maximal number of rounds pre node */
102  	#define DEFAULT_MAXROUNDSROOT        10      /**< maximal number of rounds in the root node */
103  	#define DEFAULT_MAXNLEVELS           20      /**< maximal number of levels in level graph */
104  	#define DEFAULT_MAXPERNODESLEVEL    100      /**< maximal percentage of nodes allowed in one level of the levelgraph [0-100] */
105  	#define DEFAULT_OFFSETNODESLEVEL     10      /**< additional offset of nodes allowed in one level of the levelgraph */
106  	#define DEFAULT_SORTROOTNEIGHBORS  TRUE      /**< sort neighbors of the root in the level graph */
107  	#define DEFAULT_MAXCUTSLEVEL         50      /**< maximal number of cuts produced per level */
108  	#define DEFAULT_MAXUNSUCESSFULL       3      /**< maximal number of unsuccessful calls at each node */
109  	#define DEFAULT_CUTTHRESHOLD         -1      /**< maximal number of other cuts s.t. separation is applied (-1 for direct call) */
110  	
111  	
112  	/*
113  	 * Data structures
114  	 */
115  	
116  	/** Graph structure for level graph
117  	 *
118  	 *  This graph is tailored to the heuristic search for odd holes, @see separateHeur().
119  	 *
120  	 *  This undirected graph is represented by a directed graph with forward and backward arcs. Arcs are
121  	 *  forward if they lead from a level l to level l+1, i.e., away from the root; backward arcs
122  	 *  lead from a level l+1 to level l. This distinction enables a fast construction and search
123  	 *  process. In the latter only forward or backward arcs have to be searched.
124  	 *
125  	 *  Target nodes and weights of the arcs incident to each node (adjacency lists) are stored
126  	 *  consecutively in the arrays targetForward, targetBackward, weightForward, and weightBackward.
127  	 *  The end of each list is marked by a -1 in targetForward and targetBackward.
128  	 */
129  	struct levelGraph
130  	{
131  	   unsigned int          nnodes;             /**< number of nodes */
132  	   unsigned int          narcs;              /**< number of arcs */
133  	   unsigned int          maxnodes;           /**< maximal number of nodes of the level graph */
134  	   unsigned int          maxarcs;            /**< maximal number of arcs of the level graph */
135  	   unsigned int          nlevels;            /**< number of levels completely inserted so far */
136  	   unsigned int*         level;              /**< level number for each node */
137  	   unsigned int          lastF;              /**< last storage element index in targetForward, weightForward - forward direction */
138  	   unsigned int          lastB;              /**< last storage element index in targetBackward, weightBackward - backward direction */
139  	   int*                  beginForward;       /**< forward adjacency list index in targetForward, weightForward for each node */
140  	   int*                  beginBackward;      /**< backward adjacency list index in targetBackward, weightBackward for each node */
141  	   int*                  targetForward;      /**< target nodes of forward arcs */
142  	   int*                  targetBackward;     /**< target nodes of backward arcs */
143  	   unsigned int*         weightForward;      /**< weights of forward arcs */
144  	   unsigned int*         weightBackward;     /**< weights of backwards arcs */
145  	   unsigned int          sizeForward;        /**< size of targetForward and weightForward */
146  	   unsigned int          sizeBackward;       /**< size of targetBackward and weightBackward */
147  	   int*                  beginAdj;           /**< index of list of arcs inside a level (in sourceAdj) for each node
148  	                                              *   (the index points at the first arc starting from this node) */
149  	   unsigned int*         sourceAdj;          /**< source nodes of arcs inside a level */
150  	   unsigned int*         targetAdj;          /**< target nodes of arcs inside a level */
151  	   unsigned int*         weightAdj;          /**< weights of arcs inside a level */
152  	   unsigned int*         levelAdj;           /**< index of the first arc inside a given level */
153  	   unsigned int          sizeAdj;            /**< size of sourceAdj, targetAdj and weightAdj */
154  	};
155  	
156  	typedef struct levelGraph LEVELGRAPH;
157  	
158  	
159  	/** sorting type for starting node or root node iteration order
160  	 *
161  	 *  If the array should be sorted (1-4), the variable array is sorted every round by the chosen
162  	 *  sorttype and the search method tries the nodes in order of the array.  If the array is used
163  	 *  unsorted (0), the search methods tries the nodes in order of the array and stores the last
164  	 *  processed start node or root node and continues from this position in the next separation round.
165  	 */
166  	enum sorttype
167  	{
168  	   UNSORTED              = 0,                /**< variable array is unsorted */
169  	   MAXIMAL_LPVALUE       = 1,                /**< variable array is sorted by maximal lp-value */
170  	   MINIMAL_LPVALUE       = 2,                /**< variable array is sorted by minimal fractionality */
171  	   MAXIMAL_FRACTIONALITY = 3,                /**< variable array is sorted by maximal lp-value */
172  	   MINIMAL_FRACTIONALITY = 4                 /**< variable array is sorted by minimal fractionality */
173  	};
174  	typedef enum sorttype SORTTYPE;
175  	
176  	/** auxiliary data structure for passing graphs */
177  	struct GraphData
178  	{
179  	   SCIP_Bool             usegls;             /**< Use GLS algorithm? If true, dijstragraph != NULL should hold, otherwise levelgraph != NULL */
180  	   LEVELGRAPH*           levelgraph;         /**< level graph when using HP method, NULL otherwise */
181  	   DIJKSTRA_GRAPH*       dijkstragraph;      /**< Dijkstra graph if using method by GLS, NULL otherwise */
182  	};
183  	typedef struct GraphData GRAPHDATA;
184  	
185  	/** separator data */
186  	struct SCIP_SepaData
187  	{
188  	   int                   scale;              /**< factor for scaling of the arc-weights */
189  	   unsigned int          ncuts;              /**< number of cuts, added by the separator so far (in current and past calls) */
190  	   unsigned int          oldncuts;           /**< number of cuts at the start the current separation round */
191  	   int                   nliftedcuts;        /**< number of lifted cuts, added by the separator so far (in current and past calls) */
192  	   SCIP_Bool             usegls;             /**< use GLS method, otherwise HP method */
193  	   SCIP_Bool             multiplecuts;       /**< an odd cycle cut of length L can be generated L times; forbidding multiple cuts
194  	                                              *   per node might be faster but might miss some cuts in the current round */
195  	   SCIP_Bool             allowmultiplecuts;  /**< allow multiple cuts covering one node */
196  	   SCIP_Bool             liftoddcycles;      /**< TRUE, iff we try to lift odd cycle inequalities */
197  	   SCIP_Bool             addselfarcs;        /**< add arcs between the nodes of a variable and its negated; since not all implications
198  	                                              *   are in the graph, this often finds more cycles */
199  	   SCIP_Bool             repaircycles;       /**< if a variable and its negated appear in a cycle, we can repair the cycle
200  	                                              *   by removing both and reconnecting the remaining nodes of the cycle */
201  	   SCIP_Bool             includetriangles;   /**< handle triangles found as 3-cycles or repaired larger cycles */
202  	   unsigned int*         mapping;            /**< mapping for getting the index of a variable in the sorted variable array */
203  	   SCIP_Bool             lpliftcoef;         /**< TRUE: choose lifting candidate with highest value of coefficient*lpvalue
204  	                                              *   FALSE: choose lifting candidate with highest coefficient */
205  	   SCIP_Bool             recalcliftcoef;     /**< whether lifting coefficients should be recomputed */
206  	   int                   maxsepacuts;        /**< max. number of oddcycle cuts separated per separation round */
207  	   int                   maxsepacutsroot;    /**< max. number of oddcycle cuts separated per separation round in the root node */
208  	   int                   maxsepacutsround;   /**< max. number of oddcycle cuts separated per separation round in the current node */
209  	   SORTTYPE              sortswitch;         /**< sorted type: unsorted (0), maxlp (1), minlp (2), maxfrac (3), minfrac (4) */
210  	   int                   lastroot;           /**< save root of last GLS-method run */
211  	   SCIP_Bool             sortrootneighbors;  /**< sort neighbors of the root in the level graph */
212  	   int                   percenttestvars;    /**< percentage of variables to try the chosen method on [0-100] */
213  	   int                   offsettestvars;     /**< offset of variables to try the chosen method on */
214  	   int                   maxpernodeslevel;   /**< percentage of nodes allowed in the same level of the level graph [0-100] */
215  	   int                   offsetnodeslevel;   /**< additional offset of nodes allowed in one level of the levelgraph */
216  	   unsigned int          maxlevelsize;       /**< maximal number of nodes allowed in the same level of the level graph */
217  	   int                   maxcutsroot;        /**< maximal number of oddcycle cuts generated per root of the levelgraph */
218  	   int                   maxcutslevel;       /**< maximal number of oddcycle cuts generated per level of the level graph */
219  	   int                   maxrounds;          /**< maximal number of oddcycle separation rounds per node (-1: unlimited) */
220  	   int                   maxroundsroot;      /**< maximal number of oddcycle separation rounds in the root node (-1: unlimited) */
221  	   int                   maxreference;       /**< minimal weight on an edge (in level graph or Dijkstra graph) */
222  	   int                   maxnlevels;         /**< maximal number of levels in level graph */
223  	   int                   maxunsucessfull;    /**< maximal number of unsuccessful calls at each node */
224  	   int                   nunsucessfull;      /**< number of unsuccessful calls at current node */
225  	   int                   cutthreshold;       /**< maximal number of other cuts s.t. separation is applied (-1 for direct call) */
226  	   SCIP_Longint          lastnode;           /**< number of last node */
227  	};
228  	
229  	
230  	/*
231  	 * debugging methods
232  	 */
233  	
234  	#ifdef SCIP_OUTPUT
235  	
236  	/** displays cycle of pred data structure w.r.t. variable names of the original problem (including
237  	 *  status: original or negated node in graph)
238  	 */
239  	static
240  	void printCycle(
241  	   SCIP_VAR**            vars,               /**< problem variables */
242  	   unsigned int*         pred,               /**< cycle stored as predecessor list */
243  	   unsigned int          nbinvars,           /**< number of binary problem variables */
244  	   unsigned int          startnode           /**< a node of the cycle */
245  	   )
246  	{
247  	   unsigned int varsindex;
248  	   unsigned int counter;
249  	
250  	   assert(vars != NULL);
251  	   assert(pred != NULL);
252  	   assert(nbinvars > 0);
253  	   assert(startnode < 4*nbinvars);
254  	
255  	   counter = 0;
256  	   varsindex = startnode;
257  	
258  	   /* print start/end node */
259  	   if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) )
260  	   {
261  	      SCIPdebugMsg(scip, "+ %s\n",SCIPvarGetName(vars[varsindex%nbinvars]));
262  	   }
263  	   else
264  	   {
265  	      SCIPdebugMsg(scip, "- %s\n",SCIPvarGetName(vars[varsindex%nbinvars]));
266  	   }
267  	
268  	   /* print inner nodes */
269  	   for( varsindex = pred[startnode]; varsindex != startnode; varsindex = pred[varsindex] )
270  	   {
271  	      if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) )
272  	      {
273  	         SCIPdebugMsg(scip, "+ %s\n",SCIPvarGetName(vars[varsindex%nbinvars]));
274  	      }
275  	      else
276  	      {
277  	         SCIPdebugMsg(scip, "- %s\n",SCIPvarGetName(vars[varsindex%nbinvars]));
278  	      }
279  	      ++counter;
280  	   }
281  	
282  	   /* print start/end node */
283  	   if( varsindex < nbinvars || ( varsindex >= 2*nbinvars && varsindex < 3*nbinvars ) )
284  	   {
285  	      SCIPdebugMsg(scip, "+ %s\n",SCIPvarGetName(vars[varsindex%nbinvars]));
286  	   }
287  	   else
288  	   {
289  	      SCIPdebugMsg(scip, "- %s\n",SCIPvarGetName(vars[varsindex%nbinvars]));
290  	   }
291  	
292  	   ++counter;
293  	   SCIPdebugMsg(scip, "original cycle has %u variables.\n", counter);
294  	}
295  	#endif
296  	
297  	
298  	/*
299  	 * lifting methods
300  	 */
301  	
302  	/** using the level graph (if possible) or Dijkstra graph data structure (depending on the used
303  	 *  method) we determine whether two nodes are adjacent
304  	 */
305  	static
306  	SCIP_Bool isNeighbor(
307  	   SCIP_VAR**            vars,               /**< problem variables */
308  	   unsigned int          nbinvars,           /**< number of binary problem variables */
309  	   GRAPHDATA*            graphdata,          /**< graph */
310  	   unsigned int          a,                  /**< node index of first variable */
311  	   unsigned int          b                   /**< node index of second variable */
312  	   )
313  	{
314  	   unsigned int i;
315  	
316  	   assert(vars != NULL);
317  	   assert(nbinvars > 2);
318  	   assert(graphdata != NULL);
319  	   assert(graphdata->levelgraph != NULL || graphdata->usegls);
320  	   assert(graphdata->dijkstragraph != NULL || ! graphdata->usegls);
321  	   assert(a < 2*nbinvars);
322  	   assert(b < 2*nbinvars);
323  	   assert(a != b);
324  	
325  	   /* determine adjacency using the Dijkstra graph */
326  	   if( graphdata->usegls )
327  	   {
328  	      DIJKSTRA_GRAPH* dijkstragraph = graphdata->dijkstragraph;
329  	      if( dijkstragraph->outcnt[a] == 0 || dijkstragraph->outcnt[b] == 0 )
330  	         return FALSE;
331  	
332  	      /* @todo later: if helpful: sort head and weight list once */
333  	      for( i = dijkstragraph->outbeg[a]; i < dijkstragraph->outbeg[a] + dijkstragraph->outcnt[a]; ++i )
334  	      {
335  	         if( dijkstragraph->head[i] == b + 2*nbinvars )
336  	            return TRUE;
337  	      }
338  	   }
339  	   else    /* determine adjacency using the level graph */
340  	   {
341  	      LEVELGRAPH* levelgraph = graphdata->levelgraph;
342  	
343  	      /* if a and b are contained in the level graph (with their arcs), we can check inside the level graph structure */
344  	      if( (levelgraph->beginForward[a] != -1 || levelgraph->beginBackward[a] != -1)
345  	         && (levelgraph->beginForward[b] != -1 || levelgraph->beginBackward[b] != -1) )
346  	      {
347  	         assert(levelgraph->level[a] <= levelgraph->nlevels);
348  	         assert(levelgraph->level[b] <= levelgraph->nlevels);
349  	
350  	         /* if a and b are not in neighbored levels or the same level, they cannot be adjacent */
351  	         if( levelgraph->level[a] > levelgraph->level[b] + 1
352  	            || levelgraph->level[b] > levelgraph->level[a] + 1 )
353  	            return FALSE;
354  	
355  	         assert(levelgraph->level[a] == levelgraph->level[b]
356  	            || levelgraph->level[a]+1 == levelgraph->level[b]
357  	            || levelgraph->level[a] == levelgraph->level[b]+1);
358  	
359  	         /* first case of adjacent level */
360  	         if( levelgraph->level[a] == levelgraph->level[b]+1 )
361  	         {
362  	            if( levelgraph->beginBackward[a] >= 0 )
363  	            {
364  	               i = (unsigned int) levelgraph->beginBackward[a];
365  	               while( levelgraph->targetBackward[i] != -1 )
366  	               {
367  	                  if( levelgraph->targetBackward[i] == (int)b )
368  	                     return TRUE;
369  	                  ++i;
370  	               }
371  	            }
372  	         }
373  	         else if( levelgraph->level[a] == levelgraph->level[b]-1 )    /* second case of adjacent level */
374  	         {
375  	            if( levelgraph->beginForward[a] >= 0 )
376  	            {
377  	               i = (unsigned int) levelgraph->beginForward[a];
378  	               while( levelgraph->targetForward[i] != -1 )
379  	               {
380  	                  if( levelgraph->targetForward[i] == (int)b )
381  	                     return TRUE;
382  	                  ++i;
383  	               }
384  	            }
385  	         }
386  	         else          /* same level (note that an edge between a and b is stored for a if a < b, otherwise it is stored for b) */
387  	         {
388  	            assert(levelgraph->level[a] == levelgraph->level[b]);
389  	            assert(levelgraph->level[a] > 0); /* root has no neighbor in the same level */
390  	
391  	            if( a < b && levelgraph->beginAdj[a] >= 0 )
392  	            {
393  	               i = (unsigned int) levelgraph->beginAdj[a];
394  	               assert(i >= levelgraph->levelAdj[levelgraph->level[a]]);
395  	
396  	               while( i < levelgraph->levelAdj[levelgraph->level[a]+1] && levelgraph->sourceAdj[i] == a )
397  	               {
398  	                  if( levelgraph->targetAdj[i] == b )
399  	                     return TRUE;
400  	
401  	                  /* if adjacency list ends we are done and a and b are not adjacent */
402  	                  if( levelgraph->sourceAdj[i] == 0 && levelgraph->targetAdj[i] == 0 )
403  	                     return FALSE;
404  	
405  	                  assert(levelgraph->sourceAdj[i] < levelgraph->targetAdj[i]);
406  	                  ++i;
407  	               }
408  	            }
409  	            if( b < a && levelgraph->beginAdj[b] >= 0 )
410  	            {
411  	               i = (unsigned int) levelgraph->beginAdj[b];
412  	               assert(i >= levelgraph->levelAdj[levelgraph->level[b]]);
413  	
414  	               while( i < levelgraph->levelAdj[levelgraph->level[b]+1] && levelgraph->sourceAdj[i] == b )
415  	               {
416  	                  if( levelgraph->targetAdj[i] == a )
417  	                     return TRUE;
418  	
419  	                  /* if adjacency list ends we are done and a and b are not adjacent */
420  	                  if( levelgraph->sourceAdj[i] == 0 && levelgraph->targetAdj[i] == 0 )
421  	                     return FALSE;
422  	
423  	                  assert(levelgraph->sourceAdj[i] < levelgraph->targetAdj[i]);
424  	                  ++i;
425  	               }
426  	            }
427  	         }
428  	      }
429  	      /* if a or b is not in the levels already completely inserted in the levelgraph, we check
430  	       * their adjacency by the SCIP data structures
431  	       */
432  	      else
433  	      {
434  	         SCIP_CLIQUE** cliques;
435  	         SCIP_VAR** cliquevars;
436  	         SCIP_Bool* cliquevals;
437  	         SCIP_Bool originala;
438  	         SCIP_Bool originalb;
439  	         unsigned int ncliques;
440  	         unsigned int ncliquevars;
441  	         unsigned int j;
442  	
443  	         /* get original variables */
444  	         originala = TRUE;
445  	         if( a >= nbinvars )
446  	         {
447  	            a = a - nbinvars;
448  	            originala = FALSE;
449  	         }
450  	         assert(a < nbinvars);
451  	
452  	         originalb = TRUE;
453  	         if( b >= nbinvars )
454  	         {
455  	            b = b - nbinvars;
456  	            originalb = FALSE;
457  	         }
458  	         assert(b < nbinvars);
459  	
460  	         /* nodes cannot be connected by trivial observations */
461  	         if( SCIPvarGetNCliques(vars[a], originala) == 0 || SCIPvarGetNCliques(vars[b], originalb) == 0 )
462  	            return FALSE;
463  	
464  	         /* @todo later: possible improvement: do this test for implications and cliques separately if this here is time consuming */
465  	         /* one of the nodes seems to have more arcs than the other, we swap them (since adjacency is symmetric) */
466  	         if( SCIPvarGetNCliques(vars[a], originala) > SCIPvarGetNCliques(vars[b], originalb) )
467  	         {
468  	            unsigned int temp;
469  	            SCIP_Bool varfixingtemp;
470  	
471  	            temp = b;
472  	            varfixingtemp = originalb;
473  	            b = a;
474  	            originalb = originala;
475  	            a = temp;
476  	            originala = varfixingtemp;
477  	         }
478  	
479  	         /* check whether a and b are contained in a clique */
480  	         ncliques =  (unsigned int) SCIPvarGetNCliques(vars[a], originala);
481  	         cliques = SCIPvarGetCliques(vars[a], originala);
482  	
483  	         assert(cliques != NULL || ncliques == 0);
484  	
485  	         for( i = 0; i < ncliques; ++i )
486  	         {
487  	            assert( cliques != NULL );  /* for lint */
488  	            ncliquevars = (unsigned int) SCIPcliqueGetNVars(cliques[i]);
489  	            cliquevars = SCIPcliqueGetVars(cliques[i]);
490  	            cliquevals = SCIPcliqueGetValues(cliques[i]);
491  	
492  	            assert(cliquevars != NULL || ncliquevars == 0);
493  	            assert(cliquevals != NULL || ncliquevars == 0);
494  	
495  	            for( j = 0; j < ncliquevars; ++j )
496  	            {
497  	               assert( cliquevals != NULL &&  cliquevars != NULL ); /* for lint */
498  	               if( SCIPvarGetProbindex(vars[b]) == SCIPvarGetProbindex(cliquevars[j]) )
499  	               {
500  	                  if( (cliquevals[j] == FALSE && originalb == TRUE) || ( cliquevals[j] == TRUE && originalb == FALSE ) )
501  	                     return TRUE;
502  	               }
503  	            }
504  	         }
505  	      }
506  	   }
507  	
508  	   return FALSE;
509  	}
510  	
511  	/** inside the lifting heuristic we determine the lifting coefficient by counting the length of
512  	 *  chains adjacent to the lifting candidate.
513  	 *
514  	 *  since we have to exclude all chains adjacent to an already lifted node which is not adjacent to
515  	 *  the current lifting candidate we check all chains of the cycle of length three and block them if
516  	 *  they are adjacent.
517  	 */
518  	static
519  	void checkBlocking(
520  	   unsigned int          a,                  /**< first node of the checked cycle chain of length 3 */
521  	   unsigned int          b,                  /**< second node of the checked cycle chain of length 3 */
522  	   unsigned int          c,                  /**< third node of the checked cycle chain of length 3 */
523  	   unsigned int          i,                  /**< current lifting candidate */
524  	   unsigned int*         cycle,              /**< list of cycle nodes in order of the cycle */
525  	   unsigned int          ncyclevars,         /**< number of variables in the odd cycle */
526  	   SCIP_VAR**            vars,               /**< problem variables */
527  	   unsigned int          nbinvars,           /**< number of binary problem variables */
528  	   unsigned int*         lifted,             /**< list of lifted nodes */
529  	   unsigned int*         nlifted,            /**< number of lifted nodes */
530  	   GRAPHDATA*            graphdata,          /**< graph */
531  	   SCIP_Bool*            myi                 /**< flag array, if cycle node is inner point of a counted chain */
532  	   )
533  	{
534  	   unsigned int k;
535  	
536  	   assert(a < ncyclevars);
537  	   assert(b < ncyclevars);
538  	   assert(c < ncyclevars);
539  	   assert(cycle != NULL);
540  	   assert(ncyclevars % 2 == 1);
541  	   assert(ncyclevars > 2);
542  	   assert(ncyclevars <= nbinvars);
543  	   assert(vars != NULL);
544  	   assert(nbinvars > 2);
545  	   assert(lifted != NULL);
546  	   assert(nlifted != NULL);
547  	   assert(myi != NULL);
548  	
549  	   k = 0;
550  	   while( (myi[a] || myi[b] || myi[c]) && k < *nlifted )
551  	   {
552  	      /* if all three nodes are adjacent to a node which is already lifted and not adjacent with the
553  	       * current lifting candidate, they cannot be regarded */
554  	      if( !isNeighbor(vars, nbinvars, graphdata, i, lifted[k])
555  	         && isNeighbor(vars, nbinvars, graphdata, cycle[a], lifted[k])
556  	         && isNeighbor(vars, nbinvars, graphdata, cycle[b], lifted[k])
557  	         && isNeighbor(vars, nbinvars, graphdata, cycle[c], lifted[k]) )
558  	      {
559  	         myi[a] = FALSE;
560  	         myi[b] = FALSE;
561  	         myi[c] = FALSE;
562  	      }
563  	      ++k;
564  	   }
565  	}
566  	
567  	/** determine the heuristic lifting coefficient by counting the length of the adjacent chains of the
568  	 *  candidate (we have to exclude all chains that are adjacent to an already lifted node which is
569  	 *  not adjacent to the current candidate)
570  	 */
571  	static
572  	unsigned int getCoef(
573  	   SCIP*                 scip,               /**< SCIP data structure */
574  	   unsigned int          i,                  /**< current lifting candidate */
575  	   unsigned int*         cycle,              /**< list of cycle nodes in order of the cycle */
576  	   unsigned int          ncyclevars,         /**< number of variables in the odd cycle */
577  	   SCIP_VAR**            vars,               /**< problem variables */
578  	   unsigned int          nbinvars,           /**< number of binary problem variables */
579  	   unsigned int*         lifted,             /**< list of lifted nodes */
580  	   unsigned int*         nlifted,            /**< number of lifted nodes */
581  	   GRAPHDATA*            graphdata,          /**< graph data structure */
582  	   SCIP_Bool*            myi                 /**< flag array, if cycle node is inner point of a counted chain */
583  	   )
584  	{
585  	   int j;
586  	   unsigned int k;
587  	   unsigned int coef;                        /* coefficient of lifting candidate of the current step */
588  	   unsigned int end;
589  	
590  	   assert(scip != NULL);
591  	   assert(i < 2*nbinvars);
592  	   assert(cycle != NULL);
593  	   assert(ncyclevars % 2 == 1);
594  	   assert(ncyclevars > 2);
595  	   assert(ncyclevars <= 2*nbinvars);
596  	   assert(vars != NULL);
597  	   assert(nbinvars > 2);
598  	   assert(nlifted != NULL);
599  	   assert(lifted != NULL);
600  	
601  	   coef = 0;
602  	
603  	   /* get inner nodes of adjacent chains in cycle */
604  	   for( j = 1; j < (int)ncyclevars-1; ++j )
605  	   {
606  	      myi[j] = isNeighbor(vars, nbinvars, graphdata, i, cycle[j-1]) && isNeighbor(vars, nbinvars, graphdata, i, cycle[j])
607  	         && isNeighbor(vars, nbinvars, graphdata, i, cycle[j+1]);
608  	   }
609  	
610  	   /* the first and last node of the cycle are treated separately */
611  	   myi[0] = isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-1])
612  	      && isNeighbor(vars, nbinvars, graphdata, i, cycle[0])
613  	      && isNeighbor(vars, nbinvars, graphdata, i, cycle[1]);
614  	   myi[ncyclevars-1] = isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-2])
615  	      && isNeighbor(vars, nbinvars, graphdata, i, cycle[ncyclevars-1])
616  	      && isNeighbor(vars, nbinvars, graphdata, i, cycle[0]);
617  	
618  	   /* consider already lifted nodes that are not adjacent to current lifting candidate and
619  	    * remove all inner cycle nodes that are adjacent to them
620  	    */
621  	   for( j = 1; j < (int)ncyclevars-1; ++j )
622  	   {
623  	      checkBlocking((unsigned int) (j-1), (unsigned int) j, (unsigned int) (j+1), i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
624  	   }
625  	   checkBlocking(ncyclevars-2, ncyclevars-1, 0, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
626  	   checkBlocking(ncyclevars-1, 0, 1, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
627  	
628  	   /* calculate lifting coefficient */
629  	   k = 0;
630  	
631  	   /* first, handle the special case, that the first node of the cycle list is part of a chain */
632  	   if( myi[0] )
633  	   {
634  	      ++k;
635  	      end = ncyclevars-1;
636  	      while( myi[end] && end > 0 )
637  	      {
638  	         ++k;
639  	         --end;
640  	      }
641  	      assert(k == ncyclevars || end > 0);
642  	
643  	      /* all cycle nodes build a relevant chain (maximal chain s.t. all inner nodes are in myi) */
644  	      if( end == 0 )
645  	      {
646  	         assert(ncyclevars % 2 == 1);
647  	         coef = (ncyclevars-1)/2;
648  	         return coef;
649  	      }
650  	      assert(!myi[end]);
651  	
652  	      /* current nonempty relevant chain cannot be extended */
653  	      if( !myi[1] )
654  	      {
655  	         coef = (unsigned int) SCIPfloor(scip,(k+1.0)/2.0);
656  	         assert(coef <= (ncyclevars-1)/2);
657  	         k = 0;
658  	      }
659  	   }
660  	   else
661  	      end = ncyclevars;
662  	
663  	   /* find remaining relevant chains */
664  	   j = 1;
665  	   while( j < (int)end )
666  	   {
667  	      /* skip all nodes that are not inner node */
668  	      while( j<(int)end && ! myi[j] )
669  	         ++j;
670  	
671  	      /* collect all inner nodes (chain is extended) */
672  	      while( j<(int)end && myi[j] )
673  	      {
674  	         ++k;
675  	         ++j;
676  	      }
677  	
678  	      if( k > 0 )
679  	      {
680  	         assert(myi[j-1]);
681  	         coef += (unsigned int) SCIPfloor(scip,(k+1.0)/2.0);
682  	         assert(coef <= (ncyclevars-1)/2);
683  	         k = 0;
684  	      }
685  	   }
686  	
687  	   return coef;
688  	}
689  	
690  	/** Lifting Heuristic based on an idea by Alvarez-Valdes, Parreno, Tamarit
691  	 *
692  	 *  This method is based on the observation, that a non-cycle node can be lifted into the inequality
693  	 *  with coefficient \f$1\f$ if the node is adjacent to the nodes of a 3-chain on the cycle.
694  	 *
695  	 *  The coefficient can be calculated as
696  	 *  \f$\left\lfloor{\frac{|C|-1}{2}}\right\rfloor\f$
697  	 *  where \f$C\f$ is the chain on the cycle.
698  	 *
699  	 *  If the node is connected to several chains, the coefficients of the chains can be summed up, resulting
700  	 *  in a feasible lifting coefficient.
701  	 *
702  	 *  Additionally further variables can be lifted by considering chains connected to the additional lifting node
703  	 *  which are not connected to already lifted nodes.
704  	 *
705  	 *  This method is a feasible heuristic which gives a valid lifted inequality.
706  	 *  (Furthermore the first lifting coefficient is always smaller or equal to the largest possible lifting coefficient.)
707  	 */
708  	static
709  	SCIP_RETCODE liftOddCycleCut(
710  	   SCIP*                 scip,               /**< SCIP data structure */
711  	   unsigned int*         nlifted,            /**< number of lifted variables */
712  	   unsigned int*         lifted,             /**< indices of the lifted variables */
713  	   unsigned int*         liftcoef,           /**< lifting coefficients */
714  	   SCIP_SEPADATA*        sepadata,           /**< separator data structure */
715  	   GRAPHDATA*            graphdata,          /**< graph */
716  	   SCIP_VAR**            vars,               /**< problem variables */
717  	   unsigned int          nbinvars,           /**< number of binary problem variables */
718  	   unsigned int          startnode,          /**< a node of the cycle */
719  	   unsigned int*         pred,               /**< predecessor of each node (original and negated) in odd cycle */
720  	   unsigned int          ncyclevars,         /**< number of variables in the odd cycle */
721  	   SCIP_Real*            vals,               /**< values of the variables in the given solution */
722  	   SCIP_RESULT*          result              /**< pointer to store the result of the separation call */
723  	   )
724  	{
725  	   unsigned int* cycle;                      /* storage for cycle and lifted nodes (and their coefficients) */
726  	   unsigned int* coef;
727  	   SCIP_Bool* candList;                      /* lifting candidate list */
728  	   unsigned int i;
729  	   unsigned int j;
730  	   unsigned int negated;
731  	   int bestcand;
732  	   unsigned int liftround;
733  	   SCIP_Bool* myi;
734  	
735  	   assert(scip != NULL);
736  	   assert(graphdata != NULL);
737  	   assert(graphdata->levelgraph != NULL || graphdata->usegls);
738  	   assert(graphdata->dijkstragraph != NULL || ! graphdata->usegls);
739  	   assert(vars != NULL);
740  	   assert(nbinvars > 2);
741  	   assert(startnode < 2*nbinvars);
742  	   assert(pred != NULL);
743  	   assert(ncyclevars % 2 == 1);
744  	   assert(ncyclevars > 2);
745  	   assert(ncyclevars <= nbinvars);
746  	   assert(result != NULL);
747  	   assert(nlifted != NULL);
748  	   assert(lifted != NULL);
749  	   assert(liftcoef != NULL);
750  	
751  	   /* allocate memory for cycle list */
752  	   SCIP_CALL( SCIPallocBufferArray(scip, &cycle, (int) ncyclevars) );
753  	
754  	   /* transform cycle from predecessor list to array in order of appearance in cycle */
755  	   cycle[0] = startnode;
756  	   j = 1;
757  	   i = pred[startnode];
758  	   while( i != startnode )
759  	   {
760  	      cycle[j] = i;
761  	      i = pred[i];
762  	      ++j;
763  	   }
764  	   assert(j == ncyclevars);
765  	
766  	   /* allocate memory for coefficients of the lifting candidates (used in every step) */
767  	   SCIP_CALL( SCIPallocBufferArray(scip, &coef, (int) (2*nbinvars)) );
768  	
769  	   /* allocate memory candidate list and list of lifted nodes */
770  	   SCIP_CALL( SCIPallocBufferArray(scip, &candList, (int) (2*nbinvars)) );
771  	
772  	   /* allocate memory for counting of chains in getCoef() */
773  	   SCIP_CALL( SCIPallocBufferArray(scip, &myi, (int) ncyclevars) );
774  	
775  	   if( SCIPisStopped(scip) )
776  	      goto TERMINATE;
777  	
778  	   /* initialize candidate list */
779  	   for( i = 0; i < 2*nbinvars; ++i )
780  	      candList[i] = TRUE;
781  	
782  	   /* remove cycle variables and their negated from candidate list */
783  	   for( i = 0; i < ncyclevars; ++i )
784  	   {
785  	      candList[cycle[i]] = FALSE;
786  	      if( cycle[i] >= nbinvars )
787  	         negated = cycle[i] - nbinvars;
788  	      else
789  	         negated = cycle[i] + nbinvars;
790  	      assert(negated < 2*nbinvars);
791  	      candList[negated] = FALSE;
792  	   }
793  	
794  	   /* no candidates lifted so far */
795  	   *nlifted = 0;
796  	   bestcand = 0;
797  	   liftround = 0;
798  	
799  	   /* try lifting as long as we have lifting candidates */
800  	   while( bestcand >= 0 )
801  	   {
802  	      /* in case we use a lifting rule, which does not require the first lifting coefficient of all variables: REMOVE this */
803  	      if( sepadata->recalcliftcoef || liftround == 0 )
804  	      {
805  	         for( i = 0; i < 2*nbinvars; ++i )
806  	         {
807  	            if( candList[i] )
808  	            {
809  	               coef[i] = getCoef(scip, i, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
810  	               assert(coef[i] <= (ncyclevars-1)/2);
811  	               if( coef[i] < 1 )
812  	                  candList[i] = FALSE;
813  	            }
814  	         }
815  	      }
816  	      ++liftround;
817  	      bestcand = -1;
818  	      for( i = 0; i < 2*nbinvars; ++i )
819  	      {
820  	         if( candList[i] )
821  	         {
822  	            /* we want to weight our choice of the lifting node by the value of the current lp solution */
823  	            if( sepadata->lpliftcoef )
824  	            {
825  	               if( bestcand < 0 || coef[i]*vals[i] > coef[bestcand]*vals[bestcand] )
826  	                  bestcand = (int) i;
827  	            }
828  	            /* we only regard the coefficient */
829  	            else
830  	            {
831  	               if( bestcand < 0 || coef[i] > coef[bestcand] )
832  	                  bestcand = (int) i;
833  	            }
834  	         }
835  	      }
836  	
837  	      /* there is at least one lifting variable */
838  	      if( bestcand >= 0 )
839  	      {
840  	         if( !(sepadata->recalcliftcoef) )
841  	            coef[i] = getCoef(scip, (unsigned int) bestcand, cycle, ncyclevars, vars, nbinvars, lifted, nlifted, graphdata, myi);
842  	         assert(coef[bestcand] <= (ncyclevars-1)/2);
843  	         candList[bestcand] = FALSE;
844  	         if( coef[bestcand] > 0 )
845  	         {
846  	            if( bestcand >= (int)nbinvars )
847  	               negated = (unsigned int) bestcand - nbinvars;
848  	            else
849  	               negated = (unsigned int) bestcand + nbinvars;
850  	            assert(negated < 2*nbinvars);
851  	
852  	            candList[negated] = FALSE;
853  	
854  	            assert(*nlifted < nbinvars-ncyclevars);
855  	            lifted[*nlifted] = (unsigned int) bestcand;
856  	            liftcoef[*nlifted] = coef[bestcand];
857  	            ++(*nlifted);
858  	         }
859  	      }
860  	   }
861  	
862  	 TERMINATE:
863  	   /* free temporary memory */
864  	   SCIPfreeBufferArray(scip, &myi);
865  	   SCIPfreeBufferArray(scip, &candList);
866  	   SCIPfreeBufferArray(scip, &coef);
867  	   SCIPfreeBufferArray(scip, &cycle);
868  	
869  	   return SCIP_OKAY;
870  	}
871  	
872  	
873  	/*
874  	 * methods for both techniques
875  	 */
876  	
877  	/** add the inequality corresponding to the given odd cycle to the LP (if violated)
878  	 *  after lifting it (if requested by user flag)
879  	 */
880  	static
881  	SCIP_RETCODE generateOddCycleCut(
882  	   SCIP*                 scip,               /**< SCIP data structure */
883  	   SCIP_SEPA*            sepa,               /**< separator */
884  	   SCIP_SOL*             sol,                /**< given primal solution */
885  	   SCIP_VAR**            vars,               /**< problem variables */
886  	   unsigned int          nbinvars,           /**< number of binary problem variables */
887  	   unsigned int          startnode,          /**< a node of the cycle */
888  	   unsigned int*         pred,               /**< predecessor of each node (original and negated) in odd cycle */
889  	   unsigned int          ncyclevars,         /**< number of variables in the odd cycle */
890  	   unsigned int*         incut,              /**< TRUE iff node is covered already by a cut */
891  	   SCIP_Real*            vals,               /**< values of the variables in the given solution */
892  	   SCIP_SEPADATA*        sepadata,           /**< separator data structure */
893  	   GRAPHDATA*            graphdata,          /**< graph data structure */
894  	   SCIP_RESULT*          result              /**< pointer to store the result of the separation call */
895  	   )
896  	{
897  	   unsigned int i;
898  	   unsigned int negatedcount;
899  	   unsigned int negated;
900  	
901  	   /* memory for lifting */
902  	   unsigned int nlifted;   /* number of lifted variables */
903  	   unsigned int* lifted;   /* index of the lifted variables */
904  	   unsigned int* liftcoef; /* lifting coefficient */
905  	
906  	   /* memory for cut generation */
907  	   SCIP_ROW* cut;
908  	   char cutname[SCIP_MAXSTRLEN];
909  	
910  	   assert(scip != NULL);
911  	   assert(vars != NULL);
912  	   assert(startnode < 2*nbinvars);
913  	   assert(pred != NULL);
914  	   assert(ncyclevars % 2 == 1);
915  	   assert(ncyclevars <= nbinvars);
916  	   assert(incut != NULL);
917  	   assert(graphdata != NULL);
918  	   assert(graphdata->levelgraph != NULL || graphdata->usegls);
919  	   assert(graphdata->dijkstragraph != NULL || ! graphdata->usegls);
920  	   assert(result != NULL);
921  	
922  	#ifdef SCIP_OUTPUT
923  	   /* debug method that prints out all found cycles */
924  	   printCycle(vars, pred, nbinvars, startnode);
925  	#endif
926  	
927  	   /* cycle contains only one node */
928  	   if( ncyclevars < 3 )
929  	   {
930  	      SCIPdebugMsg(scip, "fixing variable\n");
931  	      /* strengthening variable bounds due to single-variable-cycle */
932  	      if( startnode < nbinvars )
933  	      {
934  	         SCIP_CALL( SCIPchgVarUb(scip, vars[startnode], 0.0) );
935  	      }
936  	      else
937  	      {
938  	         negated = startnode - nbinvars;
939  	         assert(negated < nbinvars);
940  	         SCIP_CALL( SCIPchgVarLb(scip, vars[negated], 1.0) );
941  	      }
942  	      *result = SCIP_REDUCEDDOM;
943  	      return SCIP_OKAY;
944  	   }
945  	
946  	   /* cycle is a triangle (can be excluded by user) */
947  	   if( ncyclevars < 5 && ! sepadata->includetriangles )
948  	      return SCIP_OKAY;
949  	
950  	   if( SCIPisStopped(scip) )
951  	      return SCIP_OKAY;
952  	
953  	   /* lift the cycle inequality */
954  	   nlifted = 0;
955  	   lifted = NULL;
956  	   liftcoef = NULL;
957  	   if( sepadata->liftoddcycles )
958  	   {
959  	      SCIP_CALL( SCIPallocBufferArray(scip, &lifted, (int) (nbinvars - ncyclevars)) );
960  	      SCIP_CALL( SCIPallocBufferArray(scip, &liftcoef, (int) (nbinvars - ncyclevars)) );
961  	      SCIP_CALL( liftOddCycleCut(scip, &nlifted, lifted, liftcoef, sepadata, graphdata, vars, nbinvars, startnode, pred, ncyclevars, vals, result) );
962  	   }
963  	   /* if we don't try to lift, we generate and add the cut as is */
964  	
965  	   /* create cut */
966  	   (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "oddcycle_%d", sepadata->ncuts);
967  	   SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), (ncyclevars-1)/2.0, FALSE, FALSE, TRUE) );
968  	   SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
969  	   negatedcount = 0;
970  	
971  	   /* add variables of odd cycle to cut inequality */
972  	   i = pred[startnode];
973  	   while( i != startnode )
974  	   {
975  	      assert(i < 2*nbinvars);
976  	      if( i < nbinvars )
977  	      {
978  	         /* inserting original variable */
979  	         SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[i], 1.0) );
980  	         incut[i] = TRUE;
981  	      }
982  	      else
983  	      {
984  	         negated = i - nbinvars;
985  	         assert(negated < nbinvars);
986  	
987  	         /* inserting negated variable */
988  	         SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[negated], -1.0) );
989  	         ++negatedcount;
990  	         incut[negated] = TRUE;
991  	      }
992  	      i = pred[i];
993  	   }
994  	   assert(startnode == i);
995  	
996  	   /* insert startnode */
997  	   if( startnode < nbinvars )
998  	   {
999  	      /* inserting original variable */
1000 	      SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[startnode], 1.0) );
1001 	      incut[startnode] = TRUE;
1002 	   }
1003 	   else
1004 	   {
1005 	      negated = startnode - nbinvars;
1006 	      assert(negated < nbinvars);
1007 	
1008 	      /* inserting negated variable */
1009 	      SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[negated], -1.0) );
1010 	      ++negatedcount;
1011 	      incut[negated] = TRUE;
1012 	   }
1013 	
1014 	   /* add lifted variables to cut inequality (if existing) */
1015 	   for( i = 0; i < nlifted; ++i)
1016 	   {
1017 	      assert(lifted != NULL);
1018 	      assert(liftcoef != NULL);
1019 	      if( lifted[i] < nbinvars )
1020 	      {
1021 	         assert(vars[lifted[i]] != NULL);
1022 	         SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[lifted[i]], (SCIP_Real) liftcoef[i]) );
1023 	      }
1024 	      else
1025 	      {
1026 	         negated = lifted[i] - nbinvars;
1027 	         assert(negated < nbinvars);
1028 	         assert(vars[negated] != NULL);
1029 	         SCIP_CALL( SCIPaddVarToRow(scip, cut, vars[negated], -1.0*liftcoef[i]) );
1030 	         negatedcount += liftcoef[i];
1031 	      }
1032 	   }
1033 	
1034 	   /* modify right hand side corresponding to number of added negated variables */
1035 	   SCIP_CALL( SCIPchgRowRhs(scip, cut, SCIProwGetRhs(cut) - negatedcount) );
1036 	   SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
1037 	
1038 	   /* set cut rank: for oddcycle cuts we always set to 1 */
1039 	   SCIProwChgRank(cut, 1);
1040 	
1041 	   /* not every odd cycle has to be violated due to incompleteness of the implication graph */
1042 	   if( SCIPisCutEfficacious(scip, sol, cut) )
1043 	   {
1044 	      SCIP_Bool infeasible;
1045 	
1046 	      SCIP_CALL( SCIPaddRow(scip, cut, FALSE, &infeasible) );
1047 	      ++sepadata->ncuts;
1048 	      if ( nlifted > 0 )
1049 	         ++sepadata->nliftedcuts;
1050 	      if ( infeasible )
1051 	         *result = SCIP_CUTOFF;
1052 	      else
1053 	      {
1054 	         SCIP_CALL( SCIPaddPoolCut(scip, cut) );
1055 	
1056 	         if( *result == SCIP_DIDNOTFIND )
1057 	            *result = SCIP_SEPARATED;
1058 	      }
1059 	
1060 	#ifdef SCIP_OUTPUT
1061 	      SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
1062 	#endif
1063 	
1064 	      assert(*result == SCIP_CUTOFF || *result == SCIP_SEPARATED || *result == SCIP_REDUCEDDOM);
1065 	   }
1066 	
1067 	   SCIP_CALL( SCIPreleaseRow(scip, &cut) );
1068 	
1069 	   if( sepadata->liftoddcycles )
1070 	   {
1071 	      SCIPfreeBufferArray(scip, &liftcoef);
1072 	      SCIPfreeBufferArray(scip, &lifted);
1073 	   }
1074 	   return SCIP_OKAY;
1075 	}
1076 	
1077 	/** check whether the given object is really a cycle without sub-cycles (sub-cycles may be
1078 	 *  calculated by the GLS algorithm in case there is no violated odd cycle inequality) and removes
1079 	 *  pairs of original and negated variables from the cycle
1080 	 */
1081 	static
1082 	SCIP_RETCODE cleanCycle(
1083 	   SCIP*                 scip,               /**< SCIP data structure */
1084 	   unsigned int*         pred,               /**< predecessor list of current cycle segment */
1085 	   SCIP_Bool*            incycle,            /**< flag array iff node is in cycle segment */
1086 	   unsigned int*         incut,              /**< flag array iff node is already covered by a cut */
1087 	   unsigned int          x,                  /**< index of current variable */
1088 	   unsigned int          startnode,          /**< index of first variable of cycle segment */
1089 	   unsigned int          nbinvars,           /**< number of binary problem variables */
1090 	   unsigned int*         ncyclevars,         /**< number of nodes in current cycle segment */
1091 	   SCIP_Bool             repaircycles,       /**< user flag if we should try to repair damaged cycles */
1092 	   SCIP_Bool             allowmultiplecuts,  /**< user flag if we allow multiple cuts per node */
1093 	   SCIP_Bool*            success             /**< FALSE iff an irreparable cycle appears */
1094 	   )
1095 	{
1096 	   unsigned int negx;
1097 	
1098 	   assert(scip != NULL);
1099 	   assert(pred != NULL);
1100 	   assert(incycle != NULL);
1101 	   assert(incut != NULL);
1102 	   assert(ncyclevars != NULL);
1103 	   assert(*ncyclevars <= nbinvars);
1104 	   assert(success != NULL);
1105 	   assert(*success);
1106 	
1107 	   assert(x < 2*nbinvars);
1108 	
1109 	   /* skip variable if it is already covered by a cut and we do not allow multiple cuts per node */
1110 	   if( incut[x] && !allowmultiplecuts )
1111 	   {
1112 	      *success = FALSE;
1113 	      return SCIP_OKAY;
1114 	   }
1115 	
1116 	   /* get index of negated variable of current variable */
1117 	   if( x < nbinvars )
1118 	      negx = x + nbinvars;
1119 	   else
1120 	      negx = x - nbinvars;
1121 	   assert(negx < 2*nbinvars);
1122 	
1123 	   /* given object is not an odd cycle (contains sub-cycle) or contains original and negated
1124 	    * variable pair but we should not repair this
1125 	    */
1126 	   if( incycle[x] || (incycle[negx] && !repaircycles) )
1127 	   {
1128 	      *success = FALSE;
1129 	      return SCIP_OKAY;
1130 	   }
1131 	
1132 	   /* cycle does not contain original and negated variable pair */
1133 	   if( !incycle[negx] )
1134 	   {
1135 	      assert(!incycle[x]);
1136 	      incycle[x] = TRUE;
1137 	      ++(*ncyclevars);
1138 	      return SCIP_OKAY;
1139 	   }
1140 	
1141 	   /* delete original and negated variable and cross-link their neighbors the following way, if possible:
1142 	    * suppose the cycle contains segments:
1143 	    * startnode - ... - a - neg(x) - c1 - c2 - ... - cn-1 - cn - x - z=pred(x)
1144 	    *
1145 	    * because of the chain a - neg(x) - x - cn it holds that
1146 	    *   a=1 => x=0 => neg(x)=1 => cn=0 and
1147 	    *   cn=1 => x=0 => neg(x)=1 => a=0
1148 	    * because of the chain z - x - neg(x) - b it holds that
1149 	    *   z=1 => x=0 => neg(x)=1 => c1=0 and
1150 	    *   c1=1 => x=0 => neg(x)=1 => z=0
1151 	    *
1152 	    * in addition to that, in our linked list structure we need to relink the chain c1-...-cn in reverse order.
1153 	    * so we gain the order: a - cn - cn-1 - ... - c2 - c1 - z
1154 	    */
1155 	
1156 	   /* if negated variable is first node in cycle,
1157 	    * cross-linking not possible because there is no successor z of neg(x) contained in cycle yet
1158 	    */
1159 	   if( negx == startnode )
1160 	   {
1161 	      *success = FALSE;
1162 	      return SCIP_OKAY;
1163 	   }
1164 	
1165 	   /* if original and negated variable are neighbors, cross linking is not possible,
1166 	    * but x and neg(x) can simply be removed
1167 	    * a - neg(x)=pred[a] - x=pred[neg(x)] - z=pred[x] --> a - z=pred[x]=:pred[a]
1168 	    */
1169 	   if( pred[negx] == x )
1170 	   {
1171 	      unsigned int a;
1172 	
1173 	      /* find a */
1174 	      a = startnode;
1175 	      while( pred[a] != negx )
1176 	         a = pred[a];
1177 	
1178 	      /* link a and z */
1179 	      pred[a] = pred[x];
1180 	   }
1181 	   /* cross linking as mentioned above */
1182 	   else
1183 	   {
1184 	      unsigned int a;
1185 	      unsigned int z;
1186 	
1187 	      /* memory for chain reverse */
1188 	      unsigned int* chain;
1189 	      unsigned int nchain;
1190 	
1191 	      unsigned int i;
1192 	
1193 	      /* allocate temporary memory */
1194 	      SCIP_CALL( SCIPallocBufferArray(scip, &chain, (int) *ncyclevars) );
1195 	
1196 	      /* find and store a */
1197 	      a = startnode;
1198 	      while( pred[a] != negx )
1199 	         a = pred[a];
1200 	
1201 	      /* store chain */
1202 	      i = pred[negx];
1203 	      nchain = 0;
1204 	      while( i != x )
1205 	      {
1206 	         chain[nchain] = i;
1207 	         ++nchain;
1208 	         i = pred[i];
1209 	      }
1210 	      assert(nchain > 0);
1211 	
1212 	      /* store z */
1213 	      z = pred[x];
1214 	
1215 	      /* link a and c1 */
1216 	      pred[a] = chain[nchain-1];
1217 	
1218 	      /* link cn and z */
1219 	      pred[chain[0]] = z;
1220 	
1221 	      /* reverse the chain */
1222 	      for( i = nchain-1; i > 0; --i )
1223 	         pred[chain[i]] = chain[i-1];
1224 	
1225 	      /* free temporary memory */
1226 	      SCIPfreeBufferArray(scip, &chain);
1227 	   }
1228 	
1229 	   /* remove negated variable from cycle */
1230 	   assert(!incycle[x] && incycle[negx]);
1231 	   incycle[negx] = FALSE;
1232 	   --(*ncyclevars);
1233 	
1234 	   return SCIP_OKAY;
1235 	}
1236 	
1237 	
1238 	/*
1239 	 * methods for separateHeur()
1240 	 */
1241 	
1242 	/** memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need)
1243 	 *
1244 	 *  Since the array sizes differ the method can be called for each of the three data structure types:
1245 	 *  - Forward: sizeForward, targetForward, weightForward
1246 	 *  - Backward: sizeBackward, targetBackward, weightBackward
1247 	 *  - Adj (inner level edges): sizeAdj, sourceAdj, targetAdj, weightAdj
1248 	 */
1249 	static
1250 	SCIP_RETCODE checkArraySizesHeur(
1251 	   SCIP*                 scip,               /**< SCIP data structure */
1252 	   LEVELGRAPH*           graph,              /**< LEVELGRAPH data structure */
1253 	   unsigned int*         size,               /**< given size */
1254 	   int**                 targetArray,        /**< given target array (or NULL if sourceAdjArray and targetAdjArray given) */
1255 	   unsigned int**        weightArray,        /**< given weight array */
1256 	   unsigned int**        sourceAdjArray,     /**< given sourceAdj array (or NULL if targetArray given) */
1257 	   unsigned int**        targetAdjArray,     /**< given targetAdj array (or NULL if targetArray given) */
1258 	   SCIP_Bool*            success             /**< FALSE, iff memory reallocation fails */
1259 	   )
1260 	{
1261 	   SCIP_Real memorylimit;
1262 	   unsigned int additional;
1263 	   SCIP_Bool avoidmemout;
1264 	
1265 	   assert(scip != NULL);
1266 	   assert(graph != NULL);
1267 	   assert(size != NULL);
1268 	   assert(targetArray != NULL || (sourceAdjArray != NULL && targetAdjArray != NULL));
1269 	   assert(weightArray != NULL);
1270 	   assert(success != NULL);
1271 	
1272 	   SCIPdebugMsg(scip, "reallocating...\n");
1273 	
1274 	   additional = MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**weightArray));
1275 	   if( targetArray != NULL )
1276 	   {
1277 	      additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**targetArray));
1278 	   }
1279 	   else
1280 	   {
1281 	      additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**sourceAdjArray));
1282 	      additional += MIN(graph->maxarcs + graph->maxnodes - *size, *size) * ((int) sizeof(**targetAdjArray));
1283 	   }
1284 	
1285 	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1286 	   if( !SCIPisInfinity(scip, memorylimit) )
1287 	   {
1288 	      memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1289 	      memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1290 	   }
1291 	
1292 	   SCIP_CALL( SCIPgetBoolParam(scip, "misc/avoidmemout", &avoidmemout) );
1293 	   /* if memorylimit would be exceeded or any other limit is reached free all data and exit */
1294 	   if( (avoidmemout && memorylimit <= additional/1048576.0) || SCIPisStopped(scip) )
1295 	   {
1296 	      *success = FALSE;
1297 	      SCIPdebugMsg(scip, "...memory limit exceeded\n");
1298 	      return SCIP_OKAY;
1299 	   }
1300 	
1301 	   *size = 2 * (*size);
1302 	
1303 	   SCIP_CALL( SCIPreallocBufferArray(scip, weightArray, (int) MIN(graph->maxarcs + graph->maxnodes, *size)) );
1304 	   if( targetArray != NULL )
1305 	   {
1306 	      SCIP_CALL( SCIPreallocBufferArray(scip, targetArray, (int) MIN(graph->maxarcs + graph->maxnodes, *size)) );
1307 	   }
1308 	   else
1309 	   {
1310 	      assert(sourceAdjArray != NULL);
1311 	      assert(targetAdjArray != NULL);
1312 	      SCIP_CALL( SCIPreallocBufferArray(scip, sourceAdjArray, (int) MIN(graph->maxarcs, *size)) );
1313 	      SCIP_CALL( SCIPreallocBufferArray(scip, targetAdjArray, (int) MIN(graph->maxarcs, *size)) );
1314 	   }
1315 	
1316 	   /* if memorylimit is exceeded free all data and exit */
1317 	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
1318 	   if( !SCIPisInfinity(scip, memorylimit) )
1319 	   {
1320 	      memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
1321 	      memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
1322 	   }
1323 	
1324 	   if( avoidmemout && memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
1325 	   {
1326 	      *success = FALSE;
1327 	      SCIPdebugMsg(scip, "...memory limit exceeded\n");
1328 	      return SCIP_OKAY;
1329 	   }
1330 	
1331 	   SCIPdebugMsg(scip, "...with success\n");
1332 	
1333 	   return SCIP_OKAY;
1334 	}
1335 	
1336 	/** Add arc to level graph */
1337 	static
1338 	SCIP_RETCODE addArc(
1339 	   SCIP*                 scip,               /**< SCIP data structure */
1340 	   LEVELGRAPH*           graph,              /**< LEVELGRAPH data structure */
1341 	   unsigned int          u,                  /**< source node */
1342 	   unsigned int          v,                  /**< target node */
1343 	   unsigned int          level,              /**< number of current level */
1344 	   unsigned int          weight,             /**< weight of the arc */
1345 	   unsigned int*         nAdj,               /**< array of numbers of arcs inside levels */
1346 	   SCIP_Bool*            success             /**< FALSE, iff memory reallocation fails */
1347 	   )
1348 	{
1349 	   /* arc is a forward arc */
1350 	   if( graph->level[v] == level+1 )
1351 	   {
1352 	      graph->targetForward[graph->lastF] = (int) v;
1353 	      graph->weightForward[graph->lastF] = weight;
1354 	      ++(graph->lastF);
1355 	      ++(graph->narcs);
1356 	      if( graph->lastF == graph->sizeForward )
1357 	      {
1358 	         SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeForward), &(graph->targetForward),
1359 	               &(graph->weightForward), NULL, NULL, success) );
1360 	         if( !(*success) )
1361 	            return SCIP_OKAY;
1362 	      }
1363 	   }
1364 	   else
1365 	   {
1366 	      assert(graph->level[v] == level || graph->level[v] == level-1);
1367 	
1368 	      /* arc is a backward arc */
1369 	      if( graph->level[v] == level-1 )
1370 	      {
1371 	         graph->targetBackward[graph->lastB] = (int) v;
1372 	         graph->weightBackward[graph->lastB] = weight;
1373 	         ++(graph->lastB);
1374 	         ++(graph->narcs);
1375 	
1376 	         if( graph->lastB == graph->sizeBackward )
1377 	         {
1378 	            SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeBackward), &(graph->targetBackward),
1379 	                  &(graph->weightBackward), NULL, NULL, success) );
1380 	            if( !(*success) )
1381 	               return SCIP_OKAY;
1382 	         }
1383 	      }
1384 	      else       /* arc is in the same level */
1385 	      {
1386 	         assert(graph->level[v] == level);
1387 	
1388 	         /* add arc only once, i.e., if u < v */
1389 	         if( u < v )
1390 	         {
1391 	            graph->sourceAdj[graph->levelAdj[level+1]+*nAdj] = u;
1392 	            graph->targetAdj[graph->levelAdj[level+1]+*nAdj] = v;
1393 	            graph->weightAdj[graph->levelAdj[level+1]+*nAdj] = weight;
1394 	            ++(*nAdj);
1395 	            ++(graph->narcs);
1396 	
1397 	            if( graph->levelAdj[level+1]+*nAdj == graph->sizeAdj )
1398 	            {
1399 	               SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeAdj), NULL, &(graph->weightAdj),
1400 	                     &(graph->sourceAdj), &(graph->targetAdj), success) );
1401 	               if( !(*success) )
1402 	                  return SCIP_OKAY;
1403 	            }
1404 	         }
1405 	      }
1406 	   }
1407 	   return SCIP_OKAY;
1408 	}
1409 	
1410 	/** add implications from cliques of the given node u
1411 	 *
1412 	 *  @see createNextLevel()
1413 	 */
1414 	static
1415 	SCIP_RETCODE addNextLevelCliques(
1416 	   SCIP*                 scip,               /**< SCIP data structure */
1417 	   SCIP_SEPADATA*        sepadata,           /**< separator data structure */
1418 	   SCIP_VAR**            vars,               /**< problem variables */
1419 	   SCIP_Real*            vals,               /**< values of the binary variables in the current LP relaxation */
1420 	   unsigned int          u,                  /**< current node */
1421 	   LEVELGRAPH*           graph,              /**< LEVELGRAPH data structure */
1422 	   unsigned int          level,              /**< number of current level */
1423 	   SCIP_Bool*            inlevelgraph,       /**< flag array if node is already inserted in level graph */
1424 	   unsigned int*         newlevel,           /**< array of nodes of the next level */
1425 	   unsigned int*         nnewlevel,          /**< number of nodes of the next level */
1426 	   unsigned int*         nAdj,               /**< array of numbers of arcs inside levels */
1427 	   SCIP_Bool*            success             /**< FALSE, iff memory reallocation fails */
1428 	   )
1429 	{
1430 	   SCIP_Bool varfixing;
1431 	   unsigned int ncliques;
1432 	   unsigned int nbinvars;
1433 	   unsigned int varsidx;
1434 	   SCIP_CLIQUE** cliques;
1435 	   unsigned int ncliquevars;
1436 	   SCIP_VAR** cliquevars;
1437 	   SCIP_Bool* cliquevals;
1438 	   unsigned int j;
1439 	   unsigned int k;
1440 	
1441 	   assert(scip != NULL);
1442 	   assert(vars != NULL);
1443 	   assert(vals != NULL);
1444 	   assert(graph != NULL);
1445 	   assert(graph->targetForward != NULL);
1446 	   assert(graph->weightForward != NULL);
1447 	   assert(graph->targetBackward != NULL);
1448 	   assert(graph->weightBackward != NULL);
1449 	   assert(graph->sourceAdj != NULL);
1450 	   assert(graph->targetAdj != NULL);
1451 	   assert(graph->weightAdj != NULL);
1452 	   assert(inlevelgraph != NULL);
1453 	   assert(newlevel != NULL);
1454 	   assert(nnewlevel != NULL);
1455 	   assert(nAdj != NULL);
1456 	   assert(success != NULL);
1457 	
1458 	   assert(u < graph->maxnodes);
1459 	
1460 	   nbinvars = (graph->maxnodes)/2;
1461 	
1462 	   /* current node signifies a problem variable */
1463 	   if( u < nbinvars )
1464 	   {
1465 	      varfixing = TRUE;
1466 	      varsidx = u;
1467 	   }
1468 	   /* current node signifies a negated variable */
1469 	   else
1470 	   {
1471 	      varfixing = FALSE;
1472 	      varsidx = u - nbinvars;
1473 	   }
1474 	   assert(varsidx < nbinvars);
1475 	   assert(!SCIPisFeasIntegral(scip, vals[varsidx]));
1476 	
1477 	   /* get cliques of the current variable */
1478 	   ncliques = (unsigned int) SCIPvarGetNCliques(vars[varsidx], varfixing);
1479 	   if( ncliques == 0 )
1480 	      return SCIP_OKAY;
1481 	
1482 	   cliques = SCIPvarGetCliques(vars[varsidx], varfixing);
1483 	   assert(cliques != NULL);
1484 	
1485 	   for( j = 0; j < ncliques; ++j )
1486 	   {
1487 	      ncliquevars = (unsigned int) SCIPcliqueGetNVars(cliques[j]);
1488 	      cliquevars = SCIPcliqueGetVars(cliques[j]);
1489 	      cliquevals = SCIPcliqueGetValues(cliques[j]);
1490 	
1491 	      assert(cliquevars != NULL || ncliquevars == 0);
1492 	      assert(cliquevals != NULL || ncliquevars == 0);
1493 	
1494 	      for( k = 0; k < ncliquevars; ++k )
1495 	      {
1496 	         unsigned int l;
1497 	         unsigned int v;
1498 	         unsigned int weight;
1499 	
1500 	         assert( cliquevars != NULL && cliquevals != NULL );  /* for lint */
1501 	
1502 	         l = sepadata->mapping[SCIPvarGetProbindex(cliquevars[k])];
1503 	         assert(l < nbinvars);
1504 	
1505 	         /* skip integral neighbors */
1506 	         if( SCIPisFeasIntegral(scip, vals[l]) )
1507 	            continue;
1508 	
1509 	         /* consider clique with negated variable (x = 1 -> y >= 1 <=>  x = 1 -> neg(y) <= 0) */
1510 	         if( cliquevals[k] == FALSE )
1511 	            v = l + nbinvars;
1512 	         /* x = 1 -> y <= 0 */
1513 	         else
1514 	            v = l;
1515 	         assert(v < graph->maxnodes);
1516 	
1517 	         /* if variable is a new node, it will be assigned to the next level,
1518 	          * but if the level contains more nodes than allowed
1519 	          * (defined by percent per level plus offset),
1520 	          * we skip the rest of the nodes
1521 	          */
1522 	         if( !inlevelgraph[v] && (*nnewlevel) <= sepadata->maxlevelsize )
1523 	         {
1524 	            ++(graph->nnodes);
1525 	            graph->level[v] = level+1;
1526 	            inlevelgraph[v] = TRUE;
1527 	            newlevel[*nnewlevel] = v;
1528 	            ++(*nnewlevel);
1529 	         }
1530 	         assert(*nnewlevel > sepadata->maxlevelsize || inlevelgraph[v]);
1531 	
1532 	         /* calculate arc weight and add arc, if the neighbor node is on the same or a neighbor level */
1533 	         if( inlevelgraph[v] && (graph->level[v] == level+1 || graph->level[v] == level || graph->level[v] == level-1))
1534 	         {
1535 	            int tmp;
1536 	
1537 	            /* the computation of 1.0 - vals[v] if v is negated is ensured by the fact that v > nbinvars in this case */
1538 	            /* set weight of arc (x,y) to 1 - x* -y* */
1539 	            if( varfixing )
1540 	            {
1541 	               /* x = 1 -> y <= 0  or  y >= 1 */
1542 	               tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - vals[v]));
1543 	               weight = (unsigned int) MAX(tmp, sepadata->maxreference);
1544 	            }
1545 	            else
1546 	            {
1547 	               /* x = 0 <-> neg(x) = 1 -> y <= 0  or  y >= 1 */
1548 	               tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1.0 - (1.0 - vals[varsidx]) - vals[v]));
1549 	               weight = (unsigned int) MAX(tmp, sepadata->maxreference);
1550 	            }
1551 	
1552 	            /* add arc from current to neighbor node */
1553 	            SCIP_CALL( addArc(scip, graph, u, v, level, weight, nAdj, success) );
1554 	            if( !(*success) )
1555 	               return SCIP_OKAY;
1556 	         }
1557 	      }
1558 	   }
1559 	   return SCIP_OKAY;
1560 	}
1561 	
1562 	
1563 	/** sort level of root neighbors
1564 	 *
1565 	 *  If we limit the size of nodes of a level, we want to add the best neighbors to the next level.
1566 	 *  Since sorting every level is too expensive, we sort the neighbors of the root (if requested).
1567 	 *
1568 	 *  Create the first level as follows:
1569 	 *  - create flag array for binary variables and their negated and set their values FALSE
1570 	 *  - iterate over the implication and clique neighbors of the root and set their flag array values to TRUE
1571 	 *  - create variable array and insert all variables with flag value TRUE
1572 	 *  - sort variable array by maximal fractionality
1573 	 *  - add variables from sorted array to levelgraph until first level is full (or all variables are inserted)
1574 	 *
1575 	 *  Even inserting all variables might help for the following creation of further levels since the neighbors
1576 	 *  of nodes with high fractionality often have high fractionalities themselves and would be inserted first
1577 	 *  when further levels would have been sorted (which actually is not the case).
1578 	 */
1579 	static
1580 	SCIP_RETCODE insertSortedRootNeighbors(
1581 	   SCIP*                 scip,               /**< SCIP data structure */
1582 	   LEVELGRAPH*           graph,              /**< LEVELGRAPH data structure */
1583 	   unsigned int          nbinvars,           /**< number of binary problem variables */
1584 	   unsigned int          ncurlevel,          /**< number of nodes of the current level */
1585 	   unsigned int          u,                  /**< source node */
1586 	   SCIP_Real*            vals,               /**< values of the binary variables in the current LP relaxation */
1587 	   SCIP_VAR**            vars,               /**< problem variables */
1588 	   SCIP_SEPADATA*        sepadata,           /**< separator data structure */
1589 	   unsigned int*         nnewlevel,          /**< number of nodes of the next level */
1590 	   SCIP_Bool*            inlevelgraph,       /**< nodes in new graph corr. to old graph (-1 if unassigned) */
1591 	   unsigned int          level,              /**< number of current level */
1592 	   unsigned int*         newlevel,           /**< array of nodes of the next level */
1593 	   SCIP_Bool*            success             /**< FALSE, iff memory reallocation fails */
1594 	   )
1595 	{
1596 	   /* storage for the neighbors of the root */
1597 	   unsigned int root;
1598 	   unsigned int nneighbors;
1599 	   SCIP_Bool* isneighbor;
1600 	   int* neighbors;
1601 	   SCIP_Real* sortvals;
1602 	
1603 	   SCIP_Bool varfixing;
1604 	   unsigned int varsidx;
1605 	
1606 	   /* storage for cliques to the neighbors of the root node */
1607 	   unsigned int ncliques;
1608 	   SCIP_CLIQUE** cliques;
1609 	   unsigned int ncliquevars;
1610 	   SCIP_VAR** cliquevars;
1611 	   SCIP_Bool* cliquevals;
1612 	
1613 	   unsigned int j;
1614 	   unsigned int k;
1615 	   unsigned int v;
1616 	
1617 	   /* allocate flag array for neighbor detection */
1618 	   SCIP_CALL( SCIPallocBufferArray(scip, &isneighbor, (int) graph->maxnodes) );
1619 	   BMSclearMemoryArray(isneighbor, graph->maxnodes);
1620 	
1621 	   nbinvars = (graph->maxnodes)/2;
1622 	
1623 	   assert(ncurlevel == 1);
1624 	   root = u;
1625 	
1626 	   /* current node signifies a problem variable */
1627 	   if( root < nbinvars )
1628 	   {
1629 	      varfixing = TRUE;
1630 	      varsidx = root;
1631 	   }
1632 	   /* current node signifies a negated variable */
1633 	   else
1634 	   {
1635 	      varfixing = FALSE;
1636 	      varsidx = root - nbinvars;
1637 	   }
1638 	   assert(varsidx < nbinvars);
1639 	   assert(! SCIPisFeasIntegral(scip, vals[varsidx]));
1640 	   nneighbors = 0;
1641 	
1642 	   /* count cliques of the root */
1643 	   ncliques = (unsigned int) SCIPvarGetNCliques(vars[varsidx], varfixing);
1644 	   if( ncliques > 0 )
1645 	   {
1646 	      cliques = SCIPvarGetCliques(vars[varsidx], varfixing);
1647 	      assert(cliques != NULL);
1648 	
1649 	      for( j = 0; j < ncliques; ++j )
1650 	      {
1651 	         ncliquevars = (unsigned int) SCIPcliqueGetNVars(cliques[j]);
1652 	         cliquevars = SCIPcliqueGetVars(cliques[j]);
1653 	         cliquevals = SCIPcliqueGetValues(cliques[j]);
1654 	
1655 	         assert(cliquevars != NULL || ncliquevars == 0);
1656 	         assert(cliquevals != NULL || ncliquevars == 0);
1657 	
1658 	         for( k = 0; k < ncliquevars; ++k )
1659 	         {
1660 	            unsigned int kidx;
1661 	
1662 	            assert( cliquevars != NULL && cliquevals != NULL ); /* for lint */
1663 	
1664 	            kidx = sepadata->mapping[SCIPvarGetProbindex(cliquevars[k])];
1665 	            assert(kidx < nbinvars);
1666 	
1667 	            /* skip root */
1668 	            if( kidx == varsidx )
1669 	               continue;
1670 	
1671 	            /* skip integral neighbors */
1672 	            if( SCIPisFeasIntegral(scip, vals[kidx]))
1673 	               continue;
1674 	
1675 	            if( cliquevals[k] == TRUE )
1676 	            {
1677 	               if ( ! isneighbor[kidx] )
1678 	               {
1679 	                  ++nneighbors;
1680 	                  isneighbor[kidx] = TRUE;
1681 	               }
1682 	            }
1683 	            else
1684 	            {
1685 	               assert(cliquevals[k] == FALSE);
1686 	               if ( ! isneighbor[kidx + nbinvars] )
1687 	               {
1688 	                  ++nneighbors;
1689 	                  isneighbor[kidx+nbinvars] = TRUE;
1690 	               }
1691 	            }
1692 	         }
1693 	      }
1694 	   }
1695 	
1696 	   /* root cannot be part of the next level */
1697 	   assert(! isneighbor[root]);
1698 	
1699 	   /* allocate memory for sorting of root neighbors */
1700 	   SCIP_CALL( SCIPallocBufferArray(scip, &neighbors, (int) nneighbors) );
1701 	   SCIP_CALL( SCIPallocBufferArray(scip, &sortvals, (int) nneighbors) );
1702 	
1703 	   k = 0;
1704 	   for( j = 0; j < graph->maxnodes; ++j )
1705 	   {
1706 	      if( isneighbor[j] )
1707 	      {
1708 	         assert(j != root);
1709 	         assert(!SCIPisFeasIntegral(scip, vals[j]));
1710 	
1711 	         neighbors[k] = (int) j;
1712 	         sortvals[k] = MIN(1.0 - vals[j], vals[j]);
1713 	         ++k;
1714 	      }
1715 	   }
1716 	   assert(k == nneighbors);
1717 	
1718 	   /* sort neighbors by fractionality */
1719 	   SCIPsortDownRealInt(sortvals, neighbors, (int) nneighbors);
1720 	
1721 	   /* free temporary memory */
1722 	   SCIPfreeBufferArray(scip, &sortvals);
1723 	
1724 	   /* insert sorted neighbors until level size limit is reached (or all neighbors are inserted) */
1725 	   for( j = 0; j < nneighbors && (*nnewlevel) <= sepadata->maxlevelsize; ++j )
1726 	   {
1727 	      int tmp;
1728 	
1729 	      v = (unsigned int) neighbors[j];
1730 	      assert( v < 2 * nbinvars );
1731 	
1732 	      /* only the root is contained in the levelgraph */
1733 	      assert(! inlevelgraph[v] || v == root+nbinvars || v == root-nbinvars);
1734 	
1735 	      /* insert neighbor into levelgraph */
1736 	      ++(graph->nnodes);
1737 	      graph->level[v] = level + 1;
1738 	      inlevelgraph[v] = TRUE;
1739 	      newlevel[*nnewlevel] = v;
1740 	      ++(*nnewlevel);
1741 	
1742 	      assert(! SCIPisFeasIntegral(scip, vals[varsidx]));
1743 	      assert(! SCIPisFeasIntegral(scip, vals[v]));
1744 	
1745 	      graph->targetForward[graph->lastF] = (int) v;
1746 	      /* the computation of 1.0 - vals[v] if v is negated is ensured by the fact that v > nbinvars in this case */
1747 	      if( varfixing )
1748 	      {
1749 	         tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1.0 - vals[varsidx] - vals[v]));
1750 	         graph->weightForward[graph->lastF] = (unsigned int) MAX(tmp, sepadata->maxreference);
1751 	      }
1752 	      else
1753 	      {
1754 	         assert( ! varfixing );
1755 	         tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1.0 - (1.0 - vals[varsidx]) - vals[v]));
1756 	         graph->weightForward[graph->lastF] = (unsigned int) MAX(tmp, sepadata->maxreference);
1757 	      }
1758 	      ++(graph->lastF);
1759 	      ++(graph->narcs);
1760 	      if( graph->lastF == graph->sizeForward )
1761 	      {
1762 	         SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeForward), &(graph->targetForward),
1763 	               &(graph->weightForward), NULL, NULL, success) );
1764 	
1765 	         if( !(*success) )
1766 	            break;
1767 	      }
1768 	   }
1769 	
1770 	   /* free temporary memory */
1771 	   SCIPfreeBufferArray(scip, &neighbors);
1772 	   SCIPfreeBufferArray(scip, &isneighbor);
1773 	
1774 	   return SCIP_OKAY;
1775 	}
1776 	
1777 	/** Find shortest path from start node to root
1778 	 *
1779 	 *  We perform a BFS to find the shortest path to the root. D stores the distance to the start
1780 	 *  node, P stores the partent nodes in the shortest path tree (-1 if node has not been reached).
1781 	 */
1782 	static
1783 	SCIP_RETCODE findShortestPathToRoot(
1784 	   SCIP*                 scip,               /**< SCIP data structure */
1785 	   int                   scale,              /**< scaling factor for edge weights */
1786 	   LEVELGRAPH*           graph,              /**< LEVELGRAPH data structure */
1787 	   unsigned int          startnode,          /**< start node for path search */
1788 	   unsigned int*         distance,           /**< distances of searched nodes from root */
1789 	   unsigned int*         queue,              /**< node queue for path search */
1790 	   SCIP_Bool*            inQueue,            /**< whether node is in the queue */
1791 	   int*                  parentTree          /**< parent tree (-1 if no parent) */
1792 	   )
1793 	{
1794 	   unsigned int i;
1795 	   int startQueue;
1796 	   int endQueue;
1797 	   unsigned int u;
1798 	   int v;
1799 	   unsigned int d;
1800 	
1801 	   assert(scip != NULL);
1802 	   assert(graph != NULL);
1803 	   assert(graph->beginBackward != NULL);
1804 	   assert(graph->targetBackward != NULL);
1805 	   assert(graph->weightBackward != NULL);
1806 	   assert(distance != NULL);
1807 	   assert(queue != NULL);
1808 	   assert(inQueue != NULL);
1809 	   assert(parentTree != NULL);
1810 	   assert(scale >= 0);
1811 	
1812 	   /* initialize distances */
1813 	   for( i = 0; i < graph->maxnodes; ++i )
1814 	   {
1815 	      distance[i] = 2 * (graph->nnodes) * (unsigned) scale;
1816 	      parentTree[i] = -1;
1817 	      inQueue[i] = FALSE;
1818 	   }
1819 	   distance[startnode] = 0;
1820 	
1821 	   /* initialize queue */
1822 	   startQueue = 0;
1823 	   endQueue = 0;
1824 	   queue[0] = startnode;
1825 	
1826 	   /* as long as queue is not empty */
1827 	   while( startQueue <= endQueue )
1828 	   {
1829 	      /* pop first node from queue */
1830 	      u = queue[startQueue];
1831 	      ++startQueue;
1832 	
1833 	      /* check adjacent nodes */
1834 	      assert(graph->beginBackward[u] >= 0);
1835 	      i = (unsigned int) graph->beginBackward[u];
1836 	      for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] )
1837 	      {
1838 	         /* distance to u via current arc: */
1839 	         d = distance[u] + graph->weightBackward[i];
1840 	
1841 	         /* if we found a shorter connection */
1842 	         if( d < distance[v] )
1843 	         {
1844 	            distance[v] = d;
1845 	            parentTree[v] = (int) u;
1846 	
1847 	            /* insert in queue if not already present */
1848 	            if( !inQueue[v] )
1849 	            {
1850 	               ++endQueue;
1851 	               queue[endQueue] = (unsigned int) v;
1852 	               inQueue[v] = TRUE;
1853 	            }
1854 	         }
1855 	      }
1856 	      /* it is not necessary to stop if we found the root (in this case there are no arcs left) and we stop anyway */
1857 	   }
1858 	   assert(parentTree[u] != -1);
1859 	
1860 	   return SCIP_OKAY;
1861 	}
1862 	
1863 	
1864 	/** Block shortest path
1865 	 *
1866 	 *  We traverse the shortest path found by findShortestPathToRoot() and block all neighbors (in the
1867 	 *  original graph) of nodes in the path, i.e., we set blocked to TRUE. We do not block neighbors of
1868 	 *  the root node, since they have to be used. For the start node we only block nodes on the
1869 	 *  previous layers,
1870 	 *
1871 	 *  @see findShortestPathToRoot()
1872 	 */
1873 	static
1874 	SCIP_RETCODE blockRootPath(
1875 	   SCIP*                 scip,               /**< SCIP data structure */
1876 	   LEVELGRAPH*           graph,              /**< LEVELGRAPH data structure */
1877 	   unsigned int          startnode,          /**< start node */
1878 	   SCIP_Bool*            inlevelgraph,       /**< nodes in new graph corr. to old graph (-1 if unassigned) */
1879 	   SCIP_Bool*            blocked,            /**< whether node is blocked */
1880 	   int*                  parentTree,         /**< parent tree */
1881 	   unsigned int          root                /**< root of the current level graph */
1882 	   )
1883 	{
1884 	   unsigned int u;
1885 	   unsigned int i;
1886 	   int v;
1887 	
1888 	   assert(scip != NULL);
1889 	   assert(graph != NULL);
1890 	   assert(graph->level != NULL);
1891 	   assert(graph->beginForward != NULL);
1892 	   assert(graph->targetForward != NULL);
1893 	   assert(graph->beginBackward != NULL);
1894 	   assert(graph->targetBackward != NULL);
1895 	   assert(graph->sourceAdj != NULL);
1896 	   assert(graph->targetAdj != NULL);
1897 	   assert(inlevelgraph != NULL);
1898 	   assert(blocked != NULL);
1899 	   assert(parentTree != NULL);
1900 	
1901 	   assert(parentTree[root] >= 0);
1902 	
1903 	   /* follow the path from the predecessor of root to the start node and block all neighbors */
1904 	   u = (unsigned int) parentTree[root];
1905 	   while( u != startnode )
1906 	   {
1907 	      /*  block neighbors of u in higher level */
1908 	      i = (unsigned int) graph->beginForward[u];
1909 	      for( v = graph->targetForward[i]; v >= 0; v = graph->targetForward[++i] )
1910 	      {
1911 	         assert(inlevelgraph[v]);
1912 	         blocked[v] = TRUE;
1913 	      }
1914 	
1915 	      /*  block neighbors of u in lower level */
1916 	      i = (unsigned int) graph->beginBackward[u];
1917 	      for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] )
1918 	      {
1919 	         assert(inlevelgraph[v]);
1920 	         blocked[v] = TRUE;
1921 	      }
1922 	
1923 	      /*  block neighbors of u in same level */
1924 	      assert(graph->level[u] > 0);
1925 	      for( i = graph->levelAdj[graph->level[u]]; i < graph->levelAdj[graph->level[u]+1]; ++i )
1926 	      {
1927 	         assert(graph->sourceAdj[i] < graph->targetAdj[i]);
1928 	         assert(graph->level[graph->sourceAdj[i]] == graph->level[graph->targetAdj[i]]);
1929 	
1930 	         /* remember that these arcs are only stored for one direction */
1931 	         if( graph->sourceAdj[i] == u )
1932 	         {
1933 	            blocked[graph->targetAdj[i]] = TRUE;
1934 	         }
1935 	         if( graph->targetAdj[i] == u )
1936 	         {
1937 	            blocked[graph->sourceAdj[i]] = TRUE;
1938 	         }
1939 	      }
1940 	
1941 	      /* get next node on the path */
1942 	      u = (unsigned int) parentTree[u];
1943 	   }
1944 	   assert(u == startnode);
1945 	
1946 	   /* block nodes adjacent to start node on previous level */
1947 	   assert(graph->beginBackward[u] > 0);
1948 	   i = (unsigned int) graph->beginBackward[u];
1949 	   for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] )
1950 	      blocked[v] = TRUE;
1951 	
1952 	   return SCIP_OKAY;
1953 	}
1954 	
1955 	
1956 	/** Find shortest path from root to target node
1957 	 *
1958 	 *  We perform a BFS to find the shortest path from the root. The only difference to
1959 	 *  findShortestPathToRoot() is that we avoid nodes that are blocked.
1960 	 */
1961 	static
1962 	SCIP_RETCODE
1963 	findUnblockedShortestPathToRoot(
1964 	   SCIP*                 scip,               /**< SCIP data structure */
1965 	   int                   scale,              /**< scaling factor for edge weights */
1966 	   LEVELGRAPH*           graph,              /**< LEVELGRAPH data structure */
1967 	   unsigned int          startnode,          /**< start node for path search */
1968 	   unsigned int*         distance,           /**< distances of searched nodes from root */
1969 	   unsigned int*         queue,              /**< node queue for path search */
1970 	   SCIP_Bool*            inQueue,            /**< whether node is in the queue */
1971 	   int*                  parentTreeBackward, /**< parent tree (-1 if no parent) */
1972 	   unsigned int          root,               /**< root of the current level graph */
1973 	   SCIP_Bool*            blocked             /**< whether nodes can be used */
1974 	   )
1975 	{
1976 	   unsigned int i;
1977 	   int startQueue;
1978 	   int endQueue;
1979 	   unsigned int u;
1980 	   int v;
1981 	   unsigned int d;
1982 	   int* parentTree;
1983 	   int* transform;
1984 	
1985 	   assert(scip != NULL);
1986 	   assert(graph != NULL);
1987 	   assert(graph->beginBackward != NULL);
1988 	   assert(graph->targetBackward != NULL);
1989 	   assert(graph->weightBackward != NULL);
1990 	   assert(distance != NULL);
1991 	   assert(queue != NULL);
1992 	   assert(inQueue != NULL);
1993 	   assert(scale >= 0);
1994 	
1995 	   /* allocate temporary memory */
1996 	   SCIP_CALL( SCIPallocBufferArray(scip, &parentTree, (int) graph->maxnodes) );
1997 	   SCIP_CALL( SCIPallocBufferArray(scip, &transform, (int) graph->maxnodes) );
1998 	
1999 	   assert(parentTree != NULL);
2000 	   assert(transform != NULL);
2001 	
2002 	   /* initialize distances */
2003 	   for( i = 0; i < graph->maxnodes; ++i )
2004 	   {
2005 	      distance[i] = 2 * (graph->nnodes) * (unsigned)scale;
2006 	      parentTree[i] = -1;
2007 	      parentTreeBackward[i] = -1;
2008 	      transform[i] = -1;
2009 	      inQueue[i] = FALSE;
2010 	   }
2011 	   distance[startnode] = 0;
2012 	
2013 	   /* initialize queue */
2014 	   startQueue = 0;
2015 	   endQueue = 0;
2016 	   queue[0] = startnode;
2017 	
2018 	   /* as long as queue is not empty */
2019 	   while( startQueue <= endQueue )
2020 	   {
2021 	      /* pop first node from queue */
2022 	      u = queue[startQueue];
2023 	      ++startQueue;
2024 	
2025 	      /* check adjacent nodes */
2026 	      assert(graph->beginBackward[u] >= 0);
2027 	      i = (unsigned int) graph->beginBackward[u];
2028 	      for( v = graph->targetBackward[i]; v >= 0; v = graph->targetBackward[++i] )
2029 	      {
2030 	         if( blocked[v] && v != (int) root)
2031 	            continue;
2032 	
2033 	         /* distance to u via current arc: */
2034 	         d = distance[u] + graph->weightBackward[i];
2035 	
2036 	         /* if we found a shorter connection */
2037 	         if( d < distance[v] )
2038 	         {
2039 	            distance[v] = d;
2040 	            parentTree[v] = (int) u;
2041 	
2042 	            /* insert in queue if not already present */
2043 	            if( !inQueue[v] )
2044 	            {
2045 	               ++endQueue;
2046 	               queue[endQueue] = (unsigned int) v;
2047 	               inQueue[v] = TRUE;
2048 	            }
2049 	         }
2050 	      }
2051 	      /* it is not necessary to stop if we found the root (in this case there are no arcs left) and we stop anyway */
2052 	   }
2053 	
2054 	   /* reverse order such that it is a path from the root */
2055 	   v = (int) root;
2056 	   transform[0] = (int) root;
2057 	   i = 1;
2058 	   while(parentTree[v] >= 0)
2059 	   {
2060 	      transform[i] = parentTree[v];
2061 	      ++i;
2062 	      v = parentTree[v];
2063 	   }
2064 	   --i;
2065 	   while(i > 0)
2066 	   {
2067 	      parentTreeBackward[transform[i]] = transform[i-1];
2068 	      --i;
2069 	   }
2070 	
2071 	   /* free temporary memory */
2072 	   SCIPfreeBufferArray(scip, &transform);
2073 	   SCIPfreeBufferArray(scip, &parentTree);
2074 	
2075 	   return SCIP_OKAY;
2076 	}
2077 	
2078 	/** create next level of level graph for odd cycle separation
2079 	 *
2080 	 *  @see separateHeur()
2081 	 */
2082 	static
2083 	SCIP_RETCODE createNextLevel(
2084 	   SCIP*                 scip,               /**< SCIP data structure */
2085 	   SCIP_SEPADATA*        sepadata,           /**< separator data structure */
2086 	   SCIP_VAR**            vars,               /**< problem variables */
2087 	   SCIP_Real*            vals,               /**< values of the binary variables in the current LP relaxation */
2088 	   LEVELGRAPH*           graph,              /**< LEVELGRAPH data structure */
2089 	   unsigned int          level,              /**< number of current level */
2090 	   SCIP_Bool*            inlevelgraph,       /**< flag array if node is already inserted in level graph */
2091 	   unsigned int*         curlevel,           /**< array of nodes of the current level */
2092 	   unsigned int          ncurlevel,          /**< number of nodes of the current level */
2093 	   unsigned int*         newlevel,           /**< array of nodes of the next level */
2094 	   unsigned int*         nnewlevel,          /**< number of nodes of the next level */
2095 	   SCIP_Bool*            success             /**< FALSE, iff memory reallocation fails */
2096 	   )
2097 	{
2098 	   unsigned int i;
2099 	   unsigned int nbinvars;
2100 	   unsigned int nAdj;
2101 	
2102 	   assert(scip != NULL);
2103 	   assert(vars != NULL);
2104 	   assert(vals != NULL);
2105 	   assert(graph != NULL);
2106 	   assert(graph->level != NULL);
2107 	   assert(graph->beginForward != NULL);
2108 	   assert(graph->targetForward != NULL);
2109 	   assert(graph->weightForward != NULL);
2110 	   assert(graph->beginBackward != NULL);
2111 	   assert(graph->targetBackward != NULL);
2112 	   assert(graph->weightBackward != NULL);
2113 	   assert(graph->beginAdj != NULL);
2114 	   assert(graph->levelAdj != NULL);
2115 	   assert(graph->sourceAdj != NULL);
2116 	   assert(graph->targetAdj != NULL);
2117 	   assert(graph->weightAdj != NULL);
2118 	   assert(inlevelgraph != NULL);
2119 	   assert(curlevel != NULL);
2120 	   assert(newlevel != NULL);
2121 	   assert(success != NULL);
2122 	
2123 	   *nnewlevel = 0;
2124 	   nAdj = 0;
2125 	   assert(graph->maxnodes % 2 == 0);
2126 	   nbinvars = (graph->maxnodes)/2;
2127 	
2128 	   /* for every node in current level add its implications and assign its neighbors to the next
2129 	    * level, if neighbor is not already existing in the level graph
2130 	    */
2131 	   for( i = 0; i < ncurlevel; ++i )
2132 	   {
2133 	      unsigned int negated;
2134 	      unsigned int u;
2135 	
2136 	      /* get node */
2137 	      u = curlevel[i];
2138 	      assert(u < graph->maxnodes);
2139 	      assert(graph->level[u] == level);
2140 	      assert(graph->beginForward[u] < 0);
2141 	      assert(graph->beginBackward[u] < 0);
2142 	      assert(graph->beginAdj[u] < 0);
2143 	      assert(inlevelgraph[u]);
2144 	
2145 	      /* get negated */
2146 	      if( u < nbinvars )
2147 	         negated = u + nbinvars;
2148 	      else
2149 	         negated = u - nbinvars;
2150 	      assert(negated < graph->maxnodes);
2151 	      assert(negated < nbinvars || u < nbinvars);
2152 	      assert(negated >= nbinvars || u >= nbinvars);
2153 	
2154 	      /* initialize adjacency lists for node u */
2155 	      graph->beginForward[u] = (int) graph->lastF;
2156 	      graph->beginBackward[u] = (int) graph->lastB;
2157 	      graph->beginAdj[u] = (int) (graph->levelAdj[level+1] + nAdj);
2158 	
2159 	      /* if we want to add arcs between a variable and its negated */
2160 	      if( sepadata->addselfarcs )
2161 	      {
2162 	         /* add negated variable, if not existing in the levelgraph,
2163 	          * but if the level contains more nodes than allowed
2164 	          * (defined by percent per level plus offset),
2165 	          * we skip the rest of the nodes
2166 	          */
2167 	         if( !inlevelgraph[negated] && (*nnewlevel) <= sepadata->maxlevelsize )
2168 	         {
2169 	            ++(graph->nnodes);
2170 	            graph->level[negated] = level+1;
2171 	            inlevelgraph[negated] = TRUE;
2172 	            newlevel[*nnewlevel] = negated;
2173 	            ++(*nnewlevel);
2174 	         }
2175 	         assert( *nnewlevel > sepadata->maxlevelsize || inlevelgraph[negated] );
2176 	
2177 	         /* add self-arc if negated variable is on a neighbored level */
2178 	         if( inlevelgraph[negated] && ((graph->level[negated] == level - 1)
2179 	               || (graph->level[negated] == level) || (graph->level[negated] == level + 1)) )
2180 	         {
2181 	            /* add arc from u to its negated variable */
2182 	            SCIP_CALL( addArc(scip, graph, u, negated, level, 0, &nAdj, success) );
2183 	            if( !(*success) )
2184 	               return SCIP_OKAY;
2185 	         }
2186 	      }
2187 	
2188 	      /* insert level of sorted root neighbors (if requested) */
2189 	      if( graph->nlevels == 0 && sepadata->sortrootneighbors )
2190 	      {
2191 	         SCIP_CALL( insertSortedRootNeighbors(scip, graph, nbinvars, ncurlevel, u, vals, vars,
2192 	               sepadata, nnewlevel, inlevelgraph, level, newlevel, success) );
2193 	      }
2194 	      else
2195 	      {
2196 	         SCIP_CALL( addNextLevelCliques(scip, sepadata, vars, vals, u, graph, level, inlevelgraph,
2197 	               newlevel, nnewlevel, &nAdj, success) );
2198 	      }
2199 	      if( !(*success) )
2200 	         return SCIP_OKAY;
2201 	
2202 	      /* every node has a backward arc */
2203 	      assert(graph->lastB > (unsigned int) graph->beginBackward[u] || graph->nlevels == 0 );
2204 	
2205 	      /* root has outgoing arcs otherwise we would have skipped it */
2206 	      assert(graph->lastF > 0);
2207 	
2208 	      /* close adjacency lists */
2209 	      graph->targetForward[graph->lastF] = -1;
2210 	      ++(graph->lastF);
2211 	      if( graph->lastF == graph->sizeForward )
2212 	      {
2213 	         SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeForward), &(graph->targetForward),
2214 	               &(graph->weightForward), NULL, NULL, success) );
2215 	
2216 	         if( !(*success) )
2217 	            return SCIP_OKAY;
2218 	      }
2219 	      graph->targetBackward[graph->lastB] = -1;
2220 	      ++(graph->lastB);
2221 	      if( graph->lastB == graph->sizeBackward )
2222 	      {
2223 	         SCIP_CALL( checkArraySizesHeur(scip, graph, &(graph->sizeBackward), &(graph->targetBackward),
2224 	               &(graph->weightBackward), NULL, NULL, success) );
2225 	
2226 	         if( !(*success) )
2227 	            return SCIP_OKAY;
2228 	      }
2229 	
2230 	      /* terminate adjacency list with 0 for current level lifting */
2231 	      graph->sourceAdj[graph->levelAdj[level+1]+nAdj] = 0;
2232 	      graph->targetAdj[graph->levelAdj[level+1]+nAdj] = 0;
2233 	   }
2234 	   graph->levelAdj[level+2] = graph->levelAdj[level+1]+nAdj;
2235 	
2236 	   return SCIP_OKAY;
2237 	}
2238 	
2239 	/** The heuristic method for finding odd cycles by Hoffman, Padberg uses a level graph
2240 	 *  which is constructed as follows:
2241 	 *  First we choose a node (i.e. a variable of the problem or its negated) as root
2242 	 *  and assign it to level 0 (and no other node is assigned to level 0).
2243 	 *  All neighbors of the root are assigned to level 1 and the arcs between are added.
2244 	 *
2245 	 *  In general:
2246 	 *  All neighbors of nodes in level i that are assigned to level i+1, if they do not already appear in levels <= i.
2247 	 *  All arcs between nodes in level i and their neighbors are added.
2248 	 *
2249 	 *  In the construction we only take nodes that are contained in the fractional graph,
2250 	 *  i.e., their current LP values are not integral.
2251 	 *
2252 	 *  Since SCIP stores implications between original and negated variables,
2253 	 *  the level graph has at most twice the number of fractional binary variables of the problem.
2254 	 *
2255 	 *  Since the implication graph of SCIP is (normally) incomplete,
2256 	 *  it is possible to use arcs between an original variable and its negated
2257 	 *  to obtain more cycles which are valid but not found due to missing links.
2258 	 */
2259 	static
2260 	SCIP_RETCODE separateHeur(
2261 	   SCIP*                 scip,               /**< SCIP data structure */
2262 	   SCIP_SEPA*            sepa,               /**< separator */
2263 	   SCIP_SEPADATA*        sepadata,           /**< separator data structure */
2264 	   SCIP_SOL*             sol,                /**< given primal solution */
2265 	   SCIP_RESULT*          result              /**< pointer to store the result of the separation call */
2266 	   )
2267 	{
2268 	   /* memory for variable data */
2269 	   SCIP_VAR** scipvars;                      /* variables of the current SCIP (unsorted) */
2270 	   SCIP_VAR** vars;                          /* variables of the current SCIP (sorted if requested) */
2271 	   SCIP_Real* vals;                          /* LP-values of the variables (and negated variables) */
2272 	   unsigned int nbinvars;                    /* number of nodecandidates for implicationgraph */
2273 	   unsigned int* incut;                      /* flag array for check if a variable is already covered by a cut */
2274 	
2275 	   /* storage for levelgraph */
2276 	   LEVELGRAPH graph;
2277 	   unsigned int* curlevel;
2278 	   unsigned int* newlevel;
2279 	   unsigned int ncurlevel;
2280 	   unsigned int nnewlevel;
2281 	   SCIP_Bool* inlevelgraph;
2282 	
2283 	   /* storage for path finding */
2284 	   unsigned int* queue;
2285 	   SCIP_Bool* inQueue;
2286 	   int* parentTree;
2287 	   int* parentTreeBackward;
2288 	   unsigned int* distance;
2289 	   SCIP_Bool* blocked;
2290 	
2291 	   /* counter and limits  */
2292 	   unsigned int maxroots;                    /* maximum of level graph roots */
2293 	   unsigned int rootcounter;                 /* counter of tried roots */
2294 	   unsigned int ncutsroot;                   /* counter of cuts per root */
2295 	   unsigned int ncutslevel;                  /* counter of cuts per level */
2296 	
2297 	   unsigned int i;
2298 	   unsigned int j;
2299 	   unsigned int k;
2300 	
2301 	   int nscipbinvars;
2302 	   int nscipintvars;
2303 	   int nscipimplvars;
2304 	   int nintegral;
2305 	   int l;
2306 	
2307 	   assert(scip != NULL);
2308 	   assert(sepadata != NULL);
2309 	   assert(result != NULL);
2310 	
2311 	   SCIP_CALL( SCIPgetVarsData(scip, &scipvars, NULL, &nscipbinvars, &nscipintvars, &nscipimplvars, NULL) );
2312 	   assert(nscipbinvars >= 0);
2313 	   assert(nscipintvars >= 0);
2314 	   assert(nscipimplvars >= 0);
2315 	
2316 	   nintegral = nscipbinvars + nscipintvars + nscipimplvars;
2317 	   assert(scipvars != NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0)));
2318 	
2319 	   /* collect binary variables, including implicit binary */
2320 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars, nintegral) );
2321 	   for (l = 0; l < nscipbinvars; ++l)
2322 	      vars[l] = scipvars[l]; /*lint !e613*/
2323 	
2324 	   nbinvars = (unsigned int) nscipbinvars;
2325 	   for (l = nscipbinvars; l < nintegral; ++l)
2326 	   {
2327 	      assert( SCIPvarGetType(scipvars[l]) != SCIP_VARTYPE_CONTINUOUS ); /*lint !e613*/
2328 	      if ( SCIPvarIsBinary(scipvars[l]) ) /*lint !e613*/
2329 	         vars[nbinvars++] = scipvars[l]; /*lint !e613*/
2330 	   }
2331 	
2332 	   if( nbinvars == 0 )
2333 	   {
2334 	      SCIPfreeBufferArray(scip, &vars);
2335 	      return SCIP_OKAY;
2336 	   }
2337 	
2338 	   /* initialize flag array to avoid multiple cuts per variable, if requested by user-flag */
2339 	   SCIP_CALL( SCIPallocBufferArray(scip, &vals, (int) (2 * nbinvars)) );
2340 	
2341 	   /* prepare values */
2342 	   assert( vars != NULL );
2343 	   switch( sepadata->sortswitch )
2344 	   {
2345 	   case UNSORTED :
2346 	      /* if no sorting is requested, we use the normal variable array */
2347 	      break;
2348 	
2349 	   case MAXIMAL_LPVALUE :
2350 	      /* store lp-values */
2351 	      for( i = 0; i < nbinvars; ++i )
2352 	         vals[i] = SCIPgetSolVal(scip, sol, vars[i]);
2353 	
2354 	      /* sort by lp-value, maximal first */
2355 	      SCIPsortDownRealPtr(vals, (void**)vars, (int) nbinvars);
2356 	      break;
2357 	
2358 	   case MINIMAL_LPVALUE :
2359 	      /* store lp-values */
2360 	      for( i = 0; i < nbinvars; ++i )
2361 	         vals[i] = SCIPgetSolVal(scip, sol, vars[i]);
2362 	
2363 	      /* sort by lp-value, minimal first */
2364 	      SCIPsortRealPtr(vals, (void**)vars, (int) nbinvars);
2365 	      break;
2366 	
2367 	   case MAXIMAL_FRACTIONALITY  :
2368 	      /* store lp-values and determine fractionality */
2369 	      for( i = 0; i < nbinvars; ++i )
2370 	      {
2371 	         vals[i] = SCIPgetSolVal(scip, sol, vars[i]);
2372 	         vals[i] = MIN(1.0 - vals[i], vals[i]);
2373 	      }
2374 	
2375 	      /* sort by fractionality, maximal first */
2376 	      SCIPsortDownRealPtr(vals, (void**)vars, (int) nbinvars);
2377 	      break;
2378 	
2379 	   case MINIMAL_FRACTIONALITY :
2380 	      /* store lp-values and determine fractionality */
2381 	      for( i = 0; i < nbinvars; ++i )
2382 	      {
2383 	         vals[i] = SCIPgetSolVal(scip, sol, vars[i]);
2384 	         vals[i] = MIN(1.0 - vals[i], vals[i]);
2385 	      }
2386 	
2387 	      /* sort by fractionality, minimal first */
2388 	      SCIPsortRealPtr(vals, (void**)vars, (int) nbinvars);
2389 	      break;
2390 	
2391 	   default :
2392 	      SCIPerrorMessage("invalid sortswitch value\n");
2393 	      SCIPABORT();
2394 	      return SCIP_INVALIDDATA;  /*lint !e527*/
2395 	   }
2396 	   assert(vars != NULL);
2397 	
2398 	   /* create mapping for getting the index of a variable via its probindex to the index in the sorted variable array */
2399 	   SCIP_CALL( SCIPallocBufferArray(scip, &(sepadata->mapping), nintegral) );
2400 	
2401 	   /* initialize LP value and cut flag for all variables */
2402 	   for( i = 0; i < nbinvars; ++i )
2403 	   {
2404 	      assert( 0 <= SCIPvarGetProbindex(vars[i]) && SCIPvarGetProbindex(vars[i]) < nintegral);  /* since binary, integer, and implicit variables are first */
2405 	      sepadata->mapping[SCIPvarGetProbindex(vars[i])] = i;
2406 	      vals[i] = SCIPgetSolVal(scip, sol, vars[i]); /* need to get new values, since they might be corrupted */
2407 	   }
2408 	
2409 	   for( i = nbinvars; i < 2*nbinvars; ++i )
2410 	      vals[i] = 1.0 - vals[i - nbinvars];
2411 	
2412 	   /* determine size of level graph */
2413 	   graph.maxnodes = 2 * nbinvars;
2414 	
2415 	   /* the implication graph is redundant and therefore more implications and clique arcs may occur than should be possible
2416 	    * @todo later: filtering of edges which were already added
2417 	    */
2418 	   /* graph.maxarcs = nbinvars*(2*nbinvars-1); */ /* = 2*nbinvars*(2*nbinvars-1)/2 */
2419 	   graph.maxarcs = UINT_MAX;
2420 	
2421 	   /* set sizes for graph memory storage */
2422 	   graph.sizeForward = 100 * graph.maxnodes;
2423 	   graph.sizeBackward = 100 * graph.maxnodes;
2424 	   graph.sizeAdj = 100 * graph.maxnodes;
2425 	
2426 	   /* allocate memory for level graph structure */
2427 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.level, (int) graph.maxnodes) );
2428 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.beginForward, (int) graph.maxnodes) );
2429 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.beginBackward, (int) graph.maxnodes) );
2430 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetForward, (int) MIN(graph.sizeForward, graph.maxarcs)) );
2431 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetBackward, (int) MIN(graph.sizeBackward, graph.maxarcs)) );
2432 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightForward, (int) MIN(graph.sizeForward, graph.maxarcs)) );
2433 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightBackward, (int) MIN(graph.sizeBackward, graph.maxarcs)) );
2434 	
2435 	   SCIP_CALL( SCIPallocBufferArray(scip, &curlevel, (int) graph.maxnodes) );
2436 	   SCIP_CALL( SCIPallocBufferArray(scip, &newlevel, (int) graph.maxnodes) );
2437 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.beginAdj, (int) graph.maxnodes) );
2438 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.sourceAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) );
2439 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.targetAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) );
2440 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.weightAdj, (int) MIN(graph.sizeAdj, graph.maxarcs)) );
2441 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.levelAdj, (int) graph.maxnodes) );
2442 	   SCIP_CALL( SCIPallocBufferArray(scip, &inlevelgraph, (int) graph.maxnodes) );
2443 	
2444 	   SCIP_CALL( SCIPallocBufferArray(scip, &queue, (int) graph.maxnodes) );
2445 	   SCIP_CALL( SCIPallocBufferArray(scip, &inQueue, (int) graph.maxnodes) );
2446 	   SCIP_CALL( SCIPallocBufferArray(scip, &parentTree, (int) graph.maxnodes) );
2447 	   SCIP_CALL( SCIPallocBufferArray(scip, &parentTreeBackward, (int) graph.maxnodes) );
2448 	   SCIP_CALL( SCIPallocBufferArray(scip, &distance, (int) graph.maxnodes) );
2449 	   SCIP_CALL( SCIPallocBufferArray(scip, &blocked, (int) graph.maxnodes) );
2450 	
2451 	   SCIP_CALL( SCIPallocBufferArray(scip, &incut, (int) (2 * nbinvars)) );
2452 	
2453 	   /* initialize cut flag for all variables */
2454 	   BMSclearMemoryArray(incut, 2*nbinvars);
2455 	
2456 	   /* determine the number of level graph roots */
2457 	   maxroots = (unsigned int) SCIPceil(scip, sepadata->offsettestvars + (0.02 * nbinvars * sepadata->percenttestvars));
2458 	   sepadata->maxlevelsize = (unsigned int) SCIPceil(scip, sepadata->offsetnodeslevel + 0.01 * sepadata->maxpernodeslevel * graph.maxnodes);
2459 	   rootcounter = 0;
2460 	
2461 	   /* check each node as root */
2462 	   for( i = (unsigned int) sepadata->lastroot; i < graph.maxnodes && rootcounter < maxroots
2463 	           && sepadata->ncuts - sepadata->oldncuts < (unsigned int) sepadata->maxsepacutsround
2464 	           && !SCIPisStopped(scip) ; ++i )
2465 	   {
2466 	      /* skip node if it is already covered by a cut and if we do not want to search cycles starting
2467 	       * with a node already covered by a cut */
2468 	      if( incut[i] && ! sepadata->multiplecuts )
2469 	         continue;
2470 	
2471 	      /* skip variable if its LP-value is not fractional */
2472 	      if( SCIPisFeasIntegral(scip, vals[i]) )
2473 	         continue;
2474 	
2475 	      /* consider original and negated variable pair and skip variable if there is only one edge leaving the pair */
2476 	      if( SCIPvarGetNCliques(vars[i % nbinvars], TRUE) + SCIPvarGetNCliques(vars[i % nbinvars], FALSE) == 0 )
2477 	         continue;
2478 	
2479 	      /* skip variable having too less implics and cliques itself */
2480 	      if( i < nbinvars )
2481 	      {
2482 	         if( SCIPvarGetNCliques(vars[i % nbinvars], TRUE ) == 0 )
2483 	            continue;
2484 	         if( !(sepadata->addselfarcs) && SCIPvarGetNCliques(vars[i % nbinvars], TRUE ) == 0 )
2485 	            continue;
2486 	      }
2487 	      else
2488 	      {
2489 	         if( SCIPvarGetNCliques(vars[i % nbinvars], FALSE) == 0 )
2490 	            continue;
2491 	
2492 	         if( !(sepadata->addselfarcs) && SCIPvarGetNCliques(vars[i % nbinvars], FALSE) == 0 )
2493 	            continue;
2494 	      }
2495 	
2496 	      /* node is actually considered as root node for the level graph */
2497 	      ++rootcounter;
2498 	      ncutsroot = 0;
2499 	
2500 	      /* initialize graph */
2501 	      for( j = 0; j < graph.maxnodes; ++j)
2502 	      {
2503 	         graph.beginForward[j] = -1;
2504 	         graph.beginBackward[j] = -1;
2505 	         graph.beginAdj[j] = -1;
2506 	         inlevelgraph[j] = FALSE;
2507 	         blocked[j] = FALSE;
2508 	      }
2509 	      graph.lastF = 0;
2510 	      graph.lastB = 0;
2511 	      graph.nlevels = 0;
2512 	      graph.narcs = 0;
2513 	
2514 	      /* insert root (first level contains root only) */
2515 	      inlevelgraph[i] = TRUE;
2516 	      graph.level[i] = 0;
2517 	      graph.levelAdj[0] = 0;
2518 	      graph.nnodes = 1;
2519 	      curlevel[0] = i;
2520 	      ncurlevel = 1;
2521 	
2522 	      /* there are no arcs inside the root level */
2523 	      graph.levelAdj[graph.nlevels+1] = 0;
2524 	
2525 	      /* create new levels until there are not more nodes for a new level */
2526 	      do
2527 	      {
2528 	         SCIP_Bool success;
2529 	         success = TRUE;
2530 	
2531 	         /* all neighbors of nodes in level i that are assigned to level i+1,
2532 	            if they do not already appear in levels <= i. */
2533 	         SCIP_CALL( createNextLevel(scip, sepadata, vars, vals, &graph, graph.nlevels, inlevelgraph,
2534 	               curlevel, ncurlevel, newlevel, &nnewlevel, &success) );
2535 	
2536 	         if( !success )
2537 	            goto TERMINATE;
2538 	
2539 	         /* search for odd holes */
2540 	         if( graph.nlevels > 0 && (sepadata->includetriangles || graph.nlevels > 1) )
2541 	         {
2542 	            unsigned int maxcutslevel;
2543 	
2544 	            ncutslevel = 0;
2545 	
2546 	            /* calculate maximal cuts in this level due to cut limitations (per level, per root, per separation round) */
2547 	            maxcutslevel = (unsigned int) sepadata->maxcutslevel;
2548 	            maxcutslevel = (unsigned int) MIN((int) maxcutslevel, (int) ncutsroot - sepadata->maxcutsroot);
2549 	            maxcutslevel = (unsigned int) MIN((int) maxcutslevel, sepadata->maxsepacutsround + (int) sepadata->oldncuts - (int) sepadata->ncuts);
2550 	
2551 	            /* for each cross edge in this level find both shortest paths to root (as long as no limits are reached) */
2552 	            for( j = graph.levelAdj[graph.nlevels+1]; j < graph.levelAdj[graph.nlevels+2]
2553 	                    && ncutslevel < maxcutslevel && !SCIPisStopped(scip); ++j )
2554 	            {
2555 	               unsigned int ncyclevars;
2556 	               unsigned int u;
2557 	
2558 	               /* storage for cut generation */
2559 	               unsigned int* pred; /* predecessor list */
2560 	               SCIP_Bool* incycle; /* flag array for check of double variables in found cycle */
2561 	
2562 	               assert(graph.sourceAdj[j] < graph.targetAdj[j]);
2563 	
2564 	               /* find shortest path from source to root and update weight of cycle */
2565 	               SCIP_CALL( findShortestPathToRoot(scip, sepadata->scale, &graph, graph.sourceAdj[j], distance, queue, inQueue, parentTree) );
2566 	
2567 	#ifndef NDEBUG
2568 	               /* check that this path ends in the root node */
2569 	               u = i;
2570 	               k = 1;
2571 	               while( u != graph.sourceAdj[j] )
2572 	               {
2573 	                  assert(parentTree[u] != -1 && k <= graph.maxnodes);
2574 	                  u = (unsigned int) parentTree[u];
2575 	                  ++k;
2576 	               }
2577 	#endif
2578 	
2579 	               /* block all nodes that are adjacent to nodes of the first path */
2580 	               for( k = 0; k < graph.nnodes; ++k )
2581 	                  blocked[k] = FALSE;
2582 	               SCIP_CALL( blockRootPath(scip, &graph, graph.sourceAdj[j], inlevelgraph, blocked, parentTree, i) );
2583 	
2584 	               /* if the target is block, no violated odd hole can be found */
2585 	               if( blocked[graph.targetAdj[j]] )
2586 	                  continue;
2587 	
2588 	               /* find shortest path from root to target node avoiding blocked nodes */
2589 	               SCIP_CALL( findUnblockedShortestPathToRoot(scip, sepadata->scale, &graph,
2590 	                     graph.targetAdj[j], distance, queue, inQueue, parentTreeBackward, i, blocked) );
2591 	
2592 	               /* no odd cycle cut found */
2593 	               if( parentTreeBackward[graph.targetAdj[j]] < 0 )
2594 	                  continue;
2595 	
2596 	               /* allocate and initialize predecessor list and flag array representing odd cycle */
2597 	               SCIP_CALL( SCIPallocBufferArray(scip, &pred, (int) (2 * nbinvars)) );
2598 	               SCIP_CALL( SCIPallocBufferArray(scip, &incycle, (int) (2 * nbinvars)) );
2599 	               for( k = 0; k < 2 * nbinvars; ++k )
2600 	               {
2601 	                  pred[k] = DIJKSTRA_UNUSED;
2602 	                  incycle[k] = FALSE;
2603 	               }
2604 	               ncyclevars = 0;
2605 	               success = TRUE;
2606 	
2607 	               /* check cycle for x-neg(x)-sub-cycles and clean them
2608 	                *  (note that a variable cannot appear twice in a cycle since it is only once in the graph)
2609 	                * convert parentTreeBackward and parentTree to pred&incycle structure for generateOddCycleCut
2610 	                */
2611 	               u = graph.targetAdj[j];
2612 	
2613 	               /* add path to root to cycle */
2614 	               while( success && u != i )
2615 	               {
2616 	                  /* insert u in predecessor list */
2617 	                  pred[u] = (unsigned int) parentTreeBackward[u];
2618 	
2619 	                  /* remove pairs of original and negated variable from cycle */
2620 	                  SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2621 	                        sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
2622 	
2623 	                  assert(parentTreeBackward[u] >= 0 || u == i);
2624 	
2625 	                  /* select next node on path */
2626 	                  u = (unsigned int) parentTreeBackward[u];
2627 	               }
2628 	
2629 	               /* add path from root to cycle */
2630 	               while( success && u != graph.sourceAdj[j] )
2631 	               {
2632 	                  /* insert u in predecessor list */
2633 	                  pred[u] = (unsigned int) parentTree[u];
2634 	
2635 	                  /* remove pairs of original and negated variable from cycle */
2636 	                  SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2637 	                        sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
2638 	
2639 	                  /* select next node on path */
2640 	                  u = (unsigned int) parentTree[u];
2641 	               }
2642 	               assert(!success || u == graph.sourceAdj[j]);
2643 	
2644 	               /* close the cycle */
2645 	               if( success )
2646 	               {
2647 	                  pred[u] = graph.targetAdj[j];
2648 	
2649 	                  /* remove pairs of original and negated variable from cycle */
2650 	                  SCIP_CALL( cleanCycle(scip, pred, incycle, incut, u, graph.targetAdj[j], nbinvars, &ncyclevars,
2651 	                        sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
2652 	               }
2653 	
2654 	               /* generate cut (if cycle is valid) */
2655 	               if(success)
2656 	               {
2657 	                  GRAPHDATA graphdata;
2658 	                  unsigned int oldncuts;
2659 	
2660 	                  graphdata.usegls = FALSE;
2661 	                  graphdata.levelgraph = &graph;
2662 	                  graphdata.dijkstragraph = NULL;
2663 	
2664 	                  oldncuts = sepadata->ncuts;
2665 	
2666 	                  SCIP_CALL( generateOddCycleCut(scip, sepa, sol, vars, nbinvars, graph.targetAdj[j], pred, ncyclevars,
2667 	                        incut, vals, sepadata, &graphdata, result) );
2668 	
2669 	                  if(oldncuts < sepadata->ncuts)
2670 	                  {
2671 	                     ++ncutsroot;
2672 	                     ++ncutslevel;
2673 	                  }
2674 	               }
2675 	
2676 	               /* free temporary memory */
2677 	               SCIPfreeBufferArray(scip, &incycle);
2678 	               SCIPfreeBufferArray(scip, &pred);
2679 	
2680 	               if ( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM )
2681 	                  break;
2682 	            }
2683 	         }
2684 	
2685 	         if ( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM )
2686 	            break;
2687 	
2688 	         /* copy new level to current one */
2689 	         ++(graph.nlevels);
2690 	         for( j = 0; j < nnewlevel; ++j )
2691 	            curlevel[j] = newlevel[j];
2692 	         ncurlevel = nnewlevel;
2693 	      }
2694 	      /* stop level creation loop if new level is empty or any limit is reached */
2695 	      while( nnewlevel > 0 && !SCIPisStopped(scip)
2696 	         && graph.nlevels < (unsigned int) sepadata->maxnlevels
2697 	         && ncutsroot < (unsigned int) sepadata->maxcutsroot
2698 	         && sepadata->ncuts - sepadata->oldncuts < (unsigned int) sepadata->maxsepacutsround);
2699 	   }
2700 	
2701 	   /* store the last tried root (when running without sorting the variable array, we don't want
2702 	    * to always check the same variables and therefore start next time where we stopped last time)
2703 	    */
2704 	   if( sepadata->sortswitch == UNSORTED )
2705 	   {
2706 	      if( i == graph.maxnodes )
2707 	         sepadata->lastroot = 0;
2708 	      else
2709 	         sepadata->lastroot = (int) i;
2710 	   }
2711 	
2712 	 TERMINATE:
2713 	   /* free memory */
2714 	   SCIPfreeBufferArray(scip, &incut);
2715 	
2716 	   SCIPfreeBufferArray(scip, &blocked);
2717 	   SCIPfreeBufferArray(scip, &distance);
2718 	   SCIPfreeBufferArray(scip, &parentTreeBackward);
2719 	   SCIPfreeBufferArray(scip, &parentTree);
2720 	   SCIPfreeBufferArray(scip, &inQueue);
2721 	   SCIPfreeBufferArray(scip, &queue);
2722 	
2723 	   SCIPfreeBufferArray(scip, &inlevelgraph);
2724 	   SCIPfreeBufferArray(scip, &graph.levelAdj);
2725 	   SCIPfreeBufferArray(scip, &graph.weightAdj);
2726 	   SCIPfreeBufferArray(scip, &graph.targetAdj);
2727 	   SCIPfreeBufferArray(scip, &graph.sourceAdj);
2728 	   SCIPfreeBufferArray(scip, &graph.beginAdj);
2729 	   SCIPfreeBufferArray(scip, &newlevel);
2730 	   SCIPfreeBufferArray(scip, &curlevel);
2731 	
2732 	   SCIPfreeBufferArray(scip, &graph.weightBackward);
2733 	   SCIPfreeBufferArray(scip, &graph.weightForward);
2734 	   SCIPfreeBufferArray(scip, &graph.targetBackward);
2735 	   SCIPfreeBufferArray(scip, &graph.targetForward);
2736 	   SCIPfreeBufferArray(scip, &graph.beginBackward);
2737 	   SCIPfreeBufferArray(scip, &graph.beginForward);
2738 	   SCIPfreeBufferArray(scip, &graph.level);
2739 	
2740 	   SCIPfreeBufferArray(scip, &(sepadata->mapping));
2741 	   SCIPfreeBufferArray(scip, &vals);
2742 	   SCIPfreeBufferArray(scip, &vars);
2743 	
2744 	   return SCIP_OKAY;
2745 	}
2746 	
2747 	
2748 	/* methods for separateGLS() */
2749 	
2750 	/** memory reallocation method (the graph is normally very dense, so we dynamically allocate only the memory we need) */
2751 	static
2752 	SCIP_RETCODE checkArraySizesGLS(
2753 	   SCIP*                 scip,               /**< SCIP data structure */
2754 	   unsigned int          maxarcs,            /**< maximal size of graph->head and graph->weight */
2755 	   unsigned int*         arraysize,          /**< current size of graph->head and graph->weight */
2756 	   DIJKSTRA_GRAPH*       graph,              /**< Dijkstra Graph data structure */
2757 	   SCIP_Bool*            success             /**< FALSE, iff memory reallocation fails */
2758 	   )
2759 	{
2760 	   SCIP_Real memorylimit;
2761 	   unsigned int additional;
2762 	   unsigned int j;
2763 	   unsigned int oldarraysize;
2764 	
2765 	   assert(scip != NULL);
2766 	   assert(arraysize != NULL);
2767 	   assert(graph != NULL);
2768 	   assert(graph->head != NULL);
2769 	   assert(graph->weight != NULL);
2770 	   assert(success != NULL);
2771 	
2772 	   SCIPdebugMsg(scip, "reallocating graph->head and graph->weight...\n");
2773 	
2774 	   additional = (MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((int) sizeof(*(graph->head)));
2775 	   additional += (MIN(maxarcs, 2 * (*arraysize)) - (*arraysize)) * ((int) sizeof(*(graph->weight)));
2776 	
2777 	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
2778 	   if( !SCIPisInfinity(scip, memorylimit) )
2779 	   {
2780 	      memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
2781 	      memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
2782 	   }
2783 	
2784 	   /* if memorylimit would be exceeded or any other limit is reached free all data and exit */
2785 	   if( memorylimit <= additional/1048576.0 || SCIPisStopped(scip) )
2786 	   {
2787 	      *success = FALSE;
2788 	      SCIPdebugMsg(scip, "...memory limit exceeded\n");
2789 	      return SCIP_OKAY;
2790 	   }
2791 	
2792 	   oldarraysize = *arraysize;
2793 	   *arraysize = 2*(*arraysize);
2794 	
2795 	   SCIP_CALL( SCIPreallocBufferArray(scip, &(graph->head), (int) MIN(maxarcs, (*arraysize))) );
2796 	   SCIP_CALL( SCIPreallocBufferArray(scip, &(graph->weight), (int) MIN(maxarcs, (*arraysize))) );
2797 	
2798 	   /* if memorylimit exceeded, leave the separator */
2799 	   SCIP_CALL( SCIPgetRealParam(scip, "limits/memory", &memorylimit) );
2800 	
2801 	   if( !SCIPisInfinity(scip, memorylimit) )
2802 	   {
2803 	      memorylimit -= SCIPgetMemUsed(scip)/1048576.0;
2804 	      memorylimit -= SCIPgetMemExternEstim(scip)/1048576.0;
2805 	   }
2806 	
2807 	   if( memorylimit <= 2.0*SCIPgetMemExternEstim(scip)/1048576.0 )
2808 	   {
2809 	      SCIPdebugMsg(scip, "...memory limit exceeded - freeing all arrays\n");
2810 	      *success = FALSE;
2811 	      return SCIP_OKAY;
2812 	   }
2813 	
2814 	   /* initialize new segments of graph as empty graph */
2815 	   for( j = oldarraysize; j < MIN(maxarcs,(*arraysize)); ++j )
2816 	   {
2817 	      (graph->head)[j] = DIJKSTRA_UNUSED;
2818 	      (graph->weight)[j] = DIJKSTRA_UNUSED;
2819 	   }
2820 	
2821 	   SCIPdebugMsg(scip, "...with success\n");
2822 	
2823 	   return SCIP_OKAY;
2824 	}
2825 	
2826 	/** add implications from cliques of the given node */
2827 	static
2828 	SCIP_RETCODE addGLSCliques(
2829 	   SCIP*                 scip,               /**< SCIP data structure */
2830 	   SCIP_SEPADATA*        sepadata,           /**< separator data structure */
2831 	   SCIP_VAR**            vars,               /**< problem variables */
2832 	   unsigned int          varsidx,            /**< index of current variable inside the problem variables */
2833 	   unsigned int          dijkindex,          /**< index of current variable inside the Dijkstra Graph */
2834 	   SCIP_Real*            vals,               /**< value of the variables in the given solution */
2835 	   unsigned int          nbinvars,           /**< number of binary problem variables */
2836 	   unsigned int          ncliques,           /**< number of cliques of the current node */
2837 	   DIJKSTRA_GRAPH*       graph,              /**< Dijkstra Graph data structure */
2838 	   unsigned int*         narcs,              /**< current number of arcs inside the Dijkstra Graph */
2839 	   unsigned int          maxarcs,            /**< maximal number of arcs inside the Dijkstra Graph */
2840 	   SCIP_Bool             original,           /**< TRUE, iff variable is a problem variable */
2841 	   SCIP_Bool*            emptygraph,         /**< TRUE, iff there is no arc in the implication graph of the binary variables of SCIP */
2842 	   unsigned int*         arraysize,          /**< current size of graph->head and graph->weight */
2843 	   SCIP_Bool*            success             /**< FALSE, iff memory reallocation fails */
2844 	   )
2845 	{
2846 	   SCIP_VAR* neighbor;                       /* current neighbor of the current variable */
2847 	   unsigned int neighindex;
2848 	   SCIP_CLIQUE** cliques;                    /* cliques of the current variable (with x==0/1) */
2849 	   unsigned int ncliquevars;                 /* number of variables of a clique */
2850 	   SCIP_VAR** cliquevars;                    /* variables of a clique */
2851 	   SCIP_Bool* cliquevals;                    /* is the cliquevariable fixed to TRUE or to FALSE */
2852 	   unsigned int k;
2853 	   unsigned int m;
2854 	
2855 	   assert(scip != NULL);
2856 	   assert(sepadata != NULL);
2857 	   assert(vars != NULL);
2858 	   assert(graph != NULL);
2859 	   assert(graph->head != NULL);
2860 	   assert(graph->weight != NULL);
2861 	   assert(narcs != NULL);
2862 	   assert(emptygraph != NULL);
2863 	   assert(arraysize != NULL);
2864 	   assert(success != NULL);
2865 	
2866 	   /* if current variable has cliques of current clique-type */
2867 	   cliques = SCIPvarGetCliques(vars[varsidx], original);
2868 	   assert(cliques != NULL || ncliques == 0);
2869 	
2870 	   for( k = 0; k < ncliques; ++k )
2871 	   {
2872 	      assert( cliques != NULL ); /* for lint */
2873 	
2874 	      /* get clique data */
2875 	      cliquevars = SCIPcliqueGetVars(cliques[k]);
2876 	      ncliquevars = (unsigned int) SCIPcliqueGetNVars(cliques[k]);
2877 	      cliquevals = SCIPcliqueGetValues(cliques[k]);
2878 	
2879 	      assert(cliquevars != NULL || ncliquevars == 0);
2880 	      assert(cliquevals != NULL || ncliquevars == 0);
2881 	
2882 	      /* add arcs for all fractional variables in clique */
2883 	      for( m = 0; m < ncliquevars; ++m )
2884 	      {
2885 	         int tmp;
2886 	
2887 	         assert( cliquevars != NULL && cliquevals != NULL ); /* for lint */
2888 	         neighbor = cliquevars[m];
2889 	
2890 	         neighindex = sepadata->mapping[SCIPvarGetProbindex(neighbor)];
2891 	         assert(neighindex < nbinvars);
2892 	
2893 	         /* ignore current variable */
2894 	         if( neighindex == varsidx )
2895 	            continue;
2896 	
2897 	         /* we use only variables with fractional LP-solution values */
2898 	         if( SCIPisFeasIntegral(scip, vals[neighindex]) )
2899 	            continue;
2900 	
2901 	         /* forward direction (the backward is created at the occurrence of the current variable in the cliquevars of the neighbor) */
2902 	         /* x==1 */
2903 	         if( original )
2904 	         {
2905 	            /* implication to y=0 (I->III) */
2906 	            if( cliquevals[m] )
2907 	            {
2908 	               tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - vals[neighindex] ));
2909 	               graph->weight[*narcs] = (unsigned int) MAX(0, tmp);
2910 	               graph->head[*narcs] = neighindex + 2 * nbinvars;
2911 	            }
2912 	            /* implication to y=1 (I->IV) (cliquevals[m] == FALSE) */
2913 	            else
2914 	            {
2915 	               tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - vals[varsidx] - (1 - vals[neighindex]) ));
2916 	               graph->weight[*narcs] = (unsigned int) MAX(0, tmp);
2917 	               graph->head[*narcs] = neighindex + 3 * nbinvars;
2918 	            }
2919 	         }
2920 	         /* x==0 */
2921 	         else
2922 	         {
2923 	            /* implication to y=0 (II->III) */
2924 	            if( cliquevals[m] )
2925 	            {
2926 	               tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - (1 - vals[varsidx]) - vals[neighindex] ));
2927 	               graph->weight[*narcs] = (unsigned int) MAX(0, tmp);
2928 	               graph->head[*narcs] = neighindex + 2 * nbinvars;
2929 	            }
2930 	            /* implication to y=1 (II->IV) (cliquevals[m] == FALSE) */
2931 	            else
2932 	            {
2933 	               tmp = (int) SCIPfeasCeil(scip, sepadata->scale * (1 - (1 - vals[varsidx]) - (1-vals[neighindex]) )) ;
2934 	               graph->weight[*narcs] = (unsigned int) MAX(0, tmp);
2935 	               graph->head[*narcs] = neighindex + 3 * nbinvars;
2936 	            }
2937 	         }
2938 	
2939 	         /* update minimum and maximum weight values */
2940 	         if( graph->weight[*narcs] < graph->minweight )
2941 	            graph->minweight = graph->weight[*narcs];
2942 	
2943 	         if( graph->weight[*narcs] > graph->maxweight )
2944 	            graph->maxweight = graph->weight[*narcs];
2945 	
2946 	         ++(*narcs);
2947 	         if( *arraysize == *narcs )
2948 	         {
2949 	            SCIP_CALL( checkArraySizesGLS(scip, maxarcs, arraysize, graph, success) );
2950 	
2951 	            if( !(*success) )
2952 	               return SCIP_OKAY;
2953 	         }
2954 	         assert((*narcs) < maxarcs);
2955 	         ++(graph->outcnt[dijkindex]);
2956 	
2957 	         *emptygraph = FALSE;
2958 	      }
2959 	   }
2960 	
2961 	   return SCIP_OKAY;
2962 	}
2963 	
2964 	/** The classical method for finding odd cycles by Groetschel, Lovasz, Schrijver uses a bipartite graph
2965 	 *  which contains in each partition a node for every node in the original graph.
2966 	 *  All arcs uv of the original graph are copied to arcs from u of the first partition to v' of the second partition
2967 	 *  and from u' of the second partition to v of the first partition.
2968 	 *  A Dijkstra algorithm is used to find a path from a node x to its copy x', if existing.
2969 	 *  The nodes in the original graph corresponding to the nodes on the path form an odd cycle.
2970 	 *
2971 	 *  Since SCIP stores implications between original and negated variables,
2972 	 *  our original graph has at most twice the number of binary variables of the problem.
2973 	 *  By creating the bipartite graph we gain 4 segments of the graph:
2974 	 *
2975 	 *  I   - nodes of the original variables in the first bipartition \n
2976 	 *  II  - nodes of the negated variables in the first bipartition \n
2977 	 *  III - nodes of the original variables in the second bipartition \n
2978 	 *  IV  - nodes of the negated variables in the second bipartition
2979 	 *
2980 	 *  The length of every segment if the number of binary variables in the original problem.
2981 	 *
2982 	 *  Since the implication graph of SCIP is (normally) incomplete,
2983 	 *  it is possible to use arcs between an original variable and its negated
2984 	 *  to obtain more cycles which are valid but not found due to missing links.
2985 	 */
2986 	static
2987 	SCIP_RETCODE separateGLS(
2988 	   SCIP*                 scip,               /**< SCIP data structure */
2989 	   SCIP_SEPA*            sepa,               /**< separator */
2990 	   SCIP_SEPADATA*        sepadata,           /**< separator data structure */
2991 	   SCIP_SOL*             sol,                /**< given primal solution */
2992 	   SCIP_RESULT*          result              /**< pointer to store the result of the separation call */
2993 	   )
2994 	{
2995 	   SCIP_Bool emptygraph;                     /* flag if graph contains an arc */
2996 	
2997 	   SCIP_Real* vals;                          /* values of the variables in the given solution */
2998 	   unsigned int* incut;
2999 	
3000 	   unsigned int i;
3001 	   unsigned int j;
3002 	
3003 	   SCIP_VAR** scipvars;                      /* variables of the current SCIP (unsorted) */
3004 	   SCIP_VAR** vars;                          /* variables of the current SCIP (sorted if requested) */
3005 	   unsigned int nbinvars;                    /* number of binary problem variables */
3006 	   SCIP_Bool original;                       /* flag if the current variable is original or negated */
3007 	
3008 	   unsigned int ncliques;                    /* number of cliques of the current variable */
3009 	
3010 	   DIJKSTRA_GRAPH graph;                     /* Dijkstra graph data structure */
3011 	   unsigned int arraysize;                   /* current size of graph->head and graph->weight */
3012 	   unsigned int narcs;                       /* number of arcs in the Dijkstra graph */
3013 	   unsigned int maxarcs;                     /* maximum number of arcs in the Dijkstra graph */
3014 	   unsigned int maxstarts;                   /* maximum number of start nodes */
3015 	   unsigned int startcounter;                /* counter of tried start nodes */
3016 	   unsigned long long cutoff;                /* cutoff value for Dijkstra algorithm */
3017 	
3018 	   unsigned int startnode;                   /* start node for Dijkstra algorithm */
3019 	   unsigned int endnode;                     /* target node for Dijkstra algorithm */
3020 	   unsigned long long* dist;                 /* distance matrix for Dijkstra algorithm */
3021 	   unsigned int* pred;                       /* predecessor list for found cycle */
3022 	   unsigned int* entry;                      /* storage for Dijkstra algorithm */
3023 	   unsigned int* order;                      /* storage for Dijkstra algorithm */
3024 	   unsigned int dijkindex;
3025 	   SCIP_Bool success;                        /* flag for check for several errors */
3026 	
3027 	   SCIP_Bool* incycle;                       /* flag array if variable is contained in the found cycle */
3028 	   unsigned int* pred2;                      /* temporary predecessor list for backprojection of found cycle */
3029 	
3030 	   int nscipbinvars;
3031 	   int nscipintvars;
3032 	   int nscipimplvars;
3033 	   int nintegral;
3034 	   int k;
3035 	
3036 	   assert(scip != NULL);
3037 	   assert(sepadata != NULL);
3038 	   assert(result != NULL);
3039 	
3040 	   success = TRUE;
3041 	   emptygraph = TRUE;
3042 	
3043 	   SCIP_CALL( SCIPgetVarsData(scip, &scipvars, NULL, &nscipbinvars, &nscipintvars, &nscipimplvars, NULL) );
3044 	   assert(nscipbinvars >= 0);
3045 	   assert(nscipintvars >= 0);
3046 	   assert(nscipimplvars >= 0);
3047 	
3048 	   nintegral = nscipbinvars + nscipintvars + nscipimplvars;
3049 	   assert(scipvars != NULL || ((nscipbinvars == 0) && (nscipintvars == 0) && (nscipimplvars == 0) && (nintegral == 0)));
3050 	
3051 	   /* collect binary variables, including implicit binary */
3052 	   SCIP_CALL( SCIPallocBufferArray(scip, &vars, nintegral) );
3053 	   for (k = 0; k < nscipbinvars; ++k)
3054 	      vars[k] = scipvars[k]; /*lint !e613*/
3055 	
3056 	   nbinvars = (unsigned int) nscipbinvars;
3057 	   for (k = nscipbinvars; k < nintegral; ++k)
3058 	   {
3059 	      assert( SCIPvarGetType(scipvars[k]) != SCIP_VARTYPE_CONTINUOUS ); /*lint !e613*/
3060 	      if ( SCIPvarIsBinary(scipvars[k]) ) /*lint !e613*/
3061 	         vars[nbinvars++] = scipvars[k]; /*lint !e613*/
3062 	   }
3063 	
3064 	   if( nbinvars == 0 )
3065 	   {
3066 	      SCIPfreeBufferArray(scip, &vars);
3067 	      return SCIP_OKAY;
3068 	   }
3069 	
3070 	   /* initialize flag array to avoid multiple cuts per variable, if requested by user-flag */
3071 	   SCIP_CALL( SCIPallocBufferArray(scip, &vals, (int) (2 * nbinvars)) );
3072 	
3073 	   /* prepare values */
3074 	   assert( vars != NULL );
3075 	   switch( sepadata->sortswitch )
3076 	   {
3077 	   case UNSORTED :
3078 	      /* if no sorting is requested, we use the normal variable array */
3079 	      break;
3080 	
3081 	   case MAXIMAL_LPVALUE :
3082 	      /* store lp-values */
3083 	      for( i = 0; i < nbinvars; ++i )
3084 	         vals[i] = SCIPgetSolVal(scip, sol, vars[i]);
3085 	
3086 	      /* sort by lp-value, maximal first */
3087 	      SCIPsortDownRealPtr(vals, (void**)vars, (int) nbinvars);
3088 	      break;
3089 	
3090 	   case MINIMAL_LPVALUE :
3091 	      /* store lp-values */
3092 	      for( i = 0; i < nbinvars; ++i )
3093 	         vals[i] = SCIPgetSolVal(scip, sol, vars[i]);
3094 	
3095 	      /* sort by lp-value, minimal first */
3096 	      SCIPsortRealPtr(vals, (void**)vars, (int) nbinvars);
3097 	      break;
3098 	
3099 	   case MAXIMAL_FRACTIONALITY  :
3100 	      /* store lp-values and determine fractionality */
3101 	      for( i = 0; i < nbinvars; ++i )
3102 	      {
3103 	         vals[i] = SCIPgetSolVal(scip, sol, vars[i]);
3104 	         vals[i] = MIN(1.0 - vals[i], vals[i]);
3105 	      }
3106 	
3107 	      /* sort by fractionality, maximal first */
3108 	      SCIPsortDownRealPtr(vals, (void**)vars, (int) nbinvars);
3109 	      break;
3110 	
3111 	   case MINIMAL_FRACTIONALITY :
3112 	      /* store lp-values and determine fractionality */
3113 	      for( i = 0; i < nbinvars; ++i )
3114 	      {
3115 	         vals[i] = SCIPgetSolVal(scip, sol, vars[i]);
3116 	         vals[i] = MIN(1.0 - vals[i], vals[i]);
3117 	      }
3118 	
3119 	      /* sort by fractionality, minimal first */
3120 	      SCIPsortRealPtr(vals, (void**)vars, (int) nbinvars);
3121 	      break;
3122 	
3123 	   default :
3124 	      SCIPerrorMessage("invalid sortswitch value\n");
3125 	      SCIPABORT();
3126 	      return SCIP_INVALIDDATA;  /*lint !e527*/
3127 	   }
3128 	   assert(vars != NULL);
3129 	
3130 	   /* create mapping for getting the index of a variable via its probindex to the index in the sorted variable array */
3131 	   SCIP_CALL( SCIPallocBufferArray(scip, &(sepadata->mapping), nintegral) );
3132 	   SCIP_CALL( SCIPallocBufferArray(scip, &incut, (int) (4 * nbinvars)) );
3133 	   BMSclearMemoryArray(incut, 4 * nbinvars);
3134 	
3135 	   /* initialize LP value and cut flag for all variables */
3136 	   for( i = 0; i < nbinvars; ++i )
3137 	   {
3138 	      assert( 0 <= SCIPvarGetProbindex(vars[i]) && SCIPvarGetProbindex(vars[i]) < nintegral);  /* since binary, integer, and implicit variables are first */
3139 	      sepadata->mapping[SCIPvarGetProbindex(vars[i])] = i;
3140 	      vals[i] = SCIPgetSolVal(scip, sol, vars[i]); /* need to get new values, since they might be corrupted */
3141 	   }
3142 	
3143 	   for( i = nbinvars; i < 2*nbinvars; ++i )
3144 	      vals[i] = 1 - vals[i - nbinvars];
3145 	
3146 	   /* initialize number of nodes in  Dijkstra graph (2*2*n nodes in a mirrored bipartite graph with negated variables) */
3147 	   graph.nodes = 4 * nbinvars;
3148 	
3149 	   /* Initialize number of arcs in Dijkstra graph, should be (nbinvars+1) * graph.nodes, but might deviate, because
3150 	    * there might be parallel arcs:
3151 	    * nbinvars-1 possible arcs per node (it is not possible to be linked to variable and negated)
3152 	    * + 1 self-arc (arc to negated variable)
3153 	    * + 1 dummy arc for Dijkstra data structure
3154 	    * = nbinvars+1 arcs per node
3155 	    * * graph.nodes
3156 	    * = (nbinvars+1)*graph.nodes
3157 	    * + graph.nodes => separating entries for arclist)
3158 	    *
3159 	    * Number is corrected below.
3160 	    */
3161 	   graph.arcs = 0;
3162 	
3163 	   /* the implication graph is redundant and therefore more implications and clique arcs may occur than should be possible
3164 	    * @todo later: filtering of edges which were already added,  maxarcs should be graph.arcs rather than INT_MAX;
3165 	    */
3166 	   maxarcs = UINT_MAX;
3167 	
3168 	   /* allocate memory for Dijkstra graph arrays */
3169 	   arraysize = 100 * graph.nodes;
3170 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.outbeg, (int) graph.nodes) );
3171 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.outcnt, (int) graph.nodes) );
3172 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.head, (int) MIN(maxarcs, arraysize)) );
3173 	   SCIP_CALL( SCIPallocBufferArray(scip, &graph.weight, (int) MIN(maxarcs, arraysize)) );
3174 	   SCIP_CALL( SCIPallocBufferArray(scip, &dist, (int) graph.nodes) );
3175 	   SCIP_CALL( SCIPallocBufferArray(scip, &pred, (int) graph.nodes) );
3176 	   SCIP_CALL( SCIPallocBufferArray(scip, &entry, (int) graph.nodes) );
3177 	   SCIP_CALL( SCIPallocBufferArray(scip, &order, (int) graph.nodes) );
3178 	
3179 	   /* initialize Dijkstra graph as empty graph */
3180 	   for( i = 0; i < MIN(arraysize, maxarcs); ++i )
3181 	   {
3182 	      graph.head[i] = DIJKSTRA_UNUSED;
3183 	      graph.weight[i] = DIJKSTRA_UNUSED;
3184 	   }
3185 	   graph.minweight = DIJKSTRA_FARAWAY;
3186 	   graph.maxweight = 0;
3187 	   narcs = 0;
3188 	
3189 	#ifndef NDEBUG
3190 	   for( i = 0; i < graph.nodes; ++i )
3191 	   {
3192 	      graph.outbeg[i] = 0;
3193 	      graph.outcnt[i] = 0;
3194 	   }
3195 	#endif
3196 	
3197 	   /* add arcs from first to second partition to Dijkstra graph (based on the original fractional implication graph) */
3198 	   for( dijkindex = 0; dijkindex < 2 * nbinvars; ++dijkindex )
3199 	   {
3200 	      graph.outbeg[dijkindex] = narcs;
3201 	      graph.outcnt[dijkindex] = 0;
3202 	
3203 	      /* decide if we have original or negated variable */
3204 	      if( dijkindex < nbinvars )
3205 	      {
3206 	         i = dijkindex;
3207 	         original = TRUE;
3208 	      }
3209 	      else
3210 	      {
3211 	         i = dijkindex - nbinvars;
3212 	         original = FALSE;
3213 	      }
3214 	      assert(i < nbinvars);
3215 	
3216 	      /* if the variable has a fractional value we add it to the graph */
3217 	      if( ! SCIPisFeasIntegral(scip, vals[i]) )
3218 	      {
3219 	         ncliques =  (unsigned int) SCIPvarGetNCliques(vars[i], original);
3220 	
3221 	         /* insert arcs for cliques (take var => getCliques => take cliquevar => add forward-arc) */
3222 	         /* add clique arcs of clique-type "original" if current variable has them */
3223 	         if( ncliques >= 1 )
3224 	         {
3225 	            /* x==1/0 -> y==0/1 (I/II -> III/IV) */
3226 	            SCIP_CALL( addGLSCliques(scip, sepadata, vars, i, dijkindex, vals, nbinvars, ncliques, &graph,
3227 	                  &narcs, maxarcs, original, &emptygraph, &arraysize, &success) );
3228 	
3229 	            if( !success )
3230 	               goto TERMINATE;
3231 	         }
3232 	      }
3233 	
3234 	      /* add link to copy of negated variable (useful if/because the implication graph is incomplete) */
3235 	      if( sepadata->addselfarcs && graph.outcnt[dijkindex] > 0 )
3236 	      {
3237 	         /* I -> IV */
3238 	         if( original )
3239 	         {
3240 	            assert(dijkindex < nbinvars);
3241 	            graph.head[narcs] = dijkindex + 3*nbinvars;
3242 	         }
3243 	         /* II -> III */
3244 	         else
3245 	         {
3246 	            assert(dijkindex >= nbinvars && dijkindex < 2*nbinvars);
3247 	            graph.head[narcs] = dijkindex + nbinvars;
3248 	         }
3249 	         graph.weight[narcs] = 0;
3250 	
3251 	         /* update minimum and maximum weight values */
3252 	         if( graph.weight[narcs] < graph.minweight )
3253 	            graph.minweight = graph.weight[narcs];
3254 	
3255 	         if( graph.weight[narcs] > graph.maxweight )
3256 	            graph.maxweight = graph.weight[narcs];
3257 	
3258 	         ++narcs;
3259 	         if( arraysize == narcs )
3260 	         {
3261 	            SCIP_CALL( checkArraySizesGLS(scip, maxarcs, &arraysize, &graph, &success) );
3262 	            if( !success )
3263 	               goto TERMINATE;
3264 	         }
3265 	         assert(narcs < maxarcs);
3266 	         ++(graph.outcnt[dijkindex]);
3267 	      }
3268 	
3269 	      /* add separating arc */
3270 	      graph.head[narcs] = DIJKSTRA_UNUSED;
3271 	      graph.weight[narcs] = DIJKSTRA_UNUSED;
3272 	      ++narcs;
3273 	      if( arraysize == narcs )
3274 	      {
3275 	         SCIP_CALL( checkArraySizesGLS(scip, maxarcs, &arraysize, &graph, &success) );
3276 	         if( !success )
3277 	            goto TERMINATE;
3278 	      }
3279 	      assert(narcs < maxarcs);
3280 	   }
3281 	
3282 	   /* if the graph is empty, there is nothing to do */
3283 	   if( emptygraph )
3284 	      goto TERMINATE;
3285 	
3286 	   /* add arcs from second to first partition to Dijkstra graph */
3287 	   for( i = 0; i < 2*nbinvars; ++i )
3288 	   {
3289 	      graph.outbeg[2 * nbinvars + i] = narcs;
3290 	      graph.outcnt[2 * nbinvars + i] = 0;
3291 	
3292 	      /* copy all arcs to head from the second to the first bipartition */
3293 	      for( j = graph.outbeg[i]; j < graph.outbeg[i] + graph.outcnt[i]; ++j )
3294 	      {
3295 	         /* there are only arcs from first bipartition to the second */
3296 	         assert(graph.head[j] >= 2*nbinvars && graph.head[j] < 4*nbinvars);
3297 	
3298 	         /* the backward arcs head from III->I or IV->II */
3299 	         graph.head[narcs] = graph.head[j] - 2 * nbinvars;
3300 	         graph.weight[narcs] = graph.weight[j];
3301 	         ++narcs;
3302 	         if( arraysize == narcs )
3303 	         {
3304 	            SCIP_CALL( checkArraySizesGLS(scip, maxarcs, &arraysize, &graph, &success) );
3305 	
3306 	            if( !success )
3307 	               goto TERMINATE;
3308 	         }
3309 	         assert(narcs < maxarcs);
3310 	         ++(graph.outcnt[2*nbinvars+i]);
3311 	      }
3312 	
3313 	      /* add separating arc */
3314 	      graph.head[narcs] = DIJKSTRA_UNUSED;
3315 	      graph.weight[narcs] = DIJKSTRA_UNUSED;
3316 	      ++narcs;
3317 	
3318 	      if( arraysize == narcs )
3319 	      {
3320 	         SCIP_CALL( checkArraySizesGLS(scip, maxarcs, &arraysize, &graph, &success) );
3321 	
3322 	         if( !success )
3323 	            goto TERMINATE;
3324 	      }
3325 	      assert(narcs < maxarcs);
3326 	   }
3327 	
3328 	   /* correct number of arcs */
3329 	   graph.arcs = narcs;
3330 	
3331 	   SCIPdebugMsg(scip, "--- graph successfully created (%u nodes, %u arcs) ---\n", graph.nodes, narcs);
3332 	
3333 	   /* graph is now prepared for Dijkstra methods */
3334 	   assert( dijkstraGraphIsValid(&graph) );
3335 	
3336 	#ifdef SCIP_ODDCYCLE_WRITEGRAPH
3337 	   {
3338 	      char probname [SCIP_MAXSTRLEN];
3339 	      char filename [SCIP_MAXSTRLEN];
3340 	      char* name;
3341 	
3342 	      (void)  SCIPsnprintf(probname, SCIP_MAXSTRLEN, "%s", SCIPgetProbName(scip));
3343 	      SCIPsplitFilename(probname, NULL, &name, NULL, NULL);
3344 	      (void)  SCIPsnprintf(filename, SCIP_MAXSTRLEN, "%s_%d.gml", name, SCIPgetNLPs(scip));
3345 	      SCIP_CALL( SCIPwriteCliqueGraph(scip, filename, TRUE, TRUE) );
3346 	      SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Wrote clique/implication graph to <%s>.\n", filename);
3347 	   }
3348 	#endif
3349 	
3350 	   /* determine the number of start nodes */
3351 	   maxstarts = (unsigned int) SCIPceil(scip, sepadata->offsettestvars + (0.02 * nbinvars * sepadata->percenttestvars));
3352 	   startcounter = 0;
3353 	
3354 	   /* allocate and initialize predecessor list and flag array representing odd cycle */
3355 	   SCIP_CALL( SCIPallocBufferArray(scip, &pred2, (int) (2 * nbinvars)) );
3356 	   SCIP_CALL( SCIPallocBufferArray(scip, &incycle, (int) (2 * nbinvars)) );
3357 	
3358 	   /* separate odd cycle inequalities by GLS method */
3359 	   cutoff = (unsigned long long) (0.5 * sepadata->scale);
3360 	   for( i = (unsigned int) sepadata->lastroot; i < 2 * nbinvars
3361 	           && startcounter < maxstarts
3362 	           && sepadata->ncuts - sepadata->oldncuts < (unsigned int) sepadata->maxsepacutsround
3363 	           && !SCIPisStopped(scip); ++i )
3364 	   {
3365 	      unsigned int ncyclevars;               /* cycle length */
3366 	      SCIP_Bool edgedirection;               /* partitionindicator for backprojection from bipartite graph to original graph:
3367 	                                              * is the current edge a backwards edge, i.e., from second to first partition? */
3368 	
3369 	      /* skip isolated node */
3370 	      if( graph.head[graph.outbeg[i]] == DIJKSTRA_UNUSED )
3371 	         continue;
3372 	
3373 	      /* if node has only one arc, there is no odd cycle containing this node
3374 	       * (but there are invalid odd circuits containing the only neighbor twice)
3375 	       */
3376 	      if( graph.head[graph.outbeg[i]+1] == DIJKSTRA_UNUSED )
3377 	         continue;
3378 	
3379 	      /* search shortest path from node to its counter part in the other partition */
3380 	      startnode = i;
3381 	      endnode = i + 2 * nbinvars;
3382 	
3383 	      /* skip node if it is already covered by a cut and
3384 	       * we do not want to search cycles starting with a node already covered by a cut
3385 	       */
3386 	      if( incut[startnode] && ! sepadata->multiplecuts )
3387 	         continue;
3388 	
3389 	      ++startcounter;
3390 	
3391 	      if ( sepadata->allowmultiplecuts )
3392 	         (void) dijkstraPairCutoffIgnore(&graph, startnode, endnode, incut, cutoff, dist, pred, entry, order);
3393 	      else
3394 	         (void) dijkstraPairCutoff(&graph, startnode, endnode, cutoff, dist, pred, entry, order);
3395 	
3396 	      /* no odd cycle cut found */
3397 	      if( dist[endnode] == DIJKSTRA_FARAWAY )
3398 	         continue;
3399 	
3400 	      /* skip check if cutoff has been exceeded */
3401 	      if ( dist[endnode] >= cutoff )
3402 	         continue;
3403 	
3404 	      /* detect cycle including:
3405 	       * project bipartitioned graph to original graph of variables and their negated
3406 	       * (pred&incycle-structure for generateOddCycleCut)
3407 	       * check cycles for double variables and try to clean variable-negated-sub-cycles if existing
3408 	       */
3409 	      for( j = 0; j < 2 * nbinvars; ++j )
3410 	      {
3411 	         pred2[j] = DIJKSTRA_UNUSED;
3412 	         incycle[j] = FALSE;
3413 	      }
3414 	
3415 	      ncyclevars = 0;
3416 	      edgedirection = TRUE;
3417 	      success = TRUE;
3418 	
3419 	      /* construct odd cycle in implication graph from shortest path on bipartite graph */
3420 	      for( dijkindex = endnode; dijkindex != startnode && success; dijkindex = pred[dijkindex], edgedirection = !edgedirection )
3421 	      {
3422 	         if( edgedirection )
3423 	         {
3424 	            /* check that current node is in second partition and next node is in first partition */
3425 	            assert(dijkindex >= 2 * nbinvars && dijkindex < 4 * nbinvars);
3426 	            assert(pred[dijkindex] < 2*nbinvars);
3427 	
3428 	            pred2[dijkindex - 2 * nbinvars] = pred[dijkindex];
3429 	
3430 	            /* check whether the object found is really a cycle without sub-cycles
3431 	             * (sub-cycles may occur in case there is not violated odd cycle inequality)
3432 	             * and remove pairs of original and negated variable from cycle
3433 	             */
3434 	            SCIP_CALL( cleanCycle(scip, pred2, incycle, incut, dijkindex-2*nbinvars, endnode-2*nbinvars, nbinvars,
3435 	                  &ncyclevars, sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
3436 	         }
3437 	         else
3438 	         {
3439 	            /* check that current node is in first partition and next node is in second partition */
3440 	            assert(dijkindex < 2 * nbinvars);
3441 	            assert(pred[dijkindex] >= 2 * nbinvars && pred[dijkindex] < 4 * nbinvars);
3442 	
3443 	            pred2[dijkindex] = pred[dijkindex] - 2 * nbinvars;
3444 	
3445 	            /* check whether the object found is really a cycle without sub-cycles
3446 	             * (sub-cycles may occur in case there is not violated odd cycle inequality)
3447 	             * and remove pairs of original and negated variable from cycle
3448 	             */
3449 	            SCIP_CALL( cleanCycle(scip, pred2, incycle, incut, dijkindex, endnode-2*nbinvars, nbinvars, &ncyclevars,
3450 	                  sepadata->repaircycles, sepadata->allowmultiplecuts, &success) );
3451 	         }
3452 	      }
3453 	
3454 	      if( success )
3455 	      {
3456 	         GRAPHDATA graphdata;
3457 	
3458 	         /* generate cut */
3459 	         graphdata.usegls = TRUE;
3460 	         graphdata.dijkstragraph = &graph;
3461 	         graphdata.levelgraph = NULL;
3462 	
3463 	         SCIP_CALL( generateOddCycleCut(scip, sepa, sol, vars, nbinvars, startnode, pred2, ncyclevars, incut, vals, sepadata, &graphdata, result) );
3464 	      }
3465 	   }
3466 	
3467 	   /* free temporary memory */
3468 	   SCIPfreeBufferArray(scip, &incycle);
3469 	   SCIPfreeBufferArray(scip, &pred2);
3470 	
3471 	   /* store the last tried root (when running without sorting the variable array, we don't want
3472 	    * to always check the same variables and therefore start next time where we stopped last time)
3473 	    */
3474 	   if( sepadata->sortswitch == UNSORTED )
3475 	   {
3476 	      if( i == 2 * nbinvars )
3477 	         sepadata->lastroot = 0;
3478 	      else
3479 	         sepadata->lastroot = (int) i;
3480 	   }
3481 	
3482 	 TERMINATE:
3483 	   /* free temporary memory */
3484 	   SCIPfreeBufferArray(scip, &order);
3485 	   SCIPfreeBufferArray(scip, &entry);
3486 	   SCIPfreeBufferArray(scip, &pred);
3487 	   SCIPfreeBufferArray(scip, &dist);
3488 	   SCIPfreeBufferArray(scip, &graph.weight);
3489 	   SCIPfreeBufferArray(scip, &graph.head);
3490 	   SCIPfreeBufferArray(scip, &graph.outcnt);
3491 	   SCIPfreeBufferArray(scip, &graph.outbeg);
3492 	   SCIPfreeBufferArray(scip, &incut);
3493 	   SCIPfreeBufferArray(scip, &(sepadata->mapping));
3494 	   SCIPfreeBufferArray(scip, &vals);
3495 	   SCIPfreeBufferArray(scip, &vars);
3496 	
3497 	   return SCIP_OKAY;
3498 	}
3499 	
3500 	
3501 	/** separation method */
3502 	static
3503 	SCIP_RETCODE separateOddCycles(
3504 	   SCIP*                 scip,               /**< SCIP data structure */
3505 	   SCIP_SEPA*            sepa,               /**< separator */
3506 	   SCIP_SOL*             sol,                /**< given primal solution */
3507 	   int                   depth,              /**< current depth */
3508 	   SCIP_RESULT*          result              /**< pointer to store the result of the separation call */
3509 	   )
3510 	{
3511 	   SCIP_SEPADATA* sepadata;
3512 	   int ncalls;
3513 	   SCIPdebug( int oldnliftedcuts; )
3514 	   int nfrac = 0;
3515 	
3516 	   *result = SCIP_DIDNOTRUN;
3517 	
3518 	   /* get separator data */
3519 	   sepadata = SCIPsepaGetData(sepa);
3520 	   assert(sepadata != NULL);
3521 	
3522 	   ncalls = SCIPsepaGetNCallsAtNode(sepa);
3523 	
3524 	   /* only call separator a given number of rounds at each b&b node */
3525 	   if( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
3526 	      || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
3527 	      return SCIP_OKAY;
3528 	
3529 	   /* only call separator if enough binary variables are present */
3530 	   if( SCIPgetNBinVars(scip) < 3 || (! sepadata->includetriangles && SCIPgetNBinVars(scip) < 5) )
3531 	   {
3532 	      SCIPdebugMsg(scip, "skipping separator: not enough binary variables\n");
3533 	      return SCIP_OKAY;
3534 	   }
3535 	
3536 	   /* only call separator if enough fractional variables are present */
3537 	   if ( sol != NULL )
3538 	   {
3539 	      SCIP_VAR** vars;
3540 	      SCIP_Real solval;
3541 	      int nvars;
3542 	      int v;
3543 	
3544 	      SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
3545 	
3546 	      /* first compute fractional variables */
3547 	      for( v = 0; v < nvars; ++v )
3548 	      {
3549 	         solval = SCIPgetSolVal(scip, sol, vars[v]);
3550 	
3551 	         if ( ! SCIPisFeasIntegral(scip, solval) )
3552 	            ++nfrac;
3553 	      }
3554 	   }
3555 	   else
3556 	      nfrac = SCIPgetNLPBranchCands(scip);
3557 	
3558 	   if( nfrac < 3 || (! sepadata->includetriangles && nfrac < 5) )
3559 	   {
3560 	      SCIPdebugMsg(scip, "skipping separator: not enough fractional variables\n");
3561 	      return SCIP_OKAY;
3562 	   }
3563 	
3564 	   /* only call separator if enough implications and cliques are present */
3565 	   if( SCIPgetNImplications(scip) + SCIPgetNCliques(scip) < 3 )
3566 	   {
3567 	      SCIPdebugMsg(scip, "skipping separator: not enough implications present\n");
3568 	      return SCIP_OKAY;
3569 	   }
3570 	
3571 	   /* only run if number of cuts already found is small enough */
3572 	   if ( sepadata->cutthreshold >= 0 && SCIPgetNCutsFoundRound(scip) >= sepadata->cutthreshold )
3573 	      return SCIP_OKAY;
3574 	
3575 	   /* store node number and reset number of unsuccessful calls */
3576 	   if ( sepadata->lastnode != SCIPnodeGetNumber(SCIPgetCurrentNode(scip)) )
3577 	   {
3578 	      sepadata->nunsucessfull = 0;
3579 	      sepadata->lastnode = SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
3580 	   }
3581 	   else
3582 	   {
3583 	      if ( sepadata->nunsucessfull > sepadata->maxunsucessfull )
3584 	      {
3585 	         SCIPdebugMsg(scip, "skipping separator: number of unsucessfull calls = %d.\n", sepadata->nunsucessfull);
3586 	         return SCIP_OKAY;
3587 	      }
3588 	   }
3589 	
3590 	   *result = SCIP_DIDNOTFIND;
3591 	   sepadata->oldncuts = sepadata->ncuts;
3592 	   SCIPdebug( oldnliftedcuts = sepadata->nliftedcuts; )
3593 	
3594 	   if( depth == 0 )
3595 	      sepadata->maxsepacutsround = sepadata->maxsepacutsroot;
3596 	   else
3597 	      sepadata->maxsepacutsround = sepadata->maxsepacuts;
3598 	
3599 	   /* perform the actual separation routines */
3600 	   if( sepadata->usegls )
3601 	   {
3602 	      SCIPdebugMsg(scip, "using GLS method for finding odd cycles\n");
3603 	      SCIP_CALL( separateGLS(scip, sepa, sepadata, sol, result) );
3604 	   }
3605 	   else
3606 	   {
3607 	      SCIPdebugMsg(scip, "using level graph heuristic for finding odd cycles\n");
3608 	      SCIP_CALL( separateHeur(scip, sepa, sepadata, sol, result) );
3609 	   }
3610 	
3611 	   if( sepadata->ncuts - sepadata->oldncuts > 0 )
3612 	   {
3613 	      SCIPdebug( SCIPdebugMsg(scip, "added %u cuts (%d allowed), %d lifted.\n", sepadata->ncuts - sepadata->oldncuts,
3614 	         sepadata->maxsepacutsround, sepadata->nliftedcuts - oldnliftedcuts); )
3615 	      sepadata->nunsucessfull = 0;
3616 	   }
3617 	   else
3618 	   {
3619 	      SCIPdebugMsg(scip, "no cuts added (%d allowed)\n", sepadata->maxsepacutsround);
3620 	      ++sepadata->nunsucessfull;
3621 	   }
3622 	   SCIPdebugMsg(scip, "total sepatime: %.2f - total number of added cuts: %u\n", SCIPsepaGetTime(sepa), sepadata->ncuts);
3623 	
3624 	   return SCIP_OKAY;
3625 	}
3626 	
3627 	
3628 	/*
3629 	 * Callback methods of separator
3630 	 */
3631 	
3632 	/** copy method for separator plugins (called when SCIP copies plugins) */
3633 	static
3634 	SCIP_DECL_SEPACOPY(sepaCopyOddcycle)
3635 	{  /*lint --e{715}*/
3636 	   assert(scip != NULL);
3637 	   assert(sepa != NULL);
3638 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3639 	
3640 	   /* call inclusion method of constraint handler */
3641 	   SCIP_CALL( SCIPincludeSepaOddcycle(scip) );
3642 	
3643 	   return SCIP_OKAY;
3644 	}
3645 	
3646 	
3647 	/** destructor of separator to free user data (called when SCIP is exiting) */
3648 	static
3649 	SCIP_DECL_SEPAFREE(sepaFreeOddcycle)
3650 	{
3651 	   SCIP_SEPADATA* sepadata;
3652 	
3653 	   sepadata = SCIPsepaGetData(sepa);
3654 	   assert(sepadata != NULL);
3655 	
3656 	   SCIPfreeBlockMemory(scip, &sepadata);
3657 	   SCIPsepaSetData(sepa, NULL);
3658 	
3659 	   return SCIP_OKAY;
3660 	}
3661 	
3662 	
3663 	/** initialization method of separator (called after problem was transformed) */
3664 	static
3665 	SCIP_DECL_SEPAINIT(sepaInitOddcycle)
3666 	{
3667 	   SCIP_SEPADATA* sepadata;
3668 	
3669 	   sepadata = SCIPsepaGetData(sepa);
3670 	   assert(sepadata != NULL);
3671 	
3672 	   sepadata->ncuts = 0;
3673 	   sepadata->oldncuts = 0;
3674 	   sepadata->nliftedcuts = 0;
3675 	   sepadata->lastroot = 0;
3676 	
3677 	   return SCIP_OKAY;
3678 	}
3679 	
3680 	
3681 	/** solving process initialization method of separator (called when branch and bound process is about to begin) */
3682 	static
3683 	SCIP_DECL_SEPAINITSOL(sepaInitsolOddcycle)
3684 	{
3685 	   SCIP_SEPADATA* sepadata;
3686 	
3687 	   assert(sepa != NULL);
3688 	
3689 	   sepadata = SCIPsepaGetData(sepa);
3690 	   assert(sepadata != NULL);
3691 	
3692 	   sepadata->nunsucessfull = 0;
3693 	   sepadata->lastnode = -1;
3694 	
3695 	   return SCIP_OKAY;
3696 	}
3697 	
3698 	
3699 	/** LP solution separation method of separator */
3700 	static
3701 	SCIP_DECL_SEPAEXECLP(sepaExeclpOddcycle)
3702 	{  /*lint --e{715}*/
3703 	   assert(sepa != NULL);
3704 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3705 	   assert(scip != NULL);
3706 	   assert(result != NULL);
3707 	
3708 	   SCIP_CALL( separateOddCycles(scip, sepa, NULL, depth, result) );
3709 	
3710 	   return SCIP_OKAY;
3711 	}
3712 	
3713 	/** arbitrary primal solution separation method of separator */
3714 	static
3715 	SCIP_DECL_SEPAEXECSOL(sepaExecsolOddcycle)
3716 	{  /*lint --e{715}*/
3717 	   assert(sepa != NULL);
3718 	   assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
3719 	   assert(scip != NULL);
3720 	   assert(result != NULL);
3721 	
3722 	   SCIP_CALL( separateOddCycles(scip, sepa, sol, depth, result) );
3723 	
3724 	   return SCIP_OKAY;
3725 	}
3726 	
3727 	
3728 	/*
3729 	 * separator specific interface methods
3730 	 */
3731 	
3732 	/** creates the oddcycle separator and includes it in SCIP */
3733 	SCIP_RETCODE SCIPincludeSepaOddcycle(
3734 	   SCIP*                 scip                /**< SCIP data structure */
3735 	   )
3736 	{
3737 	   SCIP_SEPADATA* sepadata;
3738 	   SCIP_SEPA* sepa;
3739 	
3740 	   /* create oddcycle separator data */
3741 	   SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
3742 	   sepadata->nunsucessfull = 0;
3743 	   sepadata->lastnode = -1;
3744 	
3745 	   /* include separator */
3746 	   SCIP_CALL( SCIPincludeSepaBasic(scip, &sepa, SEPA_NAME, SEPA_DESC, SEPA_PRIORITY, SEPA_FREQ, SEPA_MAXBOUNDDIST,
3747 	         SEPA_USESSUBSCIP, SEPA_DELAY,
3748 	         sepaExeclpOddcycle, sepaExecsolOddcycle,
3749 	         sepadata) );
3750 	
3751 	   assert(sepa != NULL);
3752 	
3753 	   /* set non-NULL pointers to callback methods */
3754 	   SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyOddcycle) );
3755 	   SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeOddcycle) );
3756 	   SCIP_CALL( SCIPsetSepaInit(scip, sepa, sepaInitOddcycle) );
3757 	   SCIP_CALL( SCIPsetSepaInitsol(scip, sepa, sepaInitsolOddcycle) );
3758 	
3759 	   /* add oddcycle separator parameters */
3760 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/usegls",
3761 	         "Should the search method by Groetschel, Lovasz, Schrijver be used? Otherwise use levelgraph method by Hoffman, Padberg.",
3762 	         &sepadata->usegls, FALSE, DEFAULT_USEGLS, NULL, NULL) );
3763 	
3764 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/liftoddcycles",
3765 	         "Should odd cycle cuts be lifted?",
3766 	         &sepadata->liftoddcycles, FALSE, DEFAULT_LIFTODDCYCLES, NULL, NULL) );
3767 	
3768 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxsepacuts",
3769 	         "maximal number of oddcycle cuts separated per separation round",
3770 	         &sepadata->maxsepacuts, FALSE, DEFAULT_MAXSEPACUTS, 0, INT_MAX, NULL, NULL) );
3771 	
3772 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxsepacutsroot",
3773 	         "maximal number of oddcycle cuts separated per separation round in the root node",
3774 	         &sepadata->maxsepacutsroot, FALSE, DEFAULT_MAXSEPACUTSROOT, 0, INT_MAX, NULL, NULL) );
3775 	
3776 	   /* add advanced parameters */
3777 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxrounds",
3778 	         "maximal number of oddcycle separation rounds per node (-1: unlimited)",
3779 	         &sepadata->maxrounds, FALSE, DEFAULT_MAXROUNDS, -1, INT_MAX, NULL, NULL) );
3780 	
3781 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxroundsroot",
3782 	         "maximal number of oddcycle separation rounds in the root node (-1: unlimited)",
3783 	         &sepadata->maxroundsroot, FALSE, DEFAULT_MAXROUNDSROOT, -1, INT_MAX, NULL, NULL) );
3784 	
3785 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/scalingfactor",
3786 	         "factor for scaling of the arc-weights",
3787 	         &sepadata->scale, TRUE, DEFAULT_SCALEFACTOR, 1, INT_MAX, NULL, NULL) );
3788 	
3789 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/addselfarcs",
3790 	         "add links between a variable and its negated",
3791 	         &sepadata->addselfarcs, TRUE, DEFAULT_ADDSELFARCS, NULL, NULL) );
3792 	
3793 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/repaircycles",
3794 	         "try to repair violated cycles with double appearance of a variable",
3795 	         &sepadata->repaircycles, TRUE, DEFAULT_REPAIRCYCLES, NULL, NULL) );
3796 	
3797 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/includetriangles",
3798 	         "separate triangles found as 3-cycles or repaired larger cycles",
3799 	         &sepadata->includetriangles, TRUE, DEFAULT_INCLUDETRIANGLES, NULL, NULL) );
3800 	
3801 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/multiplecuts",
3802 	         "Even if a variable is already covered by a cut, still try it as start node for a cycle search?",
3803 	         &sepadata->multiplecuts, TRUE, DEFAULT_MULTIPLECUTS, NULL, NULL) );
3804 	
3805 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/allowmultiplecuts",
3806 	         "Even if a variable is already covered by a cut, still allow another cut to cover it too?",
3807 	         &sepadata->allowmultiplecuts, TRUE, DEFAULT_ALLOWMULTIPLECUTS, NULL, NULL) );
3808 	
3809 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/lpliftcoef",
3810 	         "Choose lifting candidate by coef*lpvalue or only by coef?",
3811 	         &sepadata->lpliftcoef, TRUE, DEFAULT_LPLIFTCOEF, NULL, NULL) );
3812 	
3813 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/recalcliftcoef",
3814 	         "Calculate lifting coefficient of every candidate in every step (or only if its chosen)?",
3815 	         &sepadata->recalcliftcoef, TRUE, DEFAULT_RECALCLIFTCOEF, NULL, NULL) );
3816 	
3817 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/sortswitch",
3818 	         "use sorted variable array (unsorted(0), maxlp(1), minlp(2), maxfrac(3), minfrac(4))",
3819 	         (int*) &sepadata->sortswitch, TRUE, DEFAULT_SORTSWITCH, 0, 4, NULL, NULL) );
3820 	
3821 	   SCIP_CALL( SCIPaddBoolParam(scip, "separating/" SEPA_NAME "/sortrootneighbors",
3822 	         "sort level of the root neighbors by fractionality (maxfrac)",
3823 	         &sepadata->sortrootneighbors, TRUE, DEFAULT_SORTROOTNEIGHBORS, NULL, NULL) );
3824 	
3825 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/percenttestvars",
3826 	         "percentage of variables to try the chosen method on [0-100]",
3827 	         &sepadata->percenttestvars, TRUE, DEFAULT_PERCENTTESTVARS, 0, 100, NULL, NULL) );
3828 	
3829 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/offsettestvars",
3830 	         "offset of variables to try the chosen method on (additional to the percentage of testvars)",
3831 	         &sepadata->offsettestvars, TRUE, DEFAULT_OFFSETTESTVARS, 0, INT_MAX, NULL, NULL) );
3832 	
3833 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxpernodeslevel",
3834 	         "percentage of nodes allowed in the same level of the level graph [0-100]",
3835 	         &sepadata->maxpernodeslevel, TRUE, DEFAULT_MAXPERNODESLEVEL, 0, 100, NULL, NULL) );
3836 	
3837 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/offsetnodeslevel",
3838 	         "offset of nodes allowed in the same level of the level graph (additional to the percentage of levelnodes)",
3839 	         &sepadata->offsetnodeslevel, TRUE, DEFAULT_OFFSETNODESLEVEL, 0, INT_MAX, NULL, NULL) );
3840 	
3841 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxnlevels",
3842 	         "maximal number of levels in level graph",
3843 	         &sepadata->maxnlevels, TRUE, DEFAULT_MAXNLEVELS, 0, INT_MAX, NULL, NULL) );
3844 	
3845 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxcutsroot",
3846 	         "maximal number of oddcycle cuts generated per chosen variable as root of the level graph",
3847 	         &sepadata->maxcutsroot, TRUE, DEFAULT_MAXCUTSROOT, 0, INT_MAX, NULL, NULL) );
3848 	
3849 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxcutslevel",
3850 	         "maximal number of oddcycle cuts generated in every level of the level graph",
3851 	         &sepadata->maxcutslevel, TRUE, DEFAULT_MAXCUTSLEVEL, 0, INT_MAX, NULL, NULL) );
3852 	
3853 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxreference",
3854 	         "minimal weight on an edge (in level graph or bipartite graph)",
3855 	         &sepadata->maxreference, TRUE, DEFAULT_MAXREFERENCE, 0, INT_MAX, NULL, NULL) );
3856 	
3857 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/maxunsucessfull",
3858 	         "number of unsuccessful calls at current node",
3859 	         &sepadata->maxunsucessfull, TRUE, DEFAULT_MAXUNSUCESSFULL, 0, INT_MAX, NULL, NULL) );
3860 	
3861 	   SCIP_CALL( SCIPaddIntParam(scip, "separating/" SEPA_NAME "/cutthreshold",
3862 	         "maximal number of other cuts s.t. separation is applied (-1 for direct call)",
3863 	         &sepadata->cutthreshold, TRUE, DEFAULT_CUTTHRESHOLD, -1, INT_MAX, NULL, NULL) );
3864 	
3865 	   return SCIP_OKAY;
3866 	}
3867