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
 All Classes Functions
Public Member Functions | List of all members
PreSolver Class Reference

Public Member Functions

 PreSolver (const vector< vector< bool > > &matrix, vector< vector< int > > &groups, double extLB=0.0)
 
bool isOptimal ()
 
void bitsColsReduction ()
 
void bitsRowsReduction ()
 
void bitsCheckGroup (int index)
 
void solve (int mode)
 
vector< int > tryHeuristic ()
 
vector< int > getOptimalSolution ()
 

Constructor & Destructor Documentation

PreSolver::PreSolver ( const vector< vector< bool > > &  matrix,
vector< vector< int > > &  groups,
double  extLB = 0.0 
)

Constructor. Receives the ILP Matrix, the guard candidates groups (which are organized by the Light AVPs where the candidates belong) and the lower bound previously obtained by the solution. Using all this information, we setup the structures used when solving the ILP.

Member Function Documentation

void PreSolver::bitsCheckGroup ( int  index)

Checks a group of guard candidates to find redundant columns.

void PreSolver::bitsColsReduction ( )

Eliminates redundant columns.

void PreSolver::bitsRowsReduction ( )

Eliminates redundant rows.

vector< int > PreSolver::getOptimalSolution ( )

Constructs the optimal solution found using the initial indices.

bool PreSolver::isOptimal ( )
inline

Returns if the solution found is optimal.

void PreSolver::solve ( int  mode)

Solves an SCP using the mode selected by the user.

vector< int > PreSolver::tryHeuristic ( )

Uses Lagrangian Heuristic to find a good viable solution for the current SCP.


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