coin-Cgl
CglClique.hpp
Go to the documentation of this file.
1 #ifndef _CglClique_h_
2 #define _CglClique_h_
3 
4 #include "CglCutGenerator.hpp"
5 
6 //class OsiCuts;
7 //class OsiSolverInterface;
8 
9 class CglClique : public CglCutGenerator {
10 
11  friend void CglCliqueUnitTest(const OsiSolverInterface * siP,
12  const std::string mpdDir );
13 public:
15  CglClique(const CglClique& rhs);
17  virtual CglCutGenerator * clone() const;
18 
20  CglClique& operator=(const CglClique& rhs);
21 
22 public:
23 
24  virtual void
25  generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
26  const CglTreeInfo info = CglTreeInfo()) const;
27 
48  CglClique(bool setPacking = false, bool justOriginalRows = false);
50  virtual ~CglClique() {}
52  virtual std::string generateCpp( FILE * fp);
53 
54  void considerRows(const int numRows, const int* rowInd);
55 
56 public:
63  };
64 
66  scl_next_node_rule = method;
67  }
68 
71  }
74  }
75 
76  void setStarCliqueReport(bool yesno = true) { scl_report_result = yesno; }
77  void setRowCliqueReport(bool yesno = true) { rcl_report_result = yesno; }
78 
79  void setDoStarClique(bool yesno = true) { do_star_clique = yesno; }
80  void setDoRowClique(bool yesno = true) { do_row_clique = yesno; }
81 
82  void setMinViolation(double minviol) { petol = minviol; }
83  double getMinViolation() const { return petol; }
84 
85 private:
86 
87  struct frac_graph ;
88  friend struct frac_graph ;
89 
92  struct fnode {
94  int *nbrs;
97  double *edgecosts;
99  int degree;
101  double val;
102  };
103 
106  struct frac_graph {
108  int nodenum;
110  int edgenum;
112  double density;
121  int *all_nbr;
123  double *all_edgecost;
124 
126  nodenum(0), edgenum(0), density(0),
128  nodes(0), all_nbr(0), all_edgecost(0) {}
129  };
130 
131 protected:
138  mutable int sp_numrows;
139  mutable int* sp_orig_row_ind;
140  mutable int sp_numcols;
141  mutable int* sp_orig_col_ind;
142  mutable double* sp_colsol;
143  mutable int* sp_col_start;
144  mutable int* sp_col_ind;
145  mutable int* sp_row_start;
146  mutable int* sp_row_ind;
147 
151  mutable bool* node_node;
152 
154  mutable double petol;
155 
164 
174 
189  mutable const int* cl_perm_indices;
191  mutable int cl_perm_length;
192 
195  mutable int* cl_indices;
197  mutable int cl_length;
198 
202  mutable int* cl_del_indices;
204  mutable int cl_del_length;
205 
208 private:
211  void selectFractionalBinaries(const OsiSolverInterface& si) const;
214  void selectFractionals(const OsiSolverInterface& si) const;
216  void selectRowCliques(const OsiSolverInterface& si,int numOriginalRows) const;
218  void createSetPackingSubMatrix(const OsiSolverInterface& si) const;
220  void createFractionalGraph() const;
222  int createNodeNode() const;
224  void deleteSetPackingSubMatrix() const;
226  void deleteFractionalGraph() const;
228  void find_scl(OsiCuts& cs) const;
230  void find_rcl(OsiCuts& cs) const;
232  int scl_choose_next_node(const int current_nodenum,
233  const int *current_indices,
234  const int *current_degrees,
235  const double *current_values) const;
237  void scl_delete_node(const int del_ind, int& current_nodenum,
238  int *current_indices, int *current_degrees,
239  double *current_values) const;
241  int enumerate_maximal_cliques(int& pos, bool* scl_label, OsiCuts& cs) const;
243  int greedy_maximal_clique(OsiCuts& cs) const;
245  void recordClique(const int len, int* indices, OsiCuts& cs) const;
246 };
247 //#############################################################################
253 void CglCliqueUnitTest(const OsiSolverInterface * siP,
254  const std::string mpdDir);
256 class CglProbing;
257 class CglFakeClique : public CglClique {
258 
259 public:
261  CglFakeClique(const CglFakeClique& rhs);
263  virtual CglCutGenerator * clone() const;
264 
267 
268  virtual void
269  generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
270  const CglTreeInfo info = CglTreeInfo()) const;
271 
291  CglFakeClique(OsiSolverInterface * solver=NULL,bool setPacking = false);
293  virtual ~CglFakeClique();
295  void assignSolver(OsiSolverInterface * fakeSolver);
296 protected:
298  mutable OsiSolverInterface * fakeSolver_;
300  mutable CglProbing * probing_;
301 };
302 
303 #endif
A graph corresponding to a fractional solution of an LP.
Definition: CglClique.hpp:106
int * cl_del_indices
An array of nodes discarded from the candidate list.
Definition: CglClique.hpp:202
void CglCliqueUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglClique class.
void deleteFractionalGraph() const
bool justOriginalRows_
True if just look at original rows.
Definition: CglClique.hpp:136
double petol
The primal tolerance in the solverinterface.
Definition: CglClique.hpp:154
void createFractionalGraph() const
double * edgecosts
1-x_i-x_j, needed for odd holes, in the same order as the adj list, pointer into all_edgecost ...
Definition: CglClique.hpp:97
int cl_perm_length
The length of cl_perm_indices.
Definition: CglClique.hpp:191
OsiSolverInterface * fakeSolver_
fake solver to use
Definition: CglClique.hpp:298
double density
density= edgenum/(nodenum choose 2)
Definition: CglClique.hpp:112
CglClique & operator=(const CglClique &rhs)
Assignment operator.
virtual CglCutGenerator * clone() const
Clone.
void selectFractionals(const OsiSolverInterface &si) const
Scan through the variables and select those that are at a fractional level.
int * sp_orig_row_ind
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:139
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
bool * node_node
the node-node incidence matrix of the intersection graph.
Definition: CglClique.hpp:151
void recordClique(const int len, int *indices, OsiCuts &cs) const
void deleteSetPackingSubMatrix() const
int * all_nbr
The array of all the neighbors.
Definition: CglClique.hpp:121
void selectFractionalBinaries(const OsiSolverInterface &si) const
Scan through the variables and select those that are binary and are at a fractional level...
void setRowCliqueReport(bool yesno=true)
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:77
int * sp_orig_col_ind
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:141
void setStarCliqueCandidateLengthThreshold(int maxlen)
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:69
int cl_length
The length of cl_indices.
Definition: CglClique.hpp:197
fnode * nodes
The array of the nodes in the graph.
Definition: CglClique.hpp:118
void selectRowCliques(const OsiSolverInterface &si, int numOriginalRows) const
scl_next_node_method scl_next_node_rule
How the next node to be added to the star clique should be selected.
Definition: CglClique.hpp:166
void setStarCliqueReport(bool yesno=true)
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:76
void scl_delete_node(const int del_ind, int &current_nodenum, int *current_indices, int *current_degrees, double *current_values) const
int scl_choose_next_node(const int current_nodenum, const int *current_indices, const int *current_degrees, const double *current_values) const
virtual CglCutGenerator * clone() const
Clone.
CglFakeClique & operator=(const CglFakeClique &rhs)
Assignment operator.
int cl_del_length
The length of cl_del_indices.
Definition: CglClique.hpp:204
void setDoStarClique(bool yesno=true)
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:79
int enumerate_maximal_cliques(int &pos, bool *scl_label, OsiCuts &cs) const
friend void CglCliqueUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglClique class.
Probing Cut Generator Class.
Definition: CglProbing.hpp:22
bool setPacking_
An indicator showing whether the whole matrix in the solverinterface is a set packing problem or not...
Definition: CglClique.hpp:134
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
Generate cuts for the model data contained in si.
int nodenum
of nodes = # of fractional values in the LP solution
Definition: CglClique.hpp:108
void setMinViolation(double minviol)
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:82
int sp_numcols
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:140
double val
the fractional value of the variable corresponding to this node
Definition: CglClique.hpp:101
A node of the fractional graph.
Definition: CglClique.hpp:92
int * nbrs
pointer into all_nbr
Definition: CglClique.hpp:94
int * sp_row_ind
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:146
bool do_star_clique
whether to do the star clique algorithm or not.
Definition: CglClique.hpp:163
void setDoRowClique(bool yesno=true)
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:80
int sp_numrows
pieces of the set packing part of the solverinterface
Definition: CglClique.hpp:138
Cut Generator Base Class.
void find_rcl(OsiCuts &cs) const
void setStarCliqueNextNodeMethod(scl_next_node_method method)
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:65
int * cl_indices
List of indices that should be considered for extending the ones listed in cl_perm_indices.
Definition: CglClique.hpp:195
scl_next_node_method
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:59
int rcl_candidate_length_threshold
In the row clique method the maximal length of the candidate list (those nodes that can extend the ro...
Definition: CglClique.hpp:179
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
Generate cuts for the model data contained in si.
int edgenum
of edges in the graph
Definition: CglClique.hpp:110
int * sp_col_start
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:143
frac_graph fgraph
the intersection graph corresponding to the set packing problem
Definition: CglClique.hpp:149
CglProbing * probing_
Probing object.
Definition: CglClique.hpp:300
int greedy_maximal_clique(OsiCuts &cs) const
bool rcl_report_result
whether to give a detailed statistics on the row clique method
Definition: CglClique.hpp:181
int * sp_col_ind
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:144
double * sp_colsol
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:142
void setRowCliqueCandidateLengthThreshold(int maxlen)
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:72
double * all_edgecost
The array of the costs of the edges going to the neighbors.
Definition: CglClique.hpp:123
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:13
int scl_candidate_length_threshold
In the star clique method the maximal length of the candidate list (those nodes that are in a star...
Definition: CglClique.hpp:171
int * sp_row_start
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:145
const int * cl_perm_indices
variables/arrays that are used across many methods
Definition: CglClique.hpp:189
CglFakeClique(const CglFakeClique &rhs)
Copy constructor.
int degree
degree of the node
Definition: CglClique.hpp:99
void find_scl(OsiCuts &cs) const
bool do_row_clique
data for the star clique algorithm
Definition: CglClique.hpp:161
bool scl_report_result
whether to give a detailed statistics on the star clique method
Definition: CglClique.hpp:173
void considerRows(const int numRows, const int *rowInd)
possible choices for selecting the next node in the star clique search
virtual ~CglClique()
Destructor.
Definition: CglClique.hpp:50
void assignSolver(OsiSolverInterface *fakeSolver)
Assign solver (generator takes over ownership)
virtual ~CglFakeClique()
Destructor.
void createSetPackingSubMatrix(const OsiSolverInterface &si) const
double getMinViolation() const
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:83
CglClique(const CglClique &rhs)
Copy constructor.
int createNodeNode() const