SelfSplit is a simple static mechanism to convert a sequential tree-search code into a parallel one. In this paradigm, tree-search is distributed among a set of identical workers, each of which is able to autonomously...
详细信息
SelfSplit is a simple static mechanism to convert a sequential tree-search code into a parallel one. In this paradigm, tree-search is distributed among a set of identical workers, each of which is able to autonomously determine-without any communication with the other workers-the job parts it has to process. SelfSplit already proved quite effective in parallelizing Constraint Programming solvers. In the present paper we investigate the performance of SelfSplit when applied to a Mixed-Integer Linear Programming (MILP) solver. Both ad-hoc and general purpose MILP codes have been considered. Computational results show that SelfSplit, in spite of its simplicity, can achieve good speedups even in the MILP context. (C) 2018 Elsevier Ltd. All rights reserved.
Cographs have always been a research target in areas such as coloring, graph decomposition, and spectral theory. In this work, we present an algorithm to generate all unlabeled cographs with n vertices, based on the g...
详细信息
Cographs have always been a research target in areas such as coloring, graph decomposition, and spectral theory. In this work, we present an algorithm to generate all unlabeled cographs with n vertices, based on the generation of cotrees. The delay of our algorithm (time spent between two consecutive outputs) is O(n). The time needed to generate the first output is also O(n), which gives an overall O(n M-n) time complexity, where M-n is the number of unlabeled cographs with n vertices. The algorithm avoids the generation of duplicates (isomorphic outputs) and produces, as a by-product, a linear ordering of unlabeled cographs with n vertices. (C) 2018 Elsevier B.V. All rights reserved.
作者：
Genisson, RichardRauzy, AntoineLIM
Université Aix-Marseille I Technop. de Château Gombert 39 rue Joliot Curie 13453 Marseille Cedex 13 France LaBRI
Université Bordeaux I 351 cours de la Libération 33405 Talence Cedex France
In this paper, we study the efficiency of general solvers such as the Davis-Putnam procedure or Forward Checking on the main polynomial restrictions of SAT and Constraint Satisfaction Problems. To achieve this goal, w...
详细信息
In this paper, we study the efficiency of general solvers such as the Davis-Putnam procedure or Forward Checking on the main polynomial restrictions of SAT and Constraint Satisfaction Problems. To achieve this goal, we introduce a parametrized algorithmic scheme of polynomial complexity. We show its completness on the former restrictions. We report experiments that enforce the obtained theoretical results.
Polygonal array graphs have been widely investigated, and they represent a relevant area of interest in mathematical chemistry because they have been used to study intrinsic properties of molecular graphs. For example...
详细信息
ISBN:
(纸本)9783319592268;9783319592251
Polygonal array graphs have been widely investigated, and they represent a relevant area of interest in mathematical chemistry because they have been used to study intrinsic properties of molecular graphs. For example, to determine the Merrifield-Simmons index of a polygonal array A(n) that is the number of independent sets of that graph, denoted as i(A(n)). In this paper we consider the problem of extending an initial polygonal array A(n) adding a new polygon p to form A(n+1), for minimizing or maximizing the Merrifield-Simmons index i(A(n+1)) = i(A(n) boolean OR p). Our method does not require to compute i(A(n)) or i(A(n) boolean OR p), explicitly.
High sensitivity to initial conditions is generally viewed as a drawback of tree search methods because it leads to erratic behavior to be mitigated somehow. In this paper we investigate the opposite viewpoint and con...
详细信息
High sensitivity to initial conditions is generally viewed as a drawback of tree search methods because it leads to erratic behavior to be mitigated somehow. In this paper we investigate the opposite viewpoint and consider this behavior as an opportunity to exploit. Our working hypothesis is that erraticism is in fact just a consequence of the exponential nature of tree search that acts as a chaotic amplifier, so it is largely unavoidable. We propose a bet-and-run approach to actually turn erraticism to one's advantage. The idea is to make a number of short sample runs with randomized initial conditions, to bet on the "most promising" run selected according to certain simple criteria, and to bring it to completion. Computational results on a large testbed of mixed integer linear programs from the literature are presented, showing the potential of this approach even when embedded in a proof-of-concept implementation.
暂无评论