source: trunk/Cbc/src/CbcSymmetry.hpp

Last change on this file was 2491, checked in by forrest, 5 days ago

better SOS in mipstart, ctrl-c back, improve symmetric

File size: 10.2 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#define COUENNE_HACKED_EPS 1.e-07
57#define COUENNE_HACKED_EPS_SYMM 1e-8
58#define COUENNE_HACKED_EXPRGROUP 8
59
60/** Class to deal with symmetry
61 *
62 *  Hacked from Couenne
63 *  Thanks, but it had been nice to make sure that there are no symbol collisions when building Couenne with this Cbc.
64 */
65
66class 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
115public:
116  /**@name Constructors and destructors */
117  //@{
118  /// Default constructor
119  CbcSymmetry();
120
121  /// Copy constructor
122  CbcSymmetry(const CbcSymmetry &);
123
124  /// Assignment operator
125  CbcSymmetry &operator=(const CbcSymmetry &rhs);
126
127  /// Destructor
128  ~CbcSymmetry();
129  //@}
130
131  // Symmetry Info
132
133  std::vector< int > *Find_Orbit(int) const;
134
135  myclass0 node_sort;
136  myclass index_sort;
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();
143  /// Fixes variables using orbits (returns number fixed)
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;
161  CbcNauty *getNtyInfo() { return nauty_info_; }
162
163  // bool node_sort (  Node  a, Node  b);
164  // bool index_sort (  Node  a, Node  b);
165
166  /// empty if no NTY, symmetry data structure setup otherwise
167  void setupSymmetry(CbcModel * model);
168
169private:
170  mutable std::vector< Node > node_info_;
171  mutable CbcNauty *nauty_info_;
172  int numberColumns_;
173  int numberUsefulOrbits_;
174  int numberUsefulObjects_;
175  int *whichOrbit_;
176};
177
178class CbcNauty {
179
180public:
181  enum VarStatus { FIX_AT_ZERO,
182    FIX_AT_ONE,
183    FREE };
184
185  /**@name Constructors and destructors */
186  //@{
187private:
188  /// Default constructor
189  CbcNauty();
190
191public:
192  /// Normal constructor (if dense - NULLS)
193  CbcNauty(int n, const size_t *v, const int *d, const int *e);
194
195  /// Copy constructor
196  CbcNauty(const CbcNauty &);
197
198  /// Assignment operator
199  CbcNauty &operator=(const CbcNauty &rhs);
200
201  /// Destructor
202  ~CbcNauty();
203  //@}
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
221  /// Returns the orbits in a "convenient" form
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  /// Pointer to options
240  inline optionblk *options() const
241  {
242    return options_;
243  }
244  /**
245   * Methods to classify orbits.  Not horribly efficient, but gets the job done
246   */
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
257private:
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_;
273  int worksize_;
274  int m_;
275  int n_;
276  size_t nel_;
277  graph *canonG_;
278
279  bool autoComputed_;
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 >
291    ret;
292
293  // File pointer for automorphism group
294  FILE *afp_;
295};
296
297/** Branching object for Orbital branching
298
299    Variable_ is the set id number (redundant, as the object also holds a
300    pointer to the set.
301 */
302class CbcOrbitalBranchingObject : public CbcBranchingObject {
303
304public:
305  // Default Constructor
306  CbcOrbitalBranchingObject();
307
308  // Useful constructor
309  CbcOrbitalBranchingObject(CbcModel *model, int column,
310    int way,
311    int numberExtra, const int *extraToZero);
312
313  // Copy constructor
314  CbcOrbitalBranchingObject(const CbcOrbitalBranchingObject &);
315
316  // Assignment operator
317  CbcOrbitalBranchingObject &operator=(const CbcOrbitalBranchingObject &rhs);
318
319  /// Clone
320  virtual CbcBranchingObject *clone() const;
321
322  // Destructor
323  virtual ~CbcOrbitalBranchingObject();
324
325  using CbcBranchingObject::branch;
326  /// Does next branch and updates state
327  virtual double branch();
328  /** Update bounds in solver as in 'branch' and update given bounds.
329        branchState is -1 for 'down' +1 for 'up' */
330  virtual void fix(OsiSolverInterface *solver,
331    double *lower, double *upper,
332    int branchState) const;
333
334  /** Reset every information so that the branching object appears to point to
335        the previous child. This method does not need to modify anything in any
336        solver. */
337  virtual void previousBranch()
338  {
339    CbcBranchingObject::previousBranch();
340  }
341
342  using CbcBranchingObject::print;
343  /** \brief Print something about branch - only if log level high
344    */
345  virtual void print();
346
347  /** Return the type (an integer identifier) of \c this */
348  virtual CbcBranchObjType type() const
349  {
350    return SoSBranchObj;
351  }
352
353  /** Compare the original object of \c this with the original object of \c
354        brObj. Assumes that there is an ordering of the original objects.
355        This method should be invoked only if \c this and brObj are of the same
356        type.
357        Return negative/0/positive depending on whether \c this is
358        smaller/same/larger than the argument.
359    */
360  virtual int compareOriginalObject(const CbcBranchingObject *brObj) const;
361
362  /** Compare the \c this with \c brObj. \c this and \c brObj must be os the
363        same type and must have the same original object, but they may have
364        different feasible regions.
365        Return the appropriate CbcRangeCompare value (first argument being the
366        sub/superset if that's the case). In case of overlap (and if \c
367        replaceIfOverlap is true) replace the current branching object with one
368        whose feasible region is the overlap.
369     */
370  virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap = false);
371
372private:
373  /// Column to go to 1
374  int column_;
375  /// Number (without column) going to zero on down branch
376  int numberOther_;
377  /// Number extra
378  int numberExtra_;
379  /// Fix to zero
380  int *fixToZero_;
381};
382
383#endif
384
385/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
386*/
Note: See TracBrowser for help on using the repository browser.