Cgl 0.60.3
Loading...
Searching...
No Matches
CglClique.hpp
Go to the documentation of this file.
1// $Id$
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
14class CglClique : public CglCutGenerator {
15
16 friend void CglCliqueUnitTest(const OsiSolverInterface * siP,
17 const std::string mpdDir );
18public:
20 CglClique(const CglClique& rhs);
22 virtual CglCutGenerator * clone() const;
23
26
27public:
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
61public:
69
73
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
92private:
93
94 struct frac_graph ;
95 friend struct frac_graph ;
96
99 struct fnode {
101 int *nbrs;
104 double *edgecosts;
108 double val;
109 };
110
137
138protected:
149 double* sp_colsol;
154
159
161 double petol;
164
173
183
198 const int* cl_perm_indices;
201
207
214
217private:
220 void selectFractionalBinaries(const OsiSolverInterface& si);
223 void selectFractionals(const OsiSolverInterface& si);
225 void selectRowCliques(const OsiSolverInterface& si,int numOriginalRows);
227 void createSetPackingSubMatrix(const OsiSolverInterface& si);
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);
252 int greedy_maximal_clique(OsiCuts& cs);
254 void recordClique(const int len, int* indices, OsiCuts& cs);
255};
256//#############################################################################
262void CglCliqueUnitTest(const OsiSolverInterface * siP,
263 const std::string mpdDir);
265class CglProbing;
266class CglFakeClique : public CglClique {
267
268public:
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);
305protected:
307 OsiSolverInterface * fakeSolver_;
310};
311
312#endif
void CglCliqueUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglClique class.
int * cl_del_indices
An array of nodes discarded from the candidate list.
void selectFractionals(const OsiSolverInterface &si)
Scan through the variables and select those that are at a fractional level.
int rcl_candidate_length_threshold
In the row clique method the maximal length of the candidate list (those nodes that can extend the ro...
int enumerate_maximal_cliques(int &pos, bool *scl_label, OsiCuts &cs)
CglClique(bool setPacking=false, bool justOriginalRows=false)
Default constructor.
void setDoStarClique(bool yesno=true)
Definition CglClique.hpp:84
void deleteSetPackingSubMatrix()
void setStarCliqueCandidateLengthThreshold(int maxlen)
Definition CglClique.hpp:74
int * sp_col_start
int scl_candidate_length_threshold
In the star clique method the maximal length of the candidate list (those nodes that are in a star,...
void setRowCliqueReport(bool yesno=true)
Definition CglClique.hpp:82
int cl_length
The length of cl_indices.
virtual std::string generateCpp(FILE *fp)
Create C++ lines to get to current state.
int maxNumber_
Maximum number of binaries for looking at all.
const int * cl_perm_indices
variables/arrays that are used across many methods
void setDoRowClique(bool yesno=true)
Definition CglClique.hpp:85
bool justOriginalRows_
True if just look at original rows.
int sp_numrows
pieces of the set packing part of the solverinterface
CglClique & operator=(const CglClique &rhs)
Assignment operator.
void selectRowCliques(const OsiSolverInterface &si, int numOriginalRows)
void considerRows(const int numRows, const int *rowInd)
int scl_choose_next_node(const int current_nodenum, const int *current_indices, const int *current_degrees, const double *current_values)
void setStarCliqueNextNodeMethod(scl_next_node_method method)
Definition CglClique.hpp:70
void deleteFractionalGraph()
virtual ~CglClique()
Destructor.
Definition CglClique.hpp:55
CglClique(const CglClique &rhs)
Copy constructor.
void recordClique(const int len, int *indices, OsiCuts &cs)
int * sp_row_start
int cl_perm_length
The length of cl_perm_indices.
int createNodeNode()
scl_next_node_method
possible choices for selecting the next node in the star clique search
Definition CglClique.hpp:64
@ SCL_MAX_XJ_MAX_DEG
Definition CglClique.hpp:67
void setMaxNumber(int value)
Maximum number of binaries for looking at all.
Definition CglClique.hpp:90
int * sp_col_ind
void setMinViolation(double minviol)
Definition CglClique.hpp:87
frac_graph fgraph
the intersection graph corresponding to the set packing problem
virtual CglCutGenerator * clone() const
Clone.
bool * node_node
the node-node incidence matrix of the intersection graph.
int greedy_maximal_clique(OsiCuts &cs)
int * sp_orig_col_ind
void setStarCliqueReport(bool yesno=true)
Definition CglClique.hpp:81
bool do_row_clique
data for the star clique algorithm
int * cl_indices
List of indices that should be considered for extending the ones listed in cl_perm_indices.
double getMinViolation() const
Definition CglClique.hpp:88
void selectFractionalBinaries(const OsiSolverInterface &si)
Scan through the variables and select those that are binary and are at a fractional level.
void find_scl(OsiCuts &cs)
void find_rcl(OsiCuts &cs)
void createSetPackingSubMatrix(const OsiSolverInterface &si)
bool scl_report_result
whether to give a detailed statistics on the star clique method
void setRowCliqueCandidateLengthThreshold(int maxlen)
Definition CglClique.hpp:77
bool setPacking_
An indicator showing whether the whole matrix in the solverinterface is a set packing problem or not.
double * sp_colsol
void createFractionalGraph()
int * sp_row_ind
friend void CglCliqueUnitTest(const OsiSolverInterface *siP, const std::string mpdDir)
A function that tests the methods in the CglClique class.
friend struct frac_graph
Definition CglClique.hpp:95
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
bool do_star_clique
whether to do the star clique algorithm or not.
void scl_delete_node(const int del_ind, int &current_nodenum, int *current_indices, int *current_degrees, double *current_values)
int cl_del_length
The length of cl_del_indices.
bool rcl_report_result
whether to give a detailed statistics on the row clique method
double petol
The primal tolerance in the solverinterface.
int * sp_orig_row_ind
scl_next_node_method scl_next_node_rule
How the next node to be added to the star clique should be selected.
Cut Generator Base Class.
virtual CglCutGenerator * clone() const
Clone.
CglFakeClique(OsiSolverInterface *solver=NULL, bool setPacking=false)
Default constructor.
virtual void generateCuts(const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
Generate cuts for the model data contained in si.
CglFakeClique(const CglFakeClique &rhs)
Copy constructor.
CglProbing * probing_
Probing object.
CglFakeClique & operator=(const CglFakeClique &rhs)
Assignment operator.
OsiSolverInterface * fakeSolver_
fake solver to use
virtual ~CglFakeClique()
Destructor.
void assignSolver(OsiSolverInterface *fakeSolver)
Assign solver (generator takes over ownership)
Probing Cut Generator Class.
Information about where the cut generator is invoked from.
A node of the fractional graph.
Definition CglClique.hpp:99
int degree
degree of the node
int * nbrs
pointer into all_nbr
double val
the fractional value of the variable corresponding to this node
double * edgecosts
1-x_i-x_j, needed for odd holes, in the same order as the adj list, pointer into all_edgecost
A graph corresponding to a fractional solution of an LP.
double density
density= edgenum/(nodenum choose 2)
int * all_nbr
The array of all the neighbors.
fnode * nodes
The array of the nodes in the graph.
double * all_edgecost
The array of the costs of the edges going to the neighbors.