Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Bin Packing Problem with Time Lags

Orlando Rivera Letelier 1 François Clautiaux 2, 3 Ruslan Sadykov 2, 3
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
Abstract : We introduce and motivate a variant of the bin packing problem where bins are assigned to time slots, and minimum and maximum lags are required between some pairs of items. We suggest two integer programming formulations for the problem: a compact one, and a stronger formulation with an exponential number of variables and constraints. We propose a branch-cut-and-price approach which exploits the latter formulation. For this purpose, we devise separation algorithms based on a mathematical characterization of feasible assignments for two important special cases of the problem. Computational experiments are reported for instances inspired from a real-case application of chemical treatment planning in vineyards, as well as for literature instances for special cases of the problem. The experimental results show the efficiency of our branch-cut-and-price approach, as it outperforms the compact formulation of newly proposed instances, and is able to obtain improved lower and upper bounds for literature instances.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [33 references]  Display  Hide  Download
Contributor : Ruslan Sadykov Connect in order to contact the contributor
Submitted on : Tuesday, November 3, 2020 - 12:46:12 PM
Last modification on : Saturday, December 4, 2021 - 3:43:58 AM
Long-term archiving on: : Thursday, February 4, 2021 - 6:31:29 PM


Files produced by the author(s)


  • HAL Id : hal-02986895, version 1



Orlando Rivera Letelier, François Clautiaux, Ruslan Sadykov. Bin Packing Problem with Time Lags. 2020. ⟨hal-02986895⟩



Record views


Files downloads