90C11 Mixed integer programming
Refine
Document Type
- Master's Thesis (3) (remove)
Language
- English (3)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
Institute
Generic Branch-Cut-and-Price
(2010)
Since the initial application of mathematical optimisation methods to mine planning in 1965, the Lerchs-Grossmann algorithm for computing the ultimate pit limit, operations researchers have worked on a variety of challenging problems in the area of open pit mining. This thesis focuses on the open pit mining production scheduling problem: Given the discretisation of an orebody as a block model, determine the sequence in which the blocks should be removed from the pit, over the lifespan of the mine, such that the net present value of the mining operation is maximised. In practise, when some material has been removed from the pit, it must be processed further in order to extract the valuable elements contained therein. If the concentration of valuable elements is not sufficiently high, the material is discarded as waste or stockpiled. Realistically-sized block models can contain hundreds of thousands of blocks. A common approach to render these problem instances computationally tractable is the aggregation of blocks to larger scheduling units. The thrust of this thesis is the investigation of a new mixed-integer programming formulation for the open pit mining production scheduling problem, which allows for processing decisions to be made at block level, while the actual mining schedule is still computed at aggregate level. A drawback of this model in its full form is the large number of additional variables needed to model the processing decisions. One main result of this thesis shows how these processing variables can be aggregated efficiently to reduce the problem size significantly, while practically incurring no loss in net present value. The second focus is on the application of lagrangean relaxation to the resource constraints. Using a result of Möhring et al. (2003) for project scheduling, the lagrangean relaxation can be solved efficiently via minimum cut computations in a weighted digraph. Experiments with a bundle algorithm implementation by Helmberg showed how the lagrangean dual can be solved within a small fraction of the time required by standard linear programming algorithms, while yielding practically the same dual bound. Finally, several problem-specific heuristics are presented together with computational results: two greedy sub-MIP start heuristics and a large neighbourhood search heuristic. A combination of a lagrangean-based start heuristic followed by a large neighbourhood search proved to be effective in generating solutions with objective values within a 0.05% gap of the optimum.
A lot of problems arising in Combinatorial Optimization and Operations Research can be formulated as Mixed Integer Programs (MIP). Although MIP-solving is an NP-hard optimization problem, many practically relevant instances can be solved in reasonable time. In modern MIP-solvers like the branch-cut-and-price-framework SCIP, primal heuristics play a major role in finding and improving feasible solutions at the early steps of the solution process. This helps to reduce the overall computational effort, guides the remaining search process, and proves the feasibility of the MIP model. Furthermore, a heuristic solution with a small gap to optimality often is sufficient in practice. We investigate 16 different heuristics, all of which are available in SCIP. Four of them arise from the literature of the last decade, nine are specific implementations of general heuristic ideas, three have been newly developed. We present an improved version of the feasibility pump heuristic by Fischetti et al., which in experiments produced solutions with only a third of the optimality gap compared to the original version. Furthermore, we introduce two new Large Neighborhood Search (LNS) heuristics. Crossover is an LNS improvement heuristic making use of similarities of diverse MIP solutions to generate new incumbent solutions. RENS is an LNS rounding heuristic which evaluates the space of all possible roundings of a fractional LP-solution. This heuristic makes it possible to determine whether a point can be rounded to an integer solution and which is the best possible rounding. We conclude with a computational comparison of all described heuristics. It points out that a single heuristic on its own has only a slight impact on the overall performance of SCIP, but the combination of all of them reduces the running time by a factor of two compared to a version without any heuristics.