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}*/
98static
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 */
189const 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 */
199const 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 */
208const 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 */
214const char* SYMsymmetryGetAddDesc(void)
215{
216 return "Symmetry preprocessor by Markus Anders (github.com/markusa4/sassy)";
217}
218
219/** computes autormorphisms of a graph */
220static
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 */
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 {
459 }
461
462 return success;
463}
SCIP_RETCODE SYMbuildSassyGraph(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *graph, SCIP_Bool *success)
SCIP_RETCODE SYMbuildSassyGraphCheck(SCIP *scip, sassy::static_graph *sassygraph, SYM_GRAPH *G1, SYM_GRAPH *G2, int *nnodes, int *nnodesfromG1, SCIP_Bool *success)
methods to build sassy graph for symmetry detection
interface for symmetry computations
SCIP_Bool SYMcheckGraphsAreIdentical(SCIP *scip, SYM_SYMTYPE symtype, SYM_GRAPH *G1, SYM_GRAPH *G2)
const char * SYMsymmetryGetName(void)
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)
const char * SYMsymmetryGetAddName(void)
SCIP_RETCODE SYMcomputeSymmetryGenerators(SCIP *scip, int maxgenerators, SYM_GRAPH *graph, int *nperms, int *nmaxperms, int ***perms, SCIP_Real *log10groupsize, SCIP_Real *symcodetime)
SCIP_Bool SYMcanComputeSymmetry(void)
const char * SYMsymmetryGetDesc(void)
static void sassyhook(void *user_param, int n, const int *aut, int nsupp, const int *suppa)
#define XSTR(x)
const char * SYMsymmetryGetAddDesc(void)
Constraint handler for linear constraints in their most general form, .
constraint handler for nonlinear constraints specified by algebraic expressions
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define SCIP_CALL_ABORT(x)
Definition: def.h:353
#define SCIP_CALL(x)
Definition: def.h:374
private functions to work with algebraic expressions
power and signed power expression handlers
sum expression handler
variable expression handler
#define nnodes
Definition: gastrans.c:74
const char * SCIPgetProbName(SCIP *scip)
Definition: scip_prob.c:1067
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
Definition: scip_mem.h:99
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SYM_SYMTYPE SCIPgetSymgraphSymtype(SYM_GRAPH *graph)
int SCIPgetSymgraphNVars(SYM_GRAPH *graph)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
Definition: scip_timing.c:378
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
public methods for memory management
methods for dealing with symmetry detection graphs
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
enum SYM_Symtype SYM_SYMTYPE
Definition: type_symmetry.h:64
@ SYM_SYMTYPE_SIGNPERM
Definition: type_symmetry.h:62
@ SYM_SYMTYPE_PERM
Definition: type_symmetry.h:61