On the Directed Cut Polyhedra and Open Pit Mining

Many aspects of open pit mine planning can be modelled as a combinatorial optimization problem. This thesis reviews some existing mine scheduling methods and some of their short comings. Many of the problems are related to the partially ordered knapsack problem with multiple knapsack constraints. This is a special case of a maximum directed cut problem with multiple knapsack constraints on the arcs in the cut.;A polynomial time algorithm for optimizing over the undirected cut polytope is given for the special case of when an objective function has the same optimal value on two relaxations, the rooted metric polytope and the metric polytope. Projections of the directed cut polytope onto the arc set of an arbitrary directed graph are researched. A method known as triangular elimination is extended from the undirected cut context to a directed cut context.;A complexity result proving that the problem of selecting a physically connected maximum value set of blocks from a 2D grid is NP-hard is given. In the mining literature such a grid would be called a bench.;An implementation of a LP rounding algorithm known as pipage rounding is applied to a pushback design problem. This simple and efficient technique produces results within 6.4% of optimal for a real data set.;The major contribution of this thesis is the study of the directed cut polytope and cone, which are the convex hull and positive hull of all directed cut vectors of a complete directed graph, respectively. Many results are presented on the polyhedral structure of these polyhedra. A relation between the directed cut polyhedra and undirected cut polyhedra is established that provides families of facet defining inequalities for the directed cut polyhedra from the undirected cut polyhedra.