Discrete flow pooling problems in coal supply chains

Abstract

The pooling problem is a nonconvex nonlinear programming problem (NLP) with applications in the refining and petrochemical industries, but also the coal mining industry. The problem can be stated as follows: given a set of raw material suppliers (inputs) and qualities of the supplies, find a cost-minimising way of blending these raw materials in intermediate pools and outputs so as to satisfy requirements on the output qualities. The blending in two stages (in pools and outputs) introduces bilinear constraints. The pooling problem can alternatively be described as a minimum cost network flow problem with additional bilinear constraints to capture the blending of raw materials. In this paper we study a variation of the pooling problem that arises naturally in the coal mining industry and is sometimes referred to as grade targeting. Coal is made-to-order according to customers’ desired product qualities. Deviations from these target qualities result in contractually agreed bonuses and penalties. In the pooling problem variation we study, costs are associated with these bonuses and penalties instead of network flows. While in the original pooling problem we have hard bounds on the qualities and unmet demand is penalised in the objective function, in our coal mining variation we have hard demand constraints and deviations from target qualities are penalised. This makes finding a feasible solution easy, while in the pooling problem finding a nontrivial feasible solution that satisfies the quality requirements is already hard. An implication of this is that we are able to solve larger problem instances than those typically studied in the pooling problem literature. To model the coal blending process accurately, we define a time-expanded network where the intermediate pools represent coal stockpiles over time. Since coal is transported in large quantities, we study the trade-off between continuous and discretized flows in coal blending, i.e., solving a continuous flow problem where arbitrarily small flows are allowed versus solving a discretized flow problem where flows must be in multiples of some basic unit, e.g. trainloads. We also study two exact mixed-integer linear programming (MILP) linearizations of these mixed-integer nonlinear programs (MINLPs), which can be derived from unary and binary expansions of the flow integrality constraint. Such discretizations are typically studied as approximations to an originally continuous problem, however, in our application, a discretized formulation describes the original problem more accurately than a continuous formulation. The paper is organized as follows. In Section 1.1, we introduce the pooling problem and present a variant of the well-known PQ-formulation. In Section 1.2, we extend the pooling problem to model a simplified coal supply chain. After a short literature review on coal supply chains, we present four different problems: the continuous flow problem (a MINLP), in which arbitrarily small flows are allowed, and three discretized flow problems (a MINLP and two MILPs), in which flows must be in multiples of trainloads. The discretization can be achieved by adding integrality constraints for the flow variables. We then show how to overcome the nonlinearity which is inherent in the pooling problem with the use of unary and binary expansions of the integer flow variables, which yields exact MILP reformulations of the discretized MINLP. We conclude the paper with Section 2 where we provide computational results for the four different problems which we solve for a real-life industry setting.