Making Compact-Table Compact
Linnea Ingmar, Christian Schulte.
The compact-table propagator for table constraints appears to be a strong candidate for inclusion into any constraint solver due to its efficiency and simplicity. However, successful integration into a constraint solver based on copying rather than trailing is not obvious: while the underlying bit-set data structure is sparse for efficiency it is not compact for memory, which is essential for a copying solver.
The paper introduces techniques to make compact-table an excellent fit for a copying solver. The key is to make sparse bit-sets dynamically compact (only their essential parts occupy memory and their implementation is dynamically adapted during search) and tables shared (their read-only parts are shared among copies). Dynamically compact bit-sets reduce peak memory by 7.2% and runtime by 13.6% on average and by up to 66.3% and 33.2%. Shared tables even further reduce runtime and memory usage. The reduction in runtime exceeds the reduction in memory and a cache analysis indicates that our techniques might also be beneficial for trailing solvers. The proposed implementation has replaced Gecode's original implementations as it runs on average almost an order of magnitude faster while using half the memory.
In: John Hooker, editor, Twentyforth International Conference on Principles and Practice of Constraint Programming, Lille, France, volume 11008 of Lecture Notes in Computer Science, pages 210-218. Springer-Verlag, August, 2018. DOI 10.1007/978-3-319-98334-9_14.
Copyright Springer-Verlag, the original publication is available at www.springerlink.com