Cbc  2.9.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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  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 
105  inline bool operator() (register const char *a, register const char *b) const
106  {return strcmp (a, b) < 0;}
107 };
108 
114 class CbcSymmetry {
115 
116  public:
117 
120  CbcSymmetry ();
122 
124  CbcSymmetry (const CbcSymmetry &);
125 
127  CbcSymmetry & operator=(const CbcSymmetry& rhs);
128 
130  ~CbcSymmetry ();
132 
133  // Symmetry Info
134 
135  std::vector<int> *Find_Orbit(int) const;
136 
139 
140  void Compute_Symmetry() const;
141  int statsOrbits(CbcModel * model, int type) const;
142  //double timeNauty () const;
143  void Print_Orbits() const;
144  void fillOrbits();
146  int orbitalFixing(OsiSolverInterface * solver);
147  inline int * whichOrbit()
148  { return numberUsefulOrbits_ ? whichOrbit_ : NULL;}
149  inline int numberUsefulOrbits() const
150  { return numberUsefulOrbits_;}
151  inline int numberUsefulObjects() const
152  { return numberUsefulObjects_;}
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 
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_;
169  int numberUsefulObjects_;
170  int * whichOrbit_;
171 };
172 
173 class CbcNauty
174 {
175 
176 public:
178 
181 private:
183  CbcNauty ();
184 public:
186  CbcNauty (int n, const size_t * v, const int * d, const int * e);
187 
189  CbcNauty (const CbcNauty &);
190 
192  CbcNauty & operator=(const CbcNauty& rhs);
193 
195  ~CbcNauty ();
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 
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;}
220  inline int errorStatus() const
221  { return stats_->errstatus;}
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 
283 
284 public:
285 
286  // Default Constructor
288 
289  // Useful constructor
291  int way,
292  int numberExtra, const int * extraToZero);
293 
294  // Copy constructor
296 
297  // Assignment operator
299 
301  virtual CbcBranchingObject * clone() const;
302 
303  // Destructor
304  virtual ~CbcOrbitalBranchingObject ();
305 
308  virtual double branch();
311  virtual void fix(OsiSolverInterface * solver,
312  double * lower, double * upper,
313  int branchState) const ;
314 
318  virtual void previousBranch() {
320  }
321 
325  virtual void print();
326 
328  virtual CbcBranchObjType type() const {
329  return SoSBranchObj;
330  }
331 
339  virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
340 
350  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
351 
352 private:
354  int column_;
356  int numberOther_;
358  int numberExtra_;
360  int * fixToZero_;
361 };
362 
363 #endif
CbcNauty * getNtyInfo()
void setupSymmetry(const OsiSolverInterface &solver)
empty if no NTY, symmetry data structure setup otherwise
myclass0 node_sort
void bounds(register double a, register double b)
Definition: CbcSymmetry.hpp:74
void color_node(int ix, int color)
virtual ~CbcOrbitalBranchingObject()
void computeAuto()
void addElement(int ix, int jx)
double get_ub() const
Definition: CbcSymmetry.hpp:70
virtual CbcBranchingObject * clone() const
Clone.
int get_index() const
Definition: CbcSymmetry.hpp:67
int errorStatus() const
int * whichOrbit()
void ChangeBounds(const double *lower, const double *upper, int numberColumns, bool justFixedAtOne) const
int getNumOrbits() const
void fillOrbits()
#define COUENNE_HACKED_EPS_SYMM
Definition: CbcSymmetry.hpp:78
bool operator()(register const Node &a, register const Node &b)
Definition: CbcSymmetry.hpp:99
void deleteElement(int ix, int jx)
bool operator()(register const char *a, register const char *b) const
CbcRangeCompare
std::vector< std::vector< int > > * getOrbits() const
Returns the orbits in a &quot;convenient&quot; form.
void clearPartitions()
virtual double branch()
Does next branch and updates state.
Branching object for Orbital branching.
myclass index_sort
~CbcSymmetry()
Destructor.
void unsetWriteAutoms()
bool isSparse() const
void node(int, double, double, double, int, int)
void Compute_Symmetry() const
bool compare(register Node &a, register Node &b) const
Class to deal with symmetry.
double getGroupSize() const
void setWriteAutoms(const std::string &afilename)
Methods to classify orbits.
int way() const
Get the state of the branching object.
Abstract branching object base class Now just difference with OsiBranchingObject. ...
int numberUsefulOrbits() const
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child...
void getVstat(double *v, int nv)
virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap=false)
Compare the this with brObj.
CbcBranchObjType
void Print_Orbits() const
CbcOrbitalBranchingObject & operator=(const CbcOrbitalBranchingObject &rhs)
int get_color() const
Definition: CbcSymmetry.hpp:71
CbcModel * model() const
Return model.
virtual double branch()=0
Execute the actions required to branch, as specified by the current state of the branching object...
virtual CbcBranchObjType type() const
Return the type (an integer identifier) of this.
virtual void print() const
Print something about branch - only if log level high.
double get_lb() const
Definition: CbcSymmetry.hpp:69
double get_coeff() const
Definition: CbcSymmetry.hpp:68
void insertRHS(int rhs, int cons)
void color_vertex(register int k)
Definition: CbcSymmetry.hpp:66
~CbcNauty()
Destructor.
int statsOrbits(CbcModel *model, int type) const
CbcNauty & operator=(const CbcNauty &rhs)
Assignment operator.
int get_code() const
Definition: CbcSymmetry.hpp:72
int get_sign() const
Definition: CbcSymmetry.hpp:73
virtual int compareOriginalObject(const CbcBranchingObject *brObj) const
Compare the original object of this with the original object of brObj.
virtual void print()
Print something about branch - only if log level high.
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child...
virtual void fix(OsiSolverInterface *solver, double *lower, double *upper, int branchState) const
Update bounds in solver as in &#39;branch&#39; and update given bounds.
CbcSymmetry & operator=(const CbcSymmetry &rhs)
Assignment operator.
int orbitalFixing(OsiSolverInterface *solver)
Fixes variables using orbits (returns number fixed)
int largestOrbit(const double *lower, const double *upper) const
bool operator()(register const Node &a, register const Node &b)
Definition: CbcSymmetry.hpp:82
Simple Branch and bound class.
Definition: CbcModel.hpp:101
int getNumGenerators() const
std::vector< int > * Find_Orbit(int) const
int getN() const
CbcSymmetry()
Default constructor.
int numberUsefulObjects() const