dec_isomorph.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-2018 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 
40 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
41 /* #define SCIP_DEBUG */
42 
43 #include "dec_isomorph.h"
44 #include "pub_decomp.h"
45 #include "cons_decomp.h"
46 #include "scip_misc.h"
47 #include "gcg.h"
48 #include "class_seeed.h"
49 #include "class_seeedpool.h"
50 #include "scip/clock.h"
51 
52 #include "bliss/graph.hh"
53 #include "pub_gcgvar.h"
54 #include <cstring>
55 #include <cassert>
56 #include <algorithm>
57 #include <iostream>
58 
59 #include "pub_bliss.h"
60 
61 /* constraint handler properties */
62 #define DEC_DETECTORNAME "isomorph"
63 #define DEC_DESC "Detector for pricing problems suitable for aggregation"
64 #define DEC_FREQCALLROUND 1
65 #define DEC_MAXCALLROUND 0
66 #define DEC_MINCALLROUND 0
67 #define DEC_FREQCALLROUNDORIGINAL 1
68 #define DEC_MAXCALLROUNDORIGINAL 0
69 #define DEC_MINCALLROUNDORIGINAL 0
70 #define DEC_PRIORITY 100
71 #define DEC_DECCHAR 'I'
73 #define DEC_ENABLED FALSE
74 #define DEC_ENABLEDORIGINAL FALSE
75 #define DEC_ENABLEDFINISHING FALSE
76 #define DEC_ENABLEDPOSTPROCESSING FALSE
77 #define DEC_SKIP TRUE
78 #define DEC_USEFULRECALL FALSE
79 #define DEC_LEGACYMODE TRUE
82 #define DEFAULT_MAXDECOMPSEXACT 6
83 #define DEFAULT_MAXDECOMPSEXTEND 4
85 #define DEFAULT_LEGACYEXACT TRUE
86 #define DEFAULT_LEGACYEXTEND FALSE
89 #define SET_MULTIPLEFORSIZETRANSF 12500
90 
91 /*
92  * Data structures
93  */
94 
96 struct DEC_DetectorData
97 {
98  SCIP_RESULT result;
101  SCIP_Bool legacyextend;
102  SCIP_Bool legacyexact;
103 };
104 
105 typedef struct struct_hook AUT_HOOK;
106 
109 {
110  SCIP_Bool aut;
111  unsigned int n;
112  SCIP* scip;
113  int* conssperm;
118  struct_hook(SCIP_Bool aut,
119  unsigned int n,
120  SCIP* scip
121  );
122 
124  struct_hook(SCIP_Bool aut,
125  unsigned int n,
126  SCIP* scip,
127  gcg::Seeed* seeed,
128  gcg::Seeedpool* seeedpool
129  );
130 
131  ~struct_hook();
133  SCIP_Bool getBool();
134 
136  void setBool(SCIP_Bool aut);
137 
139  SCIP* getScip();
140 
142  gcg::Seeed* getSeeed();
143 
145  gcg::Seeedpool* getSeeedpool();
146 };
147 
149 {
150  return this->scip;
151 }
152 
154 {
155  return this->seeed;
156 }
157 
159 {
160  return this->seeedpool;
161 }
162 
164 {
165  return aut;
166 }
167 
168 void struct_hook::setBool( SCIP_Bool aut_ )
169 {
170  aut = aut_;
171 }
172 
173 
174 
175 
178 int gcd(int a, int b) {
179  return b == 0 ? a : gcd(b, a % b);
180 }
181 
184  SCIP_Bool aut_,
185  unsigned int n_,
186  SCIP* scip_
187  ) : conssperm(NULL)
188 {
189  aut = aut_;
190  n = n_;
191  scip = scip_;
192  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &conssperm, SCIPgetNConss(scip)) ); /*lint !e666*/
193  seeed = NULL;
194  seeedpool = NULL;
195 }
196 
199  SCIP_Bool aut_,
200  unsigned int n_,
201  SCIP* scip_,
202  gcg::Seeed* seeed_,
203  gcg::Seeedpool* seeedpool_
204  ) : conssperm(NULL)
205 {
206  aut = aut_;
207  n = n_;
208  scip = scip_;
209  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &conssperm, seeedpool_->getNConss() ) ); /*lint !e666*/
210  seeed = seeed_;
211  seeedpool = seeedpool_;
212 }
213 
215 { /*lint -esym(1540,struct_hook::conssperm) */
216  if( conssperm != NULL )
217  SCIPfreeMemoryArrayNull(scip, &conssperm);
218  conssperm = NULL;
219  scip = NULL;
220 }
222 static
223 void fhook(
224  void* user_param,
225  unsigned int N,
226  const unsigned int* aut
227  )
228 { /*lint -e715*/
229  int i;
230  int nconss;
231  SCIP_CONS** conss;
232  AUT_HOOK* hook = (AUT_HOOK*) user_param;
233  int auti;
234  int ind;
235 
236  nconss = SCIPgetNConss(hook->getScip());
237  assert(nconss == SCIPgetNConss(hook->getScip()));
238  conss = SCIPgetConss(hook->getScip());
239 
240  for( i = 0; i < nconss; i++ )
241  {
242  assert(aut[i] < INT_MAX);
243  if( (size_t) i != aut[i])
244  {
245  auti = (int) aut[i];
246 
247  SCIPdebugMessage("%d <%s> <-> %d <%s>\n", i, SCIPconsGetName(conss[i]), auti, SCIPconsGetName(conss[auti]));
248 
249  ind = MIN(i, auti);
250 
251  if( hook->conssperm[i] != -1)
252  ind = MIN(ind, hook->conssperm[i]);
253  if( hook->conssperm[auti] != -1 )
254  ind = MIN(ind, hook->conssperm[auti]);
255 
256  hook->conssperm[i] = ind;
257  hook->conssperm[auti] = ind;
258  hook->setBool(TRUE);
259  }
260  }
261 }
262 
264 static
266  void* user_param,
267  unsigned int N,
268  const unsigned int* aut
269  )
270 { /*lint -e715*/
271  int i;
272  int nconss;
273  AUT_HOOK* hook = (AUT_HOOK*) user_param;
274  int auti;
275  int ind;
276  gcg::Seeed* seeed;
278 
279  seeed = hook->getSeeed();
280  seeedpool = hook->getSeeedpool() ;
281  assert(seeed != NULL);
282  assert(seeedpool != NULL);
283  nconss = seeed->getNOpenconss();
284 
285  for( i = 0; i < nconss; i++ )
286  {
287  SCIP_CONS* cons = seeedpool->getConsForIndex(seeed->getOpenconss()[i]);
288  assert(aut[i] < INT_MAX);
289  if( (size_t) i != aut[i])
290  {
291  auti = (int) aut[i];
292 
293  SCIPdebugMessage("%d <%s> <-> %d <%s>\n", i, SCIPconsGetName(cons), auti, SCIPconsGetName(seeedpool->getConsForIndex(seeed->getOpenconss()[auti])));
294 
295  ind = MIN(i, auti);
296 
297  if( hook->conssperm[i] != -1)
298  ind = MIN(ind, hook->conssperm[i]);
299  if( hook->conssperm[auti] != -1 )
300  ind = MIN(ind, hook->conssperm[auti]);
301 
302  hook->conssperm[i] = ind;
303  hook->conssperm[auti] = ind;
304  hook->setBool(TRUE);
305  }
306  }
307 }
308 
309 static
310 SCIP_RETCODE allocMemory(
311  SCIP* scip,
312  AUT_COLOR* colorinfo,
313  int nconss,
314  int nvars
315  )
316 {
317  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarraycoefs, nvars) );
318  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarrayvars, nvars) );
319  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarrayconss, nconss) );
320  colorinfo->alloccoefsarray = nvars;
321  return SCIP_OKAY;
322 }
323 
325 static
327  SCIP* scip,
328  AUT_COLOR* colorinfo
329 )
330 {
331  int i;
332 
333  for( i = 0; i < colorinfo->lenvarsarray; i++ )
334  {
335  AUT_VAR* svar = (AUT_VAR*) colorinfo->ptrarrayvars[i];
336  delete svar;
337  }
338  for( i = 0; i < colorinfo->lenconssarray; i++ )
339  {
340  AUT_CONS* scons = (AUT_CONS*) colorinfo->ptrarrayconss[i];
341  delete scons;
342  }
343  for( i = 0; i < colorinfo->lencoefsarray; i++ )
344  {
345  AUT_COEF* scoef = (AUT_COEF*) colorinfo->ptrarraycoefs[i];
346  delete scoef;
347  }
348 
349  SCIPfreeMemoryArray(scip, &colorinfo->ptrarraycoefs);
350  SCIPfreeMemoryArray(scip, &colorinfo->ptrarrayconss);
351  SCIPfreeMemoryArray(scip, &colorinfo->ptrarrayvars);
352 }
353 
355 static
356 SCIP_RETCODE setupArrays(
357  SCIP* scip,
358  AUT_COLOR* colorinfo,
359  SCIP_RESULT* result
360  )
361 { /*lint -esym(593,scoef) */
362  int i;
363  int j;
364  int nconss;
365  int nvars;
366  SCIP_CONS** conss;
367  SCIP_VAR** vars;
368  AUT_COEF* scoef;
369  AUT_CONS* scons;
370  SCIP_Bool added;
371  SCIP_Bool onlysign;
372 
373  //allocate max n of coefarray, varsarray, and boundsarray in scip
374  nconss = SCIPgetNConss(scip);
375  nvars = SCIPgetNVars(scip);
376  SCIP_CALL( allocMemory(scip, colorinfo, nconss, nvars) );
377 
378  conss = SCIPgetConss(scip);
379  vars = SCIPgetVars(scip);
380 
381  onlysign = colorinfo->getOnlySign();
382 
383  //save the properties of variables in a struct array and in a sorted pointer array
384  for( i = 0; i < nvars; i++ )
385  {
386  AUT_VAR* svar = new AUT_VAR(scip, vars[i]);
387  //add to pointer array iff it doesn't exist
388  SCIP_CALL( colorinfo->insert(svar, &added) );
389  SCIPdebugMessage("%s color %d %d\n", SCIPvarGetName(vars[i]), colorinfo->get(*svar), colorinfo->color);
390  //otherwise free allocated memory
391  if( !added )
392  delete svar;
393  }
394 
395  //save the properties of constraints in a struct array and in a sorted pointer array
396  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
397  {
398  SCIP_Real* curvals = NULL;
399  SCIP_VAR** curvars = NULL;
400 
401  int ncurvars = GCGconsGetNVars(scip, conss[i]);
402  if( ncurvars == 0 )
403  continue;
404  scons = new AUT_CONS(scip, conss[i]);
405  //add to pointer array iff it doesn't exist
406  SCIPdebugMessage("nconss %d %d\n", nconss, *result);
407  SCIP_CALL( colorinfo->insert(scons, &added) );
408  SCIPdebugMessage("%s color %d %d\n", SCIPconsGetName(conss[i]), colorinfo->get(*scons), colorinfo->color);
409  //otherwise free allocated memory
410  if( !added )
411  delete scons;
412 
413  SCIP_CALL( SCIPallocMemoryArray(scip, &curvars, ncurvars) );
414  SCIP_CALL( SCIPallocMemoryArray(scip, &curvals, ncurvars) );
415 
416  SCIP_CALL( GCGconsGetVars(scip, conss[i], curvars, ncurvars) );
417  SCIP_CALL( GCGconsGetVals(scip, conss[i], curvals, ncurvars) );
418 
419  //save the properties of variables of the constraints in a struct array and in a sorted pointer array
420  for( j = 0; j < ncurvars; j++ )
421  {
422  SCIP_Real constant;
423  added = FALSE;
424 
425  if( SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED)
426  SCIPgetProbvarSum(scip, &(curvars[j]), &(curvals[j]), &constant);
427 
428  if( !onlysign )
429  {
430  scoef = new AUT_COEF(scip, curvals[j]);
431  }
432  else
433  {
434  if( SCIPisPositive(scip, curvals[j]) )
435  scoef = new AUT_COEF(scip, 1.0);
436  else if( SCIPisNegative(scip, curvals[j]) )
437  scoef = new AUT_COEF(scip, -1.0);
438  else
439  scoef = new AUT_COEF(scip, 0.0);
440  }
441 
442  //test, whether the coefficient is not zero
443  if( !SCIPisZero(scip, scoef->getVal()) )
444  {
445  //add to pointer array iff it doesn't exist
446  SCIP_CALL( colorinfo->insert(scoef, &added) );
447  SCIPdebugMessage("%f color %d %d\n", scoef->getVal(), colorinfo->get(*scoef), colorinfo->color);
448  }
449  //otherwise free allocated memory
450  if( !added )
451  delete scoef;
452 
453  }
454  SCIPfreeMemoryArray(scip, &curvars);
455  SCIPfreeMemoryArray(scip, &curvals);
456 }
457  return SCIP_OKAY;
458 }
459 
461 static
462 SCIP_RETCODE setupArrays(
463  SCIP* scip,
464  AUT_COLOR* colorinfo,
465  SCIP_RESULT* result,
466  gcg::Seeed* seeed,
468  )
469 { /*lint -esym(593,scoef) */
470  int i;
471  int j;
472  int nconss;
473  int nvars;
474  AUT_COEF* scoef;
475  AUT_CONS* scons;
476  SCIP_Bool added;
477  SCIP_Bool onlysign;
478 
479  //allocate max n of coefarray, varsarray, and boundsarray in scip
480  nconss = seeed->getNOpenconss();
481  nvars = seeed->getNVars();
482  SCIP_CALL( allocMemory(scip, colorinfo, nconss, nvars) );
483 
484  onlysign = colorinfo->getOnlySign();
485 
486  //save the properties of variables in a struct array and in a sorted pointer array
487  for( i = 0; i < nvars; i++ )
488  {
489  SCIP_VAR* var = seeedpool->getVarForIndex(i);
490  AUT_VAR* svar = new AUT_VAR(scip, var);
491  //add to pointer array iff it doesn't exist
492  SCIP_CALL( colorinfo->insert(svar, &added) );
493  SCIPdebugMessage("%s color %d %d\n", SCIPvarGetName(var), colorinfo->get(*svar), colorinfo->color);
494  //otherwise free allocated memory
495  if( !added )
496  delete svar;
497  }
498 
499  //save the properties of constraints in a struct array and in a sorted pointer array
500  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
501  {
502  int consindex = seeed->getOpenconss()[i];
503  SCIP_CONS* cons = seeedpool->getConsForIndex(consindex);
504 
505  int ncurvars = seeedpool->getNVarsForCons(consindex);
506  if( ncurvars == 0 )
507  continue;
508 
509  scons = new AUT_CONS(scip, cons);
510  //add to pointer array iff it doesn't exist
511  SCIPdebugMessage("nconss %d %d\n", nconss, *result);
512  SCIP_CALL( colorinfo->insert(scons, &added) );
513  SCIPdebugMessage("%s color %d %d\n", SCIPconsGetName(cons), colorinfo->get(*scons), colorinfo->color);
514  //otherwise free allocated memory
515  if( !added )
516  delete scons;
517 
518  //save the properties of variables of the constraints in a struct array and in a sorted pointer array
519  for( j = 0; j < ncurvars; j++ )
520  {
521  added = FALSE;
522 
523  if( !onlysign )
524  {
525  scoef = new AUT_COEF(scip, seeedpool->getValsForCons(consindex)[j]);
526  }
527  else
528  {
529  if( SCIPisPositive(scip, seeedpool->getValsForCons(consindex)[j]) )
530  scoef = new AUT_COEF(scip, 1.0);
531  else if( SCIPisNegative(scip, seeedpool->getValsForCons(consindex)[j]) )
532  scoef = new AUT_COEF(scip, -1.0);
533  else
534  scoef = new AUT_COEF(scip, 0.0);
535  }
536 
537  //test, whether the coefficient is not zero
538  if( !SCIPisZero(scip, scoef->getVal()) )
539  {
540  //add to pointer array iff it doesn't exist
541  SCIP_CALL( colorinfo->insert(scoef, &added) );
542  SCIPdebugMessage("%f color %d %d\n", scoef->getVal(), colorinfo->get(*scoef), colorinfo->color);
543  }
544  //otherwise free allocated memory
545  if( !added )
546  delete scoef;
547 
548  }
549  }
550  return SCIP_OKAY;
551 }
552 
554 static
555 SCIP_RETCODE createGraph(
556  SCIP* scip,
557  AUT_COLOR colorinfo,
558  bliss::Graph* graph,
559  SCIP_RESULT* result
560  )
561 {
562  int i;
563  int j;
564  int z;
565  int nvars;
566  int nconss;
567  int ncurvars;
568  int curvar;
569  int color;
570  SCIP_CONS** conss;
571  SCIP_VAR** vars;
572  SCIP_VAR** curvars = NULL;
573  SCIP_Real* curvals = NULL;
574  unsigned int nnodes;
575  SCIP_Bool onlysign;
576 
577  nnodes = 0;
578  //building the graph out of the arrays
579  bliss::Graph* h = graph;
580  nconss = SCIPgetNConss(scip);
581  nvars = SCIPgetNVars(scip);
582  conss = SCIPgetConss(scip);
583  vars = SCIPgetVars(scip);
584  z = 0;
585  onlysign = colorinfo.getOnlySign();
586 
587  //add a node for every constraint
588  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
589  {
590  ncurvars = GCGconsGetNVars(scip, conss[i]);
591 
592  AUT_CONS scons(scip, conss[i]);
593  color = colorinfo.get(scons);
594 
595  if( color == -1 )
596  {
597  *result = SCIP_DIDNOTFIND;
598  break;
599  }
600 
601  assert(color >= 0);
602  (void)h->add_vertex((unsigned int) color);
603  nnodes++;
604  }
605  //add a node for every variable
606  for( i = 0; i < nvars && *result == SCIP_SUCCESS; i++ )
607  {
608  AUT_VAR svar(scip, vars[i]);
609  color = colorinfo.get(svar);
610 
611  if( color == -1 )
612  {
613  *result = SCIP_DIDNOTFIND;
614  break;
615  }
616  (void) h->add_vertex((unsigned int) (colorinfo.getLenCons() + color));
617  nnodes++;
618  }
619  //connecting the nodes with an additional node in the middle
620  //it is necessary, since only nodes have colors
621  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
622  {
623  AUT_CONS scons(scip, conss[i]);
624  ncurvars = GCGconsGetNVars(scip, conss[i]);
625  if( ncurvars == 0 )
626  continue;
627  SCIP_CALL( SCIPallocMemoryArray(scip, &curvars, ncurvars) );
628  SCIP_CALL( GCGconsGetVars(scip, conss[i], curvars, ncurvars) );
629  SCIP_CALL( SCIPallocMemoryArray(scip, &curvals, ncurvars) );
630  SCIP_CALL( GCGconsGetVals(scip, conss[i], curvals, ncurvars) );
631 
632  for( j = 0; j < ncurvars; j++ )
633  {
634  SCIP_Real constant;
635 
636  if( SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED)
637  SCIPgetProbvarSum(scip, &(curvars[j]), &(curvals[j]), &constant);
638 
639  SCIP_Real val;
640 
641  if( !onlysign )
642  {
643  val = curvals[j];
644  }
645  else
646  {
647  if( SCIPisPositive(scip, curvals[j]) )
648  val = 1.0;
649  else if( SCIPisNegative(scip, curvals[j]) )
650  val = -1.0;
651  else
652  val = 0.0;
653  }
654 
655  AUT_COEF scoef(scip, val);
656  AUT_VAR svar(scip, curvars[j]);
657 
658  color = colorinfo.get(scoef);
659 
660  if( color == -1 )
661  {
662  *result = SCIP_DIDNOTFIND;
663 
664  break;
665  }
666  curvar = SCIPvarGetProbindex(curvars[j]);
667  (void) h->add_vertex((unsigned int) (colorinfo.getLenCons() + colorinfo.getLenVar() + color)); /*lint !e864 */
668  nnodes++;
669  h->add_edge((unsigned int)i, (unsigned int) (nconss + nvars + z));
670  h->add_edge((unsigned int) (nconss + nvars + z), (unsigned int) (nconss + curvar));
671  SCIPdebugMessage(
672  "nz: c <%s> (id: %d, colour: %d) -> nz (id: %d) (value: %f, colour: %d) -> var <%s> (id: %d, colour: %d) \n",
673  SCIPconsGetName(conss[i]), i, colorinfo.get(scons),
674  nconss + nvars + z, scoef.getVal(),
675  color + colorinfo.getLenCons() + colorinfo.getLenVar(), /*lint !e864 */
676  SCIPvarGetName(curvars[j]), nconss + curvar,
677  colorinfo.get(svar) + colorinfo.getLenCons()); /*lint !e864 */
678  z++;
679 
680  }
681 
682  SCIPfreeMemoryArray(scip, &curvals);
683  SCIPfreeMemoryArray(scip, &curvars);
684 
685  }
686  SCIPdebugMessage("Iteration 1: nnodes = %ud, Cons = %d, Vars = %d\n", nnodes, colorinfo.getLenCons(), colorinfo.getLenVar()); /*lint !e864 */
687  assert(*result == SCIP_SUCCESS && nnodes == h->get_nof_vertices());
688 
689  //free all allocated memory
690  freeMemory(scip, &colorinfo);
691  return SCIP_OKAY;
692 }
693 
695 static
696 SCIP_RETCODE createGraph(
697  SCIP* scip,
698  AUT_COLOR colorinfo,
699  bliss::Graph* graph,
700  SCIP_RESULT* result,
701  gcg::Seeed* seeed,
703  )
704 {
705  int i;
706  int j;
707  int z;
708  int nvars;
709  int nconss;
710  int ncurvars;
711  int curvar;
712  int color;
713  unsigned int nnodes;
714  SCIP_Bool onlysign;
715  nnodes = 0;
716  //building the graph out of the arrays
717  bliss::Graph* h = graph;
718  nconss = seeed->getNOpenconss();
719  nvars = seeed->getNVars();
720  z = 0;
721  onlysign = colorinfo.getOnlySign();
722 
723  //add a node for every constraint
724  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
725  {
726  ncurvars = seeedpool->getNVarsForCons(seeed->getOpenconss()[i]);
727  SCIP_CONS* cons = seeedpool->getConsForIndex(seeed->getOpenconss()[i]);
728 
729  AUT_CONS scons(scip, cons);
730  color = colorinfo.get(scons);
731 
732  if( color == -1 )
733  {
734  *result = SCIP_DIDNOTFIND;
735  break;
736  }
737 
738  assert(color >= 0);
739  (void)h->add_vertex((unsigned int) color);
740  nnodes++;
741  }
742  //add a node for every variable
743  for( i = 0; i < nvars && *result == SCIP_SUCCESS; i++ )
744  {
745  SCIP_VAR* var = seeedpool->getVarForIndex(i);
746  AUT_VAR svar(scip, var);
747  color = colorinfo.get(svar);
748 
749  if( color == -1 )
750  {
751  *result = SCIP_DIDNOTFIND;
752  break;
753  }
754  (void) h->add_vertex((unsigned int) (colorinfo.getLenCons() + color));
755  nnodes++;
756  }
757  //connecting the nodes with an additional node in the middle
758  //it is necessary, since only nodes have colors
759  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
760  {
761  int consindex = seeed->getOpenconss()[i];
762  SCIP_CONS* cons = seeedpool->getConsForIndex(consindex);
763  AUT_CONS scons(scip, cons);
764  ncurvars = seeedpool->getNVarsForCons(seeed->getOpenconss()[i]);
765  if( ncurvars == 0 )
766  continue;
767 
768  for( j = 0; j < ncurvars; j++ )
769  {
770  int varindex = seeedpool->getVarsForCons(consindex)[j];
771  SCIP_VAR* var = seeedpool->getVarForIndex(varindex);
772 
773 
774 // if( SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED)
775 // SCIPgetProbvarSum(scip, &(curvars[j]), &(curvals[j]), &constant);
776 
777  SCIP_Real val;
778 
779  if( !onlysign )
780  {
781  val = seeedpool->getValsForCons(consindex)[j];
782  }
783  else
784  {
785  if( SCIPisPositive(scip, seeedpool->getValsForCons(consindex)[j]) )
786  val = 1.0;
787  else if( SCIPisNegative(scip, seeedpool->getValsForCons(consindex)[j]) )
788  val = -1.0;
789  else
790  val = 0.0;
791  }
792  *result = SCIP_SUCCESS;
793 
794  AUT_COEF scoef(scip, val);
795  AUT_VAR svar(scip, var);
796 
797  color = colorinfo.get(scoef);
798 
799  if( color == -1 )
800  {
801  *result = SCIP_DIDNOTFIND;
802  break;
803  }
804 
805  curvar = SCIPvarGetProbindex(var);
806  (void) h->add_vertex((unsigned int) (colorinfo.getLenCons() + colorinfo.getLenVar() + color)); /*lint !e864 */
807  nnodes++;
808  h->add_edge((unsigned int)i, (unsigned int) (nconss + nvars + z));
809  h->add_edge((unsigned int) (nconss + nvars + z), (unsigned int) (nconss + curvar));
810  SCIPdebugMessage(
811  "nz: c <%s> (id: %d, colour: %d) -> nz (id: %d) (value: %f, colour: %d) -> var <%s> (id: %d, colour: %d) \n",
812  SCIPconsGetName(cons), i, colorinfo.get(scons),
813  nconss + nvars + z, scoef.getVal(),
814  color + colorinfo.getLenCons() + colorinfo.getLenVar(), /*lint !e864 */
815  SCIPvarGetName(var), nconss + curvar,
816  colorinfo.get(svar) + colorinfo.getLenCons()); /*lint !e864 */
817  z++;
818 
819  }
820 
821 
822  }
823  SCIPdebugMessage("Iteration 1: nnodes = %ud, Cons = %d, Vars = %d\n", nnodes, colorinfo.getLenCons(), colorinfo.getLenVar()); /*lint !e864 */
824  assert(*result == SCIP_SUCCESS && nnodes == h->get_nof_vertices());
825 
826  //free all allocated memory
827  freeMemory(scip, &colorinfo);
828  return SCIP_OKAY;
829 }
830 
831 
837  SCIP* scip,
838  gcg::Seeed** newSeeed,
839  int* masterconss,
840  int nmasterconss,
841  gcg::Seeed* seeed,
843  SCIP_Bool exact
844  )
845 {
846 
847 
848  char decinfo[SCIP_MAXSTRLEN];
849  int nconss;
850  int nvars;
851  int nblocks;
852  int* blockrepresentative;
853  int nextblock = 1;
854  SCIP_Bool* consismaster;
855  int i, j;
856  int* vartoblock;
857  int ncurvars;
858 
859  std::vector<int> constoblock( seeedpool->getNConss(), -1);
860  std::vector<int> newconstoblock( seeedpool->getNConss(), -1);
861 
862  assert(scip != NULL);
863  assert(nmasterconss == 0 || masterconss != NULL);
864  assert(SCIPgetStage(scip) >= SCIP_STAGE_TRANSFORMED);
865 
866  nconss = seeed->getNOpenconss();
867  nvars = seeed->getNVars();
868 
869  assert( nmasterconss <= nconss );
870 
871  nblocks = nconss-nmasterconss+1;
872  assert(nblocks > 0);
873 
874  SCIP_CALL( SCIPallocMemoryArray(scip, &blockrepresentative, nblocks) );
875  SCIP_CALL( SCIPallocMemoryArray(scip, &consismaster, nconss) );
876  SCIP_CALL( SCIPallocMemoryArray(scip, &vartoblock, nvars) );
877 
878  for( i = 0; i < nmasterconss; ++i )
879  {
880  constoblock[masterconss[i]] = nblocks+1;
881  }
882 
883  for( i = 0; i < nconss; ++i )
884  {
885  consismaster[i] = ( constoblock[seeed->getOpenconss()[i]] != -1 );
886  }
887 
888  for( i = 0; i < nvars; ++i )
889  {
890  vartoblock[i] = -1;
891  }
892 
893  for( i = 0; i < nblocks; ++i )
894  {
895  blockrepresentative[i] = -1;
896  }
897 
898  /* assign constraints to representatives */
899 
900  /* go through the all constraints */
901  for( i = 0; i < nconss; ++i )
902  {
903  int consblock;
904  int cons = seeed->getOpenconss()[i];
905 
906  if( consismaster[i] )
907  continue;
908 
909  /* get variables of constraint; ignore empty constraints */
910  ncurvars = seeedpool->getNVarsForCons(seeed->getOpenconss()[i]);
911  assert(ncurvars >= 0);
912 
913  assert( constoblock[cons] == -1 );
914 
915  /* if there are no variables, put it in the first block, otherwise put it in the next block */
916  if( ncurvars == 0 )
917  consblock = -1;
918  else
919  consblock = nextblock;
920 
921  /* go through all variables */
922  for( j = 0; j < ncurvars; ++j )
923  {
924  int var;
925  int varblock;
926  var = seeedpool->getVarsForCons(cons)[j];
927 
928  assert(var >= 0);
929 
931  /* get block of variable */
932  varblock = vartoblock[var];
933 
934  /* if variable is already assigned to a block, assign constraint to that block */
935  if( varblock > -1 && varblock != consblock )
936  {
937  consblock = MIN(consblock, blockrepresentative[varblock]);
938  SCIPdebugPrintf("still in block %d.\n", varblock);
939  }
940  else if( varblock == -1 )
941  {
942  /* if variable is free, assign it to the new block for this constraint */
943  varblock = consblock;
944  assert(varblock > 0);
945  assert(varblock <= nextblock);
946  vartoblock[var] = varblock;
947  SCIPdebugPrintf("new in block %d.\n", varblock);
948  }
949  else
950  {
951  assert((varblock > 0) && (consblock == varblock));
952  SCIPdebugPrintf("no change.\n");
953  }
954 
955  SCIPdebugPrintf("VARINDEX: %d (%d)\n", var, vartoblock[var]);
956  }
957 
958  /* if the constraint belongs to a new block, mark it as such */
959  if( consblock == nextblock )
960  {
961  assert(consblock > 0);
962  blockrepresentative[consblock] = consblock;
963  assert(blockrepresentative[consblock] > 0);
964  assert(blockrepresentative[consblock] <= nextblock);
965  ++(nextblock);
966  }
967 
968  SCIPdebugMessage("Cons %s will be in block %d (next %d)\n", SCIPconsGetName(seeedpool->getConsForIndex(cons)), consblock, nextblock);
969 
970  for( j = 0; j < ncurvars; ++j )
971  {
972  int var;
973  int oldblock;
974  var = seeedpool->getVarsForCons(cons)[j];
975 
976  oldblock = vartoblock[var];
977  assert((oldblock > 0) && (oldblock <= nextblock));
978 
979  SCIPdebugMessage("\tVar %s ", SCIPvarGetName(seeedpool->getVarForIndex(var)));
980  if( oldblock != consblock )
981  {
982  SCIPdebugPrintf("reset from %d to block %d.\n", oldblock, consblock);
983  vartoblock[var] = consblock;
984  SCIPdebugPrintf("VARINDEX: %d (%d)\n", var, consblock);
985 
986  if( (blockrepresentative[oldblock] != -1) && (blockrepresentative[oldblock] > blockrepresentative[consblock]) )
987  {
988  int oldrepr;
989  oldrepr = blockrepresentative[oldblock];
990  SCIPdebugMessage("\t\tBlock representative from block %d changed from %d to %d.\n", oldblock, blockrepresentative[oldblock], consblock);
991  assert(consblock > 0);
992  blockrepresentative[oldblock] = consblock;
993  if( (oldrepr != consblock) && (oldrepr != oldblock) )
994  {
995  blockrepresentative[oldrepr] = consblock;
996  SCIPdebugMessage("\t\tBlock representative from block %d changed from %d to %d.\n", oldrepr, blockrepresentative[oldrepr], consblock);
997  }
998  }
999  }
1000  else
1001  {
1002  SCIPdebugPrintf("will not be changed from %d to %d.\n", oldblock, consblock);
1003  }
1004  }
1005  assert(consblock >= 1 || consblock == -1);
1006  assert(consblock <= nextblock);
1007 
1008  /* store the constraint block */
1009  if( consblock != -1 )
1010  {
1011  SCIPdebugMessage("cons %s in block %d\n", SCIPconsGetName(seeedpool->getConsForIndex(cons)), consblock);
1012  constoblock[cons] = consblock;
1013  }
1014  else
1015  {
1016  SCIPdebugMessage("ignoring %s\n", SCIPconsGetName(seeedpool->getConsForIndex(cons)));
1017  }
1018  }
1019 
1020  /* postprocess blockrepresentatives */
1021 
1022  int tempblock = 1;
1023  int maxblock = nextblock;
1024 
1025  assert(maxblock >= 1);
1026  assert(blockrepresentative != NULL );
1027  //SCIPdebugPrintf("Blocks: ");
1028 
1029  for( i = 1; i < maxblock; ++i )
1030  {
1031  /* forward replace the representatives */
1032  assert(blockrepresentative[i] >= 0);
1033  assert(blockrepresentative[i] < maxblock);
1034  if( blockrepresentative[i] != i )
1035  blockrepresentative[i] = blockrepresentative[blockrepresentative[i]];
1036  else
1037  {
1038  blockrepresentative[i] = tempblock;
1039  ++tempblock;
1040  }
1041  /* It is crucial that this condition holds */
1042  assert(blockrepresentative[i] <= i);
1043  // SCIPdebugPrintf("%d ", blockrepresentative[i]);
1044  }
1045 // SCIPdebugPrintf("\n");
1046 
1047  /* convert temporary data to detectordata */
1048 
1049  /* fillout Constoblock */
1050  /* convert temporary data to detectordata */
1051  for( i = 0; i < nconss; ++i )
1052  {
1053  int consblock;
1054 
1055  int cons = seeed->getOpenconss()[i];
1056 
1057  if( consismaster[i] )
1058  {
1059  /* notation is misleading: masterconss are only potential master constraints */
1060  /* SCIP_CALL( SCIPhashmapInsert(newconstoblock, (void*) (size_t) cons, (void*) (size_t) (nblocks+1)) ); */
1061  continue;
1062  }
1063 
1064  if( constoblock[cons] == -1)
1065  continue;
1066 
1067  consblock = constoblock[cons]; /*lint !e507*/
1068  assert(consblock > 0);
1069  consblock = blockrepresentative[consblock];
1070  assert(consblock <= nblocks);
1071  newconstoblock[cons] = consblock;
1072  SCIPdebugMessage("%d %s\n", consblock, SCIPconsGetName(seeedpool->getConsForIndex(cons)));
1073  }
1074  (*newSeeed) = new gcg::Seeed(seeed);
1075  SCIP_CALL( (*newSeeed)->assignSeeedFromConstoblockVector(newconstoblock, nblocks) );
1076 
1077  (*newSeeed)->considerImplicits();
1078  (*newSeeed)->refineToBlocks();
1079 
1080  if( exact )
1081  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "isomorph\\_exact");
1082  else
1083  (void) SCIPsnprintf(decinfo, SCIP_MAXSTRLEN, "isomorph\\_extended" );
1084  (*newSeeed)->addDetectorChainInfo(decinfo);
1085 
1086 
1087 
1088  //(*newSeeed)->showScatterPlot(seeedpool);
1089 
1090  SCIPfreeMemoryArray(scip, &vartoblock);
1091  SCIPfreeMemoryArray(scip, &consismaster);
1092  SCIPfreeMemoryArray(scip, &blockrepresentative);
1093 
1094  return SCIP_OKAY;
1095 }
1096 
1098 static
1099 DEC_DECL_FREEDETECTOR(detectorFreeIsomorph)
1100 { /*lint --e{715}*/
1101  DEC_DETECTORDATA *detectordata;
1102 
1103  assert(scip != NULL);
1104  assert(detector != NULL);
1105 
1106  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
1107 
1108  detectordata = DECdetectorGetData(detector);
1109  assert(detectordata != NULL);
1110 
1111  SCIPfreeMemory(scip, &detectordata);
1112 
1113  return SCIP_OKAY;
1114 }
1115 
1117 static
1118 DEC_DECL_INITDETECTOR(detectorInitIsomorph)
1119 { /*lint --e{715}*/
1120  DEC_DETECTORDATA *detectordata;
1121 
1122  assert(scip != NULL);
1123  assert(detector != NULL);
1124 
1125  assert(strcmp(DECdetectorGetName(detector), DEC_DETECTORNAME) == 0);
1126 
1127  detectordata = DECdetectorGetData(detector);
1128  assert(detectordata != NULL);
1129 
1130  detectordata->result = SCIP_SUCCESS;
1131 
1132  return SCIP_OKAY;
1133 }
1134 
1139  int* permutation,
1140  int permsize
1141 )
1142 {
1143  // renumbering from 0 to number of permutations
1144  int nperms = -1;
1145 
1146  for( int i = 0; i < permsize; i++ )
1147  {
1148  SCIPdebugMessage("%d: %d -> ", i, permutation[i]);
1149  if( permutation[i] == -1 )
1150  {
1151  SCIPdebugPrintf("%d\n", permutation[i]);
1152  continue;
1153  }
1154 
1155  if( permutation[i] > nperms && permutation[permutation[i]] > nperms )
1156  {
1157  nperms++;
1158  permutation[i] = nperms;
1159  }
1160  else
1161  {
1162  permutation[i] = permutation[permutation[i]];
1163  }
1164  SCIPdebugPrintf("%d\n", permutation[i]);
1165  }
1166 
1167  return nperms+1;
1168 }
1169 
1172  int* permutation,
1173  int permsize
1174 )
1175 {
1176  int tmp = 0;
1177  // assign to a permutation circle only one number
1178  for( int i = 0; i < permsize; i++ )
1179  {
1180  if( permutation[i] != -1 && permutation[i] != i )
1181  {
1182  tmp = permutation[i];
1183  permutation[i] = permutation[tmp];
1184  }
1185  SCIPdebugMessage("%d %d\n",i, permutation[i]);
1186 
1187  }
1188 }
1189 
1191 static
1192 std::vector< std::vector<int> > getAllSubsets(std::vector<int> set)
1193 {
1194  std::vector< std::vector<int> > subset;
1195  std::vector<int> empty;
1196  subset.push_back( empty );
1197 
1198  for ( size_t i = 0; i < set.size(); ++i )
1199  {
1200  std::vector< std::vector<int> > subsetTemp = subset;
1201 
1202  for (size_t j = 0; j < subsetTemp.size(); ++j)
1203  subsetTemp[j].push_back( set[i] );
1204 
1205  for (size_t j = 0; j < subsetTemp.size(); ++j)
1206  subset.push_back( subsetTemp[j] );
1207  }
1208  return subset;
1209 }
1210 
1212 SCIP_RETCODE reorderPermutations(
1213  SCIP* scip,
1215  int* permutation,
1216  int permsize,
1217  int nperms
1218 )
1219 {
1220  int i;
1221  int* count;
1222  int* order;
1223  int* invorder;
1224 
1225  assert(scip != NULL);
1226  assert(permutation != NULL);
1227  assert(permsize > 0);
1228  assert(nperms > 0);
1229 
1230  SCIP_CALL( SCIPallocMemoryArray(scip, &count, nperms) );
1231  SCIP_CALL( SCIPallocMemoryArray(scip, &order, nperms) );
1232  SCIP_CALL( SCIPallocMemoryArray(scip, &invorder, nperms) );
1233  BMSclearMemoryArray(count, nperms);
1234  BMSclearMemoryArray(order, nperms);
1235  BMSclearMemoryArray(invorder, nperms);
1236 
1237  /* initialize order array that will give a mapping from new to old representatives */
1238  for( i = 0; i < nperms; ++i )
1239  {
1240  order[i] = i;
1241  }
1242 
1243  /* count sizes of orbits */
1244  for( i = 0; i < permsize; ++i )
1245  {
1246  if( permutation[i] >= 0 )
1247  {
1248  count[permutation[i]] += 1;
1249 
1250  SCIPdebugMessage("permutation[i] = %d; count %d\n", permutation[i], count[permutation[i]]);
1251  }
1252  }
1253 
1254  /* sort count and order array */
1255  SCIPsortDownIntInt(count, order, nperms);
1256 
1257 #ifdef SCIP_DEBUG
1258 
1259  for( i = 0; i < nperms; ++i )
1260  {
1261  SCIPdebugMessage("count[%d] = %d, order[%d] = %d\n", i, count[i], i, order[i]);
1262  }
1263 #endif
1264 
1265  /* compute invorder array that gives a mapping from old to new representatives */
1266  for( i = 0; i < nperms; ++i )
1267  {
1268  invorder[order[i]] = i;
1269  SCIPdebugMessage("invorder[%d] = %d\n", order[i], invorder[order[i]]);
1270  }
1271 
1272  SCIPdebugMessage("Best permutation with orbit of size %d, best %d\n", count[0], order[0]);
1273 
1274  /* update representatives of constraints */
1275  for( i = 0; i < permsize; ++i )
1276  {
1277  if( permutation[i] >= 0 )
1278  permutation[i] = invorder[permutation[i]];
1279  }
1280 
1281 
1282  std::vector<int> orbitsizes(0);
1283 
1284  /* compute invorder array that gives a mapping from old to new representatives */
1285  for( i = 0; i < nperms; ++i )
1286  {
1287  int orbitsize;
1288  orbitsize = count[i];
1289 
1291  std::vector<int>::const_iterator orbitsizesIter = orbitsizes.begin();
1292  for(; orbitsizesIter != orbitsizes.end(); ++orbitsizesIter)
1293  {
1294  if(*orbitsizesIter == orbitsize)
1295  break;
1296  }
1297 
1298  if( orbitsizesIter == orbitsizes.end() )
1299  {
1300  seeedpool->addCandidatesNBlocks(orbitsize);
1301 
1302  orbitsizes.push_back(orbitsize);
1303  }
1304  }
1305  std::vector< std::vector<int> > subsetsOfOrbitsizes = getAllSubsets(orbitsizes);
1306 
1307  for(size_t subset = 0; subset < subsetsOfOrbitsizes.size(); ++subset)
1308  {
1309  int greatestCD = 1;
1310 
1311  if(subsetsOfOrbitsizes[subset].size() == 0 || subsetsOfOrbitsizes[subset].size() == 1)
1312  continue;
1313 
1314  greatestCD = gcd(subsetsOfOrbitsizes[subset][0], subsetsOfOrbitsizes[subset][1] );
1315 
1316  for( size_t j = 2; j < subsetsOfOrbitsizes[subset].size() ; ++j)
1317  {
1318  greatestCD = gcd( greatestCD, subsetsOfOrbitsizes[subset][j] );
1319  }
1320 
1321  seeedpool->addCandidatesNBlocks(greatestCD);
1322  }
1323 
1324 
1325  SCIPfreeMemoryArray(scip, &count);
1326  SCIPfreeMemoryArray(scip, &order);
1327  SCIPfreeMemoryArray(scip, &invorder);
1328 
1329  return SCIP_OKAY;
1330 }
1331 
1333 static
1334 SCIP_RETCODE detectIsomorph(
1335  SCIP* scip,
1336  int* ndecdecomps,
1337  DEC_DECOMP*** decdecomps,
1338  DEC_DETECTORDATA* detectordata,
1339  SCIP_RESULT* result,
1340  SCIP_Bool onlysign,
1341  int maxdecomps
1342 )
1343 {
1344  bliss::Graph graph;
1345  bliss::Stats bstats;
1346  AUT_HOOK *ptrhook;
1347  AUT_COLOR *colorinfo;
1348 
1349  int nconss = SCIPgetNConss(scip);
1350  int i;
1351  int unique;
1352  int oldndecdecomps;
1353 
1354  oldndecdecomps = *ndecdecomps;
1355 
1356  detectordata->result = SCIP_SUCCESS;
1357 
1358  colorinfo = new AUT_COLOR();
1359 
1360  colorinfo->setOnlySign(onlysign);
1361 
1362  if( !onlysign )
1363  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting aggregatable structure: ");
1364  else
1365  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting almost aggregatable structure: ");
1366 
1367  SCIP_CALL( setupArrays(scip, colorinfo, &detectordata->result) );
1368  SCIP_CALL( createGraph(scip, *colorinfo, &graph, &detectordata->result) );
1369 
1370  ptrhook = new AUT_HOOK(FALSE, graph.get_nof_vertices(), scip);
1371  for( i = 0; i < nconss; i++ )
1372  {
1373  ptrhook->conssperm[i] = -1;
1374  }
1375 
1376  graph.find_automorphisms(bstats, fhook, ptrhook);
1377 
1378  if( !ptrhook->getBool() )
1379  detectordata->result = SCIP_DIDNOTFIND;
1380 
1381  if( detectordata->result == SCIP_SUCCESS )
1382  {
1383  int nperms;
1384  DEC_DECOMP* newdecomp;
1385  int nmasterconss;
1386  SCIP_CONS** masterconss = NULL;
1387  int p;
1388 
1389  // assign to a permutation circle only one number
1390  collapsePermutation(ptrhook->conssperm, nconss);
1391  // renumbering from 0 to number of permutations
1392  nperms = renumberPermutations(ptrhook->conssperm, nconss);
1393 
1394  // reorder decomposition (corresponding to orbit size)
1395  //SCIP_CALL( reorderPermutations(scip, ptrhook->conssperm, nconss, nperms) );
1396 
1397  if( *ndecdecomps == 0 )
1398  SCIP_CALL( SCIPallocMemoryArray(scip, decdecomps, *ndecdecomps + MIN(maxdecomps, nperms)) ); /*lint !e506*/
1399  else
1400  SCIP_CALL( SCIPreallocMemoryArray(scip, decdecomps, *ndecdecomps + MIN(maxdecomps, nperms)) ); /*lint !e506*/
1401 
1402  int pos = *ndecdecomps;
1403  for( p = *ndecdecomps; p < *ndecdecomps + MIN(maxdecomps, nperms); ++p )
1404  {
1405  SCIP_CALL( SCIPallocMemoryArray(scip, &masterconss, nconss) );
1406 
1407  SCIPdebugMessage("masterconss of decomp %d:\n", p);
1408 
1409  nmasterconss = 0;
1410  for( i = 0; i < nconss; i++ )
1411  {
1412  if( p - *ndecdecomps != ptrhook->conssperm[i] )
1413  {
1414  masterconss[nmasterconss] = SCIPgetConss(scip)[i];
1415  SCIPdebugMessage("%s\n", SCIPconsGetName(masterconss[nmasterconss]));
1416  nmasterconss++;
1417  }
1418  }
1419  SCIPdebugMessage("%d\n", nmasterconss);
1420 
1421  if( nmasterconss < SCIPgetNConss(scip) )
1422  {
1423  SCIP_CALL( DECcreateDecompFromMasterconss(scip, &((*decdecomps)[pos]), masterconss, nmasterconss) );
1424 
1425  SCIPfreeMemoryArray(scip, &masterconss);
1426  }
1427  else
1428  {
1429  SCIPfreeMemoryArray(scip, &masterconss);
1430 
1431  continue;
1432  }
1433 
1434 
1435  SCIP_CALL( DECcreatePolishedDecomp(scip, (*decdecomps)[pos], &newdecomp) );
1436  if( newdecomp != NULL )
1437  {
1438  SCIP_CALL( DECdecompFree(scip, &((*decdecomps)[pos])) );
1439  (*decdecomps)[pos] = newdecomp;
1440  }
1441 
1442  ++pos;
1443  }
1444  *ndecdecomps = pos;
1445 
1446  if( *ndecdecomps > 0 )
1447  {
1448  unique = DECfilterSimilarDecompositions(scip, *decdecomps, *ndecdecomps);
1449  }
1450  else
1451  {
1452  unique = *ndecdecomps;
1453  }
1454 
1455  for( p = unique; p < *ndecdecomps; ++p )
1456  {
1457  SCIP_CALL( DECdecompFree(scip, &((*decdecomps)[p])) );
1458  (*decdecomps)[p] = NULL;
1459  }
1460 
1461  *ndecdecomps = unique;
1462 
1463  if( *ndecdecomps > 0 )
1464  {
1465  SCIP_CALL( SCIPreallocMemoryArray(scip, decdecomps, *ndecdecomps) );
1466  }
1467 
1468  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "found %d (new) decompositions.\n", *ndecdecomps - oldndecdecomps);
1469  }
1470  else
1471  {
1472  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "not found.\n");
1473  }
1474 
1475  if( *ndecdecomps == 0 )
1476  {
1477  SCIPfreeMemoryArrayNull(scip, decdecomps);
1478  }
1479 
1480  delete colorinfo;
1481 
1482  delete ptrhook;
1483 
1484  *result = detectordata->result;
1485 
1486  return SCIP_OKAY;
1487 }
1488 
1490 static
1491 SCIP_RETCODE detectIsomorph(
1492  SCIP* scip,
1493  gcg::Seeed* seeed,
1495  int* nNewSeeeds,
1496  gcg::Seeed*** newSeeeds,
1497  DEC_DETECTORDATA* detectordata,
1498  SCIP_RESULT* result,
1499  SCIP_Bool onlysign,
1500  int maxdecomps
1501 )
1502 {
1503  SCIP_CLOCK* temporaryClock;
1504  SCIP_CALL_ABORT( SCIPcreateClock(scip, &temporaryClock) );
1505  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
1506 
1507  bliss::Graph graph;
1508  bliss::Stats bstats;
1509  AUT_HOOK *ptrhook;
1510  AUT_COLOR *colorinfo;
1511 
1512  int nconss = seeed->getNOpenconss();
1513  int i;
1514  int oldnseeeds;
1515 
1516  oldnseeeds = *nNewSeeeds;
1517 
1518  detectordata->result = SCIP_SUCCESS;
1519 
1520  colorinfo = new AUT_COLOR();
1521 
1522  colorinfo->setOnlySign(onlysign);
1523 
1524 
1525  if( !onlysign )
1526  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting aggregatable structure: ");
1527  else
1528  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Detecting almost aggregatable structure: ");
1529 
1530  SCIP_CALL( setupArrays(scip, colorinfo, &detectordata->result, seeed, seeedpool) );
1531  SCIP_CALL( createGraph(scip, *colorinfo, &graph, &detectordata->result, seeed, seeedpool) );
1532 
1533  ptrhook = new AUT_HOOK(FALSE, graph.get_nof_vertices(), scip, seeed, seeedpool);
1534  for( i = 0; i < nconss; i++ )
1535  {
1536  ptrhook->conssperm[i] = -1;
1537  }
1538 
1539  graph.find_automorphisms(bstats, fhookForSeeeds, ptrhook);
1540 
1541  if( !ptrhook->getBool() )
1542  detectordata->result = SCIP_DIDNOTFIND;
1543 
1544  if( detectordata->result == SCIP_SUCCESS )
1545  {
1546  int nperms;
1547  int nmasterconss;
1548  int* masterconss = NULL;
1549  int p;
1550 
1551  // assign to a permutation circle only one number
1552  collapsePermutation(ptrhook->conssperm, nconss);
1553  // renumbering from 0 to number of permutations
1554  nperms = renumberPermutations(ptrhook->conssperm, nconss);
1555 
1556  // reorder decomposition (corresponding to orbit size)
1557  SCIP_CALL( reorderPermutations(scip, seeedpool, ptrhook->conssperm, nconss, nperms) );
1558 
1559  if( *nNewSeeeds == 0 )
1560  SCIP_CALL( SCIPallocMemoryArray(scip, newSeeeds, *nNewSeeeds + MIN(maxdecomps, nperms)) ); /*lint !e506*/
1561  else
1562  SCIP_CALL( SCIPreallocMemoryArray(scip, newSeeeds, *nNewSeeeds + MIN(maxdecomps, nperms)) ); /*lint !e506*/
1563 
1564  int pos = *nNewSeeeds;
1565 
1566  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
1567  SCIP_Real tempTime = SCIPclockGetTime(temporaryClock);
1568 
1569  for( p = *nNewSeeeds; p < *nNewSeeeds + nperms && pos < *nNewSeeeds + maxdecomps; ++p )
1570  {
1571  SCIP_CALL_ABORT( SCIPresetClock(scip, temporaryClock ) );
1572  SCIP_CALL_ABORT( SCIPstartClock(scip, temporaryClock) );
1573  SCIP_CALL( SCIPallocMemoryArray(scip, &masterconss, nconss) );
1574 
1575  SCIPdebugMessage("masterconss of seeed %d:\n", p);
1576 
1577  nmasterconss = 0;
1578  for( i = 0; i < nconss; i++ )
1579  {
1580  if( p - *nNewSeeeds != ptrhook->conssperm[i] )
1581  {
1582  masterconss[nmasterconss] = seeed->getOpenconss()[i];
1583  SCIPdebugMessage("%s\n", SCIPconsGetName(seeedpool->getConsForIndex(masterconss[nmasterconss])));
1584  nmasterconss++;
1585  }
1586  }
1587  SCIPdebugMessage("%d\n", nmasterconss);
1588 
1589  if( nmasterconss < nconss )
1590  {
1591  SCIP_Bool isduplicate;
1592  int q;
1593 
1594  SCIP_CALL( createSeeedFromMasterconss(scip, &((*newSeeeds)[pos]), masterconss, nmasterconss, seeed, seeedpool, !onlysign) );
1595 
1596  ((*newSeeeds)[pos])->calcHashvalue();
1597  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
1598  (*newSeeeds)[pos]->addClockTime( tempTime + SCIPclockGetTime(temporaryClock) );
1599 
1600  isduplicate = FALSE;
1601 
1602  for( q = 0; q < pos && !isduplicate; ++q )
1603  {
1604  SCIP_CALL( ((*newSeeeds)[pos])->isEqual((*newSeeeds)[q], &isduplicate, TRUE) );
1605  }
1606 
1607 
1608  if( isduplicate )
1609  {
1610  delete (*newSeeeds)[pos];
1611  }
1612  else
1613  {
1614  ++pos;
1615  }
1616 
1617  SCIPfreeMemoryArray(scip, &masterconss);
1618 
1619 
1620  }
1621 
1622  else
1623  {
1624  SCIPfreeMemoryArray(scip, &masterconss);
1625 
1626  SCIP_CALL_ABORT( SCIPstopClock(scip, temporaryClock ) );
1627 
1628  continue;
1629  }
1630  }
1631  *nNewSeeeds = pos;
1632 
1633  if( *nNewSeeeds > 0 )
1634  {
1635  SCIP_CALL( SCIPreallocMemoryArray(scip, newSeeeds, *nNewSeeeds) );
1636  }
1637 
1638  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "found %d (new) decompositions.\n", *nNewSeeeds - oldnseeeds);
1639  }
1640  else
1641  {
1642  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "not found.\n");
1643  }
1644 
1645  if( *nNewSeeeds == 0 )
1646  {
1647  SCIPfreeMemoryArrayNull(scip, newSeeeds);
1648  }
1649 
1650 
1651  delete colorinfo;
1652 
1653 
1654  delete ptrhook;
1655 
1656  *result = detectordata->result;
1657 
1658  SCIP_CALL_ABORT(SCIPfreeClock(scip, &temporaryClock) );
1659 
1660  return SCIP_OKAY;
1661 }
1662 
1663 
1664 //#define detectorPropagateSeeedIsomorph NULL
1665 DEC_DECL_PROPAGATESEEED(detectorPropagateSeeedIsomorph)
1666 {
1667  *result = SCIP_DIDNOTFIND;
1668  DEC_DETECTORDATA* detectordata = DECdetectorGetData(detector);
1669  gcg::Seeed* seeed = seeedPropagationData->seeedToPropagate ;
1670 
1671  seeedPropagationData->nNewSeeeds = 0;
1672  seeedPropagationData->newSeeeds = NULL;
1673 
1674  if(seeed->getNBlocks() != 0 || seeed->getNOpenvars() != seeed->getNVars())
1675  {
1676  *result = SCIP_SUCCESS;
1677  return SCIP_OKAY;
1678  }
1679 
1680  if( detectordata->maxdecompsextend > 0 )
1681  SCIP_CALL( detectIsomorph(scip, seeed, seeedPropagationData->seeedpool, &(seeedPropagationData->nNewSeeeds), &(seeedPropagationData->newSeeeds), detectordata, result, TRUE, detectordata->maxdecompsextend) );
1682 
1683  if( detectordata->maxdecompsexact > 0 )
1684  SCIP_CALL( detectIsomorph(scip, seeed, seeedPropagationData->seeedpool, &(seeedPropagationData->nNewSeeeds), &(seeedPropagationData->newSeeeds), detectordata, result, FALSE, detectordata->maxdecompsexact) );
1685 
1686  for( int i = 0; i < seeedPropagationData->nNewSeeeds; ++i )
1687  {
1688  seeedPropagationData->newSeeeds[i]->refineToMaster();
1689  }
1690 
1691  return SCIP_OKAY;
1692 }
1693 #define detectorExitIsomorph NULL
1694 
1695 
1697 static DEC_DECL_DETECTSTRUCTURE(detectorDetectIsomorph)
1698 { /*lint -esym(429,ptrhook)*/
1699 
1700  *result = SCIP_DIDNOTFIND;
1701 
1702  *ndecdecomps = 0;
1703  *decdecomps = NULL;
1704 
1705 
1706  if( detectordata->legacyextend)
1707  SCIP_CALL( detectIsomorph(scip, ndecdecomps, decdecomps, detectordata, result, TRUE, detectordata->maxdecompsextend) );
1708 
1710  if( detectordata->legacyexact)
1711  SCIP_CALL( detectIsomorph(scip, ndecdecomps, decdecomps, detectordata, result, FALSE, detectordata->maxdecompsexact) );
1712 
1713  return SCIP_OKAY;
1714 }
1715 #define detectorFinishSeeedIsomorph NULL
1716 
1717 #define detectorPostprocessSeeedIsomorph NULL
1718 
1719 static
1720 DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveIsomorph)
1721 {
1722  char setstr[SCIP_MAXSTRLEN];
1723  const char* name = DECdetectorGetName(detector);
1724  int newval;
1725  SCIP_Real modifier;
1726 
1727  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
1728  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
1729 
1730  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
1731  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE) );
1732 
1733  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
1734  SCIP_CALL( SCIPsetBoolParam(scip, setstr, TRUE ) );
1735 
1736  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxcallround", name);
1737  SCIP_CALL( SCIPgetIntParam(scip, setstr, &newval) );
1738  ++newval;
1739  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1740  SCIPinfoMessage(scip, NULL, "After Setting %s = %d\n", setstr, newval);
1741 
1742 
1743  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origmaxcallround", name);
1744  SCIP_CALL( SCIPgetIntParam(scip, setstr, &newval) );
1745  ++newval;
1746  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1747  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1748 
1749  /* check if no problem is read */
1750  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
1751  {
1752  newval = MAX( 0, DEFAULT_MAXDECOMPSEXACT );
1753  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsexact", name);
1754  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1755  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1756 
1757  newval = MAX( 0, DEFAULT_MAXDECOMPSEXTEND );
1758  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsextend", name);
1759  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1760  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1761  return SCIP_OKAY;
1762  }
1763 
1764  modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
1765 
1766  modifier = log(modifier) / log(2);
1767 
1768  if (!SCIPisFeasPositive(scip, modifier) )
1769  modifier = -1.;
1770 
1771  modifier = SCIPfloor(scip, modifier);
1772  modifier += 0;
1773 
1774  newval = MAX( 0, DEFAULT_MAXDECOMPSEXACT - modifier );
1775  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsexact", name);
1776  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1777  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1778 
1779  newval = MAX( 0, DEFAULT_MAXDECOMPSEXTEND - modifier );
1780  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsextend", name);
1781  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1782  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1783 
1784  return SCIP_OKAY;
1785 
1786 }
1787 
1788 
1789 static
1790 DEC_DECL_SETPARAMDEFAULT(setParamDefaultIsomorph)
1791 {
1792  char setstr[SCIP_MAXSTRLEN];
1793  int newval;
1794  SCIP_Real modifier;
1795 
1796  const char* name = DECdetectorGetName(detector);
1797 
1798  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
1799  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLED) );
1800 
1801  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
1802  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDORIGINAL) );
1803 
1804  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
1805  SCIP_CALL( SCIPsetBoolParam(scip, setstr, DEC_ENABLEDFINISHING ) );
1806 
1807 
1808  /* check if no problem is read */
1809  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
1810  {
1811  newval = MAX( 0, DEFAULT_MAXDECOMPSEXACT );
1812  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsexact", name);
1813  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1814  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1815 
1816  newval = MAX( 0, DEFAULT_MAXDECOMPSEXTEND );
1817  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsextend", name);
1818  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1819  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1820  return SCIP_OKAY;
1821  }
1822 
1823 
1824  modifier = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) ) / SET_MULTIPLEFORSIZETRANSF;
1825 
1826  modifier = log(modifier) / log(2);
1827 
1828  if (!SCIPisFeasPositive(scip, modifier) )
1829  modifier = -1.;
1830 
1831  modifier = SCIPfloor(scip, modifier);
1832  modifier += 2;
1833 
1834  newval = MAX( 0, DEFAULT_MAXDECOMPSEXACT - modifier );
1835  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsexact", name);
1836  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1837  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1838 
1839  newval = MAX( 0, DEFAULT_MAXDECOMPSEXTEND - modifier );
1840  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsextend", name);
1841  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1842  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1843 
1844 
1845 
1846  return SCIP_OKAY;
1847 
1848 }
1849 
1850 static
1851 DEC_DECL_SETPARAMFAST(setParamFastIsomorph)
1852 {
1853  char setstr[SCIP_MAXSTRLEN];
1854  int newval;
1855 
1856  const char* name = DECdetectorGetName(detector);
1857 
1858  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/enabled", name);
1859  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
1860 
1861  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origenabled", name);
1862  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE) );
1863 
1864  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/finishingenabled", name);
1865  SCIP_CALL( SCIPsetBoolParam(scip, setstr, FALSE ) );
1866 
1867  /* check if no problem is read */
1868  if( SCIPgetStage(scip) < SCIP_STAGE_PROBLEM )
1869  {
1870  newval = MAX( 0, DEFAULT_MAXDECOMPSEXACT );
1871  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsexact", name);
1872  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1873  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1874 
1875  newval = MAX( 0, DEFAULT_MAXDECOMPSEXTEND );
1876  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsextend", name);
1877  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1878  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1879  return SCIP_OKAY;
1880  }
1881 
1882 
1883 
1884  newval = ( (SCIP_Real)SCIPgetNConss(scip) + (SCIP_Real)SCIPgetNVars(scip) > SET_MULTIPLEFORSIZETRANSF) ? 0 : 1;
1885  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsexact", name);
1886  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1887  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1888 
1889  newval = 0;
1890  (void) SCIPsnprintf(setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxdecompsextend", name);
1891  SCIP_CALL( SCIPsetIntParam(scip, setstr, newval ) );
1892  SCIPinfoMessage(scip, NULL, "%s = %d\n", setstr, newval);
1893 
1894 
1895  return SCIP_OKAY;
1896 
1897 }
1898 
1899 
1900 /*
1901  * detector specific interface methods
1902  */
1903 
1904 
1906 extern "C"
1908  SCIP* scip
1909  )
1910 {
1911  DEC_DETECTORDATA* detectordata;
1912 
1913  detectordata = NULL;
1914 
1915  SCIP_CALL( SCIPallocMemory(scip, &detectordata) );
1916  assert(detectordata != NULL);
1917 
1918 
1919 
1921  detectordata, detectorDetectIsomorph, detectorFreeIsomorph, detectorInitIsomorph, detectorExitIsomorph, detectorPropagateSeeedIsomorph, NULL, NULL, detectorFinishSeeedIsomorph, detectorPostprocessSeeedIsomorph, setParamAggressiveIsomorph, setParamDefaultIsomorph, setParamFastIsomorph) );
1922 
1923  /* add isomorph constraint handler parameters */
1924  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/isomorph/maxdecompsexact",
1925  "Maximum number of solutions/decompositions with exact detection", &detectordata->maxdecompsexact, FALSE,
1926  DEFAULT_MAXDECOMPSEXACT, 0, INT_MAX, NULL, NULL) );
1927 
1928  SCIP_CALL( SCIPaddIntParam(scip, "detection/detectors/isomorph/maxdecompsextend",
1929  "Maximum number of solutions/decompositions with extended detection", &detectordata->maxdecompsextend, FALSE,
1930  DEFAULT_MAXDECOMPSEXTEND, 0, INT_MAX, NULL, NULL) );
1931 
1932  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/isomorph/legacyextend",
1933  "is extended detection activated when doing legacy detection", &detectordata->legacyextend, FALSE,
1934  DEFAULT_LEGACYEXTEND, NULL, NULL) );
1935 
1936  SCIP_CALL( SCIPaddBoolParam(scip, "detection/detectors/isomorph/legacyexact",
1937  "is exact detection activated when doing legacy detection", &detectordata->legacyexact, FALSE,
1938  DEFAULT_LEGACYEXACT, NULL, NULL) );
1939 
1940 
1941  return SCIP_OKAY;
1942 }
#define DEC_ENABLEDFINISHING
static SCIP_RETCODE allocMemory(SCIP *scip, AUT_COLOR *colorinfo, int nconss, int nvars)
#define DEC_ENABLED
static DEC_DECL_INITDETECTOR(detectorInitIsomorph)
SCIP_RETCODE reorderPermutations(SCIP *scip, gcg::Seeedpool *seeedpool, int *permutation, int permsize, int nperms)
#define DEC_MAXCALLROUNDORIGINAL
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
static DEC_DECL_SETPARAMFAST(setParamFastIsomorph)
const int * getOpenconss()
returns array containing constraints not assigned yet
#define DEC_SKIP
void collapsePermutation(int *permutation, int permsize)
GCG interface methods.
void addCandidatesNBlocks(int candidate)
adds and counts how often added a candidate for block size and
struct struct_var AUT_VAR
Definition: pub_bliss.h:49
DEC_DETECTORDATA * DECdetectorGetData(DEC_DETECTOR *detector)
returns the data of the provided detector
detector for pricing problems that can be aggregated (uses bliss)
gcg::Seeed * getSeeed()
static SCIP_RETCODE setupArrays(SCIP *scip, AUT_COLOR *colorinfo, SCIP_RESULT *result)
int getNVars()
returns number of vars
const SCIP_Real * getValsForCons(int consIndex)
returns the nonzero coefficients of the coefficient matrix for a constraint
struct struct_cons AUT_CONS
Definition: pub_bliss.h:48
SCIP_RETCODE DECcreatePolishedDecomp(SCIP *scip, DEC_DECOMP *decomp, DEC_DECOMP **newdecomp)
Definition: decomp.c:4255
#define detectorPostprocessSeeedIsomorph
helper functions for automorphism detection
int gcd(int a, int b)
struct struct_coef AUT_COEF
Definition: pub_bliss.h:50
#define DEFAULT_LEGACYEXACT
static SCIP_RETCODE createGraph(SCIP *scip, AUT_COLOR colorinfo, bliss::Graph *graph, SCIP_RESULT *result)
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:433
#define DEC_LEGACYMODE
static SCIP_RETCODE detectIsomorph(SCIP *scip, int *ndecdecomps, DEC_DECOMP ***decdecomps, DEC_DETECTORDATA *detectordata, SCIP_RESULT *result, SCIP_Bool onlysign, int maxdecomps)
int DECfilterSimilarDecompositions(SCIP *scip, DEC_DECOMP **decs, int ndecs)
Definition: decomp.c:3983
struct struct_colorinformation AUT_COLOR
Definition: pub_bliss.h:51
static DEC_DECL_DETECTSTRUCTURE(detectorDetectIsomorph)
SCIP_RETCODE DECdecompFree(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:525
void setBool(SCIP_Bool aut)
int getNOpenvars()
returns size of vector containing variables not assigned yet
#define DEC_DESC
gcg::Seeed * seeed
#define DEC_ENABLEDORIGINAL
SCIP_VAR * getVarForIndex(int varIndex)
returns SCIP variable related to a variable index
#define DEC_PRIORITY
gcg::Seeedpool * getSeeedpool()
#define DEC_USEFULRECALL
gcg::Seeedpool * seeedpool
int getNConss()
returns the number of variables considered in the seeedpool
SCIP_RETCODE DECcreateDecompFromMasterconss(SCIP *scip, DEC_DECOMP **decomp, SCIP_CONS **masterconss, int nmasterconss)
Definition: decomp.c:2688
SCIP_Bool getBool()
#define DEFAULT_MAXDECOMPSEXACT
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:620
#define DEC_FREQCALLROUND
SCIP_Bool legacyexact
various SCIP helper methods
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
static void freeMemory(SCIP *scip, AUT_COLOR *colorinfo)
struct struct_hook AUT_HOOK
static void fhookForSeeeds(void *user_param, unsigned int N, const unsigned int *aut)
static DEC_DECL_FREEDETECTOR(detectorFreeIsomorph)
#define DEC_MAXCALLROUND
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:489
SCIP_Bool aut
int renumberPermutations(int *permutation, int permsize)
static void fhook(void *user_param, unsigned int N, const unsigned int *aut)
SCIP_RETCODE SCIPincludeDetectorIsomorphism(SCIP *scip)
#define DEFAULT_MAXDECOMPSEXTEND
int getNBlocks()
returns the number of blocks
#define DEFAULT_LEGACYEXTEND
#define DEC_DECCHAR
#define DEC_ENABLEDPOSTPROCESSING
static DEC_DECL_SETPARAMAGGRESSIVE(setParamAggressiveIsomorph)
#define detectorExitIsomorph
public methods for GCG variables
#define DEC_DETECTORNAME
#define SET_MULTIPLEFORSIZETRANSF
SCIP_RETCODE DECincludeDetector(SCIP *scip, const char *name, const char decchar, const char *description, int freqCallRound, int maxCallRound, int minCallRound, int freqCallRoundOriginal, int maxCallRoundOriginal, int minCallRoundOriginal, int priority, SCIP_Bool enabled, SCIP_Bool enabledOriginal, SCIP_Bool enabledFinishing, SCIP_Bool enabledPostprocessing, SCIP_Bool skip, SCIP_Bool usefulRecall, SCIP_Bool legacymode, DEC_DETECTORDATA *detectordata, DEC_DECL_DETECTSTRUCTURE((*detectStructure)), DEC_DECL_FREEDETECTOR((*freeDetector)), DEC_DECL_INITDETECTOR((*initDetector)), DEC_DECL_EXITDETECTOR((*exitDetector)), DEC_DECL_PROPAGATESEEED((*propagateSeeedDetector)), DEC_DECL_PROPAGATEFROMTOOLBOX((*propagateFromToolboxDetector)), DEC_DECL_FINISHFROMTOOLBOX((*finishFromToolboxDetector)), DEC_DECL_FINISHSEEED((*finishSeeedDetector)), DEC_DECL_POSTPROCESSSEEED((*postprocessSeeedDetector)), DEC_DECL_SETPARAMAGGRESSIVE((*setParamAggressiveDetector)), DEC_DECL_SETPARAMDEFAULT((*setParamDefaultDetector)),)
includes one detector
DEC_DECL_PROPAGATESEEED(detectorPropagateSeeedIsomorph)
unsigned int n
struct gcg::subset subset
static DEC_DECL_SETPARAMDEFAULT(setParamDefaultIsomorph)
int getNOpenconss()
returns size of vector containing constraints not assigned yet
#define DEC_MINCALLROUND
class with functions for seeed pool where a seeed is a (potentially incomplete) description of a deco...
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
SCIP_RESULT result
Definition: dec_dbscan.cpp:88
SCIP_Bool legacyextend
#define DEC_FREQCALLROUNDORIGINAL
#define detectorFinishSeeedIsomorph
constraint handler for structure detection
#define DEC_MINCALLROUNDORIGINAL
SCIP_CONS * getConsForIndex(int consIndex)
returns the SCIP constraint related to a constraint index
SCIP_RETCODE createSeeedFromMasterconss(SCIP *scip, gcg::Seeed **newSeeed, int *masterconss, int nmasterconss, gcg::Seeed *seeed, gcg::Seeedpool *seeedpool, SCIP_Bool exact)
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
struct_hook(SCIP_Bool aut, unsigned int n, SCIP *scip)
public methods for working with decomposition structures
SCIP * getScip()
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
static std::vector< std::vector< int > > getAllSubsets(std::vector< int > set)