American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Analysis of a batch arrival retrial queue with impatient customers subject to the server disasters
  • JIMO Home
  • This Issue
  • Next Article
    Effect of warranty and quantity discounts on a deteriorating production system with a Markovian production process and allowable shortages
doi: 10.3934/jimo.2020136

A reformulation-linearization based algorithm for the smallest enclosing circle problem

Yi Jiang , and  Yuan Cai

School of Mathematical Sciences and VC/VR Key Lab, Sichuan Normal University, Chengdu, Sichuan 610066, China

* Corresponding author: yijiang103@163.com

Received  March 2020 Revised  June 2020 Published  August 2020

Fund Project: The first author is supported by National Natural Science Foundation of China No.11126336 and No.11201324, New Teachers' Fund for Doctor Stations, Ministry of Education No.20115134120001, Fok Ying Tuny Education Foundation No.141114, Youth fund of Sichuan province No.2013JQ0027

In this paper, an effective algorithm based on the reformulation-linearization technique (RLT) is developed to solve the smallest enclosing circle problem. Extensive computational experiments demonstrate that the algorithm based on the RLT outperforms the existing algorithms in terms of the solution time and quality in average.

Keywords: The smallest enclosing circle, second order cone programming, linear programming.
Mathematics Subject Classification: Primary: 90C30.
Citation: Yi Jiang, Yuan Cai. A reformulation-linearization based algorithm for the smallest enclosing circle problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2020136
References:
[1]

C. Audet, P. Hansen, B. Jaumard and G. Savard, A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87 (2000), 131-152.  doi: 10.1007/s101079900106.  Google Scholar

[2]

M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications, Springer, Berlin, Heidelberg, 2008. doi: 10.1007/978-3-540-77974-2.  Google Scholar

[3]

P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plane, Proceedings of the Edinburgh Mathematical Society, 3 (1884), 30-33.  doi: 10.1017/S0013091500037238.  Google Scholar

[4]

D. W. Hearn and J. Vijay, Efficient algorithms for the (weighted) minimum circle problem, Oper. Res., 30 (1982), 777-795.  doi: 10.1287/opre.30.4.777.  Google Scholar

[5]

Y. Jiang, C. Luo and S. G. Ling, An efficient cutting plane algorithm for the smallest enclosing circle problem, J. Ind. Manag. Optim., 13 (2017), 147-153.  doi: 10.3934/jimo.2016009.  Google Scholar

[6]

H. D. Sherali and C. H. Tuncbilek, Global optimization algorithm for polynomial programming using a reformulation-linearization technique, J. Global Optim., 2 (1992), 101-112.  doi: 10.1007/BF00121304.  Google Scholar

[7]

H. D. Sherali and C. H. Tuncbilek, Reformulation-convexification approach for solving nonconvex quadratic programming problems, J. Global Optim., 7 (1995), 1-31. doi: 10.1007/BF01100203.  Google Scholar

[8]

H. D. Sherali and C. H. Tuncbilek, Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems, J. Global Optim., 10 (1997), 381-390.  doi: 10.1023/A:1008237515535.  Google Scholar

[9]

S. H. Pan and X. S. Li, An efficient algorithm for the smallest enclosing ball problem in high dimension, Appl. Math. Comput., 172 (2006), 49-61.  doi: 10.1016/j.amc.2005.01.127.  Google Scholar

[10]

S. Skyum, A simple algorithm for computing the smallest enclosing circle, Inform. Process. Lett., 37 (1991), 121-125.  doi: 10.1016/0020-0190(91)90030-L.  Google Scholar

[11]

J. Sturm, Using SeDuMi 1.02, A MATLAB toolbox for optimization over symmetric cones. Interior point methods, Optim. Methods Softw. 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.  Google Scholar

[12]

J. J. Sylvester, A question in the geometry of situation, Quart. J. Math., 1 (1857), 79. Google Scholar

[13]

E. Welzl, Smallest enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer, Berlin, 1991,359-370. doi: 10.1007/BFb0038202.  Google Scholar

[14]

