Cbc 2.10.10
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
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(register 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(register double a, register double b)
92 {
93 lb = a;
94 ub = b;
95 }
96 };
97
98 struct myclass0 {
99 inline bool operator()(register const Node &a, register 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()(register const Node &a, register const Node &b)
108 {
109 return (a.get_index() < b.get_index());
110 }
111 };
112
114 inline bool operator()(register const char *a, register const char *b) const
115 {
116 return strcmp(a, b) < 0;
117 }
118 };
119
120public:
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(register Node &a, register 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_;}
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 }
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
CbcBranchObjType
@ SoSBranchObj
#define COUENNE_HACKED_EPS_SYMM
Definition: CbcSymmetry.hpp:62
Abstract branching object base class Now just difference with OsiBranchingObject.
virtual void previousBranch()
Reset every information so that the branching object appears to point to the previous child.
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)
int * lab_
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
int * ptn_
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_
int * vstat_
double getGroupSize() const
optionblk * options() const
Pointer to options.
std::multimap< int, int >::iterator it
void clearPartitions()
setword * workspace_
Branching object for Orbital branching.
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
Definition: CbcSymmetry.hpp:87
void bounds(register double a, register double b)
Definition: CbcSymmetry.hpp:91
int get_code() const
Definition: CbcSymmetry.hpp:89
double get_coeff() const
Definition: CbcSymmetry.hpp:85
int get_color() const
Definition: CbcSymmetry.hpp:88
int get_sign() const
Definition: CbcSymmetry.hpp:90
void color_vertex(register int k)
Definition: CbcSymmetry.hpp:83
double get_lb() const
Definition: CbcSymmetry.hpp:86
int get_index() const
Definition: CbcSymmetry.hpp:84
void node(int, double, double, double, int, int)
Class to deal with symmetry.
Definition: CbcSymmetry.hpp:71
CbcNauty * nauty_info_
void incrementNautyBranches(int n)
int changeBounds(double *saveLower, double *saveUpper, OsiSolverInterface *solver) const
int numberUsefulOrbits() const
bool compare(register Node &a, register Node &b) 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 nautyFixSucceeded_
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
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...
int * whichOrbit_
~CbcSymmetry()
Destructor.
CbcNauty * getNtyInfo()
int numberUsefulOrbits_
int * permutation(int which) const
Permutation arrays.
void fixSuccess(int nFixed)
int nautyBranchCalls_
void setupSymmetry(CbcModel *model)
empty if no NTY, symmetry data structure setup otherwise
bool operator()(register const char *a, register const char *b) const
bool operator()(register const Node &a, register const Node &b)
Definition: CbcSymmetry.hpp:99
bool operator()(register const Node &a, register const Node &b)