Cardinality reasoning for bin-packing constraint: Application to a tank allocation problem

Pierre Schaus, Jean Charles Régin, Rowan Van Schaeren, Wout Dullaert, Birger Raa

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

Flow reasoning has been successfully used in CP for more than a decade. It was originally introduced by Régin in the well-known Alldifferent and Global Cardinality Constraint (GCC) available in most of the CP solvers. The BinPacking constraint was introduced by Shaw and mainly uses an independent knapsack reasoning in each bin to filter the possible bins for each item. This paper considers the use of a cardinality/flow reasoning for improving the filtering of a bin-packing constraint. The idea is to use a GCC as a redundant constraint to the BinPacking that will count the number of items placed in each bin. The cardinality variables of the GCC are then dynamically updated during the propagation. The cardinality reasoning of the redundant GCC makes deductions that the bin-packing constraint cannot see since the placement of all items into every bin is considered at once rather than for each bin individually. This is particularly well suited when a minimum loading in each bin is specified in advance. We apply this idea on a Tank Allocation Problem (TAP). We detail our CP model and give experimental results on a real-life instance demonstrating the added value of the cardinality reasoning for the bin-packing constraint.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings
Pages815-822
Number of pages8
Volume7514 LNCS
DOIs
Publication statusPublished - 2012
Event18th International Conference on Principles and Practice of Constraint Programming, CP 2012 - Quebec City, QC, Canada
Duration: 8 Oct 201212 Oct 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7514 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

Conference18th International Conference on Principles and Practice of Constraint Programming, CP 2012
CountryCanada
CityQuebec City, QC
Period8/10/1212/10/12

Fingerprint

Bin Packing
Bins
Cardinality Constraints
Global Constraints
Cardinality
Reasoning
Knapsack
Deduction
Placement
Count
Filtering
Propagation
Filter
Experimental Results

Keywords

  • Constraint Programming
  • Load Planning
  • Tank Allocation

Cite this

Schaus, P., Régin, J. C., Van Schaeren, R., Dullaert, W., & Raa, B. (2012). Cardinality reasoning for bin-packing constraint: Application to a tank allocation problem. In Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings (Vol. 7514 LNCS, pp. 815-822). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7514 LNCS). https://doi.org/10.1007/978-3-642-33558-7_58
Schaus, Pierre ; Régin, Jean Charles ; Van Schaeren, Rowan ; Dullaert, Wout ; Raa, Birger. / Cardinality reasoning for bin-packing constraint : Application to a tank allocation problem. Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. Vol. 7514 LNCS 2012. pp. 815-822 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{624cb49656304dcdbc8de7cccb95a3ad,
title = "Cardinality reasoning for bin-packing constraint: Application to a tank allocation problem",
abstract = "Flow reasoning has been successfully used in CP for more than a decade. It was originally introduced by R{\'e}gin in the well-known Alldifferent and Global Cardinality Constraint (GCC) available in most of the CP solvers. The BinPacking constraint was introduced by Shaw and mainly uses an independent knapsack reasoning in each bin to filter the possible bins for each item. This paper considers the use of a cardinality/flow reasoning for improving the filtering of a bin-packing constraint. The idea is to use a GCC as a redundant constraint to the BinPacking that will count the number of items placed in each bin. The cardinality variables of the GCC are then dynamically updated during the propagation. The cardinality reasoning of the redundant GCC makes deductions that the bin-packing constraint cannot see since the placement of all items into every bin is considered at once rather than for each bin individually. This is particularly well suited when a minimum loading in each bin is specified in advance. We apply this idea on a Tank Allocation Problem (TAP). We detail our CP model and give experimental results on a real-life instance demonstrating the added value of the cardinality reasoning for the bin-packing constraint.",
keywords = "Constraint Programming, Load Planning, Tank Allocation",
author = "Pierre Schaus and R{\'e}gin, {Jean Charles} and {Van Schaeren}, Rowan and Wout Dullaert and Birger Raa",
year = "2012",
doi = "10.1007/978-3-642-33558-7_58",
language = "English",
isbn = "9783642335570",
volume = "7514 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "815--822",
booktitle = "Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings",

}

