Cbc  2.9.9
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
CglClique.hpp
Go to the documentation of this file.
1 // $Id: CglClique.hpp 1330 2016-01-26 19:35:16Z forrest $
2 // Copyright (C) 2000, International Business Machines
3 // Corporation and others. All Rights Reserved.
4 // This code is licensed under the terms of the Eclipse Public License (EPL).
5 
6 #ifndef _CglClique_h_
7 #define _CglClique_h_
8 
9 #include "CglCutGenerator.hpp"
10 
11 //class OsiCuts;
12 //class OsiSolverInterface;
13 
14 class CglClique : public CglCutGenerator {
15 
16  friend void CglCliqueUnitTest(const OsiSolverInterface * siP,
17  const std::string mpdDir );
18 public:
20  CglClique(const CglClique& rhs);
22  virtual CglCutGenerator * clone() const;
23 
25  CglClique& operator=(const CglClique& rhs);
26 
27 public:
28 
29  virtual void
30  generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
31  const CglTreeInfo info = CglTreeInfo());
32 
53  CglClique(bool setPacking = false, bool justOriginalRows = false);
55  virtual ~CglClique() {}
57  virtual std::string generateCpp( FILE * fp);
58 
59  void considerRows(const int numRows, const int* rowInd);
60 
61 public:
68  };
69 
71  scl_next_node_rule = method;
72  }
73 
76  }
79  }
80 
81  void setStarCliqueReport(bool yesno = true) { scl_report_result = yesno; }
82  void setRowCliqueReport(bool yesno = true) { rcl_report_result = yesno; }
83 
84  void setDoStarClique(bool yesno = true) { do_star_clique = yesno; }
85  void setDoRowClique(bool yesno = true) { do_row_clique = yesno; }
86 
87  void setMinViolation(double minviol) { petol = minviol; }
88  double getMinViolation() const { return petol; }
90  inline void setMaxNumber(int value) { maxNumber_ = value; }
91 
92 private:
93 
94  struct frac_graph ;
95  friend struct frac_graph ;
96 
99  struct fnode {
101  int *nbrs;
104  double *edgecosts;
106  int degree;
108  double val;
109  };
110 
113  struct frac_graph {
115  int nodenum;
117  int edgenum;
119  double density;
128  int *all_nbr;
130  double *all_edgecost;
131 
133  nodenum(0), edgenum(0), density(0),
135  nodes(0), all_nbr(0), all_edgecost(0) {}
136  };
137 
138 protected:
149  double* sp_colsol;
154 
158  bool* node_node;
159 
161  double petol;
164 
173 
183 
198  const int* cl_perm_indices;
201 
207 
214 
217 private:
223  void selectFractionals(const OsiSolverInterface& si);
225  void selectRowCliques(const OsiSolverInterface& si,int numOriginalRows);
229  void createFractionalGraph();
231  int createNodeNode();
235  void deleteFractionalGraph();
237  void find_scl(OsiCuts& cs);
239  void find_rcl(OsiCuts& cs);
241  int scl_choose_next_node(const int current_nodenum,
242  const int *current_indices,
243  const int *current_degrees,
244  const double *current_values);
246  void scl_delete_node(const int del_ind, int& current_nodenum,
247  int *current_indices, int *current_degrees,
248  double *current_values);
250  int enumerate_maximal_cliques(int& pos, bool* scl_label, OsiCuts& cs);
254  void recordClique(const int len, int* indices, OsiCuts& cs);
255 };
256 //#############################################################################
262 void CglCliqueUnitTest(const OsiSolverInterface * siP,
263  const std::string mpdDir);
265 class CglProbing;
266 class CglFakeClique : public CglClique {
267 
268 public:
270  CglFakeClique(const CglFakeClique& rhs);
272  virtual CglCutGenerator * clone() const;
273 
276 
277  virtual void
278  generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
279  const CglTreeInfo info = CglTreeInfo());
280 
300  CglFakeClique(OsiSolverInterface * solver=NULL,bool setPacking = false);
302  virtual ~CglFakeClique();
304  void assignSolver(OsiSolverInterface * fakeSolver);
305 protected:
310 };
311 
312 #endif
int createNodeNode()
int edgenum
of edges in the graph
Definition: CglClique.hpp:117
void selectFractionals(const OsiSolverInterface &si)
Scan through the variables and select those that are at a fractional level.
void scl_delete_node(const int del_ind, int &current_nodenum, int *current_indices, int *current_degrees, double *current_values)
void selectRowCliques(const OsiSolverInterface &si, int numOriginalRows)
int * sp_orig_col_ind
Definition: CglClique.hpp:148
int sp_numcols
Definition: CglClique.hpp:147
OsiSolverInterface * fakeSolver_
fake solver to use
Definition: CglClique.hpp:307
double * all_edgecost
The array of the costs of the edges going to the neighbors.
Definition: CglClique.hpp:130
int degree
degree of the node
Definition: CglClique.hpp:106
double val
the fractional value of the variable corresponding to this node
Definition: CglClique.hpp:108
int * cl_del_indices
An array of nodes discarded from the candidate list.
Definition: CglClique.hpp:211
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
int greedy_maximal_clique(OsiCuts &cs)
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
double getMinViolation() const
Definition: CglClique.hpp:88
bool rcl_report_result
whether to give a detailed statistics on the row clique method
Definition: CglClique.hpp:190
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
void deleteFractionalGraph()
int nodenum
of nodes = # of fractional values in the LP solution
Definition: CglClique.hpp:115
int * sp_row_ind
Definition: CglClique.hpp:153
int cl_length
The length of cl_indices.
Definition: CglClique.hpp:206
void setStarCliqueNextNodeMethod(scl_next_node_method method)
Definition: CglClique.hpp:70
void find_scl(OsiCuts &cs)
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int * sp_col_ind
Definition: CglClique.hpp:151
Abstract Base Class for describing an interface to a solver.
void deleteSetPackingSubMatrix()
CglProbing * probing_
Probing object.
Definition: CglClique.hpp:309
int maxNumber_
Maximum number of binaries for looking at all.
Definition: CglClique.hpp:163
void setStarCliqueCandidateLengthThreshold(int maxlen)
Definition: CglClique.hpp:74
int cl_perm_length
The length of cl_perm_indices.
Definition: CglClique.hpp:200
void setMaxNumber(int value)
Maximum number of binaries for looking at all.
Definition: CglClique.hpp:90
int * cl_indices
List of indices that should be considered for extending the ones listed in cl_perm_indices.
Definition: CglClique.hpp:204
const int * cl_perm_indices
variables/arrays that are used across many methods
Definition: CglClique.hpp:198
Cut Generator Base Class.
A graph corresponding to a fractional solution of an LP.
Definition: CglClique.hpp:113
CglFakeClique & operator=(const CglFakeClique &rhs)
Assignment operator.
CglFakeClique(const CglFakeClique &rhs)
Copy constructor.
void CglCliqueUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglClique class.
scl_next_node_method
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:64
void recordClique(const int len, int *indices, OsiCuts &cs)
void setRowCliqueReport(bool yesno=true)
Definition: CglClique.hpp:82
int sp_numrows
pieces of the set packing part of the solverinterface
Definition: CglClique.hpp:145
bool scl_report_result
whether to give a detailed statistics on the star clique method
Definition: CglClique.hpp:182
double density
density= edgenum/(nodenum choose 2)
Definition: CglClique.hpp:119
virtual ~CglClique()
Destructor.
Definition: CglClique.hpp:55
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:104
int * sp_row_start
Definition: CglClique.hpp:152
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
int * nbrs
pointer into all_nbr
Definition: CglClique.hpp:101
int * all_nbr
The array of all the neighbors.
Definition: CglClique.hpp:128
bool do_star_clique
whether to do the star clique algorithm or not.
Definition: CglClique.hpp:172
virtual CglCutGenerator * clone() const
Clone.
CglClique(const CglClique &rhs)
Copy constructor.
void setStarCliqueReport(bool yesno=true)
Definition: CglClique.hpp:81
friend void CglCliqueUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglClique class.
int cl_del_length
The length of cl_del_indices.
Definition: CglClique.hpp:213
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:175
frac_graph fgraph
the intersection graph corresponding to the set packing problem
Definition: CglClique.hpp:156
A node of the fractional graph.
Definition: CglClique.hpp:99
void selectFractionalBinaries(const OsiSolverInterface &si)
Scan through the variables and select those that are binary and are at a fractional level...
void setDoRowClique(bool yesno=true)
Definition: CglClique.hpp:85
bool do_row_clique
data for the star clique algorithm
Definition: CglClique.hpp:170
void createSetPackingSubMatrix(const OsiSolverInterface &si)
CglClique & operator=(const CglClique &rhs)
Assignment operator.
int * sp_col_start
Definition: CglClique.hpp:150
void find_rcl(OsiCuts &cs)
void setDoStarClique(bool yesno=true)
Definition: CglClique.hpp:84
int * sp_orig_row_ind
Definition: CglClique.hpp:146
void setRowCliqueCandidateLengthThreshold(int maxlen)
Definition: CglClique.hpp:77
void setMinViolation(double minviol)
Definition: CglClique.hpp:87
virtual CglCutGenerator * clone() const
Clone.
double * sp_colsol
Definition: CglClique.hpp:149
fnode * nodes
The array of the nodes in the graph.
Definition: CglClique.hpp:125
bool * node_node
the node-node incidence matrix of the intersection graph.
Definition: CglClique.hpp:158
void createFractionalGraph()
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:188
double petol
The primal tolerance in the solverinterface.
Definition: CglClique.hpp:161
bool setPacking_
An indicator showing whether the whole matrix in the solverinterface is a set packing problem or not...
Definition: CglClique.hpp:141
void considerRows(const int numRows, const int *rowInd)
virtual ~CglFakeClique()
Destructor.
int enumerate_maximal_cliques(int &pos, bool *scl_label, OsiCuts &cs)
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:180
void assignSolver(OsiSolverInterface *fakeSolver)
Assign solver (generator takes over ownership)
int scl_choose_next_node(const int current_nodenum, const int *current_indices, const int *current_degrees, const double *current_values)
Probing Cut Generator Class.
Definition: CglProbing.hpp:25
bool justOriginalRows_
True if just look at original rows.
Definition: CglClique.hpp:143