An improved binary programming formulation for the secure domination problem
- PDF / 369,259 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 107 Downloads / 242 Views
An improved binary programming formulation for the secure domination problem Ryan Burdett1 · Michael Haythorpe1 Accepted: 22 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The secure domination problem, a variation of the domination problem with some important real-world applications, is considered. Very few algorithmic attempts to solve this problem have been presented in literature, and the most successful to date is a binary programming formulation which is solved using CPLEX. A new binary programming formulation is proposed here which requires fewer constraints and fewer binary variables than the existing formulation. It is implemented in CPLEX, and tested on certain families of graphs that have previously been considered in the context of secure domination. It is shown that the runtime required for the new formulation to solve the instances is significantly less than that of the existing formulation. An extension of our formulation that solves the related, but further constrained, secure connected domination problem is also given; to the best of the authors’ knowledge, this is the first such formulation in literature. Keywords Secure · Domination · Graph · Binary programming · Formulation · Secure connected
1 Introduction In this manuscript we consider the secure domination problem, which is a recently introduced special case of the more famous domination problem. Consider a graph G = V , E, with vertex set V and edge set E. We shall use the convention that n = |V | is the order of the graph, and m = |E| is the size of the graph. We will use N (i) to denote the subset of vertices { j | j ∈ V , (i, j) ∈ E}, and N [i] = {N (i), i}. We refer to N (i) as the open neighbourhood of i and N [i] as the closed neighbourhood of i. Then a dominating set of G is a subset of the vertices D that satisfies the following: for every vertex v ∈ V , at least one vertex in the closed neighbourhood of v is contained in D. That is, every vertex in the graph is either in D, or is adjacent to a vertex in D; we refer to vertices for which this is true as being covered.
B
Michael Haythorpe [email protected] Ryan Burdett [email protected]
1
Flinders University, 1284 South Road,Tonsley Park, Adelaide, SA, Australia
123
Annals of Operations Research
Then the domination problem for a given graph G is to find the dominating set D ∗ of smallest cardinality for that graph, where the cardinality of D ∗ is called the domination number γ (G) of the graph. There are many real-world interpretations of the domination problem, and we outline a common one here as follows. Suppose that the graph G corresponds to a facility, and each vertex V corresponds to a location in the facility. If you can observe location i from location j, then (i, j) is an edge in G. Then, if a dominating set D is found, and a guard is placed at each of the locations in D, every location in the facility is being observed by at least one guard. The domination problem attempts to do so with the
Data Loading...
