Note on: An improved algorithm for the packing of unequal circles within a larger containing circle

This note proposed an improved version of the algorithm proposed by Wang et al. [Wang, H. Q., Huang, W. Q., Zhang, Q., & Xu, D. M. (2002). An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research, 141, 339–347] for solving the disk packing problem with equilibrium constraints. An efficient strategy of accelerating the search process is introduced in the gradient method to shorten the execution time. A number of computational results are presented, showing the effectiveness of the proposed method.     

Packing unequal circles using formulation space search

In this paper we present a heuristic algorithm for the problem of packing unequal circles in a fixed size container such as the unit circle, the unit square or a rectangle. We view the problem as being one of scaling the radii of the unequal circles so that they can all be packed into the container. Our algorithm is composed of an optimisation phase and an improvement phase. The optimisation phase is based on the formulation space search method whilst the improvement phase creates a perturbation of the current solution by swapping two circles. The instances considered in this work can be categorised into two: instances with large variations in radii and instances with small variations in radii. We consider six different containers: circle, square, rectangle, right-angled isosceles triangle, semicircle and circular quadrant. Computational results show improvements over previous work in the literature.     

Constrained circles packing test problems: all the optimal solutions known

Taking a satellite module layout design as engineering background, this paper gives constrained test problems for an unequal circle packing whose optimal solutions are all given. Given a circular container D with radius R, the test problem can be constructed in the following steps. First, M=217 circles are packed into D without overlaps by ‘packing with a tangent circle’ to get the values of radii and centroid coordinates of the circles, which are expressed by R. Then the 217 circles are arranged in descending sequence of radius and are divided into 23 groups according to the radius. Finally, seven test problems are constructed according to the circles of q=1, 2, …, 7 groups. The optimal solution to the test problems as well as its optimality and uniqueness proof are also presented. The experimental results show that the test problems can effectively evaluate performances of different evolutionary algorithms.     

Local search techniques for a routing-packing problem

We propose a complex real-world problem in logistics that integrates routing and packing aspects. It can be seen as an extension of the Three-Dimensional Loading Capacitated Vehicle Routing Problem (3L-CVRP) introduced by Gendreau, Iori, Laporte, and Martello (2006). The 3L-CVRP consists in finding a set of routes that satisfies the demand of all customers, minimizes the total routing cost, and guarantees a packing of items that is feasible according to loading constraints. Our problem formulation includes additional constraints in relation to the stability of the cargo, to the fragility of items, and to the loading and unloading policy. In addition, it considers the possibility of split deliveries, so that each customer can be visited more than once. We propose a local search approach that considers the overall problem in a single stage. It is based on a composite strategy that interleaves simulated annealing with large-neighborhood search. We test our solver on 13 real-world instances provided by our industrial partner, which are very diverse in size and features. In addition, we compare our solver on benchmarks from the literature of the 3L-CVRP showing that our solver performs well compared to other approaches proposed in the literature.     

An Efficient Processor Allocation Algorithm Using Two-Dimensional Packing

Mesh is one of the most widely used interconnection networks for multiprocessor systems. In this paper, we propose an approach to partition a given mesh intomsubmeshes which can be allocated tomtasks with grid structures. We adapt two-dimensional packing to solve the submesh allocation problem. Due to the intractability of the two-dimensional packing problem, finding an optimal solution is computationally infeasible. We develop an efficient heuristic packing algorithm called TP-heuristic. Allocating a submesh to each task is achieved using the results of packing. We propose two different methods called uniform scaling and nonuniform scaling. Experiments were carried out to test the accuracy of solutions provided by our allocation algorithm.     

An action-space-based global optimization algorithm for packing circles into a square container

This paper proposes an action-space-based global optimization (ASGO) approach for the problem of packing unequal circles into a square container such that the size of the square is minimized. Starting from several random configurations, ASGO runs the following potential descent method and basin-hopping strategy iteratively. It finds configurations with the local minimum potential energy by the limited-memory BFGS (LBFGS) algorithm, then selects the circular items having the most deformations and moves them to some large vacant space or randomly chosen vacant space. By adapting the action space defined for the rectangular packing problem, we approximate each circular item as a rectangular item, thus making it much easier to find comparatively larger vacant spaces for any given configuration. The tabu strategy is used to prevent cycling and enhance the diversification during the search procedure. Several other strategies, such as swapping two similar circles or swapping two circles in different quadrants in the container, are combined to increase the diversity of the configurations. We compare the performance of ASGO on 68 benchmark instances at the Packomania website with the state-of-the-art results. ASGO obtains configurations with smaller square containers on 63 instances; at the same time it matches or approaches the current best results on the other five instances.     

Trigonometric Bézier and Stancu polynomials over intervals and triangles

We introduce a family of trigonometric polynomials, denoted as Stancu polynomials, which contains the trigonometric Lagrange and Bernstein polynomials. This family depends only on one real parameter, denoted as design parameter. Our approach works for curves as well as for surfaces over triangles. The resulting Stancu curves respectively surfaces therefore establish a link between trigonometric interpolatory and Bernstein-Bézier curves respectively surfaces.     

A GRASP×ELS for the vehicle routing problem with basic three-dimensional loading constraints

This paper addresses an extension of the capacitated vehicle routing problem where the client demand consists of three-dimensional weighted items (3L-CVRP). The objective is to design a set of trips for a homogeneous fleet of vehicles based at a depot node which minimizes the total transportation cost. Items in each vehicle trip must satisfy the three-dimensional orthogonal packing constraints. This problem is strongly connected to real-life transportation systems where the packing of items to be delivered by each vehicle can have a significant impact on the routes. We propose a new way to solve the packing sub-problem. It consists of a two-step procedure in which the z-constraints are first relaxed to get a (x,y) positioning of the items. Then, a compatible z-coordinate is computed to get a packing solution. Items can be rotated but additional constraints such as item fragility, support and LIFO are not considered. This method is included in a GRASP×ELS hybrid algorithm dedicated to the computation of VRP routes. The route optimization alternates between two search spaces: the space of VRP routes and the space of giant trips. The projection from one to the other is done by dedicated procedures (namely the Split and the concatenation algorithms). Moreover, a Local Search is defined on each search space. Furthermore, hash tables are used to store the result of the packing checks and thus save a substantial amount of CPU time. The effectiveness of our approach is illustrated by computational experiments on 3L-CVRP instances from the literature. A new set of realistic instances based on the 96 French districts are also proposed. They range from 19 nodes for the small instances to 255 nodes for the large instances and they can be stated as realistic since they are based on true travel distances in kilometers between French cities. The impact of the hash tables is illustrated as well.     

High density packings of equal circles in rectangles with variable aspect ratio

Arranging a fixed number n   of equal non-overlapping circles in a rectangle with variable aspect ratio is a non-standard packing problem. It arises if one has to decide how a certain number of circular items should be packed into a rectangular box when no assumption is made on the shape of the box. How must the box be designed to achieve the maximum packing density? This special problem was investigated by Lubachevsky and Graham in 2003, where they classified record packings for n≤213$n\le 213$. However, their work lacks a precise treatment of the closure of observed vacancies as well as any numerical data of the best arrangements found.     

When guanxi meets structural holes: Exploring the guanxi networks of Chinese entrepreneurs on digital platforms

In this exploratory study, we investigate how Chinese entrepreneurs on digital platforms interact and leverage guanxi (a system of relationships and social network) to buffer the negative impacts of structural holes on knowledge orchestration. We develop our research model and formulate ten hypotheses by drawing on the literature. We adopt a mixed-methods research approach in which we use quantitative surveys to test the hypotheses, and qualitative interviews to explain why certain relationships are stronger in one stage of entrepreneurial development than the other. The study contributes to the literature on digital entrepreneurship in two ways. First, this study offers an initial understanding of the dynamics of guanxi networks for knowledge mobilisation and knowledge coordination across start-up and growth stages of Chinese entrepreneurs on digital platforms. Second, by drawing on the relevant literature, our findings extend the current understanding of knowledge orchestration of digital entrepreneurs and contribute to the literatures of structural holes theory and guanxi.     

Testing equality of covariance matrices when data are incomplete

In the statistics literature, a number of procedures have been proposed for testing equality of several groups’ covariance matrices when data are complete, but this problem has not been considered for incomplete data in a general setting. This paper proposes statistical tests for equality of covariance matrices when data are missing. A Wald test (denoted by T₁), a likelihood ratio test (LRT) (denoted by R), based on the assumption of normal populations are developed. It is well-known that for the complete data case the classic LRT and the Wald test constructed under the normality assumption perform poorly in instances when data are not from multivariate normal distributions. As expected, this is also the case for the incomplete data case and therefore has led us to construct a robust Wald test (denoted by T₂) that performs well for both normal and non-normal data. A re-scaled LRT (denoted by R^*) is also proposed. A simulation study is carried out to assess the performance of T₁, T₂, R, and R^* in terms of closeness of their observed significance level to the nominal significance level as well as the power of these tests. It is found that T₂ performs very well for both normal and non-normal data in both small and large samples. In addition to its usual applications, we have discussed the application of the proposed tests in testing whether a set of data are missing completely at random (MCAR).     

Fast and effective characterization for classification and similarity searches of 2D and 3D spatial region data

We propose a method for characterizing spatial region data. The method efficiently constructs a k-dimensional feature vector using concentric spheres in 3D (circles in 2D) radiating out of a region's center of mass. These signatures capture structural and internal volume properties. We evaluate our approach by performing experiments on classification and similarity searches, using artificial and real datasets. To generate artificial regions we introduce a region growth model. Similarity searches on artificial data demonstrate that our technique, although straightforward, compares favorably to mathematical morphology, while being two orders of magnitude faster. Experiments with real datasets show its effectiveness and general applicability.     

Packing equal circles into a circle with circular prohibited areas

The paper considers the problem of packing a maximal number of identical circles of a given radius into a multiconnected domain. The domain is a circle with prohibited areas to be finite unions of circles of given radii. We construct a mathematical model of the problem and investigate its characteristics. The starting points are constructed in a random way or on the ground of the hexagonal lattice. To find the local maxima, a modification of the Zoutendijk method of feasible directions and a strategy of active inequalities are applied. We compare our results with the benchmark instances of packing circles into circular and annular containers. A number of numerical examples are given.     

ChangeLocator: locate crash-inducing changes based on crash reports

Software crashes are severe manifestations of software bugs. Debugging crashing bugs is tedious and time-consuming. Understanding software changes that induce a crashing bug can provide useful contextual information for bug fixing and is highly demanded by developers. Locating the bug inducing changes is also useful for automatic program repair, since it narrows down the root causes and reduces the search space of bug fix location. However, currently there are no systematic studies on locating the software changes to a source code repository that induce a crashing bug reflected by a bucket of crash reports. To tackle this problem, we first conducted an empirical study on characterizing the bug inducing changes for crashing bugs (denoted as crash-inducing changes). We also propose ChangeLocator, a method to automatically locate crash-inducing changes for a given bucket of crash reports. We base our approach on a learning model that uses features originated from our empirical study and train the model using the data from the historical fixed crashes. We evaluated ChangeLocator with six release versions of Netbeans project. The results show that it can locate the crash-inducing changes for 44.7%, 68.5%, and 74.5% of the bugs by examining only top 1, 5 and 10 changes in the recommended list, respectively. It significantly outperforms the existing state-of-the-art approach.     

求解不等圆布局问题的一类遗传算法物方法

在已有求解不等圆布局问题算法的基础上 ,根据问题特点提出了一类遗传算法 ,通过将拟物方法与标准遗传算法结合使用 ,较好地解决了对布局优化函数进行全局最优求解的问题 最后通过实例计算验证了本算法的有效性 .     

求解圆形packing问题的拟人退火算法

Circles packing problem is an NP-hard problem and is difficult to solve. In this paper, a hybrid search strategy for circles packing problem is discussed. A way of generating new configuration is presented by simulating the moving of elastic objects, which can avoid the blindness of simulated annealing search and make iteration process converge fast. Inspired by the life experiences of people, an effective personified strategy to jump out of local minima is given. Based on the simulated annealing idea and personification strategy, an effective personified annealing algorithm for circles packing problem is developed. Numerical experiments on benchmark problem instances show that the proposed algorithm outperforms the best algorithm in the literature.     

Extended artificial chromosomes genetic algorithm for permutation flowshop scheduling problems

In our previous researches, we proposed the artificial chromosomes with genetic algorithm (ACGA) which combines the concept of the Estimation of Distribution Algorithms (EDAs) with genetic algorithms (GAs). The probabilistic model used in the ACGA is the univariate probabilistic model. We showed that ACGA is effective in solving the scheduling problems. In this paper, a new probabilistic model is proposed to capture the variable linkages together with the univariate probabilistic model where most EDAs could use only one statistic information. This proposed algorithm is named extended artificial chromosomes with genetic algorithm (eACGA). We investigate the usefulness of the probabilistic models and to compare eACGA with several famous permutation-oriented EDAs on the benchmark instances of the permutation flowshop scheduling problems (PFSPs). eACGA yields better solution quality for makespan criterion when we use the average error ratio metric as their performance measures. In addition, eACGA is further integrated with well-known heuristic algorithms, such as NEH and variable neighborhood search (VNS) and it is denoted as eACGA_hybrid to solve the considered problems. No matter the solution quality and the computation efficiency, the experimental results indicate that eACGA_hybrid outperforms other known algorithms in literature. As a result, the proposed algorithms are very competitive in solving the PFSPs.     

Interactive noise-controlled boundary image matching using the time-series moving average transform

In this paper we propose a time-series matching-based approach that provides the interactive boundary image matching with noise control for a large-scale image database. To achieve the noise reduction effect in boundary image matching, we exploit the moving average transform of time-series matching. We are motivated by a simple intuition that the moving average transform might reduce the noise of boundary images as well as that of time-series data. To confirm this intuition, we first propose a new notion of k-order image matching, which applies the moving average transform to boundary image matching. A boundary image can be represented as a sequence in the time-series domain, and our k-order image matching identifies similar boundary images in this time-series domain by comparing the k-moving average transformed sequences. We then propose an index-based method that efficiently performs k-order image matching on a large image database, and formally prove its correctness. We also formally analyze the relationship of orders and their matching results and present an interactive approach of controlling the noise reduction effect. Experimental results show that our k-order image matching exploits the noise reduction effect well, and our index-based method outperforms the sequential scan by one or two orders of magnitude. These results indicate that our k-order image matching and its index-based solution provide a very practical way of realizing the noise control boundary image matching. To our best knowledge, the proposed interactive approach for large-scale image databases is the first attempt to solve the noise control problem in the time-series domain rather than the image domain by exploiting the efficient time-series matching techniques. Thus, our approach can be widely used in removing other types of distortions in image matching areas.     

Adaptive beam search lookahead algorithms for the circular packing problem

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i, each of known radius r_i, i∈N={1, …, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of the center of C_i, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.     

Word-level neutrosophic sentiment similarity

In the specializedliterature, there are many approaches developed for capturing textual measures: textual similarity, textual readability and textual sentiment. This paper proposes a new sentiment similarity measures between pairs of words using a fuzzy-based approach in which words are considered single-valued neutrosophic sets. We build our study with the aid of the lexical resource SentiWordNet 3.0 as our intended scope is to design a new word-level similarity measure calculated by means of the sentiment scores of the involved words. Our study pays attention to the polysemous words because these words are a real challenge for any application that processes natural language data. After our knowledge, this approach is quite new in the literature and the obtained results give us hope for further investigations.