Cbc  2.9.8
CbcSymmetry.hpp
Go to the documentation of this file.
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 
57 
58 #define COUENNE_HACKED_EPS 1.e-07
59 #define COUENNE_HACKED_EPS_SYMM 1e-8
60 #define COUENNE_HACKED_EXPRGROUP 8
61 
62 
69 class CbcSymmetry {
70  class Node{
71  int index;
72  double coeff;
73  double lb;
74  double ub;
75  int color;
76  int code;
77  int sign;
78  public:
79  void node(int, double, double, double, int, int);
80  inline void color_vertex (register int k) {color = k;}
81  inline int get_index () const {return index;}
82  inline double get_coeff () const {return coeff;}
83  inline double get_lb () const {return lb;}
84  inline double get_ub () const {return ub;}
85  inline int get_color () const {return color;}
86  inline int get_code () const {return code;}
87  inline int get_sign () const {return sign;}
88  inline void bounds(register double a, register double b){ lb = a; ub = b;}
89  };
90 
91  struct myclass0 {
92  inline bool operator() (register const Node &a, register const Node &b) {
93 
94  return (( a.get_code () < b.get_code ()) ||
95  (( a.get_code () == b.get_code () &&
96  (( a.get_coeff () < b.get_coeff () - COUENNE_HACKED_EPS_SYMM) ||
97  (( fabs (a.get_coeff () - b.get_coeff ()) < COUENNE_HACKED_EPS_SYMM) &&
98  (( a.get_lb () < b.get_lb () - COUENNE_HACKED_EPS_SYMM) ||
99  (( fabs (a.get_lb () - b.get_lb ()) < COUENNE_HACKED_EPS_SYMM) &&
100  (( a.get_ub () < b.get_ub () - COUENNE_HACKED_EPS_SYMM) ||
101  (( fabs (a.get_ub () - b.get_ub ()) < COUENNE_HACKED_EPS_SYMM) &&
102  (( a.get_index () < b.get_index ())))))))))));
103 
104  }
105  } ;
106 
107 
108  struct myclass {
109  inline bool operator() (register const Node &a, register const Node &b) {
110  return (a.get_index() < b.get_index() );
111  }
112  };
113 
114 struct less_than_str {
115  inline bool operator() (register const char *a, register const char *b) const
116  {return strcmp (a, b) < 0;}
117 };
118 
119  public:
120 
123  CbcSymmetry ();
125 
127  CbcSymmetry (const CbcSymmetry &);
128 
130  CbcSymmetry & operator=(const CbcSymmetry& rhs);
131 
133  ~CbcSymmetry ();
135 
136  // Symmetry Info
137 
138  std::vector<int> *Find_Orbit(int) const;
139 
140  myclass0 node_sort;
141  myclass index_sort;
142 
143  void Compute_Symmetry() const;
144  int statsOrbits(CbcModel * model, int type) const;
145  //double timeNauty () const;
146  void Print_Orbits() const;
147  void fillOrbits();
149  int orbitalFixing(OsiSolverInterface * solver);
150  inline int * whichOrbit()
151  { return numberUsefulOrbits_ ? whichOrbit_ : NULL;}
152  inline int numberUsefulOrbits() const
153  { return numberUsefulOrbits_;}
154  inline int numberUsefulObjects() const
155  { return numberUsefulObjects_;}
156  int largestOrbit(const double * lower, const double * upper) const;
157  void ChangeBounds (const double * lower, const double * upper,
158  int numberColumns,bool justFixedAtOne) const;
159  inline bool compare (register Node &a, register Node &b) const;
160  CbcNauty *getNtyInfo () {return nauty_info_;}
161 
162  // bool node_sort ( Node a, Node b);
163  // bool index_sort ( Node a, Node b);
164 
166  void setupSymmetry (const OsiSolverInterface & solver);
167 private:
168  mutable std::vector<Node> node_info_;
169  mutable CbcNauty *nauty_info_;
170  int numberColumns_;
171  int numberUsefulOrbits_;
172  int numberUsefulObjects_;
173  int * whichOrbit_;
174 };
175 
176 class CbcNauty
177 {
178 
179 public:
180  enum VarStatus { FIX_AT_ZERO, FIX_AT_ONE, FREE };
181 
184 private:
186  CbcNauty ();
187 public:
189  CbcNauty (int n, const size_t * v, const int * d, const int * e);
190 
192  CbcNauty (const CbcNauty &);
193 
195  CbcNauty & operator=(const CbcNauty& rhs);
196 
198  ~CbcNauty ();
200 
201  void addElement(int ix, int jx);
202  void clearPartitions();
203  void computeAuto();
204  void deleteElement(int ix, int jx);
205  void color_node(int ix, int color) { vstat_[ix] = color; }
206  void insertRHS(int rhs , int cons) {constr_rhs.insert( std::pair<int,int>(rhs,cons));}
207 
208  double getGroupSize() const;
209  //int getNautyCalls() const { return nautyCalls_; }
210  //double getNautyTime() const { return nautyTime_; }
211 
212  int getN() const { return n_; }
213 
214  int getNumGenerators() const;
215  int getNumOrbits() const;
216 
218  std::vector<std::vector<int> > *getOrbits() const;
219 
220  void getVstat(double *v, int nv);
221  inline bool isSparse() const
222  { return GSparse_ != NULL;}
223  inline int errorStatus() const
224  { return stats_->errstatus;}
228  // bool isAllFixOneOrbit(const std::vector<int> &orbit) const;
229  // bool isAllFreeOrbit(const std::vector<int> &orbit) const;
230  //bool isAutoComputed() const { return autoComputed_; }
231  //bool isConstraintOrbit(const std::vector<int> &orbit) const;
232  //bool isMixedFreeZeroOrbit(const std::vector<int> &orbit) const;
233  //void makeFree(int ix) { vstat_[ix] = FREE; }
234 
235  void setWriteAutoms (const std::string &afilename);
236  void unsetWriteAutoms();
237 
238 private:
239 
240  // The base nauty stuff
241  graph *G_;
242  sparsegraph *GSparse_;
243  int *lab_;
244  int *ptn_;
245  set *active_;
246  int *orbits_;
247 #ifndef NTY_TRACES
248  optionblk *options_;
249  statsblk *stats_;
250 #else
251  TracesOptions *options_;
252  TracesStats *stats_;
253 #endif
254  setword *workspace_;
255  int worksize_;
256  int m_;
257  int n_;
258  size_t nel_;
259  graph *canonG_;
260 
261  bool autoComputed_;
262 
263  int *vstat_;
264 
265  //static int nautyCalls_;
266  //static double nautyTime_;
267 
268  std::multimap<int,int> constr_rhs;
269  std::multimap<int,int>::iterator it;
270 
271  std::pair<std::multimap<int,int>::iterator,
272  std::multimap<int,int>::iterator> ret;
273 
274  // File pointer for automorphism group
275  FILE *afp_;
276 
277 };
278 
279 
286 
287 public:
288 
289  // Default Constructor
291 
292  // Useful constructor
293  CbcOrbitalBranchingObject (CbcModel * model, int column,
294  int way,
295  int numberExtra, const int * extraToZero);
296 
297  // Copy constructor
299 
300  // Assignment operator
302 
304  virtual CbcBranchingObject * clone() const;
305 
306  // Destructor
307  virtual ~CbcOrbitalBranchingObject ();
308 
311  virtual double branch();
314  virtual void fix(OsiSolverInterface * solver,
315  double * lower, double * upper,
316  int branchState) const ;
317 
321  virtual void previousBranch() {
323  }
324 
328  virtual void print();
329 
331  virtual CbcBranchObjType type() const {
332  return SoSBranchObj;
333  }
334 
342  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
343 
352  virtual CbcRangeCompare compareBranchingObject
353  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
354 
355 private:
357  int column_;
359  int numberOther_;
361  int numberExtra_;
363  int * fixToZero_;
364 };
365 
366 #endif
std::vector< int > * Find_Orbit(int) const
CbcNauty * getNtyInfo()
void setupSymmetry(const OsiSolverInterface &solver)
empty if no NTY, symmetry data structure setup otherwise
myclass0 node_sort
virtual CbcBranchObjType type() const
Return the type (an integer identifier) of this.
void color_node(int ix, int color)
int * whichOrbit()
void fillOrbits()
#define COUENNE_HACKED_EPS_SYMM
Definition: CbcSymmetry.hpp:59
CbcRangeCompare
void ChangeBounds(const double *lower, const double *upper, int numberColumns, bool justFixedAtOne) const
Branching object for Orbital branching.
myclass index_sort
bool compare(register Node &a, register Node &b) const
~CbcSymmetry()
Destructor.
int statsOrbits(CbcModel *model, int type) const
int errorStatus() const
Class to deal with symmetry.
Definition: CbcSymmetry.hpp:69
void Compute_Symmetry() const
Abstract branching object base class Now just difference with OsiBranchingObject. ...
void Print_Orbits() const
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child...
CbcBranchObjType
virtual double branch()=0
Execute the actions required to branch, as specified by the current state of the branching object...
virtual void print() const
Print something about branch - only if log level high.
void insertRHS(int rhs, int cons)
int getN() const
int numberUsefulObjects() const
int largestOrbit(const double *lower, const double *upper) const
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child...
bool isSparse() const
CbcSymmetry & operator=(const CbcSymmetry &rhs)
Assignment operator.
int orbitalFixing(OsiSolverInterface *solver)
Fixes variables using orbits (returns number fixed)
Simple Branch and bound class.
Definition: CbcModel.hpp:101
CbcSymmetry()
Default constructor.
int numberUsefulOrbits() const