Large-scale multi-period precedence constrained knapsack problem: A mining application

Eduardo Moreno; Daniel Espinoza; Marcos Goycoolea

doi:10.1016/j.endm.2010.05.052

Large-scale multi-period precedence constrained knapsack problem: A mining application

Eduardo Moreno
, Daniel Espinoza
, Marcos Goycoolea

Producción científica: Contribución a una revista › Artículo › revisión exhaustiva

37 Citas (Scopus)

Resumen

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.

Idioma original	Inglés
Páginas (desde-hasta)	407-414
Número de páginas	8
Publicación	Electronic Notes in Discrete Mathematics
Volumen	36
N.º	C
DOI	https://doi.org/10.1016/j.endm.2010.05.052
Estado	Publicada - ago 2010

Acceder al documento

10.1016/j.endm.2010.05.052

Citar esto

@article{9142ae46ddd84d6d8894a8a22d6aeb3a,

title = "Large-scale multi-period precedence constrained knapsack problem: A mining application",

abstract = "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.",

keywords = "Integer Programming, Open-pit Mining, Precedence Constrained Knapsack Problem",

author = "Eduardo Moreno and Daniel Espinoza and Marcos Goycoolea",

year = "2010",

month = aug,

doi = "10.1016/j.endm.2010.05.052",

language = "English",

volume = "36",

pages = "407--414",

journal = "Electronic Notes in Discrete Mathematics",

issn = "1571-0653",

publisher = "Elsevier BV",

number = "C",

}

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 - https://www.scopus.com/pages/publications/77954947518

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 -

Large-scale multi-period precedence constrained knapsack problem: A mining application

Resumen

Acceder al documento

Huella

Citar esto