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
New filtering for the cumulative constraint in the context of non-overlapping rectangles
RISE, Swedish ICT, SICS, Computer Systems Laboratory.ORCID iD: 0000-0003-3079-8095
2008 (English)In: CPAIOR 2008, Springer , 2008, 1, Vol. 5015, 21-35 p.Conference paper, (Refereed)
Abstract [en]

This paper describes new filtering methods for the cumulative constraint. The first method introduces bounds for the so called longest cumulative hole problem and shows how to use these bounds in the context of the non-overlapping constraint. The second method introduces balancing knapsack constraints which relate the total height of the tasks that end at a specific time-point with the total height of the tasks that start at the same time-point. Experiments on tight rectangle packing problems show that these methods drastically reduce both the time and the number of backtracks for finding all solutions as well as for finding the first solution. For example, we found without backtracking all solutions to 66 perfect square instances of order 23-25 and sizes ranging from 332 times 332 to 661 times 661.

Place, publisher, year, edition, pages
Springer , 2008, 1. Vol. 5015, 21-35 p.
Series
LNCS, 5015
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:ri:diva-22891DOI: 10.1007/978-3-540-68155-7_5OAI: oai:DiVA.org:ri-22891DiVA: diva2:1042456
Conference
5th International Conference, CPAIOR 2008, 20-23 May 2008, Paris, France
Note

Lecture notes in computer science; 5015. DOI: 10.1007/978-3-540-68155-7_5.

Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2017-08-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full texthttp

Search in DiVA

By author/editor
Carlsson, Mats
By organisation
Computer Systems Laboratory
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 11 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
v. 2.26.0