FIT5216: Modelling Discrete Optimization Problems

Assignment 1: Mine Planning

1 Overview

For this assignment, your task is to write a MiniZinc model for a given problem specification.

• Submit your work to the MiniZinc auto grading system (using the submit button in the MiniZinc IDE).

• Submit your model (copy and paste the contents of the .mzn file) using the Moodle assignment.

You have to submit by the due date (Friday 28th March 2025, 11:55pm), using MiniZinc, to receive full marks. You can submit as often as you want before the due date. Late submissions without special consideration receive a penalty of 10% of the available marks per day. Submissions are not accepted more than 7 days after the original deadline.

This is an individual assignment. Your submission has to be entirely your own work. We will use similarity detection software to detect any attempt at collusion, and the penalties are quite harsh. Similarly you may not use generative AI during this assignment. If in doubt, contact your teaching team with any questions!

2 Problem Statement

Your task is to plan an underground mine, in order to mine valuable minerals. The area for mining is a rectangle of cells, the east west dimension has eastwest cells, and the north south dimension has northsouth cells. The mine must start at one of the given start positions, and build a tunnel from there. The tunnel has no branches as that is not supported by the mining machinery. Each cell has a cost to bore a tunnel there, and an associated amount of ore. A negative cost means that your tunnel cannot go through that cell.

For task (a) you are planning a mine tunnel with a given fixed length. For task (b) you are planning a mine tunnel with a given maximum length. Each cell of the tunnel must be orthogonally adjacent (above, below, left or right) to the previous cell, so the tunnel cannot have “branches”.

You have a given budget, which is the maximum cost you can spend. The total cost to build is the cost of all the cells that are tunneled, plus the cost of reinforcement for any negative cost cells that are adjacent to the tunnel (equal to the negative of their cost value). A negative cost in an orthogonally adjacent cell means that the ground is unstable, and instead of mining minerals, you have to reinforce the adjacent tunnel.

The company will mine the minerals inside the tunnel itself, and those in the orthogonally adjacent cells. So the total ore mined is equal to all the ore values in the tunnel and orthogonally adjacent cells.

The goal is to find the most profitable mine plan. The profit is the sum of the ore mined minus the sum of the mining cost.

Input data is given in MiniZinc data format:

eastwest = ⟨ east west dimension ⟩;

northsouht = ⟨ north south dimension ⟩;

cost = ⟨ 2D northsouth × eastwest array of costs ⟩;

re = ⟨ 2D northsouth × eastwest array of ore ⟩;

length = ⟨ length (limit) ⟩;

budget = ⟨ build budget ⟩;

Here is a sample data set:

eastwest = 9;

northsouth = 5;

cost = [| 1, 1, 1, 1, 1, 1, 1, 1,-3

| 1, 1, 1, 1, 1, 1, 1, 1, 1

| 1, 1, 1, 1, 1, 1,-4, 1, 1

| 1, 1, 1,-2, 1, 1, 1, 1, 1

| 1, 1, 1, 1, 1, 1, 1, 1, 1 |];

reward = [| 4, 0, 0, 0, 0, 0, 0, 0, 0

| 0, 6, 0, 0, 2, 0, 0, 4, 0

| 0, 0, 0, 0, 0, 0, 0, 0, 0

| 0, 0, 4, 0, 0, 0, 0, 0, 2

| 0, 0, 0, 0, 4, 0, 0, 2, 6

|];

length = 12;

budget = 18;

start = [(1,1),(9,5)];

On this 9x5 grid, the cost for each position is 1 except at positions (9,1), (7,3) and (4,4) which have negative costs and cannot be mined. The reward data is given by

and the length (limit) is 12 and the budget 18. Note that in general the costs may be different for each cell. We can start the mine at either the top left (1,1) or bottom right (9,5) corner.

Part A - Fixed Length Tunnel

Create a model mineplan.mzn that takes data in the format specified above and decides on a tunnel of length equal to the value length given in the data.

Here is a sample solution (which is not optimal but satisfies the constraints). The tunnel is represented in light blue, the additionally mined areas in light gray. Non-zero ore values and negative costs are shown.

Note that the tunnel has length 12, as required. It does not pass through any of the cells with a negative cost (the red cells). The total ore mined is the sum of the light blue cells (4), plus the light gray adjacent cells (sum=16) which adds up to 20. The total cost is 12 for tunneling plus the reinforcement cost for the two negative cost adjacent cells of 6 for a total of 18, under the budget. The overall profit is 2.

Your model must define the positions of the tunnel cells as x and y coordinates, together with the total profit. One correct output for the solution above is

x = [1, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6];

y = [1, 1, 1, 2, 3, 3, 3, 4, 4, 3, 2, 1];

profit = 2;

Note how each position e.g. (3,1) is adjacent to the next one (3,2). There are many other correct solutions.

In order to compute the cost and ore mined, you may want to decide for each cell whether it is on the tunnel path or adjacent to it. Once you have that information, it is easy to add up all the costs and rewards.

Note that you will not be able to obtain full marks by just answering part A. Some problems will have no solution, whereas using part B they have a solution.

Part B - Bounded Length Tunnel

Modify your model mineplan.mzn to treat length as a bound on the maximal possible length of the tunnel. For example a sample solution for the example data is illustrated as

The tunnel has length 8, with cost 8 + 2 = 10 within the budget of 18. It only directly covers (light blue) the start point with a reward of 4, and has adjacent rewards (light gray) of 16. The total ore is therefore 18, for a total profit of 10.

To model this extension, unused tunnel cells must be defined as having x and y coordinate 0. All the unused positions must occur at the end of the x and y lists. So a correct output for this solution is:

x = [1, 1, 1, 2, 3, 4, 5, 5, 0, 0, 0, 0];

y = [1, 2, 3, 3, 3, 3, 3, 4, 0, 0, 0, 0];

profit = 10;

3 Instructions

Edit the provided mzn model files to solve the problems described above. You are provided with some sample data files to try your model on. Your implementations can be tested locally by using the Run+check icon in the MiniZinc IDE. Note that the checker for this assignment will only test whether your model produces output in the required format, it does not check whether your solutions are correct. The checker on the server will give you feedback on the correctness of your submitted solutions and models.

4 Marking

The marks are automatically calculated.

• For most instances you can get a maximum of 0.75 for part A and 1 (full marks) for part B.

• For some instances you can get full marks with part A.

• For some instances you will always get 0 with part A.

The submission has 10 marks for locally tested data and 12 for model testing, for a total of 22 marks.