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
Lagrangian.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 #ifndef LAGRANGEAN_H
37 #define LAGRANGEAN_H
38
39 #include <iostream>
40 #include <string>
41 #include <cstdlib>
42 #include <vector>
43 #include <tr1/unordered_set>
44 #include <boost/dynamic_bitset.hpp>
45 #include <math.h>
46 #include <string.h>
47
48 #define MAX_DUAL_IT 100000
49 #define PARAM_STEP 0.05
50
51 using namespace std;
52
53 class Lagrangian {
54 private:
55 vector< vector<bool> > _matrix; // ILP matrix
56 vector< vector<int> > _rowsList; // adjacency list
57 vector< vector<int> > _colsList; // adjacency list
58 int _nRows;
59 int _nCols;
60 double * _u; // Lagrangian Multipliers
61 double * _c; // lagrangean costs -> sum_{c}(1 - sum_{w}(a_wc * u)), sendo a_wc 1 ou 0
62 double * _s; // subgradient
63 bool * _xl; // solution of relaxation
64 bool * _xh; // solution of heuristic procedure
65 double _mi; // size of the dual subgradient step
66
67 vector<int> _guards;
68 vector<int> _optimal; // optimal solution
69
70 bool * _activeConstraints;
71 bool * _activeVariables;
72 vector<int> _fixedInOne;
73 vector<int> _fixedInZero;
74 vector<int> _solvedCons;
75
76 double _v; // value of the last lagrangean relaxation iteration
77 double _lb;
78 int _ub;
79 double _extLB;
80
81 int _sameLB;
82 int _sameUB;
83 int _iterations;
84 int _bestUBIt;
85
86 unsigned int _sameLBMaxIt;
87 unsigned _sameUBMaxIt;
88 double _initialMulti;
89
90 int _paramGreedy;
91 double _paramStep;
92
96 void setInitialMultipliers();
97
101 void updateMultipliers();
102
106 void updateStep();
107
111 void calculateCosts();
112
117 void calculateSubgradient();
118
123 int chooseNextSet(int * grades, int paramGreedy);
124
128 bool isViableSolution(vector<int> solution);
129
133 bool isViableSolutionNew(vector<int> solution);
134
138 void cleaningViable(vector<int> &solution);
139
140 public:
145 Lagrangian(const vector< vector<bool> > &matrix, double extLB = 0.0);
146
150 ~Lagrangian();
151
155 double relaxation();
156
160 double dual();
161
166 int heuristicNew(int paramGreedy);
167
172 void problemReduction();
173
177 double getLB();
178
182 int getUB();
183
187 int getBestUBIt();
188
192 int getIterations();
193
197 vector<int> getSolution();
198
202 void setOptimal(int * solution, int size);
203 };
204
205 #endif
Lagrangian
Definition: Lagrangian.h:53