Bin Packing Problem with Time Lags
| hal.structure.identifier | Universidad Adolfo Ibáñez [Santiago] | |
| dc.contributor.author | RIVERA LETELIER, Orlando | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE] | |
| dc.contributor.author | CLAUTIAUX, François | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| hal.structure.identifier | Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE] | |
| dc.contributor.author | SADYKOV, Ruslan | |
| dc.date.accessioned | 2024-04-04T02:37:12Z | |
| dc.date.available | 2024-04-04T02:37:12Z | |
| dc.date.issued | 2022-03-16 | |
| dc.identifier.issn | 1091-9856 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190786 | |
| dc.description.abstractEn | 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. | |
| dc.language.iso | en | |
| dc.publisher | Institute for Operations Research and the Management Sciences (INFORMS) | |
| dc.title.en | Bin Packing Problem with Time Lags | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1287/ijoc.2022.1165 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | INFORMS Journal on Computing | |
| bordeaux.page | 2249-2270 | |
| bordeaux.volume | 34 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 4 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-02986895 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-02986895v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=INFORMS%20Journal%20on%20Computing&rft.date=2022-03-16&rft.volume=34&rft.issue=4&rft.spage=2249-2270&rft.epage=2249-2270&rft.eissn=1091-9856&rft.issn=1091-9856&rft.au=RIVERA%20LETELIER,%20Orlando&CLAUTIAUX,%20Fran%C3%A7ois&SADYKOV,%20Ruslan&rft.genre=article |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||