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

Last change on this file since 2092 was 2092, checked in by forrest, 4 years ago

symmetry and diving

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