Cbc 2.10.8
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 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
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
109 inline bool operator()(register const char *a, register const char *b) const
110 {
111 return strcmp(a, b) < 0;
112 }
113 };
114
115public:
120
123
126
130
131 // Symmetry Info
132
133 std::vector< int > *Find_Orbit(int) const;
134
137
138 void Compute_Symmetry() const;
139 int statsOrbits(CbcModel *model, int type) const;
140 //double timeNauty () const;
141 void Print_Orbits() const;
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 {
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;
162
163 // bool node_sort ( Node a, Node b);
164 // bool index_sort ( Node a, Node b);
165
167 void setupSymmetry(CbcModel * model);
168
169private:
170 mutable std::vector< Node > node_info_;
176};
177
178class CbcNauty {
179
180public:
184
187private:
190
191public:
193 CbcNauty(int n, const size_t *v, const int *d, const int *e);
194
197
200
204
205 void addElement(int ix, int jx);
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
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
240 inline optionblk *options() const
241 {
242 return options_;
243 }
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);
256
257private:
258 // The base nauty stuff
259 graph *G_;
260 sparsegraph *GSparse_;
261 int *lab_;
262 int *ptn_;
265#ifndef NTY_TRACES
266 optionblk *options_;
267 statsblk *stats_;
268#else
269 TracesOptions *options_;
270 TracesStats *stats_;
271#endif
272 setword *workspace_;
274 int m_;
275 int n_;
276 size_t nel_;
277 graph *canonG_;
278
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 >
292
293 // File pointer for automorphism group
294 FILE *afp_;
295};
296
303
304public:
305 // Default Constructor
307
308 // Useful constructor
310 int way,
311 int numberExtra, const int *extraToZero);
312
313 // Copy constructor
315
316 // Assignment operator
318
320 virtual CbcBranchingObject *clone() const;
321
322 // Destructor
324
327 virtual double branch();
330 virtual void fix(OsiSolverInterface *solver,
331 double *lower, double *upper,
332 int branchState) const;
333
337 virtual void previousBranch()
338 {
340 }
341
345 virtual void print();
346
348 virtual CbcBranchObjType type() const
349 {
350 return SoSBranchObj;
351 }
352
360 virtual int compareOriginalObject(const CbcBranchingObject *brObj) const;
361
370 virtual CbcRangeCompare compareBranchingObject(const CbcBranchingObject *brObj, const bool replaceIfOverlap = false);
371
372private:
381};
382
383#endif
384
385/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
386*/
CbcRangeCompare
CbcBranchObjType
@ SoSBranchObj
#define COUENNE_HACKED_EPS_SYMM
Definition: CbcSymmetry.hpp:57
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 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:82
void bounds(register double a, register double b)
Definition: CbcSymmetry.hpp:86
int get_code() const
Definition: CbcSymmetry.hpp:84
double get_coeff() const
Definition: CbcSymmetry.hpp:80
int get_color() const
Definition: CbcSymmetry.hpp:83
int get_sign() const
Definition: CbcSymmetry.hpp:85
void color_vertex(register int k)
Definition: CbcSymmetry.hpp:78
double get_lb() const
Definition: CbcSymmetry.hpp:81
int get_index() const
Definition: CbcSymmetry.hpp:79
void node(int, double, double, double, int, int)
Class to deal with symmetry.
Definition: CbcSymmetry.hpp:66
CbcNauty * nauty_info_
int numberUsefulOrbits() const
bool compare(register Node &a, register Node &b) const
std::vector< Node > node_info_
int numberUsefulObjects() const
myclass0 node_sort
CbcSymmetry()
Default constructor.
int numberUsefulObjects_
int statsOrbits(CbcModel *model, int type) const
myclass index_sort
void Print_Orbits() const
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
void fillOrbits()
int largestOrbit(const double *lower, const double *upper) const
CbcSymmetry & operator=(const CbcSymmetry &rhs)
Assignment operator.
std::vector< int > * Find_Orbit(int) const
CbcSymmetry(const CbcSymmetry &)
Copy constructor.
void Compute_Symmetry() const
int * whichOrbit_
~CbcSymmetry()
Destructor.
CbcNauty * getNtyInfo()
int numberUsefulOrbits_
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:94
bool operator()(register const Node &a, register const Node &b)