An Efficient Optimization Model and Tabu Search–Based Global Optimization Approach for the Continuous p -Dispersion Problem

Xiangjing Lai (), Zhenheng Lin (), Jin-Kao Hao () and Qinghua Wu ()
Additional contact information
Xiangjing Lai: Institute of Advanced Technology, Nanjing University of Posts and Telecommunications, Nanjing 210023, P.R. China
Zhenheng Lin: Institute of Advanced Technology, Nanjing University of Posts and Telecommunications, Nanjing 210023, P.R. China
Jin-Kao Hao: Laboratoire d’Etude et de Recherche en Informatique d’Angers (LERIA), Université d’Angers, 49045 Angers, France
Qinghua Wu: School of Management, Huazhong University of Science and Technology, Wuhan 430074, P.R. China

INFORMS Journal on Computing, 2025, vol. 37, issue 4, 1018-1043

Abstract: Continuous p -dispersion problems with and without boundary constraints are NP-hard optimization problems with numerous real-world applications, notably in facility location and circle packing, which are widely studied in mathematics and operations research. In this work, we concentrate on general cases with a nonconvex multiply connected region that are rarely studied in the literature due to their intractability and the absence of an efficient optimization model. Using the penalty function approach, we design a unified and almost everywhere differentiable optimization model for these complex problems and propose a tabu search–based global optimization (TSGO) algorithm for solving them. Computational results over a variety of benchmark instances show that the proposed model works very well, allowing popular local optimization methods (e.g., the quasi-Newton methods and the conjugate gradient methods) to reach high-precision solutions due to the differentiability of the model. These results further demonstrate that the proposed TSGO algorithm is very efficient and significantly outperforms several popular global optimization algorithms in the literature, improving the best-known solutions for several existing instances in a short computational time. Experimental analyses are conducted to show the influence of several key ingredients of the algorithm on computational performance.

Keywords: circle packing; continuous dispersion problem; global optimization; tabu search; nonlinear optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0089 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:4:p:1018-1043

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().