p17 | Open-Pit Mine Production Scheduling

See also

This problem is sourced from Ferchtandiker2025.

Note

• The efficient formulation p17.a is a linear relaxation of the inefficient formulation p17.b. Hence, it is not a valid reformulation of p17.b by our constructive definition. We include it in the FormulationBench dataset as a negative reformulation example.

Description

Optimizing Long-Term Open-Pit Mine Production Scheduling

Open-pit mining operations require strategic long-term production schedules to maximize profitability while adhering to physical, operational, and economic constraints. A key challenge is determining when to mine each block of material (ore or waste) to maximize the Net Present Value (NPV) of the project, considering factors like ore grades, processing capacities, mining precedences, and time-discounted cash flows.

Core Challenge The mine is divided into thousands of blocks, each with specific attributes:

Ore/waste tonnage: Ore blocks contain valuable minerals (e.g., gold, copper), while waste blocks must be removed to access ore.

Grade: The concentration of valuable minerals in ore blocks.

Economic value: Calculated as revenue from mineral sales minus mining/processing costs, discounted over time. Roughly 20% of blocks are completely made up of ore. The remaining blocks contain a fraction of ore. When not accounting for discounting, the value of a block is propostional to the percentage of ore contained in it.

The goal is to sequence block extraction over multiple periods (years) to:

Maximize NPV: Prioritize high-value blocks for early extraction to account for the time value of money.

Meet processing demands: Ensure ore production stays within mill capacity limits each period.

Respect slope stability: Blocks cannot be mined until overlying layers are removed to prevent pit collapses.

Blend ore grades: Maintain average ore grades within acceptable bounds to optimize processing efficiency.

Formulations

Formulation a (valid)

See also

This formulation is sourced from Ferchtandiker2025 (formulation id: efficient).

Note

• We add all listed implicit assumptions.

Parameters

Name	Description	Type	Shape
n	Number of blocks	integer	scalar
t	Number of scheduling periods	integer	scalar
c	Net Present Value (NPV) of mining block i in period tau	continuous	[n, t]
g	Ore grade of each block	continuous	[n]
O	Ore tonnage of each block	continuous	[n]
W	Waste tonnage of each block	continuous	[n]
G_min	Minimum allowed average ore grade in any period	continuous	scalar
G_max	Maximum allowed average ore grade in any period	continuous	scalar
PC_min	Minimum per-period ore processing capacity	continuous	scalar
PC_max	Maximum per-period ore processing capacity	continuous	scalar
MC_min	Minimum per-period total mining capacity (ore + waste)	continuous	scalar
MC_max	Maximum per-period total mining capacity (ore + waste)	continuous	scalar
P	Precedence matrix: P[i][j] = 1 if block i must be mined before block j	binary	[n, n]

Definitions

Name	Description	Formulation
I0	Set of block indices with grade strictly less than 1 (mixed/low-grade blocks that remain binary)	\(I_0 = \{ i \in I : g_i < 1 \}\)
I1	Set of block indices with grade equal to 1 (pure-ore blocks relaxed to continuous [0,1])	\(I_1 = \{ i \in I : g_i = 1 \}\)

Variables

Name	Description	Type	Shape / Indices
x	Extraction variable: binary for mixed/low-grade blocks (I0), continuous fraction in [0,1] for pure-ore blocks (I1)	continuous	[n, t]

Assumptions

Description	Formulation	Implicit
Number of blocks is positive.	\(n \geq 1\)	yes
Number of scheduling periods is positive.	\(t \geq 1\)	yes
NPV of each block in each period is non-negative.	\(c_i^\tau \geq 0 \quad \forall i \in I,\; \tau \in T\)	yes
Ore grade of each block is non-negative.	\(g_i \geq 0 \quad \forall i \in I\)	yes
Ore tonnage of each block is non-negative.	\(O_i \geq 0 \quad \forall i \in I\)	yes
Waste tonnage of each block is non-negative.	\(W_i \geq 0 \quad \forall i \in I\)	yes

Constraints

• Binary integrality for mixed/low-grade blocks.

  \[ x_i^\tau \in \{0,1\} \quad \forall i \in I_0,\; \forall \tau \in T \]

• Upper grade blending constraint: weighted average ore grade does not exceed G_max in each period.

  \[ \sum_{i \in I} (g_i - G_{\max}) O_i x_i^\tau \leq 0 \quad \forall \tau \in T \]

• Lower grade blending constraint: weighted average ore grade is at least G_min in each period.

  \[ \sum_{i \in I} (g_i - G_{\min}) O_i x_i^\tau \geq 0 \quad \forall \tau \in T \]

• Each block is mined at most once over the entire planning horizon.

  \[ \sum_{\tau \in T} x_i^\tau \leq 1 \quad \forall i \in I \]

• Ore processing capacity upper bound per period.

  \[ \sum_{i \in I} O_i x_i^\tau \leq PC_{\max} \quad \forall \tau \in T \]

• Ore processing capacity lower bound per period.

  \[ \sum_{i \in I} O_i x_i^\tau \geq PC_{\min} \quad \forall \tau \in T \]

