MineLib: a library of open pit mining problems

Abstract

Similar to the mixed-integer programming library (MIPLIB), we present a library of publicly available test problem instances for three classical types of open pit mining problems: the ultimate pit limit problem and two variants of open pit production scheduling problems. The ultimate pit limit problem determines a set of notional three-dimensional blocks containing ore and/or waste material to extract to maximize value subject to geospatial precedence constraints. Open pit production scheduling problems seek to determine when, if ever, a block is extracted from an open pit mine. A typical objective is to maximize the net present value of the extracted ore; constraints include precedence and upper bounds on operational resource usage. Extensions of this problem can include (i) lower bounds on operational resource usage, (ii) the determination of whether a block is sent to a waste dump, i.e., discarded, or to a processing plant, i.e., to a facility that derives salable mineral from the block, (iii) average grade constraints at the processing plant, and (iv) inventories of extracted but unprocessed material. Although open pit mining problems have appeared in academic literature dating back to the 1960s, no standard representations exist, and there are no commonly available corresponding data sets. We describe some representative open pit mining problems, briefly mention related literature, and provide a library consisting of mathematical models and sets of instances, available on the Internet. We conclude with directions for use of this newly established mining library. The library serves not only as a suggestion of standard expressions of and available data for open pit mining problems, but also as encouragement for the development of increasingly sophisticated algorithms.

Appendix A: File format specifications

1.1 A.1 General assumptions

All files are ASCII, and lines beginning with the character ‘%’ are assumed to be comments. Each line contains fields delimited (separated) by a space, a horizontal tabular character, or a colon character (ASCII codes 32, 9 and 58, respectively). All separators at the beginning of a line are discarded. Multiple contiguous separators are treated as a single separator.

All entries are of the form <keyword> : <parameter_type>, or simply, a sequence of <parameter_type> definitions. <keyword> is an alphanumerical name used to identify certain entries, and <parameter_type> defines a variable or data of a certain type. The types <str>, <int>, <char> and <dbl> correspond to a string (not containing a separator), an integer, a character, or a double type, as in C and other popular programming languages. We assume that all entries are given in the order specified in this document.

We introduce a flexible format, because this is the way in which many practitioners transfer information about block models at the time of this writing. By maintaining the status quo, we hope that the mining community will contribute to and use the library. Additionally, in practice, not all mines use the same information. For example, in some mines, the blocks have information on three different concentrations of minerals; some information might pertain to contaminants, while other information might pertain to sub-products. Having that information is essential to compute correct values for the block depending on the processing technology used.

1.2 A.2 The block-model descriptor file

The Block-Model Descriptor File stores model information at a block-by-block level. Each line in the file corresponds to a block in the model. All lines have the same number of columns. These columns are organized as follows:

<int id> <int x> <int y> <int z> <str ₁> ⋯ <str _k >

Each row contains the following information about a block:

• id stores a unique identifier for the block, where the block identifiers are numbered, starting with zero.

• x, y, z represent the coordinates of the block, where a zero z-coordinate corresponds to the bottom-most shelf in the orebody and the z-axis points in the upwards direction. The y-axis points directly towards the viewer while the x-axis points to the left of the viewer.

• str ₁,…,str _k represent optional user-specified fields that may represent, e.g., tonnage, ore grade, or information about impurities. These values can be of any pure type declared before and must comply with our delimiter rules for parsing. This flexibility is allowed to match the usual formats used in the industry.

1.3 A.3 The block-precedence descriptor file

The Block-Precedence Descriptor File articulates precedence relationships between blocks in the model. Information is represented at a block-by-block level. Each line in the file corresponds to a block in the model and its corresponding set of predecessors. Precedence relationships are described as follows:

<int b> <int n> <int p ₁> ⋯ <int p _n >

Each row gives the following precedence information:

• b stores the unique identifier of a block.

• n stores the number of predecessors specified for block b.

• p ₁,…,p _n store the identifiers of the n predecessors of block b.

In general, we assume that p ₁,…,p _n are immediate predecessors of block b, but this is not a strict requirement. We assume that no two entries in the file can begin with the same identifier. If a block b has no predecessors, then the corresponding value n is set to 0 and no values p _i are specified in the line.

1.4 A.4 Optimization-model descriptor file

The Optimization-Model Descriptor File is used to store the necessary information to formulate $\mathit{(UPIT)}$, $\mathit{(CPIT)}$, and $\mathit{(PCPSP)}$.

1.4.1 A.4.1 The file format

NAME: <str s>

Identifies the data file.

TYPE: <str s>

Specifies the problem type. The value of s must be $\mathit{(}UPIT)$, $\mathit{(}CPIT)$, or $\mathit{(}PCPSP)$.

NBLOCKS: <int n>

Gives the number of blocks in the problem.

NPERIODS: <int t _max >

Identifies the number of time periods for the problem; this field is valid for formulating problems of type $\mathit{(CPIT)}$ and $\mathit{(PCPSP)}$.

NDESTINATIONS: <int d _max >

