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

- Alphabetical List
- Class List
- Class Hierarchy
- Class Members

# CglClique Class Reference

`#include <CglClique.hpp>`

Inheritance diagram for CglClique:

[legend]
Collaboration diagram for CglClique:

[legend]
List of all members.

## 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...
| CglClique (bool setPacking=false, bool justOriginalRows=false)
| Default constructor.
virtual | ~CglClique ()
| Destructor.
virtual std::string | generateCpp (FILE *fp)
| Create C++ lines to get to current state.
void | considerRows (const int numRows, const int *rowInd)
| possible choices for selecting the next node in the star clique search
void | setStarCliqueNextNodeMethod (scl_next_node_method method)
| possible choices for selecting the next node in the star clique search
void | setStarCliqueCandidateLengthThreshold (int maxlen)
| possible choices for selecting the next node in the star clique search
void | setRowCliqueCandidateLengthThreshold (int maxlen)
| possible choices for selecting the next node in the star clique search
void | setStarCliqueReport (bool yesno=true)
| possible choices for selecting the next node in the star clique search
void | setRowCliqueReport (bool yesno=true)
| possible choices for selecting the next node in the star clique search
void | setDoStarClique (bool yesno=true)
| possible choices for selecting the next node in the star clique search
void | setDoRowClique (bool yesno=true)
| possible choices for selecting the next node in the star clique search
void | setMinViolation (double minviol)
| possible choices for selecting the next node in the star clique search
double | getMinViolation () const
| possible choices for selecting the next node in the star clique search
bool | setPacking_
| An indicator showing whether the whole matrix in the solverinterface is a set packing problem or not.
bool | justOriginalRows_
| True if just look at original rows.
int | sp_numrows
| pieces of the set packing part of the solverinterface
int * | sp_orig_row_ind
| possible choices for selecting the next node in the star clique search
int | sp_numcols
| possible choices for selecting the next node in the star clique search
int * | sp_orig_col_ind
| possible choices for selecting the next node in the star clique search
double * | sp_colsol
| possible choices for selecting the next node in the star clique search
int * | sp_col_start
| possible choices for selecting the next node in the star clique search
int * | sp_col_ind
| possible choices for selecting the next node in the star clique search
int * | sp_row_start
| possible choices for selecting the next node in the star clique search
int * | sp_row_ind
| possible choices for selecting the next node in the star clique search
frac_graph | fgraph
| the intersection graph corresponding to the set packing problem
bool * | node_node
| the node-node incidence matrix of the intersection graph.
double | petol
| The primal tolerance in the solverinterface.
bool | do_row_clique
| whether to do the row clique algorithm or not.
bool | do_star_clique
| whether to do the star clique algorithm or not.
scl_next_node_method | scl_next_node_rule
| How the next node to be added to the star clique should be selected.
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.
bool | scl_report_result
| whether to give a detailed statistics on the star clique method
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.
bool | rcl_report_result
| whether to give a detailed statistics on the row clique method
struct | frac_graph
| possible choices for selecting the next node in the star clique search
## Public Member Functions
| CglClique (const CglClique &rhs)
| Copy constructor.
virtual CglCutGenerator * | clone () const
| Clone.
CglClique & | operator= (const CglClique &rhs)
| Assignment operator.
virtual void | generateCuts (const OsiSolverInterface &si, OsiCuts &cs, const CglTreeInfo info=CglTreeInfo()) const
| Generate cuts for the model data contained in si.
## Protected Attributes
const int * | cl_perm_indices
| List of indices that must be in the to be created clique.
int | cl_perm_length
| The length of cl_perm_indices.
int * | cl_indices
| List of indices that should be considered for extending the ones listed in cl_perm_indices.
int | cl_length
| The length of cl_indices.
int * | cl_del_indices
| An array of nodes discarded from the candidate list.
int | cl_del_length
| The length of cl_del_indices.
## Private Member Functions
void | selectFractionalBinaries (const OsiSolverInterface &si) const
| Scan through the variables and select those that are binary and are at a fractional level.
void | selectFractionals (const OsiSolverInterface &si) const
| Scan through the variables and select those that are at a fractional level.
void | selectRowCliques (const OsiSolverInterface &si, int numOriginalRows) const
void | createSetPackingSubMatrix (const OsiSolverInterface &si) const
void | createFractionalGraph () const
int | createNodeNode () const
void | deleteSetPackingSubMatrix () const
void | deleteFractionalGraph () const
void | find_scl (OsiCuts &cs) const
void | find_rcl (OsiCuts &cs) const
int | scl_choose_next_node (const int current_nodenum, const int *current_indices, const int *current_degrees, const double *current_values) const
void | scl_delete_node (const int del_ind, int &current_nodenum, int *current_indices, int *current_degrees, double *current_values) const
int | enumerate_maximal_cliques (int &pos, bool *scl_label, OsiCuts &cs) const
int | greedy_maximal_clique (OsiCuts &cs) const
void | recordClique (const int len, int *indices, OsiCuts &cs) const
## Friends
void | CglCliqueUnitTest (const OsiSolverInterface *siP, const std::string mpdDir)
| A function that tests the methods in the CglClique class.
## Classes
struct | fnode
| A node of the fractional graph. More...
struct | frac_graph
| A graph corresponding to a fractional solution of an LP. More...

