Scippy

GCG

Branch-and-Price & Column Generation for Everyone

bliss_automorph.cpp
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program */
4 /* GCG --- Generic Column Generation */
5 /* a Dantzig-Wolfe decomposition based extension */
6 /* of the branch-cut-and-price framework */
7 /* SCIP --- Solving Constraint Integer Programs */
8 /* */
9 /* Copyright (C) 2010-2021 Operations Research, RWTH Aachen University */
10 /* Zuse Institute Berlin (ZIB) */
11 /* */
12 /* This program is free software; you can redistribute it and/or */
13 /* modify it under the terms of the GNU Lesser General Public License */
14 /* as published by the Free Software Foundation; either version 3 */
15 /* of the License, or (at your option) any later version. */
16 /* */
17 /* This program is distributed in the hope that it will be useful, */
18 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
19 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
20 /* GNU Lesser General Public License for more details. */
21 /* */
22 /* You should have received a copy of the GNU Lesser General Public License */
23 /* along with this program; if not, write to the Free Software */
24 /* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.*/
25 /* */
26 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
27 
28 /**@file bliss_automorph.cpp
29  * @brief automorphism recognition of SCIPs
30  * @author Daniel Peters
31  * @author Martin Bergner
32  * @author Jonas Witt
33  * @author Michael Bastubbe
34  *
35  */
36 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
39 /* #define SCIP_DEBUG */
40 #include "bliss/graph.hh"
41 #include "bliss_automorph.h"
42 #include "scip_misc.h"
43 #include "scip/scip.h"
44 #include "gcg.h"
45 #include "scip/cons_linear.h"
46 #include "pub_bliss.h"
47 #include "class_partialdecomp.h"
48 #include "class_detprobdata.h"
49 #include "cons_decomp.hpp"
50 
51 #include <cstring>
52 
53 /** saves information of the permutation */
54 struct AUT_HOOK2
55 {
56  SCIP_Bool aut; /**< true if there is an automorphism */
57  unsigned int n; /**< number of permutations */
58  SCIP_HASHMAP* varmap; /**< hashmap for permutated variables */
59  SCIP_HASHMAP* consmap; /**< hashmap for permutated constraints */
60  SCIP** scips; /**< array of scips to search for automorphisms */
61  int* nodemap; /**< mapping of the nodes; filled generator-wise */
62  int* conssperm; /**< mapping of constraints */
63  gcg::DETPROBDATA* detprobdata; /**< problem information the automorphism should be searched for */
64  gcg::PARTIALDECOMP* partialdec; /**< decomposition information */
65  std::vector<int>* blocks; /**< array of blocks the automporphisms are searched for */
66  SCIP* scip;
67  int ncalls;
68 
69 
70  /** constructor for the hook struct*/
71  AUT_HOOK2(
72  SCIP_HASHMAP* varmap, /**< hashmap for permutated variables */
73  SCIP_HASHMAP* consmap, /**< hashmap for permutated constraints */
74  SCIP_Bool aut, /**< true if there is an automorphism */
75  unsigned int n, /**< number of permutations */
76  SCIP** scips /**< array of scips to search for automorphisms */
77  );
78 
79  /** destructor for hook struct */
80  ~AUT_HOOK2();
81 
82 
83  /** getter for the bool aut */
84  SCIP_Bool getBool();
85 
86  /** setter for the bool aut */
87  void setBool(SCIP_Bool aut);
88 
89  /** setter for new detection stuff */
93  std::vector<int>* blocks
94  );
95 
96  /** getter for the number of nodes */
97  unsigned int getNNodes();
98 
99  /** getter for the variables hashmap */
100  SCIP_HASHMAP* getVarHash();
101 
102  /** getter for the constraints hashmap */
103  SCIP_HASHMAP* getConsHash();
104 
105  /** getter for the SCIPs */
106  SCIP** getScips();
107 
108 
109 };
110 
111 
112 void AUT_HOOK2::setBool( SCIP_Bool aut_ )
113 {
114  aut = aut_;
115 }
116 
117 
119  gcg::DETPROBDATA* givendetprobdata,
120  gcg::PARTIALDECOMP* givenpartialdec,
121  std::vector<int>* givenblocks
122  )
123 {
124  this->detprobdata = givendetprobdata;
125  this->partialdec = givenpartialdec;
126  this->blocks = givenblocks;
127 
128  SCIP_CALL_ABORT( SCIPallocMemoryArray(givenscip, &(this->conssperm), detprobdata->getNConss() ) ); /*lint !e666*/
129 
130  scip = givendetprobdata->getScip();
131 
132 }
133 
135 { /*lint -esym(1540,struct_hook::conssperm) */
136  SCIPfreeMemoryArrayNull(scip, &nodemap);
137  if( conssperm != NULL )
138  SCIPfreeMemoryArrayNull(scip, &conssperm);
139  conssperm = NULL;
140  detprobdata = NULL;
141  partialdec = NULL;
142 }
143 
144 
145 
147 {
148  return aut;
149 }
150 
151 unsigned int AUT_HOOK2::getNNodes()
152 {
153  return n;
154 }
155 
156 SCIP_HASHMAP* AUT_HOOK2::getVarHash()
157 {
158  return varmap;
159 }
160 
161 SCIP_HASHMAP* AUT_HOOK2::getConsHash()
162 {
163  return consmap;
164 }
165 
167 {
168  return scips;
169 }
170 
171 /** constructor of the hook struct */
173  SCIP_HASHMAP* varmap_, /**< hashmap of permutated variables */
174  SCIP_HASHMAP* consmap_, /**< hahsmap of permutated constraints */
175  SCIP_Bool aut_, /**< true if there is an automorphism */
176  unsigned int n_, /**< number of permutations */
177  SCIP** scips_ /**< array of scips to search for automorphisms */
178  )
179 {
180  size_t i;
181  aut = aut_;
182  n = n_;
183  consmap = consmap_;
184  varmap = varmap_;
185  scips = scips_;
186  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &nodemap, n_) ); /*lint !e666*/
187  for (i = 0; i < n_; ++i)
188  nodemap[i] = -1;
189 
190  conssperm = NULL;
191  detprobdata = NULL;
192  partialdec = NULL;
193  blocks = NULL;
194 
195  ncalls = 0;
196 }
197 
198 /** hook function to save the permutation of the graph; fhook() is called by metis for every generator,
199  * AUT_HOOK* hook stores a combined mapping in nodemapping that is filled generator-wise */
200 static
201 void fhook(
202  void* user_param, /**< data structure to save hashmaps with permutation */
203  unsigned int N, /**< number of permutations */
204  const unsigned int* aut /**< array of permutations */
205  )
206 { /*lint -e715*/
207 
208  unsigned int i;
209  unsigned int j;
210  unsigned int n;
211  int nvars;
212  int nconss;
213  SCIP_VAR** vars1;
214  SCIP_VAR** vars2;
215  SCIP_CONS** conss1;
216  SCIP_CONS** conss2;
217  SCIP_Bool newdetection;
218  SCIP* partialdecscip;
219  gcg::DETPROBDATA* detprobdata;
220  gcg::PARTIALDECOMP* partialdec;
221  AUT_HOOK2* hook = (AUT_HOOK2*) user_param;
222 
223  j = 0;
224  n = hook->getNNodes();
225 
226  /* new detection stuff */
227  newdetection = (hook->detprobdata != NULL) ;
228  partialdec = hook->partialdec;
229  detprobdata = hook->detprobdata;
230  partialdecscip = NULL;
231 
232  if(hook->getBool())
233  return;
234 
235  ++hook->ncalls;
236 
237  if( hook->ncalls > 100 )
238  {
239  hook->setBool(false);
240  return;
241  }
242 
243  // SCIPdebugMessage("Looking for a permutation from [0,%u] bijective to [%u:%u] (N=%u) \n", n/2-1, n/2, n-1, N);
244  for( i = 0; i < n / 2; i++ )
245  {
246  assert(aut[i] < INT_MAX);
247 
248  if( (aut[i]) >= n / 2 && hook->nodemap[i] == -1 )
249  {
250  assert(aut[i] < n);
251 // SCIPdebugMessage("current generator: %u -> %u\n", i, aut[i]);
252  hook->nodemap[i] = aut[i];
253  }
254  }
255 
256  for( i = 0; i < n / 2; i++ )
257  {
258 // SCIPdebugMessage("general mapping : %u -> %u\n", i, hook->nodemap[i]);
259  if( hook->nodemap[i] >= (int) n / 2 )
260  ++j;
261  }
262 
263  if( j == n / 2 )
264  {
265  hook->setBool(TRUE);
266  }
267 
268  for( i = n; i < N; ++i )
269  {
270  if( aut[i] != i )
271  {
272  // SCIPdebugMessage("Master %u -> %u not the identity, no decomposition possible!\n", i, aut[i]);
273  hook->setBool(false);
274  break;
275  }
276  }
277 
278 // SCIPdebugMessage("Permutation %s found.\n", hook->getBool() ? "":"not");
279 // SCIPdebugMessage("j = %u\n", j);
280 
281  if( !hook->getBool() )
282  return;
283 
284 
285  if( newdetection )
286  nvars = partialdec->getNVarsForBlock((*hook->blocks)[0]);
287  else
288  nvars = SCIPgetNVars(hook->getScips()[0]);
289  if( newdetection )
290  assert(nvars == partialdec->getNVarsForBlock((*hook->blocks)[1]) );
291  else
292  assert(nvars == SCIPgetNVars(hook->getScips()[1]));
293 
294  if( newdetection )
295  {
296  partialdecscip = detprobdata->getScip();
297 
298  SCIP_CALL_ABORT(SCIPallocBufferArray(partialdecscip, &vars1, nvars ));
299  SCIP_CALL_ABORT(SCIPallocBufferArray(partialdecscip, &vars2, nvars ));
300  nconss = partialdec->getNConssForBlock((*hook->blocks)[0]);
301  assert(nconss == partialdec->getNConssForBlock((*hook->blocks)[1]));
302 
303  SCIP_CALL_ABORT( SCIPallocBufferArray(partialdecscip, &conss1, nconss ) );
304  SCIP_CALL_ABORT( SCIPallocBufferArray(partialdecscip, &conss2, nconss ) );
305 
306  for( int v = 0; v < nvars; ++v )
307  {
308  vars1[v] = detprobdata->getVar(partialdec->getVarsForBlock((*hook->blocks)[0])[v]);
309  vars2[v] = detprobdata->getVar(partialdec->getVarsForBlock((*hook->blocks)[1])[v]);
310  }
311 
312  for( int c = 0; c < nconss; ++c )
313  {
314  conss1[c] = detprobdata->getCons(partialdec->getConssForBlock((*hook->blocks)[0])[c]);
315  conss2[c] = detprobdata->getCons(partialdec->getConssForBlock((*hook->blocks)[1])[c]);
316  }
317  }
318  else
319  {
320  vars1 = SCIPgetVars(hook->getScips()[0]);
321  vars2 = SCIPgetVars(hook->getScips()[1]);
322  nconss = SCIPgetNConss(hook->getScips()[0]);
323  assert(nconss == SCIPgetNConss(hook->getScips()[1]));
324 
325  conss1 = SCIPgetConss(hook->getScips()[0]);
326  conss2 = SCIPgetConss(hook->getScips()[1]);
327  }
328 
329  for( i = 0; i < (unsigned int) nvars+nconss; i++ )
330  {
331  /* Assuming the following layout:
332  * 0 ... nconss-1 = vertex ids for constraints
333  * nconss ... nconss+nvars-1 = vertex ids for variables
334  * nconss+nvars ... n-1 = nonzero entries (not relevant)
335  */
336  if( i < (unsigned int) nconss )
337  {
338  unsigned int consindex = i;
339  unsigned int consindex2 = hook->nodemap[i]-n/2;
340  assert( consindex2 < (unsigned int) nconss);
341  SCIP_CONS* cons1 = conss1[consindex];
342  SCIP_CONS* cons2 = conss2[consindex2];
343  SCIP_CALL_ABORT( SCIPhashmapInsert(hook->getConsHash(), cons2, cons1) );
344  SCIPdebugMessage("cons <%s> <-> cons <%s>\n", SCIPconsGetName(cons2), SCIPconsGetName(cons1));
345  }
346  else if( i < (unsigned int) nvars+nconss )
347  {
348  unsigned int varindex = i-nconss;
349  unsigned int varindex2 = hook->nodemap[i]-nconss-n/2;
350  assert( varindex2 < (unsigned int) nvars);
351  SCIP_VAR* var1 = vars1[varindex];
352  SCIP_VAR* var2 = vars2[varindex2];
353  SCIP_CALL_ABORT( SCIPhashmapInsert(hook->getVarHash(), var2, var1) );
354  SCIPdebugMessage("var <%s> <-> var <%s>\n", SCIPvarGetName(var2), SCIPvarGetName(var1));
355  }
356  }
357 
358  if( newdetection )
359  {
360  partialdecscip = detprobdata->getScip();
361  SCIPfreeBufferArray(partialdecscip, &conss1);
362  SCIPfreeBufferArray(partialdecscip, &conss2);
363  SCIPfreeBufferArray(partialdecscip, &vars1);
364  SCIPfreeBufferArray(partialdecscip, &vars2);
365  }
366 }
367 
368 
369 /** tests if two scips have the same number of variables */
370 static
371 SCIP_RETCODE testScipVars(
372  SCIP* scip1, /**< first SCIP data structure */
373  SCIP* scip2, /**< second SCIP data structure */
374  SCIP_RESULT* result /**< result pointer to indicate success or failure */
375  )
376 {
377  if(SCIPgetNVars(scip1) != SCIPgetNVars(scip2))
378  {
379  *result = SCIP_DIDNOTFIND;
380  }
381  return SCIP_OKAY;
382 }
383 
384 
385 /** tests if two scips have the same number of constraints */
386 static
387 SCIP_RETCODE testScipCons(
388  SCIP* scip1, /**< first SCIP data structure */
389  SCIP* scip2, /**< second SCIP data structure */
390  SCIP_RESULT* result /**< result pointer to indicate success or failure */
391  )
392 {
393  if(SCIPgetNConss(scip1) != SCIPgetNConss(scip2))
394  {
395  *result = SCIP_DIDNOTFIND;
396  }
397  return SCIP_OKAY;
398 }
399 
400 
401 /** constructor for colorinfo arrays */
402 static SCIP_RETCODE allocMemory(
403  SCIP* scip, /**< SCIP data structure */
404  AUT_COLOR* colorinfo, /**< struct to save intermediate information */
405  int nconss, /**< number of constraints */
406  int nvars /**< number of variables */
407  )
408 {
409  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarraycoefs, ((size_t) nconss * nvars)));
410  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarrayvars, (size_t) nvars));
411  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarrayconss, (size_t) nconss));
412  colorinfo->alloccoefsarray = nconss * nvars;
413  return SCIP_OKAY;
414 }
415 
416 /** constructor for colorinfo arrays */
417 static SCIP_RETCODE allocMemoryNewDetection(
418  SCIP* scip, /**< SCIP data structure */
419  gcg::DETPROBDATA* detprobdata, /**< SCIP data structure */
420  AUT_COLOR* colorinfo, /**< struct to save intermediate information */
421  int nconss, /**< number of constraints */
422  int nvars, /**< number of variables */
423  int ncoeffs /**< number of coefficients */
424  )
425 {
426  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarraycoefs, ((size_t) ncoeffs )));
427  colorinfo->alloccoefsarray = ncoeffs;
428  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarrayvars, (size_t) nvars));
429  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarrayconss, (size_t) nconss));
430  return SCIP_OKAY;
431 }
432 
433 
434 
435 /** reallocate colorinfo arrays with new size */
436 static SCIP_RETCODE reallocMemory(
437  SCIP* scip, /**< problem information */
438  AUT_COLOR* colorinfo, /**< struct to save intermediate information */
439  int nconss, /**< number of constraints */
440  int nvars /**< number of variables */
441  )
442 {
443  SCIP_CALL(SCIPreallocMemoryArray(scip, &colorinfo->ptrarraycoefs, (size_t) colorinfo->lencoefsarray + ((size_t) nconss * nvars)));
444  colorinfo->alloccoefsarray = colorinfo->lencoefsarray + nconss * nvars;
445  SCIP_CALL( SCIPreallocMemoryArray(scip, &colorinfo->ptrarrayvars, (size_t) colorinfo->lenvarsarray + nvars));
446  SCIP_CALL( SCIPreallocMemoryArray(scip, &colorinfo->ptrarrayconss, (size_t) colorinfo->lenconssarray + nconss));
447  return SCIP_OKAY;
448 }
449 
450 
451 /** destructor for colorinfoarrays */
452 static
453 SCIP_RETCODE freeMemory(
454  SCIP* scip, /**< SCIP data structure */
455  AUT_COLOR* colorinfo /**< struct to save intermediate information */
456  )
457 {
458  int i;
459 
460  for(i = 0; i < colorinfo->lenvarsarray; i++ ){
461  AUT_VAR* svar = (AUT_VAR*) colorinfo->ptrarrayvars[i];
462  delete svar;
463  }
464  for(i = 0; i < colorinfo->lenconssarray; i++ ){
465  AUT_CONS* scons = (AUT_CONS*) colorinfo->ptrarrayconss[i];
466  delete scons;
467  }
468  for(i = 0; i < colorinfo->lencoefsarray; i++ ){
469  AUT_COEF* scoef = (AUT_COEF*) colorinfo->ptrarraycoefs[i];
470  delete scoef;
471  }
472 
473  SCIPfreeMemoryArray(scip, &colorinfo->ptrarraycoefs);
474  SCIPfreeMemoryArray(scip, &colorinfo->ptrarrayconss);
475  SCIPfreeMemoryArray(scip, &colorinfo->ptrarrayvars);
476  return SCIP_OKAY;
477 }
478 
479 /** set up a help structure for graph creation */
480 static
481 SCIP_RETCODE setuparrays(
482  SCIP* origscip, /**< SCIP data structure */
483  SCIP** scips, /**< SCIPs to compare */
484  int nscips, /**< number of SCIPs */
485  AUT_COLOR* colorinfo, /**< data structure to save intermediate data */
486  SCIP_RESULT* result /**< result pointer to indicate success or failure */
487  )
488 { /*lint -esym(593, scoef) */
489  int i;
490  int j;
491  int s;
492  int ncurvars;
493  int nconss;
494  int nvars;
495  SCIP_Bool added;
496 
497  added = FALSE;
498 
499  //allocate max n of coefarray, varsarray, and boundsarray in origscip
500  nconss = SCIPgetNConss(scips[0]);
501  nvars = SCIPgetNVars(scips[0]);
502  SCIP_CALL( allocMemory(origscip, colorinfo, nconss, nvars) );
503  colorinfo->setOnlySign(FALSE);
504 
505  for( s = 0; s < nscips && *result == SCIP_SUCCESS; ++s )
506  {
507  SCIP *scip = scips[s];
508  SCIP_CONS** conss = SCIPgetConss(scip);
509  SCIP_VAR** vars = SCIPgetVars(scip);
510  SCIPdebugMessage("Handling SCIP %i (%d x %d)\n", s, nconss, nvars);
511  //save the properties of variables in a struct array and in a sorted pointer array
512  for( i = 0; i < nvars; i++ )
513  {
514  AUT_VAR* svar = new AUT_VAR(scip, vars[i]);
515  //add to pointer array iff it doesn't exist
516  SCIP_CALL( colorinfo->insert(svar, &added) );
517  if( s > 0 && added)
518  {
519  *result = SCIP_DIDNOTFIND;
520  break;
521  }
522  //otherwise free allocated memory
523  if( !added )
524  delete svar;
525  }
526  //save the properties of constraints in a struct array and in a sorted pointer array
527  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
528  {
529  SCIP_Real* curvals = NULL;
530  ncurvars = GCGconsGetNVars(scip, conss[i]); //SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(origscip), SCIPgetNVars(scip1)+1) );
531  if( ncurvars == 0 )
532  continue;
533  AUT_CONS* scons = new AUT_CONS(scip, conss[i]);
534  //add to pointer array iff it doesn't exist
535  SCIP_CALL( colorinfo->insert(scons, &added) );
536  if( s > 0 && added)
537  {
538  *result = SCIP_DIDNOTFIND;
539  break;
540  }
541  //otherwise free allocated memory
542  if( !added )
543  delete scons;
544 
545  SCIP_CALL( SCIPallocBufferArray(origscip, &curvals, ncurvars));
546  SCIP_CALL( GCGconsGetVals(scip, conss[i], curvals, ncurvars) );
547  //save the properties of variables of the constraints in a struct array and in a sorted pointer array
548  for( j = 0; j < ncurvars; j++ )
549  {
550  AUT_COEF* scoef = new AUT_COEF(scip, curvals[j] );
551  //test, whether the coefficient is not zero
552  if( !SCIPisZero(scip, scoef->getVal()) )
553  {
554  //add to pointer array iff it doesn't exist
555  SCIP_CALL( colorinfo->insert(scoef, &added) );
556  if( s > 0 && added)
557  {
558  *result = SCIP_DIDNOTFIND;
559  break;
560  }
561  }
562  //otherwise free allocated memory
563  if( !added )
564  delete scoef;
565  }
566  SCIPfreeBufferArray(origscip, &curvals);
567  }
568  //size of the next instance, in order to allocate memory
569  if( s < nscips - 1 )
570  {
571  nconss = SCIPgetNConss(scips[(size_t)s + 1]);
572  nvars = SCIPgetNVars(scips[(size_t)s + 1]);
573  }
574  //set zero, if no next instance exists
575  else
576  {
577  nconss = 0;
578  nvars = 0;
579  }
580  //reallocate memory with size of ptrarray[bounds, vars, coefs] + max of scip[i+1]
581  SCIP_CALL( reallocMemory(origscip, colorinfo, nconss, nvars) );
582  }
583 
584  /* add color information for master constraints */
585  SCIP_CONS** origmasterconss = GCGgetOrigMasterConss(origscip);
586  int nmasterconss = GCGgetNMasterConss(origscip);
587 
588  SCIP_CALL( reallocMemory(origscip, colorinfo, nmasterconss, SCIPgetNVars(origscip)) );
589 
590  for( i = 0; i < nmasterconss && *result == SCIP_SUCCESS; ++i )
591  {
592  SCIP_CONS* mastercons = origmasterconss[i];
593  ncurvars = GCGconsGetNVars(origscip, mastercons);
594  SCIP_Real* curvals;
595  SCIP_CALL( SCIPallocBufferArray(origscip, &curvals, ncurvars) );
596  GCGconsGetVals(origscip, mastercons, curvals, ncurvars);
597 
598  /* add right color for master constraint */
599  AUT_CONS* scons = new AUT_CONS(origscip, mastercons);
600  SCIP_CALL( colorinfo->insert(scons, &added) );
601 
602  /* if it hasn't been added, it is already present */
603  if(!added)
604  delete scons;
605 
606  for( j = 0; j < ncurvars; ++j )
607  {
608  AUT_COEF* scoef = new AUT_COEF(origscip, curvals[j] );
609 
610  added = FALSE;
611 
612  if( !SCIPisZero(origscip, scoef->getVal()) )
613  {
614  SCIP_CALL( colorinfo->insert(scoef, &added) );
615  }
616 
617  if( !added )
618  delete scoef;
619  }
620  SCIPfreeBufferArray(origscip, &curvals);
621  }
622 
623  return SCIP_OKAY;
624 }
625 
626 
627 /** set up a help structure for graph creation for new detection loop*/
628 static
630  SCIP* scip, /**< SCIP data structure */
631  gcg::DETPROBDATA* detprobdata, /**< detprobdata corresponing to presolved or unpresolved problem */
632  gcg::PARTIALDECOMP* partialdec, /**< partial decomp the symmetry for two blocks is checked for */
633  int nblocks, /**< number of blocks the symmetry should be checked for */
634  std::vector<int> blocks, /**< vectors of block indices the symmetry be checked for */
635  AUT_COLOR* colorinfo, /**< data structure to save intermediate data */
636  SCIP_RESULT* result /**< result pointer to indicate success or failure */
637  )
638 { /*lint -esym(593, scoef) */
639  int i;
640  int j;
641  int b;
642  int nconss;
643  int nvars;
644  SCIP_Bool added;
645 
646  added = FALSE;
647 
648  //allocate max n of coefarray, varsarray, and boundsarray in origscip
649  nconss = partialdec->getNConssForBlock(blocks[0]) ;
650  nvars = partialdec->getNVarsForBlock(blocks[0]) ;
651  colorinfo->setOnlySign(FALSE);
652 
653  for( b = 0; b < nblocks && *result == SCIP_SUCCESS; ++b )
654  {
655  int block = blocks[b];
656 
657  assert( partialdec->getNVarsForBlock(blocks[b]) == nvars );
658  assert( partialdec->getNConssForBlock(blocks[b]) == nconss );
659 
660  SCIPdebugMessage("Handling block %i (id %d %d x %d)\n", b, block, partialdec->getNConssForBlock(blocks[b]), partialdec->getNVarsForBlock(blocks[b]));
661  //save the properties of variables in a struct array and in a sorted pointer array
662  for( i = 0; i < nvars; i++ )
663  {
664  SCIP_VAR* var;
665  AUT_VAR* svar;
666 
667  var = detprobdata->getVar(partialdec->getVarsForBlock(block)[i]);
668  svar = new AUT_VAR(scip, var);
669  //add to pointer array iff it doesn't exist
670  SCIP_CALL( colorinfo->insert(svar, &added) );
671  if( b > 0 && added)
672  {
673  *result = SCIP_DIDNOTFIND;
674  break;
675  }
676  //otherwise free allocated memory
677  if( !added )
678  delete svar;
679  }
680  //save the properties of constraints in a struct array and in a sorted pointer array
681  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
682  {
683  int consid;
684  SCIP_CONS* cons;
685 
686  consid = partialdec->getConssForBlock(block)[i];
687  cons = detprobdata->getCons(consid);
688 
689  if( detprobdata->getNVarsForCons(consid) == 0 )
690  continue;
691 
692  AUT_CONS* scons = new AUT_CONS(scip, cons);
693  //add to pointer array iff it doesn't exist
694  SCIP_CALL( colorinfo->insert(scons, &added) );
695  if( b > 0 && added)
696  {
697  *result = SCIP_DIDNOTFIND;
698  break;
699  }
700  //otherwise free allocated memory
701  if( !added )
702  delete scons;
703 
704  //save the properties of variables of the constraints in a struct array and in a sorted pointer array
705  for( j = 0; j < detprobdata->getNVarsForCons(consid); j++ )
706  {
707  SCIP_Real val;
708  AUT_COEF* scoef;
709  val = detprobdata->getVal(consid, detprobdata->getVarsForCons(consid)[j]);
710  scoef = new AUT_COEF(scip, val );
711  //test, whether the coefficient is not zero
712  if( !SCIPisZero(scip, scoef->getVal()) )
713  {
714  //add to pointer array iff it doesn't exist
715  SCIP_CALL( colorinfo->insert(scoef, &added) );
716  if( b > 0 && added)
717  {
718  *result = SCIP_DIDNOTFIND;
719  break;
720  }
721  }
722  //otherwise free allocated memory
723  if( !added )
724  delete scoef;
725  }
726  }
727  }
728 
729  /* add color information for master constraints */
730  for( i = 0; i < partialdec->getNMasterconss() && *result == SCIP_SUCCESS; ++i )
731  {
732  int masterconsid;
733  SCIP_CONS* mastercons;
734 
735  masterconsid = partialdec->getMasterconss()[i];
736  mastercons = detprobdata->getCons(masterconsid);
737 
738  /* add right color for master constraint */
739  AUT_CONS* scons = new AUT_CONS(scip, mastercons);
740  SCIP_CALL( colorinfo->insert(scons, &added) );
741 
742  /* if it hasn't been added, it is already present */
743  if(!added)
744  delete scons;
745 
746  for( j = 0; j < detprobdata->getNVarsForCons(masterconsid); ++j )
747  {
748  AUT_COEF* scoef;
749  int varid;
750 
751  varid = detprobdata->getVarsForCons(masterconsid)[j];
752  scoef= new AUT_COEF(scip, detprobdata->getVal(masterconsid, varid) );
753 
754  added = FALSE;
755 
756  if( !SCIPisZero(scip, scoef->getVal()) )
757  {
758  SCIP_CALL( colorinfo->insert(scoef, &added) );
759  }
760 
761  if( !added )
762  delete scoef;
763  }
764  }
765 
766  return SCIP_OKAY;
767 }
768 
769 
770 /** create a graph out of an array of scips */
771 static
772 SCIP_RETCODE createGraph(
773  SCIP* origscip, /**< SCIP data structure */
774  SCIP** scips, /**< SCIPs to compare */
775  int nscips, /**< number of SCIPs */
776  int* pricingindices, /**< indices of the given pricing problems */
777  AUT_COLOR colorinfo, /**< data structure to save coloring information for conss, vars, and coeffs*/
778  bliss::Graph* graph, /**< graph needed for discovering isomorphism */
779  int* pricingnodes, /**< number of pricing nodes without master */
780  SCIP_RESULT* result /**< result pointer to indicate success or failure */
781  )
782 {
783  int i;
784  int j;
785  int s;
786  int ncurvars;
787  int curvar;
788  int* nnodesoffset = NULL;
789  int color;
790 
791  SCIP_VAR** curvars = NULL;
792  SCIP_Real* curvals = NULL;
793 
794  int nnodes = 0;
795  //building the graph out of the arrays
796  bliss::Graph* h = graph;
797 
798  int* pricingnonzeros = NULL;
799  int* mastercoefindex = NULL;
800  SCIP_CALL( SCIPallocBufferArray(origscip, &pricingnonzeros, nscips) );
801  SCIP_CALL( SCIPallocBufferArray(origscip, &nnodesoffset, nscips) );
802  SCIP_CALL( SCIPallocBufferArray(origscip, &mastercoefindex, nscips) );
803  BMSclearMemoryArray(pricingnonzeros, nscips);
804  BMSclearMemoryArray(nnodesoffset, nscips);
805  BMSclearMemoryArray(mastercoefindex, nscips);
806 
807  SCIP_CONS** origmasterconss = GCGgetOrigMasterConss(origscip);
808  int nmasterconss = GCGgetNMasterConss(origscip);
809 
810  for( s = 0; s < nscips && *result == SCIP_SUCCESS; ++s)
811  {
812  SCIPdebugMessage("Pricing problem %d\n", pricingindices[s]);
813  SCIP *scip = scips[s];
814  int nconss = SCIPgetNConss(scip);
815  int nvars = SCIPgetNVars(scip);
816  SCIP_CONS** conss = SCIPgetConss(scip);
817  SCIP_VAR** vars = SCIPgetVars(scip);
818 
819  int z = 0;
820 
821  nnodesoffset[s] = nnodes;
822 
823  //add a node for every constraint
824  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
825  {
826  ncurvars = GCGconsGetNVars(scip, conss[i]);
827  if( ncurvars == 0 )
828  continue;
829 
830  color = colorinfo.get( AUT_CONS(scip, conss[i]) );
831 
832  if(color == -1) {
833  *result = SCIP_DIDNOTFIND;
834  break;
835  }
836 
837  SCIPdebugMessage("cons <%s> color %d\n", SCIPconsGetName(conss[i]), color);
838  (void) h->add_vertex((unsigned int)color);
839  nnodes++;
840  }
841  //add a node for every variable
842  for( i = 0; i < nvars && *result == SCIP_SUCCESS; i++ )
843  {
844  color = colorinfo.get( AUT_VAR(scip, vars[i]) );
845 
846  if(color == -1) {
847  *result = SCIP_DIDNOTFIND;
848  break;
849  }
850  SCIPdebugMessage("var <%s> color %d\n", SCIPvarGetName(vars[i]), color);
851 
852  (void) h->add_vertex((unsigned int) colorinfo.getLenCons() + color);
853  nnodes++;
854  }
855  //connecting the nodes with an additional node in the middle
856  //it is necessary, since only nodes have colors
857  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
858  {
859  int conscolor = colorinfo.get(AUT_CONS(scip, conss[i]));
860  ncurvars = GCGconsGetNVars(scip, conss[i]);
861  if( ncurvars == 0 )
862  continue;
863  SCIP_CALL( SCIPallocBufferArray(origscip, &curvars, ncurvars) );
864  SCIP_CALL( GCGconsGetVars(scip, conss[i], curvars, ncurvars) );
865  SCIP_CALL( SCIPallocBufferArray(origscip, &curvals, ncurvars) );
866  SCIP_CALL( GCGconsGetVals(scip, conss[i], curvals, ncurvars) );
867  for( j = 0; j < ncurvars; j++ )
868  {
869  int varcolor = colorinfo.get( AUT_VAR(scip, curvars[j] )) + colorinfo.getLenCons(); /*lint !e864 */
870  color = colorinfo.get( AUT_COEF(scip, curvals[j] ));
871  if( color == -1 )
872  {
873  *result = SCIP_DIDNOTFIND;
874  break;
875  }
876  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
877  curvar = SCIPvarGetProbindex(curvars[j]);
878  (void) h->add_vertex((unsigned int) color);
879  nnodes++;
880  h->add_edge((unsigned int) nnodesoffset[s] + i, (unsigned int) nnodesoffset[s] + nconss + nvars + z);
881  h->add_edge((unsigned int) nnodesoffset[s] + nconss + nvars + z, (unsigned int) nnodesoffset[s]+nconss + curvar);
882  SCIPdebugMessage("nz: c <%s> (id: %d, color: %d) -> nz (id: %d) (value: %f, color: %d) -> var <%s> (id: %d, color: %d) \n",
883  SCIPconsGetName(conss[i]),
884  nnodesoffset[s] + i,
885  conscolor,
886  nnodesoffset[s] + nconss + nvars + z,
887  curvals[j],
888  color+colorinfo.getLenCons() + colorinfo.getLenVar(), /*lint !e864 */
889  SCIPvarGetName(curvars[j]),
890  nnodesoffset[s] + nconss + curvar,
891  varcolor);
892  z++;
893  }
894  SCIPfreeBufferArray(origscip, &curvals);
895  SCIPfreeBufferArray(origscip, &curvars);
896  }
897  pricingnonzeros[s] = z;
898 
899  /* add coefficient nodes for nonzeros in the master */
900  for( i = 0; i < nmasterconss && *result == SCIP_SUCCESS; ++i )
901  {
902  SCIP_CONS* mastercons = origmasterconss[i];
903  ncurvars = GCGconsGetNVars(origscip, mastercons);
904  SCIP_CALL( SCIPallocBufferArray(origscip, &curvars, ncurvars) );
905  SCIP_CALL( SCIPallocBufferArray(origscip, &curvals, ncurvars) );
906  GCGconsGetVars(origscip, mastercons, curvars, ncurvars);
907  GCGconsGetVals(origscip, mastercons, curvals, ncurvars);
908  for( j = 0; j < ncurvars; ++j )
909  {
910  if( GCGoriginalVarIsLinking(curvars[j]) )
911  {
912  SCIPdebugMessage("Var <%s> is linking, abort detection.\n", SCIPvarGetName(curvars[j]));
913  *result = SCIP_DIDNOTFIND;
914  return SCIP_OKAY;
915  }
916  int block = GCGvarGetBlock(curvars[j]);
917 
918  /* ignore if the variable belongs to a different block */
919  if( block != pricingindices[s] )
920  {
921  // SCIPdebugMessage("Var <%s> belongs to a different block (%d)\n", SCIPvarGetName(curvars[j]), block);
922  continue;
923  }
924 
925  color = colorinfo.get(AUT_COEF(origscip, curvals[j]));
926  assert(color != -1);
927  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
928 
929  /* add coefficent node for current coeff */
930  (void) h->add_vertex((unsigned int)color);
931  assert(ABS(curvals[j] < SCIPinfinity(scip)));
932  SCIPdebugMessage("master nz for var <%s> (id: %d) (value: %f, color: %d)\n", SCIPvarGetName(curvars[j]), nnodes, curvals[j], color);
933  nnodes++;
934  }
935  SCIPfreeBufferArray(origscip, &curvals);
936  SCIPfreeBufferArray(origscip, &curvars);
937  }
938  SCIPdebugMessage("Iteration %d: nnodes = %d\n", s, nnodes);
939  assert(*result == SCIP_SUCCESS && (unsigned int) nnodes == h->get_nof_vertices());
940  }
941  /* connect the created graphs with nodes for the master problem */
942 
943  SCIPdebugMessage( "handling %d masterconss\n", nmasterconss);
944  *pricingnodes = nnodes;
945 
946  for( i = 0; i < nmasterconss && *result == SCIP_SUCCESS; ++i )
947  {
948  SCIP_CONS* mastercons = origmasterconss[i];
949  ncurvars = GCGconsGetNVars(origscip, mastercons);
950  SCIP_CALL( SCIPallocBufferArray(origscip, &curvars, ncurvars) );
951  SCIP_CALL( SCIPallocBufferArray(origscip, &curvals, ncurvars) );
952  GCGconsGetVars(origscip, mastercons, curvars, ncurvars);
953  GCGconsGetVals(origscip, mastercons, curvals, ncurvars);
954 
955  SCIPdebugMessage("Handling cons <%s>\n", SCIPconsGetName(mastercons));
956 
957  /* create node for masterconss and get right color */
958  int conscolor = colorinfo.get(AUT_CONS(origscip, mastercons));
959  assert(conscolor != -1);
960  (void) h->add_vertex((unsigned int) conscolor);
961  int masterconsnode = nnodes;
962  nnodes++;
963 
964  for( j = 0; j < ncurvars; ++j )
965  {
966  SCIP* pricingscip = NULL;
967  if( GCGoriginalVarIsLinking(curvars[j]) )
968  {
969  SCIPdebugMessage("Var <%s> is linking, abort detection.\n", SCIPvarGetName(curvars[j]));
970  *result = SCIP_DIDNOTFIND;
971  return SCIP_OKAY;
972  }
973  int block = GCGvarGetBlock(curvars[j]);
974  int ind = -1;
975  SCIPdebugMessage("Var <%s> is in block %d\n", SCIPvarGetName(curvars[j]), block);
976  for( s = 0; s < nscips; ++s )
977  {
978  if( block == pricingindices[s])
979  {
980  ind = s;
981  pricingscip = scips[s];
982  break;
983  }
984  }
985 
986  /* ignore if the variable belongs to a different block */
987  if( pricingscip == NULL )
988  {
989  // SCIPdebugMessage("Var <%s> belongs to a different block (%d)\n", SCIPvarGetName(curvars[j]), block);
990  continue;
991  }
992 
993  color = colorinfo.get(AUT_COEF(origscip, curvals[j]));
994  assert(color != -1);
995  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
996  SCIP_VAR* pricingvar = GCGoriginalVarGetPricingVar(curvars[j]);
997 
998  /* get coefficient node for current coefficient */
999  int coefnodeindex = nnodesoffset[ind] + SCIPgetNVars(pricingscip) + SCIPgetNConss(pricingscip) + pricingnonzeros[ind] + mastercoefindex[ind];
1000  ++(mastercoefindex[ind]);
1001 
1002  int varcolor = colorinfo.get(AUT_VAR(pricingscip, pricingvar));
1003  assert(varcolor != -1);
1004  varcolor += colorinfo.getLenCons();
1005 
1006  assert( (uint) masterconsnode < h->get_nof_vertices());
1007  assert( (uint) coefnodeindex < h->get_nof_vertices());
1008  /* master constraint and coefficient */
1009  h->add_edge((unsigned int) masterconsnode, (unsigned int) coefnodeindex);
1010  SCIPdebugMessage("ma: c <%s> (id: %d, color: %d) -> nz (id: %d) (value: <%.6f> , color: %d) -> pricingvar <%s> (id: %d, color: %d)\n",
1011  SCIPconsGetName(mastercons),
1012  masterconsnode, conscolor, coefnodeindex, curvals[j], color, SCIPvarGetName(pricingvar),
1013  nnodesoffset[ind] + SCIPgetNConss(pricingscip) + SCIPvarGetProbindex(pricingvar), varcolor);
1014 
1015  /* get node index for pricing variable and connect masterconss, coeff and pricingvar nodes */
1016  h->add_edge((unsigned int) coefnodeindex, (unsigned int) nnodesoffset[ind] + SCIPgetNConss(pricingscip) + SCIPvarGetProbindex(pricingvar));
1017  }
1018  SCIPfreeBufferArray(origscip, &curvals);
1019  SCIPfreeBufferArray(origscip, &curvars);
1020  }
1021 
1022  //free all allocated memory
1023  SCIPfreeBufferArray(origscip, &mastercoefindex);
1024  SCIPfreeBufferArray(origscip, &nnodesoffset);
1025  SCIPfreeBufferArray(origscip, &pricingnonzeros);
1026 
1027  return SCIP_OKAY;
1028 }
1029 
1030 /** create a graph out of an array of scips */
1031 static
1033  SCIP* scip, /**< SCIP data structure */
1034  gcg::DETPROBDATA* detprobdata, /**< detection process information and data */
1035  gcg::PARTIALDECOMP* partialdec, /**< partial decomposition */
1036  int nblocks, /**< number of blocks the symmetry should be checked for */
1037  std::vector<int> blocks, /**< vectors of block indices the symmetry be checked for */
1038  AUT_COLOR colorinfo, /**< data structure to save intermediate data */
1039  bliss::Graph* graph, /**< graph needed for discovering isomorphism */
1040  int* pricingnodes, /**< number of pricing nodes without master */
1041  SCIP_RESULT* result /**< result pointer to indicate success or failure */
1042  )
1043 {
1044  int i;
1045  int j;
1046  int b;
1047  int ncurvars;
1048  int* nnodesoffset;
1049  int color;
1050  int nconss;
1051  int nvars;
1052  int nnodes;
1053  bliss::Graph* h;
1054  int* pricingnonzeros;
1055  int* mastercoefindex;
1056  std::vector<bool> masterconssrelevant;
1057 
1058  masterconssrelevant = std::vector<bool>(partialdec->getNMasterconss(), false);
1059 
1060  pricingnonzeros = NULL;
1061  mastercoefindex = NULL;
1062  nnodesoffset = NULL;
1063 
1064  nnodes = 0;
1065  //building the graph out of the arrays
1066  h = graph;
1067 
1068  scip = detprobdata->getScip();
1069 
1070  SCIP_CALL( SCIPallocBufferArray(scip, &mastercoefindex, nblocks) );
1071  BMSclearMemoryArray(mastercoefindex, nblocks);
1072 
1073  nconss = partialdec->getNConssForBlock(blocks[0]);
1074  nvars = partialdec->getNVarsForBlock(blocks[0]);
1075 
1076  SCIP_CALL( SCIPallocBufferArray(scip, &nnodesoffset, nblocks) );
1077  BMSclearMemoryArray(nnodesoffset, nblocks);
1078  SCIP_CALL( SCIPallocBufferArray(scip, &pricingnonzeros, nblocks) );
1079  BMSclearMemoryArray(pricingnonzeros, nblocks);
1080 
1081  for( b = 0; b < nblocks && *result == SCIP_SUCCESS; ++b )
1082  {
1083  int block;
1084 
1085  block = blocks[b];
1086  SCIPdebugMessage("Pricing problem %d\n", blocks[b]);
1087  int z;
1088 
1089  z = 0;
1090 
1091  nnodesoffset[b] = nnodes;
1092 
1093  //add a node for every constraint
1094  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
1095  {
1096  int consid;
1097  SCIP_CONS* cons;
1098 
1099  consid = partialdec->getConssForBlock(block)[i];
1100  ncurvars = detprobdata->getNVarsForCons(consid);
1101  cons = detprobdata->getCons(consid);
1102 
1103  if( ncurvars == 0 )
1104  continue;
1105 
1106  color = colorinfo.get( AUT_CONS(scip, cons) );
1107 
1108  if(color == -1) {
1109  *result = SCIP_DIDNOTFIND;
1110  break;
1111  }
1112 
1113  SCIPdebugMessage("cons <%s> color %d\n", SCIPconsGetName(cons), color);
1114  (void) h->add_vertex((unsigned int)color);
1115  nnodes++;
1116  }
1117  //add a node for every variable
1118  for( i = 0; i < nvars && *result == SCIP_SUCCESS; i++ )
1119  {
1120  int varid;
1121  SCIP_VAR* var;
1122 
1123  varid = partialdec->getVarsForBlock(block)[i];
1124  var = detprobdata->getVar(varid);
1125 
1126  color = colorinfo.get( AUT_VAR(scip, var) );
1127 
1128  if(color == -1) {
1129  *result = SCIP_DIDNOTFIND;
1130  break;
1131  }
1132 
1133  SCIPdebugMessage("var <%s> color %d\n", SCIPvarGetName(var), color);
1134  (void) h->add_vertex((unsigned int) colorinfo.getLenCons() + color);
1135  nnodes++;
1136  }
1137  //connecting the nodes with an additional node in the middle
1138  //it is necessary, since only nodes have colors
1139  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
1140  {
1141  int consid;
1142  SCIP_CONS* cons;
1143  int conscolor;
1144 
1145  consid = partialdec->getConssForBlock(block)[i];
1146  ncurvars = detprobdata->getNVarsForCons(consid);
1147  cons = detprobdata->getCons(consid);
1148  conscolor = colorinfo.get(AUT_CONS(scip, cons));
1149 
1150  if( ncurvars == 0 )
1151  continue;
1152 
1153  for( j = 0; j < ncurvars; j++ )
1154  {
1155  int varcolor;
1156  int varid;
1157  SCIP_VAR* var;
1158  SCIP_Real val;
1159 
1160  varid = detprobdata->getVarsForCons(consid)[j];
1161  var = detprobdata->getVar(varid);
1162 
1163  val = detprobdata->getVal(consid, varid);
1164 
1165  varcolor = colorinfo.get( AUT_VAR(scip, var )) + colorinfo.getLenCons(); /*lint !e864 */
1166  color = colorinfo.get( AUT_COEF(scip, val ));
1167  if( color == -1 )
1168  {
1169  *result = SCIP_DIDNOTFIND;
1170  break;
1171  }
1172  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
1173  (void) h->add_vertex((unsigned int) color);
1174  nnodes++;
1175  h->add_edge((unsigned int) nnodesoffset[b] + i, (unsigned int) nnodesoffset[b] + nconss + nvars + z);
1176  h->add_edge((unsigned int) nnodesoffset[b] + nconss + nvars + z, (unsigned int) nnodesoffset[b]+nconss + partialdec->getVarProbindexForBlock(varid, block) );
1177  SCIPdebugMessage("nz: c <%s> (id: %d, color: %d) -> nz (id: %d) (value: %f, color: %d) -> var <%s> (id: %d, color: %d) \n",
1178  SCIPconsGetName(cons),
1179  nnodesoffset[b] + i,
1180  conscolor,
1181  nnodesoffset[b] + nconss + nvars + z,
1182  val,
1183  color+colorinfo.getLenCons() + colorinfo.getLenVar(), /*lint !e864 */
1184  SCIPvarGetName(var),
1185  nnodesoffset[b]+nconss + partialdec->getVarProbindexForBlock(varid, block),
1186  varcolor);
1187  z++;
1188  }
1189  }
1190  pricingnonzeros[b] = z;
1191 
1192  /* add coefficient nodes for nonzeros in the master */
1193  for( i = 0; i < partialdec->getNMasterconss() && *result == SCIP_SUCCESS; ++i )
1194  {
1195  int masterconsid;
1196 
1197  masterconsid = partialdec->getMasterconss()[i];
1198  ncurvars = detprobdata->getNVarsForCons(masterconsid);
1199 
1200  for( j = 0; j < ncurvars; ++j )
1201  {
1202  int varid;
1203  SCIP_VAR* var;
1204  SCIP_Real val;
1205 
1206  varid = detprobdata->getVarsForCons(masterconsid)[j];
1207  /* ignore if the variable belongs to a different block */
1208  if( !partialdec->isVarBlockvarOfBlock(varid, block) )
1209  {
1210 // SCIPdebugMessage("Var <%s> belongs to a different block (%d)\n", SCIPvarGetName(detprobdata->getVar(varid) ), block);
1211  continue;
1212  }
1213 
1214  var = detprobdata->getVar(varid);
1215  val = detprobdata->getVal(masterconsid, varid);
1216  color = colorinfo.get(AUT_COEF(scip, val));
1217  assert(color != -1);
1218  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
1219 
1220  masterconssrelevant[i] = true;
1221 
1222  /* add coefficent node for current coeff */
1223  (void) h->add_vertex((unsigned int)color);
1224  assert(ABS(val < SCIPinfinity(scip)));
1225  SCIPdebugMessage("master nz for var <%s> (id: %d) (value: %f, color: %d)\n", SCIPvarGetName(var), nnodes, val, color);
1226  nnodes++;
1227  }
1228  }
1229  SCIPdebugMessage("Iteration %d: nnodes = %d\n", b, nnodes);
1230  assert(*result == SCIP_SUCCESS && (unsigned int) nnodes == h->get_nof_vertices());
1231  }
1232  /* connect the created graphs with nodes for the master problem */
1233 
1234  SCIPdebugMessage( "handling %d masterconss\n", partialdec->getNMasterconss());
1235  *pricingnodes = nnodes;
1236 
1237  for( i = 0; i < partialdec->getNMasterconss() && *result == SCIP_SUCCESS; ++i )
1238  {
1239  int masterconsid;
1240  SCIP_CONS* mastercons;
1241  int masterconsnode;
1242  int conscolor;
1243 
1244  /**experimental */
1245  if( !masterconssrelevant[i] )
1246  continue;
1247  /*experimental end */
1248 
1249  masterconsid= partialdec->getMasterconss()[i];
1250  mastercons = detprobdata->getCons(masterconsid);
1251  ncurvars = detprobdata->getNVarsForCons(masterconsid);
1252 
1253  SCIPdebugMessage("Handling cons <%s>\n", SCIPconsGetName(mastercons));
1254 
1255  /* create node for masterconss and get right color */
1256  conscolor = colorinfo.get(AUT_CONS(scip, mastercons) );
1257  assert(conscolor != -1);
1258  (void) h->add_vertex((unsigned int) conscolor);
1259  masterconsnode = nnodes;
1260  nnodes++;
1261 
1262  for( j = 0; j < ncurvars; ++j )
1263  {
1264  int varid;
1265  SCIP_VAR* var;
1266  SCIP_Real val;
1267  int blockid;
1268  int coefnodeindex;
1269  int bid;
1270  int varcolor;
1271 
1272  blockid = -1;
1273  bid = -1;
1274  varid = detprobdata->getVarsForCons(masterconsid)[j];
1275 
1276  var = detprobdata->getVar(varid);
1277 
1278  for( b = 0; b < nblocks; ++b )
1279  {
1280  if( partialdec->isVarBlockvarOfBlock(varid, blocks[b]) )
1281  {
1282  bid = b;
1283  blockid = blocks[b];
1284  break;
1285  }
1286  }
1287 
1288  /* ignore if the variable belongs to a different block */
1289  if( blockid == -1 )
1290  {
1291  //SCIPdebugMessage("Var <%s> belongs to a different block \n", SCIPvarGetName(var));
1292  continue;
1293  }
1294  val = detprobdata->getVal(masterconsid, varid);
1295 
1296  color = colorinfo.get(AUT_COEF(scip, val));
1297  assert(color != -1);
1298  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
1299 
1300  /* get coefficient node for current coefficient */
1301  coefnodeindex = nnodesoffset[bid] + nvars + nconss + pricingnonzeros[bid] + mastercoefindex[bid];
1302  ++(mastercoefindex[bid]);
1303 
1304  varcolor = colorinfo.get(AUT_VAR(scip, var));
1305  assert(varcolor != -1);
1306  varcolor += colorinfo.getLenCons();
1307 
1308  assert( (uint) masterconsnode < h->get_nof_vertices());
1309  assert( (uint) coefnodeindex < h->get_nof_vertices());
1310  /* master constraint and coefficient */
1311  h->add_edge((unsigned int) masterconsnode, (unsigned int) coefnodeindex);
1312  SCIPdebugMessage("ma: c <%s> (id: %d, color: %d) -> nz (id: %d) (value: <%.6f> , color: %d) -> pricingvar <%s> (id: %d, color: %d)\n",
1313  SCIPconsGetName(mastercons),
1314  masterconsnode, conscolor, coefnodeindex, val, color, SCIPvarGetName(var),
1315  nnodesoffset[bid] + nconss + varid, varcolor);
1316 
1317  /* get node index for pricing variable and connect masterconss, coeff and pricingvar nodes */
1318  h->add_edge((unsigned int) coefnodeindex, (unsigned int) nnodesoffset[bid] + nconss + partialdec->getVarProbindexForBlock(varid, blockid) );
1319  }
1320  }
1321 
1322 
1323  //free all allocated memory
1324  SCIPfreeBufferArray(scip, &pricingnonzeros);
1325  SCIPfreeBufferArray(scip, &nnodesoffset);
1326  SCIPfreeBufferArray(scip, &mastercoefindex);
1327 
1328  return SCIP_OKAY;
1329 }
1330 
1331 
1332 /** compare two graphs w.r.t. automorphism */
1333 extern "C"
1334 SCIP_RETCODE cmpGraphPair(
1335  SCIP* origscip, /**< SCIP data structure */
1336  SCIP* scip1, /**< first SCIP data structure to compare */
1337  SCIP* scip2, /**< second SCIP data structure to compare */
1338  int prob1, /**< index of first pricing prob */
1339  int prob2, /**< index of second pricing prob */
1340  SCIP_RESULT* result, /**< result pointer to indicate success or failure */
1341  SCIP_HASHMAP* varmap, /**< hashmap to save permutation of variables */
1342  SCIP_HASHMAP* consmap, /**< hashmap to save permutation of constraints */
1343  unsigned int searchnodelimit, /**< bliss search node limit (requires patched bliss version) */
1344  unsigned int generatorlimit /**< bliss generator limit (requires patched bliss version) */
1345  )
1346 {
1347  bliss::Graph graph;
1348  bliss::Stats bstats;
1349  AUT_HOOK2 *ptrhook;
1350  AUT_COLOR colorinfo;
1351  int nscips;
1352  SCIP* scips[2];
1353  int pricingindices[2];
1354  int pricingnodes = 0;
1355  scips[0] = scip1;
1356  scips[1] = scip2;
1357  pricingindices[0] = prob1;
1358  pricingindices[1] = prob2;
1359  nscips = 2;
1360  *result = SCIP_SUCCESS;
1361 
1362  SCIP_CALL( testScipVars(scips[0], scips[1], result) );
1363  SCIP_CALL( testScipCons(scips[0], scips[1], result) );
1364 
1365  SCIP_CALL( setuparrays(origscip, scips, nscips, &colorinfo, result) );
1366  SCIP_CALL( createGraph(origscip, scips, nscips, pricingindices, colorinfo, &graph, &pricingnodes, result) );
1367  SCIP_CALL( freeMemory(origscip, &colorinfo) );
1368 
1369  ptrhook = new AUT_HOOK2(varmap, consmap, FALSE, (unsigned int) pricingnodes, scips);
1370 #ifdef BLISS_PATCH_PRESENT
1371  graph.set_search_limits(searchnodelimit, generatorlimit);
1372 #endif
1373  graph.find_automorphisms(bstats, fhook, ptrhook);
1374 
1375  SCIPverbMessage(origscip, SCIP_VERBLEVEL_FULL , NULL, "finished calling bliss: number of reporting function calls (=number of generators): %d \n", ptrhook->ncalls);
1376 
1377  if( !ptrhook->getBool() )
1378  *result = SCIP_DIDNOTFIND;
1379 
1380  delete ptrhook;
1381  return SCIP_OKAY;
1382 }
1383 
1384 /** compare two graphs w.r.t. automorphism */
1385 SCIP_RETCODE cmpGraphPair(
1386  SCIP* scip, /**< SCIP data structure */
1387  gcg::PARTIALDECOMP* partialdec, /**< partialdec the graphs should be compared for */
1388  int block1, /**< index of first pricing prob */
1389  int block2, /**< index of second pricing prob */
1390  SCIP_RESULT* result, /**< result pointer to indicate success or failure */
1391  SCIP_HASHMAP* varmap, /**< hashmap to save permutation of variables */
1392  SCIP_HASHMAP* consmap, /**< hashmap to save permutation of constraints */
1393  unsigned int searchnodelimit, /**< bliss search node limit (requires patched bliss version) */
1394  unsigned int generatorlimit /**< bliss generator limit (requires patched bliss version) */
1395  )
1396 {
1397  bliss::Graph graph;
1398  bliss::Stats bstats;
1399  AUT_HOOK2 *ptrhook;
1400  AUT_COLOR colorinfo;
1401  std::vector<int> blocks;
1402  gcg::DETPROBDATA* detprobdata;
1403  int nconss;
1404  int nvars;
1405  int ncoeffs;
1406 
1407  int pricingnodes;
1408 
1409  *result = SCIP_SUCCESS;
1410 
1411  assert(partialdec != NULL );
1412 
1413  blocks = std::vector<int>(2, -1);
1414  blocks[0] = block1;
1415  blocks[1] = block2;
1416  pricingnodes = 0;
1417 
1418  if (partialdec->isAssignedToOrigProb() )
1419  detprobdata = GCGconshdlrDecompGetDetprobdataOrig(scip);
1420  else
1421  detprobdata = GCGconshdlrDecompGetDetprobdataPresolved(scip);
1422 
1423  assert(detprobdata != NULL);
1424 
1425  //allocate max n of coefarray, varsarray, and boundsarray in origscip
1426  nconss = partialdec->getNConssForBlock(blocks[0]) ;
1427  nvars = partialdec->getNVarsForBlock(blocks[0]) ;
1428  ncoeffs = partialdec->getNCoeffsForBlock( blocks[0]);
1429  SCIP_CALL( allocMemoryNewDetection(scip, detprobdata, &colorinfo, nconss*2+partialdec->getNMasterconss(), nvars*2, ncoeffs*2 + partialdec->getNCoeffsForMaster() ) );
1430  SCIP_CALL( setuparraysnewdetection(scip, detprobdata, partialdec, 2, blocks, &colorinfo, result) );
1431  SCIPdebugMessage("finished setup array method.\n");
1432  SCIP_CALL( createGraphNewDetection(scip, detprobdata, partialdec, 2, blocks, colorinfo, &graph, &pricingnodes, result) );
1433  SCIP_CALL( freeMemory(scip, &colorinfo) );
1434  SCIPdebugMessage("finished create graph.\n");
1435  ptrhook = new AUT_HOOK2(varmap, consmap, FALSE, (unsigned int) pricingnodes, NULL);
1436  SCIPdebugMessage("finished creating aut hook.\n");
1437  ptrhook->setNewDetectionStuff(detprobdata, partialdec, &blocks);
1438 
1439 #ifdef BLISS_PATCH_PRESENT
1440  graph.set_search_limits(searchnodelimit, generatorlimit);
1441 #endif
1442  graph.find_automorphisms(bstats, fhook, ptrhook);
1443  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL , NULL, "finished calling bliss: number of reporting function calls (=number of generators): %d \n", ptrhook->ncalls);
1444 
1445  SCIPdebugMessage("finished find automorphisms.\n");
1446 
1447  if( !ptrhook->getBool() )
1448  *result = SCIP_DIDNOTFIND;
1449 
1450  delete ptrhook;
1451  return SCIP_OKAY;
1452 }
int getNConss()
returns the number of variables considered in the detprobdata
static SCIP_RETCODE allocMemory(SCIP *scip, AUT_COLOR *colorinfo, int nconss, int nvars)
unsigned int n
unsigned int getNNodes()
int GCGgetNMasterConss(SCIP *scip)
Definition: relax_gcg.c:4079
GCG interface methods.
std::vector< int > & getVarsForBlock(int block)
Gets array containing vars of a block.
static SCIP_RETCODE createGraphNewDetection(SCIP *scip, gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec, int nblocks, std::vector< int > blocks, AUT_COLOR colorinfo, bliss::Graph *graph, int *pricingnodes, SCIP_RESULT *result)
AUT_HOOK2(SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool aut, unsigned int n, SCIP **scips)
void setNewDetectionStuff(gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec, std::vector< int > *blocks)
gcg::DETPROBDATA * detprobdata
SCIP * getScip()
returns the corresponding scip data structure
struct struct_cons AUT_CONS
Definition: pub_bliss.h:50
int getVarProbindexForBlock(int varid, int block)
Gets index in variables array of a block for a variable.
bool isVarBlockvarOfBlock(int var, int block)
Checks whether the var is assigned to the block.
std::vector< int > & getMasterconss()
Gets array containing all master conss indices.
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:1033
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:490
DETPROBDATA * GCGconshdlrDecompGetDetprobdataOrig(SCIP *scip)
help method to access detprobdata for unpresolved problem
int getNVarsForBlock(int block)
Gets size of the vector containing vars assigned to a block.
SCIP ** getScips()
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:216
various SCIP helper methods
struct struct_colorinformation AUT_COLOR
Definition: pub_bliss.h:53
int getNConssForBlock(int block)
Gets size of the vector containing conss assigned to a block.
SCIP_CONS * getCons(int consIndex)
returns the SCIP constraint related to a constraint index
SCIP_HASHMAP * consmap
static SCIP_RETCODE allocMemoryNewDetection(SCIP *scip, gcg::DETPROBDATA *detprobdata, AUT_COLOR *colorinfo, int nconss, int nvars, int ncoeffs)
SCIP_HASHMAP * varmap
SCIP_Bool aut
static SCIP_RETCODE testScipVars(SCIP *scip1, SCIP *scip2, SCIP_RESULT *result)
SCIP_HASHMAP * getConsHash()
C++ interface of cons_decomp.
static SCIP_RETCODE freeMemory(SCIP *scip, AUT_COLOR *colorinfo)
struct struct_coef AUT_COEF
Definition: pub_bliss.h:52
static SCIP_RETCODE setuparraysnewdetection(SCIP *scip, gcg::DETPROBDATA *detprobdata, gcg::PARTIALDECOMP *partialdec, int nblocks, std::vector< int > blocks, AUT_COLOR *colorinfo, SCIP_RESULT *result)
static SCIP_RETCODE reallocMemory(SCIP *scip, AUT_COLOR *colorinfo, int nconss, int nvars)
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:621
SCIP_HASHMAP * getVarHash()
SCIP_CONS ** GCGgetOrigMasterConss(SCIP *scip)
Definition: relax_gcg.c:4117
int getNCoeffsForBlock(int blockid)
Gets the number of nonzero coeffs in a certain block.
void setBool(SCIP_Bool aut)
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:434
automorphism recognition of SCIPs
std::vector< int > & getConssForBlock(int block)
returns array containing constraints assigned to a block
class to manage partial decompositions
std::vector< int > * blocks
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
helper functions for automorphism detection
static SCIP_RETCODE testScipCons(SCIP *scip1, SCIP *scip2, SCIP_RESULT *result)
DETPROBDATA * GCGconshdlrDecompGetDetprobdataPresolved(SCIP *scip)
help method to access detprobdata for transformed problem
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:182
struct struct_var AUT_VAR
Definition: pub_bliss.h:51
class storing (potentially incomplete) decompositions
static void fhook(void *user_param, unsigned int N, const unsigned int *aut)
SCIP_Real getVal(int row, int col)
returns a coefficient from the coefficient matrix
SCIP_RETCODE cmpGraphPair(SCIP *origscip, SCIP *scip1, SCIP *scip2, int prob1, int prob2, SCIP_RESULT *result, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, unsigned int searchnodelimit, unsigned int generatorlimit)
std::vector< int > & getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
int getNMasterconss()
Gets size of the vector containing master conss.
bool isAssignedToOrigProb()
Gets whether the partialdec is from the presolved problem.
SCIP_VAR * getVar(int varIndex)
returns SCIP variable related to a variable index
class storing partialdecs and the problem matrix
static SCIP_RETCODE createGraph(SCIP *origscip, SCIP **scips, int nscips, int *pricingindices, AUT_COLOR colorinfo, bliss::Graph *graph, int *pricingnodes, SCIP_RESULT *result)
gcg::PARTIALDECOMP * partialdec
static SCIP_RETCODE setuparrays(SCIP *origscip, SCIP **scips, int nscips, AUT_COLOR *colorinfo, SCIP_RESULT *result)
SCIP_Bool getBool()