RIGOROUS ALGORITHMS TO OPTIMISE STOPE BOUNDARIES; CAPABILITIES, RESTRICTIONS AND APPLICATIONS

. The capabilities, restrictions and applications of these algorithms are evaluated and compared. Key word: Underground Mining, Stope Boundaries, Optimisation, Rigorous Algorithms. INTRODUCTION There are a large number of algorithms and software developed for optimisation of open pit limits during the past decades. In contrast, a limited research has been carried out for underground cases. This is mainly because there are a variety of underground mining methods with various restrictions and conditions and the underground mining parameters are more complex. Generally, current algorithms for optimisation of ultimate limits in underground mines can be categorized in two groups; rigorous and heuristic algorithms. Rigorous, a term applied to algorithms which always find the optimum solution to the problem for the supplied data and constraints, if given sufficient time, and heuristic, a term applied to any technique which is not rigorous and finds only an approximate solution, regardless of being close to the true solution or not (Kim, 1978). The heuristic approaches include the “Floating Stope” technique of Datamine (Alford 1995) and the “Maximum Value Neighbourhood”(MVN) algorithm (Ataee- pour 1997). Both algorithms provide 3D analysis of the solution and can be applied to any underground mining methods. Nevertheless, not only they lack mathematical proof and fail to determine the true optimum but also apply on the entire mining area and do not give much details of the ultimate mining layout such as location of levels or panels. 2 Rigorous algorithms include the “Riddle's Dynamic Programming”(RDP) solution (Riddle 1977), the “Branch and Bound”(BB) technique (Ovanic and Young 1995) and the OLIPS (Optimized Layout by Integrated Probable Stope) algorithm (Jalali, 2006). All these algorithms are supported by mathematical reasoning. The Riddle solution provides a 2D analysis and has been adjusted for block caving method. The branch and bound technique provides a 1D solution to the problem and determines the start and end of a stope in one direction. The OLIPS algorithm provides a 2D analysis and enjoys complying with all underground mining methods used for tabular and vein type deposits. All these algorithms apply on an economic block model of the ore body. In addition to those mentioned above, there are two alternatives to the problem as well, including the “Octree Division” algorithm and the “Geostatistical Approach”. These approaches apply on geologic models and not the economic model. Their major disadvantage is the complexity associated with them and that they have limited applications (Ataee-pour, 2005). In this paper, the rigorous algorithms developed for optimization of stope layout are introduced. The capabilities, restrictions and applications of these algorithms are evaluated and compared. Rigorous Algorithms All existing Algorithms developed for optimization of stope boundaries Include Branch and Bound, Riddle’s DP and OLIPS algorithms enjoy mathematical proof. The Branch and Bound Technique The application of the BB technique to determine the stope layout was proposed to optimize the starting and ending locations for mining within each row of blocks (Ovanic and Young, 1995). Two piecewise linear cumulative functions were used for each row to determine these two locations. A mixed integer programming approach known as Type-Two Special Ordered Sets (SOS2) was applied for optimization of the stope boundary model. The BB algorithm is an attempt to corporate SOS2 into a mathematical model of the stope optimization. The outline of a stope can be determined through optimizing its starting and ending locations. Assume a row of blocks with their associated block positions and block net values (Fig. 1a). The objective is to find the optimum stope boundaries, which maximizes the block economic values. The horizontal coordinates of the blocks along the panel are strictly increasing and can be considered as the reference value in the piecewise linear function. It should be noted that the cumulative values of blocks have to be used. Discrete points are located on the beginning or ending points of the blocks. The number of the discrete points, therefore, equals the number of blocks plus one. A typical cumulative block value function is shown in Fig. 1b. Considering that mining proceeds from left to right and starts somewhere within the panel, two separate SOS2 sets are generated. The first set defines the leading boundary and is identified by the special variable Li, while the second one defines the trailing boundary and is identified by the special variable Ti. Then the objective function is defined as the difference between two cumulative functions corresponding to the leading and trailing boundaries:    n i ii n i ii TaLaSV 00 , (1) 3

Where, SV is the difference between cumulative values obtained for the leading and tailing boundaries (stope value); ai is the ith cumulative block economic value; Li is the ith leading special variable bounding between 0 and 1; Ti is the ith trailing special variable bounding between 0 and 1. Fig. 1: Cumulative block value function as to the block row. To apply SOS2, the mixed integer programming via the BB technique is used. The branching algorithm computes the sum of the special variables Li and Ti in the set multiplied by their reference values xi. The following branching step is set up considering two subsets. The first one refers to all variables from the beginning of the set up to the first variable whose reference is greater than the computed value. The second subset refers to variables from the end of the set down to the first variable whose reference is less than the computed value. The lower and upper bounds indicating the first and last number of the set that can be non-zero are established. The non-zero members are forced to be selected from the subset of interest. The branch and bound algorithm limits selection from a smaller and smaller subset until it forces an integer (discrete) solution. In the above example, assume that the stope is constrained to have a minimum length of 33.3 m. Applying the branch and bound algorithm described above, the optimum solution for the stope optimization is shown in Fig. 2. There are two special variables corresponding to the leading boundary L4 and L5, i.e. one third of block No. 5 is included into the stope. In addition there is only one special variable corresponding to the trailing boundary T3. They clearly satisfy all the conditions required for the SOS2 set. Therefore, the stope begins 75 m from the origin (x3.T3=75) and ends at the point 108.33 m (x4.L4+ x5.L5=108.33), and contains

33 block value units (Ovanic and Young, 1995). It is apparent that the BB algorithm removes some restrictions from mine layout design and, in particular, stope geometry optimization. There is no restriction for blocks to be treated as a whole, but rather partial blocks can be included in the optimal stope. Moreover, blocks are not limited to be regular or uniform in shape. Whatever their shape or size is does not influence the optimization since the block cumulative function is used in modeling. This is especially helpful when the geologic interpretations are overlaid on the block model. The blocks can be shaped following the geologic variations and discontinuities. The algorithm has been developed to optimize the stope Fig 2. Optimum solution for the stope optimization. 4 boundary along the panel of blocks in one dimension. It is not clear if any smoothing is required for adjacent panels in two and three dimensions. The algorithm works in special cases, where the geometry constraints can be reduced to the stope length. In addition the algorithm requires specialized mathematical optimization software. The Riddle's DP Algorithm Application of the DP technique to optimisation of the ultimate stope boundaries has only been reported for designing layout of block caving mines (Riddle, 1977). The initial algorithm was developed for optimising the ultimate open pit limits, assuming equal size blocks and a 1:1 allowable pit slope, and using the typical formulae of pit limit optimisation by DP approach:     }{ 1 1i+r,j-ijij qjij P+Max= MP ito qm=M (2) Where, mqj is the economic value of the block located in row q and column j, Mij is the cumulative economic value of a column of blocks from the surface to and including the block, Bij, R is the range of rows of blocks of the previous column that should be included in the neighbouring blocks to satisfy the maximum slope constraint and Pij is the maximum probable contribution of columns 1 to j to any feasible pit that contains the block, Bij, on its contour. However, in order to modify the algorithm to suit underground block-caving methods, the recursive formula was modified according to specific mining constraints imposed by block caving. There are basic differences between open pit and block caving constraints when applying the RDP technique. The open pit must be initiated from the surface in one- block steps. However, a block-caving mine may include a vertical boundary cut off, so that mining may begin at any elevation within a fringe stope. Besides, this entry point may vary horizontally (at any column), that is, mining does not necessarily start from the first drawpoint. Furthermore, the relation of height mined is constrained by draw control rather than pit slope. Additionally, boundary cut offs may be established at several locations across a section, under certain conditions, to leave areas void of values as pillars. Figure 3 illustrates the optimum layouts of the same section of a block model optimised by both open pit and block caving methods together with their profitability.

2 3 4 5 6 7 8 9 10

3 4 5 -1 -1 -4 1 2 10 1

1 3 3 -2 -1 -1 2 4 2 2

1 -1 6 -1 -2 -2 2 6 1 3

2 -2 1 -1 1 1 4 8 1 0

1 5 0 0 2 0 -1 1 0 -2 Column Open pit profit = 46

1 5 0 0 2 0 -1 1 0 -2

2 -2 1 -1 1 1 4 8 1 0

1 -1 6 -1 -2 -2 2 6 1 3

1 3 3 -2 -1 -1 2 4 2 2

3 4 5 -1 -1 -4 1 2 10 1

