Scippy

SCIP

Solving Constraint Integer Programs

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