Pattern based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
hal.structure.identifier | Université de Bordeaux [UB] | |
dc.contributor.author | CLAUTIAUX, François | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | SADYKOV, Ruslan | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
hal.structure.identifier | Université de Bordeaux [UB] | |
dc.contributor.author | VANDERBECK, François | |
hal.structure.identifier | Université de Bordeaux [UB] | |
hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
dc.contributor.author | VIAUD, Quentin | |
dc.date.accessioned | 2024-04-04T03:07:45Z | |
dc.date.available | 2024-04-04T03:07:45Z | |
dc.date.issued | 2019-09 | |
dc.identifier.issn | 2192-4406 | |
dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/193473 | |
dc.description.abstractEn | We consider a variant of two-dimensional guillotine cutting-stock problem that arises when different bills of order (or batches) are considered consecutively. The raw material leftover of the last cutting pattern is not counted as waste as it can be reused for cutting the next batch. The objective is thus to maximize the length of the leftover. We propose a diving heuristic based on a Dantzig-Wolfe reformulation solved by column generation in which the pricing problem is solved using dynamic programming (DP). This DP generates so-called non-proper columns, i.e. cutting patterns that cannot participate in a feasible integer solution of the problem. We show how to adapt the standard diving heuristic to this " non-proper " case while keeping its effectiveness. We also introduce the partial enumeration technique, which is designed to reduce the number of non-proper patterns in the solution space of the dynamic program. This technique helps to strengthen the lower bounds obtained by column generation and improve the quality of solutions found by the diving heuristic. Computational results are reported and compared on classical benchmarks from the literature as well as on new instances inspired from industrial data. According to these results, proposed diving algorithms outperform constructive and evolutionary heuristics. | |
dc.language.iso | en | |
dc.publisher | Springer | |
dc.subject.en | Cutting and Packing | |
dc.subject.en | Diving Heuristic | |
dc.subject.en | Dynamic Programming | |
dc.title.en | Pattern based diving heuristics for a two-dimensional guillotine cutting-stock problem with leftovers | |
dc.type | Article de revue | |
dc.identifier.doi | 10.1007/s13675-019-00113-9 | |
dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
bordeaux.journal | EURO Journal on Computational Optimization | |
bordeaux.page | 265–297 | |
bordeaux.volume | 7 | |
bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
bordeaux.issue | 3 | |
bordeaux.institution | Université de Bordeaux | |
bordeaux.institution | Bordeaux INP | |
bordeaux.institution | CNRS | |
bordeaux.peerReviewed | oui | |
hal.identifier | hal-01656179 | |
hal.version | 1 | |
hal.popular | non | |
hal.audience | Internationale | |
hal.origin.link | https://hal.archives-ouvertes.fr//hal-01656179v1 | |
bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=EURO%20Journal%20on%20Computational%20Optimization&rft.date=2019-09&rft.volume=7&rft.issue=3&rft.spage=265%E2%80%93297&rft.epage=265%E2%80%93297&rft.eissn=2192-4406&rft.issn=2192-4406&rft.au=CLAUTIAUX,%20Fran%C3%A7ois&SADYKOV,%20Ruslan&VANDERBECK,%20Fran%C3%A7ois&VIAUD,%20Quentin&rft.genre=article |
Fichier(s) constituant ce document
Fichiers | Taille | Format | Vue |
---|---|---|---|
Il n'y a pas de fichiers associés à ce document. |