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
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
Definition: Lagrangian.h:53