J. H. Rubinstein and D. Thomas :
The Steiner problem of shortest networks ,
1988 .
From unpublished proceedings of the third Australian teletraffic research seminar (Melbourne, November 1988).
misc
People
BibTeX
@misc {key83003713,
AUTHOR = {Rubinstein, J. H. and Thomas, D.},
TITLE = {The {S}teiner problem of shortest networks},
YEAR = {1988},
PAGES = {14 pp.},
NOTE = {From unpublished proceedings of the
third {A}ustralian teletraffic research
seminar (Melbourne, November 1988).},
}
J. H. Rubinstein and D. Thomas :
Minimal cost networks in the plane ,
1989 .
From unpublished proceedings of the fourth Australian teletraffic research seminar (Bond University, Robina, Australia, December 1989).
misc
People
BibTeX
@misc {key87839045,
AUTHOR = {Rubinstein, J. H. and Thomas, D.},
TITLE = {Minimal cost networks in the plane},
YEAR = {1989},
PAGES = {8 pp.},
NOTE = {From unpublished proceedings of the
fourth {A}ustralian teletraffic research
seminar (Bond University, Robina, Australia,
December 1989).},
}
J. H. Rubinstein and D. A. Thomas :
“A variational approach to the Steiner network problem Ann. Oper. Res.
33 : 6
(1991 ),
pp. 481–499 .
MR
1140992 Zbl
0734.05040 article
Abstract
People
BibTeX
Suppose \( n \) points are given in the plane. Their coordinates form a \( 2n \) -vector \( X \) . To study the question of finding the shortest Steiner network \( S \) connecting these points, we allow \( X \) to vary over a configuration space. In particular, the Steiner ratio conjecture is well suited to this approach and short proofs of the cases \( n = 4,\,5 \) are discussed. The variational approach was used by us to solve other cases of the ratio conjeture (\( n = 6 \) , see [Rubinstein and Thomas 1991] and for arbitrary \( n \) points lying on a circle). Recently, Du and Hwang have given a beautiful complete solution of the ratio conjecture, also using a configuration space approach but with convexity as the major idea. We have also solved Graham’s problem to decide when the Steiner network is the same as the minimal spanning tree, for points on a circle and on any convex polygon, again using the variational method.
@article {key1140992m,
AUTHOR = {Rubinstein, J. H. and Thomas, D. A.},
TITLE = {A variational approach to the {S}teiner
network problem},
JOURNAL = {Ann. Oper. Res.},
FJOURNAL = {Annals of Operations Research},
VOLUME = {33},
NUMBER = {6},
YEAR = {1991},
PAGES = {481--499},
DOI = {10.1007/BF02071984},
NOTE = {MR:1140992. Zbl:0734.05040.},
ISSN = {0254-5330},
}
J. H. Rubinstein and D. A. Thomas :
“The Steiner ratio conjecture for six points J. Comb. Theory, Ser. A
58 : 1
(September 1991 ),
pp. 54–77 .
MR
1119701 Zbl
0739.05034 article
Abstract
People
BibTeX
The Steiner problem is to find a shortest network (tree) \( S \) in the plane \( \mathbf{R}^2 \) connecting a given set \( X \) of \( n \) points. There is an algorithm due to Melzak [1961] for finding such an \( S \) , however, determining \( S \) has been shown to be an NP-complete problem [Garey, et al. 1977]. Let \( T \) be a shortest tree connecting the points of \( X \) and with vertices only at these points. \( T \) is called a minimal spanning tree and there is a well-known algorithm due to Prim [1957] and Kruskal [1956] for finding \( T \) in polynomial time. Let \( L_S \) and \( L_T \) denote the lengths of \( S \) and \( T \) , respectively, and let \( \rho = L_S/L_T \) . \( \rho \) is called the Steiner ratio. Gilbert and Pollak [1968] conjectured that \( \rho \geq \sqrt{3}/2 \) and this has been shown to be true for \( n=3 \) [Gilbert and Pollak 1968], 4 [Pollak 1978; Du, et al. 1982], and 5 [Du, et al. 1985]. In [Rubinstein and Thomas 1991] new proofs for the cases \( n=3 \) , 4, and 5 are given using a technique from variational calculus.
In this paper we prove the Steiner ratio conjecture for six points. We use the variational approach discussed in detail in [Rubinstein and Thomas 1991].
@article {key1119701m,
AUTHOR = {Rubinstein, J. H. and Thomas, D. A.},
TITLE = {The {S}teiner ratio conjecture for six
points},
JOURNAL = {J. Comb. Theory, Ser. A},
FJOURNAL = {Journal of Combinatorial Theory. Series
A},
VOLUME = {58},
NUMBER = {1},
MONTH = {September},
YEAR = {1991},
PAGES = {54--77},
DOI = {10.1016/0097-3165(91)90073-P},
NOTE = {MR:1119701. Zbl:0739.05034.},
ISSN = {0097-3165},
CODEN = {JCBTA7},
}
J. H. Rubinstein, D. A. Thomas, and J. F. Weng :
“Degree-five Steiner points cannot reduce network costs for planar sets Networks
22 : 6
(1992 ),
pp. 531–537 .
MR
1178862 Zbl
0774.05032 article
Abstract
People
BibTeX
@article {key1178862m,
AUTHOR = {Rubinstein, J. H. and Thomas, D. A.
and Weng, J. F.},
TITLE = {Degree-five {S}teiner points cannot
reduce network costs for planar sets},
JOURNAL = {Networks},
FJOURNAL = {Networks},
VOLUME = {22},
NUMBER = {6},
YEAR = {1992},
PAGES = {531--537},
DOI = {10.1002/net.3230220604},
NOTE = {MR:1178862. Zbl:0774.05032.},
ISSN = {0028-3045},
CODEN = {NTWKAA},
}
J. H. Rubinstein and D. A. Thomas :
“The Steiner ratio conjecture for cocircular points Discrete Comput. Geom.
7 : 1
(1992 ),
pp. 77–86 .
MR
1134454 Zbl
0774.05031 article
Abstract
People
BibTeX
A Steiner minimal tree \( S \) is a network of shortest possible length connecting a set of \( n \) points in the plane. Let \( T \) be a shortest tree connecting then points but with vertices only at these points. \( T \) is called a minimal spanning tree. The Steiner ratio conjecture is that the length of \( S \) divided by the length of \( T \) is at least \( \sqrt{3}/2 \) . In this paper we use a variational approach to show that if then points lie on a circle, then the Steiner ratio conjecture holds.
@article {key1134454m,
AUTHOR = {Rubinstein, J. H. and Thomas, D. A.},
TITLE = {The {S}teiner ratio conjecture for cocircular
points},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry},
VOLUME = {7},
NUMBER = {1},
YEAR = {1992},
PAGES = {77--86},
DOI = {10.1007/BF02187826},
NOTE = {MR:1134454. Zbl:0774.05031.},
ISSN = {0179-5376},
CODEN = {DCGEER},
}
J. H. Rubinstein and D. A. Thomas :
“Graham’s problem on shortest networks for points on a circle 193–218
in
The Steiner problem ,
published as Algorithmica
7 : 2–3 .
Issue edited by F. K. Hwang .
1992 .
MR
1146495 Zbl
0748.05051 incollection
Abstract
People
BibTeX
Suppose a configuration \( X \) consists of \( n \) points lying on a circle of radius \( r \) . If at most one of the edges joining neighboring points has length strictly greater than \( r \) , then the Steiner tree \( S \) consists of all these edges with a longest edge removed. In order to show \( S \) is, in fact, just the minimal spanning tree \( T \) , a variational approach is used to show the Steiner ratio for this configuration is at least one and equals one only if \( S \) and \( T \) coincide. The variational approach greatly reduces the number of possible Steiner trees that need to be considered.
@article {key1146495m,
AUTHOR = {Rubinstein, J. H. and Thomas, D. A.},
TITLE = {Graham's problem on shortest networks
for points on a circle},
JOURNAL = {Algorithmica},
FJOURNAL = {Algorithmica},
VOLUME = {7},
NUMBER = {2--3},
YEAR = {1992},
PAGES = {193--218},
DOI = {10.1007/BF01758758},
NOTE = {\textit{The {S}teiner problem}. Issue
edited by F. K. Hwang. MR:1146495.
Zbl:0748.05051.},
ISSN = {0178-4617},
CODEN = {ALGOEJ},
}
J. H. Rubinstein, D. Thomas, and N. Wormald :
Algorithms for constrained networks ,
1992 .
From unpublished proceedings of the seventh Australian teletraffic research seminar (Mannum, Australia, November 1992).
misc
People
BibTeX
@misc {key31512525,
AUTHOR = {Rubinstein, J. H. and Thomas, D. and
Wormald, N.},
TITLE = {Algorithms for constrained networks},
YEAR = {1992},
NOTE = {From unpublished proceedings of the
seventh {A}ustralian teletraffic research
seminar (Mannum, Australia, November
1992).},
}
D. A. Thomas, J. H. Rubinstein, and T. Cole :
“The Steiner minimal network for convex configurations Discrete Comput. Geom.
9 : 3
(1993 ),
pp. 323–333 .
MR
1204786 Zbl
0774.05033 article
Abstract
People
BibTeX
Suppose \( X \) is a convex configuration with radius of maximum curvaturer and at most one of the edges joining neighboring points has length strictly greater than \( r \) . We use the variational approach to show the Steiner tree \( S \) coincides with the minimal spanning tree and consists of all these edges with a longest edge removed. This generalizes Graham’s problem for points on a circle, which we had solved. In addition we describe the minimal spanning tree for certain convex configurations.
@article {key1204786m,
AUTHOR = {Thomas, D. A. and Rubinstein, J. H.
and Cole, T.},
TITLE = {The {S}teiner minimal network for convex
configurations},
JOURNAL = {Discrete Comput. Geom.},
FJOURNAL = {Discrete \& Computational Geometry.
An International Journal of Mathematics
and Computer Science},
VOLUME = {9},
NUMBER = {3},
YEAR = {1993},
PAGES = {323--333},
DOI = {10.1007/BF02189325},
NOTE = {MR:1204786. Zbl:0774.05033.},
ISSN = {0179-5376},
CODEN = {DCGEER},
}
M. Brazil, T. Cole, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald :
“Minimal Steiner trees for \( 2^k\times 2^k \) square lattices J. Comb. Theory, Ser. A
73 : 1
(1996 ),
pp. 91–110 .
MR
1367609 Zbl
0844.05036 article
Abstract
People
BibTeX
We prove a conjecture of Chung, Graham, and Gardner (Math. Mag. 62 (1989), 83–96), giving the form of the minimal Steiner trees for the set of points comprising the vertices of a \( 2^k\times 2^k \) square lattice. Each full component of these minimal trees is the minimal Steiner tree for the four vertices of a square.
@article {key1367609m,
AUTHOR = {Brazil, M. and Cole, T. and Rubinstein,
J. H. and Thomas, D. A. and Weng, J.
F. and Wormald, N. C.},
TITLE = {Minimal {S}teiner trees for \$2^k\times
2^k\$ square lattices},
JOURNAL = {J. Comb. Theory, Ser. A},
FJOURNAL = {Journal of Combinatorial Theory. Series
A},
VOLUME = {73},
NUMBER = {1},
YEAR = {1996},
PAGES = {91--110},
DOI = {10.1006/jcta.1996.0004},
NOTE = {MR:1367609. Zbl:0844.05036.},
ISSN = {0097-3165},
CODEN = {JCBTA7},
}
M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald :
“Full minimal Steiner trees on lattice sets J. Combin. Theory Ser. A
78 : 1
(April 1997 ),
pp. 51–91 .
MR
1439632 Zbl
0874.05018 article
People
BibTeX
@article {key1439632m,
AUTHOR = {Brazil, M. and Rubinstein, J. H. and
Thomas, D. A. and Weng, J. F. and Wormald,
N. C.},
TITLE = {Full minimal {S}teiner trees on lattice
sets},
JOURNAL = {J. Combin. Theory Ser. A},
FJOURNAL = {Journal of Combinatorial Theory. Series
A},
VOLUME = {78},
NUMBER = {1},
MONTH = {April},
YEAR = {1997},
PAGES = {51--91},
DOI = {10.1006/jcta.1996.2752},
NOTE = {MR:1439632. Zbl:0874.05018.},
ISSN = {0097-3165},
CODEN = {JCBTA7},
}
J. H. Rubinstein, D. A. Thomas, and N. C. Wormald :
“Steiner trees for terminals constrained to curves SIAM J. Discrete Math.
10 : 1
(1997 ),
pp. 1–17 .
MR
1430542 Zbl
0869.05023 article
Abstract
People
BibTeX
@article {key1430542m,
AUTHOR = {Rubinstein, J. H. and Thomas, D. A.
and Wormald, N. C.},
TITLE = {Steiner trees for terminals constrained
to curves},
JOURNAL = {SIAM J. Discrete Math.},
FJOURNAL = {SIAM Journal on Discrete Mathematics},
VOLUME = {10},
NUMBER = {1},
YEAR = {1997},
PAGES = {1--17},
DOI = {10.1137/S0895480192241190},
NOTE = {MR:1430542. Zbl:0869.05023.},
ISSN = {0895-4801},
CODEN = {SJDMEC},
}
M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald :
“Minimal Steiner trees for rectangular arrays of lattice points J. Comb. Theory, Ser. A
79 : 2
(August 1997 ),
pp. 181–208 .
MR
1462554 Zbl
0883.05038 article
Abstract
People
BibTeX
@article {key1462554m,
AUTHOR = {Brazil, M. and Rubinstein, J. H. and
Thomas, D. A. and Weng, J. F. and Wormald,
N. C.},
TITLE = {Minimal {S}teiner trees for rectangular
arrays of lattice points},
JOURNAL = {J. Comb. Theory, Ser. A},
FJOURNAL = {Journal of Combinatorial Theory. Series
A},
VOLUME = {79},
NUMBER = {2},
MONTH = {August},
YEAR = {1997},
PAGES = {181--208},
DOI = {10.1006/jcta.1996.2751},
NOTE = {MR:1462554. Zbl:0883.05038.},
ISSN = {0097-3165},
CODEN = {JCBTA7},
}
M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald :
“Shortest networks on spheres ,”
pp. 453–461
in
Network design: Connectivity and facilities location
(Princeton, NJ, 28–30 April 1997 ).
Edited by P. M. Pardalos and D.-Z. Du .
DIMACS Series in Discrete Mathematics and Theoretical Computer Science 40 .
American Mathematical Society (Providence, RI ),
1998 .
MR
1613017 Zbl
0915.05043 incollection
Abstract
People
BibTeX
A system of linear and quadratic equations is given which determines the Steiner networks on a unit sphere with a fixed topology and spanning a fixed set of terminals. A simple descent algorithm is discussed for finding such shortest networks. The stability of Steiner networks on the sphere is examined, by using the Morse inequalities and computing second variation of length.
@incollection {key1613017m,
AUTHOR = {Brazil, M. and Rubinstein, J. H. and
Thomas, D. A. and Weng, J. F. and Wormald,
N. C.},
TITLE = {Shortest networks on spheres},
BOOKTITLE = {Network design: {C}onnectivity and facilities
location},
EDITOR = {Pardalos, Panos M. and Du, Ding-Zhu},
SERIES = {DIMACS Series in Discrete Mathematics
and Theoretical Computer Science},
NUMBER = {40},
PUBLISHER = {American Mathematical Society},
ADDRESS = {Providence, RI},
YEAR = {1998},
PAGES = {453--461},
NOTE = {(Princeton, NJ, 28--30 April 1997).
MR:1613017. Zbl:0915.05043.},
ISSN = {9780821870846},
ISBN = {1052-1798},
}
M. Brazil, J. H. Rubinstein, D. A. Thomas, and J. F. Weng :
Modelling and optimisation of a weighted network in an underground mine design ,
2001 .
From unpublished proceedings of the third international conference on control theory and applications (Pretoria, South Africa, 12–14 December 2001).
misc
People
BibTeX
@misc {key27143736,
AUTHOR = {Brazil, M. and Rubinstein, J. H. and
Thomas, D. A. and Weng, J. F.},
TITLE = {Modelling and optimisation of a weighted
network in an underground mine design},
YEAR = {2001},
NOTE = {From unpublished proceedings of the
third international conference on control
theory and applications (Pretoria, South
Africa, 12--14 December 2001).},
}
J. H. Rubinstein, D. A. Thomas, and N. C. Wormald :
“A polynomial algorithm for a constrained traveling salesman problem Networks
38 : 2
(September 2001 ),
pp. 68–75 .
MR
1852365 Zbl
0990.90102 article
Abstract
People
BibTeX
@article {key1852365m,
AUTHOR = {Rubinstein, J. H. and Thomas, D. A.
and Wormald, N. C.},
TITLE = {A polynomial algorithm for a constrained
traveling salesman problem},
JOURNAL = {Networks},
FJOURNAL = {Networks},
VOLUME = {38},
NUMBER = {2},
MONTH = {September},
YEAR = {2001},
PAGES = {68--75},
DOI = {10.1002/net.1025},
NOTE = {MR:1852365. Zbl:0990.90102.},
ISSN = {0028-3045},
CODEN = {NTWKAA},
}
M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald :
“Gradient-constrained minimum networks, I: Fundamentals J. Glob. Optim.
21 : 2
(2001 ),
pp. 139–155 .
Part III was published in J. Optim. Theory Appl. 155 :1 (2012)
MR
1863330 Zbl
1068.90605 article
Abstract
People
BibTeX
In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value \( m \) . A gradient-constrained minimum Steiner tree \( T \) is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than \( m \) . We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in \( T \) is either three or four. If the edges in \( T \) are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to \( m \) , then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in \( T \) . Moreover, we prove that all four edges incident with a degree 4 Steiner point in \( T \) must have gradient \( m \) if \( m \) is less than \( 0.38 \) . Finally, we use the variational argument to locate the Steiner points in \( T \) in terms of the positions of the neighbouring vertices.
@article {key1863330m,
AUTHOR = {Brazil, M. and Rubinstein, J. H. and
Thomas, D. A. and Weng, J. F. and Wormald,
N. C.},
TITLE = {Gradient-constrained minimum networks,
{I}: {F}undamentals},
JOURNAL = {J. Glob. Optim.},
FJOURNAL = {Journal of Global Optimization},
VOLUME = {21},
NUMBER = {2},
YEAR = {2001},
PAGES = {139--155},
DOI = {10.1023/A:1011903210297},
NOTE = {Part III was published in \textit{J.
Optim. Theory Appl.} \textbf{155}:1
(2012). Rubinstein was not a co-author
of part II. MR:1863330. Zbl:1068.90605.},
ISSN = {0925-5001},
CODEN = {JGOPEO},
}
J. H. Rubinstein, D. A. Thomas, and J. Weng :
“Minimum networks for four points in space Geom. Dedicata
93 : 1
(2002 ),
pp. 57–70 .
MR
1934686 Zbl
1009.05042 article
Abstract
People
BibTeX
The minimum network problem (Steiner tree problem) in space is much harder than the one in the Euclidean plane. The Steiner tree problem for four points in the plane has been well studied. In contrast, very few results are known on this simple Steiner problem in 3D-space. In the first part of this paper we analyze the difficulties of the Steiner problem in space. From this analysis we introduce a new concept–Simpson intersections , and derive a system of iteration formulae for computing Simpson intersections. Using Simpson intersections the Steiner points can be determined by solving quadratic equations. As well this new computational method makes it easy to check the impossibility of computing Steiner trees on 4-point sets by radicals. At the end of the first part we consider some special cases (planar and symmetric 3D-cases) that can be solved by radicals. The Steiner ratio problem is to find the minimum ratio of the length of a Steiner minimal tree to the length of a minimal spanning tree. This ratio problem in the Euclidean plane was solved by D. Z. Du and F. K. Hwang in 1990, but the problem in 3D-space is still open. In 1995 W. D. Smith and J. M. Smith conjectured that the Steiner ratio for 4-point sets in 3D-space is achieved by regular tetrahedra. In the second part of this paper, using the variational method, we give a proof of this conjecture.
@article {key1934686m,
AUTHOR = {Rubinstein, J. H. and Thomas, D. A.
and Weng, J.},
TITLE = {Minimum networks for four points in
space},
JOURNAL = {Geom. Dedicata},
FJOURNAL = {Geometriae Dedicata},
VOLUME = {93},
NUMBER = {1},
YEAR = {2002},
PAGES = {57--70},
DOI = {10.1023/A:1020389712969},
NOTE = {MR:1934686. Zbl:1009.05042.},
ISSN = {0046-5755},
CODEN = {GEMDAT},
}
M. Brazil, D. Lee, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald :
“A network model to optimise cost in underground mine design Trans. S. Afr. Inst. Electr. Eng.
93 : 2
(2002 ),
pp. 97–103 .
article
Abstract
People
BibTeX
This paper examines the problem of designing an underground mine so as to optimise the development and haulage costs. It focusses particularly on the costs associated with the ramps and shafts which provide passage to and from the ore zones. This mine optimisation problem is modelled as a weighted network. The controls (variables for the optimisation process) and operational constraints are described. A main constraint in mining networks is that all ramps have gradients no more than a given maximum value \( m \) . In this paper we describe the mine design problem as an optimisation problem, and prove that under reasonable conditions the cost function of an underground mining network with maximum gradient constraint \( m \) is convex. The convexity of the objective function ensures the existence of minimum cost mining networks, and theoretically any descent algorithms for finding minimal points can be applied to the design of minimum cost mining networks.
@article {key86311505,
AUTHOR = {Brazil, M. and Lee, D. and Rubinstein,
J. H. and Thomas, D. A. and Weng, J.
F. and Wormald, N. C.},
TITLE = {A network model to optimise cost in
underground mine design},
JOURNAL = {Trans. S. Afr. Inst. Electr. Eng.},
FJOURNAL = {The Transactions of the South African
Institute of Electrical Engineers},
VOLUME = {93},
NUMBER = {2},
YEAR = {2002},
PAGES = {97--103},
URL = {http://cat.inist.fr/?aModele=afficheN&cpsidt;=13957402},
ISSN = {0038-2221},
}
M. Brazil, D. Lee, M. Van Leuven, J. H. Rubinstein, D. A. Thomas, and N. C. Wormald :
“Optimising declines in underground mines Mining Tech.
112 : 3
(2003 ),
pp. 164–170 .
article
Abstract
People
BibTeX
This paper describes a method for optimising the layout of a decline in an underground mine. It models a decline as a mathematical network connecting the access points at each level of the proposed mine to the surface portal. A feasible decline is one satisfying all operational constraints such as gradient and turning radius requirements. The task is to find the decline that minimises a given cost objective. Typically, the cost objective will be some combination of development and operational costs representing a project cost or a life-of-mine cost. The procedure to find the optimal decline has been automated and the paper describes the current capability of Decline Optimisation Tool (DOT) software. A case study on the optimisation of a decline to service the Jandam gold mine in the Pajingo field of Newmont Australia Limited demonstrates the practical application of the technique.
@article {key26756511,
AUTHOR = {Brazil, M. and Lee, D. and Van Leuven,
M. and Rubinstein, J. H. and Thomas,
D. A. and Wormald, N. C.},
TITLE = {Optimising declines in underground mines},
JOURNAL = {Mining Tech.},
FJOURNAL = {Mining Technology},
VOLUME = {112},
NUMBER = {3},
YEAR = {2003},
PAGES = {164--170},
DOI = {10.1179/037178403225003546},
ISSN = {1474-9009},
}
M. Brazil, D. A. Thomas, J. F. Weng, J. H. Rubinstein, and D. H. Lee :
“Cost optimisation for underground mining networks Optim. Eng.
6 : 2
(2005 ),
pp. 241–256 .
MR
2136609 Zbl
1093.90067 article
Abstract
People
BibTeX
In this paper we consider the problem of optimising the construction and haulage costs of underground mining networks. We focus on a model of underground mine networks consisting of ramps in which each ramp has a bounded maximum gradient. The cost depends on the lengths of the ramps, the tonnages hauled through them and their gradients. We model such an underground mine network as an edge-weighted network and show that the problem of optimising the cost of the network can be described as an unconstrained non-linear optimisation problem. We show that, under a mild condition which is satisfied in practice, the cost function is convex. Finally we briefly discuss how the model can be generalised to those underground mine networks that are composed not only of ramps but also vertical shafts, and show that the total cost in the generalised model is still convex under the same condition. The convexity of the cost function ensures that any local minimum is a global minimum for the given network topology, and theoretically any descent algorithms for finding local minima can be applied to the design of minimum cost mining networks.
@article {key2136609m,
AUTHOR = {Brazil, Marcus and Thomas, Doreen A.
and Weng, Jia F. and Rubinstein, J.
Hyam and Lee, David H.},
TITLE = {Cost optimisation for underground mining
networks},
JOURNAL = {Optim. Eng.},
FJOURNAL = {Optimization and Engineering},
VOLUME = {6},
NUMBER = {2},
YEAR = {2005},
PAGES = {241--256},
DOI = {10.1007/s11081-005-6797-x},
NOTE = {MR:2136609. Zbl:1093.90067.},
ISSN = {1389-4420},
}
M. Brazil, D. Lee, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. C. Wormald :
“Optimisation in the design of underground mine access 121–124
in
Orebody modelling and strategic mine planning: Uncertainty and risk management models .
Edited by R. Dimitrakopoulos .
Spectrum Series 14 .
Australasian Institute of Mining and Metallurgy (Melbourne ),
2005 .
incollection
Abstract
People
BibTeX
Efficient methods to model and optimise the design of open cut mines have been known for many years. The design of the infrastructure of underground mines has a similar potential for optimisation and strategic planning.
Our group has developed two pieces of software to tackle this problem–UNO (underground network optimiser) and DOT (decline optimisation tool) over the last 5 years. The idea is to connect up a system of declines, ramps, drives and possibly shafts, to minimize capital development and haulage costs over the lifetime of a mine. Constraints which can be handled by the software include: gradient bounds (typically \( 1:7 \) ), turning circle restrictions for navigability, and obstacle avoidance. The latter constraint keeps development at stand off distances from ore bodies and ensures that it avoids regions which involve high cost, such as faults, voids and other geological features.
The software is not limited to only interconnecting fixed points. It has the useful feature that a group of points can be specified such that the development is required to connect to one member of the group. So for example, if an existing ventilation rise must be accessed at some level, then a group of points along the rise can be selected. Similarly this gives the opportunity to use variable length crosscuts from a decline to an ore body. The latter gives important flexibility and can significantly reduce the development and haulage cost of a design.
Finally the goals for the next phase of development of this project will be discussed, including speeding up the algorithms and allowing for heterogeneous materials, such as aquifers and faults, as additional costs rather than obstacles.
@incollection {key49128372,
AUTHOR = {Brazil, M. and Lee, D. and Rubinstein,
J. H. and Thomas, D. A. and Weng, J.
F. and Wormald, N. C.},
TITLE = {Optimisation in the design of underground
mine access},
BOOKTITLE = {Orebody modelling and strategic mine
planning: {U}ncertainty and risk management
models},
EDITOR = {Dimitrakopoulos, Roussos},
SERIES = {Spectrum Series},
NUMBER = {14},
PUBLISHER = {Australasian Institute of Mining and
Metallurgy},
ADDRESS = {Melbourne},
YEAR = {2005},
PAGES = {121--124},
URL = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.134.6454},
ISBN = {9781920806422},
}
M. Brazil, P. A. Grossman, D. H. Lee, J. H. Rubinstein, D. A. Thomas, and N. C. Wormald :
“Decline design in underground mines using constrained path optimisation Mining Tech.
117 : 2
(2008 ),
pp. 93–99 .
article
Abstract
People
BibTeX
This paper focuses on the problem of optimising the design of an underground mine decline, so as to minimise the costs associated with infrastructure development and haulage over the lifetime of the mine. A key design consideration is that the decline must be navigable by trucks and mining equipment, hence must satisfy both gradient and turning circle constraints. The decline is modelled as a mathematical network that captures the operational constraints and costs of a real mine, and is optimised using geometric techniques for constrained path optimisation. A deep understanding of the geometric properties of gradient and turning circle constrained paths has led to a very efficient procedure for designing optimal declines. This procedure has been automated in a new version of a software tool, decline optimisation tool. A case study is described indicating the substantial improvements of the new version of the decline optimisation tool over the earlier one.
@article {key84900638,
AUTHOR = {Brazil, M. and Grossman, P. A. and Lee,
D. H. and Rubinstein, J. H. and Thomas,
D. A. and Wormald, N. C.},
TITLE = {Decline design in underground mines
using constrained path optimisation},
JOURNAL = {Mining Tech.},
FJOURNAL = {Mining Technology},
VOLUME = {117},
NUMBER = {2},
YEAR = {2008},
PAGES = {93--99},
DOI = {10.1179/174328608X362668},
ISSN = {1474-9009},
}
M. Brazil, P. A. Grossman, D. A. Thomas, J. H. Rubinstein, D. Lee, and N. C. Wormald :
“Constrained path optimisation for underground mine layout 856–861
in
Proceedings of the World Congress on Engineering 2007
(Imperial College, London, 2–4 July 2007 ),
vol. II .
Edited by S. I. Ao, L. Gelman, D. Hukins, A. Hunter, and A. M. Korsunsky .
Lecture Notes in Engineering and Computer Science 2166 .
Newswood Limited (Hong Kong ),
2008 .
incollection
Abstract
People
BibTeX
The major infrastructure component required to develop an underground mine is a decline, which is a system of tunnels used for access and haulage. In this paper we study the problem of designing a decline of minimum cost where cost is a combination of development and haulage costs over the life of the mine. A key design consideration is that the decline must be navigable to trucks and mining equipment, hence must satisfy a gradient and turning circle constraint. The decline is modelled as a mathematical network that captures the operational constraints and costs of a real mine, and is optimised using geometric techniques for constrained path optimisation. This procedure to find the optimal decline has been automated in a new version of a software tool, Decline Optimisation Tool, DOT\( ^{\textrm{TM}} \) . A case study is described comparing this version with the earlier one.
@incollection {key16036470,
AUTHOR = {Brazil, M. and Grossman, P. A. and Thomas,
D. A. and Rubinstein, J. H. and Lee,
D. and Wormald, N. C.},
TITLE = {Constrained path optimisation for underground
mine layout},
BOOKTITLE = {Proceedings of the {W}orld {C}ongress
on {E}ngineering 2007},
EDITOR = {Ao, S. I. and Gelman, Len and Hukins,
David and Hunter, Andrew and Korsunsky,
A. M.},
VOLUME = {II},
SERIES = {Lecture Notes in Engineering and Computer
Science},
NUMBER = {2166},
PUBLISHER = {Newswood Limited},
ADDRESS = {Hong Kong},
YEAR = {2008},
PAGES = {856--861},
URL = {http://www.iaeng.org/publication/WCE2007/WCE2007_pp856-861.pdf},
NOTE = {(Imperial College, London, 2--4 July
2007).},
ISSN = {2078-0958},
ISBN = {9789889867126},
}
A. J. Chang, M. Brazil, J. H. Rubinstein, and D. A. Thomas :
“Curvature-constrained directional-cost paths in the plane J. Glob. Optim.
53 : 4
(2012 ),
pp. 663–681 .
MR
2944057 Zbl
06117793 article
Abstract
People
BibTeX
This paper looks at the problem of finding the minimum cost curvature-constrained path between two directed points where the cost at every point along the path depends on the instantaneous direction. This generalises the results obtained by Dubins for curvature-constrained paths of minimum length, commonly referred to as Dubins paths. We conclude that if the reciprocal of the directional-cost function is strictly polarly convex, then the forms of the optimal paths are of the same forms as Dubins paths. If we relax the strict polar convexity to weak polar convexity, then we show that there exists a Dubins path which is optimal. The results obtained can be applied to optimising the development of underground mine networks, where the paths need to satisfy a curvature constraint and the cost of development of the tunnel depends on the direction due to the geological characteristics of the ground.
@article {key2944057m,
AUTHOR = {Chang, Alan J. and Brazil, Marcus and
Rubinstein, J. Hyam and Thomas, Doreen
A.},
TITLE = {Curvature-constrained directional-cost
paths in the plane},
JOURNAL = {J. Glob. Optim.},
FJOURNAL = {Journal of Global Optimization},
VOLUME = {53},
NUMBER = {4},
YEAR = {2012},
PAGES = {663--681},
DOI = {10.1007/s10898-011-9730-1},
NOTE = {MR:2944057. Zbl:06117793.},
ISSN = {0925-5001},
CODEN = {JGOPEO},
}
M. Brazil, J. H. Rubinstein, D. A. Thomas, J. F. Weng, and N. Wormald :
“Gradient-constrained minimum networks, III: Fixed topology J. Optim. Theory Appl.
155 : 1
(2012 ),
pp. 336–354 .
Part I was published in J. Glob. Optim. 21 :2 (2001)
MR
2983123 Zbl
1255.90120 article
Abstract
People
BibTeX
The gradient-constrained Steiner tree problem asks for a shortest total length network interconnecting a given set of points in 3-space, where the length of each edge of the network is determined by embedding it as a curve with absolute gradient no more than a given positive value \( m \) , and the network may contain additional nodes known as Steiner points. We study the problem for a fixed topology, and show that, apart from a few easily classified exceptions, if the positions of the Steiner points are such that the tree is not minimum for the given topology, then there exists a length reducing perturbation that moves exactly 1 or 2 Steiner points. In the conclusion, we discuss the application of this work to a heuristic algorithm for solving the global problem (across all topologies).
@article {key2983123m,
AUTHOR = {Brazil, M. and Rubinstein, J. H. and
Thomas, D. A. and Weng, J. F. and Wormald,
N.},
TITLE = {Gradient-constrained minimum networks,
{III}: {F}ixed topology},
JOURNAL = {J. Optim. Theory Appl.},
FJOURNAL = {Journal of Optimization Theory and Applications},
VOLUME = {155},
NUMBER = {1},
YEAR = {2012},
PAGES = {336--354},
DOI = {10.1007/s10957-012-0036-3},
NOTE = {Part I was published in \textit{J. Glob.
Optim.} \textbf{21}:2 (2001). Rubinstein
was not a co-author of part II. MR:2983123.
Zbl:1255.90120.},
ISSN = {0022-3239},
CODEN = {JOTABN},
}
