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