UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Application of push-relabel and heuristics to open pit mines Sahni, Jaspreet 1996

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
ubc_1997-0031.pdf [ 3.25MB ]
[if-you-see-this-DO-NOT-CLICK]
Metadata
JSON: 1.0087587.json
JSON-LD: 1.0087587+ld.json
RDF/XML (Pretty): 1.0087587.xml
RDF/JSON: 1.0087587+rdf.json
Turtle: 1.0087587+rdf-turtle.txt
N-Triples: 1.0087587+rdf-ntriples.txt
Original Record: 1.0087587 +original-record.json
Full Text
1.0087587.txt
Citation
1.0087587.ris

Full Text

APPLICATION OF P U S H - R E L A B E L A N D HEURISTICS TO O P E N PIT MINES by JASPREET SAHNI M.B.A., Simon Fraser University,  1992  M.Sc., The University of British Columbia,  1996  A THESIS SUBMITTED IN PARTIAL F U L F I L L M E N T OF T H E REQUIREMENTS FOR T H E D E G R E E OF M A S T E R OF SCIENCE in T H E F A C U L T Y OF G R A D U A T E STUDIES (Department of Commerce) We accept this thesis as conforming to the required standard  T H E UNIVERSITY OF BRITISH C O L U M B I A October 1996 (C)Jaspreet  Sahni,  1996  In  presenting this  degree at the  thesis  in  partial  University of  fulfilment  of  the  requirements  British Columbia, I agree that the  for  an advanced  Library shall make it  freely available for reference and study. I further agree that permission for extensive copying of this thesis for department  or  by  his  or  scholarly purposes may be her  representatives.  It  publication of this thesis for financial gain shall not  is  granted by the understood  be allowed without  permission.  Department of  Co^i^erta  and-  The University of British Columbia Vancouver, Canada  Date  -6 (2/88)  Dec^wx b-ev  H  , ' °> S fe  ©usi^esc,  that  A . d m i r t t s ' T r a \ 100  head of copying  my or  my written  Abstract  The p i t l i m i t p r o b l e m i s c r u c i a l t o mine p l a n n i n g . The us o f computer models t o d e s i g n u l t i m a t e open p i t l i m i t s i s becoming i n c r e a s i n g l y p o p u l a r . One s o l u t i o n method adopted i s t o t r a n s f o r m t h e p i t l i m i t problem t o a maximum f l o w network. A p o p u l a r maximum f l o w t e c h n i q u e i s push r e l a b e l . of t h i s t h e s i s i s twofold.  The purpose  The f i r s t i s t o check i f push  r e l a b e l a l g o r i t h m p e r f o r m s b e t t e r t h a n o t h e r MF a l g o r i t h m s on r e a l , r a t h e r t h a n randomly g e n e r a t e d d a t a (as i n t h e p a s t ) . The second i s t o d e v e l o p and t e s t h e u r i s t i c s t h a t c a n t a k e advantage o f t h e c h a r a c t e r i s t i c s o f t h e open p i t mine network s t r u c t u r e t o f u r t h e r enhance t h e push r e l a b e l  ii  routine.  Table  of  Contents  Abstract  i i  Table of Contents  i i  L i s t of Tables L i s t of  iv  Figures  V  Acknowledgement  vi  Chapter One  Introduction  1  Chapter Two  Modelling  4  Chapter Three  O p t i m i s a t i o n Techniques  6  Graph Theory-  8  Two d i m e n s i o n a l dynamic programming  9  Three d i m e n s i o n a l dynamic programming  10  L i n e a r programming  12  Network Flow  13  FKS c l o s u r e a l g o r i t h m  15  Johnson's Network f l o w  17  Push R e l a b e l  19  Heuristics  22  Our I m p l e m e n t a t i o n  24  Various Heuristics  28  I l l u s t r a t i v e example  39  R e s u l t s and C o n c l u s i o n s  47  T a b l e s and F i g u r e s  55  References  70  Chapter Four  Chapter F i v e  iii  LIST  Solution Total  OF  Times  Times  FKS Dinic Push R e l a b e l  (FIFO)  Heuristic Push R e l a b e l  (HL)  Heuristic Expanded  iv  TABLES  LIST  OF  FIGURES  S o l u t i o n time S o l u t i o n time (no FKS) S o l u t i o n time S o l u t i o n time  (no FKS)  T o t a l time Log S o l u t i o n time v s . Log Nodes  Acknowledgement  I would l i k e t o thank a l l t h e members o f my committee for  t h e i r time and p a t i e n c e . I n p a r t i c u l a r my s u p e r v i s o r Dr  Tom McCormick d e s e r v e s s p e c i a l r e c o g n i t i o n f o r h i s t i m e spent i n numerous meetings o r g a n i s i n g my r e s e a r c h . I would l i k e t o acknowledge t h e h e l p o f Lynx Geosystems, I n c . f o r p r o v i d i n g mine d a t a  (blockmod and  .spp and .spv f i l e s .  sabo2)  and t h e code f o r g e n e r a t i n g t h e  I would a l s o l i k e t o thank Todd S t e w a r t  f o r w r i t i n g t h e network g e n e r a t o r code. F i n a l l y , I thank my e n t i r e f a m i l y , e s p e c i a l l y my p a r e n t s and w i f e Meera, f o r t h e i r c o n s t a n t s u p p o r t and encouragement.  vi  CHAPTER  1  Introduction  Mine p l a n n i n g  c o n s i s t s o f determining  e x t r a c t i o n over a g i v e n time h o r i z o n .  a sequence o f  The optimum  open-pit  l i m i t o f a mine i s d e f i n e d by Caccetta and G i a n n i n i (1990) t o be  a f e a s i b l e contour whose e x t r a c t i o n r e s u l t s i n maximum  total profit. and  Feasibility  workable w a l l  slopes  n e c e s s i t a t e s the p i t t o have s a f e which depend on t h e g e o l o g i c a l  s t r u c t u r e and the mining equipment.  The u l t i m a t e p i t l i m i t s  affect  and  the e n t i r e  mine  layout  provide  essential  i n f o r m a t i o n f o r t h e e v a l u a t i o n o f t h e economic p o t e n t i a l o f the m i n e r a l and  d e p o s i t and i n f o r m u l a t i n g l o n g ,  s h o r t range mine p l a n s . Consequently,  optimum p r o f i t a b l e u l t i m a t e p i t l i m i t s  intermediate,  knowledge o f t h e  during  the i n i t i a l  stages can avoid c e r t a i n problems such as mining u n p r o f i t a b l e expansions, abandoning p r o f i t a b l e ore, and r e l o c a t i n g s u r f a c e facilities. A mine p l a n n i n g s i t u a t i o n r e q u i r e s d i f f e r e n t l e v e l s o f p r e c i s i o n a t each stage.  Johnson (1973) argues t h a t a good  e s t i m a t i o n o f the p i t l i m i t provides a s a t i s f a c t o r y b a s i s f o r the i n i t i a l f e a s i b i l i t y e v a l u a t i o n o f a m i n i n g p r o j e c t . But knowledge o f the t r u e optimum becomes more v a l u a b l e as mine life  progresses  and the knowledge o f each aspect  operation increases.  The a v a i l a b i l i t y o f a c c u r a t e  1  of the economic  pit  l i m i t s f o r i n t e r m e d i a t e range p l a n n i n g l e a d s t o b e t t e r  scheduling project.  resulting  i n increased p r o f i t a b i l i t y  f o r the  The u l t i m a t e d e c i s i o n t o abandon an o p e n - p i t m i n i n g  v e n t u r e r e q u i r e s t h a t the p i t l i m i t c a l c u l a t i o n be n o t h i n g s h o r t o f optimum.  Unfortunately, i n the past the techniques  t h a t guarantee optimum s o l u t i o n s have been t o o complex t o be understood by the mining community o r too c o s t l y t o implement i n terms o f computer p r o c e s s i n g t i m e s . use  o f simple  planning  may  and f a s t  heuristics.  therefore benefit  This r e s u l t s i n the A l l stages  from  a  o f mine  technique  which  p r o v i d e s an o p t i m a l s o l u t i o n a t a low c o s t and i n an e a s i l y understood manner. One technique used t o p r o v i d e t h e o p t i m a l p i t l i m i t i s to  t r a n s f o r m t h e network i n t o a maximum f l o w problem.  The  maximum f l o w problem can then be s o l v e d w i t h many s t a n d a r d routines  o f which  the one w i t h t h e b e s t  p r a c t i c a l performance that  i s push-relabel.  network implementations  regarded  t o be t o o slow,  which  reputation f o r  This t h e s i s  i n t h e p a s t have been  a r e indeed v e r y  fast  assesses the push r e l a b e l algorithm's performance to  shows  now.  It  as compared  o t h e r maximum-flow a l g o r i t h m s on a c t u a l c l a s s o f graphs  (open p i t mining) r a t h e r than randomly generated d a t a as has been done i n the past a t the DIMACS Challenge (Cherkassky and Goldberg 1994).  A l s o , we attempt t o take advantage o f t h e  2  special  structure  of  an  open  p i t mine  by  developing  h e u r i s t i c s i n o r d e r t o enhance the performance o f the pushr e l a b e l r o u t i n e on t h i s c l a s s o f problems.  3  2  CHAPTER  Modelling  Caccetta  and  Giannini  (1990)  define  the  optimum  u l t i m a t e p i t l i m i t of a mine as t h a t contour which i s the r e s u l t o f e x t r a c t i n g the volume o f m a t e r i a l which p r o v i d e s the t o t a l maximum p r o f i t w h i l e s a t i s f y i n g c e r t a i n operational  requirements  such  as  safe  wall  practical  slopes.  As  i n d i c a t e d by Lerchs and Grossmann(1965), the problem can expressed  a n a l y t i c a l l y as f o l l o w s .  Let v, c, and m be  t h r e e d e n s i t y f u n c t i o n s d e f i n e d at each p o i n t  (x,y,z)  be the  of a  t h r e e d i m e n s i o n a l r e g i o n c o n t a i n i n g the ore-body w i t h v ( x , y , z ) : mine v a l u e of ore per u n i t volume c ( x , y , z ) : e x t r a c t i o n c o s t per u n i t volume m(x,y,z): p r o f i t per u n i t volume = v(x,y,z) - c ( x , y , z ) L e t a(x,y, z) be the s e t of angles s p e c i f y i n g the w a l l s l o p e restrictions  at  the  point  (x,y, z)  with  respect  h o r i z o n t a l p l a n e , f o r a g i v e n s e t o f azimuths.  to  This set i s  known as the v a r i a b i l i t y o f w a l l s l o p e requirement. S as the f a m i l y o f slope  with  corresponding  respect angle  to  the  i n a.  then i s to f i n d a volume V profit  Define  s u r f a c e s such t h a t a t no p o i n t does the h o r i z o n t a l plane Denote the  function  Q  exceed  f a m i l y of  corresponding to the f a m i l y S of s u r f a c e s by V.  the  the  volumes  The problem  which maximises the i n t e g r a l  m(x,y, z ) .  4  Since,  the  in  of  practical  s i t u a t i o n s , there i s no simple a n a l y t i c a l r e p r e s e n t a t i o n f o r the f u n c t i o n s v and c, numerical techniques must be used to s o l v e the problem. blocks.  Generally, the ore body i s d i v i d e d i n t o  The mineral deposit must somehow be represented as  a model to f a c i l i t a t e mine planning.  The r e p r e s e n t a t i o n must  incorporate both the three dimensional mine s t r u c t u r e and the economic value o f the d e p o s i t . The most popular method model.  i s the r e g u l a r 3-D f i x e d block  This model was f i r s t p u b l i s h e d i n the e a r l y 1960's.  In t h i s model the t o t a l volume i s transformed  i n t o a three  dimensional g r i d whose each block i s an independent u n i t with its  own  economic content.  Since  there  are such  a large  number of blocks i n a t y p i c a l block model i t i s e s s e n t i a l that  the o p t i m i s a t i o n algorithm  delivers  the s o l u t i o n i n  minimum computer time. A f a s t algorithm c o u l d a l s o be run on a personal  computer.  Because of the c o s t l y ' r a m i f i c a t i o n s  associated with the mine contours generated, that  the  accuracy  of  these  problem  contours  compounding  this  i s the  information  which means that  times.  5  be  desire  i t i s imperative high. for  the model must  Further  sensitivity be  run many  CHAPTER Optimisation  Optimisation  refers  certain constraints.  3  Techniques  to o p t i m i s a t i o n with  respect to  Some o f these c o n s t r a i n t s are i m p l i c i t  i n the assumptions being used, and nearly a l l techniques make some key assumptions. (1)  Kim (1977) s t a t e s some o f these as:  The grade and cost of mining  each block  i s known and  accurate. (2)  The cost o f mining  each block does not depend on the  sequence of mining. (3) The d e s i r e d slopes and p i t o u t l i n e s can be approximated by removed b l o c k s . (4) The o b j e c t i v e i s to maximise t o t a l undiscounted  profit,  which i s questionable due to the d i f f e r e n c e i n present values of cash flows. In a l l optimisation techniques, the predominant type o f model used i s the r e g u l a r 3-D f i x e d block model. The block model i s represented as a weighted digraph with the v e r t i c e s representing  blocks  and  the  arcs  representing  mining  r e s t r i c t i o n s . A digraph G c o n s i s t s of a s e t of v e r t i c e s V(G) and a set of arcs E (G) .  There i s an incidence r e l a t i o n which  a s s o c i a t e s with each a r c of G an ordered p a i r o f v e r t i c e s . A  (node) weighted digraph i s one i n which each vertex has an  assigned weight.  Here, the graph contains the a r c (x,y)  6  if  the mining of block x r e q u i r e s the removal o f block y. The profit  from mining a block i s represented by an appropriate  vertex weight.  A c l o s u r e o f a weighted digraph i s a  set of  v e r t i c e s C such that i f x i s a member o f C and (x,y) i s an a r c then y must be a member of C.  The weight w(C) o f the  c l o s u r e C i s the sum of the weights of the v e r t i c e s o f C. Here, a c l o s u r e represents a f e a s i b l e p i t contour, with the weight representing the p r o f i t r e a l i s e d from that p i t contour and  conversely  maximum  the graph  weight  in a  theory problem o f determining  weighted  digraph  a  i s equivalent to  determining the optimum p i t contour. There have been at l e a s t four rigorous o p t i m i s i n g techniques presented s i n c e 1965: (1) Lerchs Grossmann (2) Dynamic programming (3) L i n e a r programming (4) Network Flow, i n c l u d i n g (a) FKS (b) Johnson (c)  Push-Relabel  (d) D i n i t z , Ford-Fulkerson, e t c . In  a d d i t i o n , there  are other n e a r l y o p t i m i s i n g h e u r i s t i c s  such as F l o a t i n g Cone.  7  Graph  The by  Theory  Lerchs-Grossmann g r a p h i c a l technique was  Helmut Lerchs  1965). The  and  Ingo Grossmann  (Lerchs  developed  and  Grossman  Lerchs-Grossmann a l g o r i t h m augments the  digraph  r e p r e s e n t i n g the ore body i n t o a rooted t r e e by adding a r o o t v e r t e x and a r c s t o a l l o t h e r v e r t i c e s . Each s e t of v e r t i c e s and  a r c s i s c l a s s i f i e d as e i t h e r s t r o n g o r weak.  A  t r e e whose root i s common to a l l s t r o n g a r c s i s a  rooted  normalised  t r e e . The Lerchs-Grossmann a l g o r i t h m proceeds by c o n s t r u c t i n g a sequence of n o r m a l i s e d t r e e s , t e r m i n a t i n g when the s e t of strong v e r t i c e s of the n o r m a l i s e d t r e e form a c l o s u r e of the graph r e p r e s e n t i n g  the  ore  body because of  the f o l l o w i n g  theorem: I f , i n a weighted d i g r a p h G, a n o r m a l i s e d tree  T can  vertices  be  of  constructed  T,  is a  such t h a t Y the  c l o s u r e of  G,  then Y  spanning  s e t of  strong  i s a maximum  closure. There has Lerchs  been a c o n s i d e r a b l e amount of work done on  Grossmann to date such as the W h i t t l e 4D  commercial  s o f t w a r e p r o j e c t which c o s t s $15,000 and i s the standard i n the i n d u s t r y now. a t r u e 3-D  This i s due to the f a c t t h a t i t p r o v i d e s  optimal.  8  Two D i m e n s i o n a l  Lerchs  Dynamic  and Grossmann f i r s t  Programming  presented  t h e b a s i c two-  dimensional optimal cross s e c t i o n method (Lerchs and Grossman 1965) .  The method determines the optimum u l t i m a t e p i t l i m i t s  i n each v e r t i c a l c r o s s - s e c t i o n o f the economic b l o c k model. The union o f these o p t i m a l c r o s s s e c t i o n p i t o u t l i n e s y i e l d s a  3-D p i t contour which  usually  violates  the w a l l  slope  r e s t r i c t i o n s and i s thus i n f e a s i b l e . The  advantages  implementation solution. it  and  of use,  this  technique  are  ease  of  i t s flexibility  and  speed  of  There are two disadvantages o f t h i s method. F i r s t ,  optimises only with regard to cross-section  and thus  r e q u i r e s e x t e n s i v e e f f o r t t o smooth out the p i t bottom and end s e c t i o n s . necessarily  Secondly, the two-dimensional contours do not line  up from  cross section  r e s u l t i n g i n an i n f e a s i b l e s o l u t i o n .  9  to cross  section  Three  Dimensional  Dynamic  Programming  A number o f dynamic programming a l g o r i t h m s attempt t o extend  the b a s i c  presented  two-dimensional  by Lerchs  and Grossmann  d i m e n s i o n a l problem. Johnson  and Sharp  cross  section  t o handle  routine  the t h r e e -  One such technique was developed by (1971).  T h i s technique e l i m i n a t e s the  bottom end smoothing which i s the primary disadvantage o f t h e two- d i m e n s i o n a l t e c h n i q u e . The  a l g o r i t h m employs r e p e t i t i v e  two-dimensional  algorithm  to  obtain  application the optimum  c o n f i g u r a t i o n on each c r o s s - s e c t i o n , f o r each l e v e l . final  application  o f the  o f the two-dimensional  block Then a  a l g o r i t h m on a  l o n g i t u d i n a l s e c t i o n where the b l o c k s r e p r e s e n t the o p t i m a l section  contours  advantages  of  down  t o each  level.  There  the t h r e e - d i m e n s i o n a l dynamic  a r e two  programming  technique. F i r s t l y , ease o f understanding and implementation. Secondly, f l e x i b i l i t y .  The major disadvantage o f t h i s method  i s t h a t the s o l u t i o n may not be f e a s i b l e because t h e method does not r e q u i r e adjacent c r o s s - s e c t i o n a l p i t c o n f i g u r a t i o n s to l i n e up. of  Other dynamic programming methods such as those  Koenigsberg  (1982) and B r a t i c e v i c  the Johnson-Sharp unfortunately  (1984) seek t o extend  method i n overcoming t h i s d i f f i c u l t y result  in  significant  increases  but in  computational complexity; s t i l l n e i t h e r achieves a p r o p e r 3-D  10  optimum  solution.  technique w i l l the  not  two p r i n c i p a l  longitudinal area  of  the  A further  axes o f  are  known as t h e  the  corner  deposit  The waste  neglected  optimum r e s u l t i n g i n s t e e p e r is  is  that  the  c o n s i d e r waste b l o c k s e x c e p t t h o s e  directions). pit  disadvantage  effect.  11  in  i n d e v e l o p i n g the  p i t slopes  along  (cross-sectional blocks  the  3-D  and  corner  pit  i n these areas.  limit This  Linear  It  Programming  i s n a t u r a l , t o formulate t h e open p i t problem as a  l i n e a r program s i n c e l i n e a r programming i s one o f t h e most popular  operations  formulation  research  as a l i n e a r  modelling  techniques.  program i s v e r y  simple  The  but the  s o l u t i o n o f such a model i s not c o m p u t a t i o n a l l y f e a s i b l e f o r large  ore bodies.  I n order  t o apply  linear  techniques t h e problem s i z e must be reduced.  12  programming  Network  Picard  Flow  (1976) proposed  a network flow model to solve  the maximum c l o s u r e problem.  The network N i s obtained from  the  digraph  D o f the orebody  (source) and t ( s i n k ) .  by adding  two v e r t i c e s  s  The source i s j o i n e d to a l l v e r t i c e s  having a p o s i t i v e weight by an a r c o f c a p a c i t y equal to the weight of the vertex.  A l l v e r t i c e s o f negative weight are  j o i n e d to the sink by an a r c having c a p a c i t y equal to the absolute value of the weight of the vertex. arcs of D are given i n f i n i t e capacity.  A l l the i n t e r n a l  Picard formulated the  problem as a 0-1 program and showed that the maximal c l o s u r e of D corresponds to a minimal any  o f the standard  number (Ahuja, method  maximum  o f algorithms Magnanti,  cut of N which can be found by flow  to solve  and O r l i n )  o f Dantzig,  routines.  the maximum  such  the augmenting  There  are a  flow  problem  as the network  simplex  path  method  o f Ford-  Fulkerson, the b l o c k i n g flow method of D i n i c , and the pushr e l a b e l method of Goldberg and Tarjan. Network flow methods have been regarded by the mining community as too slow and r e q u i r i n g too much memory, but t h i s was  before  theoretical The  good  implementations.  bounds but run time  empirical  algorithm  modern  performance  of  i s not  that matters  i n practice.  push-relabel  and  are e s t a b l i s h e d i n a paper  13  It  Dinit's  by Cherkassky  and  Goldberg  (1994).  They implemented  two v e r s i o n s o f  push-  relabel  (highest l a b e l and FIFO) each combined w i t h g l o b a l  and  relabeling heuristics,  gap  Dinic's  algorithm.  and  one  They ran these  implementation  routines  on  of  randomly  generated set of problems which were used at the F i r s t DIMACS Challenge (Cherkassky and Goldberg 1994). show faster  that  both  versions  than D i n i t z  T h e i r experiments  of p u s h - r e l a b e l  are e m p i r i c a l l y  f o r a l l s e t o f problems  and  that  the  highest l a b e l version of push-relabel i s e m p i r i c a l l y f a s t e r than  the  performance  FIFO of  version these  f o r a l l sets  routines  investigated i n this thesis.  on  of  problems.  a c t u a l mining  Some network  The  data i s  flow techniques  p r e s e n t e d t o date are d i s c u s s e d i n the f o l l o w i n g s e c t i o n s .  14  FKS  This Schmitt  technique  Closure  was  Algorithm  developed  by  Faaland,  Kim,  (1990) to solve maximum c l o s u r e problems. a  compact  representation  of  and  I t works  entirely  within  the  digraph.  Each vertex i s given a c e r t a i n weight c a l l e d supply  sup(j) and every arc has a p a i r of c a p a c i t i e s which are  set to c a p ( i , j ) = i n f i n i t y and c a p ( j , i ) = 0.  weighted  initially The unique  f e a t u r e of t h i s algorithm i s a s t a y l i s t which i s the set of nodes which need not be considered i n subsequent of  the  algorithm. The  staylist  is initially  iterations empty.  The  algorithm proceeds as f o l l o w s : Step 1: Initialise:  sup(j) = weight  of j .  Staylist  = empty.  c a p ( i , j ) = i n f i n i t y . c a p ( j , i ) = 0. Step 2: F i n d a p o s i t i v e supply node i not on the s t a y l i s t set  and  i t s predecessor l a b e l P ( i ) = 0.  Step 3: Find a node j u n l a b e l l e d i n t h i s i t e r a t i o n that i s not on the s t a y l i s t and with c a p ( i , j ) > 0.  I f none jump to step  7. Step 4: Send flow from i to j . Label P(j) = i . sup (i) -=flow. c a p ( i , j ) - = f l o w . sup(j)+=flow.  cap(j)+=flow.  15  Step  5: If  sup(j)  >  0 then  i =  j go  to  step  2.  Otherwise  sup(j) = 0 so backtrack to k=P(j). Step  6: If sup(k) > 0 then erase l a b e l s of j and nodes l a b e l l e d  after  j  i n this  Otherwise Step  iteration  and  set i=k  and  go  to step  3.  sup(k) = 0 so set j=k and go to step 5.  7: Backtrack from i to k=P(i).  Step  8: I f P(i) > 0 then send  flow from i to k and r e s e t  and cap and i=k and go to step 4. i  Otherwise  sup  P(i) =0 so add  and nodes l a b e l l e d a f t e r i to s t a y l i s t . The  maximum c l o s u r e i n the digraph at the end of the  algorithm Faaland,  is Kim,  generated  identified and  by  Schmitt's  two-dimensional  the  nodes  in  paper t e s t s  on  v e r s i o n of the  the  staylist.  small randomly  open p i t problem  with t h i s technique and so there i s no standard to compare the e m p i r i c a l complexity of t h i s algorithm with the others stated above. a  basis  for  We  implemented t h i s algorithm i n C to provide  the  performance  heuristic.  16  of  push  relabel  and  our  Johnson's  Network  Flow  T h i s technique was f i r s t proposed by Johnson i n 1968. I t uses the same block p a t t e r n r e p r e s e n t a t i o n o f allowable mining slopes as the Lerchs-Grossmann method and s t a r t s with the same network r e p r e s e n t a t i o n o f r e q u i r e d allowable mining sequence  and converts  algorithm  as  i t into  i l l u s t r a t e d by  a bipartite Johnson  network.  (1973)  The  proceeds  as  follows: Step 1: We d i v i d e the blocks i n t o two sets, and  (a) p o s i t i v e blocks  (b) negative or zero b l o c k s .  Step 2: Connect  each  positive  block  to a l l negative  blocks  which are r e q u i r e d to be mined to remove the p o s i t i v e block by adding arcs from the p o s i t i v e block to the negative b l o c k . Step 3: For each p o s i t i v e block a l l o c a t e flow from the p o s i t i v e block to i t s r e s t r i c t i n g negative blocks, mine t h i s block and i t s r e s t r i c t i n g blocks i f the sum i s p o s i t i v e . This process usually  r e q u i r e s r e a l l o c a t i n g flow f o r shared b l o c k s i n the  network. T h i s technique but  leads to an optimal u l t i m a t e p i t l i m i t  i t s disadvantage  r e a l l o c a t i n g flow.  i s i t s inefficiency  The need to r e a l l o c a t e  17  caused  due to  flow occurs when  r e s t r i c t i n g negative blocks are shared by p o s i t i v e  blocks.  The reason i s that a uneconomic p o s i t i v e block should not be used to support the s t r i p p i n g of an economic block which can support been  i t s own  compared  stripping. to  the  This r e a l l o c a t i o n process  normalisation  step  i n the  Lerchs-  Grossmann technique though Johnson's i s computationally expensive.  18  has  less  Push-Relabel  Push-Relabel i s an algorithm through a network.  f o r f i n d i n g a maximum flow  A flow network i s a d i r e c t e d graph G =  (V,E,S/t,u) where V and E are the node and arc s e t . and  t are the source and  c a p a c i t y on the a r c s .  the sink and u i s the nonnegative  A flow i s a f u n c t i o n that  capacity constraints on a l l arcs and conservation on  all  nodes  conservation  except  Nodes s  the  source  and  the  satisfies  constraints sink.  The  c o n s t r a i n t at a node v s t a t e s that the  excess  e(v), defined as the d i f f e r e n c e between the incoming and  the  outgoing flows,  the  i s equal to zero.  A preflow  satisfies  capacity constraints and the relaxed conservation  constraints  that only r e q u i r e the excesses to be nonnegative. An without  arc i s r e s i d u a l i f the violating  the  flow on i t can be  capacity  constraints,  and  increased saturated  otherwise. The  r e s i d u a l c a p a c i t y of an arc i s the amount by  which the  flow  d:V->  arc  be  increased.  A  distance  labelling  N s a t i s f i e s the f o l l o w i n g c o n d i t i o n s : d(t) = 0  every r e s i d u a l arc (v,w)  can  i s admissible  i f d(v) The  (v,w), d(v) i f d(v)  < n and e(v)  d(w)  = d(w)  + 1.  + 1.  for  A r e s i d u a l arc  A node v i s a c t i v e  > 0.  push-relabel  distance l a b e l l i n g t i l l preflow  <=  and  algorithm  maintains a preflow  there are no a c t i v e nodes.  i s converted to a flow.  19  and  a  Then the  The push r e l a b e l r o u t i n e s  of  Cherkassky and Goldberg  (1994) proceed as f o l l o w s :  Step 1: Find  an a c t i v e  node v.  An  active  node  i s one with  p o s i t i v e excess and d i s t a n c e l a b e l l e s s than n. I f there are no a c t i v e nodes then stop. Step 2: Find the next edge (v,w) of v.  I f none go to step 4.  Step 3: If(v,w) i s admissible then send d = (0,min(excess(v) , r e s i d u a l capacity(v, w)) u n i t s of flow from v to w and repeat step 3 u n t i l excess(v) equal zero. I f (v,w) not admissible go to step 2. Step 4: Replace v's d i s t a n c e l a b e l  d(v) by min  (ViW)  d(w) + 1. Go  to step 1. The main discharge o p e r a t i o n i s a p p l i e d i t e r a t i v e l y to a c t i v e nodes as above.  A l l that i s l e f t  i s to decide the  order i n which these a c t i v e nodes must be processed. are two The f i r s t all  There  a l t e r n a t i v e s presented by Goldberg and Cherkassky. one i s known as the FIFO a l g o r i t h m and maintains  a c t i v e nodes i n a queue adding a c t i v e nodes to the rear  of the queue and discharging p o s i t i v e nodes from the f r o n t of the queue i n a F i r s t - I n F i r s t - O u t order.  The second one i s  the HL algorithm and always selects the node with the highest  20  l a b e l to discharge f i r s t . Cherkassky and Goldberg improve the practical  performance  relabel  algorithms by  adding g l o b a l and gap r e l a b e l l i n g h e u r i s t i c s  to the maximal  flow code.  of  the  In t h e i r paper  (1994) Cherkassky and Goldberg  show that both the push r e l a b e l Dinitz  on randomly  push  routines perform b e t t e r than  generated sets of data from the DIMACS  generators.  21  Heuristic  Methods  Although proposed,  a  only one  f l o a t i n g cone. fact  that  number of  of  heuristic  them has  methods  been widely  The method's wide acceptance  i t very  easily  understood  and  have  been  accepted,  the  stems from the  easy  to program.  Also, there i s no r e s t r i c t i o n on wall slope v a r i a b i l i t y .  The  method as i l l u s t r a t e d by Johnson (1973) proceeds as f o l l o w s : Step  1: Define a c e r t a i n p o t e n t i a l mining  volume by s t a t i n g a  bottom block and the allowable w a l l slopes. Step  2: Sum  the  value  of  a l l the  blocks  whose  centres l i e  i n s i d e the d e f i n e d cone. Step  3: Select  the  cone  f o r mining  i f the  total  value  is  greater than zero. The above process i s continued u n t i l i t i s not p o s s i b l e to f i n d any cones of p o s i t i v e value. technique  are  that  it  is  The advantages of t h i s  easily  to  understand,  allows  v a r i a b l e p i t slopes, i s easy to implement, and that v a r i a b l e s i z e blocks present no d i f f i c u l t y .  The b a s i c shortcoming  of  the method i s i t s i n a b i l i t y to consider j o i n t c o n t r i b u t i o n s of m u l t i p l e ore blocks  located l a t e r a l l y  thereby missing the optimal s o l u t i o n .  22  a d i s t a n c e apart  CHAPTER Our  4  Implementation  As described e a r l i e r , the open p i t l i m i t problem can be converted  to a maximum  flow  problem.  The maximum  flow  problem i s very easy to s t a t e : In a c a p a c i t a t e d network, we want  to send  called  as much flow  as p o s s i b l e  between  two nodes  the source s and the sink t , without v i o l a t i n g the  capacity  restriction  algorithms  on any arc.  f o r solving  There  the maximal  are a number o f  flow  problem.  As  mentioned i n Chapter 3, the b a s i c methods are: (1) Network simplex method of Dantzig (2) The Augmenting Path method of Ford and Fulkerson (3) The Blocking Flow method of D i n i c (4) Push Relabel method o f Goldberg and Tarjan Studies by Goldfarb Dinitz  algorithm  and G r i g o r i a d i s (1988) showed that  i s i n practice  superior  to the network  simplex  and the Ford-Fulkerson  studies  such as those by Anderson and Setubal  Nguyen and Venkateswaran method  i s superior  methods.  Several  recent  (1993) and  (1993) show that the push r e l a b e l  to D i n i c ' s  method  i n practice.  p a r t i c u l a r the paper by Goldberg and Cherkassky  In  (1994) showed  that two versions of push r e l a b e l perform b e t t e r than D i n i t z f o r a l l problem sets generated by the F i r s t DIMACS challenge; The  data  used  to come  to t h i s  23  conclusion  are randomly  generated  by the DIMACS network  generators.  This t h e s i s  attempts to confirm these conclusions on r e a l sets o f data for  open-pit mining problems. Tom McCormick  and Todd  Stewart's code  generates  a  bounded network with a minimum p o s s i b l e number of blocks and arcs.  I imbed s e v e r a l implementations of  network  i s generated  to check  performance o f push r e l a b e l  i f  we  h e u r i s t i c s as the can improve the  by g i v i n g i t a "warm  start".  Since the push-relabel deals with preflows one can, g r e e d i l y or by taking advantage o f a open p i t mine s t r u c t u r e , push as much flow as we want and input these excesses  as a preflow  into the push-relabel routine thereby g i v i n g i t a warm s t a r t . F i r s t l y , the network generation r o u t i n e e s t a b l i s h e s the lowest p o s i t i v e value block i n each row column p a i r o f the ore  body because there  beneath these.  i s no need to consider  any blocks  Next we have to add on those blocks that are  o u t s i d e the ore body that would need to be removed i n order to  remove blocks w i t h i n the ore body. This i s given by the  .spp f i l e which i s the cone of slopes o f azimuths above any block. The .spp f i l e gives us a l l the blocks that need to be removed i n order to remove a s p e c i f i c block. F i n a l l y , we a l s o have slope  to add on blocks restriction.  that are necessary  This  to s a t i s f y  i s given by the .spv f i l e  wall which  gives the minimum s e t of arcs whose t r a n s i t i v e c l o s u r e gives  24  the same cone given by the .spp f i l e .  The .spv f i l e  the outer boundary blocks of the .spp f i l e . .spv  files  are generated  v i a Lynx's  code  gives us  The .spp and  and examples o f  these f i l e s are given on pages 47 and 52. We  attempt t o enhance  the speed o f the network  r o u t i n e by g i v i n g i t a warm s t a r t .  flow  Several h e u r i s t i c s are  s t u d i e d i n order to take advantage o f the three  dimensional  s t r u c t u r e o f the open p i t mine network that i s solved by a generic maximum flow problem.  The network generator proceeds  as f o l l o w s : Step 1: Read i n the 3-D block array with block values. Step 2: Establish  a bottom l a y e r  f o r each row-column  p a i r as  the lowest p o s i t i v e block l a y e r . Step 3: Extend the bottom array to a new bottom expanded  as i n d i c a t e d  by the .spp f i l e  whose s i z e i s  to allow  blocks  outside the o r i g i n a l orebody to be mined. Step 4: Establish  a linked  list  of a l l positive  value  bottom  layers. Step 5: Run  through  this  linked  25  list  and add any new bottom  layers  that  are needed  s a t i s f y w a l l slope  as i n d i c a t e d  by the .spp f i l e  to  requirements.  Step 6: Number a l l the blocks that are i n the network. Step  7: Run through  each block  from bottom up generating the  minimum p o s s i b l e number o f arcs needed to remove that block as given by the .spv f i l e .  Attempt to push flow as d i c t a t e d  by the h e u r i s t i c .  26  VARIOUS  HEURISTICS  We are using a g e n e r a l i s e d maximum flow r o u t i n e relabel) pit  to solve a s p e c i f i c a p p l i c a t i o n which i s the open  mine problem.  dimensional sink  (push  s t r u c t u r e and f i n i t e  arcs  structure  The open p i t mine problem  only.  The idea  has a  three  c a p a c i t i e s on source and  then  i s to use t h i s  to enhance the performance  special  o f the push  relabel  routine. Various h e u r i s t i c s are implemented and i n c o r p o r a t e d into  the network  relabel  routine  generation  a warm  routine,  start.  and give  the push  The performance  o f each  h e u r i s t i c i s judged by the percentage r e d u c t i o n i n s o l u t i o n time o f the push r e l a b e l networks  chosen  heuristics.  r o u t i n e over  to show a  The three  range  networks  those  instances of  o f performance are generated  blockmod data which i s a r t i f i c i a l l y a r e a l mine.  three  generated  from the  to represent  There are two c l a s s e s of h e u r i s t i c s .  that push flow using  of the  a r c information only.  Firstly, Secondly  those that push flow u s i n g node information a l s o . Class  1  MINIMUM  l  x  We know that i n order to remove blocks on one l a y e r we need to remove blocks from the l a y e r s above t h i s l a y e r . way  the network i s generated  the  central  The  the ore body g e n e r a l l y l i e s i n  (row,column) area.  27  Therefore  we  expect the  central  blocks  solution. is  The  head p a i r .  layer  offsets. straight  be  i n the  d i s t a n c e . Each arc has  optimal consider a  tail,  The d i f f e r e n c e between the t a i l ' s row number and row  we  number  have  a  is  column  the and  row a  d i s t a n c e i s then d e f i n e d as the row offset.  to  and most obvious h e u r i s t i c we x  head's  Similarly  first  upper  the minimum l  based on  the  i n the  The  l  norm i s the sum  x  So a smaller l  x  f o r and  offset layer  of  this  offset.  arc.  The  l  x  o f f s e t plus the column  of the absolute values  of  distance means an arc that goes up  a smaller l a t e r a l d e v i a t i o n . Therefore  we  want to push flow on minimum l distance arcs s i n c e they push x  flow s t r a i g h t up s t r a y i n g the l e a s t from the c e n t r a l b l o c k s . This  is  linked l i s t s  accomplished  through  creating  an  where the array index equals the l  the a r c . Then a l l arcs with the same l  x  x  array  of  distance of  d i s t a n c e are p a r t of  one l i n k e d l i s t so each time an arc i s generated we push flow first  to the  from  minimum  distance  sink i f p o s s i b l e , and l  a  distance  linked l i s t s  linked  then to arcs list  to  beginning  increasing  1  a l t e r i n g the excess on the r e s p e c t i v e  nodes and the flow on the a r c s . The mean s o l u t i o n times with and without  the h e u r i s t i c  are shown below f o r the r e p r e s e n t a t i v e set of networks.  28  Push-Rel  Reduction  .55  . 63  13 %  4277  1.12  1.23  9 %  4097  1.78  1.8  1 %  Network  Nodes  a60  2813  b45 c50  MAXIMUM  Heuristic  Z  We define the z distance of any arc as z =layer o f f s e t . We  push flows on arcs i n order of decreasing l a y e r  Arcs  connected  to  higher  layers  get  flow  first  offset.  with  exception of arcs to the sink g e t t i n g flow f i r s t . Here we not care i f flow i s moving away from the c e n t r a l b l o c k s as long as i t s going up performance of t h i s  as  h e u r i s t i c was  fast  the do  (row, column)  as p o s s i b l e .  The  t e s t e d on blockmod and a  sample f o l l o w s : Network  Nodes  a60  2813  b45 c50  MAXIMUM  We  l  Heuristic  Push-Rel  Reduction  .57  .63  10 %  4277  1.20  1.23  2 %  4097  1.8  1.8  0 %  x  know  that  before  any  block  is  in  the  optimal  s o l u t i o n i t s value must be greater than the value of the head of  any of i t s arcs not c o n s i d e r i n g the combined flow e f f e c t  from other nodes.  The c e n t r a l nodes are more l i k e l y to get  29  flow  from other  nodes than  the outer  argument can be made f o r pushing first  so as to reduce  stage.  flows t o the outer blocks  reallocation  In the maximum  l  flow  x  nodes. Therefore an  o f flows  at a  i s pushed  on  latter  arcs i n  decreasing order of l distance with the exception o f arcs to x  sink  getting  flow  first.  The performance  was  t e s t e d on  blockmod and the r e s u l t s f o l l o w : Network  Nodes  a60  2813  b45  4277  1.23  c50  4097  1.8  MAXIMUM  Z  From  -  Heuristic .62  M I N I M U M  l  Push-Rel  Reduction  .63  2 %  1.23  0 %  1.8  0 %  x  the preceding  results,  i t appears  that  pushing  flow on arcs i n the upward d i r e c t i o n i s b e t t e r than  pushing  flow on arcs away from the centre i n the l a t e r a l  direction.  From t h i s we i n f e r that we should push flows on arcs with the highest slope. would l i k e  The slope o f an a r c i s given by z/l . 1  to push flow on arcs with higher  w i t h preference given t o flow to s i n k . this  i s that there  therefore  infinite  are arcs with  l  x  d i s t a n c e o f zero and  heuristic.  on various combinations  30  first,  The d i f f i c u l t y with  slope and the above mentioned  amounts to the same as the minimum l we pushed flows  x  slopes  We  procedure Therefore  o f Max f = ( a z - b l l )  where the c o e f f i c i e n t s upward and  lateral  a and b give d i f f e r e n t  movement of  flow.  The  weights to  results  are  as  follows f o r a = 2 and b = 1: Network  Nodes  a60  2813  b45 c50  BOUNDED  We layers.  Push-Rel  Reduction  .57  .63  10 %  4277  1.18  1.23  4 %  4097  1.79  1.8  1 %  M I N I M U M  l  Heuristic  x  know that i t i s p r e f e r a b l e to send flow to the top The  question then i s that i s there a l i m i t on  the  flow beyond which i t i s no longer advantageous to push flows to  the top l a y e r s .  The  next  question i s how  do we  choose  t h i s l i m i t or bound on the amount of flow to send on an a r c . As  a l l the arcs have i n f i n i t e c a p a c i t y except those flowing  to the sink.  The bound chosen depends on the l a y e r number of  the head of the a r c .  For example with a 45 degree d i p on  each azimuth and waste block values of -W push  more  than  max(excess t a i l , a r c s with head  5W 5W)  to  a  last  layer  we do not need to  node.  So  a  flow  of  i s pushed i n i n c r e a s i n g 11 d i s t a n c e on  (layer upper bound-1) and so on. The  results  of t h i s h e u r i s t i c were promising except i t r e q u i r e s knowledge of waste block values and number of arcs which we do not have u n t i l we see the problem.  The r e s u l t s are as f o l l o w s :  31  Network  Nodes  a60  2813  b45 c50 NO  Heuristic  Push-Rel  Reduction  .55  .63  13 %  4277  1.10  1.23  11 %  4097  1.78  1.8  1 %  FLOWS I N K  For each of the h e u r i s t i c above, we p r e f e r to send to  the  sink  heuristic. a v o i d any The  first  and  then to  the  natural  to  I t i s only  i n d i c a t e d by  the  t r y what happens i f  we  arcs flowing to the sink rather than p r e f e r them.  performance  with  minimum  l  blockmod and the r e s u l t s were as Network  Nodes  a60  2813  b45 c50 CLASS  arcs  flow  h e u r i s t i c was  x  tested  on  follows:  Heuristic  Push-Rel  Reduction  .65  .63  -3 %  4277  1.26  1.23  -2 %  4097  1.83  1.8  -2 %  j u s t the  c h a r a c t e r i s t i c s of  2  We  have been c o n s i d e r i n g  the  arc without  considering  The  next set of h e u r i s t i c s use  and  nodes.  From now  on,  distance g i v i n g preference best h e u r i s t i c but we  any  we  information information  push on  arcs  on  the  nodes.  about both  with minimum  to flow to sink since t h i s was  also apply information  32  arcs l  t  the  from the nodes.  TOWARDS P O S I T I V E  BLOCKS  We p r e f e r p o s i t i v e blocks over negative blocks so we push on arcs whose head  i s positive  valued.  given to arcs connected to the sink. arc  with  l  minimum  x  distance only  First  preference i s  Secondly we push on the i f the value [head] i s  p o s i t i v e otherwise we push on the a r c with second d i s t a n c e i f i t s head i s p o s i t i v e and so on.  lowest  l  r  Unfortunately  the performance of t h i s h e u r i s t i c was not good when t e s t e d on blockmod as shown below: Network  Nodes  Heuristic  Push-Rel  Reduction  a60  2813  .63  .63  0 %  b45  4277  1.22  1.23  1 %  c50  4097  1.80  1.8  0 %  TOWARDS N E G A T I V E  BLOCKS  The only l o g i c behind using t h i s h e u r i s t i c i s that s i n c e i t s opposite had such a bad performance t h i s should perform very well.  But once again i t s performance was very bad as shown  below: Network  Nodes  Heuristic  Push-Rel  Reduction  a60  2813  .65  .63  -3 %  b45  4277  1.25  1.23  -2 %  c50  4097  1.83  1.8  -2 %  33  TOWARDS V E R Y P O S I T I V E  The  BLOCKS  reasoning behind  two h e u r i s t i c s  t h i s was that i t i s p o s s i b l e that the  above  (push  to p o s i t i v e ,  push to negative)  don't a f f e c t performance because they r e a l l y do not consider how p o s i t i v e or negative the blocks are i . e . a block of -1 i s very d i f f e r e n t from a block of -12500 yet are t r e a t e d i n the same manner.  Therefore, we push on arcs with i n c r e a s i n g 1  1  d i s t a n c e g i v i n g preference t o flow t o sink but pushing on  arcs whose head have  c a r r i e d on the t a i l  a greater value  than  i . e . very p o s i t i v e b l o c k s .  only  the excess The r e s u l t s  from t e s t i n g on blockmod are as f o l l o w s : Network  Nodes  Heuristic  Push-Rel  Reduction  a60  2813  .58  .63  8 %  b45  4277  1.15  1.23  7 %  c50  4097  1.78  1.8  1 %  TOWARDS V E R Y N E G A T I V E  For  BLOCKS  the purpose o f completeness we push on arcs with  increasing 1  1  distance g i v i n g preference to flow to sink but  pushing on arcs whose head have a negative value greater than the excess on t a i l .  The r e s u l t s are as f o l l o w s :  Network  Nodes  Heuristic  Push-Rel  Reduction  a60  2813  .65  .63  -3 %  b45  4277  1.26  1.23  -2 %  c50  4097  1.80  1.8  -2 %  34  ANALYSIS  &  CONCLUSION  The average  (over the sample s i z e o f three)  reduction  i n s o l u t i o n time f o r a l l the h e u r i s t i c s i s as f o l l o w s . tests  Other  s i m i l a r to these were done on sab02 confirming  these  r e s u l t s but s t i l l the sample s i z e i s small and the number o f base instances  (2) i s a l s o small.  (1)  Bounded minimum 1  8%  (2)  Minimum l  8%  (3)  Maximum z - minimum l  (4)  Very p o s i t i v e  5%  (5)  Maximum z  4%  (6)  Maximum l  1%  (7)  Positive  0%  (8)  Negative  -2%  (9)  Very negative  -2%  1  x  5%  a  t  (10) No flowsink  -2%  The h e u r i s t i c s with  the greatest percentage  i n mean s o l u t i o n time are bounded minimum l  x  reduction  and minimum 1}.  The extra information required to run bounded minimum l  x  not lead to a s i g n i f i c a n t reduction i n s o l u t i o n time.  does Also,  the bounded value f o r flow i s problem s p e c i f i c and r e q u i r e s knowledge  of  the  waste  block  values  and  .spv  files  beforehand. The  inherent  variability  35  i n s o l u t i o n times  i s very  little  ( i . e . .02 seconds at the most f o r a l l h e u r i s t i c s ) . The  d i f f e r e n c e i n s o l u t i o n times of these two h e u r i s t i c s and push r e l a b e l are s t r o n g l y s t a t i s t i c a l l y  s i g n i f i c a n t . As mentioned  before we do s u f f e r from a lack of more base instances (sab02 and blockmod) but an attempt  was made to generate  that are as d i f f e r e n t as p o s s i b l e .  networks  This i s f u r t h e r d i s c u s s e d  i n Chapter 5. On the b a s i s o f these runs the minimum l  x  adopted.  The  output  from  the  network  h e u r i s t i c was  flow  generator  (incorporated with the minimum l h e u r i s t i c ) i s now read i n t o x  a parser and maximal flow r o u t i n e s . be a l t e r e d to read an extended  The p a r s e r r o u t i n e must  format which i s r e q u i r e d f o r  reading i n the output o f the h e u r i s t i c i n order to give the maximal flow r o u t i n e a warm s t a r t . The output from the parser i s read i n t o Cherkassky and Goldberg's incorporate  (1994) push r e l a b e l r o u t i n e s with changes made to the warm s t a r t .  The networks are run on two  maximum flow routines with and without  the h e u r i s t i c .  The  same networks are run on D i n i c ' s algorithm without the warm s t a r t and our implementation  of FKS (chapter 2) to provide a  b a s i s f o r comparison with push r e l a b e l .  36  Illustrative  We  example  consider  a small problem  to i l l u s t r a t e  the steps  that the minimum l h e u r i s t i c incorporated network generation x  routine  runs  through.  The problem we consider has three  rows, three columns, and three l a y e r s . body  three  blocks.  dimensional  s t r u c t u r e has twenty  seven  Let's consider the ore body f i r s t :  Layer 1 -1 -1 10  block  So the o r i g i n a l ore  (Bottom layer) -1 -1 -1  -1 -1 10  -1 -1 -1  8 -1 8  -1 -1 -1  -1 -1 -1  Layer 2 -1 -1 -1 Layer 3 -1 -1 -1  The 3*3*3 ore body model i s read i n t o the r o u t i n e . For example, the value of block row 1, column 3, and l a y e r 2 i s 8.  The next  step i s to f i n d the lowest p o s i t i v e  layer i n  each row-column p a i r and put i t i n a two dimensional bottom[i] [j] = value.  array  I f there i s no p o s i t i v e l a y e r then i t s  value i s s e t to M. 37  bottom[i] [j] M  M  2  M  M  M  1  M  1  The following counters f o r upper bounds on rows, columns, and l a y e r s are s e t as rub = cub =lub =3.  Next we read i n the  information from the .spp f i l e which looks l i k e t h i s . NX: maximum number o f columns i n spp/spv f i l e NY: maximum number o f rows i n spp/spv f i l e NB: number of deepest l a y e r XC: midpoint column number i n spp/spv f i l e YC: midpoint row number i n spp/spv f i l e The azimuth i s a l i s t o f angles  ( a t o t a l o f 360°) at which  d i f f e r e n t wall slopes are permitted. of the angles of 0, 90, 180, 270 slope of 45 degrees. the  In t h i s example at each  we must have a minimum w a l l  By varying these parameters we can vary  spp/spv f i l e s which v a r i e s the c o n s t r a i n t s on the w a l l  slopes at d i f f e r e n t  angles.  38  NX, NY, NB, XC, YC, NP, BX, BY, BH= 7 10 AZIMUTH = .0 90.0 180.0 270.0 DIP = 45.0 45.0 45.0 45.0 001:00000003000000 002:00030302030300 003:00030201020300 004:03020101010203 005:00030201020300 006:00030302030300 007:00000003000000  7  3  4  4  4  10  10  A f t e r reading the spp f i l e we create an expanded bottom array bottom[i] [j] to allow f o r mining of blocks outside the ore body i n order to remove blocks at the edges o f the ore body three dimensional b l o c k s .  I t i s the s i z e o f t h i s block  structure which represents the number of blocks we would have i n our model i f we d i d not have a bounding r o u t i n e which i n t h i s case would be 7*7*3=142. dimensions (7,7).  equal  The new bottom a r r a y w i l l have  to o l d dimensions  +  (NX,NY) which means  The information from the o l d bottom i s t r a n s f e r r e d to  the new bottom a r r a y as (row=row + NY/2) and (column=column + NX/2). new bottom[i] [j] M  M  M  M  M  M  M  M  M  M  M  M  M  M  M  M  M  M  2  M  M  M  M  M  M  M  M  M  M  M  1  M  1  M  M  M  M  M  M  M  M  M  M  M  M  M  M  M  M  39  Next we  construct  a linked  row-column p a i r f o r each l e v e l . for  l a y e r 1 would contain  list  of each non-M bottom  For example our l i n k e d  two elements and t h e i r  list  respective  row-column p a i r s and f o r l a y e r 2 we have one element and i t s row-column p a i r .  We  then run through our l i n k e d  list  and  a p p l y the information a v a i l a b l e i n the spp f i l e by  putting  its  centre  to f i n d  out  what blocks need to be added to s a t i s f y the w a l l  (4,4) over each block i n the l i n k e d l i s t  restrictions.  I f any blocks  are needed  then we  slope  have  to  create new bottom blocks f o r that row-column p a i r . So we get an updated new_bottom[i][j].  40  new b o t t o m [ i ] [ j ] M  M  M  M  M  M  M  M  M  M  M  3  M  M  M  M  3  3  2  3  M  M  3  2  3  2  3  M  3  2  1  2  1  3  3  M  3  2  3  2  3  M  M  M  3  M  3  M  M  The next step i s to number the blocks i s some format. We  adopt a simple s e q u e n t i a l numbering  along each row numbering upward.  each column  system where we go  from i t s bottom  The block numbers then become as f o l l o w s :  41  layer  36 32  31  35  34, 33  27  26,  24  28  25 10  30  29,  12,  15,  17,  20,  22,  11  14,  16  19,  21  18  13 3  23  6  5  9  8  4  7  1  2  So our bounding s t r u c t u r e uses a t o t a l of 36 blocks as opposed to an o r i g i n a l  number of 142 b l o c k s .  p r i n t out each block and i t s value to the output  We  can  file.  now All  blocks outside the o r i g i n a l ore body can be given any value. In t h i s example they are given a value of -1.  42  We now input information form the .spv f i l e which looks like  this  NX, NY, NB, XC, YC, NP, BX, BY, BH= 7 10 AZIMUTH = .0 90.0 180.0 270.0 DIP = 45.0 45.0 45.0 45.0 001:00000000000000 002:00030000000300 003:00000001000000 004:00000101010000 005:00000001000000 006:00030000000300 007:00000000000000  7  We use t h i s f i l e to s e t up the a r c s .  By p l a c i n g the centre  (4,4)  3  4  4  4  10  10  over each block we can s e t up the arcs that l e a d out  from each block. In general, the order i n which you generate these arcs doesn't matter.  In our case we want to s e t up a  h e u r i s t i c which pushes flow as i t generates the arcs on arcs of i n c r e a s i n g l  x  d i s t a n c e so that we can .  Consequently, we  must generate these arcs according to ascending  1  1  distance.  We read each nonzero value from the spp f i l e and a s s i g n it  a row o f f s e t and a column o f f s e t number.  an array o f l i n k e d l i s t s  Then we create  where the array index equals the 1  d i s t a n c e o f each nonnegative value i n the spp f i l e .  2  Now we  can generate arcs by running through the l i n k e d l i s t o f each the array i n ascending  order o f the array  index.  For example, from the spp f i l e above the entry i n (4,4) has l  x  distance 0 and so i s the f i r s t  of the array element b[0] .  member o f the l i n k e d  list  S i m i l a r l y we have four members i n  43  the l i n k e d l i s t of array element b [ l ] with l  x  (5,4),  (4,5),  (4,3),  distance 1 i . e .  (3,4).  In order to run the h e u r i s t i c we need to a s s i g n excess on blocks and flows on arcs as we generate  the a r c s . A l l  p o s i t i v e value blocks are assigned an excess equal t o t h e i r v a l u e and the r e s t of the blocks have zero excess  to s t a r t  with. Once the h e u r i s t i c i s done we output  each a r c and i t s  flow and each block and i t s excess and i t s flow to the s i n k . The h e u r i s t i c has pushed excess to the top l a y e r s i n order to g i v e the maximal flow r o u t i n e a warm s t a r t . now  read  into  the parser  and the m o d i f i e d  This output i s maximal  flow  routines. We  see  decreasing  that  our  the number  bounding  o f blocks  procedure from  resulted  in  142 to 36 and the  h e u r i s t i c has pushed excess to the upper l e v e l s i n order t o give the maximal flow routine a warm s t a r t .  44  CHAPTER  5  Results  The until  usefulness  of  any  technique  cannot  i t i s a p p l i e d to an a c t u a l problem. We  be  measured  use  the  data  from a B r a z i l i a n copper mine (sab02) and data constructed to resemble  a real  mine  (blockmod) to  address  the  following  issues: 1) Whether the push r e l a b e l routine works w e l l i n p r a c t i c e on t h i s c l a s s of  graphs.  2) Whether we can take advantage of the s t r u c t u r e of an open pit  problem being solved with a generic maximum flow code.  3)  To  what  extent  does  the  network  generation  procedure  reduce the number of blocks. These questions are answered using both a small example and r e a l mine deposit data. The has  23 l a y e r s , 52 rows, and  blocks.  B r a z i l i a n copper mine(sab02)  80 columns f o r a t o t a l of 95680  The small example (blockmod) has 12 l a y e r s , 11 rows,  and 23 columns f o r a t o t a l of 3036 b l o c k s .  We  use these  two  data  sets to generate a number of d i f f e r e n t networks to  our  testing.  We  were  limited  instances of which r e a l l y only one other i s small and a r t i f i c i a l . have  more  base  instances.  to  only  these  i s a c t u a l data,  two and  base the  I d e a l l y i t would be b e t t e r to  Consequently  we  generated  networks to be as d i f f e r e n t as p o s s i b l e from each other.  45  do  the The  networks range  generated through d i f f e r e n t  from 2813  HP/Apollo  9000,  .spp  and  .spv  to 27926 nodes. We  run our r o u t i n e s  model  MB  730  with  64  RAM  with  a  files on a GNU  C  compiler and the implementations are w r i t t e n i n C.  We have t e s t e d on 4 d i f f e r e n t routines which are (1) The FKS c l o s u r e algorithm which we implemented (2)  Dinic's  algorithm  as  implemented  by  i n C.  Goldberg  and  Cherkassky (1990). (3) The  queue push  r e l a b e l implementation of Goldberg and  Cherkassky. (4) The highest l a b e l push r e l a b e l implementation of Goldberg and Cherkassky. We  implemented  incorporated generator  the  minimum  1  heuristic  1  which  i n t o Tom McCormick and Todd Stewart's  and  implemented  a  parser  routine  we  network  i n order  to  incorporate the warm s t a r t i n t o both push r e l a b e l r o u t i n e s . Solution  Time  (Push  Relabel)  Goldberg and Cherkassky performance and  FIFO  establishes  (1994) show that the e m p i r i c a l  f o r both push r e l a b e l routines )  i s better that  the  than  Dinic's.  highest  implementation performs b e t t e r  Their  paper  push  label also  relabel  than the FIFO push r e l a b e l  routine f o r a l l random problem sets.  46  label  ( highest  Goldberg and Cherkassky  perform t h e i r t e s t s on randomly generated data from the f i r s t DIMACS challenge.  The e m p i r i c a l performance  o f the push  r e l a b e l on actual data has not been tested as f a r as we know. Therefore we run a l l f i v e r o u t i n e s on r e a l data generated data  (sab02) and  (blockmod) to v e r i f y the e m p i r i c a l p r o p e r t i e s  established by Goldberg  and Cherkassky.  Table One gives the  s o l u t i o n times over a l l tested networks r e s p e c t i v e l y f o r FKS, Dinics, Push Relabel l  x  (FIFO), Push Relabel  h e u r i s t i c , Push Relabel  (FIFO) p l u s minimum  (Highest L a b e l ) , and Push Relabel  (Highest Label) plus minimum 1 h e u r i s t i c . 2  Figure One p l o t s  the s o l u t i o n times f o r FKS, D i n i c ' s , and Push R e l a b e l Push Relabel  (FIFO) plus  heuristic  (sab02 and blockmod) together  f o r both  (FIFO),  sets o f data  and s e p a r a t e l y .  Figure  p l o t s the same s o l u t i o n times from Figure One except  Two  f o r FKS  i n order to b e t t e r s c a l e the graph s i n c e FKS times are much larger  than  the other  routines.  Figure  s o l u t i o n times f o r FKS, Dinic's, Push Relabel and Push Relabel of data  p l o t s the  (Highest  Label)  (Highest Label) plus h e u r i s t i c f o r both sets  (sab02 and blockmod) together and s e p a r a t e l y .  Four p l o t s these FKS  Three  s o l u t i o n times  Figure  i n Figure Three except f o r  i n order to s c a l e the graph. The  r e s u l t s from t e s t i n g on a c t u a l data confirm  of Cherkassky and Goldberg  (1994) on randomly generated  The highest l a b e l push r e l a b e l implementation  47  those data.  i s the f a s t e s t  followed  by  FIFO  push  relabel  and  then  Dinic's.  Our  implementation o f FKS was the slowest. Solution  Time  (Heuristic)  The push r e l a b e l incorporated  with minimum l h e u r i s t i c x  performs better than j u s t the push r e l a b e l f o r both r o u t i n e s . Each routine i s run on the same network many times to check if  the  difference  in  solution  times  is  statistically  s i g n i f i c a n t . The s o l u t i o n and t o t a l times i n CPU seconds f o r three  networks  statistic  (A45, B45, and C60) are shown with  f o r d i f f e r e n c e i n mean s o l u t i o n time.  Heuristic A45 FIFO Solution Total 19.17 62.98 1 19.82 64.62 2 19.17 63.02 3 19.07 63.00 4 19.15 63.23 5 19.17 63.62 6 t = -14.10 B45 FIFO Solution Total 26.43 89.17 1 26.43 88.72 2 26.40 89.33 3 26.45 88.87 4 26.43 89.45 5 89.17 26.43 6 t = -94.36 A45 Highest Label Solution Total 14.47 58.48 1 14.45 58.55 2 14.40 58. 67 3 14.42 61.10 4 14.50 58.55 5 14.50 58. 67 6 t = -50.09  Push Relabel Total 63.65 63.48 63.42 63.18 63.67 64.03 P = .0000  Solution 20.88 20.90 20.88 20.80 20.88 20.95  Total 91.17 89.70 89.07 89.05 89.93 89.82 P = .0000  Solution 28.40 28.35 28.28 28.40 28.40 28.35  Total 58.50 58.68 58.58 65.15 58.70 58.73 .0000 P  Solution 15.78 .15.77 15.73 15.88 15.82 15.80  48  the t -  C60  FIFO Total 92.42 92.95 92.22 94.42 92.75 93.68 p = .0000  Solution Total 23.70 1 88.97 23.80 2 90.57 24.90 3 92.72 23.70 4 88.80 23.70 5 91.13 23.78 6 89.17 t = -23.18  Tables One and Two show the s o l u t i o n  Solution 28.52 28.43 28.47 28.40 28.50 28.48  and t o t a l times  f o r a l l networks with and without the h e u r i s t i c . These are also p l o t t e d i n Figures One to Four.  These r e s u l t s show that  the minimum l h e u r i s t i c s t a t i s t i c a l l y s i g n i f i c a n t l y improves x  the s o l u t i o n time performance of both push r e l a b e l Estimate  of  the Asymptotic  Growth  Rate f o r  routines.  Solution  Time  We are also i n t e r e s t e d i n the asymptotic growth rate o f an algorithm because i n p r a c t i c e the problem s i z e can be very large  for certain  relabel  does  applications.  indeed  have  We  the best  assess whether asymptotic  push-  growth i n  practice. We  run  the  regression  of  log(solution  time)  on  log(nodes) on the combined sab02 and blockmod data f o r a l l the  routines.  Plots  o f these  graphs f o r D i n i t z ,  Push-Relabel are shown on page 79. rates are as follows:  49  FKS, and  The asymptotic  growth  FKS  1.58  Dinic  1.82  PR(Q)  1.54  PR(Q)+H  1.53  PR(H)  1.51  PR(H)+H  1.50 ,  The  push  relabel  algorithm  has a b e t t e r  asymptotic  growth rate f o r t h i s c l a s s o f r e a l problems implying the problem s i z e increases improves even f u r t h e r . This  the performance o f push r e l a b e l illustrates  how w e l l  r e l a b e l r o u t i n e performs i n p r a c t i c e on a c t u a l  Total  that as  the push  data.  time  It  i s p l a u s i b l e that we might be concerned about the  t o t a l time taken to read the network, solve the maximum flow problem and output the maximum c l o s u r e . We see the t o t a l and s o l u t i o n times f o r each of the routines i n Tables 3, 4, 5, 6, 7, 8 r e s p e c t i v e l y . Also Figure 5 p l o t s the t o t a l time f o r a l l routines. The most s t r i k i n g t h i n g we n o t i c e i s that the t o t a l time  i s much greater  algorithms  than  the s o l u t i o n time  except the FKS closure algorithm. This  f o r a l l the observation  r a i s e s two p o i n t s . F i r s t l y , the push r e l a b e l algorithm i s so good i n p r a c t i c e that most of the time (see Table 9) i s spent  50  just  reading the network and  solving  i t . Secondly,  most  a very l i t t l e of  the  time  reading  i s spent  time  of  FKS  disappears because the parse routine doesn't have to create the overhead of source and sink arcs. That i s the FKS  closure  a l g o r i t h m works with the o r i g i n a l digraph and does not need extra a r c s . One p o i n t to n o t i c e i s that while the parser read time i s l i n e a r , the s o l u t i o n time i s not so therefore the r e l a t i v e advantage  that  FKS  enjoys  due  to  a  shorter  decreases as the number of nodes i n c r e a s e . 2813  nodes the t o t a l  relabel  heuristic  is  time  f o r FKS  2.82.  parser  time  For example with  i s 19.86  and  f o r push  For 27926 nodes t o t a l time i s  441.97 f o r FKS and 95.96 f o r push r e l a b e l h e u r i s t i c .  As the  problem s i z e has increased the d i f f e r e n c e i n t o t a l times has increased  significantly  from  17.04  to 345.01  illustrating  that the disadvantage of a large s u p e r l i n e a r s o l u t i o n o v e r r i d e s the advantage  of a l i n e a r  read time  f o r the  time FKS  routine. Bounding  It  i s seen that the network generator created by Todd  Stewart and Tom McCormick i s very e f f e c t i v e at bounding problem  size.  The  o r i g i n a l number of blocks i n the  the  copper  mine are 95,680 while the reduced number of blocks range from 27,926  to  18385 blocks.  Caccetta and  51  Giannini(1991)  also  reduce the problem s i z e by bounding the problem u s i n g a three dimensional  dynamic  programming  technique  of  Johnson  and  Sharpe. The routine  network  generator  is  altered  and  the  i s d i s a b l e d to check what happens i f we  expanded  bounding solve  the  (not bounded) model. The r e s u l t s f o r blockmod are  shown i n Table Nine.  We  notice  that  the  expanded model  i n f l a t e s the reading time more than the s o l u t i o n time.  The  s o l u t i o n time increases between 5 to 8 f o l d while the t o t a l time increases between 8 to 12 f o l d . well  the  graphs. We  push  relabel  works  This i l l u s t r a t e s  i n practice  on  this  how  set of  t r i e d to run the expanded model on sab02 but ran  out of memory space.  In fact, the bounded networks  generated  from sab02 are about the l a r g e s t models that can run on our machine.  Larger instances w i l l  Consequently  memory  s o l u t i o n time.  space  can  run out be  The Lerchs-Grossman  a  of memory space.  b i g g e r problem  than  technique overcomes t h i s  problem by running without an e x p l i c i t network, i . e . arcs are generated each time that they are required, for  time.  could be  It i s possible implemented  that  t r a d i n g memory  the p u s h - r e l a b e l  routine  i n a s i m i l a r manner t r a d i n g  solution  time f o r memory space. Conclusion  The r e s u l t s show that the e m p i r i c a l performance of push  52  relabel solution  i s better times  than and  Dinic's  and  asymptotic  i n c o r p o r a t i n g the minimum 1  1  FKS  both  solution  i n terms times.  of  Also,  h e u r i s t i c f u r t h e r improves  the  performance of both push r e l a b e l r o u t i n e s . There i s the need to t e s t against Lerchs Grossmann and F l o a t i n g Cone but a l a c k of money and time. The r e s u l t s a l s o i l l u s t r a t e that a s i g n i f i c a n t p o r t i o n o f the t o t a l time o f the push r e l a b e l i s read time and not s o l u t i o n time. This implies that the s o l u t i o n time of push r e l a b e l routine i s not the c o n s t r a i n i n g f a c t o r f o r u s i n g i t on  practical  problems  but  rather  the read time.  Further  research should aim on reducing the read time and not the solution which  time.  A hint  can be  taken from  the FKS  routine  has such low read time since i t deals with j u s t  the  i n t e r n a l network and does not need source and sink a r c s .  It  i s probable that one which  does not need  can implement to create  a push  source and  relabel sink  routine  arcs  which  would s i g n i f i c a n t l y reduce the t o t a l time of push r e l a b e l and thus make i t more s u i t a b l e  for practical  problems.  This  t h e s i s d i d not proceed f u r t h e r i n t h i s d i r e c t i o n due to l a c k of time but s t r o n g l y suggests t h i s research path. In conclusion,  the mining  community has  regarded the  network flow technique as being too slow and u s i n g too much memory, but  now  with modern implementations  53  such  as  push  relabel  and also  push r e l a b e l  plus  should be outdated. The computational  heuristic  this  belief  complexity o f the push  r e l a b e l which i s improved by the h e u r i s t i c i s so good that we w i l l run i n t o problems o f reading i n the network and memory space much before  the network  excessive.  54  flow  solution  time  becomes  Table 1 (Solution time in sees)  Networks  Nodes  FKS  Dinics  a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45 a60 b60 a55 b55 a50 b50 c60 a45 c55 b45 c50 c45  2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455 18385 20281 20346 21834 22644 23841 25560 25668 26108 26299 26935 27926  19.78 20.33 20.73 21 20.62 19.35 21.38 21.37 21.4 18.2 18.63 18.97 379.05 401.03 391.12 409.13 405.98 416.18 417.22 406.3 433.63 428.5 431.83 441.87  0.68 1.67 0.87 0.98 1.85 1.05 1.97 1.67 1.96 1.19 1.28 1.6 16.28 28.4 19.1 31.53 31.85 37.27 52.5 43.58 63.87 64.82 74.98 62.13  Push-Rel Push-Rel Push-Rel Push-Rel FIFO Heuristic H L Heuristic 0.63 0.55 0.47 0.42 1.17 1.03 0.88 0.72 0.97 0.77 0.77 0.65 1.87 1.32 0.85 0.65 1.65 1.52 1.23 1.22 1.33 1.12 1.23 0.93 1.97 1.9 1.45 1.33 1.32 1.33 1.18 1.15 1.8 1.78 1.41 1.38 1.13 0.98 1.03 0.98 1.23 1.12 1.37 1.27 1.47 1.43 1.2 1.11 10.65 9.4 8.27 8.13 16.62 15.12 13.21 12.21 20.73 14.08 10.47 13.43 25.9 22.22 16.07 15.43 20.73 19.55 15.75 13.32 27.5 25.63 19.32 17.82 28.47 23.78 19.9 18 20.88 19.27 15.95 14.15 31.18 28.55 21.93 18.13 28.32 26.38 20.97 19.17 30.43 30.08 26.89 20.98 33.06 27.18 22.95 21.18  55  Table 2 (Total time in sees)  Networks  Nodes  FKS  Dinics  a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45 a60 b60 a55 b55 a50 b50 c60 a45 c55 b45 c50 c45  2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455 18385 20281 20346 21834 22644 23841 25560 25668 26108 26299 26935 27926  19.86 20.41 20.85 21.35 20.68 19.51 21.48 21.42 21.61 18.24 18.85 19.62 379.12 401.08 391.17 409.2 406.3 416.25 417.87 406.37 433.7 428.55 431.92 441.97  2.97 5.87 3.82 6.43 9.13 4.87 8.92 6.93 8.97 3.94 4.57 5.67 42.62 73.1 57.55 91.8 87.78 109.88 116.67 86.72 140.87 127.05 153 136.8  Push-Rel Push-Rel Push-Rel Push-Rel FIFO Heuristic HL Heuristic 2.97 2.93 2.85 2.82 6.17 5.43 5.53 5.32 3.97 3.88 3.77 3.67 6.88 6 5.97 5.67 9.77 7.45 7.27 7.2 5.55 5.12 5.05 5.05 8.55 8.62 8.15 8.07 6.3 6.35 6.32 6.22 8.6 8.5 9.02 9 3.97 3.85 3.97 3.73 4.63 4.43 4.6 4.48 5.6 5.55 5.57 5.51 36.73 36.68 33.92 33.35 58.98 58.57 54.45 54.87 73.72 51.1 66.5 46.17 83.17 85.85 75.63 75.78 75.43 74.63 66.57 65.33 99.43 98.37 91.08 89.43 92.6 89.08 82.73 84.52 63.67 63.32 58.4 57.5 107.72 106.37 98.1 97.88 89.38 89.2 81.43 80.67 110.77 105.12 108.73 100.35 102.95 107.35 96.95 95.96  56  Table 3 (FKS)  Network a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45 a60 b60 a55 b55 a50 b50 c60 a45 c55 b45 c50 c45  Nodes 2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455 18385 20281 20346 21834 22644 23841 25560 25668 26108 26299 26935 27926  Solution 19.78 20.33 20.73 21 20.62 19.35 21.38 21.37 21.4 18.2 18.63 18.97 379.05 401.03 391.12 409.13 405.98 416.18 417.22 406.3 433.63 428.5 431.83 441.87  Total 19.86 20.41 20.85 21.35 20.68 19.51 21.48 21.42 21.61 18.24 18.85 19.62 379.12 401.08 391.17 409.2 406.3 416.25 417.87 406.37 433.7 428.55 431.92 441.97  Difference 0.08 0.08 0.12 0.35 0.06 0.16 0.1 0.05 0.21 0.04 0.22 0.65 0.07 0.05 0.05 0.07 0.32 0.07 0.65 0.07 0.07 0.05 0.09 0.1  Time v e r s u s N o d e s (Sab02) 450 - p s r 5 = =  370 -| 18000  , 19000  ,, ,  , 20000  i 21000  i 22000  , 23000  1 24000  Nodes  57  i - ^ —  , 25000  , 26000  , 27000  !| 28000  Table 4 (Dinic)  Network a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45 a60 b60 a55 b55 a50 b50 c60 a45 c55 b45 C50 c45  Nodes 2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455 18385 20281 20346 21834 22644 23841 25560 25668 26108 26299 26935 27926  Solution 0.68 1.67 0.87 0.98 1.85 1.05 1.97 1.67 1.96 1.19 1.28 1.6 16.28 28.4 19.1 31.53 31.85 37.27 52.5 43.58 63.87 64.82 74.98 62.13  Total 2.97 5.87 3.82 6.43 9.13 4.87 8.92 6.93 8.97 3.94 4.57 5.67 42.62 73.1 57.55 91.8 87.78 109.88 116.67 86.72 140.87 127.05 153 136.8  Difference 2.29 4.2 2.95 5.45 7.28 3.82 6.95 5.26 7.01 2.75 3.29 4.07 26.34 44.7 38.45 60.27 55.93 72.61 64.17 43.14 77 62.23 78.02 74.67  Time versus Nodes (Sab02) 160  0 -| 18000  1 20000  1 22000  = H 24000  1 26000  Nodes  58  1 28000  Table 5 (Push relabel(FIFO))  Network a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45 a60 b60 a55 b55 a50 b50 c60 a45 c55 b45 c50 c45  Nodes 2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455 18385 20281 20346 21834 22644 23841 25560 25668 26108 26299 26935 27926  Solution 0.63 1.17 0.97 1.87 1.65 1.33 1.9 1.32 1.8 1.13 1.23 1.47 10.65 16.62 20.73 25.9 20.73 27.5 28.47 20.88 31.18 28.32 30.43 33.06  Total 2.97 6.17 3.97 6.88 9.77 5.55 8.55 6.3 8.6 3.97 4.63 5.6 36.73 58.98 73.72 85.85 75.43 99.43 92.6 63.67 107.72 89.38 110.77 102.95  Difference 2.34 5 3 5.01 8.12 4.22 6.65 4.98 6.8 2.84 3.4 4.13 26.08 42.36 52.99 59.95 54.7 71.93 64.13 42.79 76.54 61.06 80.34 69.89  T i m e v e r s u s N o d e s (Sab02) 120 -i  18000  20000  22000  24000  Nodes  59  26000  28000  Table6(Heuristic(FIF0))  Network a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45 a60 b60 a55 b55 a50 b50 c60 a45 c55 b45 c50 c45  Nodes 2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455 18385 20281 20346 21834 22644 23841 25560 25668 26108 26299 26935 27926  Solution 0.55 1.03 0.77 1.32 1.52 1.23 1.97 1.33 1.78 0.98 1.12 1.43 9.4 15.12 14.08 22.22 19.55 25.63 23.78 19.27 28.55 26.38 30.08 27.18  Total 2.93 5.43 3.88 6 7.45 5.12 8.62 6.35 8.5 3.85 4.43 5.55 36.68 58.57 51.1 83.17 74.63 98.37 89.08 63.32 106.37 89.2 108.73 107.35  Difference 2.38 4.4 3.11 4.68 5.93 3.89 6.65 5.02 6.72 2.87 3.31 4.12 27.28 43.45 37.02 60.95 55.08 72.74 65.3 44.05 77.82 62.82 78.65 80.17  Time versus Nodes (Sab02) 120 -,  0 -| 18000  1  20000  , 22000  , 24000  Nodes  60  i 26000  1  28000  Table 7 (Push relabel(HL))  Network a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45 a60 b60 a55 b55 a50 b50 c60 a45 c55 b45 c50 c45  Nodes 2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455 18385 20281 20346 21834 22644 23841 25560 25668 26108 26299 26935 27926  Solution 0.47 0.88 0.77 0.85 1.23 1.12 1.45 1.18 1.41 1.03 1.37 1.2 8.27 13.21 13.43 16.07 15.75 19.32 19.9 15.95 21.93 20.97 26.89 22.95  Total 2.85 5.53 3.77 5.97 7.27 5.05 8.15 6.32 9.02 3.97 4.6 5.57 33.92 54.45 66.5 75.63 66.57 91.08 82.73 58.4 98.1 81.43 105.12 96.95  Difference 2.38 4.65 3 5.12 6.04 3.93 6.7 5.14 7.61 2.94 3.23 4.37 25.65 41.24 53.07 59.56 50.82 71.76 62.83 42.45 76.17 60.46 78.23 74  T i m e v e r s u s N o d e s (Sab02) 120  0 -I 18000  1 20000  1—1  ,  22000  24000  • 26000  Nodes  61  28000  Table 8 (Heuristic(HL))  Network a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45 a60 b60 a55 b55 a50 b50 c60 a45 c55 b45 c50 c45  Nodes 2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455 18385 20281 20346 21834 22644 23841 25560 25668 26108 26299 26935 27926  Solution 0.42 0.72 0.65 0.65 1.22 0.93 1.33 1.15 1.38 0.98 1.27  Total 2.82 5.32 3.67 5.67 7.2 5.05 8.07 6.22 9 3.73 4.48 5.51 33.35 54.87 46.17 75.78 65.33 89.43 84.52 57.5 97.88 80.67 100.35 95.96  1.11 8.13 12.21 10.47 15.43 13.32 17.82 18 14.15 18.13 19.17 20.98 21.18  Difference 2.4 4.6 3.02 5.02 5.98 4.12 6.74 5.07 7.62 2.75 3.21 4.4 25.22 42.66 35.7 60.35 52.01 71.61 66.52 43.35 79.75 61.5 79.37 74.78  Time v e r s u s N o d e s (Sab02) 120  18000  -  20000  22000  24000  Nodes  62  26000  28000  Table 9 (Expanded)  FIFO Network  Nodes  a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45  2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455  Highest Label Network Nodes a60 a55 b60 b55 a50 c60 b50 c55 c50 a45 b45 c45  2813 3065 3200 3430 3509 3663 3781 3838 4097 4120 4277 4455  Push-Rel Push-Rel Expanded Expanded Solution Total Solution Total 0.55 2.93 3.98 22.13 1.03 5.43 11.93 73.87 0.77 3.88 8.03 44.68 1.32 6 14.65 84.2 1.52 7.45 7.77 79.43 1.23 5.12 11.92 66.38 1.97 8.62 19.62 109.65 1.33 6.35 17.08 115.17 1.78 8.5 memory memory 0.98 3.85 7.28 35.47 4.43 9.47 48.02 1.12 13.62 1.43 5.55 68  Push-Rel Push-Rel Expanded Expanded Solution Solution Total Total 0.42 2.82 2.98 26.45 0.72 5.32 8.27 70.02 0.65 3.67 5.45 42.53 0.65 5.67 9.53 78 1.22 7.2 80.77 9.58 0.93 5.05 7.68 61.8 1.33 8.07 12.02 102.45 6.22 11.07 88.13 1.15 memory memory 1.38 9 0.98 3.73 4.75 33.55 1.27 4.48 6.25 44.35 5.51 8.45 62.43 1.11  63  Figure 1 (Solution time)  Solution time versus Nodes  —•—FKS —{§— Dinic — * — Push-Relabel(FIFO) —X—Heuristic  12000  17000  22000  27000  Nodes  Solution time versus Nodes (Blockmod) 25 20  •FKS  15  - Dinic Push-Relabe(FIFO)  I 10  -X— Heuristic  0 42700  3200  3700  4200  4700  Nodes  Solution time versus Nodes (Sab02)  ••—FKS  «• 300  •—Dinic  | 250 "| 200 150  - i s — Push-Relabel(FIFO) Heuristic  100 50 0 18000  20000  22000  24000  26000  Nodes  64  28000  Figure 2 (Solution time no F K S )  Solution time versus Nodes (Blockmod)  •Dinic -Push-Relabel(FIFO) -Heuristic  Solution time versus Nodes  (Sab02)  •Dinic -Push-Relabel(FIFO) Heuristic  18000  20000  22000  26000  24000 Nodes  65  28000  Figure 3 (Solution time)  Solution time versus Nodes (Blockmod) 25  20 15  -k  -•—Dinic -»-FKS ~*  10  Series3  - H — Heuristic I ^ ^ S B  2800  3000  3200  3400  3600  3800  4000  4200  4400  Nodes  Solution time versus Nodes (Sab02) 450 400 350 17 300 o 250  -•—FKS  ~V  ~ i t — Push-Relabel(HL) |  H  - • — Dinic  200  -X—Heuristic  150  18000  20000  22000  26000  24000 Nodes  66  28000  Figure 4 (Solution time no FKS)  Solution time versus nodes (Blockmod)  • Dinic  (A O  -Push-Relabel(HL)  a  •Heuristic  E  2800  3300  4300  3800 Nodes  Solution time versus Nodes (Sab02)  -Dinic -Push-Relabel(HL) -Heuristic  18000  20000  22000  24000  26000  Nodes  67  28000  Figure 5 (Total time)  Total time versus Nodes  2800  7800  12800  17800  22800  27800  Nodes  Total time versus Nodes (Blockmod) 25 20  1  -b-  -•—FKS  15  -f§— Dinic  10  ™ir- - Push-Relabel(HL) - X — Heuristic  2800  3300  3800  4300  Nodes  Total time versus Nodes (Sab02)  -•—FKS -*—Dinic - A — Push-Relabel(HL) | -H—Heuristic  18000  20000  22000  24000  26000  Nodes  68  28000  Log(Sol. time) vs Log(No.Nodes)  Dinitz  •Seriesl  o  (/} at  o  3.4  3.6  3.8  4  4.2  4.4  4.6  Log Nodes  FKS  -Seriesl  3.8  4  4.2  4.6  Log Nodes  Push-Relabel 2.8 2.3 1.8 -Seriesl  1.3 o  in ui  o  0.8 0.3 -0.2 3.4  3.6  3.8  4  4.2  Log Nodes  69  4.4  4.6  REFERENCES AND BIBLIOGRAPHY 1.  Caccetta, L. And L. M . Giannini (1985), On bounding techniques for the open pit limit problem, Proceedings of the Australasian Institute of Mining and Metallurgy 290, 87-89.  2.  Caccetta, L. and L. M . Giannini (1986), Optimisation techniques for the open pit limit problem, Proceedings of the Australasian Institute of Mining and Metallurgy 291, 57-63.  3.  Caccetta, L. andL. M . Giannini (1988a), An application of discrete mathematics in the design of an open pit limit, Discrete Applied Mathematics 21, 1-19.  4.  Caccetta, L. andL. M . Giannini (1988b), The generation of minimum search patterns in the optimum design of open pit mines, Proceedings of the Australasian Institute of Mining and Metallurgy 293, 57-61.  5.  Caccetta, L. andL. M . Giannini (1990), Application of Operations Research techniques in open pit mining, Asian-Pacific Operations Research: APORS'88, 707724  6.  Chen, T., 1976," 3D Pit Design with variable wall slope capabilities, "14th Applications of Computers in the mineral Industries Symposium, R. V . Ramani, ed., AIME, New York.  7.  Cherkassky, B.V. and Goldberg, A.V. (1994), On implementing Push-Relabel Method for the Maximum Flow problem, Technical Report Stanford University.  8.  Faaland, B., Kim. K. and Schmitt. T., 1990, A new algorithm for computing the maximal closure of a graph, Management Science, Vol. 36, No.3.  9.  Johnson, T.B., 1973, " A Comparative Study of Methods for determining Ultimate Open-Pit Mining Limits," 11th Applications of Computers in the Mineral Industries Symposium, University of Arizona, Tucson, A Z .  10.  Johnson, T.B., 1968, " Optimum Open-Pit Mine Production Scheduling, "Operations Research Centre, University of California, Berkeley, 120 pp.  11.  Johnson, T.B., and Sharp, W. R., 1971, A Three-Dimensional Dynamic Programming Method for Optimal Open Pit Design, U S B M Report of Investigations 7553.  12.  Kim, Y . C . , 1978. "Ultimate Pit Limit Design Methodologies using Computer ModelsThe State of the Art," Mining Engineering, October 1978, pp. 1454-1459. 70  13.  Kim, Y . C . , Cai, W., and Meyer, W.L., Comparison of microcomputer-based optimum pit limit design algorithms, "Society of Mining Engineers.  15.  Lemieux, Marc, 1979, "Moving Cone Optimising Algorithm", Computer Methods for the 80's in the Mineral Industry, ed. A. Weiss, Port City Press, Baltimore, M D , pp. 329-345.  16.  Lerchs, H . , Grossmann, IF., 1965, Optimum Design of Open-Pit Mines" Transactions, C.I.M., Vol. LXV111, pp. 17-24.  17.  Lipkewich, M.P., Borgman, L., 1969, "Two-and-Three Dimensional Pit Design Optimisation Techniques", A Decade of Digital Computing in the Minerals Industry, ed. A. Weiss, S M E of ATME, New York, pp. 505-523.  18.  Picard, J., 1976, Maximal Closure of a Graph and applications to combinatorial problems. Management Science, Vol. 22, No. 11.  71  

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
Chile 10 0
United States 5 0
China 5 2
Serbia 3 0
Canada 1 1
City Views Downloads
Unknown 8 21
Beijing 4 0
Belgrade 3 0
Ashburn 3 0
Santiago 2 0
Ottawa 1 0
Bellevue 1 0
Sunnyvale 1 0
Changsha 1 2

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}
Download Stats

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0087587/manifest

Comment

Related Items