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