The classical maximum closure problem is of particular importance to the mining industry because it is the underlying formulation related to mine design and production scheduling; this problem can be easily solved by a polynomial time max-flow/min-cut algorithm. However, if a single capacity constraint is added to the maximum closure formulation, the classical structure is destroyed and is classified in a category of NP-hard problems. Using classical integer programming techniques to solve these formulations with capacity constraints, it can take several days to solve linear programming (LP) relaxation of the real instances. This phenomenon has hindered the development of exact optimization approaches for open pit mine design and production scheduling of realistic sized problems.

In this paper, we develop an algorithm to solve the LP relaxation of the maximal closure problem with a single constraint, which is often referred to as the precedence constrained knapsack problem. The proposed algorithm expands on an existing parametric maximum flow model, and it is shown that the LP relaxation of the precedence constrained knapsack problem can be solved at the cost of only a constant factor of the worst-case time bound of the max flow algorithm. Computational results show that it is possible to solve the LP relaxation less than one minute for open pit mines with hundreds of thousands of mining blocks to be scheduled.