Applications of Integer Programming and Decomposition to Scheduling Problems: the Strategic Mine Planning Problem and the Bin Packing Problem with Time Lag

Abstract

In scheduling problems, the goal is to assign time slots to a set of activities. In these problems, there are typically precedence constraints between activities that dictate the order in which they can be carried out and resource constraints that limit the number that can simultaneously be executed. In this thesis, we develop mixed integer programming methodologies, based on decomposition methods, for two very different classes of scheduling problems. These are the Strategic Open Pit Mine Planning Problem (SOPMP) and the Bin Packing Problem with Time Lags. Given a discretized representation of an orebody known as a block model, the SOPMP that we consider consists of defining which blocks to extract, when to extract them, and how or whether to process them, in such a way as to comply with operational constraints and maximize net present value. These problems are known to be very difficult due to the large size of real mine planning problems (eg, millions of blocks, dozens of years). They are also very important in the mining industry. Every major mining operation in the world must solve this problem, at the very least, on a yearly basis. In this thesis, we tackle the SOPMP in Chapters 2 and 3. In Chapter 2 we begin by studying a lagrangean algorithm developed by Dan Bienstock and Mark Zuckerberg (henceforth, the BZ algorithm) in 2009 for solving the LP relaxation of large instances of SOPMP. In this study we generalize the classes of problems that can be solved with the BZ algorithm, and show that it can be cast as a special type of column generation algorithm. We prove, for general classes of mixed integer programming problems, that the BZ relaxation provides a bound that lies between the LP relaxation and Dantzig- Wolfe bounds. We further develop computational speed-ups that improve the performance of the BZ algorithm in practice, and test these on a large collection of data-sets. In Chapter 3 we deal with the problem of computing integer-feasible solution to SOPMP. Using the BZ algorithm developed in Chapter 2, we develop heuristics for this. In addition, we develop pre-procesing algorithms that reduce problem size, and embed the BZ algorithm in a branch-and-cut framework that makes use of two new classes of cutting planes. When comparing the value of the heuristics to the LP relaxation bound, the average gap computed is close to 10%. However, when applying the pre-processing techniques and cutting planes, this is reduced to 1.5% at the root node. Four hours of branching further reduces this to 0.6%. In Chapter 4, the BPPTL is presented. This is a generalization of the Bin i Packing Problem in which bins must be assigned to time slots, while satisfying precedence constraints with lags. Two integer programming formulations are proposed: a compact formulation that models the problem exactly, and an extended formulation that models a relaxation. For two special cases of the problem, the case with unlimited bins per period and the case with one bin per period and non-negative time lags, we strengthen the extended formulation with a special family of constraints. We propose a branch-cut-and-price (BCP) algorithm to solve this formulation, with separation of integer and fractional solutions, and a strong diving heuristic. Computational experiments confirm that the BCP algorithm outperforms solving the compact formulation with a commercial solver. Using this approach we were able to optimally solve 70% of a class of previously open instances of this problem.