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