## Detailed Description

Definition at line 9 of file CglClique.hpp.

## Member Enumeration Documentation

enum CglClique::scl_next_node_method

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 59 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 | ( |  | ) | `[inline, virtual]`

Destructor.

Definition at line 50 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()` |
| ) |  |  | const`[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 |
| ) |  |  |

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

void CglClique::setStarCliqueNextNodeMethod | ( | scl_next_node_method | method | ) | `[inline]`

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

Definition at line 65 of file CglClique.hpp.

References scl_next_node_rule.

void CglClique::setStarCliqueCandidateLengthThreshold | ( | int | maxlen | ) | `[inline]`

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

Definition at line 69 of file CglClique.hpp.

References scl_candidate_length_threshold.

void CglClique::setRowCliqueCandidateLengthThreshold | ( | int | maxlen | ) | `[inline]`

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

Definition at line 72 of file CglClique.hpp.

References rcl_candidate_length_threshold.

void CglClique::setStarCliqueReport | ( | bool | yesno = `true` | ) | `[inline]`

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

Definition at line 76 of file CglClique.hpp.

References scl_report_result.

void CglClique::setRowCliqueReport | ( | bool | yesno = `true` | ) | `[inline]`

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

Definition at line 77 of file CglClique.hpp.

References rcl_report_result.

void CglClique::setDoStarClique | ( | bool | yesno = `true` | ) | `[inline]`

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

Definition at line 79 of file CglClique.hpp.

References do_star_clique.

void CglClique::setDoRowClique | ( | bool | yesno = `true` | ) | `[inline]`

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

Definition at line 80 of file CglClique.hpp.

References do_row_clique.

void CglClique::setMinViolation | ( | double | minviol | ) | `[inline]`

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

Definition at line 82 of file CglClique.hpp.

References petol.

double CglClique::getMinViolation | ( |  | ) | const`[inline]`

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

Definition at line 83 of file CglClique.hpp.

References petol.

void CglClique::selectFractionalBinaries | ( | const OsiSolverInterface & | si | ) | const`[private]`

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

