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

- Main Page
- Classes
- Files

- File List

All Classes Functions
PreSolver.h
1 /*****************************************************************************
2 * This code is part of Art Gallery Solver (AGSol) Package, which aims the
3 * resolution of the Art Gallery Problem With Point Guards.
4 *
5 * This software version (1.0.2) has been tested under and is compatible with
6 * CGAL 3.9 and GLPK 4.52.
7 *
8 * Authors:
9 * Davi Colli Tozoni - davi.tozoni@gmail.com
10 * Marcelo Castilho Couto - coutomarcelo@gmail.com
11 *
12 * AGSol Concept and Design:
13 * Davi Colli Tozoni, Marcelo Castilho Couto, Pedro Jussieu de Rezende & Cid
14 * Carvalho de Souza.
15 *
16 * Other information can be found at:
17 * http://www.ic.unicamp.br/~cid/Problem-instances/Art-Gallery/index.html
18 *
19 * --
20 *
21 * This program is free software: you can redistribute it and/or modify it
22 * under the terms of the GNU General Public License as published by the Free
23 * Software Foundation, either version 3 of the License, or (at your option)
24 * any later version.
25 *
26 * This program is distributed in the hope that it will be useful, but
27 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
28 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
29 * for more details.
30 *
31 * You should have received a copy of the GNU General Public License along
32 * with this program. If not, see <http://www.gnu.org/licenses/>.
33 *
34 ****************************************************************************/
35
36
37 #ifndef PRESOLVER_H
38 #define PRESOLVER_H
39
40 #include <iostream>
41 #include <fstream>
42 #include <string>
43 #include <cstdlib>
44 #include <vector>
45 #include <bitset>
46 #include <boost/dynamic_bitset.hpp>
47 #include <tr1/unordered_set>
48
49 #ifdef XPRESS
50 #include "SolverPLIXpress.h"
51 #endif
52
53 #ifdef GLPK
54 #include "SolverPLIGlpk.h"
55 #endif
56
57 #include "Lagrangian.h"
58
59 /* Rotinas para medicao de tempo. Elas foram implementadas pelo Ionut Aaron (Brown,GSIA) */
60 #ifndef __SYSTEM_TIME_H
61 #define __SYSTEM_TIME_H
62
63 /* Ionut Aron, ia@cs.brown.edu (1999-2001)
64 * created: August, 1999
65 * last updated: December 20, 2001
66 */
67
68 #include <sys/resource.h>
69 #include <sys/types.h>
70 #include <time.h>
71
72 extern int getrusage();
73
74 // this macro produces a time equal to the one produced by clock(),
75 // but does not suffer from the wraparound problem of clock()
76
77 #define CPUTIME(ruse) (\
78 getrusage(RUSAGE_SELF,&ruse),\
79 ruse.ru_utime.tv_sec + ruse.ru_stime.tv_sec + \
80 1e-6 * (ruse.ru_utime.tv_usec + ruse.ru_stime.tv_usec)\
81 )
82
83 /* usage of the CPUTIME timing routine:
84 ===================================
85
86 struct rusage ruse;
87 double t0 = CPUTIME(ruse);
88 ...
89 double t1 = CPUTIME(ruse);
90 printf("CPU time: %f secs.\n", t1-t0);
91 */
92
93 #endif
94
95 #define SMALL_NUMBER_GAP 0.00000001
96
97 using namespace std;
98
99 class PreSolver {
100 private:
101 vector< vector<bool> > _matrix;
102 vector< boost::dynamic_bitset<> > _iBitsMatrix;
103 vector< vector<int> > _groups;
104 vector<bool> _cAlive;
105 vector<bool> _rAlive;
106
107 // maps variables from the presolved matrix to the original one
108 vector<int> _redMap;
109
110 struct rusage _ruse;
111 ofstream _log;
112
113 int _nCand;
114 int _nWitn;
115 int _nAliveCols;
116 int _nAliveRows;
117
118 double _extLB;
119
120 // Other variables:
121 vector<int> _heurSolution; // indices from reduced matrix
122 vector<int> _optSolution; // indices from reduced matrix
123
124 bool _foundOptimal;
125
126 public:
133 PreSolver(const vector< vector<bool> > &matrix, vector< vector<int> > &groups, double extLB = 0.0);
134
138 bool isOptimal() { return _foundOptimal; };
139
143 void bitsColsReduction();
144
148 void bitsRowsReduction();
149
153 void bitsCheckGroup(int index);
154
155 #ifdef XPRESS
156
160 void solveWithXpress(bool preXpress, double solValue, vector<int> sol);
161 #endif
162
163 #ifdef GLPK
164
168 void solveWithGlpk(double solValue, vector<int> sol);
169 #endif
170
174 void solve(int mode);
175
180 vector<int> tryHeuristic();
181
185 vector<int> getOptimalSolution();
186 };
187
188 #endif
PreSolver::isOptimal
bool isOptimal()
Definition: PreSolver.h:138
PreSolver
Definition: PreSolver.h:99