DROPS

Document

DOI: 10.4230/LIPIcs.CP.2021.46

Positive and Negative Length-Bound Reachability Constraints

Authors: Luis Quesada and Kenneth N. Brown

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract

In many application problems, including physical security and wildlife conservation, infrastructure must be configured to ensure or deny paths between specified locations. We model the problem as sub-graph design subject to constraints on paths and path lengths, and propose length-bound reachability constraints. Although reachability in graphs has been modelled before in constraint programming, the interaction of positive and negative reachability has not been studied in depth. We prove that deciding whether a set of positive and negative reachability constraints are satisfiable is NP complete. We show the effectiveness of our approach on decision problems, and also on optimisation problems. We compare our approach with existing constraint models, and we demonstrate significant improvements in runtime and solution costs, on a new problem set.

Cite as

Luis Quesada and Kenneth N. Brown. Positive and Negative Length-Bound Reachability Constraints. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 46:1-46:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{quesada_et_al:LIPIcs.CP.2021.46,
  author =	{Quesada, Luis and Brown, Kenneth N.},
  title =	{{Positive and Negative Length-Bound Reachability Constraints}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.46},
  URN =		{urn:nbn:de:0030-drops-153372},
  doi =		{10.4230/LIPIcs.CP.2021.46},
  annote =	{Keywords: Reachability Constraints, Graph Connectivity, Constraint Programming}
}

Search Results

Documents authored by Brown, Kenneth N.

Positive and Negative Length-Bound Reachability Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message