[Back]

B. Klocker, G. Raidl:
"Solving a Weighted Set Covering Problem for Improving Algorithms for Cutting Stock Problems with Setup Costs by Solution Merging";
in: "Computer Aided Systems Theory -- EUROCAST 201", 10671; issued by: Springer; Springer LNCS, 2018, ISBN: 978-3-319-74727-9, 355 - 363.

Abstract. Many practical applications of the cutting stock problem (CSP) have additional costs for setting up machine configurations. In this paper we describe a post-processing method which can improve so-lutions in general, but works especially well if additional setup costs are considered. We formalize a general cutting stock problem and a solution merging problem which can be used as a post-processing step. To solve the solution merging problem we propose an integer linear programming (ILP) model, a greedy approach, a PILOT method and a beam search. We apply the approaches to different real-world problems and compare their results. They show that in up to 50% of the instances the post-processing could improve the previous best solution.

https://publik.tuwien.ac.at/files/publik_273665.pdf