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 metadatas

Cited literature [33 references]  Display  Hide  Download

https://hal.inria.fr/hal-02986895
Contributor : Ruslan Sadykov <>
Submitted on : Tuesday, November 3, 2020 - 12:46:12 PM
Last modification on : Monday, November 16, 2020 - 8:26:04 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02986895, version 1

Collections

Citation

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

Share

Metrics

Record views

44

Files downloads

56