Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_bliss.cpp
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-2017 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 email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file compute_symmetry_bliss.cpp
17  * @brief interface for symmetry computations to bliss
18  * @author Marc Pfetsch
19  * @author Thomas Rehn
20  */
21 
22 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
23 
24 #include "compute_symmetry.h"
25 
26 /* include bliss graph */
27 #include <bliss/defs.hh>
28 #include <bliss/graph.hh>
29 
30 #include <vector>
31 #include <list>
32 #include <math.h>
33 
34 /** struct for bliss callback */
35 struct BLISS_Data
36 {
37  SCIP* scip; /**< SCIP pointer */
38  int npermvars; /**< number of variables for permutations */
39  int nperms; /**< number of permutations */
40  int** perms; /**< permutation generators as (nperms x npermvars) matrix */
41  int nmaxperms; /**< maximal number of permutations */
42  int maxgenerators; /**< maximal number of generators constructed (= 0 if unlimited) */
43 };
44 
45 
46 /** callback function for bliss */
47 static
48 void blisshook(
49  void* user_param, /**< parameter supplied at call to bliss */
50  unsigned int n, /**< size of aut vector */
51  const unsigned int* aut /**< automorphism */
52  )
53 {
54  assert( aut != NULL );
55  assert( user_param != NULL );
56 
57  BLISS_Data* data = (BLISS_Data*) user_param;
58  assert( data->scip != NULL );
59  assert( data->perms != NULL );
60  assert( data->npermvars < (int) n );
61  assert( data->maxgenerators >= 0);
62 
63  /* make sure we do not generate more that maxgenerators many permutations, if the limit is bliss is not available */
64  if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
65  return;
66 
67  /* check whether we need to resize */
68  if ( data->nperms >= data->nmaxperms )
69  {
70  int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms);
71  SCIP_RETCODE retcode = SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize);
72  if ( retcode != SCIP_OKAY )
73  return;
74  data->nmaxperms = newsize;
75  }
76 
77  /* copy first part of automorphism */
78  bool isIdentity = true;
79  int* p = 0;
80  SCIP_RETCODE retcode = SCIPallocBlockMemoryArray(data->scip, &p, data->npermvars);
81  if ( retcode != SCIP_OKAY )
82  return;
83  for (int j = 0; j < data->npermvars; ++j)
84  {
85  /* convert index of variable-level 0-nodes to variable indices */
86  p[j] = (int) aut[j];
87  if ( p[j] != j )
88  isIdentity = false;
89  }
90 
91  /* ignore trivial generators, i.e. generators that only permute the constraints */
92  if ( isIdentity )
93  {
94  SCIPfreeBlockMemoryArray(data->scip, &p, data->npermvars);
95  }
96  else
97  data->perms[data->nperms++] = p;
98 }
99 
100 
101 /** Construct colored graph for symmetry computations
102  *
103  * Construct bipartite graph:
104  * - Each variable gets a different node.
105  * - Each constraint gets a different node.
106  * - Each matrix coefficient gets a different node that is conntected to the two nodes
107  * corresponding to the constraint and variable.
108  *
109  * Each different variable, rhs, and matrix coefficient type gets a different color that is
110  * attached to the corresponding entries.
111  */
112 static
114  SCIP* scip, /**< SCIP instance */
115  bliss::Graph* G, /**< Graph to be constructed */
116  SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
117  int& nnodes, /**< number of nodes in graph */
118  int& nedges, /**< number of edges in graph */
119  SCIP_Bool& success /**< whether the construction was successful */
120  )
121 {
122  SCIPdebugMsg(scip, "Building graph with colored coefficient nodes.\n");
123 
124  nnodes = 0;
125  nedges = 0;
126  success = FALSE;
127 
128  /* add nodes for variables */
129  for (int v = 0; v < matrixdata->npermvars; ++v)
130  {
131  const int color = matrixdata->permvarcolors[v];
132  assert( 0 <= color && color < matrixdata->nuniquevars );
133 
134 #ifndef NDEBUG
135  int node = (int) G->add_vertex((unsigned) color);
136  assert( node == v );
137 #else
138  (void) G->add_vertex((unsigned) color);
139 #endif
140 
141  ++nnodes;
142  }
143  assert( (int) G->get_nof_vertices() == matrixdata->npermvars );
144 
145  /* add nodes for rhs of constraints */
146  for (int c = 0; c < matrixdata->nrhscoef; ++c)
147  {
148  const int color = matrixdata->rhscoefcolors[c];
149  assert( 0 <= color && color < matrixdata->nuniquerhs );
150 
151 #ifndef NDEBUG
152  int node = (int) G->add_vertex((unsigned) (matrixdata->nuniquevars + color));
153  assert( node == matrixdata->npermvars + c );
154 #else
155  (void) G->add_vertex((unsigned) (matrixdata->nuniquevars + color));
156 #endif
157 
158  ++nnodes;
159  }
160  assert( (int) G->get_nof_vertices() == matrixdata->npermvars + matrixdata->nrhscoef );
161 
162  /* Grouping of nodes depends on the number of nodes in the bipartite graph class.
163  * If there are more variables than constraints, we group by constraints.
164  * That is, given several variable nodes which are incident to one constraint node by the same color,
165  * we join these variable nodes to the constaint node by only one intermediate node.
166  */
167  const bool groupByConstraints = matrixdata->nrhscoef < matrixdata->npermvars;
168  if ( groupByConstraints )
169  SCIPdebugMsg(scip, "Group intermediate nodes by constraints.\n");
170  else
171  SCIPdebugMsg(scip, "Group intermediate nodes by variables.\n");
172 
173  /* "colored" edges based on all matrix coefficients - loop through ordered matrix coefficients */
174  int nusedcolors = matrixdata->nuniquevars + matrixdata->nuniquerhs;
175 
176  int ninternodes;
177  if ( groupByConstraints )
178  ninternodes = matrixdata->nrhscoef;
179  else
180  ninternodes = matrixdata->npermvars;
181 
182  int* internodes = NULL;
183  SCIP_CALL( SCIPallocBufferArray(scip, &internodes, ninternodes) ); /*lint !e530*/
184  for (int l = 0; l < ninternodes; ++l)
185  internodes[l] = -1;
186 
187  /* We pass through the matrix coeficients, grouped by color, i.e., different coefficients. If the coeffients appear
188  * in the same row or column, it suffices to only generate a single node (depending on groupByConstraints). We store
189  * this node in the array internodes. In order to avoid reinitialization, we store the node number with increasing
190  * numbers for each color. The smallest number for the current color is stored in firstcolornodenumber. */
191  int oldcolor = -1;
192 #ifndef NDEBUG
193  SCIP_Real oldcoef = SCIP_INVALID;
194 #endif
195  int firstcolornodenumber = -1;
196  for (int j = 0; j < matrixdata->nmatcoef; ++j)
197  {
198  int idx = matrixdata->matidx[j];
199  assert( 0 <= idx && idx < matrixdata->nmatcoef );
200 
201  /* find color corresponding to matrix coefficient */
202  const int color = matrixdata->matcoefcolors[idx];
203  assert( 0 <= color && color < matrixdata->nuniquemat );
204 
205  assert( 0 <= matrixdata->matrhsidx[idx] && matrixdata->matrhsidx[idx] < matrixdata->nrhscoef );
206  assert( 0 <= matrixdata->matvaridx[idx] && matrixdata->matvaridx[idx] < matrixdata->npermvars );
207 
208  const int rhsnode = matrixdata->npermvars + matrixdata->matrhsidx[idx];
209  const int varnode = matrixdata->matvaridx[idx];
210  assert( matrixdata->npermvars <= rhsnode && rhsnode < matrixdata->npermvars + matrixdata->nrhscoef );
211  assert( rhsnode < (int) G->get_nof_vertices() );
212  assert( varnode < (int) G->get_nof_vertices() );
213 
214  /* if we have only one color, we do not need intermediate nodes */
215  if ( matrixdata->nuniquemat == 1 )
216  {
217  G->add_edge((unsigned) varnode, (unsigned) rhsnode);
218  ++nedges;
219  }
220  else
221  {
222  /* if new group of coefficients has been reached */
223  if ( color != oldcolor )
224  {
225  assert( ! SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
226  oldcolor = color;
227  firstcolornodenumber = nnodes;
228 #ifndef NDEBUG
229  oldcoef = matrixdata->matcoef[idx];
230 #endif
231  }
232  else
233  assert( SCIPisEQ(scip, oldcoef, matrixdata->matcoef[idx]) );
234 
235  int varrhsidx;
236  if ( groupByConstraints )
237  varrhsidx = matrixdata->matrhsidx[idx];
238  else
239  varrhsidx = matrixdata->matvaridx[idx];
240  assert( 0 <= varrhsidx && varrhsidx < ninternodes );
241 
242  if ( internodes[varrhsidx] < firstcolornodenumber )
243  {
244  internodes[varrhsidx] = (int) G->add_vertex((unsigned) (nusedcolors + color));
245  ++nnodes;
246  }
247  assert( internodes[varrhsidx] >= matrixdata->npermvars + matrixdata->nrhscoef );
248  assert( internodes[varrhsidx] >= firstcolornodenumber );
249 
250  /* determine whether graph would be too large for bliss (can only handle int) */
251  if ( nnodes >= INT_MAX/2 )
252  {
253  SCIPfreeBufferArray(scip, &internodes);
254  return SCIP_OKAY;
255  }
256 
257  G->add_edge((unsigned) varnode, (unsigned) internodes[varrhsidx]);
258  G->add_edge((unsigned) rhsnode, (unsigned) internodes[varrhsidx]);
259  nedges += 2;
260  }
261  }
262  SCIPfreeBufferArray(scip, &internodes);
263 
264  success = TRUE; /*lint !e838*/
265 
266  return SCIP_OKAY;
267 }
268 
269 
270 /** return whether symmetry can be computed */
272 {
273  return TRUE;
274 }
275 
276 /** static variable for holding the name of bliss */
277 static char blissname[100];
278 
279 /** return name of external program used to compute generators */
280 const char* SYMsymmetryGetName(void)
281 {
282 #ifdef BLISS_PATCH_PRESENT
283  sprintf(blissname, "bliss %sp", bliss::version);
284 #else
285  sprintf(blissname, "bliss %s", bliss::version);
286 #endif
287  return blissname;
288 }
289 
290 /** return description of external program used to compute generators */
291 const char* SYMsymmetryGetDesc(void)
292 {
293  return "Computing Graph Automorphism Groups by T. Junttila and P. Kaski (http://www.tcs.hut.fi/Software/bliss/)";
294 }
295 
296 /** compute generators of symmetry group */
298  SCIP* scip, /**< SCIP pointer */
299  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
300  SYM_MATRIXDATA* matrixdata, /**< data for MIP matrix */
301  int* nperms, /**< pointer to store number of permutations */
302  int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
303  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
304  SCIP_Real* log10groupsize /**< pointer to store size of group */
305  )
306 {
307  assert( scip != NULL );
308  assert( matrixdata != NULL );
309  assert( nperms != NULL );
310  assert( nmaxperms != NULL );
311  assert( perms != NULL );
312  assert( log10groupsize != NULL );
313  assert( maxgenerators >= 0 );
314 
315  /* init */
316  *nperms = 0;
317  *nmaxperms = 0;
318  *perms = NULL;
319  *log10groupsize = 0;
320 
321  int nnodes = 0;
322  int nedges = 0;
323 
324  /* create bliss graph */
325  bliss::Graph G(0);
326 
327  SCIP_Bool success = FALSE;
328  SCIP_CALL( fillGraphByColoredCoefficients(scip, &G, matrixdata, nnodes, nedges, success) );
329  if ( ! success )
330  {
331  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, 0, "Graph construction failed.\n");
332  return SCIP_OKAY;
333  }
334 
335 #ifdef SCIP_OUTPUT
336  G.write_dot("debug.dot");
337 #endif
338 
339  SCIPdebugMsg(scip, "Symmetry detection graph has %u nodes.\n", G.get_nof_vertices());
340 
341  /* compute automorphisms */
342  bliss::Stats stats;
343  BLISS_Data data;
344  data.scip = scip;
345  data.npermvars = matrixdata->npermvars;
346  data.nperms = 0;
347  data.nmaxperms = 100 * matrixdata->npermvars;
349  data.perms = NULL;
350  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &data.perms, data.nmaxperms) );
351 
352  /* Prefer splitting partition cells corresponding to variables over those corresponding
353  * to inequalities. This is because we are only interested in the action
354  * of the automorphism group on the variables, and we need a base for this action */
355  G.set_splitting_heuristic(bliss::Graph::shs_f);
356  /* disable component recursion as advised by Tommi Junttila from bliss */
357  G.set_component_recursion(false);
358 
359  /* do not use a node limit, but set generator limit */
360 #ifdef BLISS_PATCH_PRESENT
361  G.set_search_limits(0, (unsigned) maxgenerators);
362 #endif
363 
364  /* start search */
365  G.find_automorphisms(stats, blisshook, (void*) &data);
366 #ifdef SCIP_OUTPUT
367  (void) stats.print(stdout);
368 #endif
369 
370  /* prepare return values */
371  *perms = data.perms;
372  *nperms = data.nperms;
373  *nmaxperms = data.nmaxperms;
374 
375  /* determine log10 of symmetry group size */
376  *log10groupsize = (SCIP_Real) log10l(stats.get_group_size_approx());
377 
378  return SCIP_OKAY;
379 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22604
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip.h:22593
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip.h:22587
SCIP_Real * matcoef
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip.c:46807
const char * SYMsymmetryGetName(void)
#define FALSE
Definition: def.h:64
#define TRUE
Definition: def.h:63
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
const char * SYMsymmetryGetDesc(void)
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip.c:46957
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip.h:22632
#define SCIPdebugMsg
Definition: scip.h:455
interface for symmetry computations
static void blisshook(void *user_param, unsigned int n, const unsigned int *aut)
static char blissname[100]
#define SCIP_CALL(x)
Definition: def.h:350
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
Definition: scip.c:1360
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip.h:22620
#define SCIP_Bool
Definition: def.h:61
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_MATRIXDATA *matrixdata, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize)
static SCIP_RETCODE fillGraphByColoredCoefficients(SCIP *scip, bliss::Graph *G, SYM_MATRIXDATA *matrixdata, int &nnodes, int &nedges, SCIP_Bool &success)
#define SCIP_Real
Definition: def.h:149
#define SCIP_INVALID
Definition: def.h:169
#define nnodes
Definition: gastrans.c:65