AGSol (Art Gallery Solver) 1.0.2 This package contains a software capable of optimally solving the Art Gallery Problem (AGP), one interesting NP-hard problem from the Computational Geometry field. The algorithm implemented in this solution, which can be today considered the state-of-the-art technique on the AGP, can be found in details in the following paper: Davi C. Tozoni, Pedro J. de Rezende, Cid C. de Souza. A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

- Main Page
- Classes
- Files

- Class List
- Class Index
- Class Hierarchy
- Class Members

All Classes Functions
Public Member Functions | List of all members
Lagrangian Class Reference

## Public Member Functions
| Lagrangian (const vector< vector< bool > > &matrix, double extLB=0.0)
| ~Lagrangian ()
double | relaxation ()
double | dual ()
int | heuristicNew (int paramGreedy)
void | problemReduction ()
double | getLB ()
int | getUB ()
int | getBestUBIt ()
int | getIterations ()
vector< int > | getSolution ()
void | setOptimal (int *solution, int size)

## Constructor & Destructor Documentation

Lagrangian::Lagrangian | ( | const vector< vector< bool > > & | matrix,
|  | double | extLB = `0.0`
| ) |  |

Constructor. Receives the ILP matrix and an external lower bound computed previously.

Lagrangian::~Lagrangian | ( |  | ) |

Destructor. Frees structures memory.

## Member Function Documentation

double Lagrangian::dual | ( |  | ) |

Iterativelly computes new lower and upper bounds for the ILP.

int Lagrangian::getBestUBIt | ( |  | ) |

Gets iteration where the best UB was found.

int Lagrangian::getIterations | ( |  | ) |

Gets number of iterations.

double Lagrangian::getLB | ( |  | ) |

Gets current LB value.

vector< int > Lagrangian::getSolution | ( |  | ) |

Gets optimal solution.

int Lagrangian::getUB | ( |  | ) |

Gets current UB value.

int Lagrangian::heuristicNew | ( | int | paramGreedy | ) |

Heuristic that finds a viable solution to the SCP from an existing lagrangian relaxation result.

void Lagrangian::problemReduction | ( |  | ) |

If possible, removes variables and/or constraints from the original SCP.

double Lagrangian::relaxation | ( |  | ) |

Computes lagrangian relaxation.

void Lagrangian::setOptimal | ( | int * | solution,
|  | int | size
| ) |  |

Sets optimal solution.

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

- scp-solver/Lagrangian.h
- scp-solver/Lagrangian.C