Scippy

SCIP

Solving Constraint Integer Programs

compute_symmetry_sassy_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-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 compute_symmetry_sassy_bliss.cpp
26  * @brief interface for symmetry computations to sassy as a preprocessor to bliss
27  * @author Marc Pfetsch
28  */
29 
30 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
31 
32 #include "compute_symmetry.h"
33 
34 /* include bliss */
35 #include <bliss/defs.hh>
36 #include <bliss/graph.hh>
37 
38 /* include sassy */
39 #ifdef __GNUC__
40 #pragma GCC diagnostic ignored "-Wshadow"
41 #pragma GCC diagnostic ignored "-Wunused-variable"
42 #pragma GCC diagnostic ignored "-Wsign-compare"
43 #pragma GCC diagnostic ignored "-Wunused-but-set-variable"
44 #endif
45 
46 #ifdef _MSC_VER
47 # pragma warning(push)
48 # pragma warning(disable: 4189) // local variable is initialized but not referenced
49 # pragma warning(disable: 4267) // conversion of size_t to int (at sassy/preprocessor.h:2897)
50 # pragma warning(disable: 4388) // compare signed and unsigned expression
51 # pragma warning(disable: 4456) // shadowed variable
52 # pragma warning(disable: 4430) // missing type specifier
53 #endif
54 
55 #include <sassy/preprocessor.h>
56 #include <sassy/tools/bliss_converter.h>
57 
58 #ifdef __GNUC__
59 #pragma GCC diagnostic warning "-Wunused-but-set-variable"
60 #pragma GCC diagnostic warning "-Wsign-compare"
61 #pragma GCC diagnostic warning "-Wunused-variable"
62 #pragma GCC diagnostic warning "-Wshadow"
63 #endif
64 
65 #ifdef _MSC_VER
66 # pragma warning(pop)
67 #endif
68 
69 #include "build_sassy_graph.h"
70 
71 #include "scip/expr_var.h"
72 #include "scip/expr_sum.h"
73 #include "scip/expr_pow.h"
74 #include "scip/expr.h"
75 #include "scip/cons_nonlinear.h"
76 #include "scip/cons_linear.h"
77 #include "scip/scip_mem.h"
78 #include "scip/symmetry_graph.h"
79 
80 
81 /** struct for symmetry callback */
83 {
84  SCIP* scip; /**< SCIP pointer */
85  SYM_SYMTYPE symtype; /**< type of symmetries that need to be computed */
86  int npermvars; /**< number of variables for permutations */
87  int nperms; /**< number of permutations */
88  int** perms; /**< permutation generators as (nperms x npermvars) matrix */
89  int nmaxperms; /**< maximal number of permutations */
90  int maxgenerators; /**< maximal number of generators constructed (= 0 if unlimited) */
91  SCIP_Bool restricttovars; /**< whether permutations shall be restricted to variables */
92 };
93 
94 
95 /* ------------------- hook functions ------------------- */
96 
97 /** callback function for sassy */ /*lint -e{715}*/
98 static
99 void sassyhook(
100  void* user_param, /**< parameter supplied at call to sassy */
101  int n, /**< dimension of permutations */
102  const int* aut, /**< permutation */
103  int nsupp, /**< support size */
104  const int* suppa /**< support list */
105  )
106 {
107  assert( aut != NULL );
108  assert( user_param != NULL );
109 
110  SYMMETRY_Data* data = static_cast<SYMMETRY_Data*>(user_param);
111  assert( data->scip != NULL );
112  assert( data->maxgenerators >= 0 );
113 
114  /* make sure we do not generate more that maxgenerators many permutations */
115  if ( data->maxgenerators != 0 && data->nperms >= data->maxgenerators )
116  return;
117 
118  /* copy first part of automorphism */
119  bool isIdentity = true;
120  int* p = 0;
121  int permlen;
122  if ( data->restricttovars )
123  {
124  switch ( data->symtype )
125  {
126  case SYM_SYMTYPE_PERM:
127  permlen = data->npermvars;
128  break;
129  default:
130  assert( data->symtype == SYM_SYMTYPE_SIGNPERM );
131  permlen = 2 * data->npermvars;
132  }
133  }
134  else
135  permlen = n;
136 
137  /* check whether permutation is identity */
138  for (int j = 0; j < permlen; ++j)
139  {
140  if ( (int) aut[j] != j )
141  isIdentity = false;
142  }
143 
144  /* don't store identity permutations */
145  if ( isIdentity )
146  return;
147 
148  if ( SCIPallocBlockMemoryArray(data->scip, &p, permlen) != SCIP_OKAY )
149  return;
150 
151  /* store symmetry */
152  for (int j = 0; j < permlen; ++j)
153  p[j] = (int) aut[j];
154 
155  /* check whether we should allocate space for perms */
156  if ( data->nmaxperms <= 0 )
157  {
158  if ( data->maxgenerators == 0 )
159  data->nmaxperms = 100; /* seems to cover many cases */
160  else
161  data->nmaxperms = data->maxgenerators;
162 
163  if ( SCIPallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms) != SCIP_OKAY )
164  return;
165  }
166  else if ( data->nperms >= data->nmaxperms ) /* check whether we need to resize */
167  {
168  int newsize = SCIPcalcMemGrowSize(data->scip, data->nperms + 1);
169  assert( newsize >= data->nperms );
170  assert( data->maxgenerators == 0 );
171 
172  if ( SCIPreallocBlockMemoryArray(data->scip, &data->perms, data->nmaxperms, newsize) != SCIP_OKAY )
173  return;
174 
175  data->nmaxperms = newsize;
176  }
177 
178  data->perms[data->nperms++] = p;
179 }
180 
181 
182 /** return whether symmetry can be computed */
184 {
185  return TRUE;
186 }
187 
188 /** return name of external program used to compute generators */
189 const char* SYMsymmetryGetName(void)
190 {
191 #ifdef BLISS_PATCH_PRESENT
192  return "bliss " BLISS_VERSION "p";
193 #else
194  return "bliss " BLISS_VERSION;
195 #endif
196 }
197 
198 /** return description of external program used to compute generators */
199 const char* SYMsymmetryGetDesc(void)
200 {
201  return "Computing Graph Automorphisms by T. Junttila and P. Kaski (users.aalto.fi/~tjunttil/bliss)";
202 }
203 
204 #define STR(x) #x
205 #define XSTR(x) STR(x)
206 
207 /** return name of additional external program used for computing symmetries */
208 const char* SYMsymmetryGetAddName(void)
209 {
210  return "sassy " XSTR(SASSY_VERSION_MAJOR) "." XSTR(SASSY_VERSION_MINOR);
211 }
212 
213 /** return description of additional external program used to compute symmetries */
214 const char* SYMsymmetryGetAddDesc(void)
215 {
216  return "Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)";
217 }
218 
219 /** computes autormorphisms of a graph */
220 static
222  SCIP* scip, /**< SCIP pointer */
223  SYM_SYMTYPE symtype, /**< type of symmetries that need to be computed */
224  sassy::static_graph* G, /**< pointer to graph for that automorphisms are computed */
225  int nsymvars, /**< number of variables encoded in graph */
226  int maxgenerators, /**< maximum number of generators to be constructed (=0 if unlimited) */
227  int*** perms, /**< pointer to store generators as (nperms x npermvars) matrix */
228  int* nperms, /**< pointer to store number of permutations */
229  int* nmaxperms, /**< pointer to store maximal number of permutations
230  * (needed for freeing storage) */
231  SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
232  SCIP_Bool restricttovars, /**< whether permutations shall be restricted to variables */
233  SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
234  )
235 {
236  SCIP_Real oldtime;
237 
238  assert( scip != NULL );
239  assert( G != NULL );
240  assert( maxgenerators >= 0 );
241  assert( perms != NULL );
242  assert( nperms != NULL );
243  assert( nmaxperms != NULL );
244  assert( log10groupsize != NULL );
245  assert( symcodetime != NULL );
246 
247  /* init */
248  *nperms = 0;
249  *nmaxperms = 0;
250  *perms = NULL;
251  *log10groupsize = 0;
252  *symcodetime = 0.0;
253 
254  /* init data */
255  struct SYMMETRY_Data data;
256  data.scip = scip;
257  data.symtype = symtype;
258  data.npermvars = nsymvars;
259  data.nperms = 0;
260  data.nmaxperms = 0;
262  data.perms = NULL;
264 
265  oldtime = SCIPgetSolvingTime(scip);
266 
267  /* set up sassy preprocessor */
268  sassy::preprocessor sassy;
269 
270  /* turn off some preprocessing that generates redudant permutations */
271  sassy::configstruct sconfig;
272  sconfig.CONFIG_PREP_DEACT_PROBE = true;
273  sassy.configure(&sconfig);
274 
275  /* lambda function to have access to data and pass it to sassyhook above */
276  sassy::sassy_hook sassyglue = [&](int n, const int* p, int nsupp, const int* suppa) {
277  sassyhook((void*)&data, n, p, nsupp, suppa);
278  };
279 
280  /* call sassy to reduce graph */
281  sassy.reduce(G, &sassyglue);
282 
283  /* create bliss graph */
284  bliss::Graph blissgraph(0);
285 
286  /* convert sassy to bliss graph */
287  convert_sassy_to_bliss(G, &blissgraph);
288 
289 #ifdef SCIP_OUTPUT
290  blissgraph.write_dot("debug.dot");
291 #endif
292 
293 #ifdef SCIP_DISABLED_CODE
294  char filename[SCIP_MAXSTRLEN];
295  (void) SCIPsnprintf(filename, SCIP_MAXSTRLEN, "%s.dimacs", SCIPgetProbName(scip));
296  FILE* fp = fopen(filename, "w");
297  if ( fp )
298  {
299  blissgraph.write_dimacs(fp);
300  fclose(fp);
301  }
302 #endif
303 
304 
305  /* compute automorphisms */
306  bliss::Stats stats;
307 
308  /* Prefer splitting partition cells corresponding to variables over those corresponding
309  * to inequalities. This is because we are only interested in the action
310  * of the automorphism group on the variables, and we need a base for this action */
311  blissgraph.set_splitting_heuristic(bliss::Graph::shs_f);
312  /* disable component recursion as advised by Tommi Junttila from bliss */
313  blissgraph.set_component_recursion(false);
314 
315 #if BLISS_VERSION_MAJOR >= 1 || BLISS_VERSION_MINOR >= 76
316  /* lambda function to have access to data and terminate the search if maxgenerators are reached */
317  auto term = [&]() {
318  return (maxgenerators != 0 && data.nperms >= maxgenerators); /* check the number of generators that we have created so far */
319  };
320 
321  auto hook = [&](unsigned int n, const unsigned int* aut) {
322  sassy.bliss_hook(n, aut);
323  };
324 
325  /* start search */
326  blissgraph.find_automorphisms(stats, hook, term);
327 #else
328 
329  /* Older bliss versions do not allow to terminate with a limit on the number of generators unless patched. */
330 #ifdef BLISS_PATCH_PRESENT
331  /* If patch is present, do not use a node limit, but set generator limit. This approach is not very accurate, since
332  * it limits the generators considered in bliss and not the ones that we generate (the ones that work on the variable
333  * set). */
334  G->set_search_limits(0, (unsigned) maxgenerators);
335 #endif
336 
337  /* start search */
338  blissgraph.find_automorphisms(stats, sassy::preprocessor::bliss_hook, (void*) &sassy);
339 #endif
340  *symcodetime = SCIPgetSolvingTime(scip) - oldtime;
341 
342 #ifdef SCIP_OUTPUT
343  (void) stats.print(stdout);
344 #endif
345 
346  /* prepare return values */
347  if ( data.nperms > 0 )
348  {
349  *perms = data.perms;
350  *nperms = data.nperms;
351  *nmaxperms = data.nmaxperms;
352  }
353  else
354  {
355  assert( data.perms == NULL );
356  assert( data.nmaxperms == 0 );
357 
358  *perms = NULL;
359  *nperms = 0;
360  *nmaxperms = 0;
361  }
362 
363  /* determine log10 of symmetry group size */
364  *log10groupsize = (SCIP_Real) log10l(stats.get_group_size_approx());
365 
366  return SCIP_OKAY;
367 }
368 
369 /** compute generators of symmetry group */
371  SCIP* scip, /**< SCIP pointer */
372  int maxgenerators, /**< maximal number of generators constructed (= 0 if unlimited) */
373  SYM_GRAPH* graph, /**< symmetry detection graph */
374  int* nperms, /**< pointer to store number of permutations */
375  int* nmaxperms, /**< pointer to store maximal number of permutations (needed for freeing storage) */
376  int*** perms, /**< pointer to store permutation generators as (nperms x npermvars) matrix */
377  SCIP_Real* log10groupsize, /**< pointer to store log10 of size of group */
378  SCIP_Real* symcodetime /**< pointer to store the time for symmetry code */
379  )
380 {
381  SCIP_Bool success = FALSE;
382 
383  assert( scip != NULL );
384  assert( maxgenerators >= 0 );
385  assert( graph != NULL );
386  assert( nperms != NULL );
387  assert( nmaxperms != NULL );
388  assert( perms != NULL );
389  assert( log10groupsize != NULL );
390  assert( symcodetime != NULL );
391 
392  /* init */
393  *nperms = 0;
394  *nmaxperms = 0;
395  *perms = NULL;
396  *log10groupsize = 0;
397  *symcodetime = 0.0;
398 
399  /* create sassy graph */
400  sassy::static_graph sassygraph;
401 
402  SCIP_CALL( SYMbuildSassyGraph(scip, &sassygraph, graph, &success) );
403 
404  /* compute symmetries */
406  maxgenerators, perms, nperms, nmaxperms, log10groupsize, TRUE, symcodetime) );
407 
408  return SCIP_OKAY;
409 }
410 
411 /** returns whether two given graphs are identical */
413  SCIP* scip, /**< SCIP pointer */
414  SYM_SYMTYPE symtype, /**< type of symmetries to be checked */
415  SYM_GRAPH* G1, /**< first graph */
416  SYM_GRAPH* G2 /**< second graph */
417  )
418 {
419  int** perms;
420  int nnodes;
421  int nperms;
422  int nmaxperms;
423  int nnodesfromG1;
424  SCIP_Real symcodetime = 0.0;
425  SCIP_Real log10groupsize;
426  SCIP_Bool success;
427 
428  /* create sassy graph */
429  sassy::static_graph sassygraph;
430 
431  SCIP_CALL( SYMbuildSassyGraphCheck(scip, &sassygraph, G1, G2, &nnodes, &nnodesfromG1, &success) );
432 
433  if ( ! success )
434  return FALSE;
435 
436  /* compute symmetries */
437  SCIP_CALL_ABORT( computeAutomorphisms(scip, SCIPgetSymgraphSymtype(G1), &sassygraph, nnodes, 0,
438  &perms, &nperms, &nmaxperms, &log10groupsize, FALSE, &symcodetime) );
439 
440  /* since G1 and G2 are connected and disjoint, they are isomorphic iff there is a permutation
441  * mapping a node from G1 to a node of G2
442  */
443  success = FALSE;
444  for (int p = 0; p < nperms && ! success; ++p)
445  {
446  for (int i = 0; i < nnodesfromG1; ++i)
447  {
448  if ( perms[p][i] >= nnodesfromG1 )
449  {
450  success = TRUE;
451  break;
452  }
453  }
454  }
455 
456  for (int p = 0; p < nperms; ++p)
457  {
458  SCIPfreeBlockMemoryArray(scip, &perms[p], nnodes);
459  }
460  SCIPfreeBlockMemoryArrayNull(scip, &perms, nmaxperms);
461 
462  return success;
463 }
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
#define NULL
Definition: def.h:267
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
public methods for memory management
#define SCIP_MAXSTRLEN
Definition: def.h:288
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
methods to build sassy graph for symmetry detection
private functions to work with algebraic expressions
#define FALSE
Definition: def.h:94
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
static SCIP_RETCODE computeAutomorphisms(SCIP *scip, SYM_SYMTYPE symtype, sassy::static_graph *G, int nsymvars, int maxgenerators, int ***perms, int *nperms, int *nmaxperms, SCIP_Real *log10groupsize, SCIP_Bool restricttovars, SCIP_Real *symcodetime)
variable expression handler
interface for symmetry computations
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
SCIP_Bool SYMcanComputeSymmetry(void)
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
methods for dealing with symmetry detection graphs
const char * SYMsymmetryGetName(void)
power and signed power expression handlers
#define SCIP_CALL(x)
Definition: def.h:380
#define XSTR(x)
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
#define SCIP_Bool
Definition: def.h:91
constraint handler for nonlinear constraints specified by algebraic expressions
SCIP_RETCODE SYMbuildSassyGraphCheck(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *G1, SYM_GRAPH *G2, int *nnodes, int *nnodesfromG1, SCIP_Bool *success)
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
Constraint handler for linear constraints in their most general form, .
SCIP_RETCODE SYMbuildSassyGraph(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *graph, SCIP_Bool *success)
#define SCIP_Real
Definition: def.h:173
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
sum expression handler
static void sassyhook(void *user_param, int n, const int *aut, int nsupp, const int *suppa)
const char * SYMsymmetryGetDesc(void)
#define nnodes
Definition: gastrans.c:74
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *graph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
#define SCIP_CALL_ABORT(x)
Definition: def.h:359
const char * SYMsymmetryGetAddDesc(void)
const char * SYMsymmetryGetAddName(void)