Cbc 2.10.12
Loading...
Searching...
No Matches
CbcSymmetry.hpp
Go to the documentation of this file.
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 */
28#ifndef CBC_SYMMETRY_HPP
29#define CBC_SYMMETRY_HPP
30
31#include "CbcConfig.h"
32
33#ifdef COIN_HAS_NTY
34extern "C" {
35#include "nauty/nauty.h"
36#include "nauty/nausparse.h"
37#ifdef NTY_TRACES
38#include "nauty/traces.h"
39#endif
40}
41#endif
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 4
53#endif
54class CbcNauty;
55typedef struct {
58 int * orbits;
60
61#define COUENNE_HACKED_EPS 1.e-07
62#define COUENNE_HACKED_EPS_SYMM 1e-8
63#define COUENNE_HACKED_EXPRGROUP 8
64
70
72 class Node {
73 int index;
74 double coeff;
75 double lb;
76 double ub;
77 int color;
78 int code;
79 int sign;
80
81 public:
82 void node(int, double, double, double, int, int);
83 inline void color_vertex(int k) { color = k; }
84 inline int get_index() const { return index; }
85 inline double get_coeff() const { return coeff; }
86 inline double get_lb() const { return lb; }
87 inline double get_ub() const { return ub; }
88 inline int get_color() const { return color; }
89 inline int get_code() const { return code; }
90 inline int get_sign() const { return sign; }
91 inline void bounds(double a, double b)
92 {
93 lb = a;
94 ub = b;
95 }
96 };
97
98 struct myclass0 {
99 inline bool operator()(const Node &a, const Node &b)
100 {
101
102 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())))))))))));
103 }
104 };
105
106 struct myclass {
107 inline bool operator()(const Node &a, const Node &b)
108 {
109 return (a.get_index() < b.get_index());
110 }
111 };
112
114 inline bool operator()(const char *a, const char *b) const
115 {
116 return strcmp(a, b) < 0;
117 }
118 };
119
120public:
123
125
128
131
135
136 // Symmetry Info
137
138 std::vector< int > *Find_Orbit(int) const;
139
142
143 void Compute_Symmetry() const;
144 int statsOrbits(CbcModel *model, int type) const;
145 //double timeNauty () const;
146 void Print_Orbits(int type=0) const;
149 int orbitalFixing(OsiSolverInterface *solver);
151 int orbitalFixing2(OsiSolverInterface *solver);
152 inline int *whichOrbit()
153 {
154 return numberUsefulOrbits_ ? whichOrbit_ : NULL;
155 }
156 inline int *fixedToZero() const
157 {
159 }
160 inline int numberUsefulOrbits() const
161 {
162 return numberUsefulOrbits_;
163 }
164 inline int numberUsefulObjects() const
165 {
167 }
168 int largestOrbit(const double *lower, const double *upper) const;
169 void ChangeBounds(const double *lower, const double *upper,
170 int numberColumns, bool justFixedAtOne) const;
173 int changeBounds(int kColumn, double * saveLower,
174 double * saveUpper,
175 OsiSolverInterface * solver,int mode) const;
176 int changeBounds(double *saveLower, double *saveUpper,
177 OsiSolverInterface * solver) const;
178 int changeBounds2(double *saveLower, double *saveUpper,
179 OsiSolverInterface * solver) const;
180 int fixSome(int iColumn, double *columnLower, double *columnUpper) const;
182 int worthBranching(const double *saveLower, const double *saveUpper,
183 int iColumn, int & numberCouldFix) const;
184 void fixSuccess(int nFixed);
186 void adjustStats(const CbcSymmetry * other);
187 inline int numberColumns() const
188 { return numberColumns_;}
189 inline bool compare(Node &a, Node &b) const;
191
192 // bool node_sort ( Node a, Node b);
193 // bool index_sort ( Node a, Node b);
194
196 void setupSymmetry(CbcModel * model);
197
201 inline int numberPermutations() const
202 { return numberPermutations_;}
203
204 inline int * permutation(int which) const
205 { return permutations_[which].orbits;}
206 inline int numberInPermutation(int which) const
207 { return permutations_[which].numberInPerm;}
208 inline void incrementNautyBranches(int n)
209 { nautyOtherBranches_ += n;}
212private:
213 mutable std::vector< Node > node_info_;
221 int stats_[5];
224 mutable double nautyOtherBranches_;
225 mutable int nautyBranchCalls_;
228 mutable int nautyFixCalls_;
231};
232
233class CbcNauty {
234
235public:
239
242private:
245
246public:
248 CbcNauty(int n, const size_t *v, const int *d, const int *e);
249
252
255
259
260 void addElement(int ix, int jx);
263 void deleteElement(int ix, int jx);
264 void color_node(int ix, int color) { vstat_[ix] = color; }
265 void insertRHS(int rhs, int cons) { constr_rhs.insert(std::pair< int, int >(rhs, cons)); }
266
267 double getGroupSize() const;
268 //int getNautyCalls() const { return nautyCalls_; }
269 //double getNautyTime() const { return nautyTime_; }
270
271 int getN() const { return n_; }
272
273 int getNumGenerators() const;
274 int getNumOrbits() const;
275
277 std::vector< std::vector< int > > *getOrbits() const;
278
279 void getVstat(double *v, int nv);
280 inline bool isSparse() const
281 {
282 return GSparse_ != NULL;
283 }
284 inline int errorStatus() const
285#ifndef NTY_TRACES
286 {
287 return stats_->errstatus;
288 }
289#else
290 {
291 return 0;
292 }
293#endif
295 inline optionblk *options() const
296 {
297 return options_;
298 }
299
302 // bool isAllFixOneOrbit(const std::vector<int> &orbit) const;
303 // bool isAllFreeOrbit(const std::vector<int> &orbit) const;
304 //bool isAutoComputed() const { return autoComputed_; }
305 //bool isConstraintOrbit(const std::vector<int> &orbit) const;
306 //bool isMixedFreeZeroOrbit(const std::vector<int> &orbit) const;
307 //void makeFree(int ix) { vstat_[ix] = FREE; }
308
309 void setWriteAutoms(const std::string &afilename);
311
312private:
313 // The base nauty stuff
314 graph *G_;
315 sparsegraph *GSparse_;
316 int *lab_;
317 int *ptn_;
320#ifndef NTY_TRACES
321 optionblk *options_;
322 statsblk *stats_;
323#else
324 TracesOptions *options_;
325 TracesStats *stats_;
326#endif
327 setword *workspace_;
329 int m_;
330 int n_;
331 size_t nel_;
332 graph *canonG_;
333
335
336 int *vstat_;
337
338 //static int nautyCalls_;
339 //static double nautyTime_;
340
341 std::multimap< int, int > constr_rhs;
342 std::multimap< int, int >::iterator it;
343
344 std::pair< std::multimap< int, int >::iterator,
345 std::multimap< int, int >::iterator >
347
348 // File pointer for automorphism group
349 FILE *afp_;
350};
351
358
359public:
360 // Default Constructor
362
363 // Useful constructor
365 int way,
366 int numberExtra, const int *extraToZero);
367 // Useful constructor (uses stored list)
368 CbcOrbitalBranchingObject(CbcModel *model, int column, int nFixed);
369
370 // Copy constructor
372
373 // Assignment operator
375
377 virtual CbcBranchingObject *clone() const;
378
379 // Destructor
381
384 virtual double branch();
387 virtual void fix(OsiSolverInterface *solver,
388 double *lower, double *upper,
389 int branchState) const;
390
394 virtual void previousBranch()
395 {
397 }
398
402 virtual void print();
403
405 virtual CbcBranchObjType type() const
406 {
407 return SoSBranchObj;
408 }
409
417 virtual int compareOriginalObject(const CbcBranchingObject *brObj) const;
418
427 virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap = false);
428
429private:
438};
439//#define PRINT_CBCAUTO
440#endif
CbcRangeCompare
@ SoSBranchObj
#define COUENNE_HACKED_EPS_SYMM
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child.
CbcBranchingObject()
Default Constructor.
virtual double branch()=0
Execute the actions required to branch, as specified by the current state of the branching object,...
CbcModel * model() const
Return model.
int way() const
Get the state of the branching object.
virtual void print() const
Print something about branch - only if log level high.
Simple Branch and bound class.
Definition CbcModel.hpp:100
bool autoComputed_
int getNumOrbits() const
void addElement(int ix, int jx)
std::vector< std::vector< int > > * getOrbits() const
Returns the orbits in a "convenient" form.
CbcNauty()
Default constructor.
sparsegraph * GSparse_
void color_node(int ix, int color)
statsblk * stats_
void unsetWriteAutoms()
FILE * afp_
int * orbits_
graph * G_
void getVstat(double *v, int nv)
CbcNauty(int n, const size_t *v, const int *d, const int *e)
Normal constructor (if dense - NULLS)
void insertRHS(int rhs, int cons)
int getNumGenerators() const
CbcNauty(const CbcNauty &)
Copy constructor.
bool isSparse() const
void computeAuto()
CbcNauty & operator=(const CbcNauty &rhs)
Assignment operator.
std::multimap< int, int > constr_rhs
int errorStatus() const
optionblk * options_
void deleteElement(int ix, int jx)
int getN() const
graph * canonG_
~CbcNauty()
Destructor.
void setWriteAutoms(const std::string &afilename)
Methods to classify orbits.
size_t nel_
std::pair< std::multimap< int, int >::iterator, std::multimap< int, int >::iterator > ret
set * active_
double getGroupSize() const
optionblk * options() const
Pointer to options.
std::multimap< int, int >::iterator it
void clearPartitions()
setword * workspace_
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child.
virtual ~CbcOrbitalBranchingObject()
virtual int compareOriginalObject(const CbcBranchingObject *brObj) const
Compare the original object of this with the original object of brObj.
virtual void print()
Print something about branch - only if log level high.
virtual CbcBranchingObject * clone() const
Clone.
virtual CbcBranchObjType type() const
Return the type (an integer identifier) of this.
virtual double branch()
Does next branch and updates state.
int column_
Column to go to 1.
CbcOrbitalBranchingObject & operator=(const CbcOrbitalBranchingObject &rhs)
int numberOther_
Number (without column) going to zero on down branch.
int numberExtra_
Number extra.
int * fixToZero_
Fix to zero.
CbcOrbitalBranchingObject(CbcModel *model, int column, int nFixed)
CbcOrbitalBranchingObject(CbcModel *model, int column, int way, int numberExtra, const int *extraToZero)
virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap=false)
Compare the this with brObj.
virtual void fix(OsiSolverInterface *solver, double *lower, double *upper, int branchState) const
Update bounds in solver as in 'branch' and update given bounds.
CbcOrbitalBranchingObject(const CbcOrbitalBranchingObject &)
double get_ub() const
int get_code() const
double get_coeff() const
int get_color() const
void color_vertex(int k)
int get_sign() const
double get_lb() const
int get_index() const
void node(int, double, double, double, int, int)
void bounds(double a, double b)
CbcNauty * nauty_info_
void incrementNautyBranches(int n)
int changeBounds(double *saveLower, double *saveUpper, OsiSolverInterface *solver) const
int numberUsefulOrbits() const
std::vector< Node > node_info_
int numberUsefulObjects() const
double nautyFixes_
void Print_Orbits(int type=0) const
void incrementBranchSucceeded()
cbc_permute * permutations_
myclass0 node_sort
int nautyBranchSucceeded_
int changeBounds2(double *saveLower, double *saveUpper, OsiSolverInterface *solver) const
int lastNautyFixSucceeded_
double nautyOtherBranches_
void addPermutation(cbc_permute permutation)
takes ownership of cbc_permute (orbits part)
int numberInPermutation(int which) const
void adjustStats(const CbcSymmetry *other)
Adjust statistics from threads.
int fixSome(int iColumn, double *columnLower, double *columnUpper) const
CbcSymmetry()
Default constructor.
int numberUsefulObjects_
int * fixedToZero() const
int statsOrbits(CbcModel *model, int type) const
myclass index_sort
int orbitalFixing(OsiSolverInterface *solver)
Fixes variables using orbits (returns number fixed)
int * whichOrbit()
void ChangeBounds(const double *lower, const double *upper, int numberColumns, bool justFixedAtOne) const
int numberPermutations_
void fillOrbits()
int largestOrbit(const double *lower, const double *upper) const
bool compare(Node &a, Node &b) const
int orbitalFixing2(OsiSolverInterface *solver)
Fixes variables using root orbits (returns number fixed)
int lastNautyBranchSucceeded_
CbcSymmetry & operator=(const CbcSymmetry &rhs)
Assignment operator.
std::vector< int > * Find_Orbit(int) const
int numberPermutations() const
Number of permutation arrays.
CbcSymmetry(const CbcSymmetry &)
Copy constructor.
void Compute_Symmetry() const
int worthBranching(const double *saveLower, const double *saveUpper, int iColumn, int &numberCouldFix) const
return number of orbits if worth branching
int numberColumns() const
double nautyTime_
int changeBounds(int kColumn, double *saveLower, double *saveUpper, OsiSolverInterface *solver, int mode) const
for simple stuff - returns number can fix if can use saved orbit (mode 1) otherwise may fix and retur...
~CbcSymmetry()
Destructor.
CbcNauty * getNtyInfo()
int numberUsefulOrbits_
int * permutation(int which) const
Permutation arrays.
void fixSuccess(int nFixed)
void setupSymmetry(CbcModel *model)
empty if no NTY, symmetry data structure setup otherwise
bool operator()(const char *a, const char *b) const
bool operator()(const Node &a, const Node &b)
bool operator()(const Node &a, const Node &b)