Knapsack Problems with Setups
| hal.structure.identifier | Laboratoire de Mathématiques Appliquées du Havre [LMAH] | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| dc.contributor.author | MICHEL, Sophie | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | PERROT, Nancy | |
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | VANDERBECK, François | |
| dc.date.accessioned | 2024-04-04T02:44:12Z | |
| dc.date.available | 2024-04-04T02:44:12Z | |
| dc.date.issued | 2009 | |
| dc.identifier.issn | 0377-2217 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/191390 | |
| dc.description.abstractEn | Knapsack problems with setups find their application in many concrete industrial and financial problems. Moreover, they also arise as subproblems in a Dantzig-Wolfe decomposition approach to more complex combinatorial optimization problems, where they need to be solved repeatedly and therefore efficiently. Here, we consider the multiple-class integer knapsack problem with setups. Items are partitioned into classes whose use implies a setup cost and associated capacity consumption. Item weights are assumed to be a multiple of their class weight. The total weight of selected items and setups is bounded. The objective is to maximize the difference between the profits of selected items and the fixed costs incurred for setting-up classes. A special case is the bounded integer knapsack problem with setups where each class holds a single item and its continuous version where a fraction of an item can be selected while incurring a full setup. The paper shows the extent to which classical results for the knapsack problem can be generalized to these variants with setups. In particular, an extension of the branch-and-bound algorithm of Horowitz and Sahni is developed for problems with positive setup costs. Our direct approach is compared experimentally with the approach proposed in the literature consisting in converting the problem into a multiple choice knapsack with pseudo-polynomial size. | |
| dc.language.iso | en | |
| dc.publisher | Elsevier | |
| dc.subject.en | Knapsack problem | |
| dc.subject.en | fixed cost | |
| dc.subject.en | setup | |
| dc.subject.en | variable upper bound | |
| dc.subject.en | branch-and-bound | |
| dc.title.en | Knapsack Problems with Setups | |
| dc.type | Article de revue | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | European Journal of Operational Research | |
| bordeaux.page | 909-918 | |
| bordeaux.volume | 196 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| bordeaux.type.report | rr | |
| hal.identifier | inria-00232782 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00232782v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=European%20Journal%20of%20Operational%20Research&rft.date=2009&rft.volume=196&rft.spage=909-918&rft.epage=909-918&rft.eissn=0377-2217&rft.issn=0377-2217&rft.au=MICHEL,%20Sophie&PERROT,%20Nancy&VANDERBECK,%20Fran%C3%A7ois&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||