Cbc  2.10.4
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:
118  CbcSymmetry();
120 
122  CbcSymmetry(const CbcSymmetry &);
123 
125  CbcSymmetry &operator=(const CbcSymmetry &rhs);
126 
128  ~CbcSymmetry();
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:
189  CbcNauty();
190 
191 public:
193  CbcNauty(int n, const size_t *v, const int *d, const int *e);
194 
196  CbcNauty(const CbcNauty &);
197 
199  CbcNauty &operator=(const CbcNauty &rhs);
200 
202  ~CbcNauty();
204 
205  void addElement(int ix, int jx);
206  void clearPartitions();
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
239  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);
255  void unsetWriteAutoms();
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
323  virtual ~CbcOrbitalBranchingObject();
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 */
CbcNauty::getOrbits
std::vector< std::vector< int > > * getOrbits() const
Returns the orbits in a "convenient" form.
CbcOrbitalBranchingObject::fix
virtual void fix(OsiSolverInterface *solver, double *lower, double *upper, int branchState) const
Update bounds in solver as in 'branch' and update given bounds.
CbcBranchingObject::way
int way() const
Get the state of the branching object.
Definition: CbcBranchingObject.hpp:157
SoSBranchObj
@ SoSBranchObj
Definition: CbcBranchingObject.hpp:22
CbcSymmetry::myclass::operator()
bool operator()(register const Node &a, register const Node &b)
Definition: CbcSymmetry.hpp:102
CbcSymmetry::Node::get_coeff
double get_coeff() const
Definition: CbcSymmetry.hpp:80
CbcSymmetry::whichOrbit_
int * whichOrbit_
Definition: CbcSymmetry.hpp:175
CbcSymmetry::operator=
CbcSymmetry & operator=(const CbcSymmetry &rhs)
Assignment operator.
CbcSymmetry::Node::node
void node(int, double, double, double, int, int)
CbcNauty::deleteElement
void deleteElement(int ix, int jx)
CbcNauty::autoComputed_
bool autoComputed_
Definition: CbcSymmetry.hpp:279
CbcSymmetry::orbitalFixing
int orbitalFixing(OsiSolverInterface *solver)
Fixes variables using orbits (returns number fixed)
CbcNauty
Definition: CbcSymmetry.hpp:178
CbcOrbitalBranchingObject::operator=
CbcOrbitalBranchingObject & operator=(const CbcOrbitalBranchingObject &rhs)
CbcNauty::constr_rhs
std::multimap< int, int > constr_rhs
Definition: CbcSymmetry.hpp:286
CbcOrbitalBranchingObject::numberExtra_
int numberExtra_
Number extra.
Definition: CbcSymmetry.hpp:378
CbcSymmetry::node_sort
myclass0 node_sort
Definition: CbcSymmetry.hpp:135
CbcBranchingObject::previousBranch
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child.
Definition: CbcBranchingObject.hpp:122
CbcSymmetry::CbcSymmetry
CbcSymmetry()
Default constructor.
CbcSymmetry::Node::coeff
double coeff
Definition: CbcSymmetry.hpp:69
CbcOrbitalBranchingObject::print
virtual void print()
Print something about branch - only if log level high.
CbcSymmetry::setupSymmetry
void setupSymmetry(CbcModel *model)
empty if no NTY, symmetry data structure setup otherwise
CbcNauty::addElement
void addElement(int ix, int jx)
CbcOrbitalBranchingObject::compareOriginalObject
virtual int compareOriginalObject(const CbcBranchingObject *brObj) const
Compare the original object of this with the original object of brObj.
CbcSymmetry::index_sort
myclass index_sort
Definition: CbcSymmetry.hpp:136
CbcSymmetry::Node::ub
double ub
Definition: CbcSymmetry.hpp:71
CbcBranchingObject::branch
virtual double branch()=0
Execute the actions required to branch, as specified by the current state of the branching object,...
CbcSymmetry::numberUsefulOrbits_
int numberUsefulOrbits_
Definition: CbcSymmetry.hpp:173
CbcSymmetry::compare
bool compare(register Node &a, register Node &b) const
CbcOrbitalBranchingObject::CbcOrbitalBranchingObject
CbcOrbitalBranchingObject()
CbcSymmetry::Find_Orbit
std::vector< int > * Find_Orbit(int) const
CbcNauty::VarStatus
VarStatus
Definition: CbcSymmetry.hpp:181
CbcSymmetry::less_than_str::operator()
bool operator()(register const char *a, register const char *b) const
Definition: CbcSymmetry.hpp:109
CbcSymmetry::Node::index
int index
Definition: CbcSymmetry.hpp:68
CbcModel.hpp
CbcSymmetry::fillOrbits
void fillOrbits()
CbcOrbitalBranchingObject::previousBranch
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child.
Definition: CbcSymmetry.hpp:337
CbcNauty::CbcNauty
CbcNauty()
Default constructor.
CbcNauty::lab_
int * lab_
Definition: CbcSymmetry.hpp:261
CbcNauty::GSparse_
sparsegraph * GSparse_
Definition: CbcSymmetry.hpp:260
CbcSymmetry::Node::get_index
int get_index() const
Definition: CbcSymmetry.hpp:79
CbcNauty::getGroupSize
double getGroupSize() const
CbcOrbitalBranchingObject::compareBranchingObject
virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap=false)
Compare the this with brObj.
CbcNauty::worksize_
int worksize_
Definition: CbcSymmetry.hpp:273
CbcNauty::clearPartitions
void clearPartitions()
CbcSymmetry::~CbcSymmetry
~CbcSymmetry()
Destructor.
CbcNauty::FREE
@ FREE
Definition: CbcSymmetry.hpp:183
CbcSymmetry::ChangeBounds
void ChangeBounds(const double *lower, const double *upper, int numberColumns, bool justFixedAtOne) const
CbcSymmetry::nauty_info_
CbcNauty * nauty_info_
Definition: CbcSymmetry.hpp:171
CbcSymmetry::Node::get_lb
double get_lb() const
Definition: CbcSymmetry.hpp:81
CbcSymmetry
Class to deal with symmetry.
Definition: CbcSymmetry.hpp:66
CbcNauty::unsetWriteAutoms
void unsetWriteAutoms()
CbcNauty::ret
std::pair< std::multimap< int, int >::iterator, std::multimap< int, int >::iterator > ret
Definition: CbcSymmetry.hpp:291
CbcNauty::errorStatus
int errorStatus() const
Definition: CbcSymmetry.hpp:229
CbcNauty::FIX_AT_ZERO
@ FIX_AT_ZERO
Definition: CbcSymmetry.hpp:181
CbcNauty::FIX_AT_ONE
@ FIX_AT_ONE
Definition: CbcSymmetry.hpp:182
CbcOrbitalBranchingObject
Branching object for Orbital branching.
Definition: CbcSymmetry.hpp:302
CbcSymmetry::Node::lb
double lb
Definition: CbcSymmetry.hpp:70
CbcSymmetry::Compute_Symmetry
void Compute_Symmetry() const
CbcSymmetry::Node::get_code
int get_code() const
Definition: CbcSymmetry.hpp:84
COUENNE_HACKED_EPS_SYMM
#define COUENNE_HACKED_EPS_SYMM
Definition: CbcSymmetry.hpp:57
CbcSymmetry::statsOrbits
int statsOrbits(CbcModel *model, int type) const
CbcNauty::stats_
statsblk * stats_
Definition: CbcSymmetry.hpp:267
CbcNauty::workspace_
setword * workspace_
Definition: CbcSymmetry.hpp:272
CbcSymmetry::Node
Definition: CbcSymmetry.hpp:67
CbcSymmetry::numberColumns_
int numberColumns_
Definition: CbcSymmetry.hpp:172
CbcNauty::setWriteAutoms
void setWriteAutoms(const std::string &afilename)
Methods to classify orbits.
CbcSymmetry::Node::color
int color
Definition: CbcSymmetry.hpp:72
CbcModel
Simple Branch and bound class.
Definition: CbcModel.hpp:100
CbcSymmetry::Node::get_sign
int get_sign() const
Definition: CbcSymmetry.hpp:85
CbcSymmetry::Node::sign
int sign
Definition: CbcSymmetry.hpp:74
CbcNauty::options
optionblk * options() const
Pointer to options.
Definition: CbcSymmetry.hpp:240
CbcSymmetry::Node::get_ub
double get_ub() const
Definition: CbcSymmetry.hpp:82
CbcNauty::nel_
size_t nel_
Definition: CbcSymmetry.hpp:276
CbcNauty::insertRHS
void insertRHS(int rhs, int cons)
Definition: CbcSymmetry.hpp:210
CbcSymmetry::myclass0
Definition: CbcSymmetry.hpp:93
CbcBranchingObject::print
virtual void print() const
Print something about branch - only if log level high.
Definition: CbcBranchingObject.hpp:132
CbcNauty::active_
set * active_
Definition: CbcSymmetry.hpp:263
CbcBranchingObject
Abstract branching object base class Now just difference with OsiBranchingObject.
Definition: CbcBranchingObject.hpp:51
CbcSymmetry::Node::code
int code
Definition: CbcSymmetry.hpp:73
CbcOrbitalBranchingObject::type
virtual CbcBranchObjType type() const
Return the type (an integer identifier) of this.
Definition: CbcSymmetry.hpp:348
CbcSymmetry::Node::bounds
void bounds(register double a, register double b)
Definition: CbcSymmetry.hpp:86
CbcSymmetry::Print_Orbits
void Print_Orbits() const
CbcSymmetry::Node::get_color
int get_color() const
Definition: CbcSymmetry.hpp:83
CbcNauty::getNumOrbits
int getNumOrbits() const
CbcNauty::~CbcNauty
~CbcNauty()
Destructor.
CbcOrbitalBranchingObject::branch
virtual double branch()
Does next branch and updates state.
CbcNauty::getVstat
void getVstat(double *v, int nv)
CbcNauty::it
std::multimap< int, int >::iterator it
Definition: CbcSymmetry.hpp:287
CbcNauty::getN
int getN() const
Definition: CbcSymmetry.hpp:216
CbcOrbitalBranchingObject::numberOther_
int numberOther_
Number (without column) going to zero on down branch.
Definition: CbcSymmetry.hpp:376
CbcSymmetry::numberUsefulObjects
int numberUsefulObjects() const
Definition: CbcSymmetry.hpp:153
CbcSymmetry::myclass
Definition: CbcSymmetry.hpp:101
CbcRangeCompare
CbcRangeCompare
Definition: CbcBranchBase.hpp:13
CbcSymmetry::Node::color_vertex
void color_vertex(register int k)
Definition: CbcSymmetry.hpp:78
CbcSymmetry::largestOrbit
int largestOrbit(const double *lower, const double *upper) const
CbcNauty::computeAuto
void computeAuto()
CbcNauty::operator=
CbcNauty & operator=(const CbcNauty &rhs)
Assignment operator.
CbcSymmetry::node_info_
std::vector< Node > node_info_
Definition: CbcSymmetry.hpp:170
CbcNauty::canonG_
graph * canonG_
Definition: CbcSymmetry.hpp:277
CbcNauty::getNumGenerators
int getNumGenerators() const
CbcNauty::color_node
void color_node(int ix, int color)
Definition: CbcSymmetry.hpp:209
CbcNauty::orbits_
int * orbits_
Definition: CbcSymmetry.hpp:264
CbcNauty::ptn_
int * ptn_
Definition: CbcSymmetry.hpp:262
CbcBranchObjType
CbcBranchObjType
Definition: CbcBranchingObject.hpp:17
CbcNauty::vstat_
int * vstat_
Definition: CbcSymmetry.hpp:281
CbcOrbitalBranchingObject::fixToZero_
int * fixToZero_
Fix to zero.
Definition: CbcSymmetry.hpp:380
CbcBranchingObject::model
CbcModel * model() const
Return model.
Definition: CbcBranchingObject.hpp:177
CbcOrbitalBranchingObject::column_
int column_
Column to go to 1.
Definition: CbcSymmetry.hpp:374
CbcOrbitalBranchingObject::clone
virtual CbcBranchingObject * clone() const
Clone.
CbcNauty::G_
graph * G_
Definition: CbcSymmetry.hpp:259
CbcNauty::n_
int n_
Definition: CbcSymmetry.hpp:275
CbcSymmetry::myclass0::operator()
bool operator()(register const Node &a, register const Node &b)
Definition: CbcSymmetry.hpp:94
CbcSymmetry::numberUsefulObjects_
int numberUsefulObjects_
Definition: CbcSymmetry.hpp:174
CbcNauty::afp_
FILE * afp_
Definition: CbcSymmetry.hpp:294
CbcSymmetry::numberUsefulOrbits
int numberUsefulOrbits() const
Definition: CbcSymmetry.hpp:149
CbcNauty::m_
int m_
Definition: CbcSymmetry.hpp:274
CbcNauty::options_
optionblk * options_
Definition: CbcSymmetry.hpp:266
CbcSymmetry::getNtyInfo
CbcNauty * getNtyInfo()
Definition: CbcSymmetry.hpp:161
CbcOrbitalBranchingObject::~CbcOrbitalBranchingObject
virtual ~CbcOrbitalBranchingObject()
CbcSymmetry::whichOrbit
int * whichOrbit()
Definition: CbcSymmetry.hpp:145
CbcSymmetry::less_than_str
Definition: CbcSymmetry.hpp:108
CbcNauty::isSparse
bool isSparse() const
Definition: CbcSymmetry.hpp:225