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