Bin Packing with conflicts: a generic branch-and-price algorithm
| hal.structure.identifier | Reformulations based algorithms for Combinatorial Optimization [Realopt] | |
| hal.structure.identifier | Institut de Mathématiques de Bordeaux [IMB] | |
| dc.contributor.author | SADYKOV, Ruslan | |
| 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:28:07Z | |
| dc.date.available | 2024-04-04T02:28:07Z | |
| dc.date.issued | 2013 | |
| dc.identifier.issn | 1091-9856 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/190073 | |
| dc.description.abstractEn | In the the bin packing problem with conflicts, one has to pack items in the minimum number of bins while avoiding joint assignments of items that are in conflict. Our study shows a comparatively good performance of a generic Branch-and-Price algorithm for this problem. We made use of our black box solver BaPCod, relying on its generic branching scheme and primal heuristics, while developing a specific pricing oracle. For the case where the conflict graph is an interval graph, we propose a fast dynamic programming algorithm for pricing, while for the general case we use a classic depth-first-search branch-and-bound approach. The algorithm is tested on instances from the literature where the conflict graph is an interval graph, as well as on newly generated instances with an arbitrarily conflict graph. The computational results show that the generic algorithm outperforms special purpose algorithms of the literature, closing all open instances in one hour of CPU time. | |
| dc.language.iso | en | |
| dc.publisher | Institute for Operations Research and the Management Sciences (INFORMS) | |
| dc.title.en | Bin Packing with conflicts: a generic branch-and-price algorithm | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.1287/ijoc.1120.0499 | |
| dc.subject.hal | Informatique [cs]/Recherche opérationnelle [cs.RO] | |
| bordeaux.journal | INFORMS Journal on Computing | |
| bordeaux.page | 244-255 | |
| bordeaux.volume | 25 | |
| bordeaux.hal.laboratories | Institut de Mathématiques de Bordeaux (IMB) - UMR 5251 | * |
| bordeaux.issue | 2 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| bordeaux.type.report | rr | |
| hal.identifier | inria-00539869 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00539869v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=INFORMS%20Journal%20on%20Computing&rft.date=2013&rft.volume=25&rft.issue=2&rft.spage=244-255&rft.epage=244-255&rft.eissn=1091-9856&rft.issn=1091-9856&rft.au=SADYKOV,%20Ruslan&VANDERBECK,%20Fran%C3%A7ois&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||