Bin Packing Problem with Time Lags
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]
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]
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]
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]
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]
< Reduce
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]
Language
en
Article de revue
This item was published in
INFORMS Journal on Computing. 2022-03-16, vol. 34, n° 4, p. 2249-2270
Institute for Operations Research and the Management Sciences (INFORMS)
English 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 ...Read more >
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.Read less <
Origin
Hal imported