void CglClique::selectFractionals | ( | const OsiSolverInterface & | si | ) | const`[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 |
| ) |  |  | const`[private]`

void CglClique::createSetPackingSubMatrix | ( | const OsiSolverInterface & | si | ) | const`[private]`

void CglClique::createFractionalGraph | ( |  | ) | const`[private]`

int CglClique::createNodeNode | ( |  | ) | const`[private]`

void CglClique::deleteSetPackingSubMatrix | ( |  | ) | const`[private]`

void CglClique::deleteFractionalGraph | ( |  | ) | const`[private]`

void CglClique::find_scl | ( | OsiCuts & | cs | ) | const`[private]`

void CglClique::find_rcl | ( | OsiCuts & | cs | ) | const`[private]`

int CglClique::scl_choose_next_node | ( | const int | current_nodenum,
|  | const int * | current_indices,
|  | const int * | current_degrees,
|  | const double * | current_values |
| ) |  |  | const`[private]`

void CglClique::scl_delete_node | ( | const int | del_ind,
|  | int & | current_nodenum,
|  | int * | current_indices,
|  | int * | current_degrees,
|  | double * | current_values |
| ) |  |  | const`[private]`

int CglClique::enumerate_maximal_cliques | ( | int & | pos,
|  | bool * | scl_label,
|  | OsiCuts & | cs |
| ) |  |  | const`[private]`

int CglClique::greedy_maximal_clique | ( | OsiCuts & | cs | ) | const`[private]`

void CglClique::recordClique | ( | const int | len,
|  | int * | indices,
|  | OsiCuts & | cs |
| ) |  |  | const`[private]`

## Friends And Related Function Documentation

friend struct frac_graph`[friend]`

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

Definition at line 87 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 134 of file CglClique.hpp.

bool CglClique::justOriginalRows_`[protected]`

True if just look at original rows.

Definition at line 136 of file CglClique.hpp.

int CglClique::sp_numrows`[mutable, protected]`

pieces of the set packing part of the solverinterface

Definition at line 138 of file CglClique.hpp.

int* CglClique::sp_orig_row_ind`[mutable, protected]`

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

Definition at line 139 of file CglClique.hpp.

int CglClique::sp_numcols`[mutable, protected]`

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

Definition at line 140 of file CglClique.hpp.

int* CglClique::sp_orig_col_ind`[mutable, protected]`

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

Definition at line 141 of file CglClique.hpp.

double* CglClique::sp_colsol`[mutable, protected]`

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

Definition at line 142 of file CglClique.hpp.

int* CglClique::sp_col_start`[mutable, protected]`

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

Definition at line 143 of file CglClique.hpp.

int* CglClique::sp_col_ind`[mutable, protected]`

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

Definition at line 144 of file CglClique.hpp.

int* CglClique::sp_row_start`[mutable, protected]`

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

Definition at line 145 of file CglClique.hpp.

int* CglClique::sp_row_ind`[mutable, protected]`

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

Definition at line 146 of file CglClique.hpp.

frac_graph CglClique::fgraph`[mutable, protected]`

the intersection graph corresponding to the set packing problem

Definition at line 149 of file CglClique.hpp.

bool* CglClique::node_node`[mutable, protected]`

the node-node incidence matrix of the intersection graph.

Definition at line 151 of file CglClique.hpp.

double CglClique::petol`[mutable, protected]`

The primal tolerance in the solverinterface.

Definition at line 154 of file CglClique.hpp.

Referenced by getMinViolation(), and setMinViolation().

bool CglClique::do_row_clique`[protected]`

whether to do the row clique algorithm or not.

Definition at line 161 of file CglClique.hpp.

Referenced by setDoRowClique().

bool CglClique::do_star_clique`[protected]`

whether to do the star clique algorithm or not.

Definition at line 163 of file CglClique.hpp.

Referenced by setDoStarClique().

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 166 of file CglClique.hpp.

Referenced by setStarCliqueNextNodeMethod().

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 171 of file CglClique.hpp.

Referenced by setStarCliqueCandidateLengthThreshold().

bool CglClique::scl_report_result`[protected]`

whether to give a detailed statistics on the star clique method

Definition at line 173 of file CglClique.hpp.

Referenced by setStarCliqueReport().

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 179 of file CglClique.hpp.

Referenced by setRowCliqueCandidateLengthThreshold().

bool CglClique::rcl_report_result`[protected]`

whether to give a detailed statistics on the row clique method

Definition at line 181 of file CglClique.hpp.

Referenced by setRowCliqueReport().

const int* CglClique::cl_perm_indices`[mutable, protected]`

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 189 of file CglClique.hpp.

int CglClique::cl_perm_length`[mutable, protected]`

The length of cl_perm_indices.

Definition at line 191 of file CglClique.hpp.

int* CglClique::cl_indices`[mutable, protected]`

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

Definition at line 195 of file CglClique.hpp.

int CglClique::cl_length`[mutable, protected]`

The length of cl_indices.

Definition at line 197 of file CglClique.hpp.

int* CglClique::cl_del_indices`[mutable, 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 202 of file CglClique.hpp.

int CglClique::cl_del_length`[mutable, protected]`

The length of cl_del_indices.

Definition at line 204 of file CglClique.hpp.

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

- /home/coin/SVN-release/Bcps-0.91.0/Cgl/src/CglClique/CglClique.hpp