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

Eduardo Moreno, Daniel Espinoza, Marcos Goycoolea

Research output: Contribution to journalArticlepeer-review

35 Scopus citations

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.

Original languageEnglish
Pages (from-to)407-414
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Volume36
Issue numberC
DOIs
StatePublished - Aug 2010

Keywords

  • Integer Programming
  • Open-pit Mining
  • Precedence Constrained Knapsack Problem

Fingerprint

Dive into the research topics of 'Large-scale multi-period precedence constrained knapsack problem: A mining application'. Together they form a unique fingerprint.

Cite this