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