Cbc  2.10.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Public Member Functions | Private Member Functions | Friends | List of all members
CglClique Class Reference

#include <CglClique.hpp>

+ Inheritance diagram for CglClique:
+ Collaboration diagram for CglClique:

Classes

struct  fnode
 A node of the fractional graph. More...
 
struct  frac_graph
 A graph corresponding to a fractional solution of an LP. More...
 

Public Member Functions

 CglClique (const CglClique &rhs)
 Copy constructor. More...
 
virtual CglCutGeneratorclone () const
 Clone. More...
 
CglCliqueoperator= (const CglClique &rhs)
 Assignment operator. More...
 
virtual void generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo())
 Generate cuts for the model data contained in si. More...
 
- Public Member Functions inherited from CglCutGenerator
 CglCutGenerator ()
 Default constructor. More...
 
 CglCutGenerator (const CglCutGenerator &)
 Copy constructor. More...
 
CglCutGeneratoroperator= (const CglCutGenerator &rhs)
 Assignment operator. More...
 
virtual ~CglCutGenerator ()
 Destructor. More...
 
virtual void refreshSolver (OsiSolverInterface *)
 This can be used to refresh any information. More...
 
int getAggressiveness () const
 Get Aggressiveness - 0 = neutral, 100 is normal root node. More...
 
void setAggressiveness (int value)
 Set Aggressiveness - 0 = neutral, 100 is normal root node. More...
 
void setGlobalCuts (bool trueOrFalse)
 Set whether can do global cuts. More...
 
bool canDoGlobalCuts () const
 Say whether can do global cuts. More...
 
virtual bool mayGenerateRowCutsInTree () const
 Returns true if may generate Row cuts in tree (rather than root node). More...
 
virtual bool needsOptimalBasis () const
 Return true if needs optimal basis to do cuts. More...
 
virtual int maximumLengthOfCutInTree () const
 Return maximum length of cut in tree. More...
 

Protected Attributes

const int * cl_perm_indices
 variables/arrays that are used across many methods More...
 
int cl_perm_length
 The length of cl_perm_indices. More...
 
int * cl_indices
 List of indices that should be considered for extending the ones listed in cl_perm_indices. More...
 
int cl_length
 The length of cl_indices. More...
 
int * cl_del_indices
 An array of nodes discarded from the candidate list. More...
 
int cl_del_length
 The length of cl_del_indices. More...
 

Private Member Functions

void selectFractionalBinaries (const OsiSolverInterface &si)
 Scan through the variables and select those that are binary and are at a fractional level. More...
 
void selectFractionals (const OsiSolverInterface &si)
 Scan through the variables and select those that are at a fractional level. More...
 
void selectRowCliques (const OsiSolverInterface &si, int numOriginalRows)
 
void createSetPackingSubMatrix (const OsiSolverInterface &si)
 
void createFractionalGraph ()
 
int createNodeNode ()
 
void deleteSetPackingSubMatrix ()
 
void deleteFractionalGraph ()
 
void find_scl (OsiCuts &cs)
 
void find_rcl (OsiCuts &cs)
 
int scl_choose_next_node (const int current_nodenum, const int *current_indices, const int *current_degrees, const double *current_values)
 
void scl_delete_node (const int del_ind, int &current_nodenum, int *current_indices, int *current_degrees, double *current_values)
 
int enumerate_maximal_cliques (int &pos, bool *scl_label, OsiCuts &cs)
 
int greedy_maximal_clique (OsiCuts &cs)
 
void recordClique (const int len, int *indices, OsiCuts &cs)
 

Friends

void CglCliqueUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
 A function that tests the methods in the CglClique class. More...
 

Constructors and destructors

enum  scl_next_node_method { SCL_MIN_DEGREE, SCL_MAX_DEGREE, SCL_MAX_XJ_MAX_DEG }
 possible choices for selecting the next node in the star clique search More...
 
struct frac_graph
 
bool setPacking_
 An indicator showing whether the whole matrix in the solverinterface is a set packing problem or not. More...
 
