Mathematical models based on decision hypergraphs for designing a storage cabinet
| hal.structure.identifier | Université de Bordeaux [UB] | |
| hal.structure.identifier | Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE] | |
| dc.contributor.author | MARQUES, Luis | |
| hal.structure.identifier | Université de Bordeaux [UB] | |
| 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 | Université de Bordeaux [UB] | |
| hal.structure.identifier | Formulations étendues et méthodes de décomposition pour des problèmes génériques d'optimisation [EDGE] | |
| dc.contributor.author | FROGER, Aurélien | |
| dc.date.accessioned | 2024-04-04T02:32:24Z | |
| dc.date.available | 2024-04-04T02:32:24Z | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190381 | |
| dc.description.abstractEn | We study the problem of designing a cabinet made up of a set of shelves that contain compartments whose contents slide forward on opening. Considering a set of items candidate to be stored in the cabinet over a given time horizon, the problem is to design a set of shelves, a set of compartments in each shelf and to select the items to be inserted into the compartments. The objective is to maximize the sum of the profits of the selected items. We call our problem the Storage Cabinet Physical Design (SCPD) problem. The SCPD problem combines a two-dimensional guillotine cutting problem for the design of the shelves and compartments with a set of temporal knapsack problems for the selection and assignment of items to compartments. We formalize the SCPD problem and formulate it as a maximum cost flow problem in a decision hypergraph with additional linear constraints. To reduce the size of this model, we break symmetries, generalize graph compression techniques and exploit dominance rules for precomputing subproblem solutions. We also present a set of valid inequalities to improve the linear relaxation of the model. We empirically show that solving the arc flow model with all our enhancements outperforms solving a compact mixed integer linear programming formulation of the SCPD problem. | |
| dc.description.sponsorship | AD-Lib : une bibliothèque d'agrégation/désagrégation pour des modèles de décisions séquentielles - ANR-22-CE23-0014 | |
| dc.language.iso | en | |
| dc.rights.uri | http://creativecommons.org/licenses/by/ | |
| dc.subject.en | Cutting and Packing | |
| dc.subject.en | Integer linear programming | |
| dc.subject.en | Temporal knapsack | |
| dc.subject.en | Arc flow models | |
| dc.subject.en | Decision hypergraphs | |
| dc.title.en | Mathematical models based on decision hypergraphs for designing a storage cabinet | |
| dc.type | Document de travail - Pré-publication | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| hal.identifier | hal-04303041 | |
| hal.version | 1 | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-04303041v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.au=MARQUES,%20Luis&CLAUTIAUX,%20Fran%C3%A7ois&FROGER,%20Aur%C3%A9lien&rft.genre=preprint |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||