Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Implementation and Evaluation of a Sweep-Based Propagator for Diffn in Gecode
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

This thesis builds upon Beldiceanu and Carlsson's sweep-based propagator for a non-overlapping-rectangle constraint. I design and implement a sweep-based propagator for the Diffn constraint, which deals with rectangles generalised to any number of dimensions. Such a constraint is useful in modelling scheduling, assignment, and packing problems. The work is carried out in the context of the copying constraint programming solver Gecode. Different algorithm optimisations are explored and evaluated across a range of benchmarks in terms of inference strength and execution time. The best optimisation configuration is compared against the propagator for Gecode's current two-dimensional counterpart to Diffn: NoOverlap. The results show that the sweep-based Diffn propagator yields smaller search trees than the NoOverlap propagator in models where non-overlapping constraints dominate the propagation phase, as the sweep-based propagator yields stronger bounds tightening. As other constraints are introduced into the models, the difference in search-tree size becomes smaller, and in cases where the two propagators yield identical search trees, the NoOverlap propagator performs best. While the sweep-based approach shows great potential in some of the benchmarks, the stronger inference is often dwarfed in models with several different constraints.

Place, publisher, year, edition, pages
2017. , p. 72
Series
IT ; 17025
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:uu:diva-325845OAI: oai:DiVA.org:uu-325845DiVA, id: diva2:1117103
Educational program
Master Programme in Computer Science
Supervisors
Examiners
Available from: 2017-06-28 Created: 2017-06-28 Last updated: 2017-07-03Bibliographically approved

Open Access in DiVA

fulltext(719 kB)118 downloads
File information
File name FULLTEXT01.pdfFile size 719 kBChecksum SHA-512
dd9cc6f5cffde0c6fc6edc638a706fa1afaab83aee3c5a33008d415dfd1bbfe288ed22318c6068a8c2233390741eecb0b9375dc8e2833c7956342c04e7c70a36
Type fulltextMimetype application/pdf

By organisation
Department of Information Technology
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
Total: 118 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

urn-nbn

Altmetric score

urn-nbn
Total: 1390 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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