TomSym CCTV Surveillance: Difference between revisions
(Created page with "{{Part Of Manual|title=the TomSym Manual|link=TomSym Manual}} ==Problem description== In the course of the last few months, the industrial zone of Billston has suffe...") |
No edit summary |
||
Line 7: | Line 7: | ||
The industrial zone in Billston | The industrial zone in Billston | ||
<pre> | |||
13 -- 14 -- 18 -- 17 28 -- 29 35 -- 36 | 13 -- 14 -- 18 -- 17 28 -- 29 35 -- 36 | ||
</pre> | |||
<pre> | |||
| | | | | | | | | | | | ||
| | | | | | | | | | | | ||
Line 16: | Line 19: | ||
| / | | | | | | | / | | | | | | ||
| / | | | | | | | / | | | | | | ||
</pre> | |||
<pre> | |||
12 16 -- 20 24 -- 25 -- 30 33 47 -- 45 -- 46 | 12 16 -- 20 24 -- 25 -- 30 33 47 -- 45 -- 46 | ||
</pre> | |||
<pre> | |||
| / | / | / | | | | / | / | / | | | ||
| / | / | / | | | | / | / | / | | | ||
</pre> | |||
<pre> | |||
3 -- 11 -- 21 -- 22 31 37 -- 43 -- 44 -- 49 | 3 -- 11 -- 21 -- 22 31 37 -- 43 -- 44 -- 49 | ||
</pre> | |||
<pre> | |||
| \ \ | | | | \ \ | | | ||
| \ \ | | | | \ \ | | | ||
Line 42: | Line 53: | ||
| | / | | | / | ||
| | / | | | / | ||
</pre> | |||
<pre> | |||
1 --------------------------- 2 | 1 --------------------------- 2 | ||
</pre> | |||
==Variables== | ==Variables== | ||
<pre> | |||
arcs_out/in These variables describe the network | arcs_out/in These variables describe the network | ||
of streets | of streets | ||
</pre> | |||
==Reference== | ==Reference== |
Revision as of 17:24, 2 November 2011
This page is part of the TomSym Manual. See TomSym Manual. |
Problem description
In the course of the last few months, the industrial zone of Billston has suffered from a series of break-ins and thefts during the night. The zone is watched by security men but there are too few of them. The town council in charge of security in this zone decides to install surveillance cameras to aid the security men with their task. These cameras can be directed and pivot through 360 degrees. By installing a camera at the intersection of several streets, it is possible to survey all adjoining streets. The map in the figure below shows the industrial zone with the limits of the zone to be covered by closed circuit TV (CCTV) surveillance and the 49 possible locations where to install the cameras. What is the minimum number of cameras that have to be installed to survey all the streets of this zone and where should they be placed?
The industrial zone in Billston
13 -- 14 -- 18 -- 17 28 -- 29 35 -- 36
| | | | | | | | | | | | 15 -- 19 26 -- 27 34 48 | | / | | | | | | / | | | | |
12 16 -- 20 24 -- 25 -- 30 33 47 -- 45 -- 46
| / | / | / | | | / | / | / | |
3 -- 11 -- 21 -- 22 31 37 -- 43 -- 44 -- 49
| \ \ | | | \ \ | | | | 4 -- 9 -- 10 23 -- 32 -- 38 | | | \ | | | | \ | | | | 6 5 39 -- 40 -- 41 -- 42 | | | \ | / | | \ | / | | / | 8 7 | / | | / | | / | | / | | /
1 --------------------------- 2
Variables
arcs_out/in These variables describe the network of streets
Reference
Applications of optimization... Gueret, Prins, Seveaux
% Marcus Edvall, Tomlab Optimization Inc, E-mail: tomlab@tomopt.com
% Copyright (c) 2005-2009 by Tomlab Optimization Inc., $Release: 7.2.0$
% Written Oct 7, 2005. Last modified Mar 24, 2009.
Problem setup
arcs_in = [1 1 2 2 3 3 3 3 4 4 4 6 6 9 11 12 12 13 14 14 15 15 16 ...
17 18 19 20 21 22 22 23 24 25 25 26 26 28 30 31 31 32 32 ...
33 33 34 35 37 37 38 39 40 41 43 44 44 45 45 47]';
arcs_out = [2 3 39 41 4 11 12 16 5 6 9 7 8 10 21 13 15 14 15 18 16 ...
19 20 18 19 20 21 22 23 25 32 25 26 30 27 28 29 31 32 33 ...
38 39 34 37 35 36 38 43 40 40 41 42 44 49 45 46 47 48]';
n = length(arcs_in); %arcs
arcs = tom('arcs',n,1,'int');
% All variables are binary
bnds = {0 <= arcs <= 1};
% All streets need to be covered
con = {arcs(arcs_in) + arcs(arcs_out) >= 1};
% Objective
objective = sum(arcs);
constraints = {bnds, con};
options = struct;
options.solver = 'cplex';
options.name = 'CCTV Surveillance';
sol = ezsolve(objective,constraints,[],options);
PriLev = 1;
if PriLev > 0
disp('Put cameras in nodes ')
disp(num2str(find(sol.arcs)'))
end
% MODIFICATION LOG
%
% 051205 med Created
% 060118 per Added documentation
% 060125 per Moved disp to end
% 090325 med Converted to tomSym
Problem type appears to be: mip Time for symbolic processing: 0.0099015 seconds Starting numeric solver ===== * * * =================================================================== * * * TOMLAB - TOMLAB Development license 999007. Valid to 2011-12-31 ===================================================================================== Problem: --- 1: CCTV Surveillance f_k 24.000000000000000000 f(x_0) 0.000000000000000000 Solver: CPLEX. EXIT=0. INFORM=101. CPLEX Branch-and-Cut MIP solver Optimal integer solution found FuncEv 23 Elapsed time: 0.002000 sec. Put cameras in nodes 2 3 4 6 9 13 15 18 20 21 23 25 26 28 31 33 35 37 38 39 41 44 45 47