Search

Theoretical studies on evolutionary algorithms have developed vigorously in recent years. Many such algorithms have theoretical guarantees in both running time and approximation ratio. Some approximation mechanism seems to be inherently embedded in many evolutionary algorithms. In this paper, we identify such a relation by proposing a unified analysis framework for a global simple multiobjective evolutionary algorithm (GSEMO) and apply it on a minimum weight general cover problem, which is general enough to subsume many important problems including the minimum submodular cover problem in which the submodular function is real-valued, and the minimum connected dominating set problem for which the potential function is nonsubmodular. We show that GSEMO yields theoretically guaranteed approximation ratios matching those achievable by a greedy algorithm in expected polynomial time when the potential function g is polynomial in the input size and the minimum gap between different g-values is a constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported by National Natural Science Foundation of China [11771013, U20A2068]; Zhejiang Provincial Natural Science Foundation of China [LD19A010001]. [ABSTRACT FROM AUTHOR]

Rank aggregation combines the preference rankings of multiple alternatives from different voters into a single consensus ranking, providing a useful model for a variety of practical applications but posing a computationally challenging problem. In this paper, we provide an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem with both complete and partial rankings. The algorithm features a semantic crossover based on concordant pairs and an enhanced late acceptance local search method reinforced by a relaxed acceptance and replacement strategy and a fast incremental evaluation mechanism. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on both synthetic and real-world benchmark instances compared with state-of-the-art algorithms. To demonstrate its practical usefulness, the algorithm is applied to label ranking, a well-established machine learning task. We additionally analyze several key algorithmic components to gain insight into their operation. 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 [Grant 72371157] and Shanghai Pujiang Programme [Grant 23PJC069]. 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.2022.0019) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0019). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

This study considers a well-known critical node detection problem that aims to minimize a pairwise connectivity measure of an undirected graph via the removal of a subset of nodes (referred to as critical nodes) subject to a cardinality constraint. Potential applications include epidemic control, emergency response, vulnerability assessment, carbon emission monitoring, network security, and drug design. To solve the problem, we present a "reduce-solve-combine" memetic search approach that integrates a problem reduction mechanism into the popular population-based memetic algorithm framework. At each generation, a common pattern mined from two parent solutions is first used to reduce the given problem instance, then the reduced instance is solved by a component-based hybrid neighborhood search that effectively combines an articulation point impact strategy and a node weighting strategy, and finally an offspring solution is produced by combining the mined common pattern and the solution of the reduced instance. Extensive evaluations on 42 real-world and synthetic benchmark instances show the efficacy of the proposed method, which discovers nine new upper bounds and significantly outperforms the current state-of-the-art algorithms. Investigation of key algorithmic modules additionally discloses the importance of the proposed ideas and strategies. Finally, we demonstrate the generality of the proposed method via its adaptation to solve the node-weighted critical node problem. 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 72371157, 61903144, 72031007]. 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.2022.0130) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0130). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k ≥ 2 , is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 − 4 / k) and a polynomial running time for any fixed constant k ≥ 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k ≥ 2 being a fixed constant. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This work was supported in part by the National Natural Science Foundation of China [Grants 71971177, 71725001, U1811462], Research Grants Council of Hong Kong SAR, China [Grant 15221619], and Guangdong Basic and Applied Basic Research Foundation [Grant 2023A1515030260]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2021.0193. 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.2021.0193) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0193). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

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 2 ≤ N ≤ 400 and matches 242 other best-known results. For sphere packing, the algorithm improves 66 best-known results in the range of 2 ≤ N ≤ 200 , 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). [ABSTRACT FROM AUTHOR]

We present a gradient-based algorithm for solving a class of simulation optimization problems in which the objective function is the quantile of a simulation output random variable. In contrast with existing quantile (quantile derivative) estimation techniques, which aim to eliminate the estimator bias by gradually increasing the simulation sample size, our algorithm incorporates a novel recursive procedure that only requires a single simulation sample at each step to simultaneously obtain quantile and quantile derivative estimators that are asymptotically unbiased. We show that these estimators, when coupled with the standard gradient descent method, lead to a multitime-scale stochastic approximation type of algorithm that converges to an optimal quantile value with probability one. In our numerical experiments, the proposed algorithm is applied to optimal investment portfolio problems, resulting in new solutions that complement those obtained under the classical Markowitz mean-variance framework. History: Accepted by Alice E. Smith, Editor-in-Chief; Bruno Tuffin, Area Editor for Simulation. Funding: The work of Y. Peng was supported in part by the National Natural Science Foundation of China (NSFC) [Grants 72022001, 92146003, and 71901003], and by the Key Research and Development Programof Beijing Municipal Science and Technology Commission. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2022.1214. [ABSTRACT FROM AUTHOR]

In large-scale disasters, evacuation using public transport, such as buses, is always essential, especially with limitations on the time window and resources available. Unfortunately, a Bus Evacuation Problem (BEP) is NP-hard in nature. This means it is impossible to find an optimal evacuation plan within a reasonable time window. Therefore, it is efficacious and requisite to use an approximation algorithm such that a sub-optimal plan can be derived quickly in large-scale disasters. In the literature, an approximation algorithm for BEP has been presented. However, there is not only a lack of rigorous proof of the approximation ratio, but also the computation time of the approximation algorithm is influenced by the number of evacuees. In this work, firstly the approximation ratio is derived as 2 n b + 7 , where n b is the number of buses, which is fundamentally more precise than the existing work. Further, the approximation ratio can be reduced to n b + 6 through a new proof provided in this work. More importantly, a new approximation algorithm is proposed in this work, with an aggregated network flow model that can be quickly solved as a linear programming problem in polynomial time. The approximation ratio of the new algorithm is proven to be n b + 1 when there is a pile of buses, and the computation time is insensitive to the number of evacuees. Finally, 10 sets of random cases and a real-life disaster, the flooding in Xingguo, China in 2019 are studied to illustrate the efficiency and practical applicability of the proposed approximation algorithm. [ABSTRACT FROM AUTHOR]

an important topographic attribute widely-used in precision agriculture, topographic wetness index (TWI) is designed to quantify the effect of local topography on hydrological processes and for modeling the spatial distribution of soil moisture and surface saturation. This index is formulated as TWI = ln( a/tan β), where a is the upslope contributing area per unit contour length (or Specific Catchment Area, SCA) and tan β is the local slope gradient for estimating a hydraulic gradient. The computation of both a and tan β need to reflect impacts of local terrain on local drainage. Many of the existing flow direction algorithms for computing a use global parameters, which lead to unrealistic partitioning of flow. β is often approximated by slope gradient around the pixel. In fact, the downslope gradient of the pixel is a better approximation of β. This paper examines how TWI is impacted by a multiple flow routing algorithm adaptive to local terrain and the employment of maximum downslope gradient as β. The adaptive multiple flow routing algorithm partitions flow by altering the flow partition parameter based on local maximum downslope gradient. The proposed approach for computing TWI is quantitatively evaluated using four types of artificial terrains constructed as DEMs with a series of resolutions (1, 5, 10, 20, and 30 m), respectively. The result shows that the error of TWI computed using the proposed approach is generally lower than that of TWI by the widely used approach. The new approach was applied to a low-relief agricultural catchment (about 60 km) in the Nenjiang watershed, Northeastern China. The results of this application show that the distribution of TWI by the proposed approach reflects local terrain conditions better. [ABSTRACT FROM AUTHOR]

The stochastic approximation algorithm (SAA), starting from the pioneer work by Robbins and Monro in 1950s, has been successfully applied in systems and control, statistics, machine learning, and so forth. In this paper, we will review the development of SAA in China, to be specific, the stochastic approximation algorithm with expanding truncations (SAAWET) developed by Han-Fu Chen and his colleagues during the past 35 years. We first review the historical development for the centralized algorithm including the probabilistic method (PM) and the ordinary differential equation (ODE) method for SAA and the trajectory-subsequence method for SAAWET. Then, we will give an application example of SAAWET to the recursive principal component analysis. We will also introduce the recent progress on SAAWET in a networked and distributed setting, named the distributed SAAWET (DSAAWET). [ABSTRACT FROM AUTHOR]

• An arc approximation algorithm for cucumber curvature is proposed. • The center line of the cucumber coincides with the approximated arc curve. • The new algorithm has higher classification advantages than elliptic approximation. The cucumber is one of the most important consumer vegetables, and due to high freshness and appearance standards, it must be graded according to quality. One key metric for grading cucumbers is curvature (arch height) relative to length. To date, this classification standard has not been implemented in a commercial automatic system because the curvature of the cucumber is related to its length. This paper presents and tests a circular arc approximation algorithm for measuring the curvature of a cucumber using image processing. By fitting the central axis of each cucumber to establish a curve equation, the approximate eigenvalue radius, R, and the radius of the section perpendicular to the curvature of cucumber, r, could be obtained quickly and efficiently. The curve of the cucumber was then transformed into a new characteristic, R' (R' = R – r), which was used as a threshold to classify each cucumber. The method was verified by theory and experiment, and the average error of 0.71 % corresponding to the coefficient R2 = 0.9958 of the similarity index between the curve and central axis of the cucumber was verified. It was found that the fitted curve and the central axis of the cucumber were coincident. Moreover, we designed an algorithm that can detect S-shaped cucumbers based on the analysis of the contour, which can avoid the influence of S-shaped cucumbers on the results. In our tests, 148 cucumbers were classified using the circular arc approximation method, the elliptic approximation method, and a manual method. The results of the classifications were compared. According to China's standard evaluation, the classification error rate of the circular arc approximation method was 10.1 % lower than that of the elliptic approximation method. The incidence of cucumbers being classified into an adjacent grade was 0.7 % using the circular approximation method, and there were no cases of cucumbers being classified into non-adjacent grades. The classification error rate of the elliptic approximation was 10.8 %, of which 2.7 % was classified into non-adjacent grades. Under the European standard, the cucumber classification accuracy using the circular arc approximation algorithm reached 100 %. Therefore, the proposed method offers a more accurate classifier than the elliptic approximation method, and the circular arc approximation algorithm can be fully applied in the commercial cucumber classification process. [ABSTRACT FROM AUTHOR]

This letter proposes a novel method to solve the environmental/economic dispatch (EED) problem with DC power flow constraints. A parameterized KKT condition is introduced to characterize the Pareto front. Then Nash's bargain criterion is employed to determine a compromise solution on the Pareto front. The proposed method is applied to the EED of a regional power grid in China. Numerical studies demonstrate that it is valid and promising. [ABSTRACT FROM PUBLISHER]