Cgl 0.59.7

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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 1119 2013-04-06 20:24:18Z stefan $
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:
64 enum scl_next_node_method {
65 SCL_MIN_DEGREE,
66 SCL_MAX_DEGREE,
67 SCL_MAX_XJ_MAX_DEG
68 };
69
70 void setStarCliqueNextNodeMethod(scl_next_node_method method) {
71 scl_next_node_rule = method;
72 }
73
74 void setStarCliqueCandidateLengthThreshold(int maxlen) {
75 scl_candidate_length_threshold = maxlen;
76 }
77 void setRowCliqueCandidateLengthThreshold(int maxlen) {
78 rcl_candidate_length_threshold = maxlen;
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; }
89
90 private:
91
92 struct frac_graph ;
93 friend struct frac_graph ;
94
97 struct fnode {
99 int *nbrs;
102 double *edgecosts;
104 int degree;
106 double val;
107 };
108
111 struct frac_graph {
113 int nodenum;
115 int edgenum;
117 double density;
118 int min_deg_node;
119 int min_degree;
120 int max_deg_node;
121 int max_degree;
123 fnode *nodes;
126 int *all_nbr;
128 double *all_edgecost;
129
130 frac_graph() :
131 nodenum(0), edgenum(0), density(0),
132 min_deg_node(0), min_degree(0), max_deg_node(0), max_degree(0),
133 nodes(0), all_nbr(0), all_edgecost(0) {}
134 };
135
136 protected:
139 bool setPacking_;
141 bool justOriginalRows_;
143 int sp_numrows;
144 int* sp_orig_row_ind;
145 int sp_numcols;
146 int* sp_orig_col_ind;
147 double* sp_colsol;
148 int* sp_col_start;
149 int* sp_col_ind;
150 int* sp_row_start;
151 int* sp_row_ind;
152
154 frac_graph fgraph;
156 bool* node_node;
157
159 double petol;
160
166 bool do_row_clique;
168 bool do_star_clique;
169
171 scl_next_node_method scl_next_node_rule;
176 int scl_candidate_length_threshold;
178 bool scl_report_result;
179
184 int rcl_candidate_length_threshold;
186 bool rcl_report_result;
194 const int* cl_perm_indices;
196 int cl_perm_length;
197
200 int* cl_indices;
202 int cl_length;
203
207 int* cl_del_indices;
209 int cl_del_length;
210
213 private:
216 void selectFractionalBinaries(const OsiSolverInterface& si);
219 void selectFractionals(const OsiSolverInterface& si);
221 void selectRowCliques(const OsiSolverInterface& si,int numOriginalRows);
223 void createSetPackingSubMatrix(const OsiSolverInterface& si);
225 void createFractionalGraph();
227 int createNodeNode();
229 void deleteSetPackingSubMatrix();
231 void deleteFractionalGraph();
233 void find_scl(OsiCuts& cs);
235 void find_rcl(OsiCuts& cs);
237 int scl_choose_next_node(const int current_nodenum,
238 const int *current_indices,
239 const int *current_degrees,
240 const double *current_values);
242 void scl_delete_node(const int del_ind, int& current_nodenum,
243 int *current_indices, int *current_degrees,
244 double *current_values);
246 int enumerate_maximal_cliques(int& pos, bool* scl_label, OsiCuts& cs);
248 int greedy_maximal_clique(OsiCuts& cs);
250 void recordClique(const int len, int* indices, OsiCuts& cs);
251 };
252 //#############################################################################
258 void CglCliqueUnitTest(const OsiSolverInterface * siP,
259 const std::string mpdDir);
261 class CglProbing;
262 class CglFakeClique : public CglClique {
263
264 public:
266 CglFakeClique(const CglFakeClique& rhs);
268 virtual CglCutGenerator * clone() const;
269
271 CglFakeClique& operator=(const CglFakeClique& rhs);
272
273 virtual void
274 generateCuts(const OsiSolverInterface& si, OsiCuts & cs,
275 const CglTreeInfo info = CglTreeInfo());
276
296 CglFakeClique(OsiSolverInterface * solver=NULL,bool setPacking = false);
298 virtual ~CglFakeClique();
300 void assignSolver(OsiSolverInterface * fakeSolver);
301 protected:
303 OsiSolverInterface * fakeSolver_;
305 CglProbing * probing_;
306 };
307
308 #endif
CglClique::frac_graph::frac_graph
frac_graph()
Definition: CglClique.hpp:130
CglClique::createNodeNode
int createNodeNode()
CglClique::frac_graph::edgenum
int edgenum
of edges in the graph
Definition: CglClique.hpp:115
CglClique::SCL_MIN_DEGREE
Definition: CglClique.hpp:65
CglClique::selectFractionals
void selectFractionals(const OsiSolverInterface &si)
Scan through the variables and select those that are at a fractional level.
CglClique::frac_graph::max_degree
int max_degree
Definition: CglClique.hpp:121
CglClique::scl_delete_node
void scl_delete_node(const int del_ind, int &current_nodenum, int *current_indices, int *current_degrees, double *current_values)
CglClique::selectRowCliques
void selectRowCliques(const OsiSolverInterface &si, int numOriginalRows)
CglClique::frac_graph::min_deg_node
int min_deg_node
Definition: CglClique.hpp:118
CglClique::sp_orig_col_ind
int * sp_orig_col_ind
Definition: CglClique.hpp:146
CglClique::sp_numcols
int sp_numcols
Definition: CglClique.hpp:145
CglFakeClique::fakeSolver_
OsiSolverInterface * fakeSolver_
fake solver to use
Definition: CglClique.hpp:303
CglClique::frac_graph::min_degree
int min_degree
Definition: CglClique.hpp:119
CglClique::SCL_MAX_DEGREE
Definition: CglClique.hpp:66
CglClique::frac_graph::all_edgecost
double * all_edgecost
The array of the costs of the edges going to the neighbors.
Definition: CglClique.hpp:128
CglClique::fnode::degree
int degree
degree of the node
Definition: CglClique.hpp:104
CglClique::fnode::val
double val
the fractional value of the variable corresponding to this node
Definition: CglClique.hpp:106
CglCutGenerator.hpp
CglClique::cl_del_indices
int * cl_del_indices
An array of nodes discarded from the candidate list.
Definition: CglClique.hpp:207
CglTreeInfo
Information about where the cut generator is invoked from.
Definition: CglTreeInfo.hpp:15
CglClique::greedy_maximal_clique
int greedy_maximal_clique(OsiCuts &cs)
CglClique::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
CglClique::getMinViolation
double getMinViolation() const
Definition: CglClique.hpp:88
CglClique::rcl_report_result
bool rcl_report_result
whether to give a detailed statistics on the row clique method
Definition: CglClique.hpp:186
OsiCuts
Collections of row cuts and column cuts.
Definition: OsiCuts.hpp:19
CglClique::deleteFractionalGraph
void deleteFractionalGraph()
CglClique::frac_graph::nodenum
int nodenum
of nodes = # of fractional values in the LP solution
Definition: CglClique.hpp:113
CglClique::sp_row_ind
int * sp_row_ind
Definition: CglClique.hpp:151
CglFakeClique
Definition: CglClique.hpp:262
CglClique::cl_length
int cl_length
The length of cl_indices.
Definition: CglClique.hpp:202
CglClique::setStarCliqueNextNodeMethod
void setStarCliqueNextNodeMethod(scl_next_node_method method)
Definition: CglClique.hpp:70
CglClique::SCL_MAX_XJ_MAX_DEG
Definition: CglClique.hpp:67
CglClique::frac_graph::max_deg_node
int max_deg_node
Definition: CglClique.hpp:120
CglClique::find_scl
void find_scl(OsiCuts &cs)
CglClique::generateCpp
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
CglClique::sp_col_ind
int * sp_col_ind
Definition: CglClique.hpp:149
OsiSolverInterface
Abstract Base Class for describing an interface to a solver.
Definition: OsiSolverInterface.hpp:62
CglClique
Definition: CglClique.hpp:14
CglClique::deleteSetPackingSubMatrix
void deleteSetPackingSubMatrix()
CglFakeClique::probing_
CglProbing * probing_
Probing object.
Definition: CglClique.hpp:305
CglClique::setStarCliqueCandidateLengthThreshold
void setStarCliqueCandidateLengthThreshold(int maxlen)
Definition: CglClique.hpp:74
CglClique::cl_perm_length
int cl_perm_length
The length of cl_perm_indices.
Definition: CglClique.hpp:196
CglClique::cl_indices
int * cl_indices
List of indices that should be considered for extending the ones listed in cl_perm_indices.
Definition: CglClique.hpp:200
CglClique::cl_perm_indices
const int * cl_perm_indices
variables/arrays that are used across many methods
Definition: CglClique.hpp:194
CglCutGenerator
Cut Generator Base Class.
Definition: CglCutGenerator.hpp:23
CglClique::frac_graph
A graph corresponding to a fractional solution of an LP.
Definition: CglClique.hpp:111
CglFakeClique::operator=
CglFakeClique & operator=(const CglFakeClique &rhs)
Assignment operator.
CglFakeClique::CglFakeClique
CglFakeClique(const CglFakeClique &rhs)
Copy constructor.
CglCliqueUnitTest
void CglCliqueUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglClique class.
CglClique::scl_next_node_method
scl_next_node_method
possible choices for selecting the next node in the star clique search
Definition: CglClique.hpp:64
CglClique::recordClique
void recordClique(const int len, int *indices, OsiCuts &cs)
CglClique::setRowCliqueReport
void setRowCliqueReport(bool yesno=true)
Definition: CglClique.hpp:82
CglClique::sp_numrows
int sp_numrows
pieces of the set packing part of the solverinterface
Definition: CglClique.hpp:143
CglClique::scl_report_result
bool scl_report_result
whether to give a detailed statistics on the star clique method
Definition: CglClique.hpp:178
CglClique::frac_graph::density
double density
density= edgenum/(nodenum choose 2)
Definition: CglClique.hpp:117
CglClique::~CglClique
virtual ~CglClique()
Destructor.
Definition: CglClique.hpp:55
CglClique::fnode::edgecosts
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:102
CglClique::sp_row_start
int * sp_row_start
Definition: CglClique.hpp:150
CglFakeClique::generateCuts
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
CglClique::fnode::nbrs
int * nbrs
pointer into all_nbr
Definition: CglClique.hpp:99
CglClique::frac_graph::all_nbr
int * all_nbr
The array of all the neighbors.
Definition: CglClique.hpp:126
CglClique::do_star_clique
bool do_star_clique
whether to do the star clique algorithm or not.
Definition: CglClique.hpp:168
CglClique::clone
virtual CglCutGenerator * clone() const
Clone.
CglClique::CglClique
CglClique(const CglClique &rhs)
Copy constructor.
CglClique::setStarCliqueReport
void setStarCliqueReport(bool yesno=true)
Definition: CglClique.hpp:81
CglClique::CglCliqueUnitTest
friend void CglCliqueUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglClique class.
CglClique::cl_del_length
int cl_del_length
The length of cl_del_indices.
Definition: CglClique.hpp:209
CglClique::scl_next_node_rule
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:171
CglClique::fgraph
frac_graph fgraph
the intersection graph corresponding to the set packing problem
Definition: CglClique.hpp:154
CglClique::fnode
A node of the fractional graph.
Definition: CglClique.hpp:97
CglClique::selectFractionalBinaries
void selectFractionalBinaries(const OsiSolverInterface &si)
Scan through the variables and select those that are binary and are at a fractional level...
CglClique::setDoRowClique
void setDoRowClique(bool yesno=true)
Definition: CglClique.hpp:85
CglClique::do_row_clique
bool do_row_clique
data for the star clique algorithm
Definition: CglClique.hpp:166
CglClique::createSetPackingSubMatrix
void createSetPackingSubMatrix(const OsiSolverInterface &si)
CglClique::operator=
CglClique & operator=(const CglClique &rhs)
Assignment operator.
CglClique::sp_col_start
int * sp_col_start
Definition: CglClique.hpp:148
CglClique::find_rcl
void find_rcl(OsiCuts &cs)
CglClique::setDoStarClique
void setDoStarClique(bool yesno=true)
Definition: CglClique.hpp:84
CglClique::sp_orig_row_ind
int * sp_orig_row_ind
Definition: CglClique.hpp:144
CglClique::setRowCliqueCandidateLengthThreshold
void setRowCliqueCandidateLengthThreshold(int maxlen)
Definition: CglClique.hpp:77
CglClique::setMinViolation
void setMinViolation(double minviol)
Definition: CglClique.hpp:87
CglFakeClique::clone
virtual CglCutGenerator * clone() const
Clone.
CglClique::sp_colsol
double * sp_colsol
Definition: CglClique.hpp:147
CglClique::frac_graph::nodes
fnode * nodes
The array of the nodes in the graph.
Definition: CglClique.hpp:123
CglClique::node_node
bool * node_node
the node-node incidence matrix of the intersection graph.
Definition: CglClique.hpp:156
CglClique::createFractionalGraph
void createFractionalGraph()
CglClique::rcl_candidate_length_threshold
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:184
CglClique::petol
double petol
The primal tolerance in the solverinterface.
Definition: CglClique.hpp:159
CglClique::setPacking_
bool setPacking_
An indicator showing whether the whole matrix in the solverinterface is a set packing problem or not...
Definition: CglClique.hpp:139
CglClique::considerRows
void considerRows(const int numRows, const int *rowInd)
CglFakeClique::~CglFakeClique
virtual ~CglFakeClique()
Destructor.
CglClique::enumerate_maximal_cliques
int enumerate_maximal_cliques(int &pos, bool *scl_label, OsiCuts &cs)
CglClique::scl_candidate_length_threshold
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:176
CglFakeClique::assignSolver
void assignSolver(OsiSolverInterface *fakeSolver)
Assign solver (generator takes over ownership)
CglClique::scl_choose_next_node
int scl_choose_next_node(const int current_nodenum, const int *current_indices, const int *current_degrees, const double *current_values)
CglProbing
Probing Cut Generator Class.
Definition: CglProbing.hpp:25
CglClique::justOriginalRows_
bool justOriginalRows_
True if just look at original rows.
Definition: CglClique.hpp:141