S. Xu, R. Freund and J. Sun, Solution methodologies for the smallest enclosing circle problem, Comput. Optim. Appl., 25 (2003), 283-292.  doi: 10.1023/A:1022977709811.  Google Scholar

[15]

E. A. Yildirim, Two algorithms for the minimum enclosing ball problem, SIAM J. Optim., 19 (2008), 1368-1391.  doi: 10.1137/070690419.  Google Scholar

[16]

G. Zhou, K. C. Tohemail and J. Sun, Efficient algorithms for the smallest enclosing ball problem, Comput. Optim. Appl., 30 (2005), 147-160.  doi: 10.1007/s10589-005-4565-7.  Google Scholar

show all references

References:
[1]

C. Audet, P. Hansen, B. Jaumard and G. Savard, A branch and cut algorithm for nonconvex quadratically constrained quadratic programming, Math. Program., 87 (2000), 131-152.  doi: 10.1007/s101079900106.  Google Scholar

[2]

M. de Berg, O. Cheong, M. van Kreveld and M. Overmars, Computational Geometry: Algorithms and Applications, Springer, Berlin, Heidelberg, 2008. doi: 10.1007/978-3-540-77974-2.  Google Scholar

[3]

P. Chrystal, On the problem to construct the minimum circle enclosing n given points in a plane, Proceedings of the Edinburgh Mathematical Society, 3 (1884), 30-33.  doi: 10.1017/S0013091500037238.  Google Scholar

[4]

D. W. Hearn and J. Vijay, Efficient algorithms for the (weighted) minimum circle problem, Oper. Res., 30 (1982), 777-795.  doi: 10.1287/opre.30.4.777.  Google Scholar

[5]

Y. Jiang, C. Luo and S. G. Ling, An efficient cutting plane algorithm for the smallest enclosing circle problem, J. Ind. Manag. Optim., 13 (2017), 147-153.  doi: 10.3934/jimo.2016009.  Google Scholar

[6]

H. D. Sherali and C. H. Tuncbilek, Global optimization algorithm for polynomial programming using a reformulation-linearization technique, J. Global Optim., 2 (1992), 101-112.  doi: 10.1007/BF00121304.  Google Scholar

[7]

H. D. Sherali and C. H. Tuncbilek, Reformulation-convexification approach for solving nonconvex quadratic programming problems, J. Global Optim., 7 (1995), 1-31. doi: 10.1007/BF01100203.  Google Scholar

[8]

H. D. Sherali and C. H. Tuncbilek, Comparison of two reformulation-linearization technique based linear programming relaxations for polynomial programming problems, J. Global Optim., 10 (1997), 381-390.  doi: 10.1023/A:1008237515535.  Google Scholar

[9]

S. H. Pan and X. S. Li, An efficient algorithm for the smallest enclosing ball problem in high dimension, Appl. Math. Comput., 172 (2006), 49-61.  doi: 10.1016/j.amc.2005.01.127.  Google Scholar

[10]

S. Skyum, A simple algorithm for computing the smallest enclosing circle, Inform. Process. Lett., 37 (1991), 121-125.  doi: 10.1016/0020-0190(91)90030-L.  Google Scholar

[11]

J. Sturm, Using SeDuMi 1.02, A MATLAB toolbox for optimization over symmetric cones. Interior point methods, Optim. Methods Softw. 11/12 (1999), 625-653. doi: 10.1080/10556789908805766.  Google Scholar

[12]

J. J. Sylvester, A question in the geometry of situation, Quart. J. Math., 1 (1857), 79. Google Scholar

[13]

E. Welzl, Smallest enclosing disks (balls and ellipsoids), in New Results and New Trends in Computer Science, Springer, Berlin, 1991,359-370. doi: 10.1007/BFb0038202.  Google Scholar

[14]

S. Xu, R. Freund and J. Sun, Solution methodologies for the smallest enclosing circle problem, Comput. Optim. Appl., 25 (2003), 283-292.  doi: 10.1023/A:1022977709811.  Google Scholar

[15]

E. A. Yildirim, Two algorithms for the minimum enclosing ball problem, SIAM J. Optim., 19 (2008), 1368-1391.  doi: 10.1137/070690419.  Google Scholar

[16]

G. Zhou, K. C. Tohemail and J. Sun, Efficient algorithms for the smallest enclosing ball problem, Comput. Optim. Appl., 30 (2005), 147-160.  doi: 10.1007/s10589-005-4565-7.  Google Scholar

Figure 1.  The error for under-estimating a square
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Average CPU time of three methods in 2D
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Average CPU time of three methods in 3D
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Computational results for 30000 circles by Algorithm Ⅰ in 2D
k R (x, y) Time
$ 1 $ 22.39739458 (-0.23034495, 1.54096380) 1256
$ 2 $ 22.45136334 (-0.22954489, 1.54016746) 4437
$ 3 $ 22.45378444 (-0.22950900, 1.54013173) 4705
$ 4 $ 22.45382627 (-0.22950838, 1.54013111) 4817
Table Options

Download as excel

k R (x, y) Time
$ 1 $ 22.39739458 (-0.23034495, 1.54096380) 1256
$ 2 $ 22.45136334 (-0.22954489, 1.54016746) 4437
$ 3 $ 22.45378444 (-0.22950900, 1.54013173) 4705
$ 4 $ 22.45382627 (-0.22950838, 1.54013111) 4817
Table 2.  The number of iterations on Algorithm Ⅰ in 2D
Problem Iteration
m Average Maximum Minimum
$ 30 $ 4.48 6 4
$ 300 $ 4.12 5 3
$ 3000 $ 3.78 4 3
$ 30000 $ 3.70 4 3
Table Options

Download as excel

Problem Iteration
m Average Maximum Minimum
$ 30 $ 4.48 6 4
$ 300 $ 4.12 5 3
$ 3000 $ 3.78 4 3
$ 30000 $ 3.70 4 3
Table 3.  Objective function value and average CPU time of four methods in 2D
Problem SOCP CP SDPT3 Algorithm Ⅰ
m Obj Value Time Obj Value Time Obj Value Time Obj Value Time
$ 30 $ 9.13411 128.98 9.13411 125.80 9.13411 1744.45 9.13411 66.50
$ 300 $ 15.05421 179.80 15.05421 165.26 15.05421 6848.30 15.05421 70.60
$ 3000 $ 18.31612 781.82 18.31612 918.92 18.31612 65688.71 18.31612 530.66
$ 30000 $ 21.21799 25641.96 21.21799 15716.18 21.21799 1548266.51 21.21799 5052.26
Table Options

Download as excel

Problem SOCP CP SDPT3 Algorithm Ⅰ
m Obj Value Time Obj Value Time Obj Value Time Obj Value Time
$ 30 $ 9.13411 128.98 9.13411 125.80 9.13411 1744.45 9.13411 66.50
$ 300 $ 15.05421 179.80 15.05421 165.26 15.05421 6848.30 15.05421 70.60
$ 3000 $ 18.31612 781.82 18.31612 918.92 18.31612 65688.71 18.31612 530.66
$ 30000 $ 21.21799 25641.96 21.21799 15716.18 21.21799 1548266.51 21.21799 5052.26
Table 4.  Computational results for 20000 balls by Algorithm Ⅰ in 3D
k R (x, y, z) Time
$ 1 $ 21.18238030 (-0.41033399, 0.50362615, -1.77470296) 2682
$ 2 $ 21.25471838 (-0.40932025, 0.50524350, -1.77617447) 4658
$ 3 $ 21.25805248 (-0.40927352, 0.50531805, -1.77624230) 6623
$ 4 $ 21.25808485 (-0.40927307, 0.50531877, -1.77624296) 10525
$ 5 $ 21.25808512 (-0.40927306, 0.50531878, -1.77624296) 14668
Table Options

Download as excel

k R (x, y, z) Time
$ 1 $ 21.18238030 (-0.41033399, 0.50362615, -1.77470296) 2682
$ 2 $ 21.25471838 (-0.40932025, 0.50524350, -1.77617447) 4658
$ 3 $ 21.25805248 (-0.40927352, 0.50531805, -1.77624230) 6623
$ 4 $ 21.25808485 (-0.40927307, 0.50531877, -1.77624296) 10525
$ 5 $ 21.25808512 (-0.40927306, 0.50531878, -1.77624296) 14668
Table 5.  The number of iterations on Algorithm Ⅰ in 3D
Problem Iteration
m Average Maximum Minimum
$ 20 $ 8.96 13 5
$ 200 $ 6.54 11 4
$ 2000 $ 6.68 12 4
$ 20000 $ 5.84 10 4
Table Options

