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 |
---|
35 | extern "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 | |
---|
49 | class OsiObject; |
---|
50 | // when to give up (depth since last success) |
---|
51 | #ifndef NTY_BAD_DEPTH |
---|
52 | #define NTY_BAD_DEPTH 10 |
---|
53 | #endif |
---|
54 | class 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 | |
---|
104 | struct 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 | |
---|
114 | class 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); |
---|
164 | private: |
---|
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 | |
---|
173 | class CbcNauty |
---|
174 | { |
---|
175 | |
---|
176 | public: |
---|
177 | enum VarStatus { FIX_AT_ZERO, FIX_AT_ONE, FREE }; |
---|
178 | |
---|
179 | /**@name Constructors and destructors */ |
---|
180 | //@{ |
---|
181 | private: |
---|
182 | /// Default constructor |
---|
183 | CbcNauty (); |
---|
184 | public: |
---|
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 | |
---|
235 | private: |
---|
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 | */ |
---|
282 | class CbcOrbitalBranchingObject : public CbcBranchingObject { |
---|
283 | |
---|
284 | public: |
---|
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 | |
---|
352 | private: |
---|
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 |
---|