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 | #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 | |
---|
66 | class 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 | |
---|
115 | public: |
---|
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 | |
---|
169 | private: |
---|
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 | |
---|
178 | class CbcNauty { |
---|
179 | |
---|
180 | public: |
---|
181 | enum VarStatus { FIX_AT_ZERO, |
---|
182 | FIX_AT_ONE, |
---|
183 | FREE }; |
---|
184 | |
---|
185 | /**@name Constructors and destructors */ |
---|
186 | //@{ |
---|
187 | private: |
---|
188 | /// Default constructor |
---|
189 | CbcNauty(); |
---|
190 | |
---|
191 | public: |
---|
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 | |
---|
257 | private: |
---|
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 | */ |
---|
302 | class CbcOrbitalBranchingObject : public CbcBranchingObject { |
---|
303 | |
---|
304 | public: |
---|
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 | |
---|
372 | private: |
---|
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 | */ |
---|