Schaus, P, Régin, JC, Van Schaeren, R, Dullaert, W & Raa, B 2012, Cardinality reasoning for bin-packing constraint: Application to a tank allocation problem. in Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. vol. 7514 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7514 LNCS, pp. 815-822, 18th International Conference on Principles and Practice of Constraint Programming, CP 2012, Quebec City, QC, Canada, 8/10/12. https://doi.org/10.1007/978-3-642-33558-7_58

Cardinality reasoning for bin-packing constraint : Application to a tank allocation problem. / Schaus, Pierre; Régin, Jean Charles; Van Schaeren, Rowan; Dullaert, Wout; Raa, Birger.

Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. Vol. 7514 LNCS 2012. p. 815-822 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7514 LNCS).

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Cardinality reasoning for bin-packing constraint

T2 - Application to a tank allocation problem

AU - Schaus, Pierre

AU - Régin, Jean Charles

AU - Van Schaeren, Rowan

AU - Dullaert, Wout

AU - Raa, Birger

PY - 2012

Y1 - 2012

N2 - Flow reasoning has been successfully used in CP for more than a decade. It was originally introduced by Régin in the well-known Alldifferent and Global Cardinality Constraint (GCC) available in most of the CP solvers. The BinPacking constraint was introduced by Shaw and mainly uses an independent knapsack reasoning in each bin to filter the possible bins for each item. This paper considers the use of a cardinality/flow reasoning for improving the filtering of a bin-packing constraint. The idea is to use a GCC as a redundant constraint to the BinPacking that will count the number of items placed in each bin. The cardinality variables of the GCC are then dynamically updated during the propagation. The cardinality reasoning of the redundant GCC makes deductions that the bin-packing constraint cannot see since the placement of all items into every bin is considered at once rather than for each bin individually. This is particularly well suited when a minimum loading in each bin is specified in advance. We apply this idea on a Tank Allocation Problem (TAP). We detail our CP model and give experimental results on a real-life instance demonstrating the added value of the cardinality reasoning for the bin-packing constraint.

AB - Flow reasoning has been successfully used in CP for more than a decade. It was originally introduced by Régin in the well-known Alldifferent and Global Cardinality Constraint (GCC) available in most of the CP solvers. The BinPacking constraint was introduced by Shaw and mainly uses an independent knapsack reasoning in each bin to filter the possible bins for each item. This paper considers the use of a cardinality/flow reasoning for improving the filtering of a bin-packing constraint. The idea is to use a GCC as a redundant constraint to the BinPacking that will count the number of items placed in each bin. The cardinality variables of the GCC are then dynamically updated during the propagation. The cardinality reasoning of the redundant GCC makes deductions that the bin-packing constraint cannot see since the placement of all items into every bin is considered at once rather than for each bin individually. This is particularly well suited when a minimum loading in each bin is specified in advance. We apply this idea on a Tank Allocation Problem (TAP). We detail our CP model and give experimental results on a real-life instance demonstrating the added value of the cardinality reasoning for the bin-packing constraint.

KW - Constraint Programming

KW - Load Planning

KW - Tank Allocation

UR - http://www.scopus.com/inward/record.url?scp=84868288562&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84868288562&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-33558-7_58

DO - 10.1007/978-3-642-33558-7_58

M3 - Conference contribution

SN - 9783642335570

VL - 7514 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 815

EP - 822

BT - Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings

ER -

Schaus P, Régin JC, Van Schaeren R, Dullaert W, Raa B. Cardinality reasoning for bin-packing constraint: Application to a tank allocation problem. In Principles and Practice of Constraint Programming - 18th International Conference, CP 2012, Proceedings. Vol. 7514 LNCS. 2012. p. 815-822. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-33558-7_58