• Total mining capacity (ore + waste) upper bound per period.

  \[ \sum_{i \in I} (O_i + W_i) x_i^\tau \leq MC_{\max} \quad \forall \tau \in T \]

• Total mining capacity (ore + waste) lower bound per period.

  \[ \sum_{i \in I} (O_i + W_i) x_i^\tau \geq MC_{\min} \quad \forall \tau \in T \]

• Precedence constraint: block j may be mined in period tau only after all required predecessors i (P[i][j]=1) have been fully mined by period tau.

  \[ \sum_{\tau'=1}^{\tau} x_i^{\tau'} \geq x_j^\tau \quad \forall \tau \in T,\; \forall i,j \in I \text{ with } P_{ij}=1 \]

Objective

Maximize total discounted Net Present Value (NPV) across all blocks and periods.

\[ \max \sum_{\tau \in T} \sum_{i \in I} c_i^\tau x_i^\tau \]

Formulation b (invalid)

See also

This formulation is sourced from Ferchtandiker2025 (formulation id: inefficient).

Note

• We add all listed implicit assumptions.

Parameters

Name	Description	Type	Shape
n	Number of blocks	integer	scalar
t	Number of scheduling periods	integer	scalar
c	Net Present Value (NPV) of mining block i in period tau	continuous	[n, t]
g	Ore grade of each block	continuous	[n]
O	Ore tonnage of each block	continuous	[n]
W	Waste tonnage of each block	continuous	[n]
G_min	Minimum allowed average ore grade in any period	continuous	scalar
G_max	Maximum allowed average ore grade in any period	continuous	scalar
PC_min	Minimum per-period ore processing capacity	continuous	scalar
PC_max	Maximum per-period ore processing capacity	continuous	scalar
MC_min	Minimum per-period total mining capacity (ore + waste)	continuous	scalar
MC_max	Maximum per-period total mining capacity (ore + waste)	continuous	scalar
P	Precedence matrix: P[i][j] = 1 if block i must be mined before block j	binary	[n, n]

Variables

Name	Description	Type	Shape / Indices
x	Binary indicator: 1 if block i is mined in period tau, 0 otherwise	binary	[n, t]

Assumptions

Description	Formulation	Implicit
Number of blocks is positive.	\(n \geq 1\)	yes
Number of scheduling periods is positive.	\(t \geq 1\)	yes
NPV of each block in each period is non-negative.	\(c_i^\tau \geq 0 \quad \forall i \in I,\; \tau \in T\)	yes
Ore grade of each block is non-negative.	\(g_i \geq 0 \quad \forall i \in I\)	yes
Ore tonnage of each block is non-negative.	\(O_i \geq 0 \quad \forall i \in I\)	yes
Waste tonnage of each block is non-negative.	\(W_i \geq 0 \quad \forall i \in I\)	yes
Minimum grade bound does not exceed maximum grade bound.	\(G_{\min} \leq G_{\max}\)	yes
Minimum processing capacity does not exceed maximum processing capacity.	\(PC_{\min} \leq PC_{\max}\)	yes
Minimum mining capacity does not exceed maximum mining capacity.	\(MC_{\min} \leq MC_{\max}\)	yes

Constraints

• Upper grade blending constraint: weighted average ore grade does not exceed G_max in each period.

  \[ \sum_{i \in I} (g_i - G_{\max}) O_i x_i^\tau \leq 0 \quad \forall \tau \in T \]

• Lower grade blending constraint: weighted average ore grade is at least G_min in each period.

  \[ \sum_{i \in I} (g_i - G_{\min}) O_i x_i^\tau \geq 0 \quad \forall \tau \in T \]

• Each block is mined at most once over the entire planning horizon.

  \[ \sum_{\tau \in T} x_i^\tau \leq 1 \quad \forall i \in I \]

• Ore processing capacity upper bound per period.

  \[ \sum_{i \in I} O_i x_i^\tau \leq PC_{\max} \quad \forall \tau \in T \]

• Ore processing capacity lower bound per period.

  \[ \sum_{i \in I} O_i x_i^\tau \geq PC_{\min} \quad \forall \tau \in T \]

• Total mining capacity (ore + waste) upper bound per period.

  \[ \sum_{i \in I} (O_i + W_i) x_i^\tau \leq MC_{\max} \quad \forall \tau \in T \]

• Total mining capacity (ore + waste) lower bound per period.

  \[ \sum_{i \in I} (O_i + W_i) x_i^\tau \geq MC_{\min} \quad \forall \tau \in T \]

• Precedence constraint: block j may be mined in period tau only after all required predecessors i (P[i][j]=1) have been mined by period tau.

  \[ \sum_{\tau'=1}^{\tau} x_i^{\tau'} \geq x_j^\tau \quad \forall \tau \in T,\; \forall i,j \in I \text{ with } P_{ij}=1 \]

Objective

Maximize total discounted Net Present Value (NPV) across all blocks and periods.

\[ \max \sum_{\tau \in T} \sum_{i \in I} c_i^\tau x_i^\tau \]