Cbc  2.10.5
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 #define COUENNE_HACKED_EPS 1.e-07
57 #define COUENNE_HACKED_EPS_SYMM 1e-8
58 #define COUENNE_HACKED_EXPRGROUP 8
59 
66 class CbcSymmetry {
67  class Node {
68  int index;
69  double coeff;
70  double lb;
71  double ub;
72  int color;
73  int code;
74  int sign;
75 
76  public:
77  void node(int, double, double, double, int, int);
78  inline void color_vertex(register int k) { color = k; }
79  inline int get_index() const { return index; }
80  inline double get_coeff() const { return coeff; }
81  inline double get_lb() const { return lb; }
82  inline double get_ub() const { return ub; }
83  inline int get_color() const { return color; }
84  inline int get_code() const { return code; }
85  inline int get_sign() const { return sign; }
86  inline void bounds(register double a, register double b)
87  {
88  lb = a;
89  ub = b;
90  }
91  };
92 
93  struct myclass0 {
94  inline bool operator()(register const Node &a, register const Node &b)
95  {
96 
97  return ((a.get_code() < b.get_code()) || ((a.get_code() == b.get_code() && ((a.get_coeff() < b.get_coeff() - COUENNE_HACKED_EPS_SYMM) || ((fabs(a.get_coeff() - b.get_coeff()) < COUENNE_HACKED_EPS_SYMM) && ((a.get_lb() < b.get_lb() - COUENNE_HACKED_EPS_SYMM) || ((fabs(a.get_lb() - b.get_lb()) < COUENNE_HACKED_EPS_SYMM) && ((a.get_ub() < b.get_ub() - COUENNE_HACKED_EPS_SYMM) || ((fabs(a.get_ub() - b.get_ub()) < COUENNE_HACKED_EPS_SYMM) && ((a.get_index() < b.get_index())))))))))));
98  }
99  };
100 
101  struct myclass {
102  inline bool operator()(register const Node &a, register const Node &b)
103  {
104  return (a.get_index() < b.get_index());
105  }
106  };
107 
108  struct less_than_str {
109  inline bool operator()(register const char *a, register const char *b) const
110  {
111  return strcmp(a, b) < 0;
112  }
113  };
114 
115 public:
120 
123 
126 
130 
131  // Symmetry Info
132 
133  std::vector< int > *Find_Orbit(int) const;
134 
137 
138  void Compute_Symmetry() const;
139  int statsOrbits(CbcModel *model, int type) const;
140  //double timeNauty () const;
141  void Print_Orbits() const;
142  void fillOrbits();
144  int orbitalFixing(OsiSolverInterface *solver);
145  inline int *whichOrbit()
146  {
147  return numberUsefulOrbits_ ? whichOrbit_ : NULL;
148  }
149  inline int numberUsefulOrbits() const
150  {
151  return numberUsefulOrbits_;
152  }
153  inline int numberUsefulObjects() const
154  {
155  return numberUsefulObjects_;
156  }
157  int largestOrbit(const double *lower, const double *upper) const;
158  void ChangeBounds(const double *lower, const double *upper,
159  int numberColumns, bool justFixedAtOne) const;
160  inline bool compare(register Node &a, register Node &b) const;
162 
163  // bool node_sort ( Node a, Node b);
164  // bool index_sort ( Node a, Node b);
165 
167  void setupSymmetry(CbcModel * model);
168 
169 private:
170  mutable std::vector< Node > node_info_;
176 };
177 
178 class CbcNauty {
179 
180 public:
183  FREE };
184 
187 private:
190 
191 public:
193  CbcNauty(int n, const size_t *v, const int *d, const int *e);
194 
196  CbcNauty(const CbcNauty &);
197 
200 
204 
205  void addElement(int ix, int jx);
207  void computeAuto();
208  void deleteElement(int ix, int jx);
209  void color_node(int ix, int color) { vstat_[ix] = color; }
210  void insertRHS(int rhs, int cons) { constr_rhs.insert(std::pair< int, int >(rhs, cons)); }
211 
212  double getGroupSize() const;
213  //int getNautyCalls() const { return nautyCalls_; }
214  //double getNautyTime() const { return nautyTime_; }
215 
216  int getN() const { return n_; }
217 
218  int getNumGenerators() const;
219  int getNumOrbits() const;
220 
222  std::vector< std::vector< int > > *getOrbits() const;
223 
224  void getVstat(double *v, int nv);
225  inline bool isSparse() const
226  {
227  return GSparse_ != NULL;
228  }
229  inline int errorStatus() const
230 #ifndef NTY_TRACES
231  {
232  return stats_->errstatus;
233  }
234 #else
235  {
236  return 0;
237  }
238 #endif
240  inline optionblk *options() const
241  {
242  return options_;
243  }
247  // bool isAllFixOneOrbit(const std::vector<int> &orbit) const;
248  // bool isAllFreeOrbit(const std::vector<int> &orbit) const;
249  //bool isAutoComputed() const { return autoComputed_; }
250  //bool isConstraintOrbit(const std::vector<int> &orbit) const;
251  //bool isMixedFreeZeroOrbit(const std::vector<int> &orbit) const;
252  //void makeFree(int ix) { vstat_[ix] = FREE; }
253 
254  void setWriteAutoms(const std::string &afilename);
256 
257 private:
258  // The base nauty stuff
259  graph *G_;
260  sparsegraph *GSparse_;
261  int *lab_;
262  int *ptn_;
263  set *active_;
264  int *orbits_;
265 #ifndef NTY_TRACES
266  optionblk *options_;
267  statsblk *stats_;
268 #else
269  TracesOptions *options_;
270  TracesStats *stats_;
271 #endif
272  setword *workspace_;
274  int m_;
275  int n_;
276  size_t nel_;
277  graph *canonG_;
278 
280 
281  int *vstat_;
282 
283  //static int nautyCalls_;
284  //static double nautyTime_;
285 
286  std::multimap< int, int > constr_rhs;
287  std::multimap< int, int >::iterator it;
288 
289  std::pair< std::multimap< int, int >::iterator,
290  std::multimap< int, int >::iterator >
292 
293  // File pointer for automorphism group
294  FILE *afp_;
295 };
296 
303 
304 public:
305  // Default Constructor
307 
308  // Useful constructor
310  int way,
311  int numberExtra, const int *extraToZero);
312 
313  // Copy constructor
315 
316  // Assignment operator
318 
320  virtual CbcBranchingObject *clone() const;
321 
322  // Destructor
324 
327  virtual double branch();
330  virtual void fix(OsiSolverInterface *solver,
331  double *lower, double *upper,
332  int branchState) const;
333 
337  virtual void previousBranch()
338  {
340  }
341 
345  virtual void print();
346 
348  virtual CbcBranchObjType type() const
349  {
350  return SoSBranchObj;
351  }
352 
360  virtual int compareOriginalObject(const CbcBranchingObject *brObj) const;
361 
370  virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap = false);
371 
372 private:
374  int column_;
381 };
382 
383 #endif
384 
385 /* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
386 */
CbcRangeCompare
CbcBranchObjType
@ SoSBranchObj
#define COUENNE_HACKED_EPS_SYMM
Definition: CbcSymmetry.hpp:57
Abstract branching object base class Now just difference with OsiBranchingObject.
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child.
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,...
int way() const
Get the state of the branching object.
virtual void print() const
Print something about branch - only if log level high.
Simple Branch and bound class.
Definition: CbcModel.hpp:100
bool autoComputed_
CbcNauty & operator=(const CbcNauty &rhs)
Assignment operator.
int getNumOrbits() const
void addElement(int ix, int jx)
CbcNauty()
Default constructor.
sparsegraph * GSparse_
void color_node(int ix, int color)
statsblk * stats_
void unsetWriteAutoms()
FILE * afp_
int * orbits_
graph * G_
void getVstat(double *v, int nv)
CbcNauty(int n, const size_t *v, const int *d, const int *e)
Normal constructor (if dense - NULLS)
int * lab_
void insertRHS(int rhs, int cons)
int getNumGenerators() const
std::vector< std::vector< int > > * getOrbits() const
Returns the orbits in a "convenient" form.
CbcNauty(const CbcNauty &)
Copy constructor.
bool isSparse() const
void computeAuto()
std::multimap< int, int > constr_rhs
int errorStatus() const
optionblk * options_
void deleteElement(int ix, int jx)
int getN() const
int * ptn_
graph * canonG_
~CbcNauty()
Destructor.
optionblk * options() const
Pointer to options.
void setWriteAutoms(const std::string &afilename)
Methods to classify orbits.
size_t nel_
std::pair< std::multimap< int, int >::iterator, std::multimap< int, int >::iterator > ret
set * active_
int * vstat_
double getGroupSize() const
void clearPartitions()
std::multimap< int, int >::iterator it
setword * workspace_
Branching object for Orbital branching.
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child.
virtual ~CbcOrbitalBranchingObject()
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 CbcBranchObjType type() const
Return the type (an integer identifier) of this.
virtual double branch()
Does next branch and updates state.
virtual CbcBranchingObject * clone() const
Clone.
int column_
Column to go to 1.
int numberOther_
Number (without column) going to zero on down branch.
int numberExtra_
Number extra.
int * fixToZero_
Fix to zero.
CbcOrbitalBranchingObject(CbcModel *model, int column, int way, int numberExtra, const int *extraToZero)
virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap=false)
Compare the this with brObj.
virtual void fix(OsiSolverInterface *solver, double *lower, double *upper, int branchState) const
Update bounds in solver as in 'branch' and update given bounds.
CbcOrbitalBranchingObject(const CbcOrbitalBranchingObject &)
CbcOrbitalBranchingObject & operator=(const CbcOrbitalBranchingObject &rhs)
double get_ub() const
Definition: CbcSymmetry.hpp:82
void bounds(register double a, register double b)
Definition: CbcSymmetry.hpp:86
int get_code() const
Definition: CbcSymmetry.hpp:84
double get_coeff() const
Definition: CbcSymmetry.hpp:80
int get_color() const
Definition: CbcSymmetry.hpp:83
int get_sign() const
Definition: CbcSymmetry.hpp:85
void color_vertex(register int k)
Definition: CbcSymmetry.hpp:78
double get_lb() const
Definition: CbcSymmetry.hpp:81
int get_index() const
Definition: CbcSymmetry.hpp:79
void node(int, double, double, double, int, int)
Class to deal with symmetry.
Definition: CbcSymmetry.hpp:66
CbcNauty * nauty_info_
int numberUsefulOrbits() const
bool compare(register Node &a, register Node &b) const
std::vector< Node > node_info_
int numberUsefulObjects() const
int * whichOrbit()
myclass0 node_sort
CbcSymmetry()
Default constructor.
int numberUsefulObjects_
int statsOrbits(CbcModel *model, int type) const
CbcSymmetry & operator=(const CbcSymmetry &rhs)
Assignment operator.
myclass index_sort
void Print_Orbits() const
int orbitalFixing(OsiSolverInterface *solver)
Fixes variables using orbits (returns number fixed)
void ChangeBounds(const double *lower, const double *upper, int numberColumns, bool justFixedAtOne) const
void fillOrbits()
int largestOrbit(const double *lower, const double *upper) const
CbcSymmetry(const CbcSymmetry &)
Copy constructor.
void Compute_Symmetry() const
int * whichOrbit_
~CbcSymmetry()
Destructor.
int numberUsefulOrbits_
std::vector< int > * Find_Orbit(int) const
CbcNauty * getNtyInfo()
void setupSymmetry(CbcModel *model)
empty if no NTY, symmetry data structure setup otherwise
bool operator()(register const char *a, register const char *b) const
bool operator()(register const Node &a, register const Node &b)
Definition: CbcSymmetry.hpp:94
bool operator()(register const Node &a, register const Node &b)