An improved binary programming formulation for the secure domination problem

Ryan Burdett, Michael Haythorpe

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)


The secure domination problem, a variation of the domination problem with some importantreal-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 pro-posed 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.
Original languageEnglish
Pages (from-to)561-573
Number of pages13
JournalAnnals of Operations Research
Issue number2
Publication statusPublished - Dec 2020


  • secure
  • Domination
  • Graph
  • binary programming
  • Formulation
  • secure connected


Dive into the research topics of 'An improved binary programming formulation for the secure domination problem'. Together they form a unique fingerprint.

Cite this