FathomDynamicProgramming class. More...

#include <CbcFathomDynamicProgramming.hpp>

Inheritance diagram for CbcFathomDynamicProgramming:

Collaboration diagram for CbcFathomDynamicProgramming:

Public Member Functions
	CbcFathomDynamicProgramming ()

	CbcFathomDynamicProgramming (CbcModel &model)

	CbcFathomDynamicProgramming (const CbcFathomDynamicProgramming &rhs)

virtual	~CbcFathomDynamicProgramming ()

virtual void	setModel (CbcModel *model)
	update model (This is needed if cliques update matrix etc) More...

virtual CbcFathom *	clone () const
	Clone. More...

virtual void	resetModel (CbcModel *model)
	Resets stuff if model changes. More...

virtual int	fathom (double *&newSolution)
	returns 0 if no fathoming attempted, 1 fully fathomed , 2 incomplete search, 3 incomplete search but treat as complete. More...

int	maximumSize () const
	Maximum size allowed. More...

void	setMaximumSize (int value)

int	checkPossible (int allowableSize=0)
	Returns type of algorithm and sets up arrays. More...

void	setAlgorithm (int value)

bool	tryColumn (int numberElements, const int rows, const double coefficients, double cost, int upper=COIN_INT_MAX)
	Tries a column returns true if was used in making any changes. More...

const double *	cost () const
	Returns cost array. More...

const int *	back () const
	Returns back array. More...

int	target () const
	Gets bit pattern for target result. More...

void	setTarget (int value)
	Sets bit pattern for target result. More...

Public Member Functions inherited from CbcFathom
	CbcFathom ()

	CbcFathom (CbcModel &model)

virtual	~CbcFathom ()

bool	possible () const

Protected Attributes
int	size_
	Size of states (power of 2 unless just one constraint) More...

int	type_
	Type - 0 coefficients and rhs all 1, 1 - coefficients > 1 or rhs > 1. More...

double *	cost_
	Space for states. More...

int *	back_
	Which state produced this cheapest one. More...

int *	lookup_
	Some rows may be satisified so we need a lookup. More...

int *	indices_
	Space for sorted indices. More...

int	numberActive_
	Number of active rows. More...

int	maximumSizeAllowed_
	Maximum size allowed. More...

int *	startBit_
	Start bit for each active row. More...

int *	numberBits_
	Number bits for each active row. More...

int *	rhs_
	Effective rhs. More...

int *	coefficients_
	Space for sorted coefficients. More...

int	target_
	Target pattern. More...

int	numberNonOne_
	Number of Non 1 rhs. More...

int	bitPattern_
	Current bit pattern. More...

int	algorithm_
	Current algorithm. More...

Protected Attributes inherited from CbcFathom
CbcModel *	model_
	Model. More...

bool	possible_
	Possible - if this method of fathoming can be used. More...

Private Member Functions
void	gutsOfDelete ()
	Does deleteions. More...

bool	addOneColumn0 (int numberElements, const int *rows, double cost)
	Adds one attempt of one column of type 0, returns true if was used in making any changes. More...

bool	addOneColumn1 (int numberElements, const int rows, const int coefficients, double cost)
	Adds one attempt of one column of type 1, returns true if was used in making any changes. More...

bool	addOneColumn1A (int numberElements, const int rows, const int coefficients, double cost)
	Adds one attempt of one column of type 1, returns true if was used in making any changes. More...

int	bitPattern (int numberElements, const int rows, const int coefficients)
	Gets bit pattern from original column. More...

int	bitPattern (int numberElements, const int rows, const double coefficients)
	Gets bit pattern from original column. More...

int	decodeBitPattern (int bitPattern, int *values, int numberRows)
	Fills in original column (dense) from bit pattern - returning number nonzero. More...

CbcFathomDynamicProgramming &	operator= (const CbcFathomDynamicProgramming &rhs)
	Illegal Assignment operator. More...

Detailed Description

FathomDynamicProgramming class.

The idea is that after some branching the problem will be effectively smaller than the original problem and maybe there will be a more specialized technique which can completely fathom this branch quickly.

This is a dynamic programming implementation which is very fast for some specialized problems. It expects small integral rhs, an all integer problem and positive integral coefficients. At present it can not do general set covering problems just set partitioning. It can find multiple optima for various rhs combinations.

The main limiting factor is size of state space. Each 1 rhs doubles the size of the problem. 2 or 3 rhs quadruples, 4,5,6,7 by 8 etc.

Definition at line 28 of file CbcFathomDynamicProgramming.hpp.

Constructor & Destructor Documentation

◆ CbcFathomDynamicProgramming() [1/3]

CbcFathomDynamicProgramming::CbcFathomDynamicProgramming ( )

