class_seeedpool.h
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 #ifndef GCG_CLASS_SEEEDPOOL_H__
37 #define GCG_CLASS_SEEEDPOOL_H__
38 
39 #include "objscip/objscip.h"
40 #include <vector>
41 
42 #if __cplusplus >= 201103L
43 #include <unordered_map>
44 using std::unordered_map;
45 #else
46 #include <tr1/unordered_map>
47 using std::tr1::unordered_map;
48 #endif
49 
50 #include <functional>
51 #include <string>
52 #include <utility>
53 #include "gcg.h"
54 
55 #include "class_seeed.h"
56 #include "class_consclassifier.h"
57 #include "class_varclassifier.h"
58 
59 
64 {
68  int nNewSeeeds;
69 };
70 
71 
72 namespace gcg{
73 
75 {
79 
80 };
81 
82 
83 
85 typedef Seeed* SeeedPtr;
86 
87 
88 
92 struct pair_hash
93 {
94  template<class T1, class T2>
95  std::size_t operator()(
96  const std::pair<T1, T2> &p) const
97  {
98  auto h1 = std::hash<T1>{}( p.first );
99  auto h2 = std::hash<T2>{}( p.second );
100 
101  /* overly simple hash combination */
102  return h1 ^ h2;
103  }
104 };
105 
106 
111 { /*lint -esym(1712,Seeedpool)*/
112 
113 private:
114  SCIP* scip;
115  std::vector<SeeedPtr> incompleteSeeeds;
116  std::vector<SeeedPtr> currSeeeds;
117  std::vector<SeeedPtr> finishedSeeeds;
118  std::vector<SeeedPtr> ancestorseeeds;
119  int maxndetectionrounds;
120  std::vector<std::vector<int>> varsForConss;
122  std::vector<std::vector<double>> valsForConss;
125  std::vector<std::vector<int>> conssForVars;
127  std::vector<SCIP_CONS*> consToScipCons;
128  std::vector<SCIP_VAR*> varToScipVar;
129  std::vector<DEC_DETECTOR*> detectorToScipDetector;
130  std::vector<DEC_DETECTOR*> detectorToFinishingScipDetector;
131  std::vector<DEC_DETECTOR*> detectorToPostprocessingScipDetector;
132  std::vector<std::vector<int>> conssadjacencies;
133  unordered_map<SCIP_CONS*, int> scipConsToIndex;
134  unordered_map<SCIP_VAR*, int> scipVarToIndex;
135  unordered_map<DEC_DETECTOR*, int> scipDetectorToIndex;
136  unordered_map<DEC_DETECTOR*, int> scipFinishingDetectorToIndex;
138  unordered_map<DEC_DETECTOR*, int> scipPostprocessingDetectorToIndex;
141  unordered_map<std::pair<int, int>, SCIP_Real, pair_hash> valsMap;
144  std::vector<SCIP_VAR*> unpresolvedfixedtozerovars;
146  int nVars;
147  int nConss;
148  int nDetectors;
149  int nFinishingDetectors;
150  int nPostprocessingDetectors;
151  int nnonzeros;
155  std::vector<int> usercandidatesnblocks;
156  std::vector<std::pair<int, int>> candidatesNBlocks;
158  std::vector<SCIP_Real> dualvalsrandom;
159  std::vector<SCIP_Real> dualvalsoptimaloriglp;
160  SCIP_Bool dualvalsrandomset;
161  SCIP_Bool dualvalsoptimaloriglpcalculated;
163  SCIP_Bool transformed;
165  SCIP_Bool benders;
167  std::vector<SeeedPtr> seeedstopopulate;
175  SCIP_RETCODE calculateDualvalsOptimalOrigLP();
176 
181  SCIP_RETCODE shuffleDualvalsRandom();
182 
183 public:
184 
185  std::vector<ConsClassifier*> consclassescollection;
186  std::vector<VarClassifier*> varclassescollection;
188  SCIP_Real classificationtime;
190  SCIP_Real postprocessingtime;
192  SCIP_Real translatingtime;
203  Seeedpool(
204  SCIP* scip,
205  const char* conshdlrName,
206  SCIP_Bool transformed,
207  SCIP_Bool benders
208  );
209 
213  ~Seeedpool();
214 
215 
221  SCIP_RETCODE calcClassifierAndNBlockCandidates(
222  SCIP* givenScip
223  );
224 
225 
229  void createConssAdjacency();
230 
231 
232 
237  std::vector<SeeedPtr> findSeeeds();
238 
239 
240 
244  void sortFinishedForScore();
245 
246 
252  std::vector<SeeedPtr> finishIncompleteSeeeds(
253  std::vector<SeeedPtr> incompleteseeeds
254  );
255 
256 
260  void findDecompositions();
261 
262 
263 
269  gcg::Seeed* findFinishedSeeedByID(
270  int seeedid
271  );
272 
273 
274 
279  void addSeeedToAncestor(
280  SeeedPtr seeed
281  );
282 
287  void addSeeedToCurr(
288  SeeedPtr seeed
289  );
290 
291 
298  void addSeeedToFinished(
299  SeeedPtr seeed,
300  SCIP_Bool* success
301  );
302 
303 
309  void addSeeedToFinishedUnchecked(
310  SeeedPtr seeed
311  );
312 
318  void addSeeedToIncomplete(
319  SeeedPtr seeed,
320  SCIP_Bool* success
321  );
322 
323 
329  SCIP_Bool isSeeedDuplicateofIncomplete(
330  SeeedPtr seeed
331  );
332 
333 
339  SCIP_Bool isSeeedDuplicateofFinished(
340  SeeedPtr seeed
341  );
342 
343 
351  SCIP_RETCODE calcStrongDecompositionScore(
352  SeeedPtr seeed,
353  SCIP_Real* score
354  );
355 
356 
357 
362  SCIP_Bool areThereContinuousVars();
363 
364 
365 
370  void clearAncestorSeeeds();
371 
372 
377  void clearCurrentSeeeds();
378 
379 
384  void clearFinishedSeeeds();
385 
386 
391  void clearIncompleteSeeeds();
392 
393 
399  SeeedPtr getAncestorSeeed(
400  int seeedindex
401  );
402 
403 
410  SeeedPtr getCurrentSeeed(
411  int seeedindex
412  );
413 
414 
421  SeeedPtr getFinishedSeeed(
422  int seeedindex
423  );
424 
425 
431  SeeedPtr getIncompleteSeeed(
432  int seeedindex
433  );
434 
435 
440  int getNAncestorSeeeds();
441 
442 
443 
448  int getNCurrentSeeeds();
449 
450 
451 
456  int getNFinishedSeeeds();
457 
458 
463  int getNIncompleteSeeeds();
464 
465 
470  int getNTotalConss(
471  );
472 
473 
474 
479  long getNTotalNonzeros();
480 
481 
482 
489  bool hasDuplicate(
490  SeeedPtr seeed
491  );
492 
493 
498  SCIP_Bool isForBenders();
499 
500 
511  void translateSeeedData(
512  Seeedpool* otherpool,
513  std::vector<Seeed*> otherseeeds,
514  std::vector<Seeed*>& newseeeds,
515  std::vector<ConsClassifier*> otherconsclassifiers,
516  std::vector<ConsClassifier*>& newconsclassifiers,
517  std::vector<VarClassifier*> othervarclassifiers,
518  std::vector<VarClassifier*>& newvarclassifiers
519  );
520 
521 
529  void translateSeeeds(
530  Seeedpool* otherpool,
531  std::vector<Seeed*> otherseeeds,
532  std::vector<Seeed*>& newseeeds
533  );
534 
535 
540  void populate(
541  std::vector<SeeedPtr> seeeds
542  );
543 
549  SCIP_RETCODE prepareSeeed(
550  SeeedPtr seeed
551  );
552 
557  void sortAllRelevantSeeeds();
558 
559 
565  bool isConsCardinalityCons(
566  int consindexd
567  );
568 
574  bool isConsSetppc(
575  int consindexd
576  );
577 
578 
584  bool isConsSetpp(
585  int consindexd
586  );
587 
588 
595  const int* getVarsForCons(
596  int consIndex
597  );
598 
605  const SCIP_Real* getValsForCons(
606  int consIndex
607  );
608 
609 
615  const int* getConssForVar(
616  int varIndex
617  );
618 
619 
625  SCIP_Real getDualvalOptimalLP(
626  int consindex
627  );
628 
634  SCIP_Real getDualvalRandom(
635  int consindex
636  );
637 
638 
645  int getNVarsForCons(
646  int consIndex
647  );
648 
655  int getNConssForVar(
656  int varIndex
657  );
658 
665  const int* getConssForCons(
666  int consIndex
667  );
668 
669 
675  int getNConssForCons(
676  int consIndex
677  );
678 
679 
685  SCIP_VAR* getVarForIndex(
686  int varIndex
687  );
688 
689 
695  SCIP_CONS* getConsForIndex(
696  int consIndex
697  );
698 
704  DEC_DETECTOR* getDetectorForIndex(
705  int detectorIndex
706  );
707 
713  DEC_DETECTOR* getFinishingDetectorForIndex(
714  int detectorIndex
715  );
716 
717 
723  DEC_DETECTOR* getPostprocessingDetectorForIndex(
724  int detectorIndex
725  );
726 
727 
734  SCIP_Real getVal(
735  int row,
736  int col
737  );
738 
744  int getIndexForVar(
745  SCIP_VAR* var
746  );
747 
748 
754  int getIndexForCons(
755  SCIP_CONS* cons
756  );
757 
758 
764  int getIndexForDetector(
765  DEC_DETECTOR* detector
766  );
767 
768 
774  int getIndexForFinishingDetector(
775  DEC_DETECTOR* detector
776  );
777 
778 
784  int getIndexForPostprocessingDetector(
785  DEC_DETECTOR* detector
786  );
787 
788 
793  int getNewIdForSeeed();
794 
795 
800  int getNDetectors();
801 
806  int getNNonzeros();
807 
812  int getNFinishingDetectors();
813 
814 
819  int getNPostprocessingDetectors();
820 
821 
826  int getNVars();
827 
828 
833  int getNConss();
834 
835 
840  SCIP* getScip();
841 
842 
848  SCIP_CONS* getScipCons(
849  int consid
850  );
851 
852 
858  SCIP_VAR* getScipVar(
859  int varid
860  );
861 
862 
868  std::vector<int> getSortedCandidatesNBlocks();
869 
875  std::vector<std::pair<int, int>> getSortedCandidatesNBlocksFull();
876 
877 
882  void addCandidatesNBlocks(
883  int candidate
884  );
885 
886 
892  void addCandidatesNBlocksNVotes(
893  int candidate,
894  int nvotes
895  );
896 
897 
902  void addUserCandidatesNBlocks(
903  int candidate
904  );
905 
906 
911  int getNUserCandidatesNBlocks();
912 
913 
917  void calcCandidatesNBlocks();
918 
923  void addConsClassifier(
924  ConsClassifier* classifier
925  );
926 
927 
933  ConsClassifier* createConsClassifierForSCIPConstypes();
934 
935 
941  ConsClassifier* createConsClassifierForMiplibConstypes();
942 
943 
949  ConsClassifier* createConsClassifierForConsnamesDigitFreeIdentical();
950 
951 
957  ConsClassifier* createConsClassifierForConsnamesLevenshteinDistanceConnectivity(
958  int connectivity
959  );
960 
961 
966  ConsClassifier* createConsClassifierForNNonzeros();
967 
968 
974  ConsClassifier* getConsClassifier(
975  int classifierIndex
976  );
977 
978 
984  int* getConsClassifierArray(
985  int classifierIndex
986  );
987 
992  int getNConsClassifiers();
993 
994 
998  void reduceConsclasses();
999 
1000 
1005  void addVarClassifier(
1006  VarClassifier* classifier
1007  );
1008 
1013  VarClassifier* createVarClassifierForObjValues();
1014 
1015 
1020  VarClassifier* createVarClassifierForObjValueSigns();
1021 
1026  VarClassifier* createVarClassifierForSCIPVartypes();
1027 
1032  int getNVarClassifiers();
1033 
1039  VarClassifier* getVarClassifier(
1040  int classifierIndex
1041  );
1042 
1043 
1049  int* getVarClassifierArray(
1050  int classifierIndex
1051  );
1052 
1057  void reduceVarclasses();
1058 
1059 
1067  std::vector<SeeedPtr> removeSomeOneblockDecomps(
1068  std::vector<SeeedPtr> givenseeeds
1069  );
1070 
1071 
1078  SCIP_RETCODE createDecompFromSeeed(
1079  SeeedPtr seeed,
1080  DEC_DECOMP** newdecomp
1081  );
1082 
1083 
1093  SCIP_RETCODE createSeeedFromDecomp(
1094  DEC_DECOMP* decomp,
1095  SeeedPtr* newseeed
1096  );
1097 
1102  SCIP_Bool getTransformedInfo();
1103 
1104 
1111  SCIP_RETCODE printBlockcandidateInformation(
1112  SCIP* scip,
1113  FILE* file
1114  );
1115 
1116 
1123  SCIP_RETCODE printClassifierInformation(
1124  SCIP* scip,
1125  FILE* file
1126  );
1127 
1128 
1129 private:
1130 
1131 
1142  void calcTranslationMapping(
1143  Seeedpool* origpool,
1144  std::vector<int>& rowothertothis,
1145  std::vector<int>& rowthistoother,
1146  std::vector<int>& colothertothis,
1147  std::vector<int>& colthistoother,
1148  std::vector<int>& missingrowinthis
1149  );
1150 
1151 
1161  std::vector<Seeed*> getTranslatedSeeeds(
1162  std::vector<Seeed*>& otherseeeds,
1163  std::vector<int>& rowothertothis,
1164  std::vector<int>& rowthistoother,
1165  std::vector<int>& colothertothis,
1166  std::vector<int>& colthistoother
1167  );
1168 
1169 
1177  std::vector<ConsClassifier*> getTranslatedConsClassifiers(
1178  std::vector<ConsClassifier*>& otherclassifiers,
1179  std::vector<int>& rowothertothis,
1180  std::vector<int>& rowthistoother
1181  );
1182 
1190  std::vector<VarClassifier*> getTranslatedVarClassifiers(
1191  std::vector<VarClassifier*>& otherclassifiers,
1192  std::vector<int>& colothertothis,
1193  std::vector<int>& colthistoother
1194  );
1195 
1196 
1197 
1198 };
1199 /* class Seeedpool */
1200 
1201 
1202 
1203 } /* namespace gcg */
1204 #endif /* GCG_CLASS_SEEEDPOOL_H__ */
Seeed * SeeedPtr
SCIP_Real translatingtime
struct DEC_Detector DEC_DETECTOR
Definition: type_detector.h:46
gcg::Seeedpool * seeedpool
GCG interface methods.
SCIP_Real scorecalculatingtime
SCIP_Real nblockscandidatescalctime
SCIP_Real classificationtime
class for classifying constraints
GCG_PROBLEM_TRANSFORMED_STATUS
std::vector< VarClassifier * > varclassescollection
class to manage partial decompositions (aka seeed), each seeed corresponds to one seeedpool which con...
Definition: class_seeed.h:71
gcg::Seeed * seeedToPropagate
std::vector< ConsClassifier * > consclassescollection
SCIP_Real postprocessingtime
combine two hash function of objects of a pair to get a vaulue for the pair
std::size_t operator()(const std::pair< T1, T2 > &p) const
class for classifying variables
interface data structure for the detector calling methods
struct DecDecomp DEC_DECOMP
Definition: type_decomp.h:43