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

Arthur Godet; Xavier Lorca; Gilles Simonin

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

Arthur Godet ^{1, 2} Xavier Lorca ³ Gilles Simonin ^{1, 2}

1 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 : bin packing problem filtering algorithms approximation algorithms constraint programming

Type de document :

Communication dans un congrès

CP 2018 - The 24th International Conference on Principles and Practice of Constraints Programming, Aug 2018, Lille, France. 9 p., 2018, Doctoral Program Proceedings. 〈http://cp2018.a4cp.org/dp-proceedings.pdf#page=7〉

Domaine :

Sciences de l'ingénieur [physics]

Liste complète des métadonnées

https://hal-mines-albi.archives-ouvertes.fr/hal-01923740
Contributeur : Imt Mines Albi Ecole Nationale Supérieure Des Mines d'Albi-Carmaux <>
Soumis le : jeudi 15 novembre 2018 - 14:01:59
Dernière modification le : vendredi 14 décembre 2018 - 10:26:28

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

Identifiants

Collections

Citation

Exporter

Métriques

55

Contact

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

Identifiants

Collections

Citation

Exporter

Partager

Métriques

55

Contact