1 /* $Id: CoinPresolveDupcol.hpp 2083 2019-01-06 19:38:09Z unxusr $ */ 2 // Copyright (C) 2002, International Business Machines 3 // Corporation and others. All Rights Reserved. 4 // This code is licensed under the terms of the Eclipse Public License (EPL). 5 6 #ifndef CoinPresolveDupcol_H 7 #define CoinPresolveDupcol_H 8 9 #include "CoinPresolveMatrix.hpp" 10 11 /*! 12 \file 13 */ 14 15 #define DUPCOL 10 16 17 /*! \class dupcol_action 18 \brief Detect and remove duplicate columns 19 20 The general technique is to sum the coefficients a_(*,j) of each column. 21 Columns with identical sums are duplicates. The obvious problem is that, 22 <i>e.g.</i>, [1 0 1 0] and [0 1 0 1] both add to 2. To minimize the 23 chances of false positives, the coefficients of each row are multipled by 24 a random number r_i, so that we sum r_i*a_ij. 25 26 Candidate columns are checked to confirm they are identical. Where the 27 columns have the same objective coefficient, the two are combined. If the 28 columns have different objective coefficients, complications ensue. In order 29 to remove the duplicate, it must be possible to fix the variable at a bound. 30 */ 31 32 class dupcol_action : public CoinPresolveAction { 33 dupcol_action(); 34 dupcol_action(const dupcol_action &rhs); 35 dupcol_action &operator=(const dupcol_action &rhs); 36 37 struct action { 38 double thislo; 39 double thisup; 40 double lastlo; 41 double lastup; 42 int ithis; 43 int ilast; 44 45 double *colels; 46 int nincol; 47 }; 48 49 const int nactions_; 50 // actions_ is owned by the class and must be deleted at destruction 51 const action *const actions_; 52 dupcol_action(int nactions,const action * actions,const CoinPresolveAction * next)53 dupcol_action(int nactions, const action *actions, 54 const CoinPresolveAction *next) 55 : CoinPresolveAction(next) 56 , nactions_(nactions) 57 , actions_(actions) 58 { 59 } 60 61 public: 62 const char *name() const; 63 64 static const CoinPresolveAction *presolve(CoinPresolveMatrix *prob, 65 const CoinPresolveAction *next); 66 67 void postsolve(CoinPostsolveMatrix *prob) const; 68 69 virtual ~dupcol_action(); 70 }; 71 72 /*! \class duprow_action 73 \brief Detect and remove duplicate rows 74 75 The algorithm to detect duplicate rows is as outlined for dupcol_action. 76 77 If the feasible interval for one constraint is strictly contained in the 78 other, the tighter (contained) constraint is kept. If the feasible 79 intervals are disjoint, the problem is infeasible. If the feasible 80 intervals overlap, both constraints are kept. 81 82 duprow_action is definitely a work in progress; #postsolve is 83 unimplemented. 84 This doesn't matter as it uses useless_constraint. 85 */ 86 87 class duprow_action : public CoinPresolveAction { 88 struct action { 89 int row; 90 double lbound; 91 double ubound; 92 }; 93 94 const int nactions_; 95 const action *const actions_; 96 duprow_action()97 duprow_action() 98 : CoinPresolveAction(NULL) 99 , nactions_(0) 100 , actions_(NULL) 101 { 102 } duprow_action(int nactions,const action * actions,const CoinPresolveAction * next)103 duprow_action(int nactions, 104 const action *actions, 105 const CoinPresolveAction *next) 106 : CoinPresolveAction(next) 107 , nactions_(nactions) 108 , actions_(actions) 109 { 110 } 111 112 public: 113 const char *name() const; 114 115 static const CoinPresolveAction *presolve(CoinPresolveMatrix *prob, 116 const CoinPresolveAction *next); 117 118 void postsolve(CoinPostsolveMatrix *prob) const; 119 120 //~duprow_action() { delete[]actions_; } 121 }; 122 123 class duprow3_action : public CoinPresolveAction { 124 struct action { 125 int row; 126 double lbound; 127 double ubound; 128 }; 129 130 const int nactions_; 131 const action *const actions_; 132 duprow3_action()133 duprow3_action() 134 : CoinPresolveAction(NULL) 135 , nactions_(0) 136 , actions_(NULL) 137 { 138 } duprow3_action(int nactions,const action * actions,const CoinPresolveAction * next)139 duprow3_action(int nactions, 140 const action *actions, 141 const CoinPresolveAction *next) 142 : CoinPresolveAction(next) 143 , nactions_(nactions) 144 , actions_(actions) 145 { 146 } 147 148 public: 149 const char *name() const; 150 151 static const CoinPresolveAction *presolve(CoinPresolveMatrix *prob, 152 const CoinPresolveAction *next); 153 154 void postsolve(CoinPostsolveMatrix *prob) const; 155 156 //~duprow_action() { delete[]actions_; } 157 }; 158 159 /*! \class gubrow_action 160 \brief Detect and remove entries whose sum is known 161 162 If we have an equality row where all entries same then 163 For other rows where all entries for that equality row are same 164 then we can delete entries and modify rhs 165 gubrow_action is definitely a work in progress; #postsolve is 166 unimplemented. 167 */ 168 169 class gubrow_action : public CoinPresolveAction { 170 struct action { 171 double rhs; 172 // last is row itself 173 int *deletedRow; 174 double *rowels; 175 int *indices; // indices in gub row 176 int nDrop; 177 int ninrow; 178 }; 179 180 const int nactions_; 181 const action *const actions_; 182 183 //gubrow_action():CoinPresolveAction(NULL),nactions_(0),actions_(NULL) {} gubrow_action(int nactions,const action * actions,const CoinPresolveAction * next)184 gubrow_action(int nactions, 185 const action *actions, 186 const CoinPresolveAction *next) 187 : CoinPresolveAction(next) 188 , nactions_(nactions) 189 , actions_(actions) 190 { 191 } 192 193 public: 194 const char *name() const; 195 196 static const CoinPresolveAction *presolve(CoinPresolveMatrix *prob, 197 const CoinPresolveAction *next); 198 199 void postsolve(CoinPostsolveMatrix *prob) const; 200 201 virtual ~gubrow_action(); 202 }; 203 204 /*! \class twoxtwo_action 205 \brief Detect interesting 2 by 2 blocks 206 207 If a variable has two entries and for each row there are only 208 two entries with same other variable then we can get rid of 209 one constraint and modify costs. 210 211 This is a work in progress - I need more examples 212 */ 213 214 class twoxtwo_action : public CoinPresolveAction { 215 struct action { 216 double lbound_row; 217 double ubound_row; 218 double lbound_col; 219 double ubound_col; 220 double cost_col; 221 double cost_othercol; 222 int row; 223 int col; 224 int othercol; 225 }; 226 227 const int nactions_; 228 const action *const actions_; 229 twoxtwo_action()230 twoxtwo_action() 231 : CoinPresolveAction(NULL) 232 , nactions_(0) 233 , actions_(NULL) 234 { 235 } twoxtwo_action(int nactions,const action * actions,const CoinPresolveAction * next)236 twoxtwo_action(int nactions, 237 const action *actions, 238 const CoinPresolveAction *next) 239 : CoinPresolveAction(next) 240 , nactions_(nactions) 241 , actions_(actions) 242 { 243 } 244 245 public: 246 const char *name() const; 247 248 static const CoinPresolveAction *presolve(CoinPresolveMatrix *prob, 249 const CoinPresolveAction *next); 250 251 void postsolve(CoinPostsolveMatrix *prob) const; 252 ~twoxtwo_action()253 ~twoxtwo_action() { delete[] actions_; } 254 }; 255 256 #endif 257 258 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2 259 */ 260