source: trunk/Cbc/src/CbcSymmetry.hpp @ 2081

Last change on this file since 2081 was 2049, checked in by forrest, 5 years ago

oops forgot to add files

File size: 10.1 KB
Line 
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
35extern "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
49class OsiObject;
50// when to give up (depth since last success)
51#ifndef NTY_BAD_DEPTH
52#define NTY_BAD_DEPTH 10
53#endif
54class 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
104struct less_than_str {
105  inline bool operator() (register const  char *a, register const char *b) const
106  {return strcmp (a, b) < 0;}
107};
108
109/** Class to deal with symmetry
110 *
111 *  Hacked from Couenne
112 */
113
114class CbcSymmetry {
115
116 public:
117
118  /**@name Constructors and destructors */
119  //@{
120  /// Default constructor
121  CbcSymmetry ();
122 
123  /// Copy constructor
124  CbcSymmetry (const CbcSymmetry &);
125 
126  /// Assignment operator
127  CbcSymmetry & operator=(const CbcSymmetry& rhs);
128 
129  /// Destructor
130  ~CbcSymmetry ();
131  //@}
132 
133  // Symmetry Info
134
135  std::vector<int>  *Find_Orbit(int) const;
136
137  myclass0  node_sort; 
138  myclass index_sort;
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();
145  /// Fixes variables using orbits (returns number fixed)
146  int orbitalFixing(OsiSolverInterface * solver);
147  inline int * whichOrbit()
148  { return numberUsefulOrbits_ ? whichOrbit_ : NULL;}
149  inline int numberUsefulObjects() const
150  { return numberUsefulOrbits_;}
151  int largestOrbit(const double * lower, const double * upper) const;
152  void ChangeBounds (const double * lower, const double * upper, 
153                     int numberColumns,bool justFixedAtOne) const;
154  inline bool compare (register Node &a, register Node &b) const;
155  CbcNauty *getNtyInfo () {return nauty_info_;}
156
157  // bool node_sort (  Node  a, Node  b);
158  // bool index_sort (  Node  a, Node  b);
159
160  /// empty if no NTY, symmetry data structure setup otherwise
161  void setupSymmetry (const OsiSolverInterface & solver);
162private:
163  mutable std::vector<Node> node_info_;
164  mutable CbcNauty *nauty_info_;
165  int numberColumns_;
166  int numberUsefulOrbits_;
167  int * whichOrbit_;
168};
169
170class CbcNauty
171{
172
173public:
174  enum VarStatus { FIX_AT_ZERO, FIX_AT_ONE, FREE };
175 
176  /**@name Constructors and destructors */
177  //@{
178private:
179  /// Default constructor
180  CbcNauty ();
181public: 
182  /// Normal constructor (if dense - NULLS)
183  CbcNauty (int n, const size_t * v, const int * d, const int * e);
184 
185  /// Copy constructor
186  CbcNauty (const CbcNauty &);
187 
188  /// Assignment operator
189  CbcNauty & operator=(const CbcNauty& rhs);
190 
191  /// Destructor
192  ~CbcNauty ();
193  //@}
194
195  void addElement(int ix, int jx);
196  void clearPartitions();
197  void computeAuto();
198  void deleteElement(int ix, int jx);
199  void color_node(int ix, int color) { vstat_[ix] = color; }
200  void insertRHS(int rhs , int cons) {constr_rhs.insert( std::pair<int,int>(rhs,cons));}
201 
202  double getGroupSize() const;
203  //int getNautyCalls() const { return nautyCalls_; }
204  //double getNautyTime() const { return nautyTime_; }
205
206  int getN() const { return n_; }
207 
208  int getNumGenerators() const;
209  int getNumOrbits() const;
210
211  /// Returns the orbits in a "convenient" form
212  std::vector<std::vector<int> > *getOrbits() const;
213
214  void getVstat(double *v, int nv);
215  inline bool isSparse() const
216  { return GSparse_ != NULL;}
217
218  /**
219   * Methods to classify orbits.  Not horribly efficient, but gets the job done
220   */
221  //  bool isAllFixOneOrbit(const std::vector<int> &orbit) const;
222  // bool isAllFreeOrbit(const std::vector<int> &orbit) const;
223  //bool isAutoComputed() const { return autoComputed_; }
224  //bool isConstraintOrbit(const std::vector<int> &orbit) const;
225  //bool isMixedFreeZeroOrbit(const std::vector<int> &orbit) const;
226  //void makeFree(int ix) { vstat_[ix] = FREE; } 
227
228  void setWriteAutoms (const std::string &afilename);
229  void unsetWriteAutoms();
230
231private:
232
233  // The base nauty stuff
234  graph *G_;
235  sparsegraph *GSparse_;
236  int *lab_;
237  int *ptn_;
238  set *active_;
239  int *orbits_;
240#ifndef NTY_TRACES
241  optionblk *options_;
242  statsblk *stats_;
243#else
244  TracesOptions *options_;
245  TracesStats *stats_;
246#endif
247  setword *workspace_;
248  int worksize_;
249  int m_;
250  int n_;
251  size_t nel_;
252  graph *canonG_;
253 
254  bool autoComputed_;
255
256  int *vstat_;
257
258  //static int nautyCalls_;
259  //static double nautyTime_;
260
261  std::multimap<int,int> constr_rhs;
262  std::multimap<int,int>::iterator it;
263
264  std::pair<std::multimap<int,int>::iterator,
265            std::multimap<int,int>::iterator> ret;
266
267  // File pointer for automorphism group
268  FILE *afp_;
269
270};
271
272
273/** Branching object for Orbital branching
274
275    Variable_ is the set id number (redundant, as the object also holds a
276    pointer to the set.
277 */
278class CbcOrbitalBranchingObject : public CbcBranchingObject {
279
280public:
281
282    // Default Constructor
283    CbcOrbitalBranchingObject ();
284
285    // Useful constructor
286    CbcOrbitalBranchingObject (CbcModel * model,  int column,
287                               int way,
288                               int numberExtra, const int * extraToZero);
289
290    // Copy constructor
291    CbcOrbitalBranchingObject ( const CbcOrbitalBranchingObject &);
292
293    // Assignment operator
294    CbcOrbitalBranchingObject & operator=( const CbcOrbitalBranchingObject& rhs);
295
296    /// Clone
297    virtual CbcBranchingObject * clone() const;
298
299    // Destructor
300    virtual ~CbcOrbitalBranchingObject ();
301
302    using CbcBranchingObject::branch ;
303    /// Does next branch and updates state
304    virtual double branch();
305    /** Update bounds in solver as in 'branch' and update given bounds.
306        branchState is -1 for 'down' +1 for 'up' */
307    virtual void fix(OsiSolverInterface * solver,
308                     double * lower, double * upper,
309                     int branchState) const ;
310
311    /** Reset every information so that the branching object appears to point to
312        the previous child. This method does not need to modify anything in any
313        solver. */
314    virtual void previousBranch() {
315        CbcBranchingObject::previousBranch();
316    }
317
318    using CbcBranchingObject::print ;
319    /** \brief Print something about branch - only if log level high
320    */
321    virtual void print();
322
323    /** Return the type (an integer identifier) of \c this */
324    virtual CbcBranchObjType type() const {
325        return SoSBranchObj;
326    }
327
328    /** Compare the original object of \c this with the original object of \c
329        brObj. Assumes that there is an ordering of the original objects.
330        This method should be invoked only if \c this and brObj are of the same
331        type.
332        Return negative/0/positive depending on whether \c this is
333        smaller/same/larger than the argument.
334    */
335    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
336
337    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
338        same type and must have the same original object, but they may have
339        different feasible regions.
340        Return the appropriate CbcRangeCompare value (first argument being the
341        sub/superset if that's the case). In case of overlap (and if \c
342        replaceIfOverlap is true) replace the current branching object with one
343        whose feasible region is the overlap.
344     */
345    virtual CbcRangeCompare compareBranchingObject
346    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
347
348private:
349    /// Column to go to 1
350    int column_;
351    /// Number (without column) going to zero on down branch
352    int numberOther_;
353    /// Number extra
354    int numberExtra_;
355    /// Fix to zero
356    int * fixToZero_;
357};
358
359#endif
Note: See TracBrowser for help on using the repository browser.