Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Making Compact-Table Compact
KTH, School of Electrical Engineering and Computer Science (EECS), Software and Computer systems, SCS.ORCID iD: 0000-0002-6283-7004
2018 (English)In: 24th International Conference on the Principles and Practice of Constraint Programming, CP 2018, Springer, 2018, Vol. 11008, p. 210-218Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer, 2018. Vol. 11008, p. 210-218
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 11008
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:kth:diva-238350DOI: 10.1007/978-3-319-98334-9_14Scopus ID: 2-s2.0-85053157546ISBN: 9783319983332 (print)OAI: oai:DiVA.org:kth-238350DiVA, id: diva2:1262864
Conference
24th International Conference on the Principles and Practice of Constraint Programming, CP 2018, Lille, France, 27 August 2018 through 31 August 2018
Note

QC 20181113

Available from: 2018-11-13 Created: 2018-11-13 Last updated: 2018-12-17Bibliographically approved

Open Access in DiVA

fulltext(251 kB)65 downloads
File information
File name FULLTEXT01.pdfFile size 251 kBChecksum SHA-512
c7ba5f506bd8ea0ba40472937cb31c9b88e684c9babc80eb04ef184d512cc90bdca3ab65f512ea541f243b77d9601c0620ddb9fea26a88acbc8f7131aedf1bc2
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusconference

Authority records BETA

Schulte, Christian

Search in DiVA

By author/editor
Schulte, Christian
By organisation
Software and Computer systems, SCS
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 65 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 168 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf