#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 CglCutGenerator *	clone () const
	Clone. More...

CglClique &	operator= (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...

CglCutGenerator &	operator= (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
	possible choices for selecting the next node in the star clique search More...

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
	possible choices for selecting the next node in the star clique search More...

int	sp_numcols
	possible choices for selecting the next node in the star clique search More...

int *	sp_orig_col_ind
	possible choices for selecting the next node in the star clique search More...

double *	sp_colsol
	possible choices for selecting the next node in the star clique search More...

int *	sp_col_start
	possible choices for selecting the next node in the star clique search More...

int *	sp_col_ind
	possible choices for selecting the next node in the star clique search More...

int *	sp_row_start
	possible choices for selecting the next node in the star clique search More...

int *	sp_row_ind
	possible choices for selecting the next node in the star clique search More...

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...

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)
	possible choices for selecting the next node in the star clique search More...

void	setStarCliqueNextNodeMethod (scl_next_node_method method)
	possible choices for selecting the next node in the star clique search More...

void	setStarCliqueCandidateLengthThreshold (int maxlen)
	possible choices for selecting the next node in the star clique search More...

void	setRowCliqueCandidateLengthThreshold (int maxlen)
	possible choices for selecting the next node in the star clique search More...

void	setStarCliqueReport (bool yesno=true)
	possible choices for selecting the next node in the star clique search More...

void	setRowCliqueReport (bool yesno=true)
	possible choices for selecting the next node in the star clique search More...

void	setDoStarClique (bool yesno=true)
	possible choices for selecting the next node in the star clique search More...

void	setDoRowClique (bool yesno=true)
	possible choices for selecting the next node in the star clique search More...

void	setMinViolation (double minviol)
	possible choices for selecting the next node in the star clique search More...

double	getMinViolation () const
	possible choices for selecting the next node in the star clique search 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

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 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
	)

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

void CglClique::setStarCliqueCandidateLengthThreshold ( int maxlen )

inline

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

Definition at line 74 of file CglClique.hpp.

void CglClique::setRowCliqueCandidateLengthThreshold ( int maxlen )

inline

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

Definition at line 77 of file CglClique.hpp.

void CglClique::setStarCliqueReport ( bool yesno = true )

inline

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

Definition at line 81 of file CglClique.hpp.

void CglClique::setRowCliqueReport ( bool yesno = true )

inline

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

Definition at line 82 of file CglClique.hpp.

void CglClique::setDoStarClique ( bool yesno = true )

inline

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

Definition at line 84 of file CglClique.hpp.

void CglClique::setDoRowClique ( bool yesno = true )

inline

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

Definition at line 85 of file CglClique.hpp.

void CglClique::setMinViolation ( double minviol )

inline

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

Definition at line 87 of file CglClique.hpp.

double CglClique::getMinViolation ( ) const

inline

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

Definition at line 88 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

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

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

bool CglClique::justOriginalRows_

protected

True if just look at original rows.

Definition at line 141 of file CglClique.hpp.

int CglClique::sp_numrows

protected

pieces of the set packing part of the solverinterface

Definition at line 143 of file CglClique.hpp.

int* CglClique::sp_orig_row_ind

protected

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

Definition at line 144 of file CglClique.hpp.

int CglClique::sp_numcols

protected

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

Definition at line 145 of file CglClique.hpp.

int* CglClique::sp_orig_col_ind

protected

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

Definition at line 146 of file CglClique.hpp.

double* CglClique::sp_colsol

protected

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

Definition at line 147 of file CglClique.hpp.

int* CglClique::sp_col_start

protected

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

Definition at line 148 of file CglClique.hpp.

int* CglClique::sp_col_ind

protected

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

Definition at line 149 of file CglClique.hpp.

int* CglClique::sp_row_start

protected

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

Definition at line 150 of file CglClique.hpp.

int* CglClique::sp_row_ind

protected

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

Definition at line 151 of file CglClique.hpp.

frac_graph CglClique::fgraph

protected

the intersection graph corresponding to the set packing problem

Definition at line 154 of file CglClique.hpp.

bool* CglClique::node_node

protected

the node-node incidence matrix of the intersection graph.

Definition at line 156 of file CglClique.hpp.

double CglClique::petol

protected

The primal tolerance in the solverinterface.

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

bool CglClique::do_star_clique

protected

whether to do the star clique algorithm or not.

Definition at line 168 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 171 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 176 of file CglClique.hpp.

bool CglClique::scl_report_result

protected

whether to give a detailed statistics on the star clique method

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

bool CglClique::rcl_report_result

protected

whether to give a detailed statistics on the row clique method

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

int CglClique::cl_perm_length

protected

The length of cl_perm_indices.

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

int CglClique::cl_length

protected

The length of cl_indices.

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

int CglClique::cl_del_length

protected

The length of cl_del_indices.

Definition at line 209 of file CglClique.hpp.

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

/home/coin/svn-release/Blis-0.94.3/Cgl/src/CglClique/CglClique.hpp

Classes

Public Member Functions

Protected Attributes

Private Member Functions

Friends

Constructors and destructors

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation