1,720,970 research outputs found
A new branch-and-filter exact algorithm for binary constraint satisfaction problems
Full text linkA binary constraint satisfaction problem (BCSP) consists in determining an assignment of values to variables that is compatible with a set of constraints. The problem is called binary because the constraints
involve only pairs of variables. The BCSP is a cornerstone problem in Constraint Programming (CP), appearing in a very wide range of real-world applications. In this work, we develop a new exact algorithm
which effectively solves the BCSP by reformulating it as a k -clique problem on the underlying microstructure graph representation. Our new algorithm exploits the cutting-edge branching scheme of the state-
of-the-art maximum clique algorithms combined with two filtering phases in which the domains of the
variables are reduced. Our filtering phases are based on colouring techniques and on heuristically solving
an associated boolean satisfiability (SAT) problem. In addition, the algorithm initialization phase performs
a reordering of the microstructure graph vertices that produces an often easier reformulation to solve. We
carry out an extensive computational campaign on a benchmark of almost 20 0 0 instances, encompassing numerous real and synthetic problems from the literature. The performance of the new algorithm is
compared against four SAT-based solvers and three general purpose CP solvers. Our tests reveal that the
new algorithm significantly outperforms all the others in several classes of BCSP instances
A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts
Full text linkWe study the Knapsack Problem with Conflicts, a generalization of the Knapsack Problem in which a set of conflicts specifies pairs of items which cannot be simultaneously selected. In this work, we propose a novel combinatorial branch-and-bound algorithm for this problem based on an n-ary branching scheme. Our algorithm effectively combines different procedures for pruning the branch-and-bound nodes based on different relaxations of the Knapsack Problem with Conflicts. Its main elements of novelty are: (i) the adoption of the branching-and-pruned set branching scheme which, while extensively used in the maximum-clique literature, was never successfully employed for solving the Knapsack Problem with Conflicts; (ii) the adoption of the Multiple-Choice Knapsack Problem for the derivation of upper bounds used for pruning the branch-and-bound tree nodes; and (iii) the design of a new upper bound for the latter problem which can be computed very efficiently. Key to our algorithm is its high pruning potential and the low computational effort that it requires to process each branch-and-bound node. An extensive set of experiments carried out on the benchmark instances typically used in the literature shows that, for edge densities ranging from 0.1 to 0.9, our algorithm is faster by up to two orders of magnitude than the state-of-the-art method and by up to several orders of magnitude than a state-of-the-art mixed-integer linear programming solver
A new branch-and-bound algorithm for the maximum edge-weighted clique problem
Full text linkWe study the maximum edge-weighted clique problem, a problem related to the maximum (vertex-weighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics, material science, computer vision, robotics, and many more. In this work, we propose a new combinatorial branch-and-bound algorithm for the problem which relies on a novel bounding procedure capable of pruning a very large amount of nodes of the branch-and-bound tree. Extensive computational experiments on random and structured graphs, encompassing standard benchmarks used in the literature as well as recently introduced real-world large-scale graphs, show that our new algorithm outperforms the state-of-the-art by several orders of magnitude on many instances
CliSAT: A new exact algorithm for hard maximum clique problems
Full text linkGiven a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the
largest possible number of vertices. We propose a new exact algorithm, called CliSAT , to solve the
MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial
optimization due to its practical relevance for a wide range of applications. The newly developed exact approach is a combinatorial branch-and-bound algorithm that exploits the state-of-the-art branching
scheme enhanced by two new bounding techniques with the goal of reducing the branching tree. The
first one is based on graph colouring procedures and partial maximum satisfiability problems arising in
the branching scheme. The second one is a filtering phase based on constraint programming and domain
propagation techniques. CliSAT is designed for structured MCP instances which are computationally
difficult to solve since they are dense and contain many interconnected large cliques. Extensive experiments on hard benchmark instances, as well as new hard instances arising from different applications,
show that CliSAT outperforms the state-of-the-art MCP algorithms, in some cases by several orders of
magnitude
A branch-and-cut algorithm for the Edge Interdiction Clique Problem
Full text linkGiven a graph G and an interdiction budget k∈N, the Edge Interdiction Clique Problem (EICP) asks to find a subset of at most k edges to remove from G so that the size of the maximum clique, in the interdicted graph, is minimized. The EICP belongs to the family of interdiction problems with the aim of reducing the clique number of the graph. The EICP optimal solutions, called optimal interdiction policies, determine the subset of most vital edges of a graph which are crucial for preserving its clique number. We propose a new set-covering-based Integer Linear Programming (ILP) formulation for the EICP with an exponential number of constraints, called the clique-covering inequalities. We design a new branch-and-cut algorithm which is enhanced by a tailored separation procedure and by an effective heuristic initialization phase. Thanks to the new exact algorithm, we manage to solve the EICP in several sets of instances from the literature. Extensive tests show that the new exact algorithm greatly outperforms the state-of-the-art approaches for the EICP
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
