class_seeedpool.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 
34 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
35 
36 /*@todo don't disable lint */
37 /*lint -e64 disable useless and wrong lint warning */
38 
39 /*@todo this looks like a workaround, is disabling warnings a good idea? */
40 #ifdef __INTEL_COMPILER
41 #ifndef _OPENMP
42 #pragma warning disable 3180 /* disable wrong and useless omp warnings */
43 #endif
44 #endif
45 
46 //#define WRITE_ORIG_CONSTYPES
47 // #define SCIP_DEBUG
48 
49 #include "scip/scipdefplugins.h"
50 #include "gcg.h"
51 #include "objscip/objscip.h"
52 #include "scip/scip.h"
53 #include "class_seeedpool.h"
54 #include "struct_detector.h"
55 #include "pub_decomp.h"
56 #include "struct_decomp.h"
57 #include "cons_decomp.h"
58 #include "decomp.h"
59 #include "scip_misc.h"
60 #include "scip/clock.h"
61 #include "scip/cons.h"
62 #include "scip/scip.h"
63 #include "scip/var.h"
64 #include <algorithm>
65 #include <list>
66 #include <iostream>
67 #include <stdio.h>
68 #include <sstream>
69 #include <iomanip>
70 #include <queue>
71 #include <fstream>
72 #include <exception>
74 #include <random>
75 
76 
77 
78 #ifdef _OPENMP
79 #include <omp.h>
80 #endif
81 
82 #define DEFAULT_RANDSEED 23
84 #define SCIP_CALL_EXC( x ) do \
85  { \
86  SCIP_RETCODE _restat_; \
87  if( ( _restat_ = ( x ) ) != SCIP_OKAY ) \
88  { \
89  SCIPerrorMessage( "Error <%d> in function call\n", _restat_); \
90  throw std::exception(); \
91  } \
92  } \
93  while( false )
94 
95 #define ENUM_TO_STRING( x ) # x
96 #define DEFAULT_THREADS 0
99 //#ifdef WITH_PRINTORIGCONSTYPES
100 
102 {
119 };
121 
123 {
127 };
129 //#endif
130 
131 
132 
133 
134 namespace gcg{
135 
138 struct sort_decr
139 {
141  const std::pair<int, int> &left,
142  const std::pair<int, int> &right)
143  {
144  if( left.second != right.second )
145  return left.second > right.second;
146  else return left.first < right.first;
147  }
148 };
149 
150 struct sort_pred
151 {
153  const std::pair<int, int> &left,
154  const std::pair<int, int> &right)
155  {
156  return left.second < right.second;
157  }
158 };
159 
160 
161 SCIP_RETCODE Seeedpool::calculateDualvalsOptimalOrigLP()
162 {
163 
164  SCIP* scipcopy;
165  SCIP_HASHMAP* origtocopiedconss;
166  SCIP_Bool valid;
167  int nvars;
168  SCIP_VAR** copiedvars;
169 
170  int nconss;
171 
172  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "startetd calculating optimal dual values for original lp\n");
173 
174  SCIPhashmapCreate(&origtocopiedconss, SCIPblkmem(scip), SCIPgetNConss(scip) );
175 
176  SCIPcreate(&scipcopy);
177  // SCIPincludeDefaultPlugins(scipcopy);
178 
179 
180  SCIPcopy(scip, scipcopy, NULL, origtocopiedconss, "", FALSE, FALSE, FALSE, &valid );
181 
182  nconss = getNConss();
183 
184  assert(SCIPgetNConss(scip) == getNConss() );
185 
186  nvars = SCIPgetNVars(scipcopy);
187  copiedvars = SCIPgetVars(scipcopy);
188 
189  dualvalsoptimaloriglp = std::vector<SCIP_Real>(getNConss(), 0.);
190 
191  for( int var = 0; var < nvars ; ++var )
192  {
193  SCIP_VAR* copyvar = copiedvars[var];
194  SCIP_Bool infeasible;
195 
196  if( SCIPvarGetType(copyvar) == SCIP_VARTYPE_BINARY )
197  SCIPchgVarUbGlobal(scipcopy, copyvar, 1. );
198 
199  SCIPchgVarType(scipcopy, copyvar, SCIP_VARTYPE_CONTINUOUS, &infeasible);
200  }
201 
202  copiedvars = SCIPgetVars(scipcopy);
203 
205  SCIPsetIntParam(scipcopy, "presolving/maxrounds", 0);
206 
208  SCIPsetIntParam(scipcopy, "separating/maxrounds", 0);
209  SCIPsetIntParam(scipcopy, "separating/maxroundsroot", 0);
210 
212  SCIPsetIntParam(scipcopy, "propagating/maxrounds", 0);
213  SCIPsetIntParam(scipcopy, "propagating/maxroundsroot", 0);
214 
216  SCIPsetIntParam(scipcopy, "lp/solvefreq", 1);
217 
219  SCIPsetLongintParam(scipcopy, "limits/nodes", 1);
220 
221  SCIPsetIntParam(scipcopy, "display/verblevel", SCIP_VERBLEVEL_FULL);
222 
223  SCIPtransformProb(scipcopy);
224 
225 // SCIPstartDive(scipcopy);
226 // SCIPconstructLP(scipcopy, FALSE);
227 // SCIPsolveDiveLP(scipcopy, -1, &lperror, &cutoff );
228 
229 
230 
231  // SCIPwriteTransProblem(scipcopy, "lporig.lp", "lp", FALSE);
232 
233  //SCIPwriteParams(scipcopy, "lporig.set", TRUE, TRUE);
234 
235  SCIPsolve(scipcopy);
236 
237  // SCIPprintStatistics( scipcopy, NULL );
238 
239  // assert(FALSE);
240 
241  for( int c = 0; c < nconss; ++c )
242  {
243  SCIP_CONS* cons;
244  SCIP_CONS* copiedcons;
245 
246  cons = getConsForIndex(c);
247  if( !transformed && SCIPconsGetTransformed(cons) != NULL )
248  cons = SCIPconsGetTransformed(cons);
249  else if ( !transformed )
250  {
251  SCIPwarningMessage(scip, "Could not find constraint for random dual variable initilization when calculating strong decomposition score; skip cons: %s \n", SCIPconsGetName(cons));
252  continue;
253  }
254  copiedcons = (SCIP_CONS*) SCIPhashmapGetImage(origtocopiedconss, (void*) cons);
255 
256  assert(copiedcons != NULL);
257  assert( !SCIPconsIsTransformed(copiedcons) );
258 
259  if( SCIPconsGetTransformed(copiedcons) != NULL )
260  copiedcons = SCIPconsGetTransformed(copiedcons);
261 
262  dualvalsoptimaloriglp[c] = GCGconsGetDualsol(scipcopy, copiedcons);
263  if( !SCIPisFeasEQ(scip, 0., dualvalsoptimaloriglp[c]) )
264  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "optimal dual sol of constraint %s is %f \n", SCIPconsGetName(cons), dualvalsoptimaloriglp[c]);
265  }
266 
267  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "finished calculating optimal dual values for original lp, start freeing\n");
268 
269  SCIPhashmapFree(&origtocopiedconss);
270  SCIPfree(&scipcopy);
271 
272  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "finished freeing\n");
273 
274  return SCIP_OKAY;
275 }
276 
278 static
279 SCIP_Bool isRangedRow(
280  SCIP* scip,
281  SCIP_Real lhs,
282  SCIP_Real rhs
283  )
284 {
285  assert(scip != NULL);
286 
287  return !(SCIPisEQ(scip, lhs, rhs)
288  || SCIPisInfinity(scip, -lhs) || SCIPisInfinity(scip, rhs) );
289 }
290 
292 static
294  SCIP* scip,
295  SCIP_Real x
296  )
297 {
298  assert(scip != NULL);
299 
300  return (!SCIPisInfinity(scip, x) && !SCIPisNegative(scip, x) && SCIPisIntegral(scip, x));
301 }
302 
304 static
306  SCIP* scip,
307  SCIP* subscip,
308  Seeedpool* seeedpool,
309  SeeedPtr seeed,
310  int block,
311  SCIP_HASHMAP* hashorig2pricingvar
312  )
313 {
314  SCIP_CONS* newcons;
315  SCIP_HASHMAP* hashorig2pricingconstmp;
316  int c;
317  char name[SCIP_MAXSTRLEN];
318  SCIP_Bool success;
319 
320  assert(scip != NULL);
321 
322 // subscipconss = DECdecompGetSubscipconss(relaxdata->decdecomp);
323 // nsubscipconss = DECdecompGetNSubscipconss(relaxdata->decdecomp);
324 
325  SCIP_CALL( SCIPhashmapCreate(&hashorig2pricingconstmp, SCIPblkmem(scip), seeedpool->getNConss() ) ); /*lint !e613*/
326 
327  assert(hashorig2pricingvar != NULL);
328  for( c = 0; c < seeed->getNConssForBlock(block); ++c )
329  {
330  SCIP_CONS* cons;
331 
332  cons = seeedpool->getConsForIndex( seeed->getConssForBlock(block)[c] );
333 
334  SCIPdebugMessage("copying %s to pricing problem %d\n", SCIPconsGetName(cons), block);
335  if( !SCIPconsIsActive(cons) )
336  {
337  SCIPdebugMessage("skipping, cons <%s> inactive\n", SCIPconsGetName(cons) );
338  continue;
339  }
340  SCIP_CALL( SCIPgetTransformedCons(scip, cons, &cons) );
341  assert(cons != NULL);
342 
343  /* copy the constraint */
344  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "p%d_%s", block, SCIPconsGetName(cons));
345  SCIP_CALL( SCIPgetConsCopy(scip, subscip, cons, &newcons, SCIPconsGetHdlr(cons),
346  hashorig2pricingvar, hashorig2pricingconstmp, name,
347  TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, TRUE, &success) );
348 
349  /* constraint was successfully copied */
350  assert(success);
351 
352  SCIP_CALL( SCIPaddCons(subscip, newcons) );
353 #ifndef NDEBUG
354  {
355  SCIP_VAR** curvars;
356  int ncurvars;
357 
358  ncurvars = GCGconsGetNVars(subscip, newcons);
359  curvars = NULL;
360  if( ncurvars > 0 )
361  {
362  SCIP_CALL( SCIPallocBufferArray(scip, &curvars, ncurvars) );
363  SCIP_CALL( GCGconsGetVars(subscip, newcons, curvars, ncurvars) );
364 
365  SCIPfreeBufferArrayNull(scip, &curvars);
366  }
367  }
368 #endif
369 SCIP_CALL( SCIPreleaseCons(subscip, &newcons) );
370  }
371 
372  SCIPhashmapFree(&hashorig2pricingconstmp);
373 
374  return SCIP_OKAY;
375 }
376 
377 
378 
380 static
382  SCIP* scip,
383  int clocktype,
384  SCIP_Real infinity,
385  SCIP_Real epsilon,
386  SCIP_Real sumepsilon,
387  SCIP_Real feastol,
388  SCIP_Real lpfeastol,
389  SCIP_Real dualfeastol,
390  SCIP_Bool enableppcuts,
391  SCIP_Real timelimit
392  )
393 {
394  assert(scip != NULL);
395 
396  /* disable conflict analysis */
397  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/useprop", FALSE) );
398  SCIP_CALL( SCIPsetCharParam(scip, "conflict/useinflp", 'o') );
399  SCIP_CALL( SCIPsetCharParam(scip, "conflict/useboundlp", 'o') );
400  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/usesb", FALSE) );
401  SCIP_CALL( SCIPsetBoolParam(scip, "conflict/usepseudo", FALSE) );
402 
403  /* reduce the effort spent for hash tables */
404  SCIP_CALL( SCIPsetBoolParam(scip, "misc/usevartable", FALSE) );
405  SCIP_CALL( SCIPsetBoolParam(scip, "misc/useconstable", FALSE) );
406  SCIP_CALL( SCIPsetBoolParam(scip, "misc/usesmalltables", TRUE) );
407 
408  /* disable expensive presolving */
409  /* @todo test whether this really helps, perhaps set presolving emphasis to fast? */
410  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/linear/presolpairwise", FALSE) );
411  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/setppc/presolpairwise", FALSE) );
412  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/logicor/presolpairwise", FALSE) );
413  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/linear/presolusehashing", FALSE) );
414  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/setppc/presolusehashing", FALSE) );
415  SCIP_CALL( SCIPsetBoolParam(scip, "constraints/logicor/presolusehashing", FALSE) );
416 
417  /* disable dual fixing presolver for the moment, because we want to avoid variables fixed to infinity */
418  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/freq", -1) );
419  SCIP_CALL( SCIPsetIntParam(scip, "propagating/dualfix/maxprerounds", 0) );
420  SCIP_CALL( SCIPfixParam(scip, "propagating/dualfix/freq") );
421  SCIP_CALL( SCIPfixParam(scip, "propagating/dualfix/maxprerounds") );
422 
423  /* disable solution storage ! */
424  SCIP_CALL( SCIPsetIntParam(scip, "limits/maxorigsol", 0) );
425  SCIP_CALL( SCIPsetRealParam(scip, "limits/time", timelimit ) );
426 
427  /* disable multiaggregation because of infinite values */
428  SCIP_CALL( SCIPsetBoolParam(scip, "presolving/donotmultaggr", TRUE) );
429 
430  /* @todo enable presolving and propagation of xor constraints if bug is fixed */
431 
432  /* disable presolving and propagation of xor constraints as work-around for a SCIP bug */
433  SCIP_CALL( SCIPsetIntParam(scip, "constraints/xor/maxprerounds", 0) );
434  SCIP_CALL( SCIPsetIntParam(scip, "constraints/xor/propfreq", -1) );
435 
436  /* disable output to console */
437  SCIP_CALL( SCIPsetIntParam(scip, "display/verblevel", (int)SCIP_VERBLEVEL_NORMAL) );
438 #if SCIP_VERSION > 210
439  SCIP_CALL( SCIPsetBoolParam(scip, "misc/printreason", FALSE) );
440 #endif
441  SCIP_CALL( SCIPsetIntParam(scip, "limits/maxorigsol", 0) );
442  SCIP_CALL( SCIPfixParam(scip, "limits/maxorigsol") );
443 
444  /* do not abort subproblem on CTRL-C */
445  SCIP_CALL( SCIPsetBoolParam(scip, "misc/catchctrlc", FALSE) );
446 
447  /* set clock type */
448  SCIP_CALL( SCIPsetIntParam(scip, "timing/clocktype", clocktype) );
449 
450  SCIP_CALL( SCIPsetBoolParam(scip, "misc/calcintegral", FALSE) );
451  SCIP_CALL( SCIPsetBoolParam(scip, "misc/finitesolutionstore", TRUE) );
452 
453  SCIP_CALL( SCIPsetRealParam(scip, "numerics/infinity", infinity) );
454  SCIP_CALL( SCIPsetRealParam(scip, "numerics/epsilon", epsilon) );
455  SCIP_CALL( SCIPsetRealParam(scip, "numerics/sumepsilon", sumepsilon) );
456  SCIP_CALL( SCIPsetRealParam(scip, "numerics/feastol", feastol) );
457  SCIP_CALL( SCIPsetRealParam(scip, "numerics/lpfeastol", lpfeastol) );
458  SCIP_CALL( SCIPsetRealParam(scip, "numerics/dualfeastol", dualfeastol) );
459 
460  /* jonas' stuff */
461  if( enableppcuts )
462  {
463  int pscost;
464  int prop;
465 
466  SCIP_CALL( SCIPgetIntParam(scip, "branching/pscost/priority", &pscost) );
467  SCIP_CALL( SCIPgetIntParam(scip, "propagating/maxroundsroot", &prop) );
468  SCIP_CALL( SCIPsetIntParam(scip, "branching/pscost/priority", 11000) );
469  SCIP_CALL( SCIPsetIntParam(scip, "propagating/maxroundsroot", 0) );
470  SCIP_CALL( SCIPsetPresolving(scip, SCIP_PARAMSETTING_OFF, TRUE) );
471  }
472  return SCIP_OKAY;
473 }
474 
475 
476 
477 
480  std::vector<SCIP_Bool> const& childsfinished
481  )
482 {
483  for( size_t s = 0; s < childsfinished.size(); ++ s )
484  {
485  if( ! childsfinished[s] )
486  return true;
487  }
488  return false;
489 }
490 
493  std::vector<SCIP_Bool> const& childsfinished,
494  std::vector<int> const& childs
495  )
496 {
497  for( size_t s = 0; s < childsfinished.size(); ++ s )
498  {
499  if( ! childsfinished[s] )
500  return childs[s];
501  }
502  return - 1;
503 }
504 
507  std::vector<SCIP_Bool> const& childsfinished,
508  std::vector<int> const& childs
509  )
510 {
511  for( size_t s = 0; s < childsfinished.size(); ++ s )
512  {
513  if( ! childsfinished[s] )
514  return (int) s;
515  }
516  return - 1;
517 }
518 
521 SCIP_Bool finishNextChild(
522  std::vector<int>& childs,
523  std::vector<SCIP_Bool>& childsfinished,
524  int child
525  )
526 {
527  for( size_t s = 0; s < childsfinished.size(); ++ s )
528  {
529  if( ! childsfinished[s] )
530  {
531  assert( childs[s] == child );
532  childsfinished[s] = true;
533  return s == childsfinished.size() - 1;
534  }
535  }
536  return false;
537 }
538 
539 
542  SCIP* scip,
543  const char* detectorname,
544  SCIP_Bool transformed,
545  int* maxcallround,
546  int* mincallround,
547  int* freqcallround
548  )
549 {
550  char setstr[SCIP_MAXSTRLEN];
551  if( transformed )
552  {
553  (void) SCIPsnprintf( setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/maxcallround", detectorname );
554  SCIP_CALL( SCIPgetIntParam( scip, setstr, maxcallround ) );
555  (void) SCIPsnprintf( setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/mincallround", detectorname );
556  SCIP_CALL( SCIPgetIntParam( scip, setstr, mincallround ) );
557  (void) SCIPsnprintf( setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/freqcallround", detectorname );
558  SCIP_CALL_ABORT( SCIPgetIntParam( scip, setstr, freqcallround ) );
559  }
560  else
561  {
562  (void) SCIPsnprintf( setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origmaxcallround", detectorname );
563  SCIP_CALL( SCIPgetIntParam( scip, setstr, maxcallround ) );
564  (void) SCIPsnprintf( setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origmincallround", detectorname );
565  SCIP_CALL( SCIPgetIntParam( scip, setstr, mincallround ) );
566  (void) SCIPsnprintf( setstr, SCIP_MAXSTRLEN, "detection/detectors/%s/origfreqcallround", detectorname );
567  SCIP_CALL( SCIPgetIntParam( scip, setstr, freqcallround ) );
568  }
569 
570  return SCIP_OKAY;
571 }
572 
573 
576  SeeedPtr i,
577  SeeedPtr j
578  )
579 {
580  return ( i->getMaxWhiteScore() > j->getMaxWhiteScore() );
581 }
582 
583 
586  SeeedPtr i,
587  SeeedPtr j
588  )
589 {
590  return ( i->getScore( BORDER_AREA ) > j->getScore( BORDER_AREA ) );
591 }
592 
593 
596  SeeedPtr i,
597  SeeedPtr j
598  )
599 {
600  return ( i->getScore( CLASSIC ) > j->getScore( CLASSIC ) );
601 }
602 
604 SCIP_Bool cmpSeeedsFWhite(
605  SeeedPtr i,
606  SeeedPtr j
607  )
608 {
610 }
611 
614  SeeedPtr i,
615  SeeedPtr j
616  )
617 {
619 }
620 
621 
624  SeeedPtr i,
625  SeeedPtr j
626  )
627 {
628  return ( i->getScore( SETPART_FWHITE ) > j->getScore( SETPART_FWHITE ) );
629 }
630 
633  SeeedPtr i,
634  SeeedPtr j
635  )
636 {
637  return ( i->getScore( SETPART_AGG_FWHITE ) > j->getScore( SETPART_AGG_FWHITE ) );
638 }
639 
640 
643  SeeedPtr i,
644  SeeedPtr j
645  )
646 {
647  return ( i->getScore( BENDERS ) > j->getScore( BENDERS ) );
648 }
649 
650 
651 /* method to thin out the vector of given seeeds */
652 std::vector<SeeedPtr> thinout(
653  std::vector<SeeedPtr> finishedseeeds,
654  size_t ndecomps,
655  SCIP_Bool addtrivialdecomp
656  )
657 {
658  std::vector<SeeedPtr> justbest( 0 );
659  for( size_t dec = 0; dec < ndecomps && dec < finishedseeeds.size(); ++ dec )
660  {
661  justbest.push_back( finishedseeeds[dec] );
662  }
663 
664  if( addtrivialdecomp )
665  {
666  for( size_t dec = 0; dec < finishedseeeds.size(); ++ dec )
667  {
668  if( finishedseeeds[dec]->getNMasterconss() == 0 && finishedseeeds[dec]->getNLinkingvars() == 0
669  && finishedseeeds[dec]->getNBlocks() == 1 )
670  {
671  justbest.push_back( finishedseeeds[dec] );
672  }
673  }
674  }
675  return justbest;
676 }
677 
678 
681  std::string s,
682  std::string t
683  )
684 {
685  /* easy cases */
686  if( s.compare( t ) == 0 )
687  return 0;
688  if( s.length() == 0 )
689  return t.length();
690  if( t.length() == 0 )
691  return s.length();
692 
693  /* vectors to store integer distances */
694  std::vector<int> prev( t.length() + 1 );
695  std::vector<int> curr( t.length() + 1 );
696 
697  /* initialize prev (previous row of distances) */
698  for( size_t i = 0; i < prev.size(); ++i )
699  {
700  prev[i] = i;
701  }
702  for( size_t i = 0; i < s.length(); ++i )
703  {
704  /* calculate curr (row distances) from the previous one */
705 
706  curr[0] = i + 1;
707 
708  /* fill remaining of row using 'Bellman' equality */
709  for( size_t j = 0; j < t.length(); ++j )
710  {
711  int cost = ( s[i] == t[j] ) ? 0 : 1;
712  curr[j + 1] = std::min( curr[j] + 1, std::min( prev[j + 1] + 1, prev[j] + cost ) );
713  }
714 
715  /* copy curr to prev for next iteration */
716  for( size_t j = 0; j < prev.size(); ++j )
717  prev[j] = curr[j];
718  }
719 
720  return curr[t.length()];
721 }
722 
723 
726  char *str,
727  int *nremoved
728  )
729 {
730  char digits[11] = "0123456789";
731  * nremoved = 0;
732 
733  for( int i = 0; i < 10; ++ i )
734  {
735  char digit = digits[i];
736  size_t j = 0;
737  while( j < strlen( str ) )
738  {
739  if( str[j] == digit )
740  {
741  * nremoved = * nremoved + 1;
742  for( size_t k = j; k < strlen( str ); ++ k )
743  {
744  str[k] = str[k + 1];
745  }
746  }
747  else
748  ++ j;
749  }
750  }
751 }
752 
753 
755 int gcd(
756  int a,
757  int b
758  )
759 {
760  return b == 0 ? a : gcd( b, a % b );
761 }
762 
763 
766  SCIP* scip,
767  SCIP_CONS* cons
768  )
769 {
770  return cons;
771 }
772 
773 
776  SCIP* scip,
777  SCIP_VAR* var
778  )
779 {
780  return SCIPvarGetProbvar( var );
781 }
782 
785  SCIP* scip,
786  SCIP_VAR* var
787  )
788 {
789 
790  return ( SCIPisEQ(scip, SCIPvarGetLbGlobal(var), SCIPvarGetUbGlobal(var) ) && SCIPisEQ(scip, SCIPvarGetUbGlobal(var), 0. ) );
791 }
792 
793 
794 
797  SeeedPtr compseeed,
798  std::vector<SeeedPtr> const & seeeds,
799  bool sort
800  )
801 {
802  assert( compseeed != NULL );
803  SCIP_Bool isduplicate;
804 
805  for( size_t i = 0; i < seeeds.size(); ++ i )
806  {
807  assert( seeeds[i] != NULL );
808 
809  compseeed->isEqual( seeeds[i], & isduplicate, sort );
810  if( isduplicate )
811  return false;
812  }
813  return true;
814 }
815 
816 
819  SeeedPtr seeed,
820  std::vector<SeeedPtr> const & currseeeds,
821  std::vector<SeeedPtr> const & finishedseeeds,
822  bool sort
823  )
824 {
825  SCIP_Bool bool1 = seeedIsNoDuplicateOfSeeeds( seeed, currseeeds, sort );
826  SCIP_Bool bool2 = seeedIsNoDuplicateOfSeeeds( seeed, finishedseeeds, sort );
827  return ( bool1 && bool2 );
828 }
829 
830 
833  SCIP* givenScip,
834  const char* conshdlrName,
835  SCIP_Bool _transformed,
836  SCIP_Bool _benders
837  ) :
838  scip( givenScip ), incompleteSeeeds( 0 ), currSeeeds( 0 ), ancestorseeeds( 0 ), unpresolvedfixedtozerovars(0),
839  nVars( SCIPgetNVars( givenScip ) ), nConss( SCIPgetNConss( givenScip ) ), nDetectors( 0 ),
840  nFinishingDetectors( 0 ), nPostprocessingDetectors(0), nnonzeros( 0 ), candidatesNBlocks( 0 ), dualvalsrandom(std::vector<SCIP_Real>(0)), dualvalsoptimaloriglp(std::vector<SCIP_Real>(0)) , dualvalsrandomset(FALSE), dualvalsoptimaloriglpcalculated(FALSE), transformed( _transformed ), benders(_benders),
841  classificationtime(0.), nblockscandidatescalctime(0.), postprocessingtime(0.), scorecalculatingtime(0.), translatingtime(0.)
842 {
843  SCIP_CONS** conss;
844  SCIP_VAR** vars;
845 
846  int ndetectors;
847  DEC_Detector** detectors;
848  SCIP_Bool createconssadj;
849  SCIP_Bool useconnected;
850  SCIP_Bool useconssadj;
851 
852  createconssadj = TRUE;
853 
854  if( transformed )
855  SCIPgetBoolParam(scip, "detection/detectors/connectedbase/enabled", &useconnected);
856  else
857  SCIPgetBoolParam(scip, "detection/detectors/connectedbase/origenabled", &useconnected);
858 
859  SCIPgetBoolParam(scip, "detection/detectors/connectedbase/useconssadj", &useconssadj);
860 
861 
862  if( ! transformed )
863  {
864  nVars = SCIPgetNOrigVars( scip );
865  nConss = SCIPgetNOrigConss( scip );
866  }
867 
868  int relevantVarCounter = 0;
869  int relevantConsCounter = 0;
870 
873 
875  SCIP_CALL_ABORT( SCIPgetIntParam( givenScip, "detection/maxrounds", & maxndetectionrounds ) );
876 
877  assert( ndetectors > 0 );
878 
879 
881  for( int d = 0; d < ndetectors; ++d )
882  {
883  DEC_DETECTOR* detector;
884  detector = detectors[d];
885 
886  assert( detector != NULL );
887  if( transformed )
888  {
889  if( ! detector->enabled || detector->propagateSeeed == NULL )
890  continue;
891  }
892  else
893  {
894  if( ! detector->enabledOrig || detector->propagateSeeed == NULL )
895  continue;
896  }
897 
898  scipDetectorToIndex[detector] = nDetectors;
899  detectorToScipDetector.push_back( detector );
900  ++ nDetectors;
901  }
902 
904  for( int d = 0; d < ndetectors; ++d )
905  {
906  DEC_DETECTOR* detector;
907 
908  detector = detectors[d];
909  assert( detector != NULL );
910  if( ! detector->enabledFinishing || detector->finishSeeed == NULL )
911  continue;
912 
913  scipFinishingDetectorToIndex[detector] = nFinishingDetectors;
914  detectorToFinishingScipDetector.push_back( detector );
915  ++ nFinishingDetectors;
916  }
917 
919  for( int d = 0; d < ndetectors; ++d )
920  {
921  DEC_DETECTOR* detector;
922 
923  detector = detectors[d];
924  assert( detector != NULL );
925  if( ! detector->enabledPostprocessing || detector->postprocessSeeed == NULL )
926  continue;
927 
928  scipPostprocessingDetectorToIndex[detector] = nPostprocessingDetectors;
929  detectorToPostprocessingScipDetector.push_back( detector );
930  ++nPostprocessingDetectors;
931  }
932 
934  if( transformed )
935  {
936  conss = SCIPgetConss( scip );
937  vars = SCIPgetVars( scip );
938  }
939  else
940  {
941  conss = SCIPgetOrigConss( scip );
942  vars = SCIPgetOrigVars( scip );
943  }
944 
947  for( int i = 0; i < nConss; ++ i )
948  {
949  SCIP_CONS* relevantCons;
950 
951  relevantCons = transformed ? consGetRelevantRepr( scip, conss[i] ) : conss[i];
952 
953  if( SCIPconsIsDeleted( relevantCons ) || SCIPconsIsObsolete(relevantCons) )
954  {
955  continue;
956  }
957 
958 
959  if( relevantCons != NULL )
960  {
961  scipConsToIndex[relevantCons] = relevantConsCounter;
962  consToScipCons.push_back( relevantCons );
963  SCIPcaptureCons(scip, relevantCons);
964 
965  ++relevantConsCounter;
966  }
967  else
968  {
969  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "relevant cons is NULL\n");
970  }
971  }
972 
973  for( int i = 0; i < nVars; ++ i )
974  {
975  SCIP_VAR* relevantVar;
976 
977  relevantVar = NULL;
978 
979  if( transformed )
980  relevantVar = varGetRelevantRepr( scip, vars[i] );
981  else
982  relevantVar = vars[i];
983 
984 
985  if( varIsFixedToZero(scip, vars[i]) )
986  {
987  unpresolvedfixedtozerovars.push_back(relevantVar);
988  continue;
989  }
990 
991  if( relevantVar != NULL )
992  {
993  scipVarToIndex[relevantVar] = relevantVarCounter;
994  varToScipVar.push_back( relevantVar );
995  ++ relevantVarCounter;
996  }
997  }
998 
1000  nVars = relevantVarCounter;
1001  nConss = relevantConsCounter;
1002  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, " nvars: %d / nconss: %d \n", nVars, nConss );
1003  varsForConss = std::vector<std::vector<int>>( nConss );
1004  valsForConss = std::vector < std::vector < SCIP_Real >> ( nConss );
1005  conssForVars = std::vector<std::vector<int>>( nVars );
1006 
1007  assert( (int) varToScipVar.size() == nVars );
1008  assert( (int) consToScipCons.size() == nConss );
1009 
1013  for( int i = 0; i < (int) consToScipCons.size(); ++ i )
1014  {
1015  SCIP_CONS* cons;
1016  SCIP_VAR** currVars;
1017  SCIP_Real* currVals;
1018  int nCurrVars;
1019 
1020  cons = consToScipCons[i];
1021 
1022  nCurrVars = GCGconsGetNVars( scip, cons );
1023 
1024  if( nCurrVars == 0 )
1025  continue;
1026 
1027  assert(SCIPconsGetName( cons) != NULL);
1028 
1029  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & currVars, nCurrVars ) );
1030  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & currVals, nCurrVars ) );
1031  SCIP_CALL_ABORT( GCGconsGetVars( scip, cons, currVars, nCurrVars ) );
1032  SCIP_CALL_ABORT( GCGconsGetVals( scip, cons, currVals, nCurrVars ) );
1033 
1034  for( int currVar = 0; currVar < nCurrVars; ++ currVar )
1035  {
1036  int varIndex;
1037  unordered_map<SCIP_VAR*, int>::const_iterator iterVar;
1038 
1039  if( varIsFixedToZero(scip, currVars[currVar]) )
1040  continue;
1041 
1042  /*@todo remove this after the bug is fixed */
1043  /* because of the bug of GCGconsGet*()-methods some variables have to be negated */
1044  if( ! SCIPvarIsNegated( currVars[currVar] ) )
1045  iterVar = scipVarToIndex.find( currVars[currVar] );
1046  else
1047  iterVar = scipVarToIndex.find( SCIPvarGetNegatedVar( currVars[currVar] ) );
1048 
1049  if( iterVar == scipVarToIndex.end() )
1050  continue;
1051 
1052  varIndex = iterVar->second;
1053 
1054  varsForConss[i].push_back( varIndex );
1055  conssForVars[varIndex].push_back( i );
1056  valsForConss[i].push_back( currVals[currVar] );
1057  valsMap[std::pair<int, int>( i, varIndex )] = currVals[currVar];
1058  ++ nnonzeros;
1059  }
1060  SCIPfreeBufferArrayNull( scip, & currVals );
1061  SCIPfreeBufferArrayNull( scip, & currVars );
1062 
1063  }
1064 
1065  SCIPgetBoolParam(scip, "detection/conssadjcalculated", &createconssadj );
1066  createconssadj = createconssadj && (getNConss() < 1000);
1067 
1068  if( !createconssadj )
1069  SCIPsetBoolParam(scip, "detection/conssadjcalculated", FALSE );
1070 
1071  if( createconssadj )
1072  {
1074  }
1075 
1076  /* init seeedpool with empty seeed */
1077  SeeedPtr emptyseeed = new Seeed( scip, SCIPconshdlrDecompGetNextSeeedID( scip ), this );
1078  SCIP_Bool onlybinmaster;
1079  SCIP_Bool onlycontsubpr;
1080 
1081  SCIPgetBoolParam(scip, "detection/benders/onlybinmaster", &onlybinmaster);
1082  SCIPgetBoolParam(scip, "detection/benders/onlycontsubpr", &onlycontsubpr);
1083  if( onlybinmaster )
1084  {
1085  emptyseeed->initOnlyBinMaster();
1086  emptyseeed->considerImplicits();
1087  }
1088 
1089 
1090  addSeeedToCurr( emptyseeed );
1091  addSeeedToAncestor(emptyseeed);
1092 
1093  for( int i = 0; i < SCIPconshdlrDecompGetNBlockNumberCandidates( scip ); ++i )
1094  {
1096  }
1097 
1098 } //end constructor
1099 
1100 
1103 {
1104  for( int c = 0; c < nConss; ++c )
1105  {
1106  SCIP_CONS* cons;
1107 
1108  cons = getConsForIndex(c);
1109  SCIPreleaseCons(scip, &cons);
1110  }
1111 
1112 
1113  for( size_t i = 0; i < ancestorseeeds.size(); ++i )
1114  {
1115  size_t help = ancestorseeeds.size() - i - 1;
1116  if( ancestorseeeds[help] != NULL && ancestorseeeds[help]->getID() >= 0 )
1117  {
1118  delete ancestorseeeds[help];
1119  }
1120 
1121  }
1122 
1123 
1124  for( size_t i = 0; i < finishedSeeeds.size(); ++i )
1125  {
1126  size_t help = finishedSeeeds.size() - i - 1;
1127  if( finishedSeeeds[help] != NULL && finishedSeeeds[help]->getID() >= 0 )
1128  {
1129  delete finishedSeeeds[help];
1130  }
1131  }
1132 
1133  for( size_t i = 0; i < incompleteSeeeds.size(); ++i )
1134  {
1135  size_t help = incompleteSeeeds.size() - i - 1;
1136  if( incompleteSeeeds[help] != NULL && incompleteSeeeds[help]->getID() >= 0 )
1137  delete incompleteSeeeds[help];
1138  }
1139 
1140 
1141  for( size_t i = 0; i < consclassescollection.size(); ++ i )
1142  {
1143  size_t help = consclassescollection.size() - i - 1;
1144  if( consclassescollection[help] != NULL )
1145  delete consclassescollection[help];
1146  }
1147 
1148  for( size_t i = 0; i < varclassescollection.size(); ++ i )
1149  {
1150  size_t help = varclassescollection.size() - i - 1;
1151  if( varclassescollection[help] != NULL )
1152  delete varclassescollection[help];
1153  }
1154 }
1155 
1156 
1159  SCIP* givenScip
1160  )
1161 {
1162  SCIP_Bool conssclassnnonzeros;
1163  SCIP_Bool conssclassscipconstypes;
1164  SCIP_Bool conssclassmiplibconstypes;
1165  SCIP_Bool conssclassconsnamenonumbers;
1166  SCIP_Bool conssclassconsnamelevenshtein;
1167  SCIP_Bool varclassscipvartypes;
1168  SCIP_Bool varclassobjvals;
1169  SCIP_Bool varclassobjvalsigns;
1170  SCIP_CLOCK* classificationclock;
1171  SCIP_CLOCK* nblockcandnclock;
1172 
1173  SCIPcreateClock( scip, & classificationclock );
1174  SCIPcreateClock( scip, & nblockcandnclock );
1175  SCIP_CALL( SCIPstartClock( scip, classificationclock ) );
1176 
1177  if( transformed )
1178  {
1179  SCIPgetBoolParam( scip, "detection/consclassifier/nnonzeros/enabled", & conssclassnnonzeros );
1180  SCIPgetBoolParam( scip, "detection/consclassifier/scipconstype/enabled", & conssclassscipconstypes );
1181  SCIPgetBoolParam( scip, "detection/consclassifier/miplibconstype/enabled", & conssclassmiplibconstypes );
1182  SCIPgetBoolParam( scip, "detection/consclassifier/consnamenonumbers/enabled", & conssclassconsnamenonumbers );
1183  SCIPgetBoolParam( scip, "detection/consclassifier/consnamelevenshtein/enabled", & conssclassconsnamelevenshtein );
1184  SCIPgetBoolParam( scip, "detection/varclassifier/scipvartype/enabled", & varclassscipvartypes );
1185  SCIPgetBoolParam(scip, "detection/varclassifier/objectivevalues/enabled", &varclassobjvals);
1186  SCIPgetBoolParam(scip, "detection/varclassifier/objectivevaluesigns/enabled", &varclassobjvalsigns);
1187  }
1188  else
1189  {
1190  SCIPgetBoolParam( scip, "detection/consclassifier/nnonzeros/origenabled", & conssclassnnonzeros );
1191  SCIPgetBoolParam( scip, "detection/consclassifier/scipconstype/origenabled", & conssclassscipconstypes );
1192  SCIPgetBoolParam( scip, "detection/consclassifier/miplibconstype/origenabled", & conssclassmiplibconstypes );
1193  SCIPgetBoolParam( scip, "detection/consclassifier/consnamenonumbers/origenabled", & conssclassconsnamenonumbers );
1194  SCIPgetBoolParam( scip, "detection/consclassifier/consnamelevenshtein/origenabled", & conssclassconsnamelevenshtein );
1195  SCIPgetBoolParam( scip, "detection/varclassifier/scipvartype/origenabled", & varclassscipvartypes );
1196  SCIPgetBoolParam(scip, "detection/varclassifier/objectivevalues/origenabled", &varclassobjvals);
1197  SCIPgetBoolParam(scip, "detection/varclassifier/objectivevaluesigns/origenabled", &varclassobjvalsigns);
1198  }
1199 
1200 
1201 
1202  if( conssclassnnonzeros )
1204  if( conssclassscipconstypes )
1206  if( conssclassmiplibconstypes )
1208 
1209  if( conssclassconsnamenonumbers )
1211  if( conssclassconsnamelevenshtein )
1213 
1214  if( varclassscipvartypes )
1216  if ( varclassobjvals )
1218  if ( varclassobjvalsigns )
1220 
1221 
1223  reduceVarclasses();
1224 
1225  SCIP_CALL( SCIPstopClock( scip, classificationclock ) );
1226  classificationtime = SCIPgetClockTime( scip, classificationclock );
1227  SCIPfreeClock( scip, & classificationclock );
1228 
1229  SCIP_CALL( SCIPstartClock( scip, nblockcandnclock ) );
1231  SCIP_CALL( SCIPstopClock( scip, nblockcandnclock ) );
1232  nblockscandidatescalctime = SCIPgetClockTime( scip, nblockcandnclock );
1233  SCIPfreeClock( scip, & nblockcandnclock );
1234 
1235 
1236  return SCIP_OKAY;
1237 }
1238 
1240 {
1241 
1242  std::vector<std::list<int>> conssadjacenciestemp( consToScipCons.size(), std::list<int>(0) );
1243 
1245  for( size_t i = 0; i < consToScipCons.size(); ++i )
1246  {
1247  for( size_t varid = 0; varid < varsForConss[i].size(); ++varid )
1248  {
1249  int var = varsForConss[i][varid];
1250 
1251  for( size_t otherconsid = 0; otherconsid < conssForVars[var].size(); ++otherconsid )
1252  {
1253  int othercons = conssForVars[var][otherconsid];
1254  if( othercons == (int) i )
1255  continue;
1256 
1257  std::list<int>::iterator consiter = std::lower_bound( conssadjacenciestemp[i].begin(),conssadjacenciestemp[i].end(), othercons);
1258 
1259  if( consiter == conssadjacenciestemp[i].end() || *consiter != othercons )
1260  conssadjacenciestemp[i].insert(consiter, othercons);
1261  }
1262  }
1263 
1264  }
1265 
1266  for( size_t i = 0; i < consToScipCons.size(); ++ i )
1267  {
1268  conssadjacencies.push_back(std::vector<int>(0));
1269  std::list<int>::iterator consiter = conssadjacenciestemp[i].begin();
1270  std::list<int>::iterator consiterend = conssadjacenciestemp[i].end();
1271  for( ; consiter != consiterend; ++consiter )
1272  {
1273  conssadjacencies[i].push_back(*consiter);
1274  }
1275  }
1276 
1277 }
1278 
1279 
1280 
1283 std::vector<SeeedPtr> Seeedpool::findSeeeds()
1284 {
1291  bool displaySeeeds = false;
1292  int verboseLevel;
1293  std::vector<int> successDetectors;
1294  std::vector<SeeedPtr> delSeeeds;
1295  bool duplicate;
1296  SCIP_CLOCK* postprocessingclock;
1297  SCIPcreateClock( scip, & postprocessingclock );
1298 
1299 
1300  successDetectors = std::vector<int>( nDetectors, 0 );
1301 
1302  delSeeeds = std::vector < SeeedPtr > ( 0 );
1303 
1304  verboseLevel = 1;
1305 
1307  SCIP_CALL_ABORT( SCIPgetIntParam( scip, "detection/maxrounds", & maxndetectionrounds ) );
1308 
1309 
1311  for( size_t i = 0; i < currSeeeds.size(); ++ i )
1312  {
1313  SCIP_CALL_ABORT( prepareSeeed( currSeeeds[i] ) );
1314  if( currSeeeds[i]->getID() < 0 )
1315  currSeeeds[i]->setID(getNewIdForSeeed() );
1316  }
1317 
1319  for( size_t i = 0; i < seeedstopopulate.size(); ++ i )
1320  {
1321  SCIP_CALL_ABORT( prepareSeeed( seeedstopopulate[i] ) );
1322  if( seeedIsNoDuplicateOfSeeeds( seeedstopopulate[i], currSeeeds, true ) )
1323  currSeeeds.push_back( seeedstopopulate[i] );
1324  else
1325  continue;
1326  if( seeedstopopulate[i]->getID() < 0 )
1327  seeedstopopulate[i]->setID(getNewIdForSeeed() );
1328  }
1329 
1330  for( int round = 0; round < maxndetectionrounds; ++ round )
1331  {
1332  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Begin of detection round %d of %d total rounds \n", round, maxndetectionrounds);
1333  if( currSeeeds.size() == 0 )
1334  {
1335  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Detection loop can be aborted since there are no more partial decompositions to refine! \n" );
1336  break;
1337  }
1338 
1339 
1340  std::vector<SeeedPtr> nextSeeeds = std::vector < SeeedPtr > ( 0 );
1341  std::vector<SeeedPtr> currSeeedsToDelete = std::vector < SeeedPtr > ( 0 );
1342 
1343 #pragma omp parallel for schedule( static, 1 )
1344  for( size_t s = 0; s < currSeeeds.size(); ++ s )
1345  {
1346  SeeedPtr seeedPtr;
1347  seeedPtr = currSeeeds[s];
1348 
1349 #pragma omp critical ( ostream )
1350  {
1351  if( displaySeeeds || verboseLevel >= 1 )
1352  {
1353  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Start to propagate seeed with id %d (%d of %d in round %d) \n", seeedPtr->getID(), s, currSeeeds.size(), round);
1354  if( displaySeeeds )
1355  seeedPtr->displaySeeed();
1356  }
1357  }
1358 
1360  for( int d = 0; d < nDetectors; ++ d )
1361  {
1362  SEEED_PROPAGATION_DATA* seeedPropData;
1363  seeedPropData = new SEEED_PROPAGATION_DATA();
1364  seeedPropData->seeedpool = this;
1365  seeedPropData->nNewSeeeds = 0;
1366  DEC_DETECTOR* detector;
1367  std::vector<SeeedPtr>::const_iterator newSIter;
1368  std::vector<SeeedPtr>::const_iterator newSIterEnd;
1369  int maxcallround;
1370  int mincallround;
1371  int freqcallround;
1372  const char* detectorname;
1373  SCIP_CLOCK* detectorclock;
1374 
1375  detector = detectorToScipDetector[d];
1376  detectorname = DECdetectorGetName( detector );
1377  SCIP_RESULT result = SCIP_DIDNOTFIND;
1378 
1380  if( seeedPtr->isPropagatedBy( detector ) && ! detector->usefulRecall )
1381  continue;
1382 
1384  SCIP_CALL_ABORT(
1385  getDetectorCallRoundInfo( scip, detectorname, transformed, & maxcallround, & mincallround,
1386  & freqcallround ) );
1387 
1388  if( maxcallround < round || mincallround > round || ( ( round - mincallround ) % freqcallround != 0 ) )
1389  continue;
1390 
1391 #pragma omp critical ( seeedcount )
1392  seeedPropData->seeedToPropagate = new gcg::Seeed( seeedPtr );
1393 
1395 #pragma omp critical ( clock )
1396  SCIPcreateClock( scip, & detectorclock );
1397  SCIP_CALL_ABORT( SCIPstartClock( scip, detectorclock ) );
1398 
1399  if( verboseLevel >= 1 )
1400  {
1401 #pragma omp critical ( scipinfo )
1402  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, "Detector %s started to propagate seeed with id %d ) \n",
1403  DECdetectorGetName( detectorToScipDetector[d] ), seeedPtr->getID() );
1404  }
1405 
1406  SCIP_CALL_ABORT(
1407  detectorToScipDetector[d]->propagateSeeed( scip, detectorToScipDetector[d], seeedPropData, & result ) );
1408 
1409  for( int j = 0; j < seeedPropData->nNewSeeeds; ++ j )
1410  {
1411 #pragma omp critical ( seeedcount )
1412 
1413  seeedPropData->newSeeeds[j]->setID( getNewIdForSeeed() );
1414  prepareSeeed( seeedPropData->newSeeeds[j] );
1415  assert( seeedPropData->newSeeeds[j]->checkConsistency( ) );
1416  seeedPropData->newSeeeds[j]->addDecChangesFromAncestor( seeedPtr );
1417  seeedPropData->newSeeeds[j]->setDetectorPropagated(detectorToScipDetector[d]);
1418  }
1419 
1420  SCIP_CALL_ABORT( SCIPstopClock( scip, detectorclock ) );
1421 
1422 #pragma omp critical ( clockcount )
1423  detectorToScipDetector[d]->dectime += SCIPgetClockTime( scip, detectorclock );
1424 
1425 #pragma omp critical ( clock )
1426  SCIPfreeClock( scip, & detectorclock );
1427 
1428  if( seeedPropData->nNewSeeeds != 0 && ( displaySeeeds ) )
1429  {
1430 #pragma omp critical ( ostream )
1431  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, "Detector %s found %d new seeed%s: \n",
1432  DECdetectorGetName( detectorToScipDetector[d] ), seeedPropData->nNewSeeeds, (seeedPropData->nNewSeeeds == 1 ? "": "s") );
1433 #pragma omp critical ( ostream )
1434  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, "%d", seeedPropData->newSeeeds[0]->getID() );
1435  for( int j = 1; j < seeedPropData->nNewSeeeds; ++ j )
1436  {
1437 #pragma omp critical ( ostream )
1438  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, ", %d", seeedPropData->newSeeeds[0]->getID() );
1439  }
1440 #pragma omp critical ( ostream )
1441  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, "\n" );
1442 
1443  if( displaySeeeds )
1444  {
1445  for( int j = 0; j < seeedPropData->nNewSeeeds; ++ j )
1446  {
1447 #pragma omp critical ( ostream )
1448  seeedPropData->newSeeeds[j]->displaySeeed();
1449  }
1450 
1451  }
1452  }
1453  else if( displaySeeeds )
1454  {
1455 #pragma omp critical ( ostream )
1456  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, "Detector %s found 0 new seeeds.\n", DECdetectorGetName( detectorToScipDetector[d] ) );
1457  }
1458 
1460  for( int seeed = 0; seeed < seeedPropData->nNewSeeeds; ++ seeed )
1461  {
1462  SCIP_Bool noduplicate;
1463  if( seeedPropData->newSeeeds[seeed]->isComplete() )
1464  seeedPropData->newSeeeds[seeed]->deleteEmptyBlocks(false);
1465 #pragma omp critical ( seeedptrstore )
1466  noduplicate = seeedIsNoDuplicate( seeedPropData->newSeeeds[seeed], nextSeeeds, finishedSeeeds, false );
1467  if( ! seeedPropData->newSeeeds[seeed]->isTrivial() && noduplicate )
1468  {
1469  if( seeedPropData->newSeeeds[seeed]->getNOpenconss() == 0
1470  && seeedPropData->newSeeeds[seeed]->getNOpenvars() == 0 )
1471  {
1472  if( verboseLevel > 2 )
1473  {
1474 #pragma omp critical ( ostream )
1475  {
1476  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, "Seeed %d is added to finished seeeds.\n", seeedPropData->newSeeeds[seeed]->getID() );
1477  seeedPropData->newSeeeds[seeed]->showVisualisation();
1478  }
1479  }
1480 #pragma omp critical ( seeedptrstore )
1481  {
1482  assert( seeedPropData->newSeeeds[seeed]->getID() >= 0 );
1483  addSeeedToFinished( seeedPropData->newSeeeds[seeed], &noduplicate );
1484  }
1485  }
1486  else
1487  {
1488  if( verboseLevel > 2 )
1489  {
1490 #pragma omp critical ( ostream )
1491  {
1492  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, "Seeed %d is addded to next round seeeds!\n", seeedPropData->newSeeeds[seeed]->getID() );
1493  seeedPropData->newSeeeds[seeed]->showVisualisation();
1494  }
1495  }
1496 #pragma omp critical ( seeedptrstore )
1497  {
1498  nextSeeeds.push_back( seeedPropData->newSeeeds[seeed] );
1499  }
1500  }
1501  }
1502  else
1503  {
1504  delete seeedPropData->newSeeeds[seeed];
1505  seeedPropData->newSeeeds[seeed] = NULL;
1506  }
1507  }
1508 
1510  delete seeedPropData->seeedToPropagate;
1511  SCIPfreeMemoryArrayNull( scip, & seeedPropData->newSeeeds );
1512  seeedPropData->newSeeeds = NULL;
1513  seeedPropData->nNewSeeeds = 0;
1514  delete seeedPropData;
1515  } // end for detectors
1516 
1517  SCIPverbMessage( scip, SCIP_VERBLEVEL_HIGH, NULL, "Start finishing of partial decomposition %d.\n", seeedPtr->getID() );
1518  for( int d = 0; d < nFinishingDetectors; ++ d )
1519  {
1520  DEC_DETECTOR* detector = detectorToFinishingScipDetector[d];
1521  SCIP_RESULT result = SCIP_DIDNOTFIND;
1522  SEEED_PROPAGATION_DATA* seeedPropData;
1523  seeedPropData = new SEEED_PROPAGATION_DATA();
1524  seeedPropData->seeedpool = this;
1525  seeedPropData->nNewSeeeds = 0;
1526 #pragma omp critical ( seeedcount )
1527  seeedPropData->seeedToPropagate = new gcg::Seeed( seeedPtr );
1528 
1529  if( verboseLevel > 2 )
1530 #pragma omp critical ( ostream )
1531  {
1532  SCIPverbMessage( scip, SCIP_VERBLEVEL_FULL, NULL, "Check if finisher of detector %s is enabled. \n", DECdetectorGetName( detectorToFinishingScipDetector[d] ) );
1533  }
1534 
1536  if( ! detector->enabledFinishing )
1537  continue;
1538 
1539  if( verboseLevel > 2 )
1540 #pragma omp critical ( ostream )
1541  {
1542  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "Call finisher for detector %s\n",
1543  DECdetectorGetName( detectorToFinishingScipDetector[d] ) );
1544  }
1545  SCIP_CALL_ABORT(
1546  detectorToFinishingScipDetector[d]->finishSeeed( scip, detectorToFinishingScipDetector[d], seeedPropData,
1547  & result ) );
1548 
1549  for( int finished = 0; finished < seeedPropData->nNewSeeeds; ++ finished )
1550  {
1551  SeeedPtr seeed = seeedPropData->newSeeeds[finished];
1552  seeed->deleteEmptyBlocks(false);
1553 #pragma omp critical ( seeedcount )
1554  seeed->setID( getNewIdForSeeed() );
1555  seeed->sort();
1556  seeed->calcHashvalue();
1557  seeed->setSeeedpool(this);
1558  seeed->addDecChangesFromAncestor( seeedPtr );
1559  seeed->setFinishedByFinisher( true );
1560  seeed->setFinishingDetectorPropagated(detectorToFinishingScipDetector[d]);
1561 #pragma omp critical ( seeedptrstore )
1562  {
1563  SCIP_Bool success;
1564  addSeeedToFinished( seeed, &success );
1565  if( !success )
1566  {
1567  bool isIdentical = false;
1568  for( size_t h = 0; h < finishedSeeeds.size(); ++ h )
1569  {
1570  if( seeed == finishedSeeeds[h] )
1571  {
1572  isIdentical = true;
1573  break;
1574  }
1575  }
1576 
1577  if( ! isIdentical )
1578  {
1579  currSeeedsToDelete.push_back( seeed );
1580  }
1581  }
1582  }
1583  }
1584  SCIPfreeMemoryArrayNull( scip, & seeedPropData->newSeeeds );
1585  delete seeedPropData->seeedToPropagate;
1586  seeedPropData->newSeeeds = NULL;
1587  seeedPropData->nNewSeeeds = 0;
1588  delete seeedPropData;
1589  }
1590  #pragma omp critical (seeedptrstore)
1591  addSeeedToAncestor(seeedPtr);
1592  } // end for currseeeds
1593 
1594  for( size_t s = 0; s < currSeeedsToDelete.size(); ++ s )
1595  {
1596  delete currSeeedsToDelete[s];
1597  currSeeedsToDelete[s] = NULL;
1598  }
1599 
1600  currSeeeds = nextSeeeds;
1601  } // end for rounds
1602 
1604 #pragma omp parallel for schedule( static, 1 )
1605  for( size_t i = 0; i < currSeeeds.size(); ++ i )
1606  {
1607  SeeedPtr seeedPtr = currSeeeds[i];
1608  for( int d = 0; d < nFinishingDetectors; ++ d )
1609  {
1610  DEC_DETECTOR* detector = detectorToFinishingScipDetector[d];
1611  SCIP_RESULT result = SCIP_DIDNOTFIND;
1612  SEEED_PROPAGATION_DATA* seeedPropData;
1613  seeedPropData = new SEEED_PROPAGATION_DATA();
1614  seeedPropData->seeedpool = this;
1615  seeedPropData->nNewSeeeds = 0;
1616 
1617 #pragma omp critical ( seeedcount )
1618  seeedPropData->seeedToPropagate = new gcg::Seeed( seeedPtr );
1619 
1620  if( verboseLevel > 2 )
1621  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "check if finisher of detector %s is enabled\n",
1622  DECdetectorGetName( detectorToFinishingScipDetector[d] ) );
1623 
1625  if( ! detector->enabledFinishing )
1626  continue;
1627 
1628  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "call finisher for detector %s \n", DECdetectorGetName( detectorToFinishingScipDetector[d] ) );
1629 
1630  SCIP_CALL_ABORT(
1631  detectorToFinishingScipDetector[d]->finishSeeed( scip, detectorToFinishingScipDetector[d], seeedPropData,
1632  & result ) );
1633 
1634  for( int finished = 0; finished < seeedPropData->nNewSeeeds; ++ finished )
1635  {
1636  SeeedPtr seeed = seeedPropData->newSeeeds[finished];
1637  seeed->deleteEmptyBlocks(false);
1638 #pragma omp critical ( seeedcount )
1639  seeed->setID( getNewIdForSeeed() );
1640 
1641  seeed->calcHashvalue();
1642  seeed->addDecChangesFromAncestor( seeedPtr );
1643  seeed->setFinishedByFinisher( true );
1644  seeed->setSeeedpool(this);
1645  seeed->setFinishingDetectorPropagated(detectorToFinishingScipDetector[d] );
1646 
1647  if( seeedIsNoDuplicateOfSeeeds( seeed, finishedSeeeds, false ) )
1648  {
1649  if( verboseLevel > 2 )
1650  {
1651  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, " Seeed %d is finished from next round seeeds!\n", seeed->getID() );
1652  seeed->showVisualisation();
1653  }
1654 #pragma omp critical ( seeedptrstore )
1655  {
1656  SCIP_Bool success;
1657  assert( seeed->getID() >= 0 );
1658  addSeeedToFinished( seeed, &success );
1659  }
1660  }
1661  else
1662  delete seeed;
1663 
1664  SCIPfreeMemoryArrayNull( scip, & seeedPropData->newSeeeds );
1665  seeedPropData->newSeeeds = NULL;
1666  seeedPropData->nNewSeeeds = 0;
1667  }
1668 
1669  delete seeedPropData->seeedToPropagate;
1670  delete seeedPropData;
1671  }
1672 #pragma omp critical ( seeedptrstore )
1673  addSeeedToAncestor(seeedPtr);
1674  } // end for finishing curr seeeds
1675 
1676  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "%d finished seeeds are found.\n", (int) finishedSeeeds.size() );
1677 
1678  if( displaySeeeds )
1679  {
1680  for( size_t i = 0; i < finishedSeeeds.size(); ++ i )
1681  {
1682  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "%d-th finished seeed:\n", (int) i );
1683  finishedSeeeds[i]->displaySeeed();
1684  }
1685  }
1686 
1688  for( size_t i = 0; i < finishedSeeeds.size(); ++ i )
1689  {
1690  assert( finishedSeeeds[i]->checkConsistency( ) );
1691  assert( finishedSeeeds[i]->getNOpenconss() == 0 );
1692  assert( finishedSeeeds[i]->getNOpenvars() == 0 );
1693 
1694  SCIP_CALL_ABORT( finishedSeeeds[i]->buildDecChainString() );
1695  for( int d = 0; d < nDetectors; ++ d )
1696  {
1697  if( finishedSeeeds[i]->isPropagatedBy( detectorToScipDetector[d] ) )
1698  successDetectors[d] += 1;
1699  }
1700  }
1701 
1704  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Measured running time per detector: \n" );
1705 
1706  for( int i = 0; i < nDetectors; ++ i )
1707  {
1708  if( SCIPgetVerbLevel(scip) >= SCIP_VERBLEVEL_HIGH )
1709  {
1710  std::cout << "Detector " << std::setw( 25 ) << std::setiosflags( std::ios::left )
1711  << DECdetectorGetName( detectorToScipDetector[i] ) << " \t worked on \t " << successDetectors[i] << " of "
1712  << finishedSeeeds.size() << "\t and took a total time of \t" << detectorToScipDetector[i]->dectime << std::endl;
1713  }
1714  }
1715 
1716  SCIPdebugMessage("Started score calculating of finished decompositions\n");
1717  if( (int) finishedSeeeds.size() != 0 )
1718  {
1719  SCIP_Real maxscore = finishedSeeeds[0]->getScore( SCIPconshdlrDecompGetCurrScoretype( scip ) );
1720  // SeeedPtr bestSeeed = finishedSeeeds[0];
1721  for( size_t i = 1; i < finishedSeeeds.size(); ++ i )
1722  {
1723  SCIP_Real score = finishedSeeeds[i]->getScore( SCIPconshdlrDecompGetCurrScoretype( scip ) );
1724  if( score > maxscore )
1725  {
1726  maxscore = score;
1727  }
1728  }
1729  }
1730  SCIPdebugMessage("Finished score calculating of finished decompositions\n");
1731 
1732  SCIPdebugMessage("Started marking curr seeeds for deletion\n");
1734  for( size_t c = 0; c < currSeeeds.size(); ++c )
1735  {
1736  duplicate = false;
1737  SCIP_CALL_ABORT( currSeeeds[c]->buildDecChainString() );
1738  for( size_t d = 0; d < delSeeeds.size(); ++ d )
1739  {
1740  if( currSeeeds[c] == delSeeeds[d] )
1741  {
1742  duplicate = true;
1743  break;
1744  }
1745  }
1746  if( ! duplicate )
1747  {
1748  delSeeeds.push_back( currSeeeds[c] );
1749  }
1750  }
1751 
1753  std::vector<SeeedPtr >postprocessed(0);
1754  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "Started postprocessing of decompositions...\n");
1755  SCIP_CALL_ABORT( SCIPstartClock( scip, postprocessingclock ) );
1756 #pragma omp parallel for schedule( static, 1 )
1757  for( size_t c = 0 ; c < finishedSeeeds.size(); ++c )
1758  {
1759  SeeedPtr seeedPtr = finishedSeeeds[c];
1760  for( int d = 0; d < getNPostprocessingDetectors(); ++d )
1761  {
1762  DEC_DETECTOR* detector = detectorToPostprocessingScipDetector[d];
1763  SCIP_RESULT result = SCIP_DIDNOTFIND;
1764  SEEED_PROPAGATION_DATA* seeedPropData;
1765  seeedPropData = new SEEED_PROPAGATION_DATA();
1766  seeedPropData->seeedpool = this;
1767  seeedPropData->nNewSeeeds = 0;
1768 
1769 #pragma omp critical ( seeedcount )
1770  seeedPropData->seeedToPropagate = new gcg::Seeed( seeedPtr );
1771 
1772  if( verboseLevel > 2 )
1773  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "check if postprocessor of detector %s is enabled\n",
1774  DECdetectorGetName( detectorToPostprocessingScipDetector[d] ) );
1775 
1777  if( ! detector->enabledPostprocessing )
1778  continue;
1779 
1780 
1781  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "call finisher for detector %s \n", DECdetectorGetName( detectorToPostprocessingScipDetector[d] ) );
1782 
1783  SCIP_CALL_ABORT(
1784  detectorToPostprocessingScipDetector[d]->postprocessSeeed( scip, detectorToPostprocessingScipDetector[d], seeedPropData,
1785  & result ) );
1786 
1787  for( int finished = 0; finished < seeedPropData->nNewSeeeds; ++ finished )
1788  {
1789  SeeedPtr seeed = seeedPropData->newSeeeds[finished];
1790 #pragma omp critical ( seeedcount )
1791  seeed->setID( getNewIdForSeeed() );
1792 
1793  seeed->calcHashvalue();
1794  seeed->addDecChangesFromAncestor( seeedPtr );
1795  seeed->setFinishedByFinisher( true );
1796  seeed->setSeeedpool(this);
1797  seeed->setDetectorPropagated(detectorToPostprocessingScipDetector[d]);
1798 
1799  if( seeedIsNoDuplicateOfSeeeds( seeed, finishedSeeeds, false ) && seeedIsNoDuplicateOfSeeeds( seeed, postprocessed, false ) )
1800  {
1801  if( verboseLevel > 2 )
1802  {
1803  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, " Seeed %d is finished from next round seeeds!\n", seeed->getID() );
1804  seeed->showVisualisation();
1805  }
1806 #pragma omp critical ( seeedptrstore )
1807  {
1808  assert( seeed->getID() >= 0 );
1809  postprocessed.push_back( seeed);
1810  }
1811  }
1812  else
1813  delete seeed;
1814 
1815  }
1816  SCIPfreeMemoryArrayNull( scip, & seeedPropData->newSeeeds );
1817  seeedPropData->newSeeeds = NULL;
1818  seeedPropData->nNewSeeeds = 0;
1819  delete seeedPropData->seeedToPropagate;
1820  delete seeedPropData;
1821  }
1822 //#pragma omp critical ( seeedptrstore )
1823 // addSeeedToAncestor(seeedPtr);
1824 
1825  } // end for postprocessing finished seeeds
1826  SCIP_CALL_ABORT( SCIPstopClock( scip, postprocessingclock ) );
1827  postprocessingtime = SCIPgetClockTime( scip, postprocessingclock );
1828  for( size_t c = 0; c < postprocessed.size(); ++c)
1829  addSeeedToFinishedUnchecked(postprocessed[c]);
1830  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "...finished postprocessing of decompositions. Added %d new decomps. \n", postprocessed.size());
1831  SCIP_CALL_ABORT( SCIPfreeClock( scip, & postprocessingclock ) );
1832 
1833 
1835  return finishedSeeeds;
1836  }
1837 
1838 
1839 /* sorts seeeds in finished seeeds data structure according to their score */
1841 {
1843  std::sort(finishedSeeeds.begin(), finishedSeeeds.end(), cmpSeeedsMaxWhite);
1844 
1846  std::sort(finishedSeeeds.begin(), finishedSeeeds.end(), cmpSeeedsBorderArea);
1847 
1849  std::sort(finishedSeeeds.begin(), finishedSeeeds.end(), cmpSeeedsClassic);
1850 
1852  std::sort(finishedSeeeds.begin(), finishedSeeeds.end(), cmpSeeedsFWhite);
1853 
1855  std::sort(finishedSeeeds.begin(), finishedSeeeds.end(), cmpSeeedsAggFWhite);
1856 
1858  std::sort(finishedSeeeds.begin(), finishedSeeeds.end(), cmpSeeedsPPCfWhite);
1859 
1861  std::sort(finishedSeeeds.begin(), finishedSeeeds.end(), cmpSeeedsPPCaggFWhite);
1862 
1864  std::sort(finishedSeeeds.begin(), finishedSeeeds.end(), cmpSeeedsBenders);
1865 
1866 
1867 }
1868 
1872  std::vector<SeeedPtr> incompleteseeeds
1873  )
1874 {
1875  std::vector<SeeedPtr> finisheds( 0, NULL );
1876  int verboseLevel = 1;
1877 
1878 #pragma omp parallel for schedule( static, 1 )
1879  for( size_t i = 0; i < incompleteseeeds.size(); ++ i )
1880  {
1881  SeeedPtr seeedPtr = incompleteseeeds[i];
1882 
1883  for( int d = 0; d < nFinishingDetectors; ++ d )
1884  {
1885  DEC_DETECTOR* detector = detectorToFinishingScipDetector[d];
1886  SCIP_RESULT result = SCIP_DIDNOTFIND;
1887  SEEED_PROPAGATION_DATA* seeedPropData;
1888  seeedPropData = new SEEED_PROPAGATION_DATA();
1889  seeedPropData->seeedpool = this;
1890  seeedPropData->nNewSeeeds = 0;
1891 
1892 #pragma omp critical ( seeedcount )
1893  seeedPropData->seeedToPropagate = new gcg::Seeed( seeedPtr );
1894 
1895  if( verboseLevel > 2 )
1896  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "check if finisher of detector %s is enabled\n", DECdetectorGetName( detectorToScipDetector[d] ) );
1897 
1899  if( ! detector->enabledFinishing )
1900  continue;
1901 
1902  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "call finisher for detector %s\n", DECdetectorGetName( detectorToFinishingScipDetector[d] ) );
1903 
1904  SCIP_CALL_ABORT(
1905  detectorToFinishingScipDetector[d]->finishSeeed( scip, detectorToFinishingScipDetector[d], seeedPropData,
1906  & result ) );
1907 
1908  for( int finished = 0; finished < seeedPropData->nNewSeeeds; ++ finished )
1909  {
1910  SeeedPtr seeed = seeedPropData->newSeeeds[finished];
1911 #pragma omp critical ( seeedcount )
1912  seeed->setID( getNewIdForSeeed() );
1913 
1914  seeed->calcHashvalue();
1915  seeed->addDecChangesFromAncestor( seeedPtr );
1916  seeed->setFinishedByFinisher( true );
1917 
1918  if( seeedIsNoDuplicateOfSeeeds( seeed, finishedSeeeds, false ) )
1919  {
1920  if( verboseLevel > 2 )
1921  {
1922  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "seeed %d is finished from next round seeeds! \n", seeed->getID() );
1923  seeed->showVisualisation();
1924  }
1925 #pragma omp critical ( seeedptrstore )
1926  {
1927  assert( seeed->getID() >= 0 );
1928  finisheds.push_back( seeed );
1929  }
1930  }
1931 
1932  SCIPfreeMemoryArrayNull( scip, & seeedPropData->newSeeeds );
1933  seeedPropData->newSeeeds = NULL;
1934  seeedPropData->nNewSeeeds = 0;
1935  }
1936 
1937  delete seeedPropData->seeedToPropagate;
1938  delete seeedPropData;
1939  }
1940  } // end for finishing curr seeeds
1941  return finisheds;
1942 }
1943 
1944 
1947 {
1948  std::vector<int> successDetectors;
1949 
1950  successDetectors = std::vector<int>( nDetectors, 0 );
1951 
1952  finishedSeeeds = findSeeeds();
1953 
1954  /* sort the seeeds according to maximum white measure */
1956 
1957 }
1958 
1959 
1960 /*SCIP_RETCODE DECdecompCheckConsistency(DEC_DECOMP* decomp)
1961 {
1962  int c;
1963  int b;
1964  int v;
1965 
1966  for( v = 0; v < SCIPgetNVars(scip); ++v )
1967  {
1968  assert(SCIPhashmapExists(DECdecompGetVartoblock(decomp), SCIPgetVars(scip)[v]));
1969  }
1970 }*/
1971 
1974  int seeedid
1975  )
1976  {
1977  for( size_t fs = 0; fs < finishedSeeeds.size(); ++fs )
1978  {
1979  if ( finishedSeeeds[fs]->getID() == seeedid )
1980  return finishedSeeeds[fs];
1981  }
1982 
1983  return NULL;
1984  }
1985 
1986 
1987 
1990  SeeedPtr seeed
1991  )
1992 {
1993  ancestorseeeds.push_back( seeed );
1994 }
1995 
1996 
1999  SeeedPtr seeed
2000  )
2001 {
2002  if( seeedIsNoDuplicateOfSeeeds(seeed, currSeeeds, false) )
2003  currSeeeds.push_back( seeed );
2004 }
2005 
2006 
2009  SeeedPtr seeed,
2010  SCIP_Bool* success
2011  )
2012 {
2013  if( seeedIsNoDuplicateOfSeeeds(seeed, finishedSeeeds, false) )
2014  {
2015  finishedSeeeds.push_back( seeed );
2016  *success = TRUE;
2017  }
2018  else
2019  {
2020  *success = FALSE;
2021  }
2022  return;
2023 }
2024 
2025 
2028  SeeedPtr seeed
2029  )
2030 {
2031  finishedSeeeds.push_back( seeed );
2032 
2033  return;
2034 }
2035 
2036 
2039  SeeedPtr seeed,
2040  SCIP_Bool* success
2041  )
2042 {
2043  *success = FALSE;
2044  if( seeedIsNoDuplicateOfSeeeds(seeed, incompleteSeeeds, false) )
2045  {
2046  incompleteSeeeds.push_back( seeed );
2047  *success = TRUE;
2048  }
2049  return;
2050 }
2051 
2053  SeeedPtr seeed
2054  )
2055 {
2056  return !(seeedIsNoDuplicateOfSeeeds(seeed, incompleteSeeeds, false));
2057 }
2058 
2060  SeeedPtr seeed
2061  )
2062 {
2063  return !(seeedIsNoDuplicateOfSeeeds(seeed, finishedSeeeds, false));
2064 }
2065 
2067 
2068  for( int v = 0; v < getNVars(); ++v )
2069  {
2070  if( SCIPvarGetType( getVarForIndex(v)) == SCIP_VARTYPE_CONTINUOUS || SCIPvarGetType( getVarForIndex(v)) == SCIP_VARTYPE_IMPLINT )
2071  return TRUE;
2072  }
2073  return FALSE;
2074 }
2075 
2077 /*
2078  * strong decompositon score is defined as follows:
2079  */
2081  SeeedPtr seeed,
2082  SCIP_Real* score
2083  )
2084 {
2085  SCIP_Bool hittimelimit;
2086  SCIP_Bool errorpricing;
2087  //std::vector<SCIP_Real> randomdualvals;
2088 
2090  SCIP_Real timelimit;
2091  SCIP_Real timelimitfast;
2092 
2099  SCIP_Real scorecoef_fastbenefical;
2100  SCIP_Real scorecoef_mediumbenefical;
2103  SCIP_Real scorecoef_fastnobenefical;
2104  SCIP_Real scorecoef_mediumnobenefical;
2105 
2106  int npricingconss;
2107 
2108  SCIP_Real infinity;
2109  SCIP_Real epsilon;
2110  SCIP_Real sumepsilon;
2111  SCIP_Real feastol;
2112  SCIP_Real lpfeastol;
2113  SCIP_Real dualfeastol;
2114  SCIP_Bool enableppcuts;
2115 
2116  SCIP_Bool benefical;
2117  SCIP_Bool fast;
2118 
2119  SCIP_Bool writesubproblem;
2120 
2121  int clocktype;
2122 
2123  SCIP_Real dualvalmethodcoef;
2124 
2125  if( !transformed )
2126  {
2127  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, " \n Attention! Strong decomposition score is not implemented for decomps belonging to the original problem \n\n");
2128  return SCIP_OKAY;
2129  }
2130 
2131  *score = 0.;
2132  npricingconss = 0;
2133 
2134  writesubproblem = FALSE;
2135 
2136  // randomdualvals = std::vector<SCIP_Real>(getNConss(),0. );
2137 
2138  SCIPgetRealParam(scip, "detection/strong_detection/coeffactororigvsrandom", &dualvalmethodcoef);
2139 
2140  timelimit = 30.;
2141  timelimitfast = 0.1 * timelimit;
2142 
2146  scorecoef_fastbenefical = 1.;
2147  scorecoef_mediumbenefical = 0.75;
2148 
2150 /* scorecoef_fastlittlebenefical = 0.75; */
2151 /* scorecoef_mediumlittlebenefical = 0.5; */
2152 
2153  scorecoef_fastnobenefical = 0.3;
2154  scorecoef_mediumnobenefical = 0.1;
2155 
2156  /* get numerical tolerances of the original SCIP instance in order to use the same numerical tolerances in master and pricing problems */
2157  SCIP_CALL( SCIPgetRealParam(scip, "numerics/infinity", &infinity) );
2158  SCIP_CALL( SCIPgetRealParam(scip, "numerics/epsilon", &epsilon) );
2159  SCIP_CALL( SCIPgetRealParam(scip, "numerics/sumepsilon", &sumepsilon) );
2160  SCIP_CALL( SCIPgetRealParam(scip, "numerics/feastol", &feastol) );
2161  SCIP_CALL( SCIPgetRealParam(scip, "numerics/lpfeastol", &lpfeastol) );
2162  SCIP_CALL( SCIPgetRealParam(scip, "numerics/dualfeastol", &dualfeastol) );
2163 
2164  /* get clocktype of the original SCIP instance in order to use the same clocktype in master and pricing problems */
2165  SCIP_CALL( SCIPgetIntParam(scip, "timing/clocktype", &clocktype) );
2166 
2167 
2168  enableppcuts = FALSE;
2169  SCIP_CALL( SCIPgetBoolParam(scip, "sepa/basis/enableppcuts", &enableppcuts) );
2170 
2171 
2172 
2173  for ( int block = 0; block < seeed->getNBlocks(); ++block )
2174  {
2175  npricingconss += seeed->getNConssForBlock(block);
2176  }
2177 
2178  /* for every pricing problem calculate a corresponding score coeff and break if a pricing problem cannot be solved in the timelimit */
2179  for ( int block = 0; block < seeed->getNBlocks(); ++block )
2180  {
2181  SCIP* subscip;
2182  char name[SCIP_MAXSTRLEN];
2183  SCIP_HASHMAP* hashpricingvartoindex;
2184  SCIP_HASHMAP* hashorig2pricingvar;
2185  SCIP_Real score_coef;
2186  SCIP_Real weight_subproblem;
2187  std::stringstream subname;
2188 
2189  hittimelimit = FALSE;
2190  errorpricing = FALSE;
2191 
2192 
2193  subname << "temp_pp_" << block << ".lp";
2194  std::vector<SCIP_VAR*> indextopricingvar;
2195 
2196  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "started calculate strong decomposition subproblem for block %d \n", block );
2197 
2198  indextopricingvar = std::vector<SCIP_VAR*>(getNVars(), NULL);
2199 
2200  SCIP_CALL( SCIPhashmapCreate(&hashpricingvartoindex, SCIPblkmem(scip), getNVars()) ); /*lint !e613*/
2201  SCIP_CALL( SCIPhashmapCreate(&hashorig2pricingvar, SCIPblkmem(scip), getNVars()) ); /*lint !e613*/
2202 
2203  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "testpricing_block_%d", block);
2204 
2205  benefical = FALSE;
2206  fast = FALSE;
2207  score_coef = 0.0;
2208  weight_subproblem = (SCIP_Real) seeed->getNConssForBlock(block) / npricingconss;
2209 
2211  SCIP_CALL( SCIPcreate(&subscip) );
2212  SCIP_CALL( SCIPincludeDefaultPlugins(subscip) );
2213  SCIP_CALL( setTestpricingProblemParameters(subscip, clocktype, infinity, epsilon, sumepsilon, feastol, lpfeastol, dualfeastol, enableppcuts, timelimit) );
2214  SCIP_CALL( SCIPsetIntParam(subscip, "presolving/maxrounds", 0) );
2215  SCIP_CALL( SCIPsetIntParam(subscip, "lp/solvefreq", 1) );
2216  SCIP_CALL( SCIPcreateProb(subscip, name, NULL, NULL, NULL, NULL, NULL, NULL, NULL) );
2217 
2218  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "started calculate strong decomposition, timelimit: %f timelimitfast: %f \n", timelimit, timelimitfast );
2219 
2220 
2222  for( int var = 0; var < seeed->getNVarsForBlock(block); ++var )
2223  {
2224  int varid;
2225  SCIP_VAR* origprobvar;
2226  SCIP_VAR* pricingprobvar;
2227  SCIP_Real obj;
2228 
2229 
2230  varid = seeed->getVarsForBlock(block)[var];
2231 
2232  if ( transformed )
2233  origprobvar = getVarForIndex(varid);
2234  else
2235  origprobvar = SCIPvarGetProbvar(getVarForIndex(varid));
2236 
2238  obj = SCIPvarGetObj(origprobvar);
2239  for( int c = 0; c < getNConssForVar(varid); ++c )
2240  {
2241  int consid;
2242  SCIP_Real dualval;
2243 
2244  dualval = 0.;
2245 
2246  consid = getConssForVar(varid)[c];
2247  if ( seeed->isConsMastercons(consid) )
2248  {
2249  if( SCIPisEQ( scip, dualvalmethodcoef, 0.0) )
2250  dualval = getDualvalRandom(consid);
2251  else if( SCIPisEQ( scip, dualvalmethodcoef, 1.0) )
2252  dualval = getDualvalOptimalLP(consid);
2253  else
2254  dualval = dualvalmethodcoef * getDualvalOptimalLP(consid) + (1.- dualvalmethodcoef) * getDualvalRandom(consid);
2255  obj -= dualval * getVal(consid, varid);
2256  }
2257  }
2258 
2260  // obj = SCIPfloor(scip, obj * 100 + 0.5 )/100.;
2261 
2262  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "pr%d_%s", block, SCIPvarGetName(origprobvar));
2263  SCIP_CALL( SCIPcreateVar(subscip, &pricingprobvar, name, SCIPvarGetLbGlobal(origprobvar),
2264  SCIPvarGetUbGlobal(origprobvar), obj, SCIPvarGetType(origprobvar),
2265  TRUE, FALSE, NULL, NULL, NULL, NULL, NULL) );
2266  SCIPhashmapSetImage(hashorig2pricingvar, origprobvar, pricingprobvar);
2267  SCIPhashmapSetImage(hashpricingvartoindex, pricingprobvar, (void*) (size_t)varid);
2268  indextopricingvar[varid] = pricingprobvar;
2269  SCIP_CALL( SCIPaddVar(subscip, pricingprobvar) );
2270  }
2271 
2273  SCIP_CALL( createTestPricingprobConss(scip, subscip, this, seeed, block, hashorig2pricingvar) );
2274 
2275  SCIP_CALL(SCIPtransformProb(subscip) );
2278  if( writesubproblem )
2279  SCIPwriteTransProblem(subscip, subname.str().c_str(), "lp", FALSE);
2280 
2282  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "started solving subproblem for block %d \n", block );
2283  SCIP_CALL( SCIPsolve(subscip) );
2284 
2285  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "finished solving subproblem in %f seconds \n", SCIPgetSolvingTime(subscip) );
2286 
2287  SCIPsolve(subscip);
2288 
2289  if( SCIPgetStatus(subscip) != SCIP_STATUS_OPTIMAL )
2290  {
2291  if( SCIPgetStatus(subscip) == SCIP_STATUS_TIMELIMIT )
2292  hittimelimit = TRUE;
2293  else
2294  errorpricing = TRUE;
2295  }
2296 
2297  if ( errorpricing || hittimelimit)
2298  {
2299  if( hittimelimit )
2300  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "Hit timelimit in pricing problem %d \n.", block);
2301  else
2302  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "Error in pricing problem %d \n.", block);
2303 
2304  *score = 0.;
2305  SCIPhashmapFree(&hashpricingvartoindex);
2306  SCIPfree(&subscip);
2307 
2310  return SCIP_OKAY;
2311  }
2312 
2313 
2315  if ( !SCIPisEQ( scip, SCIPgetFirstLPLowerboundRoot(subscip), SCIPgetDualbound(subscip) ) )
2316  benefical = TRUE;
2317 
2318  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "first dual bound: %f ; dual bound end: %f \n",SCIPgetFirstLPLowerboundRoot(subscip), SCIPgetDualbound(subscip) );
2319 
2320  if( SCIPisFeasLE( scip, SCIPgetSolvingTime(subscip), timelimitfast ) )
2321  fast = TRUE;
2322 
2323  if ( fast && benefical )
2324  score_coef = scorecoef_fastbenefical;
2325 
2326  if ( !fast && benefical )
2327  score_coef = scorecoef_mediumbenefical;
2328 
2329  if ( fast && !benefical )
2330  score_coef = scorecoef_fastnobenefical;
2331 
2332  if ( !fast && !benefical )
2333  score_coef = scorecoef_mediumnobenefical;
2334 
2335  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "scorecoef for subproblem %d is %f with weighting factor %f\n", block, score_coef, weight_subproblem );
2336 
2337  *score += score_coef * weight_subproblem;
2338 
2339  // SCIPprintStatistics(subscip, NULL);
2340 
2341 
2343  for( int var = 0; var < seeed->getNVarsForBlock(block); ++var )
2344  {
2345  int varid = seeed->getVarsForBlock(block)[var];
2346  SCIPreleaseVar(subscip, &indextopricingvar[varid]);
2347  }
2348 
2349  SCIPhashmapFree(&hashpricingvartoindex);
2350 
2351  SCIPfree(&subscip);
2352  }// end for blocks
2353 
2354 
2358  return SCIP_OKAY;
2359 }
2360 
2361 
2364 {
2365  ancestorseeeds.clear();
2366 }
2367 
2370 {
2371  currSeeeds.clear();
2372 }
2373 
2376 {
2377  finishedSeeeds.clear();
2378 }
2379 
2382 {
2383  incompleteSeeeds.clear();
2384 }
2385 
2388  int seeedindex
2389  )
2390 {
2391  assert( 0 <= seeedindex && seeedindex < (int) ancestorseeeds.size() );
2392 
2393  return ancestorseeeds[seeedindex];
2394 }
2395 
2398  int seeedindex
2399  )
2400 {
2401  assert( 0 <= seeedindex && seeedindex < (int) currSeeeds.size() );
2402 
2403  return currSeeeds[seeedindex];
2404 }
2405 
2408  int seeedindex
2409  )
2410 {
2411  assert( 0 <= seeedindex && seeedindex < (int) finishedSeeeds.size() );
2412 
2413  return finishedSeeeds[seeedindex];
2414 }
2415 
2418  int seeedindex
2419  )
2420 {
2421  assert( 0 <= seeedindex && seeedindex < (int) incompleteSeeeds.size() );
2422 
2423  return incompleteSeeeds[seeedindex];
2424 }
2425 
2428 {
2429  return ancestorseeeds.size();
2430 }
2431 
2434 {
2435  return currSeeeds.size();
2436 }
2437 
2440 {
2441  return finishedSeeeds.size();
2442 }
2443 
2446 {
2447  return incompleteSeeeds.size();
2448 }
2449 
2450 
2453 ){
2454  int nconss = 0;
2455 
2456  for ( int c = 0; c < getNConss(); ++c )
2457  {
2458  SCIP_CONS* cons = consToScipCons[c];
2459  nconss += GCGconsIsRanged(scip, cons) ? 2 : 1;
2460  }
2461 
2462  return nconss;
2463 }
2464 
2467 {
2468  long ntotalnonzeros = nnonzeros;
2469 
2470  for (int c = 0; c < getNConss(); ++c )
2471  {
2472  SCIP_CONS* cons = getScipCons(c);
2473  if( GCGconsIsRanged(scip, cons) )
2474  {
2475  ntotalnonzeros += GCGconsGetNVars(scip, cons);
2476  }
2477  }
2478 
2479  return ntotalnonzeros;
2480 }
2481 
2482 
2483 
2487  SeeedPtr seeed
2488  )
2489 {
2490  assert( seeed != NULL );
2491 
2492  return !seeedIsNoDuplicate( seeed, currSeeeds, finishedSeeeds, true );
2493 }
2494 
2495 
2498  {
2499  return benders;
2500  }
2501 
2502 
2503 
2504 
2507  Seeedpool* origpool,
2508  std::vector<Seeed*> origseeeds,
2509  std::vector<Seeed*>& newseeeds,
2510  std::vector<ConsClassifier*> otherconsclassifiers,
2511  std::vector<ConsClassifier*>& newconsclassifiers,
2512  std::vector<VarClassifier*> othervarclassifiers,
2513  std::vector<VarClassifier*>& newvarclassifiers
2514  )
2515 {
2516  assert( newseeeds.empty() );
2517  assert( newconsclassifiers.empty() );
2518  assert( newvarclassifiers.empty() );
2519 
2520  SCIP_CLOCK* translationclock;
2521 
2522  std::vector<int> rowothertothis;
2523  std::vector<int> rowthistoother;
2524  std::vector<int> colothertothis;
2525  std::vector<int> colthistoother;
2526  std::vector<int> missingrowinthis;
2527 
2528  SCIP_Bool presolvingdisabled;
2529  int presolvingrounds;
2530 
2531  presolvingdisabled = FALSE;
2532 
2533  SCIPcreateClock(scip, &translationclock);
2534  SCIPstartClock(scip, translationclock);
2535 
2536  SCIPgetIntParam(scip, "presolving/maxrounds", &presolvingrounds);
2537 
2538  if ( presolvingrounds == 0)
2539  presolvingdisabled = TRUE;
2540 
2541  SCIPverbMessage( this->scip, SCIP_VERBLEVEL_HIGH, NULL, "started translate seeed method: presolving is %s \n", (presolvingdisabled ? "disabled, try short method." : "enabled, has to do long version. " ) );
2542 
2543  if( presolvingdisabled )
2544  {
2545  missingrowinthis = std::vector<int>(0);
2546  rowothertothis = std::vector<int>(0);
2547  rowthistoother = std::vector<int>(0);
2548  colothertothis = std::vector<int>(0);
2549  colthistoother = std::vector<int>(0);
2550  for( int i = 0; i < nConss ; ++i )
2551  {
2552  rowothertothis.push_back(i);
2553  rowthistoother.push_back(i);
2554  }
2555  for( int j = 0; j < nVars ; ++j )
2556  {
2557  colthistoother.push_back(j);
2558  colothertothis.push_back(j);
2559  }
2560  } else
2561  calcTranslationMapping( origpool, rowothertothis, rowthistoother, colothertothis, colthistoother, missingrowinthis );
2562 
2563  SCIPverbMessage( this->scip, SCIP_VERBLEVEL_HIGH, NULL,
2564  " calculated translation; number of missing constraints: %d; number of other seeeds: %d \n", missingrowinthis.size(),
2565  origseeeds.size() );
2566 
2567  newseeeds = getTranslatedSeeeds( origseeeds, rowothertothis, rowthistoother, colothertothis, colthistoother );
2568  newconsclassifiers = getTranslatedConsClassifiers( otherconsclassifiers, rowothertothis, rowthistoother );
2569  newvarclassifiers = getTranslatedVarClassifiers( othervarclassifiers, colothertothis, colthistoother );\
2570 
2571  SCIPstopClock(scip, translationclock);
2572 
2573  translatingtime += SCIPgetClockTime(scip, translationclock);
2574 
2575  SCIPfreeClock(scip, &translationclock);
2576 
2577  return;
2578 
2579 
2580 }
2581 
2584  Seeedpool* origpool,
2585  std::vector<Seeed*> origseeeds,
2586  std::vector<Seeed*>& newseeeds
2587  )
2588 {
2589  assert( newseeeds.empty() );
2590 
2591  int roundspresolving;
2592  SCIP_Bool presolvingdisabled;
2593 
2594  std::vector<int> rowothertothis( 0 );
2595  std::vector<int> rowthistoother( 0 );
2596  std::vector<int> colothertothis( 0 );
2597  std::vector<int> colthistoother( 0 );
2598  std::vector<int> missingrowinthis( 0 );
2599 
2600 // SCIPverbMessage( this->scip, SCIP_VERBLEVEL_HIGH, NULL, "started translate seeed method: presolving is %s \n", (presolvingdisabled ? "disabled, try short method." : "enabled, has to do long version. " ) );
2601 //
2602 
2603  SCIPgetIntParam(scip, "presolving/maxrounds", &roundspresolving);
2604 
2605  presolvingdisabled = (roundspresolving == 0);
2606 
2607  presolvingdisabled = presolvingdisabled && (nVars == origpool->getNVars() );
2608  if( presolvingdisabled && FALSE )
2609  {
2610  missingrowinthis = std::vector<int>(0);
2611  rowothertothis = std::vector<int>(0);
2612  rowthistoother = std::vector<int>(0);
2613  colothertothis = std::vector<int>(0);
2614  colthistoother = std::vector<int>(0);
2615  for( int i = 0; i < nConss ; ++i )
2616  {
2617  rowothertothis.push_back(i);
2618  rowthistoother.push_back(i);
2619  }
2620  for( int j = 0; j < nVars ; ++j )
2621  {
2622  colthistoother.push_back(j);
2623  colothertothis.push_back(j);
2624  }
2625  } else
2626  calcTranslationMapping( origpool, rowothertothis, rowthistoother, colothertothis, colthistoother, missingrowinthis );
2627 
2628  SCIPverbMessage( this->scip, SCIP_VERBLEVEL_HIGH, NULL,
2629  " calculated translation; number of missing constraints: %d; number of other seeeds: %d \n", missingrowinthis.size(),
2630  origseeeds.size() );
2631 
2632  newseeeds = getTranslatedSeeeds( origseeeds, rowothertothis, rowthistoother, colothertothis, colthistoother );
2633 
2634 }
2635 
2637 void Seeedpool::calcTranslationMapping(
2638  Seeedpool* origpool,
2639  std::vector<int>& rowothertothis,
2640  std::vector<int>& rowthistoother,
2641  std::vector<int>& colothertothis,
2642  std::vector<int>& colthistoother,
2643  std::vector<int>& missingrowinthis
2644  )
2645 {
2646  int nrowsother = origpool->nConss;
2647  int nrowsthis = nConss;
2648  int ncolsother = origpool->nVars;
2649  int ncolsthis = nVars;
2650 
2651  std::vector<SCIP_CONS*> origscipconss = origpool->consToScipCons;
2652  std::vector<SCIP_CONS*> thisscipconss = consToScipCons;
2653  std::vector<SCIP_VAR*> origscipvars = origpool->varToScipVar;
2654  std::vector<SCIP_VAR*> thisscipvars = varToScipVar;
2655 
2656  assert(nrowsother == (int) origscipconss.size() );
2657  assert(nrowsthis == (int) thisscipconss.size() );
2658 
2659  assert(ncolsother == (int) origscipvars.size() );
2660  assert(ncolsthis == (int) thisscipvars.size() );
2661 
2662 
2663 // std::vector<SCIP_CONS*>::const_iterator origiter = origscipconss.begin();
2664 // std::vector<SCIP_CONS*>::const_iterator origiterend = origscipconss.end();
2665 //
2666 // std::vector<SCIP_CONS*>::const_iterator thisiter = thisscipconss.begin();
2667 // std::vector<SCIP_CONS*>::const_iterator thisiterend = thisscipconss.end();
2668 //
2669 // std::vector<SCIP_VAR*>::const_iterator origitervars = origscipvars.begin();
2670 // std::vector<SCIP_VAR*>::const_iterator origiterendvars = origscipvars.end();
2671 //
2672 // std::vector<SCIP_VAR*>::const_iterator thisitervars = thisscipvars.begin();
2673 // std::vector<SCIP_VAR*>::const_iterator thisiterendvars = thisscipvars.end();
2674 
2675 
2676  rowothertothis.assign( nrowsother, - 1 );
2677  rowthistoother.assign( nrowsthis, - 1 );
2678  colothertothis.assign( ncolsother, - 1 );
2679  colthistoother.assign( ncolsthis, - 1 );
2680 
2681  missingrowinthis.clear();
2682 
2683  /* identify new and deleted rows and cols; and identify bijection between maintained variables */
2684  for( int i = 0; i < nrowsother ; ++i )
2685  {
2686  SCIP_CONS* otherrow = origscipconss[i];
2687  assert( otherrow != NULL );
2688  SCIP_Bool foundmaintained = false;
2689  // thisiter = thisscipconss.begin();
2690  for( int j2 = i; j2 < nrowsthis + i; ++j2 )
2691  {
2692  int j = j2 % nrowsthis;
2693  SCIP_CONS* thisrow = thisscipconss[j];
2694  assert( SCIPconsIsTransformed( thisrow ) );
2695 
2696  if( SCIPconsGetTransformed(origscipconss[i]) == thisrow )
2697  {
2698  rowothertothis[i] = j;
2699  rowthistoother[j] = i;
2700  foundmaintained = true;
2701  break;
2702  }
2703 
2704  char buffer[SCIP_MAXSTRLEN];
2705  assert( this->scip != NULL );
2706  strcpy( buffer, SCIPconsGetName( thisrow ) + 2 );
2707  assert( this->scip != NULL );
2708  if( strcmp( SCIPconsGetName( otherrow ), SCIPconsGetName( thisrow ) ) == 0 )
2709  {
2710  rowothertothis[i] = j;
2711  rowthistoother[j] = i;
2712  foundmaintained = true;
2713  break;
2714  }
2715  }
2716  if( ! foundmaintained )
2717  {
2718  missingrowinthis.push_back( i );
2719  }
2720  }
2721 
2722  for( int i = 0; i < ncolsother; ++i )
2723  {
2724  SCIP_VAR* othervar;
2725  SCIP_VAR* probvar;
2726  SCIP_CALL_ABORT( SCIPgetTransformedVar(scip, origscipvars[i], &othervar ) );
2727  if (othervar == NULL)
2728  continue;
2729 
2730  probvar = SCIPvarGetProbvar(othervar);
2731  if ( probvar == NULL )
2732  continue;
2733 
2734  for( int j2 = i; j2 < ncolsthis + i; ++j2 )
2735  {
2736  int j = j2 % ncolsthis;
2737  if( probvar == thisscipvars[j] )
2738  {
2739  colothertothis[i] = j;
2740  colthistoother[j] = i;
2741  break;
2742  }
2743  }
2744  }
2745 
2746  if ( FALSE )
2747  {
2748  for ( int i = 0; i < (int) rowothertothis.size(); ++i )
2749  std::cout << (rowothertothis[i] == i) << " " ;
2750 
2751  std::cout << std::endl;
2752 
2753  for ( int i = 0; i < (int) colothertothis.size(); ++i )
2754  std::cout << ( colothertothis[i] == i ) << " " ;
2755  std::cout << std::endl;
2756  }
2757 }
2758 
2760 std::vector<Seeed*> Seeedpool::getTranslatedSeeeds(
2761  std::vector<Seeed*>& origseeeds,
2762  std::vector<int>& rowothertothis,
2763  std::vector<int>& rowthistoother,
2764  std::vector<int>& colothertothis,
2765  std::vector<int>& colthistoother
2766  )
2767 {
2768  std::vector<Seeed*> newseeeds( 0 );
2769 
2770  for( size_t s = 0; s < origseeeds.size(); ++ s )
2771  {
2772  SeeedPtr otherseeed;
2773  SeeedPtr newseeed;
2774 
2775  otherseeed = origseeeds[s];
2776 
2777  std::vector<int> probvarismatchedinfo = std::vector<int>(getNVars(), -1);
2778 
2779  SCIPverbMessage( this->scip, SCIP_VERBLEVEL_FULL, NULL, " transform seeed %d \n", otherseeed->getID() );
2780 
2781  newseeed = new Seeed( scip, this->getNewIdForSeeed(), this );
2782 
2784  newseeed->setNBlocks( otherseeed->getNBlocks() );
2785 
2786  newseeed->setUsergiven( otherseeed->getUsergiven() );
2787 
2789  for( int b = 0; b < otherseeed->getNBlocks(); ++ b )
2790  {
2791  for( int i = 0; i < otherseeed->getNConssForBlock( b ); i ++ )
2792  {
2793  int thiscons = rowothertothis[otherseeed->getConssForBlock( b )[i]];
2794  if( thiscons != - 1 )
2795  {
2796  newseeed->bookAsBlockCons( thiscons, b );
2797  }
2798  }
2799  }
2800 
2801  for( int i = 0; i < otherseeed->getNMasterconss(); i ++ )
2802  {
2803  int thiscons = rowothertothis[otherseeed->getMasterconss()[i]];
2804  if( thiscons != - 1 )
2805  {
2806  newseeed->bookAsMasterCons( thiscons );
2807  }
2808  }
2809 
2813  for( int j = 0; j < otherseeed->getNLinkingvars(); j ++ )
2814  {
2815  int thisvar = colothertothis[otherseeed->getLinkingvars()[j]];
2816  if( thisvar != - 1 && probvarismatchedinfo[thisvar] == -1 )
2817  {
2818  probvarismatchedinfo[thisvar] = 1;
2819  newseeed->bookAsLinkingVar(thisvar);
2820  }
2821  else
2822  if( thisvar != - 1 )
2823  {
2824  assert( probvarismatchedinfo[thisvar] == 1 );
2825  }
2826  }
2827 
2828  for( int j = 0; j < otherseeed->getNMastervars(); j ++ )
2829  {
2830  int thisvar = colothertothis[otherseeed->getMastervars()[j]];
2831  if( thisvar != - 1 && probvarismatchedinfo[thisvar] == -1 )
2832  {
2833  probvarismatchedinfo[thisvar] = 2;
2834  newseeed->bookAsMasterVar( thisvar );
2835  }
2836  else
2837  if( thisvar != - 1 )
2838  {
2839  assert( probvarismatchedinfo[thisvar] == 2 );
2840  }
2841  }
2842 
2843  newseeed->flushBooked();
2844 
2845  newseeed->setDetectorchain( otherseeed->getDetectorchainVector() );
2846  newseeed->setAncestorList( otherseeed->getAncestorList() );
2847 
2848  newseeed->addAncestorID( otherseeed->getID() );
2849 
2850  newseeed->copyClassifierStatistics( otherseeed );
2851 
2852  for( int i = 0; i < otherseeed->getNDetectors(); ++i )
2853  {
2854  newseeed->addClockTime( otherseeed->getDetectorClockTime( i ) );
2855  newseeed->addPctConssFromFree( otherseeed->getPctConssFromFree( i ) );
2856  newseeed->addPctConssToBlock( otherseeed->getPctConssToBlock( i ) );
2857  newseeed->addPctConssToBorder( otherseeed->getPctConssToBorder( i ) );
2858  newseeed->addPctVarsFromFree( otherseeed->getPctVarsFromFree( i ) );
2859  newseeed->addPctVarsToBlock( otherseeed->getPctVarsToBlock( i ) );
2860  newseeed->addPctVarsToBorder( otherseeed->getPctVarsToBorder( i ) );
2861  newseeed->addNNewBlocks( otherseeed->getNNewBlocks( i ) );
2862  }
2863 
2864  newseeed->setDetectorChainString( otherseeed->getDetectorChainString() );
2865  newseeed->setStemsFromUnpresolved( this->transformed );
2866  newseeed->setFinishedByFinisherUnpresolved( otherseeed->getFinishedByFinisher() );
2867 
2868  if( otherseeed->getFinishedByFinisher() )
2869  newseeed->setFinishedUnpresolvedBy( otherseeed->getDetectorchain()[otherseeed->getNDetectors() - 1] );
2870 
2871  newseeed->setFinishedByFinisher( otherseeed->getFinishedByFinisher() );
2872  newseeed->sort();
2873  newseeed->considerImplicits( );
2874  newseeed->deleteEmptyBlocks(benders);
2875  newseeed->getScore( SCIPconshdlrDecompGetCurrScoretype( scip ) ) ;
2876 
2877  if( newseeed->checkConsistency( ) )
2878  newseeeds.push_back( newseeed );
2879  else
2880  {
2881  delete newseeed;
2882  newseeed = NULL;
2883  }
2884 
2885  }
2886 
2887  return newseeeds;
2888 }
2889 
2891 std::vector<ConsClassifier*> Seeedpool::getTranslatedConsClassifiers(
2892  std::vector<ConsClassifier*>& otherclassifiers,
2893  std::vector<int>& rowothertothis,
2894  std::vector<int>& rowthistoother
2895  )
2896 {
2897  std::vector<ConsClassifier*> newclassifiers( 0 );
2898 
2899  for( size_t i = 0; i < otherclassifiers.size(); ++ i )
2900  {
2901  ConsClassifier* oldclassifier = otherclassifiers[i];
2902  ConsClassifier* newclassifier;
2903  std::stringstream newname;
2904 
2905  newname << oldclassifier->getName() << "-origp";
2906  newclassifier = new ConsClassifier( scip, newname.str().c_str(), oldclassifier->getNClasses(),
2907  (int) rowthistoother.size() );
2908  int bufferclassindex = - 1;
2909 
2911  for( int j = 0; j < oldclassifier->getNClasses(); ++ j )
2912  {
2913  newclassifier->setClassName( j, oldclassifier->getClassName( j ) );
2914  newclassifier->setClassDescription( j, oldclassifier->getClassDescription( j ) );
2915  newclassifier->setClassDecompInfo( j, oldclassifier->getClassDecompInfo( j ) );
2916  }
2917 
2919  for( int c = 0; c < (int) rowthistoother.size(); ++ c )
2920  {
2921  if( rowthistoother[c] != - 1 )
2922  {
2923  newclassifier->assignConsToClass( c, oldclassifier->getClassOfCons( rowthistoother[c] ) );
2924  }
2925  else
2926  {
2927  if( bufferclassindex == - 1 )
2928  {
2929  bufferclassindex = newclassifier->addClass( "buffer",
2930  "This class contains constraints which are new in the presolved problem.", BOTH );
2931  }
2932  newclassifier->assignConsToClass( c, bufferclassindex );
2933  }
2934  }
2935 
2937  newclassifier->removeEmptyClasses();
2938 
2939  newclassifiers.push_back( newclassifier );
2940  }
2941 
2942  return newclassifiers;
2943 }
2944 
2946 std::vector<VarClassifier*> Seeedpool::getTranslatedVarClassifiers(
2947  std::vector<VarClassifier*>& otherclassifiers,
2948  std::vector<int>& colothertothis,
2949  std::vector<int>& colthistoother
2950  )
2951 {
2952  std::vector<VarClassifier*> newclassifiers( 0 );
2953 
2954  for( size_t i = 0; i < otherclassifiers.size(); ++ i )
2955  {
2956  VarClassifier* oldclassifier = otherclassifiers[i];
2957  VarClassifier* newclassifier;
2958  std::stringstream newname;
2959 
2960  newname << oldclassifier->getName() << "-origp";
2961  newclassifier = new VarClassifier( scip, newname.str().c_str(), oldclassifier->getNClasses(),
2962  (int) colthistoother.size() );
2963  int bufferclassindex = - 1;
2964 
2966  for( int j = 0; j < oldclassifier->getNClasses(); ++ j )
2967  {
2968  newclassifier->setClassName( j, oldclassifier->getClassName( j ) );
2969  newclassifier->setClassDescription( j, oldclassifier->getClassDescription( j ) );
2970  newclassifier->setClassDecompInfo( j, oldclassifier->getClassDecompInfo( j ) );
2971  }
2972 
2974  for( int c = 0; c < (int) colthistoother.size(); ++ c )
2975  {
2976  if( colthistoother[c] != - 1 )
2977  {
2978  newclassifier->assignVarToClass( c, oldclassifier->getClassOfVar( colthistoother[c] ) );
2979  }
2980  else
2981  {
2982  if( bufferclassindex == - 1 )
2983  {
2984  bufferclassindex = newclassifier->addClass( "buffer",
2985  "This class contains variables which are new in the presolved problem.", ALL );
2986  }
2987  newclassifier->assignVarToClass( c, bufferclassindex );
2988  }
2989  }
2990 
2992  newclassifier->removeEmptyClasses();
2993 
2994  newclassifiers.push_back( newclassifier );
2995  }
2996 
2997  return newclassifiers;
2998 }
2999 
3002  std::vector<SeeedPtr> seeeds
3003  )
3004 {
3005  seeedstopopulate = seeeds;
3006 }
3007 
3010  SeeedPtr seeed
3011  )
3012 {
3013  seeed->setSeeedpool(this);
3014  seeed->considerImplicits( );
3015  seeed->deleteEmptyBlocks(true);
3016  seeed->calcHashvalue();
3017 
3018  return SCIP_OKAY;
3019 }
3020 
3022  int consindexd
3023  )
3024 {
3025  SCIP_CONS* cons;
3026 
3027  cons = consToScipCons[consindexd];
3028 
3029  assert(cons != NULL);
3030 
3031  return GCGgetConsIsCardinalityCons(scip, cons);
3032 
3033 
3034 }
3035 
3038  int consindexd
3039  )
3040 {
3041  SCIP_CONS* cons;
3042 
3043  cons = consToScipCons[consindexd];
3044 
3045  assert(cons != NULL);
3046 
3047  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "setppc") == 0 )
3048  {
3049  switch( SCIPgetTypeSetppc(scip, cons) )
3050  {
3051  case SCIP_SETPPCTYPE_COVERING:
3052  return true;
3053  break;
3054  case SCIP_SETPPCTYPE_PARTITIONING:
3055  return true;
3056 
3057  case SCIP_SETPPCTYPE_PACKING:
3058  return true;
3059  }
3060  }
3061  else if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "logicor") == 0 )
3062  {
3063  return true;
3064  }
3065  else if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 )
3066  {
3067  SCIP_SETPPCTYPE type;
3068 
3069  if( GCGgetConsIsSetppc(scip, cons, &type) )
3070  {
3071  switch( type )
3072  {
3073  case SCIP_SETPPCTYPE_COVERING:
3074  return true;
3075  case SCIP_SETPPCTYPE_PARTITIONING:
3076  return true;
3077  case SCIP_SETPPCTYPE_PACKING:
3078  return true;
3079  }
3080  }
3081 
3082  }
3083 
3084  return false;
3085 }
3086 
3089  int consindexd
3090  )
3091 {
3092  SCIP_CONS* cons;
3093 
3094  cons = consToScipCons[consindexd];
3095 
3096  assert(cons != NULL);
3097 
3098  if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "setppc") == 0 )
3099  {
3100  switch( SCIPgetTypeSetppc(scip, cons) )
3101  {
3102  case SCIP_SETPPCTYPE_PARTITIONING:
3103  return true;
3104 
3105  case SCIP_SETPPCTYPE_PACKING:
3106  return true;
3107  case SCIP_SETPPCTYPE_COVERING:
3108  return false;
3109 
3110  }
3111  }
3112  else if( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 )
3113  {
3114  SCIP_SETPPCTYPE type;
3115 
3116  if( GCGgetConsIsSetppc(scip, cons, &type) )
3117  {
3118  switch( type )
3119  {
3120  case SCIP_SETPPCTYPE_PARTITIONING:
3121  return true;
3122  case SCIP_SETPPCTYPE_PACKING:
3123  return true;
3124  case SCIP_SETPPCTYPE_COVERING:
3125  return false;
3126 
3127  }
3128  }
3129 
3130  }
3131 
3132  return false;
3133 }
3134 
3135 
3136 
3137 
3140 {
3141  int maxid = 0;
3142  std::vector<SeeedPtr> tmpAllRelevantSeeeds( 0 );
3143 
3144  for( size_t i = 0; i < ancestorseeeds.size(); ++ i )
3145  {
3146  if( ancestorseeeds[i]->getID() > maxid )
3147  maxid = ancestorseeeds[i]->getID();
3148  }
3149 
3150  tmpAllRelevantSeeeds = std::vector < SeeedPtr > ( maxid + 1, NULL );
3151 
3152  for( size_t i = 0; i < ancestorseeeds.size(); ++ i )
3153  {
3154  if( ancestorseeeds[i]->getID() < 0 )
3155  continue;
3156  tmpAllRelevantSeeeds[ancestorseeeds[i]->getID()] = ancestorseeeds[i];
3157  }
3158 
3159  ancestorseeeds = tmpAllRelevantSeeeds;
3160 }
3161 
3164  int cons
3165  )
3166 {
3167  return & varsForConss[cons][0];
3168 }
3169 
3171 const SCIP_Real * Seeedpool::getValsForCons(
3172  int cons
3173  )
3174 {
3175  return & valsForConss[cons][0];
3176 }
3177 
3180  int var
3181  )
3182 {
3183  return & conssForVars[var][0];
3184 }
3185 
3188  int consindex
3189  )
3190 {
3191  if( !dualvalsoptimaloriglpcalculated )
3192  calculateDualvalsOptimalOrigLP();
3193  dualvalsoptimaloriglpcalculated = TRUE;
3194 
3195  return dualvalsoptimaloriglp[consindex];
3196 }
3197 
3200  int consindex
3201 ){
3202 
3203  if( !dualvalsrandomset )
3204  shuffleDualvalsRandom();
3205  dualvalsrandomset = TRUE;
3206 
3207  return dualvalsrandom[consindex];
3208 
3209 }
3210 
3211 
3212 
3213 
3216  int cons
3217  )
3218 {
3219  return & conssadjacencies[cons][0];
3220 }
3221 
3222 
3223 
3226  int cons
3227  )
3228 {
3229  return varsForConss[cons].size();
3230 }
3231 
3234  int var
3235  )
3236 {
3237  return conssForVars[var].size();
3238 }
3239 
3242  int cons
3243  )
3244 {
3245  return conssadjacencies[cons].size();
3246 }
3247 
3248 
3251  int varIndex
3252  )
3253 {
3254  return varToScipVar[varIndex];
3255 }
3256 
3259  int consIndex
3260  )
3261 {
3262  return consToScipCons[consIndex];
3263 }
3264 
3267  int detectorIndex
3268  )
3269 {
3270  return detectorToScipDetector[detectorIndex];
3271 }
3272 
3275  int detectorIndex
3276  )
3277 {
3278  return detectorToFinishingScipDetector[detectorIndex];
3279 }
3280 
3281 
3284  int detectorIndex
3285  )
3286 {
3287  return detectorToPostprocessingScipDetector[detectorIndex];
3288 }
3289 
3290 
3293  int row,
3294  int col
3295  )
3296 {
3297  unordered_map<std::pair<int, int>, SCIP_Real, pair_hash>::const_iterator iter = valsMap.find(
3298  std::pair<int, int>( row, col ) );
3299 
3300  if( iter == valsMap.end() )
3301  return 0.;
3302 
3303  return iter->second;
3304 }
3305 
3308  SCIP_VAR* var
3309  )
3310 {
3311  return scipVarToIndex[var];
3312 }
3313 
3316  SCIP_CONS* cons
3317  )
3318 {
3319  return scipConsToIndex[cons];
3320 }
3321 
3324  DEC_DETECTOR* detector
3325  )
3326 {
3327  return scipDetectorToIndex[detector];
3328 }
3329 
3332  DEC_DETECTOR* detector
3333  )
3334 {
3335  return scipFinishingDetectorToIndex[detector];
3336 }
3337 
3340  DEC_DETECTOR* detector
3341  )
3342 {
3343  return scipPostprocessingDetectorToIndex[detector];
3344 }
3345 
3346 
3347 
3350 {
3352 }
3353 
3356 {
3357  return nDetectors;
3358 }
3359 
3362 {
3363  return nnonzeros;
3364 }
3365 
3368 {
3369  return nFinishingDetectors;
3370 }
3371 
3374 {
3375  return nPostprocessingDetectors;
3376 }
3377 
3378 
3381 {
3382  return nVars;
3383 }
3384 
3387 {
3388  return nConss;
3389 }
3390 
3391 /* returns associated scip */
3392 
3394 {
3395  return scip;
3396 }
3397 
3400  int consid
3401  )
3402 {
3403  return consToScipCons[consid];
3404 }
3405 
3408  int varid
3409 ){
3410  return varToScipVar[varid];
3411 }
3412 
3413 
3414 
3417 {
3418  std::vector<int> toreturn( 0 );
3419  SCIP_Bool output = false;
3420 
3422  if( output && !usercandidatesnblocks.empty() )
3423  {
3424  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "number of user block number candidates: %d \n", usercandidatesnblocks.size() );
3425  }
3426 
3427  for( size_t i = 0; i < usercandidatesnblocks.size() ; ++i)
3428  {
3429  toreturn.push_back( usercandidatesnblocks[i]);
3430 
3431  if( output )
3432  {
3433  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "%d \n", usercandidatesnblocks[i] );
3434  }
3435 
3436  }
3437 
3439  std::sort( candidatesNBlocks.begin(), candidatesNBlocks.end(), sort_decr() );
3440 
3442  if( output )
3443  {
3444  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "nCandidates: %d ", candidatesNBlocks.size() );
3445 
3446 
3447  for( size_t i = 0; i < candidatesNBlocks.size(); ++ i )
3448  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "nblockcandides: %d , %d times prop", candidatesNBlocks[i].first, candidatesNBlocks[i].second );
3449  }
3450 
3452  for( size_t i = 0; i < candidatesNBlocks.size(); ++ i )
3453  toreturn.push_back( candidatesNBlocks[i].first );
3454 
3455  return toreturn;
3456 }
3457 
3458 
3460 std::vector<std::pair<int, int>> Seeedpool::getSortedCandidatesNBlocksFull()
3461 {
3462  std::vector<std::pair<int, int> > toreturn( 0 );
3463  SCIP_Bool output = false;
3464 
3466  if( output && !usercandidatesnblocks.empty() )
3467  {
3468  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "number of user block number candidates: %d \n", usercandidatesnblocks.size() );
3469  }
3470 
3471  for( size_t i = 0; i < usercandidatesnblocks.size() ; ++i)
3472  {
3473  toreturn.push_back( std::pair<int, int>(usercandidatesnblocks[i], INT_MAX ) );
3474 
3475  if( output )
3476  {
3477  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "%d \n", usercandidatesnblocks[i] );
3478  }
3479 
3480  }
3481 
3483  std::sort( candidatesNBlocks.begin(), candidatesNBlocks.end(), sort_decr() );
3484 
3486  if( output )
3487  {
3488  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "nCandidates: %d ", candidatesNBlocks.size() );
3489 
3490 
3491  for( size_t i = 0; i < candidatesNBlocks.size(); ++ i )
3492  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "nblockcandides: %d , %d times prop", candidatesNBlocks[i].first, candidatesNBlocks[i].second );
3493  }
3494 
3496  for( size_t i = 0; i < candidatesNBlocks.size(); ++ i )
3497  toreturn.push_back( candidatesNBlocks[i] );
3498 
3499  return toreturn;
3500 }
3501 
3502 
3505  int candidate
3506  )
3507 {
3508  if( candidate > 1 )
3509  {
3510  bool alreadyIn = false;
3511  for( size_t i = 0; i < candidatesNBlocks.size(); ++ i )
3512  {
3513  if( candidatesNBlocks[i].first == candidate )
3514  {
3515  alreadyIn = true;
3516  ++ candidatesNBlocks[i].second;
3517  break;
3518  }
3519  }
3520  if( ! alreadyIn )
3521  {
3522  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "added block number candidate: %d \n", candidate );
3523  candidatesNBlocks.push_back( std::pair<int, int>( candidate, 1 ) );
3524  }
3525  }
3526 }
3527 
3530  int candidate,
3531  int nvotes
3532  )
3533 {
3534  if( candidate > 1 )
3535  {
3536  bool alreadyIn = false;
3537  for( size_t i = 0; i < candidatesNBlocks.size(); ++ i )
3538  {
3539  if( candidatesNBlocks[i].first == candidate )
3540  {
3541  alreadyIn = true;
3542  candidatesNBlocks[i].second += nvotes;
3543  break;
3544  }
3545  }
3546  if( ! alreadyIn )
3547  {
3548  SCIPverbMessage(scip, SCIP_VERBLEVEL_FULL, NULL, "added block number candidate: %d \n", candidate );
3549  candidatesNBlocks.push_back( std::pair<int, int>( candidate, nvotes ) );
3550  }
3551  }
3552 }
3553 
3554 
3555 
3558  int candidate
3559  )
3560 {
3561  bool alreadyIn = false;
3562  for( size_t i = 0; i < candidatesNBlocks.size(); ++i )
3563  {
3564  if( usercandidatesnblocks[i] == candidate )
3565  {
3566  SCIPverbMessage(scip, SCIP_VERBLEVEL_DIALOG, NULL, "is already given by the user as a block number candidate, there is no advantage in adding it twice \n" );
3567  return;
3568  }
3569  }
3570  if( !alreadyIn )
3571  {
3572  SCIPverbMessage(scip, SCIP_VERBLEVEL_DIALOG, NULL, "added user block number candidate: %d \n", candidate );
3573  usercandidatesnblocks.push_back(candidate);
3574  }
3575 }
3576 
3579 {
3580  return (int) usercandidatesnblocks.size();
3581 }
3582 
3585 {
3586  /* strategy: for every subset of constraint classes and variable classes calculate gcd (greatest common divisors)
3587  * of the corresponding number of constraints/variables assigned to this class */
3588 
3589  /* if distribution of classes exceeds this number it is skipped */
3590  int maximumnclasses;
3592  std::list<int> nvarspercons(0);
3593  std::list<int>::iterator iter;
3594  int candidate = -1;
3595 
3596 
3597 
3598  SCIPgetIntParam(scip, "detection/maxnclassesfornblockcandidates", &maximumnclasses);
3599 
3601  for( size_t classifier = 0; classifier < consclassescollection.size(); ++ classifier )
3602  {
3603 
3605  if( consclassescollection[classifier]->getNClasses() > maximumnclasses )
3606  {
3607  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " the current consclass distribution includes %d classes but only %d are allowed for calcCandidatesNBlocks()\n", consclassescollection[classifier]->getNClasses(), maximumnclasses );
3608  continue;
3609  }
3610 
3612  std::vector < std::vector<int> > subsetsOfConstypes = consclassescollection[classifier]->getAllSubsets( true, true,
3613  true );
3614  std::vector<int> nConssOfClasses = consclassescollection[classifier]->getNConssOfClasses();
3615 
3617  for( size_t i = 0; i < nConssOfClasses.size(); ++ i )
3618  {
3619  addCandidatesNBlocks( nConssOfClasses[i] );
3620  }
3621 
3623  for( size_t subset = 0; subset < subsetsOfConstypes.size(); ++ subset )
3624  {
3625  int greatestCD = 1;
3626 
3627  if( subsetsOfConstypes[subset].size() == 0 || subsetsOfConstypes[subset].size() == 1 )
3628  continue;
3629 
3630  greatestCD = gcd( nConssOfClasses[subsetsOfConstypes[subset][0]], nConssOfClasses[subsetsOfConstypes[subset][1]] );
3631 
3632  for( size_t i = 2; i < subsetsOfConstypes[subset].size(); ++ i )
3633  {
3634  greatestCD = gcd( greatestCD, nConssOfClasses[subsetsOfConstypes[subset][i]] );
3635  }
3636 
3637  addCandidatesNBlocks( greatestCD );
3638  }
3639  }
3640 
3642  for( size_t classifier = 0; classifier < varclassescollection.size(); ++ classifier )
3643  {
3645  if( varclassescollection[classifier]->getNClasses() > maximumnclasses )
3646  {
3647  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " the current varclass distribution includes %d classes but only %d are allowed for calcCandidatesNBlocks()\n", varclassescollection[classifier]->getNClasses(), maximumnclasses );
3648  continue;
3649  }
3650 
3652  std::vector < std::vector<int> > subsetsOfVartypes = varclassescollection[classifier]->getAllSubsets( true, true, true,
3653  true );
3654  std::vector<int> nVarsOfClasses = varclassescollection[classifier]->getNVarsOfClasses();
3655 
3657  for( size_t i = 0; i < nVarsOfClasses.size(); ++ i )
3658  {
3659  addCandidatesNBlocks( nVarsOfClasses[i] );
3660  }
3661 
3663  for( size_t subset = 0; subset < subsetsOfVartypes.size(); ++ subset )
3664  {
3665  int greatestCD = 1;
3666 
3667  if( subsetsOfVartypes[subset].size() == 0 || subsetsOfVartypes[subset].size() == 1 )
3668  continue;
3669 
3670  greatestCD = gcd( nVarsOfClasses[subsetsOfVartypes[subset][0]], nVarsOfClasses[subsetsOfVartypes[subset][1]] );
3671 
3672  for( size_t i = 2; i < subsetsOfVartypes[subset].size(); ++ i )
3673  {
3674  greatestCD = gcd( greatestCD, nVarsOfClasses[subsetsOfVartypes[subset][i]] );
3675  }
3676 
3677  addCandidatesNBlocks( greatestCD );
3678  }
3679  }
3680 
3683  for( int c = 0; c < getNConss(); ++c )
3684  {
3685  int nvars = getNVarsForCons(c);
3686  iter = std::lower_bound(nvarspercons.begin(), nvarspercons.end(), nvars);
3687  nvarspercons.insert(iter, nvars);
3688  }
3689  iter = nvarspercons.begin();
3690  for( int c = 0; c < (int) 0.5 * getNConss(); ++c )
3691  ++iter;
3692 
3693  if( *iter != 0 )
3694  candidate = getNVars() / *iter;
3695 
3696 
3697  addCandidatesNBlocks(candidate);
3698 
3699 }
3700 
3703  ConsClassifier* givenClassifier
3704  )
3705 {
3706  SCIP_Bool allowduplicates;
3707 
3708  SCIPgetBoolParam(scip, "detection/allowclassifierduplicates/enabled", &allowduplicates);
3709 
3710  if( givenClassifier != NULL )
3711  {
3713  ConsClassifier* equiv = NULL;
3714 
3715  for( size_t i = 0; !allowduplicates && i < consclassescollection.size(); ++ i )
3716  {
3717  if( givenClassifier->classifierIsDuplicateOfClassifier( consclassescollection[i] ) )
3718  {
3719  equiv = consclassescollection[i];
3720  break;
3721  }
3722  }
3723 
3724  if( equiv == NULL )
3725  consclassescollection.push_back( givenClassifier );
3726  else
3727  {
3728  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Consclassifier \"%s\" is not considered since it offers the same structure as \"%s\" consclassifier\n", givenClassifier->getName(), equiv->getName() );
3729  delete givenClassifier;
3730  }
3731  }
3732 }
3733 
3737 {
3738  std::vector<consType> foundConstypes( 0 );
3739  std::vector<int> constypesIndices( 0 );
3740  std::vector<int> classForCons = std::vector<int>( getNConss(), - 1 );
3741  ConsClassifier* classifier;
3742 
3744  for( int i = 0; i < getNConss(); ++ i )
3745  {
3746  SCIP_CONS* cons;
3747  bool found = false;
3748  cons = getConsForIndex( i );
3749  consType cT = GCGconsGetType( cons );
3750  size_t constype;
3751 
3753  for( constype = 0; constype < foundConstypes.size(); ++ constype )
3754  {
3755  if( foundConstypes[constype] == cT )
3756  {
3757  found = true;
3758  break;
3759  }
3760  }
3762  if( ! found )
3763  {
3764  foundConstypes.push_back( GCGconsGetType( cons ) );
3765  classForCons[i] = foundConstypes.size() - 1;
3766  }
3767  else
3768  classForCons[i] = constype;
3769  }
3770 
3772  classifier = new ConsClassifier( scip, "constypes", (int) foundConstypes.size(), getNConss() );
3773 
3775  for( int c = 0; c < classifier->getNClasses(); ++ c )
3776  {
3777  std::string name;
3778  std::stringstream text;
3779  switch( foundConstypes[c] )
3780  {
3781  case linear:
3782  name = "linear";
3783  break;
3784  case knapsack:
3785  name = "knapsack";
3786  break;
3787  case varbound:
3788  name = "varbound";
3789  break;
3790  case setpacking:
3791  name = "setpacking";
3792  break;
3793  case setcovering:
3794  name = "setcovering";
3795  break;
3796  case setpartitioning:
3797  name = "setpartitioning";
3798  break;
3799  case logicor:
3800  name = "logicor";
3801  break;
3802  case sos1:
3803  name = "sos1";
3804  break;
3805  case sos2:
3806  name = "sos2";
3807  break;
3808  case unknown:
3809  name = "unknown";
3810  break;
3811  case nconsTypeItems:
3812  name = "nconsTypeItems";
3813  break;
3814  default:
3815  name = "newConstype";
3816  break;
3817  }
3818  classifier->setClassName( c, name.c_str() );
3819  text << "This class contains all constraints that are of (SCIP) constype \"" << name << "\".";
3820  classifier->setClassDescription( c, text.str().c_str() );
3821  }
3822 
3824  for( int i = 0; i < classifier->getNConss(); ++ i )
3825  {
3826  classifier->assignConsToClass( i, classForCons[i] );
3827  }
3828 
3829  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Consclassifier \"%s\" yields a classification with %d different constraint classes \n", classifier->getName(), (int) foundConstypes.size() );
3830  return classifier;
3831 }
3832 
3833 
3837 {
3838  std::vector<int> nfoundconstypesrangedsinglecount( (int) SCIP_CONSTYPE_GENERAL + 1, 0 );
3839  std::vector<int> nfoundconstypesrangeddoublecount( (int) SCIP_CONSTYPE_GENERAL + 1, 0 );
3840 
3841 // std::vector<int> constypesIndices( 0 );
3842  std::vector<int> classforcons = std::vector<int>( getNConss(), -1 );
3843  ConsClassifier* classifier;
3844 
3846  for( int c = 0; c < getNConss(); ++ c )
3847  {
3848  SCIP_CONS* cons;
3849  SCIP_Real lhs;
3850  SCIP_Real rhs;
3851  SCIP_Real* vals;
3852  SCIP_VAR** vars;
3853  int nvars;
3854  int i;
3855 
3856  cons = getConsForIndex( c );
3857 
3858  nvars = GCGconsGetNVars(scip, cons );
3859 
3860  lhs = GCGconsGetLhs(scip, cons);
3861  rhs = GCGconsGetRhs(scip, cons);
3862  if( nvars != 0 )
3863  {
3864  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &vals, nvars));
3865  SCIP_CALL_ABORT( SCIPallocBufferArray(scip, &vars, nvars));
3866  SCIP_CALL_ABORT( GCGconsGetVals(scip, cons, vals, nvars ) );
3867  SCIP_CALL_ABORT( GCGconsGetVars(scip, cons, vars, nvars ) );
3868  }
3869 
3870  for( i = 0; i < nvars; i++ )
3871  {
3872  assert(!SCIPisZero(scip, vals[i]) );
3873  }
3874 
3875 
3876  /* is constraint of type SCIP_CONSTYPE_EMPTY? */
3877  if( nvars == 0 )
3878  {
3879  SCIPdebugMsg(scip, "classified as EMPTY: ");
3880  SCIPdebugPrintCons(scip, cons, NULL);
3881  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_EMPTY]++;
3882  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_EMPTY]++;
3883  classforcons[c] = SCIP_CONSTYPE_EMPTY;
3884  continue;
3885  }
3886 
3887  /* is constraint of type SCIP_CONSTYPE_FREE? */
3888  if( SCIPisInfinity(scip, rhs) && SCIPisInfinity(scip, -lhs) )
3889  {
3890  SCIPdebugMsg(scip, "classified as FREE: ");
3891  SCIPdebugPrintCons(scip, cons, NULL);
3892  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_FREE]++;
3893  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_FREE]++;
3894  classforcons[c] = SCIP_CONSTYPE_FREE;
3895  SCIPfreeBufferArray(scip, &vars);
3896  SCIPfreeBufferArray(scip, &vals);
3897  continue;
3898  }
3899 
3900  /* is constraint of type SCIP_CONSTYPE_SINGLETON? */
3901  if( nvars == 1 )
3902  {
3903  SCIPdebugMsg(scip, "classified as SINGLETON: ");
3904  SCIPdebugPrintCons(scip, cons, NULL);
3905  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_SINGLETON] += 2 ;
3906  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_SINGLETON]++;
3907  classforcons[c] = SCIP_CONSTYPE_SINGLETON;
3908  SCIPfreeBufferArray(scip, &vars) ;
3909  SCIPfreeBufferArray(scip, &vals) ;
3910  continue;
3911  }
3912 
3913  /* is constraint of type SCIP_CONSTYPE_AGGREGATION? */
3914  if( nvars == 2 && SCIPisEQ(scip, lhs, rhs) )
3915  {
3916  SCIPdebugMsg(scip, "classified as AGGREGATION: ");
3917  SCIPdebugPrintCons(scip, cons, NULL);
3918  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_AGGREGATION]++;
3919  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_AGGREGATION]++;
3920  classforcons[c] = SCIP_CONSTYPE_AGGREGATION;
3921  SCIPfreeBufferArray(scip, &vars) ;
3922  SCIPfreeBufferArray(scip, &vals) ;
3923  continue;
3924  }
3925 
3926  /* is constraint of type SCIP_CONSTYPE_{VARBOUND}? */
3927  if( nvars == 2 )
3928  {
3929  SCIPdebugMsg(scip, "classified as VARBOUND: ");
3930  SCIPdebugPrintCons(scip, cons, NULL);
3931  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_VARBOUND] += 2 ;
3932  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_VARBOUND]++;
3933  classforcons[c] = SCIP_CONSTYPE_VARBOUND;
3934  SCIPfreeBufferArray(scip, &vars) ;
3935  SCIPfreeBufferArray(scip, &vals) ;
3936  continue;
3937  }
3938 
3939  /* is constraint of type SCIP_CONSTYPE_{SETPARTITION, SETPACKING, SETCOVERING, CARDINALITY, INVKNAPSACK}? */
3940  {
3941  SCIP_Real scale;
3942  SCIP_Real b;
3943  SCIP_Bool unmatched;
3944  int nnegbinvars;
3945 
3946  unmatched = FALSE;
3947  nnegbinvars = 0;
3948 
3949  scale = REALABS(vals[0]);
3950  for( i = 0; i < nvars && !unmatched; i++ )
3951  {
3952  unmatched = unmatched || SCIPvarGetType(vars[i]) == SCIP_VARTYPE_CONTINUOUS;
3953  unmatched = unmatched || SCIPisLE(scip, SCIPvarGetLbGlobal(vars[i]), -1.0);
3954  unmatched = unmatched || SCIPisGE(scip, SCIPvarGetUbGlobal(vars[i]), 2.0);
3955  unmatched = unmatched || !SCIPisEQ(scip, REALABS(vals[i]), scale);
3956 
3957  if( vals[i] < 0.0 )
3958  nnegbinvars++;
3959  }
3960 
3961  if( !unmatched )
3962  {
3963  if( SCIPisEQ(scip, lhs, rhs) )
3964  {
3965  b = rhs/scale + nnegbinvars;
3966  if( SCIPisEQ(scip, 1.0, b) )
3967  {
3968  SCIPdebugMsg(scip, "classified as SETPARTITION: ");
3969  SCIPdebugPrintCons(scip, cons, NULL);
3970  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_SETPARTITION] += 1 ;
3971  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_SETPARTITION]++;
3972  classforcons[c] = SCIP_CONSTYPE_SETPARTITION;
3973  SCIPfreeBufferArray(scip, &vars) ;
3974  SCIPfreeBufferArray(scip, &vals) ;
3975  continue;
3976  }
3977  else if( SCIPisIntegral(scip, b) && !SCIPisNegative(scip, b) )
3978  {
3979  SCIPdebugMsg(scip, "classified as CARDINALITY: ");
3980  SCIPdebugPrintCons(scip, cons, NULL);
3981  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_CARDINALITY] += 1 ;
3982  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_CARDINALITY]++;
3983  classforcons[c] = SCIP_CONSTYPE_CARDINALITY;
3984  SCIPfreeBufferArray(scip, &vars);
3985  SCIPfreeBufferArray(scip, &vals);
3986  continue;
3987  }
3988  }
3989 
3990  b = rhs/scale + nnegbinvars;
3991  if( SCIPisEQ(scip, 1.0, b) )
3992  {
3993  SCIPdebugMsg(scip, "classified as SETPACKING: ");
3994  SCIPdebugPrintCons(scip, cons, NULL);
3995  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_SETPACKING] += 1 ;
3996  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_SETPACKING]++;
3997  classforcons[c] = SCIP_CONSTYPE_SETPACKING;
3998  rhs = SCIPinfinity(scip);
3999  }
4000  else if( SCIPisIntegral(scip, b) && !SCIPisNegative(scip, b) )
4001  {
4002  SCIPdebugMsg(scip, "classified as INVKNAPSACK: ");
4003  SCIPdebugPrintCons(scip, cons, NULL);
4004  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_INVKNAPSACK] += 1 ;
4005  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_INVKNAPSACK]++;
4006  classforcons[c] = SCIP_CONSTYPE_INVKNAPSACK;
4007  rhs = SCIPinfinity(scip);
4008  }
4009 
4010  b = lhs/scale + nnegbinvars;
4011  if( SCIPisEQ(scip, 1.0, b) )
4012  {
4013  SCIPdebugMsg(scip, "classified as SETCOVERING: ");
4014  SCIPdebugPrintCons(scip, cons, NULL);
4015  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_SETCOVERING] += 1 ;
4016  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_SETCOVERING]++;
4017  classforcons[c] = SCIP_CONSTYPE_SETCOVERING;
4018  lhs = -SCIPinfinity(scip);
4019  }
4020 
4021  if( SCIPisInfinity(scip, -lhs) && SCIPisInfinity(scip, rhs) )
4022  {
4023  SCIPfreeBufferArray(scip, &vars);
4024  SCIPfreeBufferArray(scip, &vals);
4025  continue;
4026  }
4027  }
4028  }
4029 
4030  /* is constraint of type SCIP_CONSTYPE_{EQKNAPSACK, BINPACKING, KNAPSACK}? */
4031  /* @todo If coefficients or rhs are not integral, we currently do not check
4032  * if the constraint could be scaled (finitely), such that they are.
4033  */
4034  {
4035  SCIP_Real b;
4036  SCIP_Bool unmatched;
4037 
4038  b = rhs;
4039  unmatched = FALSE;
4040  for( i = 0; i < nvars && !unmatched; i++ )
4041  {
4042  unmatched = unmatched || SCIPvarGetType(vars[i]) == SCIP_VARTYPE_CONTINUOUS;
4043  unmatched = unmatched || SCIPisLE(scip, SCIPvarGetLbGlobal(vars[i]), -1.0);
4044  unmatched = unmatched || SCIPisGE(scip, SCIPvarGetUbGlobal(vars[i]), 2.0);
4045  unmatched = unmatched || !SCIPisIntegral(scip, vals[i]);
4046 
4047  if( SCIPisNegative(scip, vals[i]) )
4048  b -= vals[i];
4049  }
4050  unmatched = unmatched || !isFiniteNonnegativeIntegral(scip, b);
4051 
4052  if( !unmatched )
4053  {
4054  if( SCIPisEQ(scip, lhs, rhs) )
4055  {
4056  SCIPdebugMsg(scip, "classified as EQKNAPSACK: ");
4057  SCIPdebugPrintCons(scip, cons, NULL);
4058  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_EQKNAPSACK] += 1 ;
4059  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_EQKNAPSACK]++;
4060  classforcons[c] = SCIP_CONSTYPE_EQKNAPSACK;
4061  SCIPfreeBufferArray(scip, &vars);
4062  SCIPfreeBufferArray(scip, &vals);
4063  continue;
4064  }
4065  else
4066  {
4067  SCIP_Bool matched;
4068 
4069  matched = FALSE;
4070  for( i = 0; i < nvars && !matched; i++ )
4071  {
4072  matched = matched || SCIPisEQ(scip, b, REALABS(vals[i]));
4073  }
4074 
4075  SCIPdebugMsg(scip, "classified as %s: ", matched ? "BINPACKING" : "KNAPSACK");
4076  SCIPdebugPrintCons(scip, cons, NULL);
4077  nfoundconstypesrangeddoublecount[matched ? SCIP_CONSTYPE_BINPACKING : SCIP_CONSTYPE_KNAPSACK] += 1 ;
4078  nfoundconstypesrangedsinglecount[matched ? SCIP_CONSTYPE_BINPACKING : SCIP_CONSTYPE_KNAPSACK]++;
4079  classforcons[c] = matched ? SCIP_CONSTYPE_BINPACKING : SCIP_CONSTYPE_KNAPSACK;
4080 
4081  }
4082 
4083  if( SCIPisInfinity(scip, -lhs) )
4084  {
4085  SCIPfreeBufferArray(scip, &vars);
4086  SCIPfreeBufferArray(scip, &vals);
4087  continue;
4088  }
4089  else
4090  rhs = SCIPinfinity(scip);
4091  }
4092  }
4093 
4094  /* is constraint of type SCIP_CONSTYPE_{INTKNAPSACK}? */
4095  {
4096  SCIP_Real b;
4097  SCIP_Bool unmatched;
4098 
4099  unmatched = FALSE;
4100 
4101  b = rhs;
4102  unmatched = unmatched || !isFiniteNonnegativeIntegral(scip, b);
4103 
4104  for( i = 0; i < nvars && !unmatched; i++ )
4105  {
4106  unmatched = unmatched || SCIPvarGetType(vars[i]) == SCIP_VARTYPE_CONTINUOUS;
4107  unmatched = unmatched || SCIPisNegative(scip, SCIPvarGetLbGlobal(vars[i]));
4108  unmatched = unmatched || !SCIPisIntegral(scip, vals[i]);
4109  unmatched = unmatched || SCIPisNegative(scip, vals[i]);
4110  }
4111 
4112  if( !unmatched )
4113  {
4114  SCIPdebugMsg(scip, "classified as INTKNAPSACK: ");
4115  SCIPdebugPrintCons(scip, cons, NULL);
4116  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_INTKNAPSACK] += 1 ;
4117  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_INTKNAPSACK]++;
4118  classforcons[c] = SCIP_CONSTYPE_INTKNAPSACK;
4119 
4120  if( SCIPisInfinity(scip, -lhs) )
4121  {
4122  SCIPfreeBufferArray(scip, &vars);
4123  SCIPfreeBufferArray(scip, &vals);
4124  continue;
4125  }
4126  else
4127  rhs = SCIPinfinity(scip);
4128  }
4129  }
4130 
4131  /* is constraint of type SCIP_CONSTYPE_{MIXEDBINARY}? */
4132  {
4133  SCIP_Bool unmatched;
4134 
4135  unmatched = FALSE;
4136  for( i = 0; i < nvars && !unmatched; i++ )
4137  {
4138  if( SCIPvarGetType(vars[i]) != SCIP_VARTYPE_CONTINUOUS
4139  && (SCIPisLE(scip, SCIPvarGetLbGlobal(vars[i]), -1.0)
4140  || SCIPisGE(scip, SCIPvarGetUbGlobal(vars[i]), 2.0)) )
4141  unmatched = TRUE;
4142  }
4143 
4144  if( !unmatched )
4145  {
4146  SCIPdebugMsg(scip, "classified as MIXEDBINARY (%d): ", isRangedRow(scip, lhs, rhs) ? 2 : 1);
4147  SCIPdebugPrintCons(scip, cons, NULL);
4148  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_MIXEDBINARY] += 1 ;
4149  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_MIXEDBINARY]++;
4150  classforcons[c] = SCIP_CONSTYPE_MIXEDBINARY;
4151  SCIPfreeBufferArray(scip, &vars) ;
4152  SCIPfreeBufferArray(scip, &vals) ;
4153  continue;
4154 
4155  }
4156  }
4157 
4158  /* no special structure detected */
4159  SCIPdebugMsg(scip, "classified as GENERAL: ");
4160  SCIPdebugPrintCons(scip, cons, NULL);
4161  nfoundconstypesrangeddoublecount[SCIP_CONSTYPE_GENERAL] += 1 ;
4162  nfoundconstypesrangedsinglecount[SCIP_CONSTYPE_GENERAL]++;
4163  classforcons[c] = SCIP_CONSTYPE_GENERAL;
4164  SCIPfreeBufferArray(scip, &vars);
4165  SCIPfreeBufferArray(scip, &vals);
4166  }
4167 
4168 
4169 
4170 
4171  classifier = new ConsClassifier( scip, "constypes according to miplib", (int) SCIP_CONSTYPE_GENERAL + 1, getNConss() );
4172 
4173 
4175  for( int c = 0; c < classifier->getNClasses(); ++ c )
4176  {
4177  std::string name;
4178  std::stringstream text;
4179  switch( c )
4180  {
4181  case (int) SCIP_CONSTYPE_EMPTY:
4182  name = "empty";
4183  break;
4184  case SCIP_CONSTYPE_FREE:
4185  name = "free";
4186  break;
4188  name = "singleton";
4189  break;
4191  name = "aggregation";
4192  break;
4194  name = "varbound";
4195  break;
4197  name = "setpartition";
4198  break;
4200  name = "setpacking";
4201  break;
4203  name = "setcovering";
4204  break;
4206  name = "cardinality";
4207  break;
4209  name = "invknapsack";
4210  break;
4212  name = "eqknapsack";
4213  break;
4215  name = "binpacking";
4216  break;
4218  name = "knapsack";
4219  break;
4221  name = "intknapsack";
4222  break;
4224  name = "mixed binary";
4225  break;
4226  case SCIP_CONSTYPE_GENERAL:
4227  name = "general";
4228  break;
4229  default:
4230  name = "unknown";
4231  break;
4232 
4233 
4234  }
4235 
4236 
4237 #ifdef WRITE_ORIG_CONSTYPES
4238  myfile << " " << nfoundconstypesrangeddoublecount[c] << ",";
4239 #endif
4240 
4241  classifier->setClassName( c, name.c_str() );
4242  text << "This class contains all constraints that are of (miplib) constype \"" << name << "\".";
4243  classifier->setClassDescription( c, text.str().c_str() );
4244  }
4245 
4246 #ifdef WRITE_ORIG_CONSTYPES
4247  myfile << std::endl;
4248  myfile.close();
4249 #endif
4250 
4251 
4252 
4253  for( int i = 0; i < classifier->getNConss(); ++ i )
4254  {
4255  classifier->assignConsToClass( i, classforcons[i] );
4256  }
4257 
4258 
4259 
4260  classifier->removeEmptyClasses();
4261  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Consclassifier \"%s\" yields a classification with %d different constraint classes \n", classifier->getName(), classifier->getNClasses() );
4262 
4263  return classifier;
4264 }
4265 
4266 
4267 
4268 
4269 
4270 
4271 
4275 {
4276  std::vector < std::string > consnamesToCompare( getNConss(), "" );
4277  std::vector<int> nConssConstype( 0 );
4278  std::vector<int> classForCons = std::vector<int>( getNConss(), - 1 );
4279  std::vector < std::string > nameClasses( 0 );
4280  ConsClassifier* classifier;
4281 
4283  for( int i = 0; i < getNConss(); ++ i )
4284  {
4285  int nremoved;
4286  char consname[SCIP_MAXSTRLEN];
4287  strcpy( consname, SCIPconsGetName( getConsForIndex( i ) ) );
4288 
4289  removeDigits( consname, & nremoved );
4290  consnamesToCompare[i] = std::string( consname );
4291  }
4292 
4293  for( int i = 0; i < getNConss(); ++ i )
4294  {
4296  bool belongstoexistingclass = false;
4297 
4298  for( size_t j = 0; j < nameClasses.size(); ++ j )
4299  {
4300  if( nameClasses[j].compare( consnamesToCompare[i] ) == 0 )
4301  {
4302  belongstoexistingclass = true;
4303  classForCons[i] = j;
4304  nConssConstype[j] ++;
4305  break;
4306  }
4307  }
4309  if( ! belongstoexistingclass )
4310  {
4311  nameClasses.push_back( consnamesToCompare[i] );
4312  nConssConstype.push_back( 1 );
4313  classForCons[i] = nameClasses.size() - 1;
4314 
4315  }
4316  }
4317 
4319  classifier = new ConsClassifier( scip, "consnames", (int) nameClasses.size(), getNConss() );
4320 
4322  for( int c = 0; c < classifier->getNClasses(); ++ c )
4323  {
4324  std::stringstream text;
4325  classifier->setClassName( c, nameClasses[c].c_str() );
4326  text << "This class contains all constraints with name \"" << nameClasses[c] << "\".";
4327  classifier->setClassDescription( c, text.str().c_str() );
4328  }
4329 
4331  for( int i = 0; i < classifier->getNConss(); ++ i )
4332  {
4333  classifier->assignConsToClass( i, classForCons[i] );
4334  }
4335 
4336  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Consclassifier \"%s\" yields a classification with %d different constraint classes \n", classifier->getName(), classifier->getNClasses() );
4337 
4338  return classifier;
4339 }
4340 
4345  int connectivity
4346  )
4347 {
4348  std::vector < std::string > consnamesToCompare( getNConss(), "" );
4349  std::vector<int> nConssConstype( 0 );
4350  std::vector<int> classForCons = std::vector<int>( getNConss(), - 1 );
4351  std::vector<bool> alreadyReached( getNConss(), false );
4352  std::queue<int> helpqueue = std::queue<int>();
4353  int nUnreachedConss = getNConss();
4354  int currentClass = - 1;
4355  int nmaxconss = 5000;
4356 
4357  std::stringstream classifierName;
4358  classifierName << "lev-dist-" << connectivity;
4359  ConsClassifier* classifier = new ConsClassifier( scip, classifierName.str().c_str(), 0, getNConss() );
4360 
4362  if( getNConss() > nmaxconss )
4363  {
4364 
4365  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " skipped levenshtein distance based constraint classes calculating since number of constraints %d exceeds limit %d \n", getNConss(), nmaxconss );
4366  delete classifier;
4367  return NULL;
4368  }
4369 
4370  std::vector < std::vector<int> > levenshteindistances( getNConss(), std::vector<int>( getNConss(), - 1 ) );
4371 
4373  for( int i = 0; i < getNConss(); ++ i )
4374  {
4375  consnamesToCompare[i] = std::string( SCIPconsGetName( getConsForIndex( i ) ) );
4376  }
4377 
4379  for( int i = 0; i < getNConss(); ++ i )
4380  {
4381  for( int j = i + 1; j < getNConss(); ++ j )
4382  {
4383  levenshteindistances[i][j] = calcLevenshteinDistance( consnamesToCompare[i], consnamesToCompare[j] );
4384  levenshteindistances[j][i] = levenshteindistances[i][j];
4385  }
4386  }
4387 
4389  while( nUnreachedConss > 0 )
4390  {
4391  int firstUnreached = - 1;
4392  currentClass ++;
4393  assert( helpqueue.empty() );
4394  for( int i = 0; i < getNConss(); ++ i )
4395  {
4396  if( classForCons[i] == - 1 )
4397  {
4398  firstUnreached = i;
4399  break;
4400  }
4401  }
4402 
4403  helpqueue.push( firstUnreached );
4404  alreadyReached[firstUnreached] = true;
4405  classForCons[firstUnreached] = currentClass;
4406  -- nUnreachedConss;
4407 
4409  while( ! helpqueue.empty() )
4410  {
4411  int nodecons = helpqueue.front();
4412  helpqueue.pop();
4413  for( int j = 0; j < getNConss(); ++ j )
4414  {
4415 
4416  if( alreadyReached[j] )
4417  continue;
4418 
4419  if( j == nodecons )
4420  continue;
4421 
4422  if( levenshteindistances[j][nodecons] > connectivity )
4423  continue;
4424 
4425  alreadyReached[j] = true;
4426  classForCons[j] = currentClass;
4427  -- nUnreachedConss;
4428  helpqueue.push( j );
4429  }
4430  }
4431 
4433  std::stringstream text;
4434  text << "This class contains all constraints with a name similar to \"" << consnamesToCompare[firstUnreached] << "\".";
4435  classifier->addClass( consnamesToCompare[firstUnreached].c_str(), text.str().c_str(), BOTH );
4436  }
4437 
4439  for( int i = 0; i < classifier->getNConss(); ++ i )
4440  {
4441  classifier->assignConsToClass( i, classForCons[i] );
4442  }
4443 
4444  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Consclassifier levenshtein: connectivity of %d yields a classification with %d different constraint classes. \n", connectivity, currentClass + 1);
4445 
4446  return classifier;
4447 }
4448 
4452 {
4453  std::vector<int> nconssforclass( 0 );
4454  std::vector<int> differentNNonzeros( 0 );
4455  std::vector<int> classForCons( getNConss(), - 1 );
4456  int counterClasses = 0;
4457 
4459  for( int i = 0; i < getNConss(); ++ i )
4460  {
4461  int consnnonzeros = getNVarsForCons( i );
4462  bool nzalreadyfound = false;
4463 
4465  for( size_t nzid = 0; nzid < differentNNonzeros.size(); ++ nzid )
4466  {
4467  if( consnnonzeros == differentNNonzeros[nzid] )
4468  {
4469  nzalreadyfound = true;
4470  classForCons[i] = nzid;
4471  ++ nconssforclass[nzid];
4472  break;
4473  }
4474  }
4475 
4477  if( ! nzalreadyfound )
4478  {
4479  classForCons[i] = counterClasses;
4480  ++ counterClasses;
4481  differentNNonzeros.push_back( consnnonzeros );
4482  nconssforclass.push_back( 1 );
4483  }
4484  }
4485 
4487  ConsClassifier* classifier = new ConsClassifier( scip, "nonzeros", (int) differentNNonzeros.size(), getNConss() );
4488 
4490  for( int c = 0; c < classifier->getNClasses(); ++ c )
4491  {
4492  std::stringstream text;
4493  text << differentNNonzeros[c];
4494  classifier->setClassName( c, text.str().c_str() );
4495  text.str( "" );
4496  text.clear();
4497  text << "This class contains all constraints with " << differentNNonzeros[c] << " nonzero coefficients.";
4498  classifier->setClassDescription( c, text.str().c_str() );
4499  }
4500 
4502  for( int i = 0; i < classifier->getNConss(); ++ i )
4503  {
4504  classifier->assignConsToClass( i, classForCons[i] );
4505  }
4506  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Consclassifier \"%s\" yields a classification with %d different constraint classes \n", classifier->getName(), classifier->getNClasses() );
4507 
4508  return classifier;
4509 }
4510 
4513  int givenClassifierIndex
4514  )
4515 {
4516  assert( 0 <= givenClassifierIndex && givenClassifierIndex < (int) consclassescollection.size() );
4517 
4518  return consclassescollection[givenClassifierIndex];
4519 }
4520 
4523  int givenClassifierIndex
4524  )
4525 {
4526  int nconss = consclassescollection[givenClassifierIndex]->getNConss();
4527  int* output = new int[nconss];
4528  for( int i = 0; i < nconss; ++ i )
4529  output[i] = consclassescollection[givenClassifierIndex]->getClassOfCons( i );
4530  return & output[0];
4531 }
4532 
4535 {
4536  return (int) consclassescollection.size();
4537 }
4538 
4541 {
4543  int maxnclasses = 0;
4544 
4545  if( getNConss() + getNVars() >= 50000 )
4546  SCIPgetIntParam(scip, "detection/maxnclassesperclassifierforlargeprobs", &maxnclasses);
4547  else
4548  SCIPgetIntParam(scip, "detection/maxnclassesperclassifier", &maxnclasses);
4549 
4550  for( size_t classifierid = 0; classifierid < consclassescollection.size(); ++ classifierid )
4551  {
4552  ConsClassifier* newclassifier = consclassescollection[classifierid]->reduceClasses( maxnclasses );
4553 
4554  if( newclassifier != NULL )
4555  {
4556  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Added reduced version of consclassifier %s with %d different constraint classes \n", consclassescollection[classifierid]->getName(), maxnclasses );
4557  addConsClassifier( newclassifier );
4558  }
4559  }
4560 }
4561 
4564  VarClassifier* givenClassifier
4565  )
4566 {
4567  SCIP_Bool allowduplicates;
4568 
4569  SCIPgetBoolParam(scip, "detection/allowclassifierduplicates/enabled", &allowduplicates);
4570 
4571  if( givenClassifier != NULL )
4572  {
4574  VarClassifier* equiv = NULL;
4575 
4576  for( size_t i = 0; !allowduplicates && i < varclassescollection.size(); ++ i )
4577  {
4578  if( givenClassifier->classifierIsDuplicateOfClassifier( varclassescollection[i] ) )
4579  {
4580  equiv = varclassescollection[i];
4581  break;
4582  }
4583  }
4584 
4585  if( equiv == NULL )
4586  varclassescollection.push_back( givenClassifier );
4587  else
4588  {
4589  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Varclassifier \"%s\" is not considered since it offers the same structure as \"%s\"\n", givenClassifier->getName(), equiv->getName() );
4590  delete givenClassifier;
4591  }
4592 
4593  }
4594 }
4595 
4599 {
4600  std::vector<SCIP_Real> foundobjvals( 0 );
4601  std::vector<int> classforvars( getNVars(), -1 );
4602  int curclassindex;
4603  SCIP_Real curobjval;
4604  VarClassifier* classifier;
4606  for( int v = 0; v < getNVars(); ++v )
4607  {
4608  assert( getVarForIndex( v ) != NULL );
4609  curobjval = SCIPvarGetObj( getVarForIndex( v ) );
4610  curclassindex = -1;
4611 
4613  for( size_t c = 0; c < foundobjvals.size(); ++c )
4614  {
4615  if( SCIPisEQ( scip, curobjval, foundobjvals[c] ) )
4616  {
4617  curclassindex = c;
4618  break;
4619  }
4620  }
4621 
4623  if( curclassindex == -1 )
4624  {
4625  foundobjvals.push_back( curobjval );
4626  classforvars[v] = foundobjvals.size() - 1;
4627  }
4628  else
4629  {
4630  classforvars[v] = curclassindex;
4631  }
4632  }
4633 
4634  classifier = new VarClassifier( scip, "varobjvals", (int) foundobjvals.size(), getNVars() );
4635 
4637  for ( int c = 0; c < classifier->getNClasses(); ++c )
4638  {
4639  std::stringstream name;
4640  std::stringstream text;
4641 
4642  name << std::setprecision( 5 ) << foundobjvals[c];
4643  text << "This class contains all variables with objective function value " << name.str() << ".";
4644 
4645  classifier->setClassName( c, name.str().c_str() );
4646  classifier->setClassDescription( c, text.str().c_str() );
4647  }
4648 
4650  for ( int v = 0; v < classifier->getNVars(); ++v )
4651  {
4652  classifier->assignVarToClass( v, classforvars[v] );
4653  }
4654 
4655  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Varclassifier \"%s\" yields a classification with %d different variable classes\n", classifier->getName(), classifier->getNClasses() ) ;
4656 
4657  return classifier;
4658 }
4659 
4665 {
4666  VarClassifier* classifier= new VarClassifier( scip, "varobjvalsigns", 3, getNVars() );
4667  SCIP_Real curobjval;
4668 
4670  classifier->setClassName( 0, "zero" );
4671  classifier->setClassDescription( 0, "This class contains all variables with objective function value zero." );
4672  classifier->setClassDecompInfo( 0, MASTER );
4673  classifier->setClassName( 1, "positive" );
4674  classifier->setClassDescription( 1, "This class contains all variables with positive objective function value." );
4675  classifier->setClassDecompInfo( 1, ALL );
4676  classifier->setClassName( 2, "negative" );
4677  classifier->setClassDescription( 2, "This class contains all variables with negative objective function value." );
4678  classifier->setClassDecompInfo( 2, ALL );
4679 
4681  for( int v = 0; v < getNVars(); ++v )
4682  {
4683  assert( getVarForIndex( v ) != NULL );
4684  curobjval = SCIPvarGetObj( getVarForIndex( v ) );
4685 
4686  if( SCIPisZero( scip, curobjval ) )
4687  {
4688  classifier->assignVarToClass( v, 0 );
4689  }
4690  else if ( SCIPisPositive( scip, curobjval ) )
4691  {
4692  classifier->assignVarToClass( v, 1 );
4693  }
4694  else
4695  {
4696  classifier->assignVarToClass( v, 2 );
4697  }
4698  }
4699 
4700  /* remove a class if there is no variable with the respective sign */
4701  classifier->removeEmptyClasses();
4702 
4703  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Varclassifier \"%s\" yields a classification with %d different variable classes\n", classifier->getName(), classifier->getNClasses() ) ;
4704 
4705  return classifier;
4706 }
4707 
4711 {
4712  std::vector < SCIP_VARTYPE > foundVartypes( 0 );
4713  std::vector<int> classForVars = std::vector<int>( getNVars(), - 1 );
4714  VarClassifier* classifier;
4715 
4716  SCIP_Bool onlycontsub;
4717  SCIP_Bool onlybinmaster;
4718 
4719  SCIPgetBoolParam(scip, "detection/benders/onlycontsubpr", &onlycontsub);
4720  SCIPgetBoolParam(scip, "detection/benders/onlybinmaster", &onlybinmaster);
4721 
4723  for( int i = 0; i < getNVars(); ++ i )
4724  {
4725  SCIP_VAR* var;
4726  bool found = false;
4727  var = getVarForIndex( i );
4728  SCIP_VARTYPE vT = SCIPvarGetType( var );
4729  size_t vartype;
4730 
4731  if( onlycontsub )
4732  {
4733  if ( vT == SCIP_VARTYPE_BINARY )
4734  vT = SCIP_VARTYPE_INTEGER;
4735  if( vT == SCIP_VARTYPE_IMPLINT )
4736  vT = SCIP_VARTYPE_CONTINUOUS;
4737  }
4738 
4740  for( vartype = 0; vartype < foundVartypes.size(); ++ vartype )
4741  {
4742  if( foundVartypes[vartype] == vT )
4743  {
4744  found = true;
4745  break;
4746  }
4747  }
4749  if( ! found )
4750  {
4751  foundVartypes.push_back( vT );
4752  classForVars[i] = foundVartypes.size() - 1;
4753  }
4754  else
4755  classForVars[i] = vartype;
4756  }
4757 
4759  classifier = new VarClassifier( scip, "vartypes", (int) foundVartypes.size(), getNVars() );
4760 
4762  for( int c = 0; c < classifier->getNClasses(); ++ c )
4763  {
4764  std::string name;
4765  std::stringstream text;
4766  switch( foundVartypes[c] )
4767  {
4768  case SCIP_VARTYPE_BINARY:
4769  name = "bin";
4770  if( onlybinmaster )
4771  classifier->setClassDecompInfo(c, gcg::LINKING);
4772  break;
4773  case SCIP_VARTYPE_INTEGER:
4774  name = "int";
4775  if( onlycontsub )
4776  classifier->setClassDecompInfo(c, gcg::LINKING);
4777  if( onlybinmaster )
4778  classifier->setClassDecompInfo(c, gcg::BLOCK);
4779  break;
4780  case SCIP_VARTYPE_IMPLINT:
4781  name = "impl";
4782  if( onlybinmaster )
4783  classifier->setClassDecompInfo(c, gcg::BLOCK);
4784  break;
4785  case SCIP_VARTYPE_CONTINUOUS:
4786  name = "cont";
4787  if( onlycontsub )
4788  classifier->setClassDecompInfo(c, gcg::BLOCK);
4789  if( onlybinmaster )
4790  classifier->setClassDecompInfo(c, gcg::BLOCK);
4791  break;
4792  default:
4793  name = "newVartype";
4794  break;
4795  }
4796  classifier->setClassName( c, name.c_str() );
4797  text << "This class contains all variables that are of (SCIP) vartype \"" << name << "\".";
4798  classifier->setClassDescription( c, text.str().c_str() );
4799  }
4800 
4802  for( int i = 0; i < classifier->getNVars(); ++ i )
4803  {
4804  classifier->assignVarToClass( i, classForVars[i] );
4805  }
4806 
4807  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Varclassifier \"%s\" yields a classification with %d different variable classes\n", classifier->getName(), classifier->getNClasses() ) ;
4808 
4809 
4810 
4811 
4812  return classifier;
4813 }
4814 
4817  int givenClassifierIndex
4818  )
4819 {
4820  assert( 0 <= givenClassifierIndex && givenClassifierIndex < (int) varclassescollection.size() );
4821 
4822  return varclassescollection[givenClassifierIndex];
4823 }
4824 
4827  int givenClassifierIndex
4828  )
4829 {
4830  int nvars = varclassescollection[givenClassifierIndex]->getNVars();
4831  int* output = new int[nvars];
4832  for( int i = 0; i < nvars; ++ i )
4833  output[i] = varclassescollection[givenClassifierIndex]->getClassOfVar( i );
4834  return & output[0];
4835 }
4836 
4839 {
4840  return (int) varclassescollection.size();
4841 }
4842 
4845 {
4847  int maxnclasses = 0;
4848 
4849  if( getNConss() + getNVars() >= 50000 )
4850  SCIPgetIntParam(scip, "detection/maxnclassesperclassifierforlargeprobs", &maxnclasses);
4851  else
4852  SCIPgetIntParam(scip, "detection/maxnclassesperclassifier", &maxnclasses);
4853 
4854  for( size_t classifierid = 0; classifierid < varclassescollection.size(); ++ classifierid )
4855  {
4856  VarClassifier* newclassifier = varclassescollection[classifierid]->reduceClasses( maxnclasses );
4857 
4858  if( newclassifier != NULL )
4859  {
4860  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, " Added reduced version of varclassifier %s with %d different variable classes\n", varclassescollection[classifierid]->getName(), maxnclasses ) ;
4861  addVarClassifier( newclassifier );
4862  }
4863  }
4864 }
4865 
4869  std::vector<SeeedPtr> seeeds
4870  )
4871 {
4872  std::vector<SeeedPtr> remainingSeeeds( 0 );
4873  std::vector<SeeedPtr> oneBlockSeeeds( 0 );
4874 
4875  int nmasterconssfirst = 1000;
4876  int nmasterconsssecond = 1001;
4877 
4878  for( size_t i = 0; i < seeeds.size(); ++ i )
4879  {
4881  if( seeeds[i]->getNBlocks() == 1 )
4882  {
4883  if( seeeds[i]->getNMasterconss() < nmasterconssfirst )
4884  {
4885  nmasterconsssecond = nmasterconssfirst;
4886  nmasterconssfirst = seeeds[i]->getNMasterconss();
4887  }
4888  else if( seeeds[i]->getNMasterconss() < nmasterconsssecond )
4889  nmasterconsssecond = seeeds[i]->getNMasterconss();
4890 
4891  }
4892  else
4893  remainingSeeeds.push_back( seeeds[i] );
4894  }
4895 
4897  for( int i = 0; i < (int) seeeds.size(); ++ i )
4898  {
4899  if( seeeds[i]->getNBlocks() == 1
4900  && ( seeeds[i]->getNMasterconss() == nmasterconssfirst || seeeds[i]->getNMasterconss() == nmasterconsssecond ) )
4901  remainingSeeeds.push_back( seeeds[i] );
4902  else if( seeeds[i]->getNBlocks() == 1 )
4903  oneBlockSeeeds.push_back( seeeds[i] );
4904  }
4905 
4907  for( int i = 0; i < (int) oneBlockSeeeds.size(); ++ i )
4908  {
4909  delete oneBlockSeeeds[i];
4910  oneBlockSeeeds[i] = NULL;
4911  }
4912 
4913  return remainingSeeeds;
4914 }
4915 
4916 
4917 SCIP_RETCODE Seeedpool::shuffleDualvalsRandom()
4918 {
4919 
4920  GCG_RANDOM_DUAL_METHOD usedmethod;
4921  SCIP_RANDNUMGEN* randnumgen;
4922 
4923  int method;
4924 
4925  SCIPgetIntParam(scip, "detection/strong_detection/dualvalrandommethod", &method);
4926 
4928  usedmethod = GCG_RANDOM_DUAL_NAIVE;
4929 
4930  if ( method == 2 )
4931  usedmethod = GCG_RANDOM_DUAL_EXPECTED_EQUAL;
4932  else if ( method == 3 )
4934 
4935  SCIPverbMessage(scip, SCIP_VERBLEVEL_HIGH, NULL, "set dual val random method to %d. \n", method );
4941  dualvalsrandom = std::vector<SCIP_Real>(getNConss(), 0.);
4942 
4943  /* create random number generator */
4944  SCIP_CALL( SCIPcreateRandom(scip, &randnumgen, DEFAULT_RANDSEED, TRUE) );
4945 
4946 
4950  if( usedmethod == GCG_RANDOM_DUAL_NAIVE )
4951  {
4952  for( int c = 0; c < getNConss(); ++c )
4953  {
4954  SCIP_Real dualval;
4955  SCIP_Real factor;
4956  SCIP_CONS* cons;
4957 
4958  cons = getConsForIndex(c);
4959  if( SCIPisInfinity( scip, -GCGconsGetLhs(scip, cons) ))
4960  {
4961  SCIP_Real modifier;
4962  modifier = 0.;
4963  if ( SCIPgetObjsense(scip) != SCIP_OBJSENSE_MAXIMIZE )
4964  modifier = -1.;
4965 
4966  factor = MAX(1., ABS(GCGconsGetRhs(scip, cons) ) );
4967  dualval = SCIPrandomGetReal(randnumgen, 0.+modifier, 1.+modifier ) * factor;
4968  }
4969  else if( SCIPisInfinity( scip, GCGconsGetRhs(scip, cons) ) )
4970  {
4971  SCIP_Real modifier;
4972  modifier = 0.;
4973  if ( SCIPgetObjsense(scip) != SCIP_OBJSENSE_MINIMIZE )
4974  modifier = -1.;
4975 
4976  factor = MAX(1., ABS(GCGconsGetLhs(scip, cons) ) );
4977  dualval = SCIPrandomGetReal(randnumgen, 0.+modifier, 1.+modifier ) * factor;
4978 
4979  }
4980  else
4981  {
4982  factor = MAX(1., ABS(GCGconsGetLhs(scip, cons) ) );
4983  factor = MAX( factor, ABS(GCGconsGetRhs(scip, cons) ) );
4984  dualval = SCIPrandomGetReal(randnumgen, -1., 1. ) * factor;
4985  }
4986 
4987  dualvalsrandom[c] = dualval;
4988  }
4989 
4990  } /* end naive approach */
4991 
4993  if( usedmethod == GCG_RANDOM_DUAL_EXPECTED_EQUAL || usedmethod == GCG_RANDOM_DUAL_EXPECTED_OVERESTIMATE)
4994  {
4995  std::default_random_engine generator (DEFAULT_RANDSEED);
4996 
4997 
4998  SCIP_Real largec = 0.;
4999  for( int v = 0; v < getNVars(); ++v )
5000  largec += ABS( SCIPvarGetObj( getVarForIndex(v) ) );
5001 
5002 
5003  for( int c = 0; c < getNConss(); ++c )
5004  {
5005  SCIP_Real dualval;
5006  SCIP_CONS* cons;
5007  std::exponential_distribution<SCIP_Real> distribution (1.0);
5008 
5009  SCIP_Real divisor = 0.;
5010 
5011  SCIP_Real randomval;
5012 
5013  for( int v = 0; v < getNVarsForCons(c); ++v )
5014  {
5015  int var = getVarsForCons(c)[v];
5016  divisor += ABS( getVal(c, var) );
5017  }
5018  if ( usedmethod == GCG_RANDOM_DUAL_EXPECTED_EQUAL )
5019  divisor *= getNConss();
5020 
5022  distribution = std::exponential_distribution<SCIP_Real>( divisor/largec);
5023 
5024  randomval = distribution(generator);
5025 
5026  cons = getConsForIndex(c);
5027  if( SCIPisInfinity( scip, -GCGconsGetLhs(scip, cons) ))
5028  {
5029  SCIP_Real modifier;
5030  modifier = 1.;
5031  if ( SCIPgetObjsense(scip) != SCIP_OBJSENSE_MAXIMIZE )
5032  modifier = -1.;
5033 
5034  dualval = modifier * randomval;
5035  }
5036  else if( SCIPisInfinity( scip, GCGconsGetRhs(scip, cons) ) )
5037  {
5038  SCIP_Real modifier;
5039  modifier = 1.;
5040  if ( SCIPgetObjsense(scip) != SCIP_OBJSENSE_MINIMIZE )
5041  modifier = -1.;
5042 
5043  dualval = modifier * randomval;
5044 
5045  }
5046  else
5047  {
5048  SCIP_Real helpval = SCIPrandomGetReal(randnumgen, -1., 1. );
5049 
5050  if ( helpval < 0. )
5051  dualval = -1. * randomval ;
5052  else dualval = randomval;
5053  }
5054 
5055  dualvalsrandom[c] = dualval;
5056  }
5057 
5058  }
5059 
5060 
5061  return SCIP_OKAY;
5062 
5063 }
5064 
5067  SeeedPtr seeed,
5068  DEC_DECOMP** newdecomp
5069  )
5070 {
5071  char detectorchaininfo[SCIP_MAXSTRLEN];
5072  SCIP_HASHMAP* vartoblock;
5073  SCIP_HASHMAP* constoblock;
5074  SCIP_HASHMAP* varindex;
5075  SCIP_HASHMAP* consindex;
5076  SCIP_VAR*** stairlinkingvars;
5077  SCIP_VAR*** subscipvars;
5078  SCIP_VAR** linkingvars;
5079  SCIP_CONS** linkingconss;
5080  SCIP_CONS*** subscipconss;
5081 
5082  std::vector<SCIP_Bool> isblockdeleted;
5083  std::vector<int> ndeletedblocksbefore;
5084  std::vector<int> mastervaridsfromdeleted;
5085  std::vector<SCIP_Var*> mastervarsfromdeleted;
5086 
5087  int* nsubscipconss;
5088  int* nsubscipvars;
5089  int* nstairlinkingvars;
5090  int nlinkingvars;
5091  int varcounter = 1; /* in varindex counting starts with 1 */
5092  int conscounter = 1; /* in consindex counting starts with 1 */
5093  int counterstairlinkingvars = 0;
5094  int size;
5095  int modifier;
5096  int nlinkingconss;
5097 
5098  assert( seeed->checkConsistency( ) );
5099  int ndeletedblocks;
5100  int nmastervarsfromdeleted;
5101  ndeletedblocks = 0;
5102  nmastervarsfromdeleted = 0;
5103  isblockdeleted = std::vector<SCIP_Bool>(seeed->getNBlocks(), FALSE);
5104  ndeletedblocksbefore = std::vector<int>(seeed->getNBlocks(), 0);
5105  mastervarsfromdeleted = std::vector<SCIP_VAR*>(0);
5106  mastervaridsfromdeleted = std::vector<int>(0);
5107 
5108  /* create decomp data structure */
5109  SCIP_CALL_ABORT( DECdecompCreate( scip, newdecomp ) );
5110 
5111  /* find out if for some blocks all conss have been deleted */
5112  for( int b = 0; b < seeed->getNBlocks(); ++b )
5113  {
5114  SCIP_Bool iscurblockdeleted = TRUE;
5115  for( int c = 0; c < seeed->getNConssForBlock( b ); ++c )
5116  {
5117  int consid = seeed->getConssForBlock( b )[c];
5118  SCIP_CONS* scipcons = consToScipCons[consid];
5119 
5120  if( scipcons != NULL && !SCIPconsIsDeleted( scipcons) )
5121  {
5122  iscurblockdeleted = FALSE;
5123  break;
5124  }
5125  }
5126  if ( iscurblockdeleted )
5127  {
5128  ++ndeletedblocks;
5129  isblockdeleted[b] = TRUE;
5130  for( int b2 = b+1; b2 < seeed->getNBlocks(); ++b2)
5131  {
5132  ++ndeletedblocksbefore[b2];
5133  }
5135  for( int v = 0; v < seeed->getNVarsForBlock( b ); ++v )
5136  {
5137  int varid = seeed->getVarsForBlock( b )[v];
5138  SCIP_VAR* scipvar = varToScipVar[varid];
5139  mastervaridsfromdeleted.push_back(varid);
5140  mastervarsfromdeleted.push_back(scipvar);
5141  ++nmastervarsfromdeleted;
5142  }
5143  }
5144  }
5145 
5147  DECdecompSetNBlocks( * newdecomp, seeed->getNBlocks() - ndeletedblocks );
5148 
5149  if( seeed->getNBlocks() - ndeletedblocks == 0 )
5150  {
5151  SCIPwarningMessage(scip, "All blocks have been deleted since only deleted constraints are contained, no reformulation is done.\n");
5152  }
5153 
5154  //detectorchaininfo ;
5156  if( seeed->getNMasterconss() != 0 )
5157  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & linkingconss, seeed->getNMasterconss() ) );
5158  else
5159  linkingconss = NULL;
5160 
5161  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & nsubscipconss, seeed->getNBlocks() - ndeletedblocks ) );
5162  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & subscipconss, seeed->getNBlocks() - ndeletedblocks ) );
5163 
5164  SCIP_CALL_ABORT( SCIPhashmapCreate( & constoblock, SCIPblkmem( scip ), seeed->getNConss() ) );
5165  SCIP_CALL_ABORT( SCIPhashmapCreate( & consindex, SCIPblkmem( scip ), seeed->getNConss() ) );
5166 
5167  /* set linking constraints */
5168  modifier = 0;
5169  nlinkingconss = seeed->getNMasterconss();
5170  for( int c = 0; c < seeed->getNMasterconss(); ++c )
5171  {
5172  int consid = seeed->getMasterconss()[c];
5173  SCIP_CONS* scipcons = ( transformed ? consToScipCons[consid] : SCIPconsGetTransformed(consToScipCons[consid]) ) ;
5174  if( SCIPconsIsDeleted( scipcons) || scipcons == NULL || SCIPconsIsObsolete(scipcons))
5175  {
5176  --nlinkingconss;
5177  ++modifier;
5178  }
5179  else
5180  {
5181  linkingconss[c-modifier] = scipcons;
5182  SCIP_CALL_ABORT( SCIPhashmapInsert( constoblock, scipcons, (void*) ( size_t )( seeed->getNBlocks() + 1 - ndeletedblocks ) ) );
5183  SCIP_CALL_ABORT( SCIPhashmapInsert( consindex, scipcons, (void*) (size_t) conscounter ) );
5184  conscounter ++;
5185  }
5186  }
5187 
5188  if( nlinkingconss != 0 )
5189  DECdecompSetLinkingconss( scip, * newdecomp, linkingconss, nlinkingconss );
5190  else
5191  linkingconss = NULL;
5192 
5193 
5194  /* set block constraints */
5195  for( int b = 0; b < seeed->getNBlocks(); ++ b )
5196  {
5197  if( isblockdeleted[b] )
5198  continue;
5199  modifier = 0;
5200  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & subscipconss[b-ndeletedblocksbefore[b]], seeed->getNConssForBlock( b ) ) );
5201  nsubscipconss[b-ndeletedblocksbefore[b]] = seeed->getNConssForBlock( b );
5202  for( int c = 0; c < seeed->getNConssForBlock( b ); ++c )
5203  {
5204  int consid = seeed->getConssForBlock( b )[c];
5205  SCIP_CONS* scipcons = ( transformed ? consToScipCons[consid] : SCIPconsGetTransformed( consToScipCons[consid] ) ) ;
5206 
5207  if( SCIPconsIsDeleted( scipcons) || scipcons == NULL )
5208  {
5209  --nsubscipconss[b-ndeletedblocksbefore[b]];
5210  ++modifier;
5211  }
5212  else
5213  {
5214  assert( scipcons != NULL );
5215  subscipconss[b-ndeletedblocksbefore[b]][c-modifier] = scipcons;
5216  SCIPdebugMessage("Set cons %s to block %d + 1 - %d in cons to block\n", SCIPconsGetName(scipcons), b, ndeletedblocksbefore[b] );
5217  SCIP_CALL_ABORT( SCIPhashmapInsert( constoblock, scipcons, (void*) ( size_t )( b + 1 - ndeletedblocksbefore[b] ) ) );
5218  SCIP_CALL_ABORT( SCIPhashmapInsert( consindex, scipcons, (void*) (size_t) conscounter ) );
5219  conscounter ++;
5220  }
5221  }
5222  }
5223 
5224  DECdecompSetSubscipconss( scip, * newdecomp, subscipconss, nsubscipconss );
5225 
5226  DECdecompSetConstoblock( * newdecomp, constoblock );
5227  DECdecompSetConsindex( * newdecomp, consindex );
5228 
5229  /* finished setting constraint data structures */
5231  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & nsubscipvars, seeed->getNBlocks() - ndeletedblocks ) );
5232  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & subscipvars, seeed->getNBlocks() - ndeletedblocks ) );
5233  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & nstairlinkingvars, seeed->getNBlocks() - ndeletedblocks ) );
5234  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & stairlinkingvars, seeed->getNBlocks() -ndeletedblocks ) );
5235 
5236  SCIP_CALL_ABORT( SCIPhashmapCreate( & vartoblock, SCIPblkmem( scip ), seeed->getNVars() + (int) unpresolvedfixedtozerovars.size() ) );
5237  SCIP_CALL_ABORT( SCIPhashmapCreate( & varindex, SCIPblkmem( scip ), seeed->getNVars() + (int) unpresolvedfixedtozerovars.size()) );
5238 
5240  nlinkingvars = seeed->getNLinkingvars() + seeed->getNMastervars() + seeed->getNTotalStairlinkingvars() + nmastervarsfromdeleted + (int) unpresolvedfixedtozerovars.size();
5241 
5242  if( nlinkingvars != 0 )
5243  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & linkingvars, nlinkingvars ) );
5244  else
5245  linkingvars = NULL;
5246 
5247  for( int v = 0; v < seeed->getNLinkingvars(); ++ v )
5248  {
5249  int var = seeed->getLinkingvars()[v];
5250  SCIP_VAR* scipvar = SCIPvarGetProbvar( varToScipVar[var] );
5251  assert( scipvar != NULL );
5252 
5253  linkingvars[v] = scipvar;
5254  SCIPdebugMessage( "Set var %s to block %d + 2 - %d in var to block\n", SCIPvarGetName(scipvar), seeed->getNBlocks(), ndeletedblocks );
5255  SCIP_CALL_ABORT( SCIPhashmapInsert( vartoblock, scipvar, (void*) ( size_t )( seeed->getNBlocks() + 2 - ndeletedblocks ) ) );
5256  SCIP_CALL_ABORT( SCIPhashmapInsert( varindex, scipvar, (void*) (size_t) varcounter ) );
5257  varcounter ++;
5258  }
5259 
5260  for( int v = 0; v < seeed->getNMastervars(); ++ v )
5261  {
5262  int var = seeed->getMastervars()[v];
5263  SCIP_VAR* scipvar = SCIPvarGetProbvar( varToScipVar[var] );
5264  linkingvars[v + seeed->getNLinkingvars()] = scipvar;
5265  SCIP_CALL_ABORT( SCIPhashmapInsert( vartoblock, scipvar, (void*) ( size_t )( seeed->getNBlocks() + 1 - ndeletedblocks) ) );
5266  SCIP_CALL_ABORT( SCIPhashmapInsert( varindex, scipvar, (void*) (size_t) varcounter ) );
5267  varcounter ++;
5268  }
5269 
5270  for( int v = 0; v < nmastervarsfromdeleted; ++v)
5271  {
5272  SCIP_VAR* var;
5273  var = SCIPvarGetProbvar(mastervarsfromdeleted[v]);
5274 
5275  linkingvars[seeed->getNMastervars() + seeed->getNLinkingvars() + v] = var;
5276  SCIP_CALL_ABORT( SCIPhashmapInsert( vartoblock, var, (void*) ( size_t )( seeed->getNBlocks() + 1 - ndeletedblocks) ) );
5277  SCIP_CALL_ABORT( SCIPhashmapInsert( varindex, var, (void*) (size_t) varcounter ) );
5278  varcounter ++;
5279  }
5280 
5281  for( int v = 0; v < (int) unpresolvedfixedtozerovars.size(); ++v)
5282  {
5283  SCIP_VAR* var;
5284  var = unpresolvedfixedtozerovars[v];
5285 
5286  linkingvars[seeed->getNMastervars() + seeed->getNLinkingvars() + nmastervarsfromdeleted + v] = var;
5287  SCIP_CALL_ABORT( SCIPhashmapInsert( vartoblock, var, (void*) ( size_t )( seeed->getNBlocks() + 1 - ndeletedblocks) ) );
5288  SCIP_CALL_ABORT( SCIPhashmapInsert( varindex, var, (void*) (size_t) varcounter ) );
5289  varcounter ++;
5290  }
5291 
5292 
5293  /* set block variables */
5294  for( int b = 0; b < seeed->getNBlocks(); ++ b )
5295  {
5296  if( isblockdeleted[b] )
5297  continue;
5298 
5299  if( seeed->getNVarsForBlock( b ) > 0 )
5300  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & subscipvars[b -ndeletedblocksbefore[b]], seeed->getNVarsForBlock( b ) ) );
5301  else
5302  subscipvars[b-ndeletedblocksbefore[b]] = NULL;
5303 
5304  if( seeed->getNStairlinkingvars( b ) > 0 )
5305  SCIP_CALL_ABORT( SCIPallocBufferArray( scip, & stairlinkingvars[b-ndeletedblocksbefore[b]], seeed->getNStairlinkingvars( b ) ) );
5306  else
5307  stairlinkingvars[b-ndeletedblocksbefore[b]] = NULL;
5308 
5309  nsubscipvars[b-ndeletedblocksbefore[b]] = seeed->getNVarsForBlock( b );
5310  nstairlinkingvars[b-ndeletedblocksbefore[b]] = seeed->getNStairlinkingvars( b );
5311 
5312  for( int v = 0; v < seeed->getNVarsForBlock( b ); ++ v )
5313  {
5314  int var = seeed->getVarsForBlock( b )[v];
5315  SCIP_VAR* scipvar = SCIPvarGetProbvar( varToScipVar[var] );
5316  assert( scipvar != NULL );
5317 
5318  subscipvars[b-ndeletedblocksbefore[b]][v] = scipvar;
5319  SCIPdebugMessage("Set var %s to block %d + 1 - %d in var to block\n", SCIPvarGetName(scipvar), b, ndeletedblocksbefore[b] );
5320  assert( !SCIPhashmapExists(vartoblock, scipvar) || SCIPhashmapGetImage(vartoblock, scipvar) == (void*) ( size_t )( b + 1 - ndeletedblocksbefore[b] ) );
5321  SCIP_CALL_ABORT( SCIPhashmapInsert( vartoblock, scipvar, (void*) ( size_t )( b + 1 - ndeletedblocksbefore[b] ) ) );
5322  SCIP_CALL_ABORT( SCIPhashmapInsert( varindex, scipvar, (void*) (size_t) varcounter ) );
5323  varcounter ++;
5324  }
5325 
5326  for( int v = 0; v < seeed->getNStairlinkingvars( b ); ++ v )
5327  {
5328  int var = seeed->getStairlinkingvars( b )[v];
5329  SCIP_VAR* scipvar = SCIPvarGetProbvar( varToScipVar[var] );
5330  assert( scipvar != NULL );
5331 
5332  stairlinkingvars[b-ndeletedblocksbefore[b]][v] = scipvar;
5333  linkingvars[seeed->getNLinkingvars() + seeed->getNMastervars() + nmastervarsfromdeleted + counterstairlinkingvars] = scipvar;
5334  SCIP_CALL_ABORT( SCIPhashmapInsert( vartoblock, scipvar, (void*) ( size_t )( seeed->getNBlocks() + 2 - ndeletedblocks) ) );
5335  SCIP_CALL_ABORT( SCIPhashmapInsert( varindex, scipvar, (void*) (size_t) varcounter ) );
5336  varcounter ++;
5337  counterstairlinkingvars ++;
5338  }
5339  }
5340 
5341  DECdecompSetSubscipvars( scip, * newdecomp, subscipvars, nsubscipvars );
5342  DECdecompSetStairlinkingvars( scip, * newdecomp, stairlinkingvars, nstairlinkingvars );
5343  DECdecompSetLinkingvars( scip, * newdecomp, linkingvars, nlinkingvars, (int) unpresolvedfixedtozerovars.size(), seeed->getNMastervars() + nmastervarsfromdeleted );
5344  DECdecompSetVarindex( * newdecomp, varindex );
5345  DECdecompSetVartoblock( * newdecomp, vartoblock );
5346 
5351  SCIPfreeBufferArrayNull( scip, & ( linkingvars ) );
5352  for( int b = seeed->getNBlocks() - 1 - ndeletedblocks; b >= 0; --b )
5353  {
5354  if( nstairlinkingvars[b] != 0 )
5355  {
5356  SCIPfreeBufferArrayNull( scip, & ( stairlinkingvars[b] ) );
5357  }
5358  }
5359 
5360 
5361  SCIPfreeBufferArrayNull( scip, & ( stairlinkingvars ) );
5362  SCIPfreeBufferArrayNull( scip, & ( nstairlinkingvars ) );
5363 
5364  for( int b = seeed->getNBlocks() - 1 - ndeletedblocks; b >= 0; --b )
5365  {
5366  if( nsubscipvars[b] != 0 )
5367  {
5368  SCIPfreeBufferArrayNull( scip, & ( subscipvars[b] ) );
5369  }
5370  }
5371 
5372  SCIPfreeBufferArrayNull( scip, & ( subscipvars ) );
5373  SCIPfreeBufferArrayNull( scip, & ( nsubscipvars ) );
5374 
5375 
5377  for( int b = seeed->getNBlocks() - 1 - ndeletedblocks; b >= 0; --b )
5378  {
5379  SCIPfreeBufferArrayNull( scip, & ( subscipconss[b] ) );
5380  }
5381  SCIPfreeBufferArrayNull( scip, & ( subscipconss ) );
5382 
5383 
5384  SCIPfreeBufferArrayNull( scip, & nsubscipconss );
5385  SCIPfreeBufferArrayNull( scip, & linkingconss );
5386 
5387 
5389  int ndetectors = seeed->getNDetectors();
5390  ( * newdecomp )->sizedetectorchain = ndetectors;
5391  size = SCIPcalcMemGrowSize( scip, ( * newdecomp )->sizedetectorchain );
5392  SCIP_CALL_ABORT( SCIPallocBlockMemoryArray( scip, & ( * newdecomp )->detectorchain, size ) );
5393  for( int k = 0; k < ndetectors; ++ k )
5394  {
5395  if( k != ndetectors - 1 || ! seeed->getFinishedByFinisher() )
5396  {
5397  // std::cout << " added detector of " << i << "-th seeed to its detetcor chain" << std::endl;
5398  ( * newdecomp )->detectorchain[k] = seeed->getDetectorchain()[k];
5399  }
5400  else
5401  ( * newdecomp )->detectorchain[k] = seeed->getDetectorchain()[k];
5402  }
5403 
5405  DECdecompSetSeeedID( * newdecomp, seeed->getID() );
5406  if( seeed->getNDetectors() > 0 )
5407  {
5408  DECdecompSetDetectorClockTimes( scip, * newdecomp, & ( seeed->getDetectorClockTimes()[0] ) );
5409  DECdecompSetDetectorPctVarsToBorder( scip, * newdecomp, & ( seeed->getPctVarsToBorderVector()[0] ) );
5410  DECdecompSetDetectorPctVarsToBlock( scip, * newdecomp, & ( seeed->getPctVarsToBlockVector()[0] ) );
5411  DECdecompSetDetectorPctVarsFromOpen( scip, * newdecomp, & ( seeed->getPctVarsFromFreeVector()[0] ) );
5412  DECdecompSetDetectorPctConssToBorder( scip, * newdecomp, & ( seeed->getPctConssToBorderVector()[0] ) );
5413  DECdecompSetDetectorPctConssToBlock( scip, * newdecomp, & ( seeed->getPctConssToBlockVector()[0] ) );
5414  DECdecompSetDetectorPctConssFromOpen( scip, * newdecomp, & ( seeed->getPctConssFromFreeVector()[0] ) );
5415  DECdecompSetNNewBlocks( scip, * newdecomp, & ( seeed->getNNewBlocksVector()[0] ) );
5416  }
5417 
5418 
5420  SCIPsnprintf( detectorchaininfo, SCIP_MAXSTRLEN, "") ;
5422  {
5423  seeed->buildDecChainString();
5424  }
5425  SCIP_CALL( DECdecompSetDetectorChainString( scip, * newdecomp, seeed->getDetectorChainString() ) );
5426 
5428  if( ( * newdecomp )->nlinkingvars == seeed->getNTotalStairlinkingvars() && ( * newdecomp )->nlinkingconss == 0
5429  && DECdecompGetNLinkingvars( * newdecomp ) > 0 )
5430  {
5431  ( * newdecomp )->type = DEC_DECTYPE_STAIRCASE;
5432  }
5433  else if( ( * newdecomp )->nlinkingvars > 0 || seeed->getNTotalStairlinkingvars() > 0 )
5434  {
5435  ( * newdecomp )->type = DEC_DECTYPE_ARROWHEAD;
5436  }
5437  else if( ( * newdecomp )->nlinkingconss > 0 )
5438  {
5439  ( * newdecomp )->type = DEC_DECTYPE_BORDERED;
5440  }
5441  else if( ( * newdecomp )->nlinkingconss == 0 && seeed->getNTotalStairlinkingvars() == 0 )
5442  {
5443  ( * newdecomp )->type = DEC_DECTYPE_DIAGONAL;
5444  }
5445  else
5446  {
5447  ( * newdecomp )->type = DEC_DECTYPE_UNKNOWN;
5448  }
5449 
5450 
5451  SCIPdebugMessage(" seeed maxwhitescore: %f\n", seeed->getMaxWhiteScore());
5452 
5453  DECsetMaxWhiteScore(scip, *newdecomp, seeed->getMaxWhiteScore() );
5454 
5455  if( transformed )
5456  SCIP_CALL(DECdecompAddRemainingConss(scip, *newdecomp) );
5457 
5458 
5459 
5460  assert(DECdecompCheckConsistency(scip, *newdecomp) );
5462  assert( ! SCIPhashmapIsEmpty( ( * newdecomp )->constoblock ) );
5463  assert( ! SCIPhashmapIsEmpty( ( * newdecomp )->vartoblock ) );
5464 
5465  return SCIP_OKAY;
5466 }
5467 
5473  DEC_DECOMP* decomp,
5474  SeeedPtr* newseeed
5475  )
5476 {
5477  assert( decomp != NULL );
5478  assert( DECdecompCheckConsistency( scip, decomp ) );
5479  assert( nConss == DECdecompGetNConss( decomp ) );
5480  assert( DECdecompGetPresolved( decomp ) );
5481  assert( transformed );
5482 
5483 // std::cout << "Linkingvars decomp: " << DECdecompGetNLinkingvars( decomp ) << "\tStairlinkingvars decomp: " << DECdecompGetNTotalStairlinkingvars( decomp ) << "\n";
5484 
5485  /* create new seeed and initialize its data */
5486  SeeedPtr seeed = new Seeed( scip, getNewIdForSeeed(), this );
5487  seeed->setNBlocks( DECdecompGetNBlocks( decomp ) );
5488 
5489  assert( seeed->getNOpenconss() == nConss );
5490  assert( seeed->getNOpenvars() == nVars );
5491 
5492  SCIP_CONS** linkingconss = DECdecompGetLinkingconss( decomp );
5493  int nlinkingconss = DECdecompGetNLinkingconss( decomp );
5494  SCIP_HASHMAP* constoblock = DECdecompGetConstoblock( decomp );
5495  int nblock;
5496 
5497  /* set linking conss */
5498  for( int c = 0; c < nlinkingconss; ++c )
5499  {
5500  seeed->bookAsMasterCons( getIndexForCons( linkingconss[c] ) );
5501  }
5502 
5503  /* set block conss */
5504  for( int c = 0; c < nConss; ++c )
5505  {
5506  nblock = (int) (size_t) SCIPhashmapGetImage( constoblock, (void*) (size_t) getConsForIndex( c ) );
5507  if( nblock >= 1 && nblock <= seeed->getNBlocks() )
5508  {
5509  seeed->bookAsBlockCons( c, nblock - 1 );
5510  }
5511  }
5512 
5513  SCIP_VAR*** stairlinkingvars = DECdecompGetStairlinkingvars( decomp );
5514  SCIP_HASHMAP* vartoblock = DECdecompGetVartoblock(decomp);
5515  assert( vartoblock != NULL );
5516 
5517  /* currently, stairlinkingvars of the decomposition are ignored
5518  * alternatively, a stairlinkingvar detection is done with the newly created seeed */
5519  if( false && stairlinkingvars != NULL )
5520  {
5521  int* nstairlinkingvars = DECdecompGetNStairlinkingvars(decomp);
5522  int varindex;
5523 
5524  /* set stairlinkingvars */
5525  for( int b = 0; b < seeed->getNBlocks(); ++b )
5526  {
5527  for( int v = 0; v < nstairlinkingvars[b]; ++v )
5528  {
5529  if( stairlinkingvars[b][v] != NULL )
5530  {
5531  varindex = getIndexForVar(stairlinkingvars[b][v]);
5532  seeed->bookAsStairlinkingVar(varindex, b);
5533  }
5534  }
5535  }
5536  }
5537 
5538  /* flush booked conss and vars in order to be able to check whether a var is already assigned to stairlinking */
5539  seeed->flushBooked();
5540 
5541  /* set other vars */
5542  for( int v = 0; v < getNVars(); ++v )
5543  {
5544  nblock = (int) (size_t) SCIPhashmapGetImage( vartoblock, (void*) (size_t) SCIPvarGetProbvar( getVarForIndex( v ) ) );
5545  if( nblock == seeed->getNBlocks() + 2 && !seeed->isVarStairlinkingvar( v ) )
5546  {
5547  seeed->bookAsLinkingVar( v );
5548  }
5549  else if( nblock == seeed->getNBlocks() + 1 )
5550  {
5551  seeed->bookAsMasterVar( v );
5552  }
5553  else if( nblock >= 1 && nblock <= seeed->getNBlocks() )
5554  {
5555  seeed->bookAsBlockVar( v, nblock - 1 );
5556  }
5557  }
5558 
5559  seeed->flushBooked();
5560 
5561  /* now all conss and vars should be assigned */
5562  assert( seeed->isComplete() );
5563  /*set all detector-related information*/
5564  for( int i = 0; i < DECdecompGetDetectorChainSize( decomp ); ++i )
5565  {
5566  seeed->setDetectorPropagated( DECdecompGetDetectorChain( decomp )[i] );
5567  seeed->addClockTime( DECdecompGetDetectorClockTimes( decomp )[i] );
5568  seeed->addPctConssFromFree( 1 - *(DECdecompGetDetectorPctConssFromOpen( decomp )) );
5571  seeed->addPctVarsFromFree( 1 - *(DECdecompGetDetectorPctVarsFromOpen( decomp )) );
5574  seeed->addNNewBlocks( *(DECdecompGetNNewBlocks( decomp )) );
5575  }
5576 
5577  if ( DECdecompGetDetectorChainString( scip, decomp ) != NULL )
5579  else
5580  {
5581  char decchaininfo[SCIP_MAXSTRLEN];
5582  char str1[2] = "\0"; /* gives {\0, \0} */
5583  str1[0] = 'U';
5584  (void) strncat( decchaininfo, str1, 1 );
5585  seeed->setDetectorChainString( decchaininfo );
5586  }
5587 
5588  /* detectorchaininfo cannot be set in the seeed as the detectors do not store the corresponding strings */
5589 
5590  /* calc maxwhitescore and hashvalue */
5591  prepareSeeed( seeed );
5592 
5593  seeed->setIsFromUnpresolved( false );
5594 
5595 
5596  assert( seeed->checkConsistency( ) );
5597 
5598  seeed->calcStairlinkingVars( );
5599 
5600 // SCIPdebugMessagePrint( scip, "Reassigned %d of %d linking vars to stairlinking.\n",
5601 
5602  *newseeed = seeed;
5603 
5604  return SCIP_OKAY;
5605 }
5606 
5609 {
5610  return transformed;
5611 }
5612 
5614  SCIP* givenscip,
5615  FILE* file
5616 )
5617 {
5618 
5619  std::sort( candidatesNBlocks.begin(), candidatesNBlocks.end(), sort_decr() );
5620  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "NBLOCKCANDIDATES \n" );
5621  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "The following %d candidates for the number of blocks are known: (candidate : number of votes) \n", (int) candidatesNBlocks.size() );
5622  for( size_t i = 0; i < candidatesNBlocks.size(); ++i )
5623  {
5624  if( candidatesNBlocks[i].second != INT_MAX )
5625  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%d : %d \n", candidatesNBlocks[i].first, candidatesNBlocks[i].second );
5626  else
5627  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%d : %s \n", candidatesNBlocks[i].first, "user given" );
5628  }
5629 
5630  return SCIP_OKAY;
5631 }
5632 
5634  SCIP* givenscip,
5635  FILE* file
5636 )
5637 {
5638 
5640  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "CONSCLASSIFIER \n" );
5641  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%d \n", (int) consclassescollection.size() );
5642 
5643  for( size_t c = 0; c < consclassescollection.size() ; ++c )
5644  {
5645  gcg::ConsClassifier* classifier = consclassescollection[c];
5646 
5647  std::vector<std::vector<int> > conssofclasses = std::vector<std::vector<int> >(classifier->getNClasses()) ;
5648  for( int cons = 0; cons < getNConss(); ++cons )
5649  conssofclasses[classifier->getClassOfCons(cons)].push_back(cons);
5650 
5652  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%s \n", classifier->getName() );
5653 
5654 
5656  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%d \n", classifier->getNClasses() );
5657 
5658  for( int cl = 0; cl < classifier->getNClasses(); ++cl )
5659  {
5661  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%s: %s\n", classifier->getClassName(cl), classifier->getClassDescription(cl) );
5663  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%d\n", conssofclasses[cl].size() );
5664  }
5665  }
5666 
5668  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "VARCLASSIFIER \n" );
5669  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%d \n", (int) varclassescollection.size() );
5670 
5671  for( size_t c = 0; c < varclassescollection.size() ; ++c )
5672  {
5673  gcg::VarClassifier* classifier = varclassescollection[c];
5674 
5675  std::vector<std::vector<int> > varsofclasses = std::vector<std::vector<int> >(classifier->getNClasses()) ;
5676  for( int var = 0; var < getNVars(); ++var )
5677  varsofclasses[classifier->getClassOfVar(var)].push_back(var);
5678 
5680  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%s \n", classifier->getName() );
5681 
5682 
5684  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%d \n", classifier->getNClasses() );
5685 
5686  for( int cl = 0; cl < classifier->getNClasses(); ++cl )
5687  {
5689  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%s: %s\n", classifier->getClassName(cl), classifier->getClassDescription(cl) );
5691  SCIPmessageFPrintInfo(SCIPgetMessagehdlr(givenscip), file, "%d\n", varsofclasses[cl].size() );
5692  }
5693  }
5694 
5695 
5696  return SCIP_OKAY;
5697 }
5698 
5699 
5700 
5701 
5702 } /* namespace gcg */
SCIP_RETCODE considerImplicits()
: assigns every open cons/var in the following manner:
void calcStairlinkingVars()
reassigns linking vars to stairlinkingvars if possible potentially reorders blocks for making a maxim...
void addSeeedToIncomplete(SeeedPtr seeed, SCIP_Bool *success)
adds a seeed to incomplete seeeds
void sortFinishedForScore()
sorts seeeds in finished seeeds data structure according to the scoretype that is currently used ...
void setFinishedByFinisher(bool finished)
sets whether this seeed was finished by a finishing detector
void clearIncompleteSeeeds()
clears incomplete seeed data structure
SCIP_Real getDualvalOptimalLP(int consindex)
returns the value of the optimal lp relaxation dual value of the given constrainr rid correspondoning...
void addDecChangesFromAncestor(Seeed *ancestor)
incorporates the changes from ancestor seeed into the statistical data structures ...
SCIP_RETCODE buildDecChainString()
creates and sets a detector chain short string for this seeed, is built from detector chain ...
SCIP_Real translatingtime
ConsClassifier * getConsClassifier(int classifierIndex)
returns pointer to a constraint classifier
SCIP_RETCODE calcClassifierAndNBlockCandidates(SCIP *givenScip)
creates constraint and variable classifiers, and deduces block number candidates
SCIP_Constype_orig
gcg::Seeedpool * seeedpool
struct DEC_Detector DEC_DETECTOR
Definition: type_detector.h:46
void DECdecompSetDetectorPctConssToBorder(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctConssToBorder)
Definition: decomp.c:1739
std::vector< int > getSortedCandidatesNBlocks()
returns the candidates for number of blocks added by the user followed by the found ones sorted in de...
void setClassName(int classindex, const char *name)
SeeedPtr getFinishedSeeed(int seeedindex)
returns a seeed from finished seeed data structure
int getNVarsForCons(int consIndex)
returns the number of variables for a given constraint
SCIP_Bool isForBenders()
returns whether or not this seeedpool is for detectiong decompositions for benders ...
int * DECdecompGetNStairlinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1157
SCIP_RETCODE prepareSeeed(SeeedPtr seeed)
registers a seeed for a seeedpool, sets it up by and calculates its hash value
void reduceVarclasses()
adds variable classifiers with a reduced number of classes this is done by greedliy merge two smalles...
SeeedPtr getCurrentSeeed(int seeedindex)
char * DECdecompGetDetectorChainString(SCIP *scip, DEC_DECOMP *decomp)
Definition: decomp.c:1693
SCIP_Real getPctVarsToBorder(int detectorchainindex)
returns fraction of variables assigned to the border for a detector
ConsClassifier * createConsClassifierForSCIPConstypes()
returns a new constraint classifier where all constraints with identical SCIP constype are assigned t...
int getNDetectors()
returns the number of propagating detectors used in the seeedpool
SCIP_RETCODE DECdecompSetLinkingvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR **linkingvars, int nlinkingvars, int nfixedlinkingvars, int nmastervars)
Definition: decomp.c:984
int getClassOfCons(int consindex)
int getNNewBlocks(int detectorchainindex)
returns number of blocks a detector added
ConsClassifier * createConsClassifierForConsnamesLevenshteinDistanceConnectivity(int connectivity)
returns a new constraint classifier where all constraints whose consnames do not a have levenshtein d...
SCIP_RETCODE DECdecompSetStairlinkingvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR ***stairlinkingvars, int *nstairlinkingvars)
Definition: decomp.c:1078
void addVarClassifier(VarClassifier *classifier)
adds a variable classifier if it is no duplicate of an existing variable classifier ...
GCG interface methods.
void addCandidatesNBlocks(int candidate)
adds and counts how often added a candidate for block size and
SCIP_RETCODE bookAsBlockVar(int varToBlock, int block)
books a variable to be added to the block constraints of the given block (by calling flushBooked all ...
void sort()
sorts the vars and conss datat structures by their indices
Seeedpool(SCIP *scip, const char *conshdlrName, SCIP_Bool transformed, SCIP_Bool benders)
constructor
SeeedPtr getAncestorSeeed(int seeedindex)
returns a seeed from ancestor seeed data structure with given index
SCIP_Real * DECdecompGetDetectorPctVarsToBorder(DEC_DECOMP *decomp)
Definition: decomp.c:1731
void DECdecompSetVarindex(DEC_DECOMP *decomp, SCIP_HASHMAP *varindex)
Definition: decomp.c:1228
void translateSeeeds(Seeedpool *otherpool, std::vector< Seeed * > otherseeeds, std::vector< Seeed * > &newseeeds)
translates seeeds if the index structure of the problem has changed, e.g. due to presolving ...
int getNConssForBlock(int block)
returns size of the vector containing conss assigned to a block
bool getFinishedByFinisher()
returns true iff this seeed was finished by finishSeeed() method of a detector
void DECdecompSetDetectorPctVarsToBlock(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctVarsToBlock)
Definition: decomp.c:1774
int DECdecompGetDetectorChainSize(DEC_DECOMP *decomp)
Definition: decomp.c:1609
SCIP_Real * DECdecompGetDetectorClockTimes(DEC_DECOMP *decomp)
Definition: decomp.c:1670
SCIP_Real * DECdecompGetDetectorPctConssFromOpen(DEC_DECOMP *decomp)
Definition: decomp.c:1911
std::vector< DEC_DETECTOR * > getDetectorchainVector()
returns the detectorchain as a vector of detector pointers
ConsClassifier * createConsClassifierForConsnamesDigitFreeIdentical()
returns a new constraint classifier where all constraints with identical consname (ignoring digits) a...
SCIP_HASHMAP * DECdecompGetVartoblock(DEC_DECOMP *decomp)
Definition: decomp.c:1196
SCIP_RETCODE setFinishingDetectorPropagated(DEC_DETECTOR *detector)
sets seeed to be finished by a detector
int getNLinkingvars()
returns size of the vector containing linking vars
SCIP_RETCODE printBlockcandidateInformation(SCIP *scip, FILE *file)
output method for json file writer to write block candidate information
const int * getMasterconss()
SCIP_Real getPctConssToBlock(int detectorchainindex)
returns fraction of constraints assigned to a block for a detector
std::vector< SCIP_Real > getPctVarsToBorderVector()
returns fraction of variables assigned to the border for detectors in detectorchain ...
static SCIP_RETCODE createTestPricingprobConss(SCIP *scip, SCIP *subscip, Seeedpool *seeedpool, SeeedPtr seeed, int block, SCIP_HASHMAP *hashorig2pricingvar)
int getNVars()
returns number of vars
SCIP_Real nblockscandidatescalctime
bool operator()(const std::pair< int, int > &left, const std::pair< int, int > &right)
SCIP_Bool isSeeedDuplicateofIncomplete(SeeedPtr seeed)
check if seeed is a duplicate of an existing incomplete seeed
void addPctConssToBorder(SCIP_Real pct)
bookkeeping information: adds fraction of constraints assigned to the border for a detector added to ...
SCIP_Real classificationtime
SCIP_Bool GCGgetConsIsCardinalityCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:848
const SCIP_Real * getValsForCons(int consIndex)
returns the nonzero coefficients of the coefficient matrix for a constraint
int getNewIdForSeeed()
returns a new unique id for a new seeed
int gcd(int a, int b)
const char * getClassName(int classindex)
int SCIPconshdlrDecompGetNextSeeedID(SCIP *scip)
int getNConss()
returns the number of constraints
int * getVarClassifierArray(int classifierIndex)
returns the assignment of variables to classes of a classifier as integer array
int SCIPconshdlrDecompGetBlockNumberCandidate(SCIP *scip, int index)
returns block number user candidate with given index
VarClassifier * createVarClassifierForSCIPVartypes()
returns a new variable classifier where all variables with identical SCIP vartype are assigned to the...
void translateSeeedData(Seeedpool *otherpool, std::vector< Seeed * > otherseeeds, std::vector< Seeed * > &newseeeds, std::vector< ConsClassifier * > otherconsclassifiers, std::vector< ConsClassifier * > &newconsclassifiers, std::vector< VarClassifier * > othervarclassifiers, std::vector< VarClassifier * > &newvarclassifiers)
translates seeeds and classifiers if the index structure of the problem has changed, e.g. due to presolving
SCIP_Bool finishNextChild(std::vector< int > &childs, std::vector< SCIP_Bool > &childsfinished, int child)
void addSeeedToFinishedUnchecked(SeeedPtr seeed)
adds a seeed to finished seeeds without checking for duplicates, dev has to check this on his own ...
SCIP_Real * DECdecompGetDetectorPctConssToBlock(DEC_DECOMP *decomp)
Definition: decomp.c:1837
SCIP_Bool getTransformedInfo()
returns true if the matrix structure corresponds to the transformed problem
SCIP_Bool unfinishedChildExists(std::vector< SCIP_Bool > const &childsfinished)
STL namespace.
DEC_DETECTOR ** SCIPconshdlrDecompGetDetectors(SCIP *scip)
void reduceConsclasses()
adds constraint classifiers with a reduced number of classes
int GCGconsGetNVars(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:433
SCIP_Real * DECdecompGetDetectorPctVarsToBlock(DEC_DECOMP *decomp)
Definition: decomp.c:1801
SCIP_VAR *** DECdecompGetStairlinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1148
VarClassifier * createVarClassifierForObjValueSigns()
returns a new variable classifier where all variables are assigned to class zero, positive or negativ...
void addUserCandidatesNBlocks(int candidate)
adds a candidate for block size given by the user
bool isVarStairlinkingvar(int var)
returns true if the var is a stairlinking var
Definition: scip_misc.h:49
int getNUserCandidatesNBlocks()
returns number of user-given block size candidates
SCIP_Real getPctConssFromFree(int detectorchainindex)
returns fraction of constraints that are not longer open for a detector
void DECdecompSetNNewBlocks(SCIP *scip, DEC_DECOMP *decomp, int *nNewBlocks)
Definition: decomp.c:1919
int getNConssForVar(int varIndex)
Definition: scip_misc.h:49
int getNOpenvars()
returns size of vector containing variables not assigned yet
USERGIVEN getUsergiven()
returns the USERGIVEN status of this seeeds
SCIP_RETCODE getDetectorCallRoundInfo(SCIP *scip, const char *detectorname, SCIP_Bool transformed, int *maxcallround, int *mincallround, int *freqcallround)
int DECdecompGetNConss(DEC_DECOMP *decomp)
Definition: decomp.c:3623
void setSeeedpool(Seeedpool *seeedpool)
set the corresponding seeedpool of this seeeds
void sortAllRelevantSeeeds()
sorts seeeds in allrelevantseeeds data structure by ascending id
bool isConsSetpp(int consindexd)
is cons with specified indec partitioning, or packing covering constraint?
SCIP_VAR * getVarForIndex(int varIndex)
returns SCIP variable related to a variable index
int getNAncestorSeeeds()
returns size of ancestor seeed data structure
int DECdecompGetNLinkingvars(DEC_DECOMP *decomp)
Definition: decomp.c:1043
consType GCGconsGetType(SCIP_CONS *cons)
Definition: scip_misc.c:51
void setClassDecompInfo(int classindex, VAR_DECOMPINFO decompInfo)
void DECdecompSetNBlocks(DEC_DECOMP *decomp, int nblocks)
Definition: decomp.c:728
consType
Definition: scip_misc.h:47
int getNTotalStairlinkingvars()
returns total number of stairlinking vars
SCIP_Bool cmpSeeedsPPCfWhite(SeeedPtr i, SeeedPtr j)
void DECdecompSetDetectorPctConssFromOpen(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctConssFromOpen)
Definition: decomp.c:1882
int getFirstUnfinishedChild(std::vector< SCIP_Bool > const &childsfinished, std::vector< int > const &childs)
void addSeeedToCurr(SeeedPtr seeed)
adds a seeed to current seeeds (data structure for seeeds that are goin to processed in the propagati...
DEC_DETECTOR * getPostprocessingDetectorForIndex(int detectorIndex)
returns the detector related to a finishing detector index
bool classifierIsDuplicateOfClassifier(IndexClassifier *otherClassifier)
const int * getLinkingvars()
returns array containing all linking vars indices
SCIP_Bool cmpSeeedsBorderArea(SeeedPtr i, SeeedPtr j)
const int * getVarsForBlock(int block)
returns array containing vars of a block
void clearAncestorSeeeds()
clears ancestor seeed data structure,
int getNConss()
returns the number of variables considered in the seeedpool
SCIP_RETCODE createDecompFromSeeed(SeeedPtr seeed, DEC_DECOMP **newdecomp)
creates a decomposition DEC_DECOMP structure for a given seeed
SCIP_RETCODE setNBlocks(int nBlocks)
sets number of blocks, only increasing number allowed
DEC_DETECTOR ** getDetectorchain()
returns detector chain as array of detector pointers
DEC_DETECTOR * getDetectorForIndex(int detectorIndex)
returns the detector related to a detector index
void DECdecompSetVartoblock(DEC_DECOMP *decomp, SCIP_HASHMAP *vartoblock)
Definition: decomp.c:1184
int DECdecompGetNLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:972
struct Seeed_Propagation_Data SEEED_PROPAGATION_DATA
Definition: type_detector.h:51
void createConssAdjacency()
create the constraint adjacency datastructure that is used (if created) for some methods to faster ac...
SCIP_RETCODE GCGconsGetVals(SCIP *scip, SCIP_CONS *cons, SCIP_Real *vals, int nvals)
Definition: scip_misc.c:620
bool operator()(const std::pair< int, int > &left, const std::pair< int, int > &right)
static SCIP_Bool isRangedRow(SCIP *scip, SCIP_Real lhs, SCIP_Real rhs)
SCIP_RETCODE flushBooked()
assigns all booked constraints and variables and deletes them from list of open cons and open vars ...
int getClassOfVar(int varindex)
int DECdecompGetNBlocks(DEC_DECOMP *decomp)
Definition: decomp.c:740
void addPctVarsToBorder(SCIP_Real pct)
bookkeeping information: adds fraction of variables assigned to the border for a detector added to de...
std::vector< SeeedPtr > findSeeeds()
constructs seeeds using the registered detectors
SCIP_Bool areThereContinuousVars()
checks if there are continouos variables
std::vector< VarClassifier * > varclassescollection
DEC_DETECTOR * getFinishingDetectorForIndex(int detectorIndex)
returns the detector related to a finishing detector index
std::vector< std::pair< int, int > > getSortedCandidatesNBlocksFull()
returns (candidate-nvotes) pair for candidates for number of blocks added by the user followed by the...
void findDecompositions()
calls findSeeeds method and sort the finished decompositions by score
void assignConsToClass(int consindex, int classindex)
SCIP_VAR * getScipVar(int varid)
returns scip var for corresponding id
void setIsFromUnpresolved(bool unpresolved)
sets whether this seeed is from the unpresolved problem
VarClassifier * createVarClassifierForObjValues()
returns a new variable classifier where all variables with identical objective function value are ass...
CONS_DECOMPINFO getClassDecompInfo(int classindex)
various SCIP helper methods
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
void initOnlyBinMaster()
prepare the seeed such that all predecessors have the folloing property: all variables in the master ...
void addPctVarsToBlock(SCIP_Real pct)
bookkeeping information: adds fraction of variables assigned to a block for a detector added to detec...
void addSeeedToAncestor(SeeedPtr seeed)
adds a seeed to ancestor seeeds
int getIndexForFinishingDetector(DEC_DETECTOR *detector)
returns the finishing detector index related to a detector
DEC_DETECTOR ** DECdecompGetDetectorChain(DEC_DECOMP *decomp)
Definition: decomp.c:1599
SCIP_CONS * consGetRelevantRepr(SCIP *scip, SCIP_CONS *cons)
gcg::Seeed * seeedToPropagate
SCIP_Real getScore(SCORETYPE type)
returns the score of the seeed (depending on used scoretype)
std::vector< ConsClassifier * > consclassescollection
SCIP_RETCODE setDetectorPropagated(DEC_DETECTOR *detector)
sets seeed to be propagated by a detector
SCIP_RETCODE setDetectorChainString(char *detectorchainstring)
sets the detector chain short string
int getNFinishingDetectors()
returns the number of finishing detectors used in the seeedpool
VarClassifier * getVarClassifier(int classifierIndex)
returns pointer to a variable classifier with given index
std::vector< SCIP_Real > getPctConssToBorderVector()
returns fraction of constraints assigned to the border for detectors in detectorchain ...
SCIP_Real postprocessingtime
int getNConssForCons(int consIndex)
returns the number of constraints for a given constraint
const int * getConssForVar(int varIndex)
returns the constraint indices of the coefficient matrix for a variable
bool hasDuplicate(SeeedPtr seeed)
returns true if the given seeed is a duplicate of a seeed that is already contained in finished seeed...
int getNNonzeros()
returns the number of nonzero entries in the coefficient matrix
int getID()
returns the unique id of the seeed
combine two hash function of objects of a pair to get a vaulue for the pair
void addPctVarsFromFree(SCIP_Real pct)
bookkeeping information: adds fraction of variables that are not longer open for a detector added to ...
static SCIP_Bool isFiniteNonnegativeIntegral(SCIP *scip, SCIP_Real x)
bool isTrivial()
returns true if this seeed is considered to be trivial, i.e. all conss are in one block...
SCIP_RETCODE DECdecompCreate(SCIP *scip, DEC_DECOMP **decdecomp)
Definition: decomp.c:467
VAR_DECOMPINFO getClassDecompInfo(int classindex)
SCIP_RETCODE isEqual(Seeed *otherseeed, SCIP_Bool *isequal, bool sortseeeds)
method to check whether this seeed is equal to a given other seeed (
SCIP_CONS ** DECdecompGetLinkingconss(DEC_DECOMP *decomp)
Definition: decomp.c:962
SCIP_RETCODE GCGconsGetVars(SCIP *scip, SCIP_CONS *cons, SCIP_VAR **vars, int nvars)
Definition: scip_misc.c:489
SCIP_Bool cmpSeeedsFWhite(SeeedPtr i, SeeedPtr j)
SCIP_RETCODE calcStrongDecompositionScore(SeeedPtr seeed, SCIP_Real *score)
calculates the strong decomposition score of a seeed
long getNTotalNonzeros()
returns the number of nonzero entries in the coefficient matrix
private methods for working with decomp structures
SCIP_Real getPctConssToBorder(int detectorchainindex)
returns fraction of constraints assigned to the border for a detector
bool isComplete()
returns true if this seeed is complete, i.e. it has no more open constraints and variables ...
SCIP_RETCODE DECdecompSetDetectorChainString(SCIP *scip, DEC_DECOMP *decomp, char *detectorchainstring)
Definition: decomp.c:1679
int * DECdecompGetNNewBlocks(DEC_DECOMP *decomp)
Definition: decomp.c:1945
SCIP_RETCODE deleteEmptyBlocks(bool variables)
deletes empty blocks and sets nblocks accordingly, a block is considered to be empty if no constraint...
void DECdecompSetDetectorPctConssToBlock(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctConssToBlock)
Definition: decomp.c:1809
const char * getClassDescription(int classindex)
SCIP_RETCODE createSeeedFromDecomp(DEC_DECOMP *decomp, SeeedPtr *newseeed)
int getIndexForCons(SCIP_CONS *cons)
returns the constraint index related to a SCIP constraint
SCIP_RETCODE setID(int id)
sets the id of the seeed
SCIP_RETCODE DECdecompCheckConsistency(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2242
SCIP_Bool cmpSeeedsMaxWhite(SeeedPtr i, SeeedPtr j)
int getNPostprocessingDetectors()
returns the number of postprocessing detectors used in the seeedpool
int * getConsClassifierArray(int classifierIndex)
returns the assignment of constraints to classes of a classifier as integer array ...
enum SCIP_Constype_orig SCIP_CONSTYPE_ORIG
int getNBlocks()
returns the number of blocks
SeeedPtr getIncompleteSeeed(int seeedindex)
returns a seeed from incomplete seeed data structure
void populate(std::vector< SeeedPtr > seeeds)
registers seeeds, e.g. done with translated seeeds from the original problem
SCIP_Bool cmpSeeedsPPCaggFWhite(SeeedPtr i, SeeedPtr j)
void setClassDescription(int classindex, const char *desc)
SCIP_CONS * getScipCons(int consid)
returns scip cons for corresponing id
enum GCG_Random_dual_methods GCG_RANDOM_DUAL_METHOD
int getIndexForPostprocessingDetector(DEC_DETECTOR *detector)
returns the postprocessing detector index related to a detector
const int * getConssForBlock(int block)
returns array containing constraints assigned to a block
std::vector< SCIP_Real > getPctConssFromFreeVector()
returns fraction of constraints that are not longer open for detectors in detectorchain ...
std::vector< SeeedPtr > finishIncompleteSeeeds(std::vector< SeeedPtr > incompleteseeeds)
method to complete a set of incomplete seeeds with the help of all included detectors that implement ...
SCIP_HASHMAP * DECdecompGetConstoblock(DEC_DECOMP *decomp)
Definition: decomp.c:1218
SCIP_VAR * varGetRelevantRepr(SCIP *scip, SCIP_VAR *var)
std::vector< int > getNNewBlocksVector()
number of blocks the detectors in the detectorchain added
SCIP_Real GCGconsGetRhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:107
bool isPropagatedBy(DEC_DETECTOR *detectorID)
returns true if this seeed was propagated by specified detector
SCIP_RETCODE DECdecompSetSubscipconss(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS ***subscipconss, int *nsubscipconss)
Definition: decomp.c:838
#define DEFAULT_RANDSEED
SCIP_RETCODE bookAsBlockCons(int consToBlock, int block)
books a constraint to be added to the block constraints of the given block (by calling flushBooked al...
SCIP_Real GCGconsGetLhs(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:205
void DECdecompSetConsindex(DEC_DECOMP *decomp, SCIP_HASHMAP *consindex)
Definition: decomp.c:1248
std::vector< SCIP_Real > getPctVarsToBlockVector()
returns fraction of variables assigned to a block for detectors in detectorchain
int SCIPconshdlrDecompGetNBlockNumberCandidates(SCIP *scip)
returns the number of block candidates given by the user
void DECdecompSetDetectorClockTimes(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *detectorClockTimes)
Definition: decomp.c:1644
void addSeeedToFinished(SeeedPtr seeed, SCIP_Bool *success)
adds a seeed to finished seeeds
bool isConsMastercons(int cons)
returns true if the cons is a master cons
void setClassDecompInfo(int classindex, CONS_DECOMPINFO decompInfo)
void addCandidatesNBlocksNVotes(int candidate, int nvotes)
adds a candidate for block size and counts how often a candidate is added
SCIP_Real * DECdecompGetDetectorPctVarsFromOpen(DEC_DECOMP *decomp)
Definition: decomp.c:1874
SCIP_Bool GCGconsIsRanged(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:743
ConsClassifier * createConsClassifierForMiplibConstypes()
returns a new constraint classifier where all constraints with identical Miplib constype are assigned...
int getIndexForVar(SCIP_VAR *var)
returns the variable index related to a SCIP variable
void calcHashvalue()
calculates the hash value of the seeed for comparing
const int * getConssForCons(int consIndex)
SCIP_Bool isSeeedDuplicateofFinished(SeeedPtr seeed)
check if seeed is a duplicate of an existing finished seeed
void showVisualisation()
generates and opens a gp visualization of the seeed
SCIP_RETCODE bookAsStairlinkingVar(int varToStairlinking, int firstBlock)
books a variable to be added to the stairlinking variables of the given block and the following block...
SCIP_Real GCGconsGetDualsol(SCIP *scip, SCIP_CONS *cons)
Definition: scip_misc.c:367
SCIP_RETCODE DECdecompSetLinkingconss(SCIP *scip, DEC_DECOMP *decomp, SCIP_CONS **linkingconss, int nlinkingconss)
Definition: decomp.c:921
static SCIP_RETCODE setTestpricingProblemParameters(SCIP *scip, int clocktype, SCIP_Real infinity, SCIP_Real epsilon, SCIP_Real sumepsilon, SCIP_Real feastol, SCIP_Real lpfeastol, SCIP_Real dualfeastol, SCIP_Bool enableppcuts, SCIP_Real timelimit)
SCIP_Real getMaxWhiteScore()
returns the "maximum white score"
int getNDetectors()
returns the number of detectors the seeed is propagated by
GCG_Random_dual_methods
void clearCurrentSeeeds()
clears current seeed data structure
char * getDetectorChainString()
the detectorchainstring contains the chars of all detectors that worked on this seeed in this order ...
void addPctConssToBlock(SCIP_Real pct)
bookkeeping information: adds fraction of constraints assigned to a block for a detector added to det...
SCIP_RETCODE DECdecompSetSubscipvars(SCIP *scip, DEC_DECOMP *decomp, SCIP_VAR ***subscipvars, int *nsubscipvars)
Definition: decomp.c:750
struct gcg::subset subset
void calcCandidatesNBlocks()
calculates and adds block size candidates using constraint classifications and variable classificatio...
SCIP_RETCODE printClassifierInformation(SCIP *scip, FILE *file)
output method for json file writer to write classifier candidate information
bool isConsSetppc(int consindexd)
is cons with specified index partitioning packing, or covering constraint?
int getNCurrentSeeeds()
returns size of current (open) seeed data structure
int getNStairlinkingvars(int block)
returns size of the vector containing stairlinking vars
int getNMasterconss()
returns size of the vector containing master conss
SCIP * getScip()
returns the corresponding scip data structure
SCIP_Bool cmpSeeedsAggFWhite(SeeedPtr i, SeeedPtr j)
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
void DECdecompSetDetectorPctVarsFromOpen(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctVarsFromOpen)
Definition: decomp.c:1846
int getNOpenconss()
returns size of vector containing constraints not assigned yet
SCIP_RETCODE displaySeeed()
displays the relevant information of the seeed
SCIP_Bool GCGgetConsIsSetppc(SCIP *scip, SCIP_CONS *cons, SCIP_SETPPCTYPE *setppctype)
Definition: scip_misc.c:762
SCIP_Real getDualvalRandom(int consindex)
return the a random value of the dual variable of the corresponding ; if it is not calculated yet it ...
SCIP_Real getPctVarsToBlock(int detectorchainindex)
returns fraction of variables assigned to a block for a detector
SCIP_Real getDetectorClockTime(int detectorchainindex)
returns the time that the detector related to the given detectorchainindex needed for detecting ...
void DECsetMaxWhiteScore(SCIP *scip, DEC_DECOMP *decdecomp, SCIP_Real maxwhitescore)
Definition: decomp.c:3226
class with functions for seeed pool where a seeed is a (potentially incomplete) description of a deco...
gcg::Seeed * findFinishedSeeedByID(int seeedid)
returns seeed with the corresponding id or NULL if it is not found in this seeedpool ...
void DECdecompSetConstoblock(DEC_DECOMP *decomp, SCIP_HASHMAP *constoblock)
Definition: decomp.c:1206
SCIP_RETCODE bookAsMasterCons(int consToMaster)
books a constraint to be added to the master constraints (by calling flushBooked all bookings are in ...
void addConsClassifier(ConsClassifier *classifier)
adds a constraint classifier if it is no duplicate of an existing constraint classifier ...
const int * getMastervars()
SCIP_Bool seeedIsNoDuplicateOfSeeeds(SeeedPtr compseeed, std::vector< SeeedPtr > const &seeeds, bool sort)
const char * DECdetectorGetName(DEC_DETECTOR *detector)
returns the name of the provided detector
int getNVarClassifiers()
returns number of different variable classifiers
bool checkConsistency()
returns true if the assignments in the seeed are consistent the following checks are performed: 1) ch...
int addClass(const char *name, const char *desc, CONS_DECOMPINFO decompInfo)
int addClass(const char *name, const char *desc, VAR_DECOMPINFO decompInfo)
const int * getStairlinkingvars(int block)
returns array containing stairlinking vars,
void assignVarToClass(int varindex, int classindex)
std::vector< SeeedPtr > removeSomeOneblockDecomps(std::vector< SeeedPtr > givenseeeds)
returns a vector of seeeds such that all seeeds of given a vector of seeeds having only one block are...
void addNNewBlocks(int nnewblocks)
bookkeeping information: adds number of new blocks created by a detector added to detector chain ...
SCIP_Bool cmpSeeedsClassic(SeeedPtr i, SeeedPtr j)
std::vector< SCIP_Real > getPctConssToBlockVector()
returns fraction of constraints assigned to a block for detectors in detectorchain ...
SCIP_Bool varIsFixedToZero(SCIP *scip, SCIP_VAR *var)
ConsClassifier * createConsClassifierForNNonzeros()
void addClockTime(SCIP_Real clocktime)
incorporates the needed time of a certain detector in the detector chain
interface data structure for the detector calling methods
SCIP_Bool seeedIsNoDuplicate(SeeedPtr seeed, std::vector< SeeedPtr > const &currseeeds, std::vector< SeeedPtr > const &finishedseeeds, bool sort)
bool isConsCardinalityCons(int consindexd)
returns whether a constraint is a cardinality constraint, i.e. of the ){i} x_i == b ...
constraint handler for structure detection
void DECdecompSetDetectorPctVarsToBorder(SCIP *scip, DEC_DECOMP *decomp, SCIP_Real *pctVarsToBorder)
Definition: decomp.c:1703
scoretype SCIPconshdlrDecompGetCurrScoretype(SCIP *scip)
SCIP_Real * DECdecompGetDetectorPctConssToBorder(DEC_DECOMP *decomp)
Definition: decomp.c:1766
int getNConsClassifiers()
returns number of different constraint classifiers
int getFirstUnfinishedChildId(std::vector< SCIP_Bool > const &childsfinished, std::vector< int > const &childs)
SCIP_RETCODE bookAsLinkingVar(int varToLinking)
books a variable to be added to the linking variables (by calling flushBooked all bookings are in fac...
SCIP_CONS * getConsForIndex(int consIndex)
returns the SCIP constraint related to a constraint index
int getNMastervars()
returns size of the vector containing master vars (hitting only constraints in the master) ...
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43
int getIndexForDetector(DEC_DETECTOR *detector)
the detector index related to a detector
int calcLevenshteinDistance(std::string s, std::string t)
std::vector< SCIP_Real > getDetectorClockTimes()
returns a vector of the clock times that each detector needed that was involved in this seeed ...
void removeDigits(char *str, int *nremoved)
std::vector< SeeedPtr > thinout(std::vector< SeeedPtr > finishedseeeds, size_t ndecomps, SCIP_Bool addtrivialdecomp)
public methods for working with decomposition structures
SCIP_RETCODE bookAsMasterVar(int varToMaster)
books a variable to be added to the master variables (by calling flushBooked all bookings are in fact...
void addPctConssFromFree(SCIP_Real pct)
bookkeeping information: fraction of constraints that are not longer open for a detector added to det...
SCIP_RETCODE DECdecompAddRemainingConss(SCIP *scip, DEC_DECOMP *decdecomp)
Definition: decomp.c:2154
const int * getVarsForCons(int consIndex)
returns the variable indices of the coefficient matrix for a constraint
SCIP_Bool cmpSeeedsBenders(SeeedPtr i, SeeedPtr j)
std::vector< SCIP_Real > getPctVarsFromFreeVector()
returns fraction of variables that are not longer open for detectors in detectorchain ...
void DECdecompSetSeeedID(DEC_DECOMP *decomp, int seeedID)
Definition: decomp.c:1619
SCIP_Real getPctVarsFromFree(int detectorchainindex)
returns fraction of variables that are not longer open for a detector
std::vector< int > getAncestorList()
get ancestor ids as vector
int getNVars()
return the number of variables considered in the seeedpool
int SCIPconshdlrDecompGetNDetectors(SCIP *scip)
SCIP_Bool DECdecompGetPresolved(DEC_DECOMP *decomp)
Definition: decomp.c:718
void clearFinishedSeeeds()
clears finished seeed data structure