Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups 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 
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 
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 
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;
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_;
173  int * whichOrbit_;
174 };
175 
176 class CbcNauty
177 {
178 
179 public:
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_;
256  int m_;
257  int n_;
258  size_t nel_;
259  graph *canonG_;
260 
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
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 
353  (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
354 
355 private:
357  int column_;
363  int * fixToZero_;
364 };
365 
366 #endif
CbcNauty * getNtyInfo()
int get_index() const
Definition: CbcSymmetry.hpp:81
void setupSymmetry(const OsiSolverInterface &solver)
empty if no NTY, symmetry data structure setup otherwise
myclass0 node_sort
void color_node(int ix, int color)
virtual ~CbcOrbitalBranchingObject()
void computeAuto()
void addElement(int ix, int jx)
int * orbits_
virtual CbcBranchingObject * clone() const
Clone.
int * whichOrbit_
bool operator()(register const char *a, register const char *b) const
std::multimap< int, int > constr_rhs
int errorStatus() const
graph * G_
int numberUsefulOrbits_
int * whichOrbit()
size_t nel_
void ChangeBounds(const double *lower, const double *upper, int numberColumns, bool justFixedAtOne) const
int getNumOrbits() const
bool autoComputed_
void fillOrbits()
#define COUENNE_HACKED_EPS_SYMM
Definition: CbcSymmetry.hpp:59
int get_sign() const
Definition: CbcSymmetry.hpp:87
void color_vertex(register int k)
Definition: CbcSymmetry.hpp:80
setword * workspace_
sparsegraph * GSparse_
void deleteElement(int ix, int jx)
CbcRangeCompare
std::vector< std::vector< int > > * getOrbits() const
Returns the orbits in a &quot;convenient&quot; form.
void clearPartitions()
std::multimap< int, int >::iterator it
virtual double branch()
Does next branch and updates state.
Branching object for Orbital branching.
myclass index_sort
optionblk * options_
~CbcSymmetry()
Destructor.
double get_coeff() const
Definition: CbcSymmetry.hpp:82
Abstract Base Class for describing an interface to a solver.
void unsetWriteAutoms()
bool isSparse() const
void Compute_Symmetry() const
bool compare(register Node &a, register Node &b) const
graph * canonG_
statsblk * stats_
Class to deal with symmetry.
Definition: CbcSymmetry.hpp:69
double getGroupSize() const
int * lab_
int * fixToZero_
Fix to zero.
void setWriteAutoms(const std::string &afilename)
Methods to classify orbits.
CbcNauty * nauty_info_
int get_code() const
Definition: CbcSymmetry.hpp:86
int way() const
Get the state of the branching object.
Abstract branching object base class Now just difference with OsiBranchingObject. ...
void bounds(register double a, register double b)
Definition: CbcSymmetry.hpp:88
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.
void node(int, double, double, double, int, int)
int get_color() const
Definition: CbcSymmetry.hpp:85
int column_
Column to go to 1.
CbcBranchObjType
void Print_Orbits() const
CbcOrbitalBranchingObject & operator=(const CbcOrbitalBranchingObject &rhs)
set * active_
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.
std::vector< Node > node_info_
virtual void print() const
Print something about branch - only if log level high.
void insertRHS(int rhs, int cons)
std::pair< std::multimap< int, int >::iterator, std::multimap< int, int >::iterator > ret
int numberOther_
Number (without column) going to zero on down branch.
int * ptn_
~CbcNauty()
Destructor.
int numberExtra_
Number extra.
int * vstat_
int statsOrbits(CbcModel *model, int type) const
double get_ub() const
Definition: CbcSymmetry.hpp:84
CbcNauty & operator=(const CbcNauty &rhs)
Assignment operator.
bool operator()(register const Node &a, register const Node &b)
Definition: CbcSymmetry.hpp:92
virtual int compareOriginalObject(const CbcBranchingObject *brObj) const
Compare the original object of this with the original object of brObj.
int numberUsefulObjects_
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)
Abstract base class for `objects&#39;.
int largestOrbit(const double *lower, const double *upper) const
Simple Branch and bound class.
Definition: CbcModel.hpp:101
FILE * afp_
int getNumGenerators() const
double get_lb() const
Definition: CbcSymmetry.hpp:83
std::vector< int > * Find_Orbit(int) const
int getN() const
CbcSymmetry()
Default constructor.
CbcNauty()
Default constructor.
int numberUsefulObjects() const
bool operator()(register const Node &a, register const Node &b)