◆ CbcFathomDynamicProgramming() [2/3]

CbcFathomDynamicProgramming::CbcFathomDynamicProgramming ( CbcModel & model )

◆ CbcFathomDynamicProgramming() [3/3]

CbcFathomDynamicProgramming::CbcFathomDynamicProgramming ( const CbcFathomDynamicProgramming & rhs )

◆ ~CbcFathomDynamicProgramming()

virtual CbcFathomDynamicProgramming::~CbcFathomDynamicProgramming ( )

virtual

Member Function Documentation

◆ setModel()

virtual void CbcFathomDynamicProgramming::setModel ( CbcModel * model )

virtual

update model (This is needed if cliques update matrix etc)

Reimplemented from CbcFathom.

◆ clone()

virtual CbcFathom* CbcFathomDynamicProgramming::clone ( ) const

virtual

Clone.

Implements CbcFathom.

◆ resetModel()

virtual void CbcFathomDynamicProgramming::resetModel ( CbcModel * model )

virtual

Resets stuff if model changes.

Implements CbcFathom.

◆ fathom()

virtual int CbcFathomDynamicProgramming::fathom ( double *& newSolution )

virtual

returns 0 if no fathoming attempted, 1 fully fathomed , 2 incomplete search, 3 incomplete search but treat as complete.

If solution then newSolution will not be NULL and will be freed by CbcModel. It is expected that the solution is better than best so far but CbcModel will double check.

If returns 3 then of course there is no guarantee of global optimum

Implements CbcFathom.

◆ maximumSize()

int CbcFathomDynamicProgramming::maximumSize ( ) const

inline

Maximum size allowed.

Definition at line 60 of file CbcFathomDynamicProgramming.hpp.

◆ setMaximumSize()

void CbcFathomDynamicProgramming::setMaximumSize ( int value )

inline

Definition at line 64 of file CbcFathomDynamicProgramming.hpp.

◆ checkPossible()

int CbcFathomDynamicProgramming::checkPossible ( int allowableSize = 0 )

Returns type of algorithm and sets up arrays.

◆ setAlgorithm()

void CbcFathomDynamicProgramming::setAlgorithm ( int value )

inline

Definition at line 71 of file CbcFathomDynamicProgramming.hpp.

◆ tryColumn()

bool CbcFathomDynamicProgramming::tryColumn	(	int	numberElements,
		const int *	rows,
		const double *	coefficients,
		double	cost,
		int	upper = `COIN_INT_MAX`
	)

Tries a column returns true if was used in making any changes.

◆ cost()

const double* CbcFathomDynamicProgramming::cost ( ) const

inline

Returns cost array.

Definition at line 82 of file CbcFathomDynamicProgramming.hpp.

◆ back()

const int* CbcFathomDynamicProgramming::back ( ) const

inline

Returns back array.

Definition at line 87 of file CbcFathomDynamicProgramming.hpp.

◆ target()

int CbcFathomDynamicProgramming::target ( ) const

inline

Gets bit pattern for target result.

Definition at line 92 of file CbcFathomDynamicProgramming.hpp.

◆ setTarget()

void CbcFathomDynamicProgramming::setTarget ( int value )

inline

Sets bit pattern for target result.

Definition at line 97 of file CbcFathomDynamicProgramming.hpp.

◆ gutsOfDelete()

void CbcFathomDynamicProgramming::gutsOfDelete ( )

private

Does deleteions.

◆ addOneColumn0()

bool CbcFathomDynamicProgramming::addOneColumn0	(	int	numberElements,
		const int *	rows,
		double	cost
	)

private

Adds one attempt of one column of type 0, returns true if was used in making any changes.

◆ addOneColumn1()

bool CbcFathomDynamicProgramming::addOneColumn1	(	int	numberElements,
		const int *	rows,
		const int *	coefficients,
		double	cost
	)

private

Adds one attempt of one column of type 1, returns true if was used in making any changes.

At present the user has to call it once for each possible value

◆ addOneColumn1A()

bool CbcFathomDynamicProgramming::addOneColumn1A	(	int	numberElements,
		const int *	rows,
		const int *	coefficients,
		double	cost
	)

private

Adds one attempt of one column of type 1, returns true if was used in making any changes.

At present the user has to call it once for each possible value. This version is when there are enough 1 rhs to do faster

◆ bitPattern() [1/2]

int CbcFathomDynamicProgramming::bitPattern	(	int	numberElements,
		const int *	rows,
		const int *	coefficients
	)

private

Gets bit pattern from original column.

◆ bitPattern() [2/2]

int CbcFathomDynamicProgramming::bitPattern	(	int	numberElements,
		const int *	rows,
		const double *	coefficients
	)

private

Gets bit pattern from original column.

◆ decodeBitPattern()

int CbcFathomDynamicProgramming::decodeBitPattern	(	int	bitPattern,
		int *	values,
		int	numberRows
	)

private

Fills in original column (dense) from bit pattern - returning number nonzero.

◆ operator=()

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

private

Illegal Assignment operator.

Member Data Documentation

◆ size_

int CbcFathomDynamicProgramming::size_

protected

Size of states (power of 2 unless just one constraint)

Definition at line 135 of file CbcFathomDynamicProgramming.hpp.

◆ type_

int CbcFathomDynamicProgramming::type_

protected

Type - 0 coefficients and rhs all 1, 1 - coefficients > 1 or rhs > 1.

Definition at line 139 of file CbcFathomDynamicProgramming.hpp.

◆ cost_

double* CbcFathomDynamicProgramming::cost_

protected

Space for states.

Definition at line 141 of file CbcFathomDynamicProgramming.hpp.

◆ back_

int* CbcFathomDynamicProgramming::back_

protected

Which state produced this cheapest one.

Definition at line 143 of file CbcFathomDynamicProgramming.hpp.

◆ lookup_

int* CbcFathomDynamicProgramming::lookup_

protected

Some rows may be satisified so we need a lookup.

Definition at line 145 of file CbcFathomDynamicProgramming.hpp.

◆ indices_

int* CbcFathomDynamicProgramming::indices_

protected

Space for sorted indices.

Definition at line 147 of file CbcFathomDynamicProgramming.hpp.

◆ numberActive_

int CbcFathomDynamicProgramming::numberActive_

protected

Number of active rows.

Definition at line 149 of file CbcFathomDynamicProgramming.hpp.

◆ maximumSizeAllowed_

int CbcFathomDynamicProgramming::maximumSizeAllowed_

protected

Maximum size allowed.

Definition at line 151 of file CbcFathomDynamicProgramming.hpp.

◆ startBit_

int* CbcFathomDynamicProgramming::startBit_

protected

Start bit for each active row.

Definition at line 153 of file CbcFathomDynamicProgramming.hpp.

◆ numberBits_

int* CbcFathomDynamicProgramming::numberBits_

protected

Number bits for each active row.

Definition at line 155 of file CbcFathomDynamicProgramming.hpp.

◆ rhs_

int* CbcFathomDynamicProgramming::rhs_

protected

Effective rhs.

Definition at line 157 of file CbcFathomDynamicProgramming.hpp.

◆ coefficients_

int* CbcFathomDynamicProgramming::coefficients_

protected

Space for sorted coefficients.

Definition at line 159 of file CbcFathomDynamicProgramming.hpp.

◆ target_

int CbcFathomDynamicProgramming::target_

protected

Target pattern.

Definition at line 161 of file CbcFathomDynamicProgramming.hpp.

◆ numberNonOne_

int CbcFathomDynamicProgramming::numberNonOne_

protected

Number of Non 1 rhs.

Definition at line 163 of file CbcFathomDynamicProgramming.hpp.

◆ bitPattern_

int CbcFathomDynamicProgramming::bitPattern_

protected

Current bit pattern.

Definition at line 165 of file CbcFathomDynamicProgramming.hpp.

◆ algorithm_

int CbcFathomDynamicProgramming::algorithm_

protected

Current algorithm.

Definition at line 167 of file CbcFathomDynamicProgramming.hpp.

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

/home/ted/Projects/Cbc/Cbc/src/CbcFathomDynamicProgramming.hpp

Public Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ CbcFathomDynamicProgramming() [1/3]

◆ CbcFathomDynamicProgramming() [2/3]

◆ CbcFathomDynamicProgramming() [3/3]

◆ ~CbcFathomDynamicProgramming()

Member Function Documentation

◆ setModel()

◆ clone()

◆ resetModel()

◆ fathom()

◆ maximumSize()

◆ setMaximumSize()

◆ checkPossible()

◆ setAlgorithm()

◆ tryColumn()

◆ cost()

◆ back()

◆ target()

◆ setTarget()

◆ gutsOfDelete()

◆ addOneColumn0()

◆ addOneColumn1()

◆ addOneColumn1A()

◆ bitPattern() [1/2]

◆ bitPattern() [2/2]

◆ decodeBitPattern()

◆ operator=()

Member Data Documentation

◆ size_

◆ type_

◆ cost_

◆ back_

◆ lookup_

◆ indices_

◆ numberActive_

◆ maximumSizeAllowed_

◆ startBit_

◆ numberBits_

◆ rhs_

◆ coefficients_

◆ target_

◆ numberNonOne_

◆ bitPattern_

◆ algorithm_