Solving a coal mixing problem by column generation.

Summary We formulate and solve an industrial coal blending problem using the column generation technique. The objective of the model is to prescribe to the industrialist, a steel group, the optimal coal blends at each coking plant, as well as the optimal coal purchases. The problem takes into account a large number of constraints coming from the industrial blending process. It is formulated as a nonlinear integer problem. Three heuristics based on the column generation method are proposed to solve the problem. At the master problem level, the demand is distributed among the plants, the production level of each plant, as well as the coal purchase and transportation plan are determined. At the sub-problem level, the optimal mixtures are determined, respecting all the technical constraints of the industrial process. The price information is passed from the master problem to the sub-problems using the dual variables of coal availability constraints. The sub-problems return the optimal coal mixtures in return. The proposed heuristic approach solved the problem submitted by the steel group.