An improved branch‐and‐bound clustering approach for data partitioning

In this paper, we are concerned with clustering algorithms for vertical partitioning. In particular, we examine the use of a branch‐and‐bound scheme. An existing algorithm using such a scheme may produce infeasible solutions to some problems. We adopt the same branch‐and‐bound scheme and develop a new branching strategy to avoid infeasibility. Illustrative examples are used to demonstrate the effectiveness of our new approach. In addition, we also show how to formulate the horizontal partitioning problem such that the same algorithm can be applied.     

A branch‐and‐cut algorithm for the Team Orienteering Problem

The Team Orienteering Problem aims at maximizing the total amount of profit collected by a fleet of vehicles while not exceeding a predefined travel time limit on each vehicle. In the last years, several exact methods based on different mathematical formulations were proposed. In this paper, we present a new two‐index formulation with a polynomial number of variables and constraints. This compact formulation, reinforced by connectivity constraints, was solved by means of a branch‐and‐cut algorithm. The total number of instances solved to optimality is 327 of 387 benchmark instances, 26 more than any previous method. Moreover, 24 not previously solved instances were closed to optimality.     

A branch‐and‐bound algorithm for scheduling of new product development projects

In this paper, we consider scheduling problem in a new product development project. Each research and development project consists of a set of activities in which each activity may be executed in several ways. Each way of execution of an activity is a different technology, called an alternative technology, which may fail due to technical risks. In this work, we focus on alternative technologies for scheduling activities to maximize the expected net present value. We assume that the activity payoff is obtained as soon as any single technology is completed successfully. Therefore, we analyze the problem and develop a two‐phase solution procedure, consisting of a branch‐and‐bound algorithm and a recursive search procedure. The efficiency of the proposed algorithm has been evaluated on a set of randomly generated test instances.     

Graphics processing unit‐accelerated bounding for branch‐and‐bound applied to a permutation problem using data access optimization

Branch‐and‐bound (B&B) algorithms are attractive methods for solving to optimality combinatorial optimization problems using an implicit enumeration of a dynamically built tree‐based search space. Nevertheless, they are time‐consuming when dealing with large problem instances. Therefore, pruning tree nodes (subproblems) is traditionally used as a powerful mechanism to reduce the size of the explored search space. Pruning requires to perform the bounding operation, which consists of applying a lower bound function to the subproblems generated during the exploration process. Preliminary experiments performed on the Flow‐Shop scheduling problem (FSP) have shown that the bounding operation consumes over 98% of the execution time of the B&B algorithm. In this paper, we investigate the use of graphics processing unit (GPU) computing as a major complementary way to speed up the search. We revisit the design and implementation of the parallel bounding model on GPU accelerators. The proposed approach enables data access optimization. Extensive experiments have been carried out on well‐known FSP benchmarks using an Nvidia Tesla C2050 GPU card. Compared to a CPU‐based single core execution using an Intel Core i7‐970 processor without GPU, speedups higher than 100 times faster are achieved for large problem instances. At an equivalent peak performance, GPU‐accelerated B&B is twice faster than its multi‐core counterpart. Copyright © 2013 John Wiley & Sons, Ltd.     

A tabu search approach for the minimum sum-of-squares clustering problem

In this paper, a tabu search based clustering approach called TS-Clustering is proposed to deal with the minimum sum-of-squares clustering problem. In the TS-Clustering algorithm, five improvement operations and three neighborhood modes are given. The improvement operation is used to enhance the clustering solution obtained in the process of iterations, and the neighborhood mode is used to create the neighborhood of tabu search. The superiority of the proposed method over some known clustering techniques is demonstrated for artificial and real life data sets.     

Work stealing with private integer–vector–matrix data structure for multi‐core branch‐and‐bound algorithms

In this paper, the focus is put on multi‐core branch‐and‐bound algorithms for solving large‐scale permutation‐based optimization problems. We investigate five work stealing (WS) strategies with a new data structure called integer–vector–matrix (IVM). In these strategies, each thread has a private IVM allowing the local management of a set of subproblems enumerated using a factorial system. The WS strategies differ in the way the victim thread is selected and the granularity of stolen work units (intervals of factoradics). To assess the efficiency of the private IVM‐based WS approach, the five WS strategies have been extensively experimented on the flowshop scheduling permutation problem and compared with their conventional linked‐list‐based counterparts. The obtained results demonstrate that the IVM‐based WS outperforms the linked‐list‐based one in terms of CPU time, memory usage and number of performed WS operations. Copyright © 2016 John Wiley & Sons, Ltd.     

Branch‐and‐bound approach for optima localization in scheduling multiprocessor jobs

We consider multiprocessor task scheduling problems with dedicated processors. We determine the tight optima localization intervals for different subproblems of the basic problem. Based on the ideas of a computer‐aided technique developed by Sevastianov and Tchernykh for shop scheduling problems, we elaborate a similar method for the multiprocessor task scheduling problem. Our method allows us to find an upper bound for the length of the optimal schedule in terms of natural lower bound. As a byproduct of our results, a family of linear‐time approximation algorithms with a constant ratio performance guarantee is designed for the NP‐hard subproblems of the basic problem, and new polynomially solvable classes of problems are found.     

Modified sequential k‐means clustering by utilizing response: A case study for fashion products

Modified sequential k‐means clustering concerns a k‐means clustering problem in which the clustering machine utilizes output similarity in addition. While conventional clustering methods commonly recognize similar instances at features‐level modified sequential clustering takes advantage of response, too. To this end, the approach we pursue is to enhance the quality of clustering by using some proper information. The information enables the clustering machine to detect more patterns and dependencies that may be relevant. This allows one to determine, for instance, which fashion products exhibit similar behaviour in terms of sales. Unfortunately, conventional clustering methods cannot tackle such cases, because they handle attributes solely at the feature level without considering any response. In this study, we introduce a novel approach underlying minimum conditional entropy clustering and show its advantages in terms of data analytics. In particular, we achieve this by modifying the conventional sequential k‐means algorithm. This modified clustering approach has the ability to reflect the response effect in a consistent manner. To verify the feasibility and the performance of this approach, we conducted several experiments based on real data from the apparel industry.     

A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem

The set k‐covering problem, an extension of the classical set covering problem, is an important NP‐hard combinatorial optimization problem with extensive applications, including computational biology and wireless network. The aim of this paper is to design a new local search algorithm to solve this problem. First, to overcome the cycling problem in local search, the set k‐covering configuration checking (SKCC) strategy is proposed. Second, we use the cost scheme of elements to define the scoring mechanism so that our algorithm can find different possible good‐quality solutions. Having combined the SKCC strategy with the scoring mechanism, a subset selection strategy is designed to decide which subset should be selected as a candidate solution component. After that, a novel local search framework, as we call DLL_ccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLL_ccsm is evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLL_ccsm performs better than its competitors in terms of solution quality in most classical instances.     

An intelligent hybrid approach for hepatitis disease diagnosis: Combining enhanced k‐means clustering and improved ensemble learning

In real world, the automatic detection of liver disease is a challenging problem among medical practitioners. The intent of this work is to propose an intelligent hybrid approach for the diagnosis of hepatitis disease. The diagnosis is performed with the combination of k‐means clustering and improved ensemble‐driven learning. To avoid clinical experience and to reduce the evaluation time, ensemble learning is deployed, which constructs a set of hypotheses by using multiple learners to solve a liver disease problem. The performance analysis of the proposed integrated hybrid system is compared in terms of accuracy, true positive rate, precision, f‐measure, kappa statistic, mean absolute error, and root mean squared error. Simulation results showed that the enhanced k‐means clustering and improved ensemble learning with enhanced adaptive boosting, bagged decision tree, and J48 decision tree‐based intelligent hybrid approach achieved better prediction outcomes than other existing individual and integrated methods.     

Comparison of metaheuristics for the k‐labeled spanning forest problem

In this paper, we study the k‐labeled spanning forest (kLSF) problem in which an undirected graph whose edges are labeled and an integer‐positive value are given; the aim is to find a spanning forest of the input graph with the minimum number of connected components and the upper bound on the number of labels. The problem is related to the minimum labeling spanning tree problem and has several applications in the real world. In this paper, we compare several metaheuristics to solve this NP‐hard problem. In particular, the proposed intelligent variable neighborhood search (VNS) shows excellent performance, obtaining high‐quality solutions in short computational running time. This approach integrates VNS with other complementary approaches from machine learning, statistics, and experimental algorithmics, in order to produce high‐quality performance and completely automate the resulting optimization strategy.     

A recombination‐based matheuristic for mixed integer programming problems with binary variables

This work introduces a heuristic for mixed integer programming (MIP) problems with binary variables, based on information obtained from differences between feasible solutions as well as solutions from the linear relaxation. This information is used to build a neighborhood that is explored as a sub‐MIP problem. The proposed heuristic is evaluated using 45 problems from the MIPLIB repository. Its performance, in terms of solution improvement over the results obtained after exploring 50,000 nodes of the branch‐and‐bound tree, is compared against that of Solution Polishing, which is another recombination‐based heuristic for MIP problems used within the CPLEX solver; as well as against the solution obtained by running the default CPLEX branch‐and‐cut (B&C) method under a same time limit. The computational results indicate that the proposed method is able to yield results that are significantly better than those obtained by the default CPLEX B&C approach and comparable to those of Solution Polishing in terms of the mean solution quality. This equivalence of expected solution quality, coupled with a simpler implementation, suggests the use of the proposed approach as a possible alternative for improving the quality of solutions in MIP problems.     

A personalized search engine based on Web‐snippet hierarchical clustering

We propose a (meta‐)search engine, called SnakeT (SNippet Aggregation for Knowledge ExtracTion), which queries more than 18 commodity search engines and offers two complementary views on their returned results. One is the classical flat‐ranked list, the other consists of a hierarchical organization of these results into folders created on‐the‐fly at query time and labeled with intelligible sentences that capture the themes of the results contained in them. Users can browse this hierarchy with various goals: knowledge extraction, query refinement and personalization of search results. In this novel form of personalization, the user is requested to interact with the hierarchy by selecting the folders whose labels (themes) best fit her query needs. SnakeT then personalizes on‐the‐fly the original ranked list by filtering out those results that do not belong to the selected folders. Consequently, this form of personalization is carried out by the users themselves and thus results fully adaptive, privacy preserving, scalable and non‐intrusive for the underlying search engines. We have extensively tested SnakeT and compared it against the best available Web‐snippet clustering engines. SnakeT is efficient and effective, and shows that a mutual reinforcement relationship between ranking and Web‐snippet clustering does exist. In fact, the better the ranking of the underlying search engines, the more relevant the results from which SnakeT distills the hierarchy of labeled folders, and hence the more useful this hierarchy is to the user. Vice versa, the more intelligible the folder hierarchy, the more effective the personalization offered by SnakeT on the ranking of the query results. Copyright © 2007 John Wiley & Sons, Ltd.     

Cuckoo and krill herd‐based k‐means++ hybrid algorithms for clustering

Clustering algorithms can be optimized using nature‐inspired techniques. Many algorithms inspired by nature, namely, firefly algorithm, ant colony optimization algorithm, and so forth, have improved clustering results. k‐means is a popular clustering technique but has limitations of local optima, which have been overcome using its various hybrids. k‐means++ is a hybrid k‐means clustering algorithm that gives the procedure to initialize centre of the clusters. In the proposed work, hybrids of nature‐inspired techniques using cuckoo and krill herd algorithm are implemented on k‐means++ algorithm to enhance cluster quality and generate optimized clusters. The designed algorithms are implemented, and the results are compared with their counterparts. Performance parameters such as accuracy, f‐measure, error rate, standard deviation, CPU time, cluster quality check, and so forth are used to measure the clustering capabilities of these algorithms. The results indicate the high performance of newly designed algorithms.     

A possibilistic clustering approach to novel fault detection and isolation

In this paper, a new approach for fault detection and isolation that is based on the possibilistic clustering algorithm is proposed. Fault detection and isolation (FDI) is shown here to be a pattern classification problem, which can be solved using clustering and classification techniques. A possibilistic clustering based approach is proposed here to address some of the shortcomings of the fuzzy c-means (FCM) algorithm. The probabilistic constraint imposed on the membership value in the FCM algorithm is relaxed in the possibilistic clustering algorithm. Because of this relaxation, the possibilistic approach is shown in this paper to give more consistent results in the context of the FDI tasks. The possibilistic clustering approach has also been used to detect novel fault scenarios, for which the data was not available while training. Fault signatures that change as a function of the fault intensities are represented as fault lines, which have been shown to be useful to classify faults that can manifest with different intensities. The proposed approach has been validated here through simulations involving a benchmark quadruple tank process and also through experimental case studies on the same setup. For large scale systems, it is proposed to use the possibilistic clustering based approach in the lower dimensional approximations generated by algorithms such as PCA. Towards this end, finally, we also demonstrate the key merits of the algorithm for plant wide monitoring study using a simulation of the benchmark Tennessee Eastman problem.     

A tabu search-based algorithm for the fuzzy clustering problem

The Fuzzy Clustering Problem (FCP) is a mathematical program which is difficult to solve since it is nonconvex, which implies possession of many local minima. The fuzzy C-means heuristic is the widely known approach to this problem, but it is guaranteed only to yield local minima. In this paper, we propose a new approach to this problem which is based on tabu search technique, and aims at finding a global solution of FCP. We compare the performance of the algorithm with the fuzzy C-means algorithm.     

The nested k‐means method: A new approach for detecting lost persons in aerial images acquired by unmanned aerial vehicles

A new method, named as the nested k‐means, for detecting a person captured in aerial images acquired by an unmanned aerial vehicle (UAV), is presented. The nested k‐means method is used in a newly built system that supports search and rescue (SAR) activities through processing of aerial photographs taken in visible light spectra (red‐green‐blue channels, RGB). First, the k‐means classification is utilized to identify clusters of colors in a three‐dimensional space (RGB). Second, the k‐means method is used to verify if the automatically selected class of colors is concurrently spatially clustered in a two‐dimensional space (easting‐northing, EN), and has human‐size area. The UAV images were acquired during the field campaign carried out in the Izerskie Mountains (SW Poland). The experiment aimed to observe several persons using an RGB camera, in spring and winter, during various periods of day, in uncovered terrain and sparse forest. It was found that the nested k‐means method has a considerable potential for detecting a person lost in the wilderness and allows to reduce area to be searched to 4.4 and 7.3% in spring and winter, respectively. In winter, land cover influences the performance of the nested k‐means method, with better skills in sparse forest than in the uncovered terrain. In spring, such a relationship does not hold. The nested k‐means method may provide the SAR teams with a tool for near real‐time detection of a person and, as a consequence, to reduce search area to approximately 0.5–7.3% of total terrain to be visited, depending on season and land cover.     

A collaborative filtering-based approach to personalized document clustering

Document clustering is an intentional act that reflects individual preferences with regard to the semantic coherency and relevant categorization of documents. Hence, effective document clustering must consider individual preferences and needs to support personalization in document categorization. Most existing document-clustering techniques, generally anchoring in pure content-based analysis, generate a single set of clusters for all individuals without tailoring to individuals' preferences and thus are unable to support personalization. The partial-clustering-based personalized document-clustering approach, incorporating a target individual's partial clustering into the document-clustering process, has been proposed to facilitate personalized document clustering. However, given a collection of documents to be clustered, the individual might have categorized only a small subset of the collection into his or her personal folders. In this case, the small partial clustering would degrade the effectiveness of the existing personalized document-clustering approach for this particular individual. In response, we extend this approach and propose the collaborative-filtering-based personalized document-clustering (CFC) technique that expands the size of an individual's partial clustering by considering those of other users with similar categorization preferences. Our empirical evaluation results suggest that when given a small-sized partial clustering established by an individual, the proposed CFC technique generally achieves better clustering effectiveness for the individual than does the partial-clustering-based personalized document-clustering technique.     

Exact formulations for the minimum interference problem in k‐connected ad hoc wireless networks

Energy consumption is one of the most critical issues in wireless ad hoc and sensor networks. A considerable amount of energy is dissipated due to radio transmission power and interference (message collisions). A typical topology control technique aims at reducing energy consumption while ensuring specific desired properties to the established wireless network (such as biconnectivity). Energy minimization can be achieved by reducing the transmission power and selecting edges that suffer or cause less interference. We propose four integer programming formulations for the k‐connected minimum wireless ad hoc interference problem, which consists in a topology control technique to find a power assignment to the nodes of an ad hoc wireless network such that the resulting network topology is k‐vertex connected and the radio interference is minimum. Interference is measured by three different models: Boolean, protocol, and physical. We report computational experiments comparing the formulations and interference models. Optimal solutions for moderately sized networks are obtained using a commercial solver.     

A multiobjective hybrid ant colony optimization approach applied to the assignment and scheduling problem

The assignment and scheduling problem is inherently multiobjective. It generally involves multiple conflicting objectives and large and highly complex search spaces. The problem allows the determination of an efficient allocation of a set of limited and shared resources to perform tasks, and an efficient arrangement scheme of a set of tasks over time, while fulfilling spatiotemporal constraints. The main objective is to minimize the project makespan as well as the total cost. Finding a good approximation set is the result of trade‐offs between diversity of solutions and convergence toward the Pareto‐optimal front. It is difficult to achieve such a balance with NP‐hard problems. In this respect, and in order to efficiently explore the search space, a hybrid bidirectional ant‐based approach is proposed in this paper, which is an improvement of a bi‐colony ant‐based approach. Its main characteristic is that it combines a solution construction developed for a more complicated problem with a Pareto‐guided local search engine.