# CbcFathomDynamicProgramming Class Reference

FathomDynamicProgramming class. More...

`#include <CbcFathomDynamicProgramming.hpp>`

Inheritance diagram for CbcFathomDynamicProgramming:
[legend]
Collaboration diagram for CbcFathomDynamicProgramming:
[legend]

List of all members.

## 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)
virtual CbcFathom * | clone () const
| Clone.
virtual void | resetModel (CbcModel *model)
| Resets stuff if model changes.
virtual int | fathom (double *&newSolution)
| returns 0 if no fathoming attempted, 1 fully fathomed , 2 incomplete search, 3 incomplete search but treat as complete.
int | maximumSize () const
| Maximum size allowed.
void | setMaximumSize (int value)
int | checkPossible (int allowableSize=0)
| Returns type of algorithm and sets up arrays.
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.
const double * | cost () const
| Returns cost array.
const int * | back () const
| Returns back array.
int | target () const
| Gets bit pattern for target result.
void | setTarget (int value)
| Sets bit pattern for target result.
## Protected Attributes
int | size_
| Size of states (power of 2 unless just one constraint).
int | type_
| Type - 0 coefficients and rhs all 1, 1 - coefficients > 1 or rhs > 1.
double * | cost_
| Space for states.
int * | back_
| Which state produced this cheapest one.
int * | lookup_
| Some rows may be satisified so we need a lookup.
int * | indices_
| Space for sorted indices.
int | numberActive_
| Number of active rows.
int | maximumSizeAllowed_
| Maximum size allowed.
int * | startBit_
| Start bit for each active row.
int * | numberBits_
| Number bits for each active row.
int * | rhs_
| Effective rhs.
int * | coefficients_
| Space for sorted coefficients.
int | target_
| Target pattern.
int | numberNonOne_
| Number of Non 1 rhs.
int | bitPattern_
| Current bit pattern.
int | algorithm_
| Current algorithm.
## Private Member Functions
void | gutsOfDelete ()
| Does deleteions.
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.
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.
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.
int | bitPattern (int numberElements, const int *rows, const int *coefficients)
| Gets bit pattern from original column.
int | bitPattern (int numberElements, const int *rows, const double *coefficients)
| Gets bit pattern from original column.
int | decodeBitPattern (int bitPattern, int *values, int numberRows)
| Fills in original column (dense) from bit pattern - returning number nonzero.
CbcFathomDynamicProgramming & | operator= (const CbcFathomDynamicProgramming &rhs)
| Illegal Assignment operator.

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

Reimplemented from CbcFathom.

## 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:

- /home/coin/svn-release/Cbc-2.8.1/Cbc/src/CbcFathomDynamicProgramming.hpp

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines