Solving the Identifying Code Set Problem with Grouped Independent Support
17/03/2023, 3pm
Speaker
Abstract
An important problem in network science is finding an optimal placement of sensors in nodes in order to uniquely detect failures in the network. This problem can be modelled as an identifying code set (ICS) problem, introduced by Karpovsky et al. in 1998. The ICS problem aims to find a cover of a set S, such that the elements in the cover define a unique signature for each of the elements of S, and to minimise the cardinality of that cover. In this work, we study a generalised identifying code set (GICS) problem, where a unique signature must be found for each subset of S that has a cardinality of at most k (instead of just each element of S). The concept of an independent support of a Boolean formula was introduced by Chakraborty et al. in 2014 to speed up propositional model counting, by identifying a subset of variables whose truth assignments uniquely define those of the other variables. In this work, we introduce an extended version of independent support, grouped independent support (GIS), and show how to reduce the GICS problem to the GIS problem. We then propose a new solving method for finding a GICS, based on finding a GIS. We show that the prior state-of-the-art approaches yield integer-linear programming (ILP) models whose sizes grow exponentially with the problem size and k, while our GIS encoding only grows polynomially with the problem size and k. While the ILP approach can solve the GICS problem on networks of at most 494 nodes, the GIS-based method can handle networks of up to 21363 nodes; a ~40x improvement. The GIS-based method shows up to a 520x improvement on the ILP-based method in terms of average solving time. For the majority of the instances that can be encoded by both methods, the cardinality of the solution returned by the GIS-based method is less than 10% larger than the cardinality of the solution found by the ILP method.
Bio
Anna Latour is a Research Fellow in prof. dr. Kuldeep Meel's group in the PLSE lab of the School of Computing at NUS. Her current research focus is on model counting, MaxSAT solving and Boolean function synthesis. Anna earned her doctorate degree in 2022 from Leiden University (NL). She completed her dissertation, titled 'Optimal decision-making under constraints and uncertainty', under supervision of prof. dr. Joost Kok, prof. dr. Holger Hoos and dr. Siegfried Nijssen. As a doctorate student, Anna was a visiting researcher at Université catholique de Louvain (BE), working on topics related to constraint programming and knowledge compilation. During a research visit to the University of Toronto (CA), she also worked with prof. dr. Fahiem Bacchus on topics related to model counting. Among Anna's awards are a Master Thesis award from the Royal Dutch Association for Information Professionals and the Royal Holland Society of Sciences and Humanities, a Women Techmakers Scholarship from Google, a Research Pitch Prize from ICT.Open and an Outstanding Reviewer award from AAAI.