Bin packing problem med konflikter består i förpackningsobjekt i ett minimum av behållare med begränsad kapacitet samtidigt som man undviker gemensamma tilldelningar av objekt som är i konflikt. Vår studie visar den jämförelsevis goda prestanda en generisk Branch-and-Price algoritm för detta problem. Vi använde oss av vår black-box lösare BaPCod, förlitar sig på sin generiska förgrening system och primal heuristics, samtidigt utveckla en specifik prissättning oracle. För det fall där konfliktgrafen är ett intervalldiagram, utvecklade vi en dynamisk programmeringsalgoritm för prissättning, medan vi för det allmänna fallet genomförde ett djup-först-sök gren-och-bundet tillvägagångssätt. Algoritmen testas på exempel från litteraturen där konfliktgrafen är ett intervalldiagram, samt på nygenererade fall med ett godtyckligt konfliktdiagram. De beräkningsresultat visar att vår generiska algoritm överträffar speciella ändamål algoritmer i litteraturen, stänga alla öppna instanser i en timme av CPU-tid.
REF beskriver en gren- och prisalgoritm för bin packa problem med konflikter, lösa konfliktbetonade Knapsack subproblem med dynamisk programmering.
Bin Packing with Conflicts: A Generic Branch-and-Price Algorithm
{'venue': 'INFORMS J. Comput.', 'journal': 'INFORMS J. Comput.', 'mag_field_of_study': ['Computer Science', 'Mathematics']}