2 3 4 5 6 7 8 9 10 Drawpoint Block caving profit = 77 a- Optimum layouts of a section example using the open pit method b- Optimum layouts of a section example (upside down) using the block-caving method Fig. 3: Comparison between open pit and block caving. The RDP algorithm is a multi-section 2D solution for 3D problems. The method provides an optimum stope in 2D section. However, it fails to determine the true 5 optimum stope in three dimensions. Although the sections are optimised, when they are put together, they may violate the stope constraints. As a solution, Riddle suggested applying the algorithm once in north-south sections and next in east-west sections. Additionally, the algorithm is restricted to block caving mining method. A Fortran IV code was prepared for this algorithm and has been run over some assumed models. The OLIPS Algorithm The OLIPS algorithm is based on the Dynamic Programming technique, which is supported by mathematical proof. The algorithm is applied on a 2D conventional economic model. So, it is best suited for vein type or tabular deposits. In fact, characteristics of the ore body in the third dimension are projected on the model plane (Jalali and Ataee-pour, 2004). The OLIPS algorithm applies on a 2D conventional fixed economic block model that is called the primary model. Then through two stages, the Probable Stope model (PS) and the Integrated Probable Stope (IPS) model are derived from the primary model. The algorithm is then implemented on the IPS model. The primary model may be thought of as a 2D matrix, where each entry, my,x, represents the net economic value of a block located in the yth row and the xth column. The matrix has X rows representing the total number of blocks in the direction of orebody’s strike and Y columns representing the total number of blocks in the ore body’s dip direction. Figure 4 illustrates a simple example of such primary model. In the PS model the stope height constraint is considered. A probable stope in each column includes a set of adjacent blocks in the same column of the primary model which satisfy the minimum height of the stope. Consider that the stope height is restricted to a minimum of h blocks, the total number of probable stopes may be obtained through Equation 3: Xx1,hyNS Y hy hx    )1(, (3)

Where, NSx,h is the number of probable stopes with a minimum of h blocks located at the xth column, h is the minimum stope height measured in the number of blocks, x is the column number, X is total number of columns, y is the row number and Y is total number of rows. The location of each probable stope in each column, x, is defined as SL(f,c),x, where SL is the stope location and f and c which form a pair, represent the location of the floor and ceiling of the stope in column x. For example, if the stope contains three adjacent blocks from the first, second and third rows of column x (i.e. blocks with net economic values m1,x, m2,x and m3,x), then its location is addressed by SL(0,3),x. Figure 5 shows the location of each of the three probable stopes in column x for a model with four rows. The net economic value of each stope may be obtained through Equation 4: YcY-h, hfX, xmM c fy xyxcf     01For ,1),,( (4) Fig.4: An example of the primary model 6

Where, M(f,c),x is the net value of the stope located at SL(f,c),x and my,x is the net value of the block located at row y and column x of the primary model. Once the net value of probable stopes are calculated, the probable stope model may be constructed. The total number of columns in this model is the same as that of the primary model and its total number of rows is one more than the number of probable stopes in each column (i.e. NSx,h+1). Figure 6 shows the probable stope model of the example shown in Figure4, assuming a three block height restriction. The lowest row indicates the net value of stopes at the location SL(0,0),x, which are in fact virtual stopes with zero (block) height. In fact the model contains, in each row, the economic value of one probable stope (M(f,c),x). The IPS model is constructed by imposing the minimum stope length constraint. Each block of the IPS model contains the maximum economic value of the stope ending at that block, while satisfying the minimum length constraint. If the minimum stope length equals l blocks, l virtual columns are added to the left of the model to provide feasible stopes, otherwise none of the blocks located in the first l blocks of the model may form a stope with a minimum length of l blocks. The net value of all stopes, which are not entirely located inside the primary model (those with columns j=1 to j= l) is set to a very large negative value. Another restriction that must be considered is the maximum variation of the elevation of both the floor and the ceiling of the stope from one column to the next. Consider that SL(f,c),x represents the stope location at column x, then the stope location at column (x+1) may assume one of the SL(f+rf,c+rc),x-1 under the following conditions: h,,...,2,1,0andh ,,...,2,1,0 )()(,,0   ccff nnrcnnrf hrffrccYrccrff (5) Where, rf is an integer number representing the floor level variation constraint, rc is an integer number representing the ceiling level variation constraint, nf is maximum number of blocks of the floor level variation constraint and nc is maximum number of blocks of the ceiling level variation constraint. Imposing the level variation constraint, the maximum net value of stopes with the minimum allowed length may be calculated through the following relations: 0:0c0,f ),0,0(  jMSVif (6)          

l 1r 1rl-jrc),rf,c(f1l-j(f,c), ),,( 1 Mmax u - M:0c0,f JjlWhere lj M Where SVif jcf (7) m 4,x m 3,x m 2,x m 1,xS L ( 0 , 3 ) , x S L ( 1 , 4 ) , x S L ( 0 , 4 ) , x Three Probable Stopes 0 2 3 4 1 Fig. 5: Location of probable stopes in the xth column Fig. 6: The PS model 7

Where, MSV(f,c),j is the maximum economic value of the stope with minimum allowed length, ending to SL(f,c),j, u is a large positive number, l is the minimum stope length allowed, M(f,c),j is economic value of the stope at SL(f,c),j and r is a counter. In fact, each cell of the IPS model represents the maximum net value of a stope with the minimum length and ending to that cell. Figure 7 illustrates the IPS model corresponding to the model of Figure 4 (Jalali and Ataee-pour, 2004). The OLIPS is proposed to optimise the stope boundaries, which is run on the IPS model described above. A Dynamic Programming technique is employed using a recursive formula, similar to that used for open pit limit optimisation. However, the formula consists of two criteria. By applying the algorithm to each stope at a specified location, the economic value of all mining areas ending to that stope are calculated and the maximum one is specified for the IPS model. The recursive formula is as follows (Jalali and Ataee-pour, 2004):         JjlWhere ljWhere jrccrff j PP 1 max P, 0

j(0,0),1),,( ),0,0( (8)         JjWhere l ljWhere NSVPMSV,PP -u P (f,c),j(f,c),jl),j,(lrc),jrf,c(f jcf 00 ),,( max 1 (9)

Where, P(f,c),j is the maximum net value of the mining area ending to the stope located at SL(f,c),j, P(0,0),j is the maximum net value of the mining area ending to the stope located at SL(0,0),j and NSVP(f,c),j is new stope value parameter. The value of NSVP(f,c),j is calculated only at two circumstances. The first one is when the algorithm starts and there is no stope formed yet. The second one is when the limits of the stope is passed and a new stope is going to be formed. The value of NSVP(f,c),j is assigned zero, otherwise. Figure 8 illustrates the application of the algorithm on the final model for nf=0, nc=1 and l=3, with the corresponding limits. As Figure 8 shows, the optimum limits provide the maximum value of 32 units (Jalali and Ataee-pour, 2004). A C++ program is developed to implement the OLIPS algorithm, which is called Stope Boundaries Optimiser (SBO). The SBO program creates a probable stope model and integrated probable model, respectively, considering the technical constraints of the underground mining method, including the minimum length and height of the stope; determines economically optimum stope boundaries using the probable stope algorithm; records the outputs in a Fig. 7: The IPS model developed using Figure 4

1 1 1 0 -1 -1 -1 -1 1 1

0 1 2 1 -1 -1 2 0 2 2 y 2 2 2 0 2 0 1 1 2 1 1

1 1 -1 1 -1 1 0 1 2 1

2 3 4 5 6 7 8 9 10 x Fig. 8: An application of the OLIPS 8 data file, including the maximum values of all probable stope boundaries, the address of all blocks, which fall within the optimum limits and their total value. The SBO complies with all underground mining methods used for tabular deposits. CONCLUSIONS Regarding the mentioned analysis of the algorithms, the main their Capabilities, Restrictions and Applications may be shown in Table 1. Table 1: Capabilities, restrictions and applications of the rigorous algorithms Algorithms Partial Blocks Mining Method Model Dimensions Rigorous/ Heuristic Computer Programming RDP No Block caving 2D Rigorous Yes BB Yes All 1D Rigorous No (General) OLIPS No All 2D Rigorous Yes (SBO) The rigorous algorithms are partial-based algorithms, i.e. they are applied on a panel or a section of an orebody. With the mathematical support, these algorithms provide the optimum solution for a panel or a section. However, when panels and levels are combined, the optimality is violated. In the other side, The rigorous algorithms are applied on a 2D or even 1D economic models. Therefore, the optimality is violated when the problem is considered in three dimensions for the entire orebody. REFERENCES

Ataee-pour, M., 1997, A New Heuristic Algorithm to Optimise Stope Boundaries, Proceeding of the 2nd Regional APCOM Symposium on Computer Applications in the Minerals

Industries, L. Puchkov (ed.), Moscow, Russia, pp.

Ataee-pour, M., 2005, A Critical Survey of the Existing Stope Layout Optimization Techniques”, Journal of Mining Science, Vol. 41, No. 5.

Jalali, S.E., Ataee-pour. M., 2004, A 2D Dynamic Programming Algorithm to Optimise Stope Boundaries, Proceedings of Mine Planning and Equipment Selection, MPES'04, (eds. M. Hardygora et al), Rotterdam, Balkema, pp 45-52

Jalali, S.E, 2006, Optimization of Underground Mining Area in Vein Type Deposits, Ph.D.

Thesis, Amirkabir University of Technology, Tehran, Iran.

Kim, Y.C., 1978, Ultimate Pit Design Methodologies Using Computer Models-The State of the Art, Mining Engineering, Society For Mining, Metallurgy And Exploration, Inc., Colorado, October, pp. 133-138.

Ovanic, J., Young, D., 1995, Economic Optimisation of Stope Geometry Using Separable Programming with Special Branch and Bound Techniques, 3rd Canadian Conference on Computer Applications in the Mineral Industry, H. Mitri (ed.), Balkema, Rotterdam, pp. 129-

Riddle, J., 1977, A Dynamic Programming Solution of a Block-Caving Mine Layout, 14th International Symposium on the Application of Computers and Operations Research in the Mineral Industry, Society for Mining, Metallurgy and Exploration, Colorado, pp. 767-780.