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
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: