# LagBaBCover Class Reference

Recursive UCP solver using Lagrangean relaxation. More...

`#include <LagBaBCover.h>`

List of all members.

## Public Member Functions

| LagBaBCover (CovMatrix *_matrix)
| ~LagBaBCover ()
list< unsigned int > | Run ()
| solve UPC using default options
list< unsigned int > | Run (CoverOpts *opts)
| solve UPC
float | getLagrangeanTime ()
| returns time spent on computing Lagrangean relaxations
unsigned int | getExpandedStates ()
| returns count of calls of recursive function

## Private Member Functions

struct CoveringMatrix * | rebuild_matrix (CovMatrix *CVM)
| creates new covering matrix from CovMatrix structure
struct CoveringMatrix * | duplicate (struct CoveringMatrix *CM)
| duplicates links to rows and cols of covering matrix
void | create_matrix (struct CoveringMatrix *Cm, int *Costs)
| creates row and column links of covering matrix
void | sort_matrix (struct CoveringMatrix *Cm)
| sorts columns of matrix according to costs and sorts rows by count of covered columns
int | branch_bound_lagrange (struct CoveringMatrix *CM, struct header_of_solution_UCP *SolUCP, long double instance)
| recursive function of branch and bound alghoritm
void | release (struct CoveringMatrix *CM)
| releases allocated memory for structure keeping matrix
void | release (struct header_of_solution_UCP *SolUCP)
| releases allocated memory for solution
struct header_of_solution_UCP * | create_New_Empty_Solution (void)
| Creates empty header structure for keeping solution.
void | append_to_solution (struct header_of_solution_UCP *Source, struct header_of_solution_UCP *Target)
| Apends columns links from one solution header to another.
void | add_to_solution (struct header_of_solution_UCP *SolutionUCP, struct CLink *Column)
| Adds given column link to solution.
void | add_to_solution_masked (struct header_of_solution_UCP *TargetSolution, struct CoveringMatrix *Matrix, unsigned char *mask, int len)
| Apends columns links marked in mask array from matrix.
list< unsigned int > | rebuild_solution (struct header_of_solution_UCP *SolutionUCP)
| creates simple array containing ID's of column links in solution
void | remove_col_from_matrix (struct CoveringMatrix *CM, struct CLink *colToRemove)
| removes given column from covering matrix
void | remove_col_from_matrix (struct CoveringMatrix *CM, int ID)
| removes given column link from covering matrix
void | remove_row_from_matrix (struct CoveringMatrix *CM, struct CLink *rowToRemove)
| removes given row link from covering matrix
void | remove_col_with_rows (struct CLink *Column, struct CoveringMatrix *CM)
| removes given column and all rows covered by this column from covering matrix
void | find_number_of_ones (struct CoveringMatrix *CM)
| finds number of covers in rows and columns also removes columns that don't cover any row
void | solve_row_dominance (struct CoveringMatrix *CM, struct header_of_solution_UCP *SolutionUCP)
| reduce the matrix by row dominance
void | solve_column_dominance (struct CoveringMatrix *CM)
| reduce the matrix by column dominance
int | solve_dominance (struct CoveringMatrix *CM, struct header_of_solution_UCP *SolutionUCP)
| Reduce matrix with dominance relations.
void | check_essentiality (struct CoveringMatrix *CM, struct header_of_solution_UCP *SolutionUCP)
| checks for essential columns in matrix
float | evaluate_column (struct CoveringMatrix *CM, struct CLink *ColumnLink)
| Evaluates column - used for selecton of column in B&B alghoritm.
struct CLink * | select_col_contrib (struct CoveringMatrix *CM)
| Selects column that should be added to solution in B&B alghoritm.
bool | check_coverage (struct CoveringMatrix *CM, list< unsigned int > solution)

## Private Attributes

long | uBound
| Cost of best feasible solution found.
long | MaxCost
| Cost of all columns.
long | NumCalls
| Count of calls of B&B method.
float | lagrangeTime
| Total time spent by solving lagrange computations.
struct CoveringMatrix * | covering_matrix
| Representation of problem (used by B&B alghoritm).
struct header_of_solution_UCP * | solution_UCP
| Representation of B&B solution.
CovMatrix * | covMatrix
| Representation of problem (used by Lagrange alghoritms).
int * | bestLgSolution
| Representation of lagrangean solution.
long | bestLgSolutionCost
| Cost of best lagrangean solution.
char | bestLgSolutionUsed
| Indicates whether best solution is obtained by lagrange algh. or B&B.
long double | bestLgState
| state with best solution found by Lagrangean heuristic
CoverOpts * | options
| options of solving (domination, relaxation parameters...)

## Detailed Description

Recursive UCP solver using Lagrangean relaxation.

## Constructor & Destructor Documentation

LagBaBCover::LagBaBCover | ( | CovMatrix * | _matrix | ) |

LagBaBCover::~LagBaBCover | ( |  | ) |

## Member Function Documentation

void LagBaBCover::add_to_solution | ( | struct header_of_solution_UCP * | SolutionUCP,
|  | struct CLink * | Column |
| ) |  |  | `[private]`

Adds given column link to solution.

Parameters:

  | SolutionUCP | target solution header
  | Column | column link that will be added

void LagBaBCover::add_to_solution_masked | ( | struct header_of_solution_UCP * | TargetSolution,
|  | struct CoveringMatrix * | Matrix,
|  | unsigned char * | mask,
|  | int | len |
| ) |  |  | `[private]`

Apends columns links marked in mask array from matrix.

Parameters:

  | TargetSolution | target solution header
  | Matrix | matrix structure containing column links
  | mask | binary vector indicating selected columns
  | len | length of mask vector

void LagBaBCover::append_to_solution | ( | struct header_of_solution_UCP * | Source,
|  | struct header_of_solution_UCP * | Target |
| ) |  |  | `[private]`

Apends columns links from one solution header to another.

Parameters:

  | Source | solution header with column links that should be added
  | Target | target solution header

int LagBaBCover::branch_bound_lagrange | ( | struct CoveringMatrix * | CM,
|  | struct header_of_solution_UCP * | SolUCP,
|  | long double | instance |
| ) |  |  | `[private]`

recursive function of branch and bound alghoritm

Parameters:

  | CM | current representation of problem
  | SolUCP | header of current solution
  | instance | unique identification of run

Returns:
  1 or 0

bool LagBaBCover::check_coverage | ( | struct CoveringMatrix * | CM,
|  | list< unsigned int > | solution |
| ) |  |  | `[private]`

void LagBaBCover::check_essentiality | ( | struct CoveringMatrix * | CM,
|  | struct header_of_solution_UCP * | SolutionUCP |
| ) |  |  | `[private]`

checks for essential columns in matrix

Parameters:

  | CM | matrix structure
  | SolutionUCP | if matrix contains any essential columns, store their links here

void LagBaBCover::create_matrix | ( | struct CoveringMatrix * | Cm,
|  | int * | Costs |
| ) |  |  | `[private]`

creates row and column links of covering matrix

Parameters:

  | Cm | structure where links will be created
  | Costs | array with costs of columns

struct header_of_solution_UCP * LagBaBCover::create_New_Empty_Solution | ( | void |  | ) | `[read, private]`

Creates empty header structure for keeping solution.

struct CoveringMatrix * LagBaBCover::duplicate | ( | struct CoveringMatrix * | CM | ) | `[read, private]`

duplicates links to rows and cols of covering matrix

Parameters:

  | CM | matrix to be duplicated

Returns:
  clone of the matrix

float LagBaBCover::evaluate_column | ( | struct CoveringMatrix * | CM,
|  | struct CLink * | ColumnLink |
| ) |  |  | `[private]`

Evaluates column - used for selecton of column in B&B alghoritm.

Parameters:

  | CM | matrix structure
  | ColumnLink | evaluated column

Returns:
  colun evaluation

void LagBaBCover::find_number_of_ones | ( | struct CoveringMatrix * | CM | ) | `[private]`

finds number of covers in rows and columns also removes columns that don't cover any row

Parameters:

  | CM | matrix structure

unsigned int LagBaBCover::getExpandedStates | ( |  | ) | `[inline]`

returns count of calls of recursive function

float LagBaBCover::getLagrangeanTime | ( |  | ) | `[inline]`

returns time spent on computing Lagrangean relaxations

struct CoveringMatrix * LagBaBCover::rebuild_matrix | ( | CovMatrix * | CVM | ) | `[read, private]`

creates new covering matrix from CovMatrix structure

Parameters:

  | CVM | data matrix

list< unsigned int > LagBaBCover::rebuild_solution | ( | struct header_of_solution_UCP * | SolutionUCP | ) | `[private]`

creates simple array containing ID's of column links in solution

Parameters:

  | SolutionUCP | source solution header

Returns:
  array containing solution columns ID's

void LagBaBCover::release | ( | struct header_of_solution_UCP * | SolUCP | ) | `[private]`

releases allocated memory for solution

Parameters:

  | SolUCP | solution to release

void LagBaBCover::release | ( | struct CoveringMatrix * | CM | ) | `[private]`

releases allocated memory for structure keeping matrix

Parameters:

  | CM | matrix to release

void LagBaBCover::remove_col_from_matrix | ( | struct CoveringMatrix * | CM,
|  | int | ID |
| ) |  |  | `[private]`

removes given column link from covering matrix

Parameters:

  | CM | matrix structure
  | ID | id of column to be removed

void LagBaBCover::remove_col_from_matrix | ( | struct CoveringMatrix * | CM,
|  | struct CLink * | colToRemove |
| ) |  |  | `[private]`

removes given column from covering matrix

Parameters:

  | CM | matrix
  | colToRemove | column link to remove

void LagBaBCover::remove_col_with_rows | ( | struct CLink * | Column,
|  | struct CoveringMatrix * | CM |
| ) |  |  | `[private]`

removes given column and all rows covered by this column from covering matrix

Parameters:

  | Column | column link to be removed
  | CM | matrix structure

void LagBaBCover::remove_row_from_matrix | ( | struct CoveringMatrix * | CM,
|  | struct CLink * | rowToRemove |
| ) |  |  | `[private]`

removes given row link from covering matrix

Parameters:

  | CM | matrix structure
  | rowToRemove | id of row to be removed

list< unsigned int > LagBaBCover::Run | ( | CoverOpts * | opts | ) |

solve UPC

Parameters:

  | opts | options for Lagrangean relaxation

Returns:
  list of column ID's

list< unsigned int > LagBaBCover::Run | ( |  | ) |

solve UPC using default options

Returns:
  list of column ID's

struct CLink * LagBaBCover::select_col_contrib | ( | struct CoveringMatrix * | CM | ) | `[read, private]`

Selects column that should be added to solution in B&B alghoritm.

Parameters:

  | CM | matrix structure

Returns:
  found column

void LagBaBCover::solve_column_dominance | ( | struct CoveringMatrix * | CM | ) | `[private]`

reduce the matrix by column dominance

Parameters:

  | CM | matrix structure

int LagBaBCover::solve_dominance | ( | struct CoveringMatrix * | CM,
|  | struct header_of_solution_UCP * | SolutionUCP |
| ) |  |  | `[private]`

Reduce matrix with dominance relations.

Parameters:

  | CM | matrix structure
  | SolutionUCP | if matrix contains any essential columns, store their links here

Returns:
  1 or 0 (depending on foun dominance)

void LagBaBCover::solve_row_dominance | ( | struct CoveringMatrix * | CM,
|  | struct header_of_solution_UCP * | SolutionUCP |
| ) |  |  | `[private]`

reduce the matrix by row dominance

Parameters:

  | CM | matrix structure
  | SolutionUCP | if matrix contains any essential columns, store their links here

void LagBaBCover::sort_matrix | ( | struct CoveringMatrix * | Cm | ) | `[private]`

sorts columns of matrix according to costs and sorts rows by count of covered columns

Parameters:

  | Cm | sorted matrix

## Member Data Documentation

int* LagBaBCover::bestLgSolution`[private]`

Representation of lagrangean solution.

long LagBaBCover::bestLgSolutionCost`[private]`

Cost of best lagrangean solution.

char LagBaBCover::bestLgSolutionUsed`[private]`

Indicates whether best solution is obtained by lagrange algh. or B&B.

long double LagBaBCover::bestLgState`[private]`

state with best solution found by Lagrangean heuristic

struct CoveringMatrix* LagBaBCover::covering_matrix`[private]`

Representation of problem (used by B&B alghoritm).

CovMatrix* LagBaBCover::covMatrix`[private]`

Representation of problem (used by Lagrange alghoritms).

float LagBaBCover::lagrangeTime`[private]`

Total time spent by solving lagrange computations.

long LagBaBCover::MaxCost`[private]`

Cost of all columns.

long LagBaBCover::NumCalls`[private]`

Count of calls of B&B method.

CoverOpts* LagBaBCover::options`[private]`

options of solving (domination, relaxation parameters...)

struct header_of_solution_UCP* LagBaBCover::solution_UCP`[private]`

Representation of B&B solution.

long LagBaBCover::uBound`[private]`

Cost of best feasible solution found.

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

- LagBaBCover.h
- LagBaBCover.cpp