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

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 CbcFathomclone () 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
CbcModelmodel_
 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...
 
CbcFathomDynamicProgrammingoperator= (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::CbcFathomDynamicProgramming ( )
CbcFathomDynamicProgramming::CbcFathomDynamicProgramming ( CbcModel model)
CbcFathomDynamicProgramming::CbcFathomDynamicProgramming ( const CbcFathomDynamicProgramming rhs)
virtual CbcFathomDynamicProgramming::~CbcFathomDynamicProgramming ( )
virtual

Member Function Documentation

virtual void CbcFathomDynamicProgramming::setModel ( CbcModel model)
virtual

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

Reimplemented from CbcFathom.

virtual CbcFathom* CbcFathomDynamicProgramming::clone ( ) const
virtual

Clone.

Implements CbcFathom.

virtual void CbcFathomDynamicProgramming::resetModel ( CbcModel model)
virtual

Resets stuff if model changes.

Implements CbcFathom.

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.

int CbcFathomDynamicProgramming::maximumSize ( ) const
inline

Maximum size allowed.

Definition at line 60 of file CbcFathomDynamicProgramming.hpp.

void CbcFathomDynamicProgramming::setMaximumSize ( int  value)
inline

Definition at line 63 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::checkPossible ( int  allowableSize = 0)

Returns type of algorithm and sets up arrays.

void CbcFathomDynamicProgramming::setAlgorithm ( int  value)
inline

Definition at line 69 of file CbcFathomDynamicProgramming.hpp.

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.

const double* CbcFathomDynamicProgramming::cost ( ) const
inline

Returns cost array.

Definition at line 79 of file CbcFathomDynamicProgramming.hpp.

const int* CbcFathomDynamicProgramming::back ( ) const
inline

Returns back array.

Definition at line 83 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::target ( ) const
inline

Gets bit pattern for target result.

Definition at line 87 of file CbcFathomDynamicProgramming.hpp.

void CbcFathomDynamicProgramming::setTarget ( int  value)
inline

Sets bit pattern for target result.

Definition at line 91 of file CbcFathomDynamicProgramming.hpp.

void CbcFathomDynamicProgramming::gutsOfDelete ( )
private

Does deleteions.

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.

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

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

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

Gets bit pattern from original column.

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

Gets bit pattern from original column.

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

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

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

Illegal Assignment operator.

Member Data Documentation

int CbcFathomDynamicProgramming::size_
protected

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

Definition at line 128 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::type_
protected

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

Definition at line 132 of file CbcFathomDynamicProgramming.hpp.

double* CbcFathomDynamicProgramming::cost_
protected

Space for states.

Definition at line 134 of file CbcFathomDynamicProgramming.hpp.

int* CbcFathomDynamicProgramming::back_
protected

Which state produced this cheapest one.

Definition at line 136 of file CbcFathomDynamicProgramming.hpp.

int* CbcFathomDynamicProgramming::lookup_
protected

Some rows may be satisified so we need a lookup.

Definition at line 138 of file CbcFathomDynamicProgramming.hpp.

int* CbcFathomDynamicProgramming::indices_
protected

Space for sorted indices.

Definition at line 140 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::numberActive_
protected

Number of active rows.

Definition at line 142 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::maximumSizeAllowed_
protected

Maximum size allowed.

Definition at line 144 of file CbcFathomDynamicProgramming.hpp.

int* CbcFathomDynamicProgramming::startBit_
protected

Start bit for each active row.

Definition at line 146 of file CbcFathomDynamicProgramming.hpp.

int* CbcFathomDynamicProgramming::numberBits_
protected

Number bits for each active row.

Definition at line 148 of file CbcFathomDynamicProgramming.hpp.

int* CbcFathomDynamicProgramming::rhs_
protected

Effective rhs.

Definition at line 150 of file CbcFathomDynamicProgramming.hpp.

int* CbcFathomDynamicProgramming::coefficients_
protected

Space for sorted coefficients.

Definition at line 152 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::target_
protected

Target pattern.

Definition at line 154 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::numberNonOne_
protected

Number of Non 1 rhs.

Definition at line 156 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::bitPattern_
protected

Current bit pattern.

Definition at line 158 of file CbcFathomDynamicProgramming.hpp.

int CbcFathomDynamicProgramming::algorithm_
protected

Current algorithm.

Definition at line 160 of file CbcFathomDynamicProgramming.hpp.


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