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},
}
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 and J. F. Weng :
“Compression theorems and Steiner ratios on spheres J. Comb. Optim.
1 : 1
(1997 ),
pp. 67–78 .
MR
1606181 Zbl
0895.90173 article
Abstract
People
BibTeX
Suppose \( A_iB_iC_i \) (\( i=1,2 \) ) are two triangles of equal side lengths lying on spheres \( \Phi_i \) with radii \( r_1,r_2 \) (\( r_1 < r_2 \) ) respectively. First we prove the existence of a map
\[ h: A_1B_1C_1\to A_2B_2C_2 \]
so that for any two points \( P_1,Q_1 \) in \( A_1B_1C_1 \) ,
\[ |P_1Q_1|\geq | h(P_1)h(Q_1)| .\]
Moreover, if \( P_1,Q_1 \) are not on the same side, then the inequality strictly holds. This compression theorem can be applied to compare the minimum of a variable in triangles on two spheres. Hence, one of the applications of the compression theorem is the study of Steiner minimal trees on spheres. The Steiner ratio is the largest lower bound for the ratio of the lengths of Steiner minimal trees to minimal spanning trees for point sets in a metric space. Using the compression theorem we prove that the Steiner ratio on spheres is the same as on the Euclidean plane, namely \( \sqrt{3}/2 \) .
@article {key1606181m,
AUTHOR = {Rubinstein, J. H. and Weng, J. F.},
TITLE = {Compression theorems and {S}teiner ratios
on spheres},
JOURNAL = {J. Comb. Optim.},
FJOURNAL = {Journal of Combinatorial Optimization},
VOLUME = {1},
NUMBER = {1},
YEAR = {1997},
PAGES = {67--78},
DOI = {10.1023/A:1009711003807},
NOTE = {MR:1606181. Zbl:0895.90173.},
ISSN = {1382-6905},
}
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. F. Weng and J. H. Rubinstein :
“A note on the compression theorem for convex surfaces 257–260
in
Combinatorics and applications
(Tianjin, China, 28–30 June 1996 ),
published as Discrete Math.
212 : 3 .
Issue edited by W. Y. C. Chen, D.-Z. Du, F. D. Hsu, and H. P. Yap .
February 2000 .
MR
1748655 Zbl
0986.90047 incollection
Abstract
People
BibTeX
Suppose \( a_ib_ic_i \) (\( i= 1,2 \) ) are two triangles of equal side lengths and lying on sphere \( \Phi_i \) with radii \( r_1 \) , \( r_2 \) (\( r_1 < r_2 \) ), respectively. We have proved that there is a continuous map \( h \) of \( a_1b_1c_1 \) onto \( a_2b_2c_2 \) so that for any two points \( p \) , \( q \) in \( a_1b_1c_1 \) , \( |pq|\geq |h(p)h(q)| \) [1997]. In this note we generalize this compression theorem to convex surfaces.
@article {key1748655m,
AUTHOR = {Weng, J. F. and Rubinstein, J. H.},
TITLE = {A note on the compression theorem for
convex surfaces},
JOURNAL = {Discrete Math.},
FJOURNAL = {Discrete Mathematics},
VOLUME = {212},
NUMBER = {3},
MONTH = {February},
YEAR = {2000},
PAGES = {257--260},
DOI = {10.1016/S0012-365X(99)00292-7},
NOTE = {\textit{Combinatorics and applications}
(Tianjin, China, 28--30 June 1996).
Issue edited by W. Y. C. Chen,
D.-Z. Du, F. D. Hsu,
and H. P. Yap. MR:1748655.
Zbl:0986.90047.},
ISSN = {0012-365X},
CODEN = {DSMHA4},
}
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).},
}
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. 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},
}
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, 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},
}