Specifies the number of possible processing alternatives for each block; this field is valid for formulating problems of type $\mathit{(PCPSP)}$.

NRESOURCE_SIDE_CONSTRAINTS: <int r _max >

Identifies the number of operational resource constraints per time period; this field is valid for problems of type $\mathit{(CPIT)}$ and $\mathit{(PCPSP)}$.

NGENERAL_SIDE_CONSTRAINTS: <int m>

Identifies the number of general side-constraints for the problem, or equivalently, the number of rows in matrix A. This field is valid for problems of type $\mathit{(PCPSP)}$.

DISCOUNT_RATE: <dbl α>

This specifies the discount rate used in computing the objective function. That is, $\hat{p}_{bt} = \frac {p_{b}}{(1+\alpha)^{t}}$ and $\tilde{p}_{bdt} = \frac{p_{bd}}{(1+\alpha)^{t}}$, where p _b and p _bd are quantities defined subsequently in the file.

OBJECTIVE_FUNCTION

The objective function is given by one row for each block. Thus, this section has NBLOCKS lines. If the problem-type is either $\mathit{(UPIT)}$ or $\mathit{(CPIT)}$, the number of destinations is assumed to be one, i.e., NDESTINATIONS = 1. In this case, p _b =p _b1. Each line is of the form:

<int b> <dbl p _b1> ⋯ <dbl $p_{bd_{max}}$>

That is, the first value (b) defines the block, and the next d _max values describe the objective function values associated with each destination. No two lines can begin with the same identifier.

RESOURCE_CONSTRAINT_COEFFICIENTS

Here, we define the coefficients q _br and $\hat{q}_{brd}$, corresponding to constraints (5) and (10) in $\mathit{(CPIT)}$ and $\mathit{(PCPSP)}$. This entry consists of n lines, where n is at most the total number of non-zero coefficients in the aforementioned constraints. Specifically, each of these lines has the form:

<int b> <int r> <dbl v>

or

<int b> <int d> <int r> <dbl v>

The values of b, d, and r indicate the block, the destination, and the operational resource, respectively. The value of v represents the coefficient q _br or $\hat{q}_{brd}$. All coefficients that are not defined in this way have value zero.

RESOURCE_CONSTRAINT_LIMITS

Here, we define the limits $\underline{R}_{rt}$ and $\bar{R}_{rt}$ corresponding to constraints (5) and (10) in $\mathit{(CPIT)}$ and $\mathit{(PCPSP)}$, respectively. This entry consists of NRESOURCE_CONSTRAINTS lines, each having the form:

<int r> <int t> <char c> <dbl v ₁>

or

<int r> <int t> <char c> <dbl v ₁> <dbl v ₂>

The value of r indicates the operational resource and the value of t indicates the time period in which the operational resource constraint holds. The value of c can be L (less-than-or-equal-to), G (greater-than-or-equal-to) or I (within an interval). If c has value L, then $\underline{R}_{rt} = -\infty$ and $\bar {R}_{rt}$ is equal to the value of v ₁. In this case, v ₂ is not defined. If c has value G, then $\bar{R}_{rt} = \infty$ and the value of $\underline{R}_{rt}$ is equal to v ₁. In this case, v ₂ is not defined. If c has value I, then v ₁ has value $\underline{R}_{rt}$ and v ₂ has value $\bar{R}_{rt}$. No default value is assumed for these limits. Thus, if an operational resource constraint has no specific type and limits, the instance is not well defined.

GENERAL_CONSTRAINT_COEFFICIENTS

Here, we define the coefficients A _bdtj of matrix A, corresponding to constraints (11) in $\mathit{(PCPSP)}$, where b is a block identifier, d a destination identifier, t a time period, and j a number between 0 and m−1, where m is the number of rows in A. This entry consists of n lines, where n is at most the total number of non-zero coefficients in matrix A. Specifically, each of these lines has the form:

<int b> <int d> <int t> <int j> <dbl v>

The values of b, d, t, j, and v indicate the block, the destination, the time period, the row, and the coefficient A _bdrj in the matrix A, respectively. All coefficients that are not defined in this way have value zero.

GENERAL_CONSTRAINT_LIMITS

Here, we define the limits corresponding to constraints (11) in $\mathit{(PCPSP)}$. This entry consists of NGENERAL_SIDE_CONSTRAINTS lines, each having the form:

<int m> <char c> <dbl v ₁>

or

<int m> <char c> <dbl v ₁> <dbl v ₂>

The value of m indicates the row number of A. The value of c can be L, G or I. If c has value L, then $\underline{a}_{m} = -\infty$ and $\bar{a}_{m}$ is equal to the value of v ₁. In this case, v ₂ is not defined. If c has value G, then $\bar{a}_{m} = \infty$ and the value of $\underline{a}_{m}$ is equal to v ₁. In this case, v ₂ is not defined. If c has value I, then v ₁ has value $\underline{a}_{m}$ and v ₂ has value $\bar{a}_{m}$. No default value is assumed for these limits. Thus, if an operational resource constraint has no specific type and limits, the instance is not well defined.