RIVERA LETELIER, Orlando; CLAUTIAUX, François; SADYKOV, Ruslan

doi:10.1287/ijoc.2022.1165

Métadonnées

Licence d’utilisation du document

RIVERA LETELIER, Orlando
Universidad Adolfo Ibáñez [Santiago]

CLAUTIAUX, François
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]

SADYKOV, Ruslan
Reformulations based algorithms for Combinatorial Optimization [Realopt]
Institut de Mathématiques de Bordeaux [IMB]
Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE]

Langue

Article de revue

Ce document a été publié dans

INFORMS Journal on Computing. 2022-03-16, vol. 34, n° 4, p. 2249-2270

Institute for Operations Research and the Management Sciences (INFORMS)

Résumé en anglais

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.< Réduire

Métadonnées

Partager cette publication !

Licence d’utilisation du document

Bin Packing Problem with Time Lags

Langue

Ce document a été publié dans

Résumé en anglais

URI

DOI

Origine

Unités de recherche