Deriving filtering algorithms from dedicated algorithms: zoom on the Bin Packing problem

Arthur Godet 1, 2 Xavier Lorca 3 Gilles Simonin 1, 2
1 IMT Atlantique - DAPI - Département Automatique, Productique et Informatique
2 TASC - Théorie, Algorithmes et Systèmes en Contraintes
LS2N - Laboratoire des Sciences du Numérique de Nantes
3 CGI - Centre Génie Industriel
Abstract : Solving NP-complete problems can be tough because of the combinatorics. Constraint Programming and Approximation algorithms can be used to solve these problems. In this paper, we explore how to automatically derive filtering algorithms from a dedicated algorithm solving the Bin Packing problem. To this end, we automatically derive a filtering algorithm from the Best-Fit algorithm. We empirically show that our filtering algorithm BF-Prop is experimentally strictly more efficient in terms of filtering than Shaw’s state-of-the-art global constraint.
Keywords : constraint programming approximation algorithms bin packing problem filtering algorithms
Document type :
Conference papers
Complete list of metadatas
https://hal-mines-albi.archives-ouvertes.fr/hal-01923740
Contributor : Imt Mines Albi Ecole Nationale Supérieure Des Mines d'Albi-Carmaux <>
Submitted on : Thursday, November 15, 2018 - 2:01:59 PM
Last modification on : Thursday, November 21, 2019 - 12:58:01 PM

Identifiers

  • HAL Id : hal-01923740, version 1

Collections

MINES-ALBI | CGI | CNRS | EC-NANTES | UNAM | LS2N | IMT-ATLANTIQUE | UNIV-NANTES | LS2N-TASC

Citation

Arthur Godet, Xavier Lorca, Gilles Simonin. Deriving filtering algorithms from dedicated algorithms: zoom on the Bin Packing problem. CP 2018 - The 24th International Conference on Principles and Practice of Constraints Programming : Doctoral Program Proceedings, Aug 2018, Lille, France. 9 p. ⟨hal-01923740⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

113

Contact

Informations

CCSD