[2049] | 1 | /* $Id: CbcSymmetry.hpp 1033 2013-12-14 19:34:28Z pbelotti $ |
---|
| 2 | * |
---|
| 3 | * Name: Hacked from CouenneProblem.hpp |
---|
| 4 | * Author: Pietro Belotti, Lehigh University |
---|
| 5 | * Andreas Waechter, IBM |
---|
| 6 | * Purpose: define the class CouenneProblem |
---|
| 7 | * |
---|
| 8 | * (C) Carnegie-Mellon University, 2006-11. |
---|
| 9 | * This file is licensed under the Eclipse Public License (EPL) |
---|
| 10 | */ |
---|
| 11 | /* |
---|
| 12 | If this is much used then we could improve build experience |
---|
| 13 | Download nauty - say to /disk/nauty25r9 |
---|
| 14 | In that directory ./configure --enable-tls --enable-wordsize=32 |
---|
| 15 | make |
---|
| 16 | copy nauty.a to libnauty.a |
---|
| 17 | |
---|
| 18 | In Cbc's configure |
---|
| 19 | add -DCOIN_HAS_NTY to CXXDEFS |
---|
| 20 | add -I/disk/nauty25r9 to CXXDEFS or ADD_CXXFLAGS |
---|
| 21 | add -L/disk/nauty25r9 -lnauty to LDFLAGS |
---|
| 22 | |
---|
| 23 | If you wish to use Traces rather than nauty then add -DNTY_TRACES |
---|
| 24 | |
---|
| 25 | To use it is -orbit on |
---|
| 26 | |
---|
| 27 | Nauty has this - |
---|
| 28 | * Permission |
---|
| 29 | * is hereby given for use and/or distribution with the exception of * |
---|
| 30 | * sale for profit or application with nontrivial military significance. * |
---|
| 31 | so you can use it internally even if you are a company. |
---|
| 32 | */ |
---|
| 33 | #ifndef CBC_SYMMETRY_HPP |
---|
| 34 | #define CBC_SYMMETRY_HPP |
---|
| 35 | extern "C" { |
---|
| 36 | #include "nauty.h" |
---|
| 37 | #include "nausparse.h" |
---|
| 38 | #ifdef NTY_TRACES |
---|
| 39 | #include "traces.h" |
---|
| 40 | #endif |
---|
| 41 | } |
---|
| 42 | |
---|
| 43 | #include <vector> |
---|
| 44 | #include <map> |
---|
| 45 | #include <string.h> |
---|
| 46 | |
---|
| 47 | #include "CbcModel.hpp" |
---|
| 48 | |
---|
| 49 | class OsiObject; |
---|
| 50 | // when to give up (depth since last success) |
---|
| 51 | #ifndef NTY_BAD_DEPTH |
---|
| 52 | #define NTY_BAD_DEPTH 10 |
---|
| 53 | #endif |
---|
| 54 | class CbcNauty; |
---|
| 55 | |
---|
| 56 | class Node{ |
---|
| 57 | int index; |
---|
| 58 | double coeff; |
---|
| 59 | double lb; |
---|
| 60 | double ub; |
---|
| 61 | int color; |
---|
| 62 | int code; |
---|
| 63 | int sign; |
---|
| 64 | public: |
---|
| 65 | void node(int, double, double, double, int, int); |
---|
| 66 | inline void color_vertex (register int k) {color = k;} |
---|
| 67 | inline int get_index () const {return index;} |
---|
| 68 | inline double get_coeff () const {return coeff;} |
---|
| 69 | inline double get_lb () const {return lb;} |
---|
| 70 | inline double get_ub () const {return ub;} |
---|
| 71 | inline int get_color () const {return color;} |
---|
| 72 | inline int get_code () const {return code;} |
---|
| 73 | inline int get_sign () const {return sign;} |
---|
| 74 | inline void bounds(register double a, register double b){ lb = a; ub = b;} |
---|
| 75 | }; |
---|
| 76 | |
---|
| 77 | #define COUENNE_HACKED_EPS 1.e-07 |
---|
| 78 | #define COUENNE_HACKED_EPS_SYMM 1e-8 |
---|
| 79 | #define COUENNE_HACKED_EXPRGROUP 8 |
---|
| 80 | |
---|
| 81 | struct myclass0 { |
---|
| 82 | inline bool operator() (register const Node &a, register const Node &b) { |
---|
| 83 | |
---|
| 84 | return (( a.get_code () < b.get_code ()) || |
---|
| 85 | (( a.get_code () == b.get_code () && |
---|
| 86 | (( a.get_coeff () < b.get_coeff () - COUENNE_HACKED_EPS_SYMM) || |
---|
| 87 | (( fabs (a.get_coeff () - b.get_coeff ()) < COUENNE_HACKED_EPS_SYMM) && |
---|
| 88 | (( a.get_lb () < b.get_lb () - COUENNE_HACKED_EPS_SYMM) || |
---|
| 89 | (( fabs (a.get_lb () - b.get_lb ()) < COUENNE_HACKED_EPS_SYMM) && |
---|
| 90 | (( a.get_ub () < b.get_ub () - COUENNE_HACKED_EPS_SYMM) || |
---|
| 91 | (( fabs (a.get_ub () - b.get_ub ()) < COUENNE_HACKED_EPS_SYMM) && |
---|
| 92 | (( a.get_index () < b.get_index ()))))))))))); |
---|
| 93 | |
---|
| 94 | } |
---|
| 95 | } ; |
---|
| 96 | |
---|
| 97 | |
---|
| 98 | struct myclass { |
---|
| 99 | inline bool operator() (register const Node &a, register const Node &b) { |
---|
| 100 | return (a.get_index() < b.get_index() ); |
---|
| 101 | } |
---|
| 102 | }; |
---|
| 103 | |
---|
| 104 | struct less_than_str { |
---|
| 105 | inline bool operator() (register const char *a, register const char *b) const |
---|
| 106 | {return strcmp (a, b) < 0;} |
---|
| 107 | }; |
---|
| 108 | |
---|
| 109 | /** Class to deal with symmetry |
---|
| 110 | * |
---|
| 111 | * Hacked from Couenne |
---|
| 112 | */ |
---|
| 113 | |
---|
| 114 | class CbcSymmetry { |
---|
| 115 | |
---|
| 116 | public: |
---|
| 117 | |
---|
| 118 | /**@name Constructors and destructors */ |
---|
| 119 | //@{ |
---|
| 120 | /// Default constructor |
---|
| 121 | CbcSymmetry (); |
---|
| 122 | |
---|
| 123 | /// Copy constructor |
---|
| 124 | CbcSymmetry (const CbcSymmetry &); |
---|
| 125 | |
---|
| 126 | /// Assignment operator |
---|
| 127 | CbcSymmetry & operator=(const CbcSymmetry& rhs); |
---|
| 128 | |
---|
| 129 | /// Destructor |
---|
| 130 | ~CbcSymmetry (); |
---|
| 131 | //@} |
---|
| 132 | |
---|
| 133 | // Symmetry Info |
---|
| 134 | |
---|
| 135 | std::vector<int> *Find_Orbit(int) const; |
---|
| 136 | |
---|
| 137 | myclass0 node_sort; |
---|
| 138 | myclass index_sort; |
---|
| 139 | |
---|
| 140 | void Compute_Symmetry() const; |
---|
| 141 | int statsOrbits(CbcModel * model, int type) const; |
---|
[2092] | 142 | //double timeNauty () const; |
---|
[2049] | 143 | void Print_Orbits() const; |
---|
| 144 | void fillOrbits(); |
---|
| 145 | /// Fixes variables using orbits (returns number fixed) |
---|
| 146 | int orbitalFixing(OsiSolverInterface * solver); |
---|
| 147 | inline int * whichOrbit() |
---|
| 148 | { return numberUsefulOrbits_ ? whichOrbit_ : NULL;} |
---|
[2092] | 149 | inline int numberUsefulOrbits() const |
---|
| 150 | { return numberUsefulOrbits_;} |
---|
[2049] | 151 | inline int numberUsefulObjects() const |
---|
[2092] | 152 | { return numberUsefulObjects_;} |
---|
[2049] | 153 | int largestOrbit(const double * lower, const double * upper) const; |
---|
| 154 | void ChangeBounds (const double * lower, const double * upper, |
---|
| 155 | int numberColumns,bool justFixedAtOne) const; |
---|
| 156 | inline bool compare (register Node &a, register Node &b) const; |
---|
| 157 | CbcNauty *getNtyInfo () {return nauty_info_;} |
---|
| 158 | |
---|
| 159 | // bool node_sort ( Node a, Node b); |
---|
| 160 | // bool index_sort ( Node a, Node b); |
---|
| 161 | |
---|
| 162 | /// empty if no NTY, symmetry data structure setup otherwise |
---|
| 163 | void setupSymmetry (const OsiSolverInterface & solver); |
---|
| 164 | private: |
---|
| 165 | mutable std::vector<Node> node_info_; |
---|
| 166 | mutable CbcNauty *nauty_info_; |
---|
| 167 | int numberColumns_; |
---|
| 168 | int numberUsefulOrbits_; |
---|
[2092] | 169 | int numberUsefulObjects_; |
---|
[2049] | 170 | int * whichOrbit_; |
---|
| 171 | }; |
---|
| 172 | |
---|
| 173 | class CbcNauty |
---|
| 174 | { |
---|
| 175 | |
---|
| 176 | public: |
---|
| 177 | enum VarStatus { FIX_AT_ZERO, FIX_AT_ONE, FREE }; |
---|
| 178 | |
---|
| 179 | /**@name Constructors and destructors */ |
---|
| 180 | //@{ |
---|
| 181 | private: |
---|
| 182 | /// Default constructor |
---|
| 183 | CbcNauty (); |
---|
| 184 | public: |
---|
| 185 | /// Normal constructor (if dense - NULLS) |
---|
| 186 | CbcNauty (int n, const size_t * v, const int * d, const int * e); |
---|
| 187 | |
---|
| 188 | /// Copy constructor |
---|
| 189 | CbcNauty (const CbcNauty &); |
---|
| 190 | |
---|
| 191 | /// Assignment operator |
---|
| 192 | CbcNauty & operator=(const CbcNauty& rhs); |
---|
| 193 | |
---|
| 194 | /// Destructor |
---|
| 195 | ~CbcNauty (); |
---|
| 196 | //@} |
---|
| 197 | |
---|
| 198 | void addElement(int ix, int jx); |
---|
| 199 | void clearPartitions(); |
---|
| 200 | void computeAuto(); |
---|
| 201 | void deleteElement(int ix, int jx); |
---|
| 202 | void color_node(int ix, int color) { vstat_[ix] = color; } |
---|
| 203 | void insertRHS(int rhs , int cons) {constr_rhs.insert( std::pair<int,int>(rhs,cons));} |
---|
| 204 | |
---|
| 205 | double getGroupSize() const; |
---|
| 206 | //int getNautyCalls() const { return nautyCalls_; } |
---|
| 207 | //double getNautyTime() const { return nautyTime_; } |
---|
| 208 | |
---|
| 209 | int getN() const { return n_; } |
---|
| 210 | |
---|
| 211 | int getNumGenerators() const; |
---|
| 212 | int getNumOrbits() const; |
---|
| 213 | |
---|
| 214 | /// Returns the orbits in a "convenient" form |
---|
| 215 | std::vector<std::vector<int> > *getOrbits() const; |
---|
| 216 | |
---|
| 217 | void getVstat(double *v, int nv); |
---|
| 218 | inline bool isSparse() const |
---|
| 219 | { return GSparse_ != NULL;} |
---|
[2092] | 220 | inline int errorStatus() const |
---|
| 221 | { return stats_->errstatus;} |
---|
[2049] | 222 | /** |
---|
| 223 | * Methods to classify orbits. Not horribly efficient, but gets the job done |
---|
| 224 | */ |
---|
| 225 | // bool isAllFixOneOrbit(const std::vector<int> &orbit) const; |
---|
| 226 | // bool isAllFreeOrbit(const std::vector<int> &orbit) const; |
---|
| 227 | //bool isAutoComputed() const { return autoComputed_; } |
---|
| 228 | //bool isConstraintOrbit(const std::vector<int> &orbit) const; |
---|
| 229 | //bool isMixedFreeZeroOrbit(const std::vector<int> &orbit) const; |
---|
| 230 | //void makeFree(int ix) { vstat_[ix] = FREE; } |
---|
| 231 | |
---|
| 232 | void setWriteAutoms (const std::string &afilename); |
---|
| 233 | void unsetWriteAutoms(); |
---|
| 234 | |
---|
| 235 | private: |
---|
| 236 | |
---|
| 237 | // The base nauty stuff |
---|
| 238 | graph *G_; |
---|
| 239 | sparsegraph *GSparse_; |
---|
| 240 | int *lab_; |
---|
| 241 | int *ptn_; |
---|
| 242 | set *active_; |
---|
| 243 | int *orbits_; |
---|
| 244 | #ifndef NTY_TRACES |
---|
| 245 | optionblk *options_; |
---|
| 246 | statsblk *stats_; |
---|
| 247 | #else |
---|
| 248 | TracesOptions *options_; |
---|
| 249 | TracesStats *stats_; |
---|
| 250 | #endif |
---|
| 251 | setword *workspace_; |
---|
| 252 | int worksize_; |
---|
| 253 | int m_; |
---|
| 254 | int n_; |
---|
| 255 | size_t nel_; |
---|
| 256 | graph *canonG_; |
---|
| 257 | |
---|
| 258 | bool autoComputed_; |
---|
| 259 | |
---|
| 260 | int *vstat_; |
---|
| 261 | |
---|
| 262 | //static int nautyCalls_; |
---|
| 263 | //static double nautyTime_; |
---|
| 264 | |
---|
| 265 | std::multimap<int,int> constr_rhs; |
---|
| 266 | std::multimap<int,int>::iterator it; |
---|
| 267 | |
---|
| 268 | std::pair<std::multimap<int,int>::iterator, |
---|
| 269 | std::multimap<int,int>::iterator> ret; |
---|
| 270 | |
---|
| 271 | // File pointer for automorphism group |
---|
| 272 | FILE *afp_; |
---|
| 273 | |
---|
| 274 | }; |
---|
| 275 | |
---|
| 276 | |
---|
| 277 | /** Branching object for Orbital branching |
---|
| 278 | |
---|
| 279 | Variable_ is the set id number (redundant, as the object also holds a |
---|
| 280 | pointer to the set. |
---|
| 281 | */ |
---|
| 282 | class CbcOrbitalBranchingObject : public CbcBranchingObject { |
---|
| 283 | |
---|
| 284 | public: |
---|
| 285 | |
---|
| 286 | // Default Constructor |
---|
| 287 | CbcOrbitalBranchingObject (); |
---|
| 288 | |
---|
| 289 | // Useful constructor |
---|
| 290 | CbcOrbitalBranchingObject (CbcModel * model, int column, |
---|
| 291 | int way, |
---|
| 292 | int numberExtra, const int * extraToZero); |
---|
| 293 | |
---|
| 294 | // Copy constructor |
---|
| 295 | CbcOrbitalBranchingObject ( const CbcOrbitalBranchingObject &); |
---|
| 296 | |
---|
| 297 | // Assignment operator |
---|
| 298 | CbcOrbitalBranchingObject & operator=( const CbcOrbitalBranchingObject& rhs); |
---|
| 299 | |
---|
| 300 | /// Clone |
---|
| 301 | virtual CbcBranchingObject * clone() const; |
---|
| 302 | |
---|
| 303 | // Destructor |
---|
| 304 | virtual ~CbcOrbitalBranchingObject (); |
---|
| 305 | |
---|
| 306 | using CbcBranchingObject::branch ; |
---|
| 307 | /// Does next branch and updates state |
---|
| 308 | virtual double branch(); |
---|
| 309 | /** Update bounds in solver as in 'branch' and update given bounds. |
---|
| 310 | branchState is -1 for 'down' +1 for 'up' */ |
---|
| 311 | virtual void fix(OsiSolverInterface * solver, |
---|
| 312 | double * lower, double * upper, |
---|
| 313 | int branchState) const ; |
---|
| 314 | |
---|
| 315 | /** Reset every information so that the branching object appears to point to |
---|
| 316 | the previous child. This method does not need to modify anything in any |
---|
| 317 | solver. */ |
---|
| 318 | virtual void previousBranch() { |
---|
| 319 | CbcBranchingObject::previousBranch(); |
---|
| 320 | } |
---|
| 321 | |
---|
| 322 | using CbcBranchingObject::print ; |
---|
| 323 | /** \brief Print something about branch - only if log level high |
---|
| 324 | */ |
---|
| 325 | virtual void print(); |
---|
| 326 | |
---|
| 327 | /** Return the type (an integer identifier) of \c this */ |
---|
| 328 | virtual CbcBranchObjType type() const { |
---|
| 329 | return SoSBranchObj; |
---|
| 330 | } |
---|
| 331 | |
---|
| 332 | /** Compare the original object of \c this with the original object of \c |
---|
| 333 | brObj. Assumes that there is an ordering of the original objects. |
---|
| 334 | This method should be invoked only if \c this and brObj are of the same |
---|
| 335 | type. |
---|
| 336 | Return negative/0/positive depending on whether \c this is |
---|
| 337 | smaller/same/larger than the argument. |
---|
| 338 | */ |
---|
| 339 | virtual int compareOriginalObject(const CbcBranchingObject* brObj) const; |
---|
| 340 | |
---|
| 341 | /** Compare the \c this with \c brObj. \c this and \c brObj must be os the |
---|
| 342 | same type and must have the same original object, but they may have |
---|
| 343 | different feasible regions. |
---|
| 344 | Return the appropriate CbcRangeCompare value (first argument being the |
---|
| 345 | sub/superset if that's the case). In case of overlap (and if \c |
---|
| 346 | replaceIfOverlap is true) replace the current branching object with one |
---|
| 347 | whose feasible region is the overlap. |
---|
| 348 | */ |
---|
| 349 | virtual CbcRangeCompare compareBranchingObject |
---|
| 350 | (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false); |
---|
| 351 | |
---|
| 352 | private: |
---|
| 353 | /// Column to go to 1 |
---|
| 354 | int column_; |
---|
| 355 | /// Number (without column) going to zero on down branch |
---|
| 356 | int numberOther_; |
---|
| 357 | /// Number extra |
---|
| 358 | int numberExtra_; |
---|
| 359 | /// Fix to zero |
---|
| 360 | int * fixToZero_; |
---|
| 361 | }; |
---|
| 362 | |
---|
| 363 | #endif |
---|