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

Last change on this file since 2280 was 2280, checked in by forrest, 3 years ago

allow heuristics to see if integers are 'optional'

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