EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC 4.0

A Branch-and-Cut-and-Price Algorithm for Cutting Stock and Related Problems

Renan F. F. da Silva, Rafael C. S. Schouery

Revista Eletrônica de Iniciação Científica em Computação · 2024

DOI: 10.5753/reic.2024.4646 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Revista Eletrônica de Iniciação Científica em Computação, 2024. Verfasst von Renan F. F. da Silva und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 15 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this project, we introduce a branch-and-cut-and-price framework to solve the Cutting Stock Problems with strong relaxations using the Set Covering (Packing) Formulations, which are solved through column generation. We propose an extended Ryan-Foster branching scheme tailored to non-binary models, a pricing algorithm that produces convergence in a few iterations, and a variable selection technique based on branching history. These strategies are combined with subset-row cuts and custom primal heuristics to create a framework that overcomes the current state-of-the-art of Cutting Stock Problem, Skiving Stock Problem, and other related problems, being at least twice faster in the first problem and at least 60% faster in the second one.

Zitieren

APA

Silva, R. F. F. D., & Schouery, R. C. S. (2024). A Branch-and-Cut-and-Price Algorithm for Cutting Stock and Related Problems. Revista Eletrônica de Iniciação Científica em Computação. https://doi.org/10.5753/reic.2024.4646

Vancouver

Silva RFFD, Schouery RCS. A Branch-and-Cut-and-Price Algorithm for Cutting Stock and Related Problems. Revista Eletrônica de Iniciação Científica em Computação. 2024. doi:10.5753/reic.2024.4646

BibTeX
@article{Silva2024,
  author = {Silva, Renan F. F. da and Schouery, Rafael C. S.},
  title = {A Branch-and-Cut-and-Price Algorithm for Cutting Stock and Related Problems},
  journal = {Revista Eletrônica de Iniciação Científica em Computação},
  year = {2024},
  doi = {10.5753/reic.2024.4646}
}
Kostenlos starten →