Download as excel

Problem Iteration
m Average Maximum Minimum
$ 20 $ 8.96 13 5
$ 200 $ 6.54 11 4
$ 2000 $ 6.68 12 4
$ 20000 $ 5.84 10 4
Table 6.  Objective function value and average CPU time of four methods in 3D
Problem SOCP CP SDPT3 Algorithm 1
m Obj Value Time Obj Value Time Obj Value Time Obj Value Time
$ 20 $ 10.20133 131.26 10.20133 138.96 10.20133 1589.39 10.20133 120.92
$ 200 $ 13.90667 168.56 13.90667 251.66 13.90667 5157.42 13.90667 123.88
$ 2000 $ 16.47548 633.00 16.47548 1694.06 16.47548 43022.79 16.47548 161.02
$ 20000 $ 20.54257 16953.74 20.54257 18185.18 20.54257 907801.50 20.54257 1462.04
Table Options

Download as excel

Problem SOCP CP SDPT3 Algorithm 1
m Obj Value Time Obj Value Time Obj Value Time Obj Value Time
$ 20 $ 10.20133 131.26 10.20133 138.96 10.20133 1589.39 10.20133 120.92
$ 200 $ 13.90667 168.56 13.90667 251.66 13.90667 5157.42 13.90667 123.88
$ 2000 $ 16.47548 633.00 16.47548 1694.06 16.47548 43022.79 16.47548 161.02
$ 20000 $ 20.54257 16953.74 20.54257 18185.18 20.54257 907801.50 20.54257 1462.04
[1]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[2]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[3]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[4]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[5]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[6]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[7]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[8]

Weisong Dong, Chang Li. Second order estimates for complex Hessian equations on Hermitian manifolds. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020377
[9]

Shasha Hu, Yihong Xu, Yuhan Zhang. Second-Order characterizations for set-valued equilibrium problems with variable ordering structures. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020164
[10]

Shenglan Xie, Maoan Han, Peng Zhu. A posteriori error estimate of weak Galerkin fem for second order elliptic problem with mixed boundary condition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020340
[11]

Soniya Singh, Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of second order impulsive systems with state-dependent delay in Banach spaces. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020103
[12]

Liupeng Wang, Yunqing Huang. Error estimates for second-order SAV finite element method to phase field crystal model. Electronic Research Archive, 2021, 29 (1) : 1735-1752. doi: 10.3934/era.2020089
[13]

Elimhan N. Mahmudov. Infimal convolution and duality in convex optimal control problems with second order evolution differential inclusions. Evolution Equations & Control Theory, 2021, 10 (1) : 37-59. doi: 10.3934/eect.2020051
[14]

Ying Lv, Yan-Fang Xue, Chun-Lei Tang. Ground state homoclinic orbits for a class of asymptotically periodic second-order Hamiltonian systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1627-1652. doi: 10.3934/dcdsb.2020176
[15]

Wen Huang, Jianya Liu, Ke Wang. Möbius disjointness for skew products on a circle and a nilmanifold. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021006
[16]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272
[17]

Gui-Qiang Chen, Beixiang Fang. Stability of transonic shock-fronts in three-dimensional conical steady potential flow past a perturbed cone. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 85-114. doi: 10.3934/dcds.2009.23.85
[18]

Makram Hamouda, Ahmed Bchatnia, Mohamed Ali Ayadi. Numerical solutions for a Timoshenko-type system with thermoelasticity with second sound. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021001
[19]

François Dubois. Third order equivalent equation of lattice Boltzmann scheme. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 221-248. doi: 10.3934/dcds.2009.23.221
[20]

Denis Serre. Non-linear electromagnetism and special relativity. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 435-454. doi: 10.3934/dcds.2009.23.435

2019 Impact Factor: 1.366

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences