TY - JOUR
T1 - Large-scale multi-period precedence constrained knapsack problem
T2 - A mining application
AU - Moreno, Eduardo
AU - Espinoza, Daniel
AU - Goycoolea, Marcos
PY - 2010/8
Y1 - 2010/8
N2 - We study an extension of the precedence constrained knapsack problem where the knapsack can be filled in multiple periods. This problem is known in the mining industry as the open-pit mine production scheduling problem. We present a new algorithm for solving the LP relaxation of this problem and an LP-based heuristic to obtain feasible solutions. Computational experiments show that we can solve real mining instances with millions of items in minutes, obtaining solutions within 6% of optimality.
AB - We study an extension of the precedence constrained knapsack problem where the knapsack can be filled in multiple periods. This problem is known in the mining industry as the open-pit mine production scheduling problem. We present a new algorithm for solving the LP relaxation of this problem and an LP-based heuristic to obtain feasible solutions. Computational experiments show that we can solve real mining instances with millions of items in minutes, obtaining solutions within 6% of optimality.
KW - Integer Programming
KW - Open-pit Mining
KW - Precedence Constrained Knapsack Problem
UR - http://www.scopus.com/inward/record.url?scp=77954947518&partnerID=8YFLogxK
U2 - 10.1016/j.endm.2010.05.052
DO - 10.1016/j.endm.2010.05.052
M3 - Article
AN - SCOPUS:77954947518
SN - 1571-0653
VL - 36
SP - 407
EP - 414
JO - Electronic Notes in Discrete Mathematics
JF - Electronic Notes in Discrete Mathematics
IS - C
ER -