1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the HiGHS linear optimization suite */ 4 /* */ 5 /* Written and engineered 2008-2021 at the University of Edinburgh */ 6 /* */ 7 /* Available as open-source under the MIT License */ 8 /* */ 9 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 10 #ifndef HIGHS_IMPLICATIONS_H_ 11 #define HIGHS_IMPLICATIONS_H_ 12 13 #include <algorithm> 14 #include <cassert> 15 #include <utility> 16 #include <vector> 17 18 #include "mip/HighsDomain.h" 19 #include "mip/HighsDomainChange.h" 20 21 class HighsCliqueTable; 22 23 class HighsImplications { 24 std::vector<HighsDomainChange> implications; 25 26 struct Implics { 27 int start; 28 int num; 29 }; 30 std::vector<Implics> implicationmap; 31 32 bool computeImplications(int col, bool val); 33 34 public: 35 HighsDomain& globaldomain; 36 HighsCliqueTable& cliquetable; 37 std::vector<HighsSubstitution> substitutions; 38 std::vector<uint8_t> colsubstituted; HighsImplications(HighsDomain & globaldom,HighsCliqueTable & cliquetable)39 HighsImplications(HighsDomain& globaldom, HighsCliqueTable& cliquetable) 40 : globaldomain(globaldom), cliquetable(cliquetable) { 41 int numcol = globaldom.colLower_.size(); 42 implicationmap.resize(2 * numcol, {-1, 0}); 43 colsubstituted.resize(numcol); 44 } 45 reset()46 void reset() { 47 colsubstituted.clear(); 48 colsubstituted.shrink_to_fit(); 49 implicationmap.clear(); 50 implicationmap.shrink_to_fit(); 51 52 int numcol = globaldomain.colLower_.size(); 53 implicationmap.resize(2 * numcol, {-1, 0}); 54 colsubstituted.resize(numcol); 55 } 56 getImplications(int col,bool val,const HighsDomainChange * & implicationsstart,bool & infeasible)57 int getImplications(int col, bool val, 58 const HighsDomainChange*& implicationsstart, 59 bool& infeasible) { 60 int loc = 2 * col + val; 61 if (implicationmap[loc].start == -1) { 62 infeasible = computeImplications(col, val); 63 64 if (infeasible) return 0; 65 } else 66 infeasible = false; 67 68 assert(implicationmap[loc].start != -1); 69 70 implicationsstart = &implications[implicationmap[loc].start]; 71 72 return implicationmap[loc].num; 73 } 74 implicationsCached(int col,bool val)75 bool implicationsCached(int col, bool val) { 76 int loc = 2 * col + val; 77 return implicationmap[loc].start != -1; 78 } 79 80 bool runProbing(int col, int& numboundchgs); 81 }; 82 83 #endif