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).},
}
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},
}
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},
}
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. 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},
}
J. H. Rubinstein, J. Weng, and N. Wormald :
“Approximations and lower bounds for the length of minimal Euclidean Steiner trees J. Glob. Optim.
35 : 4
(2006 ),
pp. 573–592 .
MR
2249549 Zbl
1133.90408 article
Abstract
People
BibTeX
We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” \( e \) in the length of an approximate Steiner tree, in terms of the maximum deviation \( d \) of an interior angle of the tree from \( 120^{\circ} \) . Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between \( e \) and \( d \) , and make a conjecture which, if true, would somewhat strengthen our bounds on the error.
@article {key2249549m,
AUTHOR = {Rubinstein, J. H. and Weng, J. and Wormald,
N.},
TITLE = {Approximations and lower bounds for
the length of minimal {E}uclidean {S}teiner
trees},
JOURNAL = {J. Glob. Optim.},
FJOURNAL = {Journal of Global Optimization},
VOLUME = {35},
NUMBER = {4},
YEAR = {2006},
PAGES = {573--592},
DOI = {10.1007/s10898-005-4207-8},
NOTE = {MR:2249549. Zbl:1133.90408.},
ISSN = {0925-5001},
CODEN = {JGOPEO},
}
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},
}
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},
}
