Exploring various set covering problem techniques to tackle the optimal camera placement problem

Optimal Camera Placement (OCP) problem is a combinatorial optimization problem, where the aim is to find an optimal placement of cameras, given that a target area is completely covered. A single-objective OCP is commonly formulated in two possible ways. The first one is to maximize the area coverage, such that minimal camera cost is maintained. The second one is to minimize camera cost, such that complete area coverage is achieved. The idea of the second formulation of OCP can be similar to a popular NP-hard combinatorial optimization problem, namely, the Set Covering Problem (SCP). Thus, OCP can be formulated as SCP. However, a special variant of SCP is used in this paper. This variant is called the unicost SCP (USCP), where the cost is assumed to be unified and, therefore, not a factor. The reason behind using USCP is that our problem instances do not consider cost as a factor, which makes USCP well-suited for this study. Thus, the objective of our OCP problem is to minimize the number of cameras rather than the cost. Despite the connection between OCP and SCP, not many studies have used techniques from the former's literature and applied them to address the latter. This study exploits this connection by implementing various SCP techniques to address 69 OCP instances retrieved from the GECCO 2021 competition on "the optimal camera placement problem and the unicost set covering problem'". First, our OCP problems are solved using classic exact methods. The initial results seem to be promising, but can be improved. Next, SCP problem reduction techniques are introduced and implemented to address the complexity of our problem. A comparison between the results before and after reduction is given. After that, the OCP is formulated as a bi-objective problem, where the two objectives are to, simultaneously, minimize the number of cameras and maximize the area coverage. An effective multi-objective technique is used to obtain the efficient solutions of this problem.