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. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 72122006, 71821001, and 72471100] Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0089 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0089 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Given a weighted graph with a capacity associated to each node (element), the capacitated dispersion problem (CDP) consists in selecting a subset of elements satisfying a capacity constraint, in such a way that the minimum distance among them is maximized. The purpose of this work is to tackle this NP-hard problem, by developing an effective and parameter-free heuristic algorithm based on the solution-based tabu search. Specifically, we propose a fast greedy construction heuristic to obtain high-quality initial solutions. To ensure a high search efficiency, our algorithm exploits the combination of three neighborhoods, including a new neighborhood based on the constrained swap strategy, and uses hash functions to identify eligible candidate solutions. Extensive computational experiments on benchmark instances in the literature are performed to demonstrate the high performance of our algorithm and get insights into the influences of the algorithmic components. The application of our algorithm to a realistic location problem further shows the usefulness of our approach for practical problems.

This paper presents an effective perturbation-based thresholding search for two popular and challenging packing problems with minimal containers: packing N identical circles in a square and packing N identical spheres in a cube. Following the penalty function approach, we handle these constrained optimization problems by solving a series of unconstrained optimization subproblems with fixed containers. The proposed algorithm relies on a two-phase search strategy that combines a thresholding search method reinforced by two general-purpose perturbation operators and a container adjustment method. The performance of the algorithm is assessed relative to a large number of benchmark instances widely studied in the literature. Computational results show a high performance of the algorithm on both problems compared with the state-of-the-art results. For circle packing, the algorithm improves 156 best-known results (new upper bounds) in the range of [Formula: see text] and matches 242 other best-known results. For sphere packing, the algorithm improves 66 best-known results in the range of [Formula: see text], whereas matching the best-known results for 124 other instances. Experimental analyses are conducted to shed light on the main search ingredients of the proposed algorithm consisting of the two-phase search strategy, the mixed perturbation and the parameters. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by the National Natural Science Foundation of China [Grants 61703213 and 61933005]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1290 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0004 ) at ( http://dx.doi.org/10.5281/zenodo.7579558 ).

Population-based memetic algorithms have been successfully applied to solve many difficult combinatorial problems. Often, a population of fixed size is used in such algorithms to record some best solutions sampled during the search. However, given the particular features of the problem instance under consideration, a population of variable size would be more suitable to ensure the best search performance possible. In this work, we propose a variable population memetic search (VPMS), where a strategic population sizing mechanism is used to dynamically adjust the population size during the search process. Our VPMS approach starts its search from a small population of only two solutions to focus on exploitation and then adapts the population size according to the search status to continuously influence the balancing between exploitation and exploration. We illustrate an application of the VPMS approach to solve the challenging critical node problem (CNP). We show that the VPMS algorithm integrating a variable population, an effective local optimization procedure, and a backbone-based crossover operator performs very well compared to state-of-the-art CNP algorithms. The algorithm is able to discover new upper bounds for 12 instances out of the 42 popular benchmark instances while matching 23 previous best-known upper bounds.

Within the multiagent systems framework, the relative states between neighbors can be acquired by some on-board sensors, and then the relative state saturations inevitably occur due to the limited sensing capabilities. This paper investigates the consensus problem of nonlinear multiagent systems subject to the relative state saturations. Utilizing the incidence matrix and the edge Laplacian, the consensus problem of nonlinear multiagent systems with the relative state saturations can be cast into the stabilization problem of edge dynamics operating on the constrained set. Three types of protocols, namely continuous, intermittent, and adaptive state feedback protocols are, respectively, proposed for achieving the constrained consensus, and meanwhile yielding consensus values. A consensus analysis is provided by virtue of state saturation theory, switched system theory, adaptive theory, and Lyapunov stability theory. Output feedback protocol is also designed. Finally, the obtained results are applied to connectivity preservation for first-order nonlinear multiagent systems, despite the presence of limited communication range and input constraints. The theoretical results are validated by two simulation examples.

An equitable legal k-coloring of an undirected graph G = (V, E) is a partition of the vertex set V into k disjoint independent sets, such that the cardinalities of any two independent sets differ by at most one (this is called the equity constraint). As a variant of the popular graph coloring problem (GCP), the equitable coloring problem (ECP) involves finding a minimum k for which an equitable legal k-coloring exists. In this paper, we present a study of searching both feasible and infeasible solutions with respect to the equity constraint. The resulting algorithm relies on a mixed search strategy exploring both equitable and inequitable colorings unlike existing algorithms where the search is limited to equitable colorings only. We present experimental results on 73 DIMACS and COLOR benchmark graphs and demonstrate the competitiveness of this search strategy by showing 9 improved best-known results (new upper bounds).