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-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 
37 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
38 
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_seeed.h"
48 #include "class_seeedpool.h"
49 
50 #include <cstring>
51 
52 typedef struct struct_hook2 AUT_HOOK2;
53 
54 
57 {
58  SCIP_Bool aut;
59  unsigned int n;
60  SCIP_HASHMAP* varmap;
61  SCIP_HASHMAP* consmap;
62  SCIP** scips;
63  int* nodemap;
64  int* conssperm;
67  std::vector<int> blocks;
68  SCIP* scip;
69  int ncalls;
70 
71 
74  SCIP_HASHMAP* varmap,
75  SCIP_HASHMAP* consmap,
76  SCIP_Bool aut,
77  unsigned int n,
78  SCIP** scips
79  );
80 
82  ~struct_hook2();
83 
84 
86  SCIP_Bool getBool();
87 
89  void setBool(SCIP_Bool aut);
90 
93  gcg::Seeedpool* seeedpool,
94  gcg::Seeed* seeed,
95  std::vector<int> blocks
96  );
97 
99  unsigned int getNNodes();
100 
102  SCIP_HASHMAP* getVarHash();
103 
105  SCIP_HASHMAP* getConsHash();
106 
108  SCIP** getScips();
109 
110 
111 };
112 
113 
114 
115 
116 void struct_hook2::setBool( SCIP_Bool aut_ )
117 {
118  aut = aut_;
119 }
120 
121 
123  gcg::Seeedpool* givenseeedpool,
124  gcg::Seeed* givenseeed,
125  std::vector<int> givenblocks
126 )
127 {
128  this->seeedpool = givenseeedpool;
129  this->seeed = givenseeed;
130  this->blocks = givenblocks;
131 
132  SCIP_CALL_ABORT( SCIPallocMemoryArray(seeedpool->getScip(), &(this->conssperm), seeedpool->getNConss() ) ); /*lint !e666*/
133 
134  scip = seeedpool->getScip();
135 
136 }
137 
139 { /*lint -esym(1540,struct_hook::conssperm) */
140  if( conssperm != NULL )
141  SCIPfreeMemoryArrayNull(scip, &conssperm);
142  conssperm = NULL;
143  seeedpool = NULL;
144  seeed = NULL;
145 }
146 
147 
148 
150 {
151  return aut;
152 }
153 
155 {
156  return n;
157 }
158 
160 {
161  return varmap;
162 }
163 
165 {
166  return consmap;
167 }
168 
170 {
171  return scips;
172 }
173 
176  SCIP_HASHMAP* varmap_,
177  SCIP_HASHMAP* consmap_,
178  SCIP_Bool aut_,
179  unsigned int n_,
180  SCIP** scips_
181  )
182 {
183  size_t i;
184  aut = aut_;
185  n = n_;
186  consmap = consmap_;
187  varmap = varmap_;
188  scips = scips_;
189  SCIP_CALL_ABORT( SCIPallocMemoryArray(scip, &nodemap, n_) ); /*lint !e666*/
190  for (i = 0; i < n_; ++i)
191  nodemap[i] = -1;
192 
193  conssperm = NULL;
194  seeedpool = NULL;
195  seeed = NULL;
196  blocks = std::vector<int>(0);
197 
198  ncalls = 0;
199 }
200 
203 static
204 void fhook(
205  void* user_param,
206  unsigned int N,
207  const unsigned int* aut
208  )
209 { /*lint -e715*/
210 
211  unsigned int i;
212  unsigned int j;
213  unsigned int n;
214  int nvars;
215  int nconss;
216  SCIP_VAR** vars1;
217  SCIP_VAR** vars2;
218  SCIP_CONS** conss1;
219  SCIP_CONS** conss2;
220  SCIP_Bool newdetection;
221  SCIP* seeedscip;
223  gcg::Seeed* seeed;
224  AUT_HOOK2* hook = (AUT_HOOK2*) user_param;
225 
226  j = 0;
227  n = hook->getNNodes();
228 
230  newdetection = (hook->seeedpool != NULL) ;
231  seeed = hook->seeed;
232  seeedpool = hook->seeedpool;
233  seeedscip = NULL;
234 
235  if(hook->getBool())
236  return;
237 
238  ++hook->ncalls;
239 
240  if( hook->ncalls > 100 )
241  {
242  hook->setBool(false);
243  return;
244  }
245 
246  // SCIPdebugMessage("Looking for a permutation from [0,%u] bijective to [%u:%u] (N=%u) \n", n/2-1, n/2, n-1, N);
247  for( i = 0; i < n / 2; i++ )
248  {
249  assert(aut[i] < INT_MAX);
250 
251  if( (aut[i]) >= n / 2 && hook->nodemap[i] == -1 )
252  {
253  assert(aut[i] < n);
254 // SCIPdebugMessage("current generator: %u -> %u\n", i, aut[i]);
255  hook->nodemap[i] = aut[i];
256  }
257  }
258 
259  for( i = 0; i < n / 2; i++ )
260  {
261 // SCIPdebugMessage("general mapping : %u -> %u\n", i, hook->nodemap[i]);
262  if( hook->nodemap[i] >= (int) n / 2 )
263  ++j;
264  }
265 
266  if( j == n / 2 )
267  {
268  hook->setBool(TRUE);
269  }
270 
271  for( i = n; i < N; ++i )
272  {
273  if( aut[i] != i )
274  {
275  // SCIPdebugMessage("Master %u -> %u not the identity, no decomposition possible!\n", i, aut[i]);
276  hook->setBool(false);
277  break;
278  }
279  }
280 
281 // SCIPdebugMessage("Permutation %s found.\n", hook->getBool() ? "":"not");
282 // SCIPdebugMessage("j = %u\n", j);
283 
284  if( !hook->getBool() )
285  return;
286 
287 
288  if( newdetection )
289  nvars = seeed->getNVarsForBlock(hook->blocks[0]);
290  else
291  nvars = SCIPgetNVars(hook->getScips()[0]);
292  if( newdetection )
293  assert(nvars == seeed->getNVarsForBlock(hook->blocks[1]) );
294  else
295  assert(nvars == SCIPgetNVars(hook->getScips()[1]));
296 
297  if( newdetection )
298  {
299  seeedscip = seeedpool->getScip();
300 
301  SCIP_CALL_ABORT(SCIPallocBufferArray(seeedscip, &vars1, nvars ));
302  SCIP_CALL_ABORT(SCIPallocBufferArray(seeedscip, &vars2, nvars ));
303  nconss = seeed->getNConssForBlock(hook->blocks[0]);
304  assert(nconss == seeed->getNConssForBlock(hook->blocks[1]));
305 
306  SCIP_CALL_ABORT( SCIPallocBufferArray(seeedscip, &conss1, nconss ) );
307  SCIP_CALL_ABORT( SCIPallocBufferArray(seeedscip, &conss2, nconss ) );
308 
309  for( int v = 0; v < nvars; ++v )
310  {
311  vars1[v] = seeedpool->getVarForIndex(seeed->getVarsForBlock(hook->blocks[0])[v]);
312  vars2[v] = seeedpool->getVarForIndex(seeed->getVarsForBlock(hook->blocks[1])[v]);
313  }
314 
315  for( int c = 0; c < nconss; ++c )
316  {
317  conss1[c] = seeedpool->getConsForIndex(seeed->getConssForBlock(hook->blocks[0])[c]);
318  conss2[c] = seeedpool->getConsForIndex(seeed->getConssForBlock(hook->blocks[1])[c]);
319  }
320  }
321  else
322  {
323  vars1 = SCIPgetVars(hook->getScips()[0]);
324  vars2 = SCIPgetVars(hook->getScips()[1]);
325  nconss = SCIPgetNConss(hook->getScips()[0]);
326  assert(nconss == SCIPgetNConss(hook->getScips()[1]));
327 
328  conss1 = SCIPgetConss(hook->getScips()[0]);
329  conss2 = SCIPgetConss(hook->getScips()[1]);
330  }
331 
332  for( i = 0; i < (unsigned int) nvars+nconss; i++ )
333  {
334  /* Assuming the following layout:
335  * 0 ... nconss-1 = vertex ids for constraints
336  * nconss ... nconss+nvars-1 = vertex ids for variables
337  * nconss+nvars ... n-1 = nonzero entries (not relevant)
338  */
339  if( i < (unsigned int) nconss )
340  {
341  unsigned int consindex = i;
342  unsigned int consindex2 = hook->nodemap[i]-n/2;
343  assert( consindex2 < (unsigned int) nconss);
344  SCIP_CONS* cons1 = conss1[consindex];
345  SCIP_CONS* cons2 = conss2[consindex2];
346  SCIP_CALL_ABORT( SCIPhashmapInsert(hook->getConsHash(), cons2, cons1) );
347  SCIPdebugMessage("cons <%s> <-> cons <%s>\n", SCIPconsGetName(cons2), SCIPconsGetName(cons1));
348  }
349  else if( i < (unsigned int) nvars+nconss )
350  {
351  unsigned int varindex = i-nconss;
352  unsigned int varindex2 = hook->nodemap[i]-nconss-n/2;
353  assert( varindex2 < (unsigned int) nvars);
354  SCIP_VAR* var1 = vars1[varindex];
355  SCIP_VAR* var2 = vars2[varindex2];
356  SCIP_CALL_ABORT( SCIPhashmapInsert(hook->getVarHash(), var2, var1) );
357  SCIPdebugMessage("var <%s> <-> var <%s>\n", SCIPvarGetName(var2), SCIPvarGetName(var1));
358  }
359  }
360 
361  if( newdetection )
362  {
363  seeedscip = seeedpool->getScip();
364  SCIPfreeBufferArray(seeedscip, &conss1);
365  SCIPfreeBufferArray(seeedscip, &conss2);
366  SCIPfreeBufferArray(seeedscip, &vars1);
367  SCIPfreeBufferArray(seeedscip, &vars2);
368  }
369 }
370 
372 static
373 SCIP_RETCODE testScipVars(
374  SCIP* scip1,
375  SCIP* scip2,
376  SCIP_RESULT* result
377  )
378 {
379  if(SCIPgetNVars(scip1) != SCIPgetNVars(scip2))
380  {
381  *result = SCIP_DIDNOTFIND;
382  }
383  return SCIP_OKAY;
384 }
385 
386 
387 
388 
390 static
391 SCIP_RETCODE testScipCons(
392  SCIP* scip1,
393  SCIP* scip2,
394  SCIP_RESULT* result
395  )
396 {
397  if(SCIPgetNConss(scip1) != SCIPgetNConss(scip2))
398  {
399  *result = SCIP_DIDNOTFIND;
400  }
401  return SCIP_OKAY;
402 }
403 
404 
406 static SCIP_RETCODE allocMemory(
407  SCIP* scip,
408  AUT_COLOR* colorinfo,
409  int nconss,
410  int nvars
411  )
412 {
413  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarraycoefs, ((size_t) nconss * nvars)));
414  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarrayvars, (size_t) nvars));
415  SCIP_CALL( SCIPallocMemoryArray(scip, &colorinfo->ptrarrayconss, (size_t) nconss));
416  return SCIP_OKAY;
417 }
418 
420 static SCIP_RETCODE allocMemoryNewDetection(
422  AUT_COLOR* colorinfo,
423  int nconss,
424  int nvars,
425  int ncoeffs
426  )
427 {
428  SCIP_CALL( SCIPallocMemoryArray(seeedpool->getScip(), &colorinfo->ptrarraycoefs, ((size_t) ncoeffs )));
429  SCIP_CALL( SCIPallocMemoryArray(seeedpool->getScip(), &colorinfo->ptrarrayvars, (size_t) nvars));
430  SCIP_CALL( SCIPallocMemoryArray(seeedpool->getScip(), &colorinfo->ptrarrayconss, (size_t) nconss));
431  return SCIP_OKAY;
432 }
433 
434 
435 
437 static SCIP_RETCODE reallocMemory(
438  SCIP* scip,
439  AUT_COLOR* colorinfo,
440  int nconss,
441  int nvars
442  )
443 {
444  SCIP_CALL( SCIPreallocMemoryArray(scip, &colorinfo->ptrarraycoefs, (size_t) colorinfo->lencoefsarray + ((size_t) 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 
452 static
453 SCIP_RETCODE freeMemory(
454  SCIP* scip,
455  AUT_COLOR* colorinfo
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 
480 static
481 SCIP_RETCODE setuparrays(
482  SCIP* origscip,
483  SCIP** scips,
484  int nscips,
485  AUT_COLOR* colorinfo,
486  SCIP_RESULT* result
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 = GCGgetLinearOrigMasterConss(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  SCIP_Real* curvals = SCIPgetValsLinear(origscip, mastercons);
594  ncurvars = SCIPgetNVarsLinear(origscip, mastercons);
595 
596  /* add right color for master constraint */
597  AUT_CONS* scons = new AUT_CONS(origscip, mastercons);
598  SCIP_CALL( colorinfo->insert(scons, &added) );
599 
600  /* if it hasn't been added, it is already present */
601  if(!added)
602  delete scons;
603 
604  for( j = 0; j < ncurvars; ++j )
605  {
606  AUT_COEF* scoef = new AUT_COEF(origscip, curvals[j] );
607 
608  added = FALSE;
609 
610  if( !SCIPisZero(origscip, scoef->getVal()) )
611  {
612  SCIP_CALL( colorinfo->insert(scoef, &added) );
613  }
614 
615  if( !added )
616  delete scoef;
617  }
618  }
619 
620  return SCIP_OKAY;
621 }
622 
623 
625 static
628  gcg::Seeed* seeed,
629  int nblocks,
630  std::vector<int> blocks,
631  AUT_COLOR* colorinfo,
632  SCIP_RESULT* result
633  )
634 { /*lint -esym(593, scoef) */
635  SCIP* scip;
636  int i;
637  int j;
638  int b;
639  int nconss;
640  int nvars;
641  int ncoeffs;
642  SCIP_Bool added;
643 
644 
645  added = FALSE;
646 
647  scip = seeedpool->getScip();
648 
649  //allocate max n of coefarray, varsarray, and boundsarray in origscip
650  nconss = seeed->getNConssForBlock(blocks[0]) ;
651  nvars = seeed->getNVarsForBlock(blocks[0]) ;
652  ncoeffs = seeed->getNCoeffsForBlock( blocks[0]);
653  SCIP_CALL( allocMemoryNewDetection(seeedpool, colorinfo, nconss*nblocks+seeed->getNMasterconss(), nvars*nblocks, ncoeffs*nblocks + seeed->getNCoeffsForMaster() ) );
654  colorinfo->setOnlySign(FALSE);
655 
656  for( b = 0; b < nblocks && *result == SCIP_SUCCESS; ++b )
657  {
658  int block = blocks[b];
659 
660  SCIPdebugMessage("Handling block %i (id %d %d x %d)\n", b, block, seeed->getNConssForBlock(blocks[b]), seeed->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 = seeedpool->getVarForIndex( seeed->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 = seeed->getConssForBlock(block)[i];
687  cons = seeedpool->getConsForIndex( consid );
688 
689  //ncurvars = GCGconsGetNVars(scip, conss[i]); //SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(origscip), SCIPgetNVars(scip1)+1) );
690 
691  if( seeedpool->getNVarsForCons(consid) == 0 )
692  continue;
693 
694  AUT_CONS* scons = new AUT_CONS(scip, cons);
695  //add to pointer array iff it doesn't exist
696  SCIP_CALL( colorinfo->insert(scons, &added) );
697  if( b > 0 && added)
698  {
699  *result = SCIP_DIDNOTFIND;
700  break;
701  }
702  //otherwise free allocated memory
703  if( !added )
704  delete scons;
705 
706  //save the properties of variables of the constraints in a struct array and in a sorted pointer array
707  for( j = 0; j < seeedpool->getNVarsForCons(consid); j++ )
708  {
709  SCIP_Real val;
710  AUT_COEF* scoef;
711  val = seeedpool->getVal(consid, seeedpool->getVarsForCons(consid)[j]);
712  scoef = new AUT_COEF(scip, val );
713  //test, whether the coefficient is not zero
714  if( !SCIPisZero(seeedpool->getScip(), scoef->getVal()) )
715  {
716  //add to pointer array iff it doesn't exist
717  SCIP_CALL( colorinfo->insert(scoef, &added) );
718  if( b > 0 && added)
719  {
720  *result = SCIP_DIDNOTFIND;
721  break;
722  }
723  }
724  //otherwise free allocated memory
725  if( !added )
726  delete scoef;
727  }
728  }
729  }
730 
731  /* add color information for master constraints */
732 
733 
734 
735  for( i = 0; i < seeed->getNMasterconss() && *result == SCIP_SUCCESS; ++i )
736  {
737  int masterconsid;
738  SCIP_CONS* mastercons;
739 
740  masterconsid = seeed->getMasterconss()[i];
741  mastercons = seeedpool->getConsForIndex(masterconsid);
742 
743  /* add right color for master constraint */
744  AUT_CONS* scons = new AUT_CONS(seeedpool->getScip(), mastercons);
745  SCIP_CALL( colorinfo->insert(scons, &added) );
746 
747  /* if it hasn't been added, it is already present */
748  if(!added)
749  delete scons;
750 
751  for( j = 0; j < seeedpool->getNVarsForCons(masterconsid); ++j )
752  {
753  AUT_COEF* scoef;
754  int varid;
755 
756  varid = seeedpool->getVarsForCons(masterconsid)[j];
757  scoef= new AUT_COEF(seeedpool->getScip(), seeedpool->getVal(masterconsid, varid) );
758 
759  added = FALSE;
760 
761  if( !SCIPisZero(seeedpool->getScip(), scoef->getVal()) )
762  {
763  SCIP_CALL( colorinfo->insert(scoef, &added) );
764  }
765 
766  if( !added )
767  delete scoef;
768  }
769  }
770 
771  return SCIP_OKAY;
772 }
773 
774 
775 
777 static
778 SCIP_RETCODE createGraph(
779  SCIP* origscip,
780  SCIP** scips,
781  int nscips,
782  int* pricingindices,
783  AUT_COLOR colorinfo,
784  bliss::Graph* graph,
785  int* pricingnodes,
786  SCIP_RESULT* result
787  )
788 {
789  int i;
790  int j;
791  int s;
792  int ncurvars;
793  int curvar;
794  int* nnodesoffset = NULL;
795  int color;
796 
797  SCIP_VAR** curvars = NULL;
798  SCIP_Real* curvals = NULL;
799 
800  int nnodes = 0;
801  //building the graph out of the arrays
802  bliss::Graph* h = graph;
803 
804  int* pricingnonzeros = NULL;
805  int* mastercoefindex = NULL;
806  SCIP_CALL( SCIPallocMemoryArray(origscip, &pricingnonzeros, nscips) );
807  SCIP_CALL( SCIPallocMemoryArray(origscip, &nnodesoffset, nscips) );
808  SCIP_CALL( SCIPallocMemoryArray(origscip, &mastercoefindex, nscips) );
809  BMSclearMemoryArray(pricingnonzeros, nscips);
810  BMSclearMemoryArray(nnodesoffset, nscips);
811  BMSclearMemoryArray(mastercoefindex, nscips);
812 
813  SCIP_CONS** origmasterconss = GCGgetLinearOrigMasterConss(origscip);
814  int nmasterconss = GCGgetNMasterConss(origscip);
815 
816  for( s = 0; s < nscips && *result == SCIP_SUCCESS; ++s)
817  {
818  SCIPdebugMessage("Pricing problem %d\n", pricingindices[s]);
819  SCIP *scip = scips[s];
820  int nconss = SCIPgetNConss(scip);
821  int nvars = SCIPgetNVars(scip);
822  SCIP_CONS** conss = SCIPgetConss(scip);
823  SCIP_VAR** vars = SCIPgetVars(scip);
824 
825  int z = 0;
826 
827  nnodesoffset[s] = nnodes;
828 
829  //add a node for every constraint
830  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
831  {
832  ncurvars = GCGconsGetNVars(scip, conss[i]);
833  if( ncurvars == 0 )
834  continue;
835 
836  color = colorinfo.get( AUT_CONS(scip, conss[i]) );
837 
838  if(color == -1) {
839  *result = SCIP_DIDNOTFIND;
840  break;
841  }
842 
843  SCIPdebugMessage("cons <%s> color %d\n", SCIPconsGetName(conss[i]), color);
844  (void) h->add_vertex((unsigned int)color);
845  nnodes++;
846  }
847  //add a node for every variable
848  for( i = 0; i < nvars && *result == SCIP_SUCCESS; i++ )
849  {
850  color = colorinfo.get( AUT_VAR(scip, vars[i]) );
851 
852  if(color == -1) {
853  *result = SCIP_DIDNOTFIND;
854  break;
855  }
856  SCIPdebugMessage("var <%s> color %d\n", SCIPvarGetName(vars[i]), color);
857 
858  (void) h->add_vertex((unsigned int) colorinfo.getLenCons() + color);
859  nnodes++;
860  }
861  //connecting the nodes with an additional node in the middle
862  //it is necessary, since only nodes have colors
863  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
864  {
865  int conscolor = colorinfo.get(AUT_CONS(scip, conss[i]));
866  ncurvars = GCGconsGetNVars(scip, conss[i]);
867  if( ncurvars == 0 )
868  continue;
869  SCIP_CALL( SCIPallocBufferArray(origscip, &curvars, ncurvars) );
870  SCIP_CALL( GCGconsGetVars(scip, conss[i], curvars, ncurvars) );
871  SCIP_CALL( SCIPallocBufferArray(origscip, &curvals, ncurvars) );
872  SCIP_CALL( GCGconsGetVals(scip, conss[i], curvals, ncurvars) );
873  for( j = 0; j < ncurvars; j++ )
874  {
875  int varcolor = colorinfo.get( AUT_VAR(scip, curvars[j] )) + colorinfo.getLenCons(); /*lint !e864 */
876  color = colorinfo.get( AUT_COEF(scip, curvals[j] ));
877  if( color == -1 )
878  {
879  *result = SCIP_DIDNOTFIND;
880  break;
881  }
882  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
883  curvar = SCIPvarGetProbindex(curvars[j]);
884  (void) h->add_vertex((unsigned int) color);
885  nnodes++;
886  h->add_edge((unsigned int) nnodesoffset[s] + i, (unsigned int) nnodesoffset[s] + nconss + nvars + z);
887  h->add_edge((unsigned int) nnodesoffset[s] + nconss + nvars + z, (unsigned int) nnodesoffset[s]+nconss + curvar);
888  SCIPdebugMessage("nz: c <%s> (id: %d, color: %d) -> nz (id: %d) (value: %f, color: %d) -> var <%s> (id: %d, color: %d) \n",
889  SCIPconsGetName(conss[i]),
890  nnodesoffset[s] + i,
891  conscolor,
892  nnodesoffset[s] + nconss + nvars + z,
893  curvals[j],
894  color+colorinfo.getLenCons() + colorinfo.getLenVar(), /*lint !e864 */
895  SCIPvarGetName(curvars[j]),
896  nnodesoffset[s] + nconss + curvar,
897  varcolor);
898  z++;
899  }
900  SCIPfreeBufferArray(origscip, &curvals);
901  SCIPfreeBufferArray(origscip, &curvars);
902  }
903  pricingnonzeros[s] = z;
904 
905  /* add coefficient nodes for nonzeros in the master */
906  for( i = 0; i < nmasterconss && *result == SCIP_SUCCESS; ++i )
907  {
908  SCIP_CONS* mastercons = origmasterconss[i];
909  curvars = SCIPgetVarsLinear(origscip, mastercons);
910  curvals = SCIPgetValsLinear(origscip, mastercons);
911  ncurvars = SCIPgetNVarsLinear(origscip, mastercons);
912  for( j = 0; j < ncurvars; ++j )
913  {
914  if( GCGoriginalVarIsLinking(curvars[j]) )
915  {
916  SCIPdebugMessage("Var <%s> is linking, abort detection.\n", SCIPvarGetName(curvars[j]));
917  *result = SCIP_DIDNOTFIND;
918  return SCIP_OKAY;
919  }
920  int block = GCGvarGetBlock(curvars[j]);
921 
922  /* ignore if the variable belongs to a different block */
923  if( block != pricingindices[s] )
924  {
925  // SCIPdebugMessage("Var <%s> belongs to a different block (%d)\n", SCIPvarGetName(curvars[j]), block);
926  continue;
927  }
928 
929 
930  color = colorinfo.get(AUT_COEF(origscip, curvals[j]));
931  assert(color != -1);
932  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
933 
934  /* add coefficent node for current coeff */
935  (void) h->add_vertex((unsigned int)color);
936  assert(ABS(curvals[j] < SCIPinfinity(scip)));
937  SCIPdebugMessage("master nz for var <%s> (id: %d) (value: %f, color: %d)\n", SCIPvarGetName(curvars[j]), nnodes, curvals[j], color);
938  nnodes++;
939  }
940  }
941  SCIPdebugMessage("Iteration %d: nnodes = %d\n", s, nnodes);
942  assert(*result == SCIP_SUCCESS && (unsigned int) nnodes == h->get_nof_vertices());
943  }
944  /* connect the created graphs with nodes for the master problem */
945 
946  SCIPdebugMessage( "handling %d masterconss\n", nmasterconss);
947  *pricingnodes = nnodes;
948 
949  for( i = 0; i < nmasterconss && *result == SCIP_SUCCESS; ++i )
950  {
951  SCIP_CONS* mastercons = origmasterconss[i];
952  curvars = SCIPgetVarsLinear(origscip, mastercons);
953  curvals = SCIPgetValsLinear(origscip, mastercons);
954  ncurvars = SCIPgetNVarsLinear(origscip, mastercons);
955 
956  SCIPdebugMessage("Handling cons <%s>\n", SCIPconsGetName(mastercons));
957 
958  /* create node for masterconss and get right color */
959  int conscolor = colorinfo.get(AUT_CONS(origscip, mastercons));
960  assert(conscolor != -1);
961  (void) h->add_vertex((unsigned int) conscolor);
962  int masterconsnode = nnodes;
963  nnodes++;
964 
965  for( j = 0; j < ncurvars; ++j )
966  {
967  SCIP* pricingscip = NULL;
968  if( GCGoriginalVarIsLinking(curvars[j]) )
969  {
970  SCIPdebugMessage("Var <%s> is linking, abort detection.\n", SCIPvarGetName(curvars[j]));
971  *result = SCIP_DIDNOTFIND;
972  return SCIP_OKAY;
973  }
974  int block = GCGvarGetBlock(curvars[j]);
975  int ind = -1;
976  SCIPdebugMessage("Var <%s> is in block %d\n", SCIPvarGetName(curvars[j]), block);
977  for( s = 0; s < nscips; ++s )
978  {
979  if( block == pricingindices[s])
980  {
981  ind = s;
982  pricingscip = scips[s];
983  break;
984  }
985  }
986 
987  /* ignore if the variable belongs to a different block */
988  if( pricingscip == NULL )
989  {
990  // SCIPdebugMessage("Var <%s> belongs to a different block (%d)\n", SCIPvarGetName(curvars[j]), block);
991  continue;
992  }
993 
994  color = colorinfo.get(AUT_COEF(origscip, curvals[j]));
995  assert(color != -1);
996  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
997  SCIP_VAR* pricingvar = GCGoriginalVarGetPricingVar(curvars[j]);
998 
999  /* get coefficient node for current coefficient */
1000  int coefnodeindex = nnodesoffset[ind] + SCIPgetNVars(pricingscip) + SCIPgetNConss(pricingscip) + pricingnonzeros[ind] + mastercoefindex[ind];
1001  ++(mastercoefindex[ind]);
1002 
1003  int varcolor = colorinfo.get(AUT_VAR(pricingscip, pricingvar));
1004  assert(varcolor != -1);
1005  varcolor += colorinfo.getLenCons();
1006 
1007  assert( (uint) masterconsnode < h->get_nof_vertices());
1008  assert( (uint) coefnodeindex < h->get_nof_vertices());
1009  /* master constraint and coefficient */
1010  h->add_edge((unsigned int) masterconsnode, (unsigned int) coefnodeindex);
1011  SCIPdebugMessage("ma: c <%s> (id: %d, color: %d) -> nz (id: %d) (value: <%.6f> , color: %d) -> pricingvar <%s> (id: %d, color: %d)\n",
1012  SCIPconsGetName(mastercons),
1013  masterconsnode, conscolor, coefnodeindex, curvals[j], color, SCIPvarGetName(pricingvar),
1014  nnodesoffset[ind] + SCIPgetNConss(pricingscip) + SCIPvarGetProbindex(pricingvar), varcolor);
1015 
1016  /* get node index for pricing variable and connect masterconss, coeff and pricingvar nodes */
1017  h->add_edge((unsigned int) coefnodeindex, (unsigned int) nnodesoffset[ind] + SCIPgetNConss(pricingscip) + SCIPvarGetProbindex(pricingvar));
1018  }
1019  }
1020 
1021  //free all allocated memory
1022  SCIP_CALL( freeMemory(origscip, &colorinfo) );
1023  SCIPfreeMemoryArray(origscip, &mastercoefindex);
1024  SCIPfreeMemoryArray(origscip, &nnodesoffset);
1025  SCIPfreeMemoryArray(origscip, &pricingnonzeros);
1026 
1027  return SCIP_OKAY;
1028 }
1029 
1031 static
1034  gcg::Seeed* seeed,
1035  int nblocks,
1036  std::vector<int> blocks,
1037  AUT_COLOR colorinfo,
1038  bliss::Graph* graph,
1039  int* pricingnodes,
1040  SCIP_RESULT* result
1041  )
1042 {
1043  SCIP* scip;
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>(seeed->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 = seeedpool->getScip();
1069 
1070 
1071 // SCIP_CALL( SCIPallocMemoryArray(origscip, &pricingnonzeros, nscips) );
1072 // SCIP_CALL( SCIPallocMemoryArray(origscip, &nnodesoffset, nscips) );
1073  SCIP_CALL( SCIPallocMemoryArray(scip, &mastercoefindex, nblocks) );
1074 // BMSclearMemoryArray(pricingnonzeros, nscips);
1075 // BMSclearMemoryArray(nnodesoffset, nscips);
1076  BMSclearMemoryArray(mastercoefindex, nblocks);
1077 //
1078 // SCIP_CONS** origmasterconss = GCGgetLinearOrigMasterConss(origscip);
1079 // int nmasterconss = GCGgetNMasterConss(origscip);
1080 
1081  nconss = seeed->getNConssForBlock(blocks[0]);
1082  nvars = seeed->getNVarsForBlock(blocks[0]);
1083 
1084  SCIP_CALL( SCIPallocMemoryArray(origscip, &nnodesoffset, nblocks) );
1085  BMSclearMemoryArray(nnodesoffset, nblocks);
1086  SCIP_CALL( SCIPallocMemoryArray(origscip, &pricingnonzeros, nblocks) );
1087  BMSclearMemoryArray(pricingnonzeros, nblocks);
1088 
1089  for( b = 0; b < nblocks && *result == SCIP_SUCCESS; ++b )
1090  {
1091  int block;
1092 
1093  block = blocks[b];
1094  SCIPdebugMessage("Pricing problem %d\n", blocks[b]);
1095 // SCIP* scip = scips[s];
1096  int z;
1097 
1098  z = 0;
1099 
1100  nnodesoffset[b] = nnodes;
1101 
1102  //add a node for every constraint
1103  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
1104  {
1105  int consid;
1106  SCIP_CONS* cons;
1107 
1108  consid = seeed->getConssForBlock(block)[i];
1109  ncurvars = seeedpool->getNVarsForCons(consid);
1110  cons = seeedpool->getConsForIndex(consid);
1111 
1112  if( ncurvars == 0 )
1113  continue;
1114 
1115  color = colorinfo.get( AUT_CONS(scip, cons) );
1116 
1117  if(color == -1) {
1118  *result = SCIP_DIDNOTFIND;
1119  break;
1120  }
1121 
1122  SCIPdebugMessage("cons <%s> color %d\n", SCIPconsGetName(cons), color);
1123  (void) h->add_vertex((unsigned int)color);
1124  nnodes++;
1125  }
1126  //add a node for every variable
1127  for( i = 0; i < nvars && *result == SCIP_SUCCESS; i++ )
1128  {
1129  int varid;
1130  SCIP_VAR* var;
1131 
1132  varid = seeed->getVarsForBlock(block)[i];
1133  var = seeedpool->getVarForIndex(varid);
1134 
1135  color = colorinfo.get( AUT_VAR(scip, var) );
1136 
1137  if(color == -1) {
1138  *result = SCIP_DIDNOTFIND;
1139  break;
1140  }
1141 
1142  SCIPdebugMessage("var <%s> color %d\n", SCIPvarGetName(var), color);
1143  (void) h->add_vertex((unsigned int) colorinfo.getLenCons() + color);
1144  nnodes++;
1145  }
1146  //connecting the nodes with an additional node in the middle
1147  //it is necessary, since only nodes have colors
1148  for( i = 0; i < nconss && *result == SCIP_SUCCESS; i++ )
1149  {
1150  int consid;
1151  SCIP_CONS* cons;
1152  int conscolor;
1153 
1154  consid = seeed->getConssForBlock(block)[i];
1155  ncurvars = seeedpool->getNVarsForCons(consid);
1156  cons = seeedpool->getConsForIndex(consid);
1157  conscolor = colorinfo.get(AUT_CONS(scip, cons));
1158 
1159  if( ncurvars == 0 )
1160  continue;
1161 
1162  for( j = 0; j < ncurvars; j++ )
1163  {
1164  int varcolor;
1165  int varid;
1166  SCIP_VAR* var;
1167  SCIP_Real val;
1168 
1169  varid = seeedpool->getVarsForCons(consid)[j];
1170  var = seeedpool->getVarForIndex(varid);
1171 
1172  val = seeedpool->getVal(consid, varid);
1173 
1174  varcolor = colorinfo.get( AUT_VAR(scip, var )) + colorinfo.getLenCons(); /*lint !e864 */
1175  color = colorinfo.get( AUT_COEF(scip, val ));
1176  if( color == -1 )
1177  {
1178  *result = SCIP_DIDNOTFIND;
1179  break;
1180  }
1181  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
1182  (void) h->add_vertex((unsigned int) color);
1183  nnodes++;
1184  h->add_edge((unsigned int) nnodesoffset[b] + i, (unsigned int) nnodesoffset[b] + nconss + nvars + z);
1185  h->add_edge((unsigned int) nnodesoffset[b] + nconss + nvars + z, (unsigned int) nnodesoffset[b]+nconss + seeed->getVarProbindexForBlock(varid, block) );
1186  SCIPdebugMessage("nz: c <%s> (id: %d, color: %d) -> nz (id: %d) (value: %f, color: %d) -> var <%s> (id: %d, color: %d) \n",
1187  SCIPconsGetName(cons),
1188  nnodesoffset[b] + i,
1189  conscolor,
1190  nnodesoffset[b] + nconss + nvars + z,
1191  val,
1192  color+colorinfo.getLenCons() + colorinfo.getLenVar(), /*lint !e864 */
1193  SCIPvarGetName(var),
1194  nnodesoffset[b]+nconss + seeed->getVarProbindexForBlock(varid, block),
1195  varcolor);
1196  z++;
1197  }
1198  }
1199  pricingnonzeros[b] = z;
1200 
1201  /* add coefficient nodes for nonzeros in the master */
1202  for( i = 0; i < seeed->getNMasterconss() && *result == SCIP_SUCCESS; ++i )
1203  {
1204  int masterconsid;
1205 
1206  masterconsid = seeed->getMasterconss()[i];
1207  ncurvars = seeedpool->getNVarsForCons(masterconsid);
1208 
1209  for( j = 0; j < ncurvars; ++j )
1210  {
1211  int varid;
1212  SCIP_VAR* var;
1213  SCIP_Real val;
1214 
1215  varid = seeedpool->getVarsForCons(masterconsid)[j];
1216  /* ignore if the variable belongs to a different block */
1217  if( !seeed->isVarBlockvarOfBlock(varid, block) )
1218  {
1219 // SCIPdebugMessage("Var <%s> belongs to a different block (%d)\n", SCIPvarGetName(seeedpool->getVarForIndex(varid) ), block);
1220  continue;
1221  }
1222 
1223  var = seeedpool->getVarForIndex(varid);
1224  val = seeedpool->getVal(masterconsid, varid);
1225  color = colorinfo.get(AUT_COEF(seeedpool->getScip(), val));
1226  assert(color != -1);
1227  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
1228 
1229  masterconssrelevant[i] = true;
1230 
1231  /* add coefficent node for current coeff */
1232  (void) h->add_vertex((unsigned int)color);
1233  assert(ABS(val < SCIPinfinity(scip)));
1234  SCIPdebugMessage("master nz for var <%s> (id: %d) (value: %f, color: %d)\n", SCIPvarGetName(var), nnodes, val, color);
1235  nnodes++;
1236  }
1237  }
1238  SCIPdebugMessage("Iteration %d: nnodes = %d\n", b, nnodes);
1239  assert(*result == SCIP_SUCCESS && (unsigned int) nnodes == h->get_nof_vertices());
1240  }
1241  /* connect the created graphs with nodes for the master problem */
1242 
1243  SCIPdebugMessage( "handling %d masterconss\n", seeed->getNMasterconss());
1244  *pricingnodes = nnodes;
1245 
1246  for( i = 0; i < seeed->getNMasterconss() && *result == SCIP_SUCCESS; ++i )
1247  {
1248  int masterconsid;
1249  SCIP_CONS* mastercons;
1250  int masterconsnode;
1251  int conscolor;
1252 
1254  if( !masterconssrelevant[i] )
1255  continue;
1256  /*experimental end */
1257 
1258 
1259  masterconsid= seeed->getMasterconss()[i];
1260  mastercons = seeedpool->getConsForIndex(masterconsid);
1261  ncurvars = seeedpool->getNVarsForCons(masterconsid);
1262 
1263  SCIPdebugMessage("Handling cons <%s>\n", SCIPconsGetName(mastercons));
1264 
1265 
1266  /* create node for masterconss and get right color */
1267  conscolor = colorinfo.get(AUT_CONS(scip, mastercons) );
1268  assert(conscolor != -1);
1269  (void) h->add_vertex((unsigned int) conscolor);
1270  masterconsnode = nnodes;
1271  nnodes++;
1272 
1273  for( j = 0; j < ncurvars; ++j )
1274  {
1275  int varid;
1276  SCIP_VAR* var;
1277  SCIP_Real val;
1278  int blockid;
1279  int coefnodeindex;
1280  int bid;
1281  int varcolor;
1282 
1283  blockid = -1;
1284  bid = -1;
1285  varid = seeedpool->getVarsForCons(masterconsid)[j];
1286 
1287  var = seeedpool->getVarForIndex(varid);
1288 
1289  for( b = 0; b < nblocks; ++b )
1290  {
1291  if( seeed->isVarBlockvarOfBlock(varid, blocks[b]) )
1292  {
1293  bid = b;
1294  blockid = blocks[b];
1295  break;
1296  }
1297  }
1298 
1299  /* ignore if the variable belongs to a different block */
1300  if( blockid == -1 )
1301  {
1302  //SCIPdebugMessage("Var <%s> belongs to a different block \n", SCIPvarGetName(var));
1303  continue;
1304  }
1305  val = seeedpool->getVal(masterconsid, varid);
1306 
1307  color = colorinfo.get(AUT_COEF(scip, val));
1308  assert(color != -1);
1309  color += colorinfo.getLenCons() + colorinfo.getLenVar(); /*lint !e864 */
1310 
1311  /* get coefficient node for current coefficient */
1312  coefnodeindex = nnodesoffset[bid] + nvars + nconss + pricingnonzeros[bid] + mastercoefindex[bid];
1313  ++(mastercoefindex[bid]);
1314 
1315  varcolor = colorinfo.get(AUT_VAR(scip, var));
1316  assert(varcolor != -1);
1317  varcolor += colorinfo.getLenCons();
1318 
1319  assert( (uint) masterconsnode < h->get_nof_vertices());
1320  assert( (uint) coefnodeindex < h->get_nof_vertices());
1321  /* master constraint and coefficient */
1322  h->add_edge((unsigned int) masterconsnode, (unsigned int) coefnodeindex);
1323  SCIPdebugMessage("ma: c <%s> (id: %d, color: %d) -> nz (id: %d) (value: <%.6f> , color: %d) -> pricingvar <%s> (id: %d, color: %d)\n",
1324  SCIPconsGetName(mastercons),
1325  masterconsnode, conscolor, coefnodeindex, val, color, SCIPvarGetName(var),
1326  nnodesoffset[bid] + nconss + varid, varcolor);
1327 
1328  /* get node index for pricing variable and connect masterconss, coeff and pricingvar nodes */
1329  h->add_edge((unsigned int) coefnodeindex, (unsigned int) nnodesoffset[bid] + nconss + seeed->getVarProbindexForBlock(varid, blockid) );
1330  }
1331  }
1332 
1333 
1334  //free all allocated memory
1335  SCIP_CALL( freeMemory(scip, &colorinfo) );
1336  SCIPfreeMemoryArray(scip, &mastercoefindex);
1337  SCIPfreeMemoryArray(scip, &nnodesoffset);
1338  SCIPfreeMemoryArray(scip, &pricingnonzeros);
1339 
1340  return SCIP_OKAY;
1341 }
1342 
1343 
1344 
1345 
1347 extern "C"
1348 SCIP_RETCODE cmpGraphPair(
1349  SCIP* origscip,
1350  SCIP* scip1,
1351  SCIP* scip2,
1352  int prob1,
1353  int prob2,
1354  SCIP_RESULT* result,
1355  SCIP_HASHMAP* varmap,
1356  SCIP_HASHMAP* consmap
1357  )
1358 {
1359  bliss::Graph graph;
1360  bliss::Stats bstats;
1361  AUT_HOOK2 *ptrhook;
1362  AUT_COLOR colorinfo;
1363  int nscips;
1364  SCIP* scips[2];
1365  int pricingindices[2];
1366  int pricingnodes = 0;
1367  scips[0] = scip1;
1368  scips[1] = scip2;
1369  pricingindices[0] = prob1;
1370  pricingindices[1] = prob2;
1371  nscips = 2;
1372  *result = SCIP_SUCCESS;
1373 
1374 
1375  SCIP_CALL( testScipVars(scips[0], scips[1], result) );
1376  SCIP_CALL( testScipCons(scips[0], scips[1], result) );
1377 
1378  SCIP_CALL( setuparrays(origscip, scips, nscips, &colorinfo, result) );
1379  SCIP_CALL( createGraph(origscip, scips, nscips, pricingindices, colorinfo, &graph, &pricingnodes, result) );
1380 
1381  ptrhook = new AUT_HOOK2(varmap, consmap, FALSE, (unsigned int) pricingnodes, scips);
1382  graph.find_automorphisms(bstats, fhook, ptrhook);
1383 
1384  SCIPverbMessage(origscip, SCIP_VERBLEVEL_FULL , NULL, "finished calling bliss: number of reporting function calls (=number of generators): %d \n", ptrhook->ncalls);
1385 
1386  if( !ptrhook->getBool() )
1387  *result = SCIP_DIDNOTFIND;
1388 
1389  SCIPfreeMemoryArrayNull(scip, &ptrhook->nodemap);
1390  delete ptrhook;
1391  return SCIP_OKAY;
1392 }
1393 
1395 extern "C"
1397  SCIP* scip,
1398  SEEED_WRAPPER* seeedwr,
1399  int block1,
1400  int block2,
1401  SCIP_RESULT* result,
1402  SCIP_HASHMAP* varmap,
1403  SCIP_HASHMAP* consmap
1404  )
1405 {
1406  bliss::Graph graph;
1407  bliss::Stats bstats;
1408  AUT_HOOK2 *ptrhook;
1409  AUT_COLOR colorinfo;
1410  std::vector<int> blocks;
1412  gcg::Seeedpool* seeedpoolunpresolved;
1413  gcg::Seeedpool* seeedpoolpresolved;
1414  gcg::Seeed* seeed;
1415 
1416 // int pricingindices[2];
1417  int pricingnodes;
1418 
1419  seeed = (gcg::Seeed*) seeedwr;
1420  *result = SCIP_SUCCESS;
1421 
1422  assert(seeed != NULL );
1423 
1424  blocks = std::vector<int>(2, -1);
1425  blocks[0] = block1;
1426  blocks[1] = block2;
1427  pricingnodes = 0;
1428 
1429  seeedpoolpresolved = (gcg::Seeedpool*) SCIPconshdlrDecompGetSeeedpoolExtern(scip);
1430  seeedpoolunpresolved = (gcg::Seeedpool*) SCIPconshdlrDecompGetSeeedpoolUnpresolvedExtern(scip);
1431 
1432  if (seeed->isFromUnpresolved() )
1433  seeedpool = seeedpoolunpresolved;
1434  else
1435  seeedpool = seeedpoolpresolved;
1436 
1437  assert(seeedpool != NULL);
1438 
1439  SCIP_CALL( setuparraysnewdetection(seeedpool, seeed, 2, blocks, &colorinfo, result) );
1440  SCIPdebugMessage("finished setup array method.\n");
1441  SCIP_CALL( createGraphNewDetection(seeedpool, seeed, 2, blocks, colorinfo, &graph, &pricingnodes, result) );
1442  SCIPdebugMessage("finished create graph.\n");
1443  ptrhook = new AUT_HOOK2(varmap, consmap, FALSE, (unsigned int) pricingnodes, NULL);
1444  SCIPdebugMessage("finished creating aut hook.\n");
1445  ptrhook->setNewDetectionStuff(seeedpool, seeed, blocks);
1446 
1447 
1448  graph.find_automorphisms(bstats, fhook, ptrhook);
1449  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL , NULL, "finished calling bliss: number of reporting function calls (=number of generators): %d \n", ptrhook->ncalls);
1450 
1451  SCIPdebugMessage("finished find automorphisms.\n");
1452 
1453  if( !ptrhook->getBool() )
1454  *result = SCIP_DIDNOTFIND;
1455 
1456  SCIPfreeMemoryArrayNull(scip, &ptrhook->nodemap);
1457  delete ptrhook;
1458  return SCIP_OKAY;
1459 }
1460 
SCIP_HASHMAP * varmap
static SCIP_RETCODE setuparrays(SCIP *origscip, SCIP **scips, int nscips, AUT_COLOR *colorinfo, SCIP_RESULT *result)
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
bool isVarBlockvarOfBlock(int var, int block)
returns true if the var is assigned to the block
GCG interface methods.
static SCIP_RETCODE setuparraysnewdetection(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed, int nblocks, std::vector< int > blocks, AUT_COLOR *colorinfo, SCIP_RESULT *result)
int getNConssForBlock(int block)
returns size of the vector containing conss assigned to a block
bool isFromUnpresolved()
returns true if the seeed is from the unpresolved problem
static SCIP_RETCODE createGraphNewDetection(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed, int nblocks, std::vector< int > blocks, AUT_COLOR colorinfo, bliss::Graph *graph, int *pricingnodes, SCIP_RESULT *result)
struct struct_var AUT_VAR
Definition: pub_bliss.h:49
gcg::Seeed * seeed
const int * getMasterconss()
SCIP_RETCODE cmpGraphPairNewdetection(SCIP *scip, SEEED_WRAPPER *seeedwr, int block1, int block2, SCIP_RESULT *result, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap)
struct struct_cons AUT_CONS
Definition: pub_bliss.h:48
helper functions for automorphism detection
SCIP_RETCODE cmpGraphPair(SCIP *origscip, SCIP *scip1, SCIP *scip2, int prob1, int prob2, SCIP_RESULT *result, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap)
struct struct_coef AUT_COEF
Definition: pub_bliss.h:50
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:433
gcg::Seeedpool * seeedpool
struct struct_colorinformation AUT_COLOR
Definition: pub_bliss.h:51
void setBool(SCIP_Bool aut)
SCIP_CONS ** GCGgetLinearOrigMasterConss(SCIP *scip)
Definition: relax_gcg.c:4051
SCIP_VAR * getVarForIndex(int varIndex)
returns SCIP variable related to a variable index
static SCIP_RETCODE reallocMemory(SCIP *scip, AUT_COLOR *colorinfo, int nconss, int nvars)
const int * getVarsForBlock(int block)
returns array containing vars of a block
int getNConss()
returns the number of variables considered in the seeedpool
SCIP_Bool getBool()
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:620
SCIP ** getScips()
unsigned int getNNodes()
SEEEDPOOL_WRAPPER * SCIPconshdlrDecompGetSeeedpoolExtern(SCIP *scip)
help method to access seeedpool for transformed problem : consider deleting this method will be delet...
SCIP_HASHMAP * getVarHash()
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 SCIP_RETCODE testScipCons(SCIP *scip1, SCIP *scip2, SCIP_RESULT *result)
struct struct_hook2 AUT_HOOK2
static SCIP_RETCODE freeMemory(SCIP *scip, AUT_COLOR *colorinfo)
SCIP_HASHMAP * consmap
int getNCoeffsForMaster()
std::vector< int > blocks
static SCIP_RETCODE testScipVars(SCIP *scip1, SCIP *scip2, SCIP_RESULT *result)
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:489
SCIP_Bool GCGoriginalVarIsLinking(SCIP_VAR *var)
Definition: gcgvar.c:176
int GCGvarGetBlock(SCIP_VAR *var)
Definition: gcgvar.c:936
unsigned int n
automorphism recognition of SCIPs
struct_hook2(SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool aut, unsigned int n, SCIP **scips)
static void fhook(void *user_param, unsigned int N, const unsigned int *aut)
const int * getConssForBlock(int block)
returns array containing constraints assigned to a block
SEEEDPOOL_WRAPPER * SCIPconshdlrDecompGetSeeedpoolUnpresolvedExtern(SCIP *scip)
help method to access seeedpool for unpresolved problem : consider deleting this method will be delet...
static SCIP_RETCODE createGraph(SCIP *origscip, SCIP **scips, int nscips, int *pricingindices, AUT_COLOR colorinfo, bliss::Graph *graph, int *pricingnodes, SCIP_RESULT *result)
int GCGgetNMasterConss(SCIP *scip)
Definition: relax_gcg.c:3992
void setNewDetectionStuff(gcg::Seeedpool *seeedpool, gcg::Seeed *seeed, std::vector< int > blocks)
static SCIP_RETCODE allocMemory(SCIP *scip, AUT_COLOR *colorinfo, int nconss, int nvars)
SCIP_HASHMAP * getConsHash()
int getNMasterconss()
returns size of the vector containing master conss
SCIP * getScip()
returns the corresponding scip data structure
int getNVarsForBlock(int block)
returns size of the vector containing vars assigned to a block
SCIP_Real getVal(int row, int col)
returns a coefficient from the coefficient matrix
class with functions for seeed pool where a seeed is a (potentially incomplete) description of a deco...
int getVarProbindexForBlock(int varid, int block)
returns index in variables array of a block for a variable
static SCIP_RETCODE allocMemoryNewDetection(gcg::Seeedpool *seeedpool, AUT_COLOR *colorinfo, int nconss, int nvars, int ncoeffs)
int getNCoeffsForBlock(int blockid)
returns the number of nonzero coeffs in a certain block
SCIP_CONS * getConsForIndex(int consIndex)
returns the SCIP constraint related to a constraint index
SCIP_VAR * GCGoriginalVarGetPricingVar(SCIP_VAR *var)
Definition: gcgvar.c:206
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint