# LagrangeSolver Class Reference

Lagrangean relaxation. More...

`#include <LagBaBCover.h>`

List of all members.

## Public Member Functions

| LagrangeSolver (SCPView *pv)
| ~LagrangeSolver ()
int | get_lgsolution_cost ()
| Returns the cost of best heuristic solution found.
unsigned char * | get_best_solution ()
| Returns the vector with best heuristic solution found.
int | get_lower_bound ()
| Returns the value of lower bound found by solving LP.
int | get_recommended_column ()
| Returns ID with lowest reduced cost.
void | solve (int iterations, int randomizeCosts, int heuristic, int heurIterations, float stepCoef, float stepCoefMin, int stepCoefIter, int maxLowerBound)
| Solve the SCP using lagrangian heuristic.
void | solve_dual (int iterations, int heuristic, int heurIterations, float stepCoef, float stepCoefMin, int stepCoefIter, int maxLowerBound, float stepCoefDual, float stepCoefMinDual, int stepCoefIterDual)
| Solve the SCP using dual lagrangian heuristic.

## Private Member Functions

void | initialize (int randomizeMultipliers, float stepCoef, float stepCoefMin, int stepCoefIter)
| Initialize variables and arrays.
int | find_heur_ub ()
| Finds simple feasible solution with simple greedy heuristic.
void | randomize_multipliers (int minCost, int maxCost)
| Randomizes initial lagrangean multipliers.
void | solve_lp ()
| Solve lagrangean problem (LP).
void | solve_dlp ()
| Solve first iteration of dual lagrangean problem.
void | solve_dlp_next ()
| Solve next iterations of dual lagrangean problem.
void | ha (int removeType)
| Heuristic - creates feasible solution Uses reduced cost.
void | ha_modified (int removeType)
| Heuristic - creates feasible solution Uses modified reduced cost.
int | compute_subgradient ()
| Calculates subgradient and updates Lagrangean multiplicatiors.
float | get_primal_reduced_cost (int columnIndex)
| Calculates reduced cost of column.
float | get_dual_reduced_cost (int rowIndex)
| Calculates dual reduced cost of row.
void | update_best_solution (float candZUB)
| Updates best solution with it's cost.

## Private Attributes

SCPView * | problemView
| View to the underlying problem.
float | ZUB
| Best feasible solution.
float | ZLP
| Current cost of lagrangean relaxation.
float | ZLB
| Current best cost of lagrangean relaxation.
int | lbound
| Current integer best cost of lagrangean relaxation.
float | heur_value
| Current heuristic solution cost.
int | best_heur_value
| Current best heuristic solution cost.
float * | t
| Vector of lagrangian multipliers.
float * | n
| Vector of dual lagrangian multipliers.
unsigned char * | primal_delta
| Vector indicating changes of lagrangean multipliers.
unsigned char * | dual_delta
| Vector indicating changes of dual lagrangean multipliers.
unsigned char * | x
| Vector of the LP solution.
float * | y
| Vector of the dual solution.
unsigned char * | x_heur
| Vector of the current feasible heuristic solution.
unsigned char * | x_best
| Vector of the best feasible heuristic solution known.
int | selected_columns
| count of columns selected by solving LP
int * | help_indexes
| array containing indexes of columns selected by solving LP
float * | help_costs
| array containing costs of columns selected by solving LP
int * | help_number_of_ones
| array containing count of rows covered by columns selected by solving LP
int | covered_rows
| number of rows covered by solving LP
bool * | row_is_covered
| Vector of rows covered by solving LP.
unsigned char * | column_is_recounted
| Vector indicating whether given column's reduced cost was recounted when solving dual problem.
unsigned char * | row_is_recounted
| Vector indicating whether given row's dual reduced cost was recounted when solving dual problem.
float * | costs
| Vector of costs of columns.
float * | reduced_costs
| Vector of reduced costs of columns.
float * | modified_reduced_costs
| Temporary vector of modified or normal reduced costs.
float * | min_costs
| Vector of lowest costs of columns covering given row.
float * | dual_reduced_costs
| Vector of dual reduced costs of rows.
int * | primal_slack
| Vector of slacks.
float * | dual_slack
| Vector of dual slacks.
int | iterations
| Iteration counter.
int | sup_iterations
| Supplementary iteration counter.
int | sup_dual_iterations
| Supplementary dual iteration counter.
float | step_coefficient
| Step coefficient.
float | dual_step_coefficient
| Dual step coefficient.
float | step_coefficient_min
| Minimal step coefficient.
int | step_coefficient_iter
| Number of iterations before step coefficient is halved.
float | sup_ZLB
| Supplementary ZLB.
float | sup_ZUB
| Supplementary ZUB.
int ** | rows_covered_by_column
| Array with indexes of rows covered by columns.
int * | rows_covered_by_column_count
| Number of rows covered by given column.
int ** | columns_covered_by_row
| Array with indexes of columns covered by rows.
int * | columns_covered_by_row_count
| Number of columns covered by given row.
int | primal_subgradient
| Subgradient.
float | dual_subgradient
| Dual subgradient.
float | primal_step
| Step.
float | dual_step
| Dual step.
int | primal_step_change_stop
| Indicates whether primal step coefficient is lower then minimal step coefficient.
int | dual_step_change_stop
| Indicates whether dual step coefficient is lower then minimal step coefficient.
int | recommended_column
| Column with lowest reduced cost.

## Detailed Description

Lagrangean relaxation.

## Constructor & Destructor Documentation

LagrangeSolver::LagrangeSolver | ( | SCPView * | pv | ) |

LagrangeSolver::~LagrangeSolver | ( |  | ) |

## Member Function Documentation

int LagrangeSolver::compute_subgradient | ( |  | ) | `[private]`

Calculates subgradient and updates Lagrangean multiplicatiors.

Returns:
  0 if subgradient is 0 or step coefficient is too small else return 1

int LagrangeSolver::find_heur_ub | ( |  | ) | `[private]`

Finds simple feasible solution with simple greedy heuristic.

unsigned char* LagrangeSolver::get_best_solution | ( |  | ) | `[inline]`

Returns the vector with best heuristic solution found.

float LagrangeSolver::get_dual_reduced_cost | ( | int | rowIndex | ) | `[private]`

Calculates dual reduced cost of row.

Parameters:

  | rowIndex | Index of row

int LagrangeSolver::get_lgsolution_cost | ( |  | ) | `[inline]`

Returns the cost of best heuristic solution found.

int LagrangeSolver::get_lower_bound | ( |  | ) | `[inline]`

Returns the value of lower bound found by solving LP.

float LagrangeSolver::get_primal_reduced_cost | ( | int | columnIndex | ) | `[private]`

Calculates reduced cost of column.

Parameters:

  | columnIndex | Index of column

int LagrangeSolver::get_recommended_column | ( |  | ) | `[inline]`

Returns ID with lowest reduced cost.

void LagrangeSolver::ha | ( | int | removeType | ) | `[private]`

Heuristic - creates feasible solution Uses reduced cost.

void LagrangeSolver::ha_modified | ( | int | removeType | ) | `[private]`

Heuristic - creates feasible solution Uses modified reduced cost.

void LagrangeSolver::initialize | ( | int | randomizeMultipliers,
|  | float | stepCoef,
|  | float | stepCoefMin,
|  | int | stepCoefIter |
| ) |  |  | `[private]`

Initialize variables and arrays.

void LagrangeSolver::randomize_multipliers | ( | int | minCost,
|  | int | maxCost |
| ) |  |  | `[private]`

Randomizes initial lagrangean multipliers.

void LagrangeSolver::solve | ( | int | iterations,
|  | int | randomizeCosts,
|  | int | heuristic,
|  | int | heurIterations,
|  | float | stepCoef,
|  | float | stepCoefMin,
|  | int | stepCoefIter,
|  | int | maxLowerBound |
| ) |  |  |

Solve the SCP using lagrangian heuristic.

Parameters:

  | iterations | max number of iterations
  | heuristic | which heuristic will be used
  | heurIterations | number of iterations between running heuristic
  | stepCoef | initial step coefficient
  | stepCoefMin | minimal step coefficient
  | stepCoefIter | number of iteration without change of LB before step coefficient is halved
  | maxLowerBound | Desired maximum lower bound. If that bound is reached, algorithm is stopped

void LagrangeSolver::solve_dlp | ( |  | ) | `[private]`

Solve first iteration of dual lagrangean problem.

If dual reduced cost is positive, set value in y vector

void LagrangeSolver::solve_dlp_next | ( |  | ) | `[private]`

Solve next iterations of dual lagrangean problem.

void LagrangeSolver::solve_dual | ( | int | iterations,
|  | int | heuristic,
|  | int | heurIterations,
|  | float | stepCoef,
|  | float | stepCoefMin,
|  | int | stepCoefIter,
|  | int | maxLowerBound,
|  | float | stepCoefDual,
|  | float | stepCoefMinDual,
|  | int | stepCoefIterDual |
| ) |  |  |

Solve the SCP using dual lagrangian heuristic.

Parameters:

  | iterations | max number of iterations
  | heuristic | which heuristic will be used
  | heurIterations | number of iterations between running heuristic
  | stepCoef | initial step coefficient
  | stepCoefMin | minimal step coefficient
  | stepCoefIter | number of iteration without change of LB before step coefficient is halved
  | maxLowerBound | Desired maximum lower bound. If that bound is reached, algorithm is stopped
  | stepCoef | initial dual step coefficient
  | stepCoefMin | minimal dual step coefficient
  | stepCoefIter | number of iteration without change of UB before dual step coefficient is halved

void LagrangeSolver::solve_lp | ( |  | ) | `[private]`

Solve lagrangean problem (LP).

void LagrangeSolver::update_best_solution | ( | float | candZUB | ) | `[private]`

Updates best solution with it's cost.

## Member Data Documentation

int LagrangeSolver::best_heur_value`[private]`

Current best heuristic solution cost.

unsigned char* LagrangeSolver::column_is_recounted`[private]`

Vector indicating whether given column's reduced cost was recounted when solving dual problem.

int** LagrangeSolver::columns_covered_by_row`[private]`

Array with indexes of columns covered by rows.

int* LagrangeSolver::columns_covered_by_row_count`[private]`

Number of columns covered by given row.

float* LagrangeSolver::costs`[private]`

Vector of costs of columns.

int LagrangeSolver::covered_rows`[private]`

number of rows covered by solving LP

unsigned char* LagrangeSolver::dual_delta`[private]`

Vector indicating changes of dual lagrangean multipliers.

float* LagrangeSolver::dual_reduced_costs`[private]`

Vector of dual reduced costs of rows.

float* LagrangeSolver::dual_slack`[private]`

Vector of dual slacks.

float LagrangeSolver::dual_step`[private]`

Dual step.

int LagrangeSolver::dual_step_change_stop`[private]`

Indicates whether dual step coefficient is lower then minimal step coefficient.

float LagrangeSolver::dual_step_coefficient`[private]`

Dual step coefficient.

float LagrangeSolver::dual_subgradient`[private]`

Dual subgradient.

float* LagrangeSolver::help_costs`[private]`

array containing costs of columns selected by solving LP

int* LagrangeSolver::help_indexes`[private]`

array containing indexes of columns selected by solving LP

int* LagrangeSolver::help_number_of_ones`[private]`

array containing count of rows covered by columns selected by solving LP

float LagrangeSolver::heur_value`[private]`

Current heuristic solution cost.

int LagrangeSolver::iterations`[private]`

Iteration counter.

int LagrangeSolver::lbound`[private]`

Current integer best cost of lagrangean relaxation.

float* LagrangeSolver::min_costs`[private]`

Vector of lowest costs of columns covering given row.

float* LagrangeSolver::modified_reduced_costs`[private]`

Temporary vector of modified or normal reduced costs.

float* LagrangeSolver::n`[private]`

Vector of dual lagrangian multipliers.

unsigned char* LagrangeSolver::primal_delta`[private]`

Vector indicating changes of lagrangean multipliers.

int* LagrangeSolver::primal_slack`[private]`

Vector of slacks.

float LagrangeSolver::primal_step`[private]`

Step.

int LagrangeSolver::primal_step_change_stop`[private]`

Indicates whether primal step coefficient is lower then minimal step coefficient.

int LagrangeSolver::primal_subgradient`[private]`

Subgradient.

SCPView* LagrangeSolver::problemView`[private]`

View to the underlying problem.

int LagrangeSolver::recommended_column`[private]`

Column with lowest reduced cost.

float* LagrangeSolver::reduced_costs`[private]`

Vector of reduced costs of columns.

bool* LagrangeSolver::row_is_covered`[private]`

Vector of rows covered by solving LP.

unsigned char* LagrangeSolver::row_is_recounted`[private]`

Vector indicating whether given row's dual reduced cost was recounted when solving dual problem.

int** LagrangeSolver::rows_covered_by_column`[private]`

Array with indexes of rows covered by columns.

int* LagrangeSolver::rows_covered_by_column_count`[private]`

Number of rows covered by given column.

int LagrangeSolver::selected_columns`[private]`

count of columns selected by solving LP

float LagrangeSolver::step_coefficient`[private]`

Step coefficient.

int LagrangeSolver::step_coefficient_iter`[private]`

Number of iterations before step coefficient is halved.

float LagrangeSolver::step_coefficient_min`[private]`

Minimal step coefficient.

int LagrangeSolver::sup_dual_iterations`[private]`

Supplementary dual iteration counter.

int LagrangeSolver::sup_iterations`[private]`

Supplementary iteration counter.

float LagrangeSolver::sup_ZLB`[private]`

Supplementary ZLB.

float LagrangeSolver::sup_ZUB`[private]`

Supplementary ZUB.

float* LagrangeSolver::t`[private]`

Vector of lagrangian multipliers.

unsigned char* LagrangeSolver::x`[private]`

Vector of the LP solution.

unsigned char* LagrangeSolver::x_best`[private]`

Vector of the best feasible heuristic solution known.

unsigned char* LagrangeSolver::x_heur`[private]`

Vector of the current feasible heuristic solution.

float* LagrangeSolver::y`[private]`

Vector of the dual solution.

float LagrangeSolver::ZLB`[private]`

Current best cost of lagrangean relaxation.

float LagrangeSolver::ZLP`[private]`

Current cost of lagrangean relaxation.

float LagrangeSolver::ZUB`[private]`

Best feasible solution.

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

- LagBaBCover.h
- LagBaBCover.cpp