source: stable/2.9/Cbc/src/CbcSymmetry.hpp @ 2208

Last change on this file since 2208 was 2208, checked in by stefan, 3 years ago

merge r2207 from trunk

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  { return stats_->errstatus;}
225  /**
226   * Methods to classify orbits.  Not horribly efficient, but gets the job done
227   */
228  //  bool isAllFixOneOrbit(const std::vector<int> &orbit) const;
229  // bool isAllFreeOrbit(const std::vector<int> &orbit) const;
230  //bool isAutoComputed() const { return autoComputed_; }
231  //bool isConstraintOrbit(const std::vector<int> &orbit) const;
232  //bool isMixedFreeZeroOrbit(const std::vector<int> &orbit) const;
233  //void makeFree(int ix) { vstat_[ix] = FREE; } 
234
235  void setWriteAutoms (const std::string &afilename);
236  void unsetWriteAutoms();
237
238private:
239
240  // The base nauty stuff
241  graph *G_;
242  sparsegraph *GSparse_;
243  int *lab_;
244  int *ptn_;
245  set *active_;
246  int *orbits_;
247#ifndef NTY_TRACES
248  optionblk *options_;
249  statsblk *stats_;
250#else
251  TracesOptions *options_;
252  TracesStats *stats_;
253#endif
254  setword *workspace_;
255  int worksize_;
256  int m_;
257  int n_;
258  size_t nel_;
259  graph *canonG_;
260 
261  bool autoComputed_;
262
263  int *vstat_;
264
265  //static int nautyCalls_;
266  //static double nautyTime_;
267
268  std::multimap<int,int> constr_rhs;
269  std::multimap<int,int>::iterator it;
270
271  std::pair<std::multimap<int,int>::iterator,
272            std::multimap<int,int>::iterator> ret;
273
274  // File pointer for automorphism group
275  FILE *afp_;
276
277};
278
279
280/** Branching object for Orbital branching
281
282    Variable_ is the set id number (redundant, as the object also holds a
283    pointer to the set.
284 */
285class CbcOrbitalBranchingObject : public CbcBranchingObject {
286
287public:
288
289    // Default Constructor
290    CbcOrbitalBranchingObject ();
291
292    // Useful constructor
293    CbcOrbitalBranchingObject (CbcModel * model,  int column,
294                               int way,
295                               int numberExtra, const int * extraToZero);
296
297    // Copy constructor
298    CbcOrbitalBranchingObject ( const CbcOrbitalBranchingObject &);
299
300    // Assignment operator
301    CbcOrbitalBranchingObject & operator=( const CbcOrbitalBranchingObject& rhs);
302
303    /// Clone
304    virtual CbcBranchingObject * clone() const;
305
306    // Destructor
307    virtual ~CbcOrbitalBranchingObject ();
308
309    using CbcBranchingObject::branch ;
310    /// Does next branch and updates state
311    virtual double branch();
312    /** Update bounds in solver as in 'branch' and update given bounds.
313        branchState is -1 for 'down' +1 for 'up' */
314    virtual void fix(OsiSolverInterface * solver,
315                     double * lower, double * upper,
316                     int branchState) const ;
317
318    /** Reset every information so that the branching object appears to point to
319        the previous child. This method does not need to modify anything in any
320        solver. */
321    virtual void previousBranch() {
322        CbcBranchingObject::previousBranch();
323    }
324
325    using CbcBranchingObject::print ;
326    /** \brief Print something about branch - only if log level high
327    */
328    virtual void print();
329
330    /** Return the type (an integer identifier) of \c this */
331    virtual CbcBranchObjType type() const {
332        return SoSBranchObj;
333    }
334
335    /** Compare the original object of \c this with the original object of \c
336        brObj. Assumes that there is an ordering of the original objects.
337        This method should be invoked only if \c this and brObj are of the same
338        type.
339        Return negative/0/positive depending on whether \c this is
340        smaller/same/larger than the argument.
341    */
342    virtual int compareOriginalObject(const CbcBranchingObject* brObj) const;
343
344    /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
345        same type and must have the same original object, but they may have
346        different feasible regions.
347        Return the appropriate CbcRangeCompare value (first argument being the
348        sub/superset if that's the case). In case of overlap (and if \c
349        replaceIfOverlap is true) replace the current branching object with one
350        whose feasible region is the overlap.
351     */
352    virtual CbcRangeCompare compareBranchingObject
353    (const CbcBranchingObject* brObj, const bool replaceIfOverlap = false);
354
355private:
356    /// Column to go to 1
357    int column_;
358    /// Number (without column) going to zero on down branch
359    int numberOther_;
360    /// Number extra
361    int numberExtra_;
362    /// Fix to zero
363    int * fixToZero_;
364};
365
366#endif
Note: See TracBrowser for help on using the repository browser.