Scippy

SCIP

Solving Constraint Integer Programs

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