Tag diversity_selection [17 articles]

Abstract

Compound selection methods currently available to chemists are based on maximum or minimum dissimilarity selection or on hierarchical clustering. Optimizable K-Dissimilarity Selection (OptiSim) is a novel and efficient stochastic selection algorithm which includes maximum and minimum dissimilarity-based selection as special cases. By adjusting the subsample size parameter K, it is possible to adjust the balance between representativeness and diversity in the compounds selected. The OptiSim algorithm is described, along with some analytical tools for comparing it to other selection methods. Such ...

Abstract

Observed in many applications, there is a potential need of extracting a small set of frequent patterns having not only high significance but also low redundancy. The significance is usually defined by the context of applications. Previous studies have been concentrating on how to compute top- k significant patterns or how to remove redundancy among patterns separately. There is limited work on finding those top- k patterns which demonstrate high-significance and low-redundancy simultaneously.In this paper, we study the problem ...

Abstract

Abstract   Description: The Maximum Diversity Problem (MDP) consists in determining a subset M of given cardinality from a set of elements N, in such a way that the sum of the pairwise differences between the elements of M is maximum. This problem, introduced by Glover, Hersh and McMillian has been deeply studied using the GRASP methodology. GRASPs are often characterized by a strong design effort dedicated to the randomized generation of high quality starting solutions, while the subsequent improvement phase is ...

Abstract

Abstract   Starting from an algorithm recently proposed by Pullan and Hoos, we formulate and analyze iterated local search algorithms for the maximum clique problem. The basic components of such algorithms are a fast neighbourhood search (not based on node evaluation but on completely random selection) and simple, yet very effective, diversification techniques and restart rules. A detailed computational study is performed in order to identify strengths and weaknesses of the proposed algorithms and the role of the different components on several ...

Abstract

We consider a polyhedral approach to the weighted maximal b -clique problem. Given a node- and edge-weighted complete graph the problem is to find a complete subgraph (clique) with no more than b nodes such that the sum of the weights of all nodes and edges in the clique is maximal. We introduce four new classes of facet defining inequalities for the associated b -clique polytope. One of these inequality classes constitutes a generalization of the well ...

Abstract

We consider an extended formulation approach to the edge-weighted maximal clique problem. The problem is formulated by using additional variables for the set of nodes with the natural variables for the set of edges. We show that the proposed formulation is superior to the natural formulation both theoretically and practically. By using the projection technique, we can also derive new classes of facet-defining inequalities for the lower-dimensional polytope of the natural variables. Computational results are reported. ...

Abstract

The unconstrained quadratic binary program (UQP) is proving to be a successful modeling and solution framework for a variety of combinatorial optimization problems. Experience reported in the literature with several problem classes has demonstrated that this approach works surprisingly well in terms of solution quality and computational times, often rivaling and sometimes surpassing more traditional methods. In this paper we report on the application of UQP to the maximum edge-weighted clique problem. Computational experience is reported illustrating the attractiveness of the ...

Abstract

Let K n =( V , E ) be the complete undirected graph with weights c e associated to the edges in E . We consider the problem of finding the subclique C =( U , F ) of K n such that the sum of the weights of the edges in F is maximized and | U | b , for some b [1,…, n ]. This problem is called ...

Abstract

Abstract   This paper extends the recently introduced Phased Local Search (PLS) algorithm to more difficult maximum clique problems and also adapts the algorithm to handle maximum vertex/edge weighted clique instances. PLS is a stochastic reactive dynamic local search algorithm that interleaves sub-algorithms which alternate between sequences of iterative improvement, during which suitable vertices are added to the current sub-graph, and plateau search, where vertices of the current sub-graph are swapped with vertices not contained in the current sub-graph. These sub-algorithms differ ...

Abstract

Considered is the problem of selecting p out of n given points in some space, such that the minimum distance between pairs of selected points is maximized. This objective may be appropriate if the selected points correspond to facility sites and the objective is to have as ‘dispersed’ a set as possible. This problem is NP-complete. Related graph theoretical problems are discussed, integer programming models are proposed, and an outline is given on a line search procedure ...

Abstract

Facility dispersion problem deals with the location of facilities on a network so as to maximize some function of the distances between facilities. We consider the problem under two different optimality criteria, namely maximizing the minimum distance (MAX-MIN) between any pair of facilities and maximizing the average distance (MAX-AVG) between any pair of facilities. Under either criterion, the problem is known to be NP-hard, even when the distances satisfy the triangle inequality. We consider the question of obtaining near-optimal solutions. For ...

Abstract

We study the polyhedral structure of an integer programming formulation of the cardinality constrained Boolean quadratic problem. We give many facet-defining inequalities. The separation problems for these inequalities appear to be difficult, which explains, in part, the difficulty encountered in solving these problems via a branch-and-cut methodology. As a special case of these inequalities, we obtain some previously known inequalities for the equipartition problem. ...

Abstract

No Abstract ...

Abstract

We present some new ideas for characterizing and comparing largechemical databases. The comparison of the contents of large databases is nottrivial since it implies pairwise comparison of hundreds of thousands ofcompounds. We have developed methods for categorizing compounds into groupsor series based on their ring-system content, using precalculatedstructure-based hashcodes. Two large databases can then be compared bysimply comparing their hashcode tables. Furthermore, the number of distinctring-system combinations can be used as an indicator of database diversity.We also present an indepen- dent ...

Abstract

Dissimilarity-based compound selection has been suggested as an effective method for selecting structurally diverse subsets of chemical databases. This article reports a comparison of several maximum-dissimilarity and sphere-exclusion algorithms for dissimilarity-based selection. The effectiveness of the algorithms is quantified by the numbers of biological activity classes identified in subsets selected from the World Drugs Index database, and by the numbers of active compounds identified in feedback searches of this database. The experiments demonstrate the general effectiveness and efficiency of the MaxMin ...