This package consists in a software that implements the algorithm presented
in:

Davi C. Tozoni, Pedro J. de Rezende, Cid C. de Souza, 2013. A Practical
Iterative Algorithm for the Art Gallery Problem using Integer Linear
Programming. Optimization Online, October 2013. www.optimization-
online.org/DB HTML/2013/11/4106.html.


This README file presents information about the Art Gallery Problem, the
software itself, the installation procedure and also examples showing how the
software can be used.


1) The Art Gallery Problem (AGP) 

The Art Gallery Problem, which is treated by this code, corresponds to the
problem of finding the minimum number of guards that would be sufficient to
ensure that an art gallery (represented by a simple polygon) is fully guarded,
assuming that a guard’s field of view covers 360 degrees as well as an
unbounded distance.


2) The Software Package

This program can be divided into 5 main modules. As presented in the package,
each of these modules is in a separate folder:

2.1) art-gallery-pg: 
    Represents the main algorithm. See Section 4 of the paper.

2.2) grid: 
    Responsable for constructing the arrangement and identifying Light AVPs. 

2.3) polygon: 
    Responsable for some important geometric operations, like the visibility
computation. Here, the Polygon_2 and Polygon_with_holes_2 classes from CGAL
were extended to include new and custom functions.

2.4) pre-solver: 
    Corresponds to our "black-box" for solving ILP (SCP) instances. Here you
can find different modes for solving them. Some of the options are:
    - GLPK
    - GLPK + Lagrangian Heuristic
    - XPRESS
    - (...)

    In this module, we also implemented a method for removing redundant rows
and columns from the original SCP, in order to improve the performance of our
solution.

2.5) scp-solver:
    Contains several libraries, one for each different way of solving an
SCP instance. The "black-box" implemented in 'pre-solver' folder calls
methods from one or more of the libraries implemented here. 
    As an example, If the software is currently solving the AGP using GLPK,
then the pre-solver will be making calls to the SolverPLIGlpk.so library. 

Obs.: If you want to use this software with another ILP Solver package, it
will be necessary to write your own SolverPLIXXX.[C|h]. Moreover, it will also
be necessary to include a call to your new library in 'pre-solver' package
(PreSolver.C).


3) How to install

    First of all, it is necessary to have an installed version of CGAL in your
machine, preferably the same used in our experiments (version 3.9).  In
addition, you will also need to have at least one ILP solver installed in your
machine. This solver can be:
    - GLPK: version 4.52
    - XPRESS: version 7.0
    It does not mean that employing a different version of these libraries
will cause the programm to fail. However, it is safer to use the mentioned
versions, since all experiments were done using them.

Finally, to install the AGP Solver, you must run the command below in the
root directory of the package:

?> ./build-all.sh -DGLPK_PATH=<path in the system> -DXPRESS_PATH=<path in the system>

If you only have installed GLPK, type:

?> ./build-all.sh -DGLPK_PATH=<path in the system>

Similarly, if you only want to use XPRESS, you don't need to put information
about GLPK.

If you want to clean all folders, just run the shell script called
'clean-all.sh'.


4) How to run

    After compiling, enter the folder 'art-gallery-pg'. If the compilation was
successfull, you will be able to see a binary file called 'artGallerySolver'.

To execute, type the command below:

?> ./artGallerySolver <file .pol> <log file> <witness discretization (ALL_VERTICES, CONVEX_VERTICES or CHWA_POINTS)> <solver mode>
where,
    <file .pol> is the file representing the polygon. See the file format in
        Section 4.1.  
    <log file> is the file where the summary log will be outputted. See the
        file format in Section 4.2.
    <witness discretization> consists in the technique chosen to select the
        initial Witness Set of our method. See Section 4.4 in our paper. 
    <solver mode> is a positive integer that represents the mode used to 
        solve SCP instances. Current possibilities are:
            1: GLPK + Lagrangian Heuristic
            2: GLPK
            3: XPRESS + Lagrangian Heuristic
            4: XPRESS

If a final optimal solution is found, a file containing all its coordinates
will be created in the same path of the instance file, but with a .sol 
extension. The file format can be found in Section 4.3.

4.1) File Format: Instances
    Each file consists of one line divided in two parts. The first part
represents the outer boundary of the polygon (or the polygon itself, if there
are no holes).  This part includes an initial integer value that represents
the number of vertices of the boundary and a counterclockwise sequence of the
vertices. Each vertex is represented by its x and y coordinates each of which
is written as the quotient of two integers (int/int).  

    The second part represents the holes of the polygon. First we have the
number of holes. After this, each hole is represented in the exact same way
described above for the boundary: an integer representing the size of the hole
and then a list of coordinates.

   As an example, here is the representation of a square with a hole
(triangle) inside: 
 4   1/1 1/1   100/2 1/1   500/10 50/1   1/1 100/2  1   3   10/1 100/10     
80/2 10/1   100/4 40/1
         ______________
        |              |
        |      /\      |
        |     /  \     |
        |    /    \    |
        |   /      \   |
        |  /________\  |
        |______________|

4.2) File Format: Results
    Each file consists of one csv table with the following values: 
     -idFile: name of the instance
     -polSize: number of vertices of the instance
     -guards: size of the final solution
     -iterations: number of iterations necessary to find the optimal solution
     -initWitnSize: size of the initial Witness Set. See Section 4.4 in our 
        paper.
     -finalWitnSize: size of the final Witness Set.
     -initCandSize: size of the initial Guard Candidate Set. See Section 4.2
        of our paper.
     -finalCandSize: size of the final Guard Candidate Set.
     -maxHorizontal: maximum number of iterations necessary to solve an AGPFC 
        instance using Algorithm 3 (Section 4.2) in our paper.
     -IPSolved: number of SCP instances treated during execution.
     -initDisTime: Time spent creating initial discretization.
     -insertDisTime: Time spent inserting witnesses in the arrangement.
     -selectCandTime: Time spent selecting guard candidates.
     -initSolverTime: Time spent creating ILP matrix and initializing solver.
     -solverTime: Time spent solving all AGPFC instances.
     -scpResolTime: Time spent with ILP Solvers (including Lagrangian 
        Heuristic).
     -newDisTime: Time spent searching for new witnesses.
     -totalTime: Total CPU time spent by the program.

4.3) File Format: Solution
    Each file consists in 2 lines. The first one has the name of the instance
file that corresponds to the solution. The second line contains an integer
representing the size of the solution followed by a sequence of coordinates
representing the optimal guards placement.


5) Examples: 
    
?> ./artGallerySolver ../instances/agp2009a-simplerand/randsimple-100-1.pol log.txt CHWA_POINTS 1
Result: Runs software on simple instance with 100 vertices, using CHWA_POINTS
    initial discretization and GLPK Solver with Lagrangian Heuristic.

?> ./artGallerySolver ../instances/gD-ortho-ortho/gD_ortho-ortho_120:500v-50h_4.pol log-2.txt CONVEX_VERTICES 4
Result: Runs software on orthogonal polygon with holes with 500 vertices,
    using all convex vertices as initial discretization and XPRESS Solver.

Obs.: All our instances that were experimented and whose results are presented
in the article can be found at the folder called 'instances'.

