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