bool justOriginalRows_
 True if just look at original rows. More...
 
int sp_numrows
 pieces of the set packing part of the solverinterface More...
 
int * sp_orig_row_ind
 
int sp_numcols
 
int * sp_orig_col_ind
 
double * sp_colsol
 
int * sp_col_start
 
int * sp_col_ind
 
int * sp_row_start
 
int * sp_row_ind
 
frac_graph fgraph
 the intersection graph corresponding to the set packing problem More...
 
bool * node_node
 the node-node incidence matrix of the intersection graph. More...
 
double petol
 The primal tolerance in the solverinterface. More...
 
int maxNumber_
 Maximum number of binaries for looking at all. More...
 
bool do_row_clique
 data for the star clique algorithm More...
 
bool do_star_clique
 whether to do the star clique algorithm or not. More...
 
scl_next_node_method scl_next_node_rule
 How the next node to be added to the star clique should be selected. More...
 
int scl_candidate_length_threshold
 In the star clique method the maximal length of the candidate list (those nodes that are in a star, i.e., connected to the center of the star) to allow complete enumeration of maximal cliques. More...
 
bool scl_report_result
 whether to give a detailed statistics on the star clique method More...
 
int rcl_candidate_length_threshold
 In the row clique method the maximal length of the candidate list (those nodes that can extend the row clique, i.e., connected to all nodes in the row clique) to allow complete enumeration of maximal cliques. More...
 
bool rcl_report_result
 whether to give a detailed statistics on the row clique method More...
 
 CglClique (bool setPacking=false, bool justOriginalRows=false)
 Default constructor. More...
 
virtual ~CglClique ()
 Destructor. More...
 
virtual std::string generateCpp (FILE *fp)
 Create C++ lines to get to current state. More...
 
void considerRows (const int numRows, const int *rowInd)
 
void setStarCliqueNextNodeMethod (scl_next_node_method method)
 
void setStarCliqueCandidateLengthThreshold (int maxlen)
 
void setRowCliqueCandidateLengthThreshold (int maxlen)
 
void setStarCliqueReport (bool yesno=true)
 
void setRowCliqueReport (bool yesno=true)
 
void setDoStarClique (bool yesno=true)
 
void setDoRowClique (bool yesno=true)
 
void setMinViolation (double minviol)
 
double getMinViolation () const
 
void setMaxNumber (int value)
 Maximum number of binaries for looking at all. More...
 

Additional Inherited Members

- Public Attributes inherited from CglCutGenerator
int aggressive_
 Aggressiveness - 0 = neutral, 100 is normal root node. More...
 
bool canDoGlobalCuts_
 True if can do global cuts i.e. no general integers. More...
 

Detailed Description

Definition at line 14 of file CglClique.hpp.

Member Enumeration Documentation

possible choices for selecting the next node in the star clique search

Enumerator
SCL_MIN_DEGREE 
SCL_MAX_DEGREE 
SCL_MAX_XJ_MAX_DEG 

Definition at line 64 of file CglClique.hpp.

Constructor & Destructor Documentation

CglClique::CglClique ( const CglClique rhs)

Copy constructor.

CglClique::CglClique ( bool  setPacking = false,
bool  justOriginalRows = false 
)

Default constructor.

If the setPacking argument is set to true then CglClique will assume that the problem in the solverinterface passed to the generateCuts() method describes a set packing problem, i.e.,

  • all variables are binary
  • the matrix is a 0-1 matrix
  • all constraints are '= 1' or '<= 1'

Otherwise the user can use the considerRows() method to set the list of clique rows, that is,

  • all coeffs corresponding to binary variables at fractional level is 1
  • all other coeffs are non-negative
  • the constraint is '= 1' or '<= 1'.

If the user does not set the list of clique rows then CglClique will start the generateCuts() methods by scanning the matrix for them. Also justOriginalRows can be set to true to limit clique creation

virtual CglClique::~CglClique ( )
inlinevirtual

Destructor.

Definition at line 55 of file CglClique.hpp.

Member Function Documentation

virtual CglCutGenerator* CglClique::clone ( ) const
virtual

Clone.

Implements CglCutGenerator.

Reimplemented in CglFakeClique.

CglClique& CglClique::operator= ( const CglClique rhs)

Assignment operator.

virtual void CglClique::generateCuts ( const OsiSolverInterface si,
OsiCuts cs,
const CglTreeInfo  info = CglTreeInfo() 
)
virtual

Generate cuts for the model data contained in si.

The generated cuts are inserted into and returned in the collection of cuts cs.

Implements CglCutGenerator.

Reimplemented in CglFakeClique.

virtual std::string CglClique::generateCpp ( FILE *  fp)
virtual

Create C++ lines to get to current state.

Reimplemented from CglCutGenerator.

void CglClique::considerRows ( const int  numRows,
const int *  rowInd 
)
void CglClique::setStarCliqueNextNodeMethod ( scl_next_node_method  method)
inline

Definition at line 70 of file CglClique.hpp.

void CglClique::setStarCliqueCandidateLengthThreshold ( int  maxlen)
inline

Definition at line 74 of file CglClique.hpp.

void CglClique::setRowCliqueCandidateLengthThreshold ( int  maxlen)
inline

Definition at line 77 of file CglClique.hpp.

void CglClique::setStarCliqueReport ( bool  yesno = true)
inline

Definition at line 81 of file CglClique.hpp.

void CglClique::setRowCliqueReport ( bool  yesno = true)
inline

Definition at line 82 of file CglClique.hpp.

void CglClique::setDoStarClique ( bool  yesno = true)
inline

Definition at line 84 of file CglClique.hpp.

void CglClique::setDoRowClique ( bool  yesno = true)
inline

Definition at line 85 of file CglClique.hpp.

void CglClique::setMinViolation ( double  minviol)
inline

Definition at line 87 of file CglClique.hpp.

double CglClique::getMinViolation ( ) const
inline

Definition at line 88 of file CglClique.hpp.

void CglClique::setMaxNumber ( int  value)
inline

Maximum number of binaries for looking at all.

Definition at line 90 of file CglClique.hpp.

void CglClique::selectFractionalBinaries ( const OsiSolverInterface si)
private

Scan through the variables and select those that are binary and are at a fractional level.

void CglClique::selectFractionals ( const OsiSolverInterface si)
private

Scan through the variables and select those that are at a fractional level.

We already know that everything is binary.

void CglClique::selectRowCliques ( const OsiSolverInterface si,
int  numOriginalRows 
)
private
void CglClique::createSetPackingSubMatrix ( const OsiSolverInterface si)
private
void CglClique::createFractionalGraph ( )
private
int CglClique::createNodeNode ( )
private
void CglClique::deleteSetPackingSubMatrix ( )
private
void CglClique::deleteFractionalGraph ( )
private
void CglClique::find_scl ( OsiCuts cs)
private
void CglClique::find_rcl ( OsiCuts cs)
private
int CglClique::scl_choose_next_node ( const int  current_nodenum,
const int *  current_indices,
const int *  current_degrees,
const double *  current_values 
)
private
void CglClique::scl_delete_node ( const int  del_ind,
int &  current_nodenum,
int *  current_indices,
int *  current_degrees,
double *  current_values 
)
private
int CglClique::enumerate_maximal_cliques ( int &  pos,
bool *  scl_label,
OsiCuts cs 
)
private
int CglClique::greedy_maximal_clique ( OsiCuts cs)
private
void CglClique::recordClique ( const int  len,
int *  indices,
OsiCuts cs 
)
private

Friends And Related Function Documentation

friend struct frac_graph
friend

Definition at line 94 of file CglClique.hpp.

void CglCliqueUnitTest ( const OsiSolverInterface siP,
const std::string  mpdDir 
)
friend

A function that tests the methods in the CglClique class.

The only reason for it not to be a member method is that this way it doesn't have to be compiled into the library. And that's a gain, because the library should be compiled with optimization on, but this method should be compiled with debugging.

Member Data Documentation

bool CglClique::setPacking_
protected

An indicator showing whether the whole matrix in the solverinterface is a set packing problem or not.

Definition at line 141 of file CglClique.hpp.

bool CglClique::justOriginalRows_
protected

True if just look at original rows.

Definition at line 143 of file CglClique.hpp.

int CglClique::sp_numrows
protected

pieces of the set packing part of the solverinterface

Definition at line 145 of file CglClique.hpp.

int* CglClique::sp_orig_row_ind
protected

Definition at line 146 of file CglClique.hpp.

int CglClique::sp_numcols
protected

Definition at line 147 of file CglClique.hpp.

int* CglClique::sp_orig_col_ind
protected

Definition at line 148 of file CglClique.hpp.

double* CglClique::sp_colsol
protected

Definition at line 149 of file CglClique.hpp.

int* CglClique::sp_col_start
protected

Definition at line 150 of file CglClique.hpp.

int* CglClique::sp_col_ind
protected

Definition at line 151 of file CglClique.hpp.

int* CglClique::sp_row_start
protected

Definition at line 152 of file CglClique.hpp.

int* CglClique::sp_row_ind
protected

Definition at line 153 of file CglClique.hpp.

frac_graph CglClique::fgraph
protected

the intersection graph corresponding to the set packing problem

Definition at line 156 of file CglClique.hpp.

bool* CglClique::node_node
protected

the node-node incidence matrix of the intersection graph.

Definition at line 158 of file CglClique.hpp.

double CglClique::petol
protected

The primal tolerance in the solverinterface.

Definition at line 161 of file CglClique.hpp.

int CglClique::maxNumber_
protected

Maximum number of binaries for looking at all.

Definition at line 163 of file CglClique.hpp.

bool CglClique::do_row_clique
protected

data for the star clique algorithm

Parameters whether to do the row clique algorithm or not.

Definition at line 170 of file CglClique.hpp.

bool CglClique::do_star_clique
protected

whether to do the star clique algorithm or not.

Definition at line 172 of file CglClique.hpp.

scl_next_node_method CglClique::scl_next_node_rule
protected

How the next node to be added to the star clique should be selected.

Definition at line 175 of file CglClique.hpp.

int CglClique::scl_candidate_length_threshold
protected

In the star clique method the maximal length of the candidate list (those nodes that are in a star, i.e., connected to the center of the star) to allow complete enumeration of maximal cliques.

Otherwise a greedy algorithm is used.

Definition at line 180 of file CglClique.hpp.

bool CglClique::scl_report_result
protected

whether to give a detailed statistics on the star clique method

Definition at line 182 of file CglClique.hpp.

int CglClique::rcl_candidate_length_threshold
protected

In the row clique method the maximal length of the candidate list (those nodes that can extend the row clique, i.e., connected to all nodes in the row clique) to allow complete enumeration of maximal cliques.

Otherwise a greedy algorithm is used.

Definition at line 188 of file CglClique.hpp.

bool CglClique::rcl_report_result
protected

whether to give a detailed statistics on the row clique method

Definition at line 190 of file CglClique.hpp.

const int* CglClique::cl_perm_indices
protected

variables/arrays that are used across many methods

List of indices that must be in the to be created clique. This is just a pointer, it is never new'd and therefore does not need to be delete[]'d either.

Definition at line 198 of file CglClique.hpp.

int CglClique::cl_perm_length
protected

The length of cl_perm_indices.

Definition at line 200 of file CglClique.hpp.

int* CglClique::cl_indices
protected

List of indices that should be considered for extending the ones listed in cl_perm_indices.

Definition at line 204 of file CglClique.hpp.

int CglClique::cl_length
protected

The length of cl_indices.

Definition at line 206 of file CglClique.hpp.

int* CglClique::cl_del_indices
protected

An array of nodes discarded from the candidate list.

These are rechecked when a maximal clique is found just to make sure that the clique is really maximal.

Definition at line 211 of file CglClique.hpp.

int CglClique::cl_del_length
protected

The length of cl_del_indices.

Definition at line 213 of file CglClique.hpp.


The documentation for this class was generated from the following file: