Scippy

SCIP

Solving Constraint Integer Programs

dpterms_util.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-2022 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file dpterms_util.c
17  * @brief Utility methods for dynamic programming solver for Steiner tree (sub-) problems
18  * @author Daniel Rehfeldt
19  *
20  * Implements two implementations for finding valid intersections of sub-trees during DP.
21  * One naive one, and one based on a search tree (DPS tree). Performance is slightly better for the latter one.
22  * NOTE: DPS tree design is mostly taken from "Separator-Based Pruned Dynamic Programming for Steiner Tree"
23  * by Iwata and Shigemura.
24  */
25 
26 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
27 //#define SCIP_DEBUG
28 #include "scip/scipdefplugins.h"
29 #include "dpterms.h"
30 #include "dptermsinterns.h"
31 
32 #define CHILD_NONE -1
33 #define CHILD_LEFT 0
34 #define CHILD_RIGHT 1
35 
36 /*
37  * Data structures
38  */
39 
40 /** sub tree */
42 {
43  int children_id[2]; /**< indices of children */
44  STP_Bitset terms_intersection; /**< intersection of all terminals of leaves of subtree */
45  STP_Bitset roots_union; /**< union of all roots of leaves of subtree */
46  int64_t nsubsets; /**< number of subsets */
47  int split_pos; /**< split position */
48 } DPSNODE;
49 
50 
51 /** search tree */
53 {
54  STP_Vectype(DPSNODE) treenodes; /**< nodes */
55  STP_Vectype(int) intersects_tmp; /**< helper */
56  int treeroot; /**< tree root */
57  int nterms; /**< number of terminals of underlying graph */
58  int nnodes; /**< number of nodes of underlying graph */
59 };
60 
61 
62 /*
63  * Local methods
64  */
65 
66 #ifndef NDEBUG
67 
68 /** valid sizes? for debug checks */
69 static
71  STP_Bitset termsmark, /**< terminal mark */
72  STP_Bitset rootsmark, /**< marks roots of extension trees */
73  const DPSTREE* dpstree /**< to check for */
74 )
75 {
76  assert(dpstree && termsmark && rootsmark);
77 
78  if( stpbitset_getCapacity(termsmark) != (((dpstree->nterms + 63) / 64) * 64) )
79  {
80  printf("termsmark size is wrong %d!=%d \n", stpbitset_getCapacity(termsmark), (((dpstree->nterms + 63) / 64) * 64));
81 
82  return FALSE;
83  }
84 
85  if( stpbitset_getCapacity(rootsmark) != (((dpstree->nnodes + 63) / 64) * 64) )
86  {
87  printf("rootsmark size is wrong %d!=%d \n", stpbitset_getCapacity(rootsmark), (((dpstree->nnodes + 63) / 64) * 64));
88 
89  return FALSE;
90  }
91 
92  return TRUE;
93 }
94 
95 
96 /** valid node? for debug checks */
97 static
99  int node_pos, /**< position of node */
100  const DPSTREE* dpstree /**< to check for */
101 )
102 {
103  assert(dpstree);
104 
105  if( node_pos < 0 )
106  {
107  return FALSE;
108  }
109 
110  if( node_pos >= StpVecGetSize(dpstree->treenodes) )
111  {
112  return FALSE;
113  }
114 
115 
116  return TRUE;
117 }
118 #endif
119 
120 
121 /** NOTE: only debug prints */
122 static
124  int node_pos, /**< position of node */
125  const DPSTREE* dpstree /**< to check for */
126 )
127 {
128  assert(treenodeIsInRange(node_pos, dpstree));
129 #ifdef SCIP_DEBUG
130  SCIPdebugMessage("node_pos=%d; split_pos=%d child1=%d, child2=%d \n",
131  node_pos,
132  dpstree->treenodes[node_pos].split_pos,
133  dpstree->treenodes[node_pos].children_id[CHILD_LEFT],
134  dpstree->treenodes[node_pos].children_id[CHILD_RIGHT]);
135 
136  SCIPdebugMessage("intersection/union: \n");
137  stpbitset_print(dpstree->treenodes[node_pos].terms_intersection);
138  stpbitset_print(dpstree->treenodes[node_pos].roots_union);
139 #endif
140 }
141 
142 
143 
144 /** adds leaf
145  * NOTE: takes ownership of termsmark and rootsmark*/
146 static
147 void addLeaf(
148  SCIP* scip, /**< SCIP data structure */
149  STP_Bitset termsmark, /**< terminal mark */
150  STP_Bitset rootsmark, /**< marks roots of extension trees */
151  int64_t nsubsets, /**< number of subsets */
152  int* leafpos, /**< position of new leaf */
153  DPSTREE* dpstree /**< to insert to */
154 )
155 {
156  DPSNODE leaf = { .children_id = {CHILD_NONE, CHILD_NONE},
157  .terms_intersection = termsmark,
158  .roots_union = rootsmark,
159  .nsubsets = nsubsets,
160  .split_pos = dpstree->nterms /* mark as leaf */
161  };
162 
163  assert(bitsetsizesAreValid(termsmark, rootsmark, dpstree));
164 
165  *leafpos = StpVecGetSize(dpstree->treenodes);
166  StpVecPushBack(scip, dpstree->treenodes, leaf);
167 }
168 
169 
170 /** inserts (recursively) */
171 static
173  SCIP* scip, /**< SCIP data structure */
174  STP_Bitset termsmark, /**< terminal mark */
175  STP_Bitset rootsmark, /**< marks roots of extension trees */
176  int64_t nsubsets, /**< number of subsets */
177  int node_pos, /**< node position */
178  int split_pos, /**< current split position */
179  int* subrootpos, /**< position of new sub-root */
180  DPSTREE* dpstree /**< to insert to */
181 )
182 {
183  STP_Vectype(DPSNODE) tnodes = dpstree->treenodes;
185 
186  assert(0 <= split_pos && split_pos <= dpstree->nterms);
187  assert(treenodeIsInRange(node_pos, dpstree));
188  assert(bitsetsizesAreValid(termsmark, rootsmark, dpstree));
189 
190  terms_intersection = tnodes[node_pos].terms_intersection;
191  assert(terms_intersection);
192 
193  /* find the correct position */
194  while( tnodes[node_pos].split_pos != split_pos &&
195  stpbitset_bitIsTrue(terms_intersection, split_pos) == stpbitset_bitIsTrue(termsmark, split_pos) )
196  {
197  split_pos++;
198  assert(split_pos <= dpstree->nterms);
199  }
200 
201  if( tnodes[node_pos].split_pos == split_pos )
202  {
203  /* split position is greater equal than split position of the current node */
204  int root;
205  const int down_direction =
206  stpbitset_bitIsTrue(termsmark, split_pos) ? CHILD_RIGHT : CHILD_LEFT;
207  const int child_position = tnodes[node_pos].children_id[down_direction];
208  STP_Bitset roots_union = tnodes[node_pos].roots_union;
209 
210  assert(child_position >= 0 && child_position != node_pos);
211 
212  /* update node data */
213  stpbitset_and(scip, termsmark, terms_intersection, terms_intersection);
214  stpbitset_or(scip, rootsmark, roots_union, roots_union);
215 
216  SCIPdebugMessage("update internal node:\n ");
217  printNodeDebugInfo(node_pos, dpstree);
218  SCIPdebugMessage("continue with child %d \n", down_direction);
219 
220  /* continue from child */
221  insertData(scip, termsmark, rootsmark, nsubsets, child_position, split_pos + 1,
222  &(root), dpstree);
223  dpstree->treenodes[node_pos].children_id[down_direction] = root;
224 
225  *subrootpos = node_pos;
226  }
227  else
228  {
229  /* split position is smaller than split position of the current node */
230  int leaf_pos;
231  STP_Bitset roots_union = tnodes[node_pos].roots_union;
232  const SCIP_Bool leafIsRight = stpbitset_bitIsTrue(termsmark, split_pos);
233 
234  assert(stpbitset_bitIsTrue(terms_intersection, split_pos) != stpbitset_bitIsTrue(termsmark, split_pos));
235 
236  /* we add a new internal node with current node and new leaf as children */
237 
238  addLeaf(scip,
239  stpbitset_newCopy(scip, termsmark),
240  stpbitset_newCopy(scip, rootsmark),
241  nsubsets, &leaf_pos, dpstree);
242 
243  stpbitset_and(scip, terms_intersection, termsmark, termsmark);
244  stpbitset_or(scip, roots_union, rootsmark, rootsmark);
245 
246  assert(stpbitset_getPopcount(rootsmark) > 0);
247 
248  {
249  DPSNODE parent = {
250  .terms_intersection = termsmark,
251  .roots_union = rootsmark,
252  .nsubsets = -1, /* mark as internal node */
253  .split_pos = split_pos };
254 
255  if( leafIsRight )
256  {
257  parent.children_id[CHILD_LEFT] = node_pos;
258  parent.children_id[CHILD_RIGHT] = leaf_pos;
259  }
260  else
261  {
262  parent.children_id[CHILD_LEFT] = leaf_pos;
263  parent.children_id[CHILD_RIGHT] = node_pos;
264  }
265 
266  *subrootpos = StpVecGetSize(dpstree->treenodes);
267  StpVecPushBack(scip, dpstree->treenodes, parent);
268 
269  SCIPdebugMessage("created new internal node: \n");
270  printNodeDebugInfo(*subrootpos, dpstree);
271  }
272  }
273 }
274 
275 
276 /** gets indices of intersections */
277 static
279  SCIP* scip, /**< SCIP data structure */
280  STP_Bitset termsmark, /**< terminal mark */
281  STP_Bitset rootsmark, /**< marks roots of extension trees */
282  int node_pos, /**< node position */
283  DPSTREE* dpstree /**< to insert to */
284 )
285 {
286  STP_Vectype(DPSNODE) tnodes = dpstree->treenodes;
287  STP_Bitset terms_intersection = tnodes[node_pos].terms_intersection;
288  STP_Bitset roots_union = tnodes[node_pos].roots_union;
289 
290  assert(scip && dpstree && termsmark && rootsmark && tnodes);
291  assert(bitsetsizesAreValid(termsmark, rootsmark, dpstree));
292  assert(treenodeIsInRange(node_pos, dpstree));
293 
294  SCIPdebugMessage("at node: \n");
295  printNodeDebugInfo(node_pos, dpstree);
296 
297  if( stpbitset_haveIntersection(terms_intersection, termsmark) )
298  {
299  SCIPdebugMessage("common terminal with subtree, returning \n");
300  return;
301  }
302  else if( !stpbitset_haveIntersection(roots_union, rootsmark) )
303  {
304  SCIPdebugMessage("no common extension-root with subtree, returning \n");
305  return;
306  }
307  /* at leaf? */
308  else if( tnodes[node_pos].split_pos == dpstree->nterms )
309  {
310  SCIPdebugMessage("...is leaf \n");
311  assert(tnodes[node_pos].nsubsets >= 0); /* double check that really leaf */
312 
313  StpVecPushBack(scip, dpstree->intersects_tmp, tnodes[node_pos].nsubsets);
314  }
315  else
316  {
317  SCIPdebugMessage("check left child \n");
318  streeCollectIntersects(scip, termsmark, rootsmark,
319  tnodes[node_pos].children_id[CHILD_LEFT],
320  dpstree);
321 
322  /* any chance to find something in the right child? */
323  if( !stpbitset_bitIsTrue(termsmark, tnodes[node_pos].split_pos) )
324  {
325  SCIPdebugMessage("check right child \n");
326  streeCollectIntersects(scip, termsmark, rootsmark,
327  tnodes[node_pos].children_id[CHILD_RIGHT],
328  dpstree);
329  }
330  }
331 }
332 
333 
334 /*
335  * Interface methods
336  */
337 
338 
339 /** for debugging: checks whether given intersection is equal to naively computed one */
341  SCIP* scip, /**< SCIP data structure */
342  STP_Bitset termsmark, /**< terminal mark */
343  STP_Bitset rootsmark, /**< marks roots of extension trees */
344  STP_Vectype(int) intersects, /**< intersection indices */
345  DPMISC* dpmisc /**< MISC DP data */
346 )
347 {
348  STP_Vectype(int) intersects_naive = dpterms_collectIntersectsNaive(scip, termsmark, rootsmark, dpmisc);
349  SCIP_Bool isEqual = TRUE;
350 
351  if( StpVecGetSize(intersects_naive) != StpVecGetSize(intersects) )
352  {
353 #ifdef SCIP_DEBUG
354  SCIPdebugMessage("wrong sizes: %d %d\n", StpVecGetSize(intersects_naive), StpVecGetSize(intersects));
355  printf("naive: \n");
356 
357  for( int i = 0; i < StpVecGetSize(intersects_naive); i++ )
358  printf("%d \n", intersects_naive[i]);
359 
360  printf("org: \n");
361  for( int i = 0; i < StpVecGetSize(intersects); i++ )
362  printf("%d \n", intersects[i]);
363 #endif
364  isEqual = FALSE;
365  }
366  else
367  {
368  const int ninds = StpVecGetSize(intersects);
369  int* intersects_org;
370 
371  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &intersects_org, ninds) );
372  BMScopyMemoryArray(intersects_org, intersects, ninds);
373 
374  SCIPsortDownInt(intersects_org, ninds);
375  SCIPsortDownInt(intersects_naive, ninds);
376 
377  for( int i = 0; i < ninds; i++ )
378  {
379  if( intersects_org[i] != intersects_naive[i] )
380  {
381  SCIPdebugMessage("wrong index %d: %d!=%d \n", i, intersects_org[i], intersects_naive[i]);
382 
383  isEqual = FALSE;
384  break;
385  }
386  }
387 
388  SCIPfreeMemoryArray(scip, &intersects_org);
389  }
390 
391 
392  StpVecFree(scip, intersects_naive);
393 
394  return isEqual;
395 }
396 
397 
398 /** gets indices of intersections by using naive computation */
399 STP_Vectype(int) dpterms_collectIntersectsNaive(
400  SCIP* scip, /**< SCIP data structure */
401  STP_Bitset termsmark, /**< terminal mark */
402  STP_Bitset rootsmark, /**< marks roots of extension trees */
403  DPMISC* dpmisc /**< MISC DP data */
404 )
405 {
406  STP_Vectype(int) intersects = NULL;
407  STP_Vectype(SOLTRACE) global_traces = dpmisc->global_traces;
408  STP_Vectype(STP_Bitset) global_termbits = dpmisc->global_termbits;
409  STP_Vectype(int) global_starts = dpmisc->global_starts;
410  const int nsets = StpVecGetSize(global_termbits);
411 
412  for( int i = 0; i < nsets; i++ )
413  {
414  STP_Bitset termsmark_i = global_termbits[i];
415  assert(stpbitset_setsAreCompatible(termsmark_i, termsmark));
416 
417  if( !stpbitset_haveIntersection(termsmark_i, termsmark) )
418  {
419  SOLTRACE* soltraces_i = &(global_traces[global_starts[i]]);
420  const int nsoltraces = global_starts[i + 1] - global_starts[i];
421  SCIP_Bool hasIntersection = FALSE;
422 
423  assert(nsoltraces >= 0);
424 
425  for( int j = 0; j < nsoltraces; j++ )
426  {
427  const int root = soltraces_i[j].root;
428 
429  if( stpbitset_bitIsTrue(rootsmark, root) )
430  {
431  hasIntersection = TRUE;
432  break;
433  }
434  }
435 
436  if( hasIntersection )
437  {
438  StpVecPushBack(scip, intersects, i);
439  }
440  }
441  }
442 
443  return intersects;
444 }
445 
446 
447 /** inserts
448  * NOTE: dps-tree takes ownership of bitsets! */
450  SCIP* scip, /**< SCIP data structure */
451  STP_Bitset termsmark, /**< terminal mark; will become OWNED */
452  STP_Bitset rootsmark, /**< marks roots of extension trees; will become OWNED */
453  int64_t nsubsets, /**< number of subsets */
454  DPSTREE* dpstree /**< to insert to */
455 )
456 {
457  assert(scip && dpstree && termsmark && rootsmark);
458  assert(nsubsets >= 0);
459  assert(bitsetsizesAreValid(termsmark, rootsmark, dpstree));
460  assert(stpbitset_getPopcount(rootsmark) > 0);
461 
462 #ifdef SCIP_DEBUG
463  SCIPdebugMessage("inserting: \n");
464  SCIPdebugMessage("termsmark: ");
465  stpbitset_print(termsmark);
466  SCIPdebugMessage("rootsmark: ");
467  stpbitset_print(rootsmark);
468 #endif
469 
470  // todo if ever too big, need to change some data to int64_t
471  if( nsubsets >= (INT_MAX - 1) )
472  {
473  SCIPerrorMessage("too many subsets in terminal-based DP \n");
474  return SCIP_ERROR;
475  }
476 
477  if( dpstree->treeroot == -1 )
478  {
479  int leafpos;
480  SCIPdebugMessage("...is first element \n");
481 
482  addLeaf(scip, termsmark, rootsmark, nsubsets, &leafpos, dpstree);
483  assert(leafpos == 0);
484  dpstree->treeroot = 0;
485  }
486  else
487  {
488  int subroot;
489  const int node_pos = dpstree->treeroot;
490  const int split_pos = 0;
491  SCIPdebugMessage("insert from root %d \n", dpstree->treeroot);
492 
493  insertData(scip, termsmark, rootsmark, nsubsets, node_pos, split_pos, &subroot, dpstree);
494  assert(subroot >= 0);
495  SCIPdebugMessage("new root=%d \n", subroot);
496  dpstree->treeroot = subroot;
497  }
498 
499  return SCIP_OKAY;
500 }
501 
502 
503 /** gets indices of intersections */
504 STP_Vectype(int) dpterms_streeCollectIntersects(
505  SCIP* scip, /**< SCIP data structure */
506  STP_Bitset termsmark, /**< terminal mark */
507  STP_Bitset rootsmark, /**< marks roots of extension trees */
508  DPSTREE* dpstree /**< to insert to */
509 )
510 {
511  STP_Vectype(int) intersects;
512 
513  assert(scip && dpstree && termsmark && rootsmark);
514  assert(bitsetsizesAreValid(termsmark, rootsmark, dpstree));
515  assert(!dpstree->intersects_tmp);
516 
517  SCIPdebugMessage("collect intersections \n");
518 
519  if( dpstree->treeroot != -1 )
520  {
521  assert(dpstree->treeroot >= 0);
522  streeCollectIntersects(scip, termsmark, rootsmark, dpstree->treeroot, dpstree);
523  }
524 
525  intersects = dpstree->intersects_tmp;
526  dpstree->intersects_tmp = NULL;
527 
528  return intersects;
529 }
530 
531 
532 /** initializes */
534  SCIP* scip, /**< SCIP data structure */
535  int nterms, /**< number of terminals */
536  int nnodes, /**< number of nodes */
537  DPSTREE** dpstree /**< initialize */
538 )
539 {
540  DPSTREE* tree;
541 
542  assert(scip);
543  assert(nterms > 0);
544  assert(nnodes >= nterms);
545 
546  SCIP_CALL( SCIPallocMemory(scip, dpstree) );
547  tree = *dpstree;
548 
549  tree->treeroot = -1;
550  tree->nterms = nterms;
551  tree->nnodes = nnodes;
552  tree->treenodes = NULL;
553  tree->intersects_tmp = NULL;
554 
555  return SCIP_OKAY;
556 }
557 
558 
559 /** frees */
561  SCIP* scip, /**< SCIP data structure */
562  DPSTREE** dpstree /**< initialize */
563 )
564 {
565  DPSTREE* tree;
566  int ntreenodes;
567 
568  assert(scip);
569  assert(!(*dpstree)->intersects_tmp);
570 
571  tree = *dpstree;
572  ntreenodes = StpVecGetSize(tree->treenodes);
573 
574  for( int i = ntreenodes - 1; i >= 0; i-- )
575  {
576  stpbitset_free(scip, &(tree->treenodes[i].terms_intersection));
577  stpbitset_free(scip, &(tree->treenodes[i].roots_union));
578  }
579 
580  StpVecFree(scip, tree->treenodes);
581 
582  SCIPfreeMemory(scip, dpstree);
583 }
static volatile int nterms
Definition: interrupt.c:38
#define StpVecGetSize(vec)
Definition: stpvector.h:139
SCIP_RETCODE dpterms_streeInit(SCIP *scip, int nterms, int nnodes, DPSTREE **dpstree)
Definition: dpterms_util.c:533
#define SCIPfreeMemoryArray(scip, ptr)
Definition: scip_mem.h:71
static SCIP_Bool treenodeIsInRange(int node_pos, const DPSTREE *dpstree)
Definition: dpterms_util.c:98
#define SCIPallocMemoryArray(scip, ptr, num)
Definition: scip_mem.h:55
static void streeCollectIntersects(SCIP *scip, STP_Bitset termsmark, STP_Bitset rootsmark, int node_pos, DPSTREE *dpstree)
Definition: dpterms_util.c:278
static SCIP_Bool stpbitset_haveIntersection(STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:177
#define FALSE
Definition: def.h:87
static int stpbitset_getCapacity(STP_Bitset bitset)
Definition: stpbitset.h:116
#define TRUE
Definition: def.h:86
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:54
struct dynamic_programming_search_tree_node DPSNODE
Dynamic programming solver for Steiner tree (sub-) problems with small number of terminals.
static void stpbitset_print(STP_Bitset bitset)
Definition: stpbitset.h:452
#define SCIPdebugMessage
Definition: pub_message.h:87
SCIP_Bool dpterms_intersectsEqualNaive(SCIP *scip, STP_Bitset termsmark, STP_Bitset rootsmark, STP_Vectype(int) intersects, DPMISC *dpmisc)
Definition: dpterms_util.c:340
static void stpbitset_and(SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2, STP_Bitset bitsetAnd)
Definition: stpbitset.h:286
static void printNodeDebugInfo(int node_pos, const DPSTREE *dpstree)
Definition: dpterms_util.c:123
#define CHILD_RIGHT
Definition: dpterms_util.c:34
STP_Bitset
static SCIP_Bool stpbitset_setsAreCompatible(STP_Bitset bitset1, STP_Bitset bitset2)
Definition: stpbitset.h:157
#define SCIPerrorMessage
Definition: pub_message.h:55
#define NULL
Definition: lpi_spx1.cpp:155
#define CHILD_NONE
Definition: dpterms_util.c:32
STP_Vectype(int)
Definition: dpterms_util.c:399
#define SCIP_CALL(x)
Definition: def.h:384
#define CHILD_LEFT
Definition: dpterms_util.c:33
static void stpbitset_or(SCIP *scip, STP_Bitset bitset1, STP_Bitset bitset2, STP_Bitset bitsetOr)
Definition: stpbitset.h:308
static SCIP_Bool bitsetsizesAreValid(STP_Bitset termsmark, STP_Bitset rootsmark, const DPSTREE *dpstree)
Definition: dpterms_util.c:70
#define SCIP_Bool
Definition: def.h:84
static STP_Bitset stpbitset_newCopy(SCIP *scip, STP_Bitset bitsetOrg)
Definition: stpbitset.h:267
static void insertData(SCIP *scip, STP_Bitset termsmark, STP_Bitset rootsmark, int64_t nsubsets, int node_pos, int split_pos, int *subrootpos, DPSTREE *dpstree)
Definition: dpterms_util.c:172
static void stpbitset_free(SCIP *scip, STP_Bitset *bitset)
Definition: stpbitset.h:100
static SCIP_Bool stpbitset_bitIsTrue(STP_Bitset bitset, int index)
Definition: stpbitset.h:223
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:127
Dynamic programming internals for Steiner tree (sub-) problems with small number of terminals...
#define SCIPfreeMemory(scip, ptr)
Definition: scip_mem.h:69
void SCIPsortDownInt(int *intarray, int len)
SCIP_RETCODE dpterms_streeInsert(SCIP *scip, STP_Bitset termsmark, STP_Bitset rootsmark, int64_t nsubsets, DPSTREE *dpstree)
Definition: dpterms_util.c:449
#define StpVecFree(scip, vec)
Definition: stpvector.h:149
static int stpbitset_getPopcount(STP_Bitset bitset)
Definition: stpbitset.h:247
#define SCIPallocMemory(scip, ptr)
Definition: scip_mem.h:51
#define nnodes
Definition: gastrans.c:65
#define StpVecPushBack(scip, vec, value)
Definition: stpvector.h:163
static void addLeaf(SCIP *scip, STP_Bitset termsmark, STP_Bitset rootsmark, int64_t nsubsets, int *leafpos, DPSTREE *dpstree)
Definition: dpterms_util.c:147
#define SCIP_CALL_ABORT(x)
Definition: def.h:363
default SCIP plugins
void dpterms_streeFree(SCIP *scip, DPSTREE **dpstree)
Definition: dpterms_util.c:560