Solving the Casting problem using Column Generation; better results with 100 variables instead of 1 billion.

Abstract

In casting problems the goal is to cast a number of orders such that the number of heats needed to obtain the molten metal for the casting is minimized. In a paper by Deb and Myburgh from 2016 the authors presented a Genetic Algorithm (GA) to nd a near-optimal solution, which took their GA less than 150 hours for the largest instances with up to 100 million heats. They further stated that this type of problems could not be solved using Integer Linear Programming (ILP) for problem instances with 200 heats or more. In this paper, we refute their claim by showing that an ILP formulation based on a set covering formulation that we solve using Column Generation can easily nd almost optimal solutions (at most a few heats more than the theoretical minimum) within a second, even for their instances requiring 100 million heats. We further show that this ILP model can easily be extended to deal with multiple crucibles and restricted availability of the orders due to release dates and deadlines.