Mark Zuckerberg
I completed my PhD in 2004 on "A Set Theoretic Approach to Lifting Procedures for 0,1 Integer Programming" under the advisorship of Professor Daniel Bienstock. We showed that the traditional lifting approaches of Balas, of Sherali and Adams, and of Lovasz and Schrijver could all be reinterpreted in a unified measure theoretic perspective within which their results all arise naturally. We showed that this broader perspective implies a more comprehensive type of lifting operator to which we referred as "subset algebra lifting", and we used this new lifting to derive algorithms for set covering problems.
After completing my doctoral work I took a position as a Senior Scientist with the Technology division of BHP Billiton, a global natural resources company headquartered in Melbourne, Australia. I work there as part of the resource extraction optimization R&D group. Our group has undergone some evolution in the intervening years and it now sits within the Resource and Business Optimization division of BHP Billiton, and my current title is Principal Scientist.
The primary purpose of our group is to provide optimization services to other parts of the company, principally by writing software that can be used by planners to design optimal "plans". We employ a software developer who designs, writes and maintains the user interface. Aside from this role there are four main aspects to our work. Firstly we meet regularly with our clients in order to understand their problem and to ensure that the development is suitable to their needs. Secondly we need to design a suitable mathematical model. Thirdly we need a solution methodology, and finally we need to implement it. These last two steps, i.e. designing and implementing the solution method, constitute the research component, and this is where most of my work has been focused.
There are a number of optimization problems that our group has worked on, but for the past few years our main focus has been the problem of how to optimally schedule the extraction and processing of the ore in an open pit mine over the life of the mine. The principal structural constraint in such problems is the fact that you cannot access a unit of material before you have extracted the material that is above it. We would like to be able to access the most valuable parts of the mine as soon as possible, as this maximizes present value, but the valuable ore is typically dispersed over a large location and at varying depths, and the choice of schedule thus has a major bearing on the present value of the mine. Moreover, for the ore to be useful in further processing (e.g. for iron ore to be useful in steel making) it often must fit a particular profile. For example iron ore must have an iron content above a certain percentage and silica, alumina and phosphorous contents below a certain percentage. This requires the schedule to be intelligent in its choice of what to extract and how to process in each scheduling period so that the aggregate product will satisfy this profile.
These problems are modelled most naturally as mixed integer programs, but considering that typical mines can have hundreds of thousands to millions of scheduling units, these problems are too big to be solved with commercial solvers. In the past we relied on aggregation of scheduling units to approximately model the problem in a form that is amenable to commercial solvers. We maintain however a research collaboration with Columbia University, and in the course of our research Dan Bienstock and I discovered certain mathematical structures in these problems that can be exploited algorithmically. This led to the development of a new linear programming algorithm and new integer programming algorithms that take advantage of these structures. These algorithms have made it possible to solve problems with millions of variables and tens of millions of constraints. This research carries the potential to be useful in other areas as well and we are still pursuing it.