An efficient algorithm for the precedence constraint knapsack problem with reference to large-scale open-pit mining pushback design. Issue 1 (2nd January 2021)

• Record Type: Journal Article
• Authors: Maiti, Nayan; Pathak, Pranjal; Samanta, Biswajit
• Is Part Of: Mining technology. Volume 130:Issue 1(2021)
• Page Start: 8
• Page End: 21
• Publication Date: 2021-01-02
• Subjects: Large-scale optimization -- precedence constrained knapsack problem -- open-pit production scheduling -- parametric maximum flow; Mining engineering -- Periodicals; Mineral industries -- Periodicals; 662.05; 622.05
• DOI: 10.1080/25726668.2020.1866369
• Languages: English
• ISSNs: 2572-6668

Abstract

ABSTRACT: In this paper, a new Specific Breakpoint Algorithm (SBA), which can efficiently search appropriate breakpoints of parametric maximum-flow-related problems, is presented. The algorithm is used to solve Lagrangian Relaxed Precedence Constrained Knapsack Problem (LRPCKP) and Linear Programming Relaxed Precedence Constrained Knapsack Problem (LPRPCKP) in mine pushback design. The relaxed solutions are then processed through Rounded Topo-Sort (RoTS) heuristic to produce feasible solutions. The study results on seven bench mark datasets on Minelib for two approaches, referred here as LRPCKP-SBA and LPRPCKP-SBA, indicate that LRPCKP-SBA in spite of being faster, produces inferior quality solutions than well known BZ and CPLEX solutions. However, LPRPCKP-SBA produces a comparable quality of solutions as BZ in a computationally more efficient manner. Furthermore, the RoTS heuristics operated on relaxed solutions produce a better quality of feasible solutions than an existing technique, Expected Topo-Sort heuristic (ExTS).