TomSym CCTV Surveillance: Difference between revisions
No edit summary |
No edit summary |
||
Line 120: | Line 120: | ||
<pre> | <pre> | ||
Problem type appears to be: mip | Problem type appears to be: mip | ||
Time for symbolic processing: 0. | Time for symbolic processing: 0.0096349 seconds | ||
Starting numeric solver | Starting numeric solver | ||
===== * * * =================================================================== * * * | ===== * * * =================================================================== * * * | ||
Line 133: | Line 133: | ||
FuncEv 23 | FuncEv 23 | ||
Elapsed time: 0. | Elapsed time: 0.004000 sec. | ||
Put cameras in nodes | 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 | 2 3 4 6 9 13 15 18 20 21 23 25 26 28 31 33 35 37 38 39 41 44 45 47 | ||
</pre> | </pre> |
Latest revision as of 09:33, 8 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.0096349 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.004000 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