Afficher la notice abrégée

Combining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem

hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorCLAUTIAUX, François
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
dc.contributor.authorSADYKOV, Ruslan
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorVANDERBECK, François
hal.structure.identifierInstitut de Mathématiques de Bordeaux [IMB]
hal.structure.identifierReformulations based algorithms for Combinatorial Optimization [Realopt]
dc.contributor.authorVIAUD, Quentin
dc.date.accessioned2024-04-04T03:11:56Z
dc.date.available2024-04-04T03:11:56Z
dc.date.created2016-12-16
dc.date.issued2018-02-13
dc.identifier.issn1572-5286
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/193816
dc.description.abstractEnThe two-dimensional knapsack problem consists in packing a set of small rectangular items into a given large rectangle while maximizing the total reward associated with selected items. We restrict our attention to packings that emanate from a k-stage guillotine-cut process. We introduce a generic model where a knapsack solution is represented by a flow in a directed acyclic hypergraph. This hypergraph model derives from a forward labeling dynamic programming recursion that enumerates all non-dominated feasible cutting patterns. To reduce the hypergraph size, we make use of further dominance rules and a filtering procedure based on Lagrangian reduced costs fixing of hyperarcs. Our hypergraph model is (incrementally) extended to account for explicit bounds on the number of copies of each item. Our exact forward labeling algorithm is numerically compared to solving the max-cost flow model in the base hyper-graph with side constraints to model production bounds. Benchmarks are reported on instances from the literature and on datasets derived from a real-world application.
dc.language.isoen
dc.publisherElsevier
dc.subject.enCutting and Packing
dc.subject.enDynamic Programming
dc.subject.enLagrangian Filtering
dc.subject.enReduced-Cost Fixing
dc.title.enCombining dynamic programming with filtering to solve a four-stage two-dimensional guillotine-cut bounded knapsack problem
dc.typeArticle de revue
dc.identifier.doi10.1016/j.disopt.2018.02.003
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
bordeaux.journalDiscrete Optimization
bordeaux.page18-44
bordeaux.volume29
bordeaux.hal.laboratoriesInstitut de Mathématiques de Bordeaux (IMB) - UMR 5251*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-01426690
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-01426690v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Discrete%20Optimization&rft.date=2018-02-13&rft.volume=29&rft.spage=18-44&rft.epage=18-44&rft.eissn=1572-5286&rft.issn=1572-5286&rft.au=CLAUTIAUX,%20Fran%C3%A7ois&SADYKOV,%20Ruslan&VANDERBECK,%20Fran%C3%A7ois&VIAUD,%20Quentin&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée