The knowledge base partitioning problem: Mathematical formulation and heuristic clustering

Allocation of production rules among several partitions in a knowledge base can shorten the compilation and execution of expert systems applications and facilitate their verification, validation and maintenance. The problem of allocation of rules or groups of rules among partitions of limited size while minimizing the sum of inter-partition connections is formulated as a 0–1 integer programming problem with a quadratic objective function. Since this type of problems is NP-complete, a clustering algorithm based on the nearest neighbor heuristic is proposed.     

A set partitioning reformulation of a school bus scheduling problem

We present an integer programming model for the integrated optimization of bus schedules and school starting times, which is a single-depot vehicle scheduling problem with additional coupling constraints among the time windows. For instances with wide time windows the linear relaxation is weak and feasible solutions found by an ILP solver are of poor quality. We apply a set partitioning relaxation to compute better lower bounds and, in combination with a primal construction heuristic, also better primal feasible solutions. Integer programs with at most two non-zero coefficient per constraint play a prominent role in our approach. Computational results for several random and a real-world instance are given and compared with results from a standard branch-and-cut approach.     

Privacy-preserving data mining: A feature set partitioning approach

In privacy-preserving data mining (PPDM), a widely used method for achieving data mining goals while preserving privacy is based on k-anonymity. This method, which protects subject-specific sensitive data by anonymizing it before it is released for data mining, demands that every tuple in the released table should be indistinguishable from no fewer than k subjects. The most common approach for achieving compliance with k-anonymity is to replace certain values with less specific but semantically consistent values. In this paper we propose a different approach for achieving k-anonymity by partitioning the original dataset into several projections such that each one of them adheres to k-anonymity. Moreover, any attempt to rejoin the projections, results in a table that still complies with k-anonymity. A classifier is trained on each projection and subsequently, an unlabelled instance is classified by combining the classifications of all classifiers.Guided by classification accuracy and k-anonymity constraints, the proposed data mining privacy by decomposition (DMPD) algorithm uses a genetic algorithm to search for optimal feature set partitioning. Ten separate datasets were evaluated with DMPD in order to compare its classification performance with other k-anonymity-based methods. The results suggest that DMPD performs better than existing k-anonymity-based algorithms and there is no necessity for applying domain dependent knowledge. Using multiobjective optimization methods, we also examine the tradeoff between the two conflicting objectives in PPDM: privacy and predictive performance.     

A Relax-and-Cut algorithm for the set partitioning problem

Relax-and-Cut algorithms offer an alternative to strengthen Lagrangian relaxation bounds. The main idea behind these algorithms is to dynamically select and dualize inequalities (cuts) within a Lagrangian relaxation framework. This paper proposes a Relax-and-Cut algorithm for the Set Partitioning Problem. Computational tests are reported for benchmark instances from the literature. For Set Partitioning instances with integrality gaps, a variant of the classical Lagrangian relaxation is often used in the literature. It introduces a knapsack constraint to the standard formulation of the problem. Our results indicate that the proposed Relax-and-Cut algorithm outperforms the latter approach in terms of lower bound quality. Furthermore, it turns out to be very competitive in terms of CPU time. Decisive in achieving that performance was the implementation of dominance rules to manage inequalities in the cut pool. The Relax-and-Cut framework proposed here could also be used as a preprocessing tool for Linear Integer Programming solvers. Computational experiments demonstrated that the combined use of our framework and XPRESS improved the performance of that Linear Integer Programming solver for the test sets used in this study.     

基于SNN-AP聚类的扩展目标量测集划分方法

针对杂波环境下且量测密度差别较大的多扩展目标量测集划分问题,引入近邻传播聚类技术,提出了一种新的量测集划分算法。该算法首先采用局部异常因子检测对量测为杂波的程度进行度量,通过设定阈值的方法进行杂波滤除,同时对于目标量测密度差别较大的问题,引入一种基于共享最近邻的相似度度量方法,考虑了周围量测的影响,接着通过迭代传递两个信息量逐步寻找聚类中心,避免了对初始聚类个数的选择。仿真实验表明,与传统量测集划分算法相比,本文所提算法在保证扩展目标跟踪性能的同时,有效减少了算法的运算时间。     

A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows

The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. This problem has been addressed using many different techniques including both exact and heuristic methods. The VRPTW benchmark problems of Solomon [Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research 1987; 35(2): 254–65] have been most commonly chosen to evaluate and compare all algorithms. Results from exact methods have been improved considerably because of parallel implementations and modern branch-and-cut techniques. However, 24 out of the 56 high order instances from Solomon's original test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many of the heuristic methods developed have proved to be efficient in identifying good solutions in reasonable amounts of time. Unfortunately, whilst the research efforts based on exact methods have been focused on the total travel distance, the focus of almost all heuristic attempts has been on the number of vehicles. Consequently, it is more difficult to compare and take advantage of the strong points from each approach. This paper proposes a robust heuristic approach for the VRPTW using travel distance as the main objective through an efficient genetic algorithm and a set partitioning formulation. The tests were produced using real numbers and truncated data type, allowing a direct comparison of its results against previously published heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previously known and published heuristic methods in terms of the minimal travel distance.     

基于遗传算法的集合划分问题求解

集合划分问题是组合优化领域中有着广泛应用基础的著名问题,属于NP难问题.通过引入精英策略提出对遗传算法的改进,并为了能把遗传算法应用到集合划分问题,对数学模型进行了等价变换.针对集合划分问题,设计出一种高效的基因表示,避免了组合优化中处理约束条件的麻烦.解决了传统二进制基因编码无法精确适应离散优化问题,首次提出一种离散编码解决方案.最后,使用Visual C 6编程实现,取得较好的结果.     

High-dimensional clustering: a clique-based hypergraph partitioning framework

Hypergraph partitioning has been considered as a promising method to address the challenges of high-dimensional clustering. With objects modeled as vertices and the relationship among objects captured by the hyperedges, the goal of graph partitioning is to minimize the edge cut. Therefore, the definition of hyperedges is vital to the clustering performance. While several definitions of hyperedges have been proposed, a systematic understanding of desired characteristics of hyperedges is still missing. To that end, in this paper, we first provide a unified clique perspective of the definition of hyperedges, which serves as a guide to define hyperedges. With this perspective, based on the concepts of shared (reverse) nearest neighbors, we propose two new types of clique hyperedges and analyze their properties regarding purity and size issues. Finally, we present an extensive evaluation using real-world document datasets. The experimental results show that, with shared (reverse) nearest neighbor-based hyperedges, the clustering performance can be improved significantly in terms of various external validation measures without the need for fine tuning of parameters.     

A rough set approach for selecting clustering attribute

A few of clustering techniques for categorical data exist to group objects having similar characteristics. Some are able to handle uncertainty in the clustering process while others have stability issues. However, the performance of these techniques is an issue due to low accuracy and high computational complexity. This paper proposes a new technique called maximum dependency attributes (MDA) for selecting clustering attribute. The proposed approach is based on rough set theory by taking into account the dependency of attributes of the database. We analyze and compare the performance of MDA technique with the bi-clustering, total roughness (TR) and min–min roughness (MMR) techniques based on four test cases. The results establish the better performance of the proposed approach.     

Algorithms and implementation of a set partitioning approach for modular machining line design

A transfer line design problem is considered. Transfer lines are sequences of workstations equipped with processing modules called blocks each of which performs specific operations. These lines are used for mass production of one type of product and thus execute repetitively a given set of operations. The machine parts move along the stations in the same direction. An identical cost is associated with each station and differing costs are associated with the blocks. The problem is to determine the number of stations, select a set of blocks and assign selected blocks to the stations so that operations of the selected blocks constitute the original set of operations and the total cost is minimized. A distinct feature of the problem is that operations at the same station are performed in parallel. Plus, there are inclusion, exclusion and precedence relations that restrict the assignment of the blocks and operations to the same station as well as the processing order of the operations on the transfer line. We implement a novel set partitioning formulation of this design problem with pre-processing procedures and heuristics. The presented approach has the best performance among the existing methods in terms of solution time and quality.     

On the set partitioning type formulation for the discrete location problem

An approach to the discrete location problem is presented. The formulation is based on the set partitioning problem with the emphasis being placed on the weighted objective function and the importance of the “value” or “attractiveness” of the potential “covers”, i.e. the number of centres served by a specific location, FORTRAN programs were written to generate the potential subsets of centres to be served, for a specific county in northern Greece, and a mathematical programming package (APEX III) was used in its integer programming mode to provide solutions for various sets of subsets of centres which were generated according to certain criteria.     

Topological operators: a relaxed query processing approach

Relaxation and approximation techniques have been proposed as approaches for improving the quality of query results, in terms of completeness and accuracy, in environments where the user may not be able to specify the query in a complete and exact way, since data are quite heterogeneous or she may not know all the characteristics of data at hand. This problem, mainly addressed for relational and XML data, is nowadays quite relevant also for geo-spatial data, due to their increasing usage in highly critical decisional processes. Among geo-spatial queries, those based on spatial and more precisely topological relations are currently used in an increasing number of applications. As far as we know, no approach has been proposed so far for relaxing queries based on topological predicates when they return an empty or insufficient answer, in order to improve result quality and user satisfaction. In this paper, we consider this problem and we present a general relaxation strategy for, possibly multi-domain, topological selection and join queries. Two specific semantics are also provided: the first applies the minimum amount of relaxation in order to get an acceptable answer; the second relaxes the given query of a certain fixed amount, depending on the considered topological predicate. Index-based processing algorithms, for efficiently executing relaxed queries based on the proposed semantics, are also presented and a specific topological similarity function, to be used for relaxation purposes, is proposed. Experimental results show that the overhead given by query relaxation is acceptable.     

A set partitioning based goal programming model for the team formation problem

In this paper, we offer a multi-objective set-partitioning formulation for team formation problems using goal programming. Instead of selecting team members to teams, we select suitable teams from a set of teams. This set is generated using a heuristic algorithm that uses the social network of potential team members. We then utilize the proposed multi-objective formulation to select the desired number of teams from this set that meets the skill requirements. Therefore, we ensure that selected teams include individuals with the required skills and effective communication with each other. Two real datasets are used to test the model. The results obtained with the proposed solution are compared with two well-known approaches: weighted and lexicographic goal programming. Results reveal that weighted and lexicographic goal programming approaches generate almost identical solutions for the datasets tested. Our approach, on the other hand, mostly picks teams with lower communication costs. Even in some cases, better solutions are obtained with the proposed approach. Findings show that the developed solution approach is a promising approach to handle team formation problems.     

Correlation-aware partitioning for skewed range query optimization

World Wide Web - Data partitioning is an effective way to reduce cost and improve query performance in large-scale Web data analytical applications. State-of-the-art partitioning approaches on...     

RDF partitioning for scalable SPARQL query processing

The volume of RDF data increases dramatically within recent years, while cloud computing platforms like Hadoop are supposed to be a good choice for processing queries over huge data sets for their wonderful scalability. Previous work on evaluating SPARQL queries with Hadoop mainly focus on reducing the number of joins through careful split of HDFS files and algorithms for generating Map/Reduce jobs. However, the way of partitioning RDF data could also affect system performance. Specifically, a good partitioning solution would greatly reduce or even totally avoid cross-node joins, and significantly cut down the cost in query evaluation. Based on HadoopDB, this work processes SPARQL queries in a hybrid architecture, where Map/Reduce takes charge of the computing tasks, and RDF query engines like RDF-3X store the data and execute join operations. According to the analysis of query workloads, this work proposes a novel algorithm for automatically partitioning RDF data and an approximate solution to physically place the partitions in order to reduce data redundancy. It also discusses how to make a good trade-off between query evaluation efficiency and data redundancy. All of these proposed approaches have been evaluated by extensive experiments over large RDF data sets.     

Spam query detection using stream clustering

Nowadays, search engines play a gateway role for users to access their needed information in the Web. However, malicious users can also use them to facilitate their attacks by submitting excessive amounts of bot-generated queries, called spam queries. In this paper, we propose a novel semi-supervised method which can effectively detect spam queries in a practical manner. We first train a model to characterize normal and malicious users, using the linguistic properties of queries as well as the behavioral characteristics of users and IP addresses. Then, we use the trained model to predict the label of arriving requests with a fast and efficient algorithm which works based on the stream clustering approach. The results of our evaluation with the real log of a local search engine show that the proposed algorithm yields an accuracy of about %94, while incurring a low response-time and memory overhead.     

The set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.     

The set LCS problem

An efficient algorithm is presented that solves a generalization of the Longest Common Subsequence problem, in which one of the two input strings contains sets of symbols which may be permuted. This problem arises from a music application.