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