constraintprogramming models have been recently proposed to solve cryptanalysis problems for symmetric block ciphers such as AES. these models are more efficient than dedicated approaches but their design is difficul...
详细信息
HPC systems are increasingly being used for big data analytics and predictive model building that employ many short jobs. In these application scenarios, HPC job dispatchers need to process large numbers of short jobs...
详细信息
ISBN:
(纸本)9783030300487
HPC systems are increasingly being used for big data analytics and predictive model building that employ many short jobs. In these application scenarios, HPC job dispatchers need to process large numbers of short jobs quickly and make decisions on-line while ensuring high Quality-of-Service (QoS) levels and meet demanding timing requirements. constraintprogramming (cp) is an effective approach for tackling job dispatching problems. Yet, the state-of-the-art cp-based job dispatchers are unable to satisfy the challenges of on-line dispatching and take advantage of job duration predictions. these limitations jeopardize achieving high QoS levels, and consequently impede the adoption of cp-based dispatchers in HPC systems. We propose a class of cp-based dispatchers that are more suitable for HPC systems running modern applications. the new dispatchers are able to reduce the time required for generating on-line dispatching decisions significantly, and are able to make effective use of job duration predictions to decrease waiting times and job slowdowns, especially for workloads dominated by short jobs.
In this paper, we show how model-checking can be generalized to temporal logic constraint solving, by considering temporal logic formulae with free variables over some domain D, and by computing a validity domain for ...
详细信息
ISBN:
(纸本)9783642042430
In this paper, we show how model-checking can be generalized to temporal logic constraint solving, by considering temporal logic formulae with free variables over some domain D, and by computing a validity domain for the variables rather than a truth value for the formula. this allows us to define a continuous degree of satisfaction for a temporal logic formula ill a, given structure, opening up the field of model-checking to optimization. We illustrate this approach with reverse engineering problems coming from systems biology, and provide some performance figures oil parameter optimization problems with respect to temporal logic specifications.
We define a model for heuristic tree search which assumes that the quality of the heuristic used for ordering the successors of a node improves as depth increases. We show that a usual value ordering heuristic for sol...
详细信息
ISBN:
(纸本)3540666265
We define a model for heuristic tree search which assumes that the quality of the heuristic used for ordering the successors of a node improves as depth increases. We show that a usual value ordering heuristic for solving constraint satisfaction problems fits to this model. Our model defines a partial order on the leaf nodes of the search tree, according to their probability to be a solution. We check which search strategies among interleaved depth-first search (IDFS), limited discrepancy search (LDS) and depth-bounded discrepancy search (DDS) visit the leaf nodes while respecting the partial order. Our study leads to conclude that, among these strategies, only Pure IDFS and a slight modification of improved LDS respect it.
作者:
Golden, KPang, WLNASA
Ames Res Ctr Computat Sci Div Moffett Field CA 94035 USA NASA
Ames Res Ctr QSS Grp Inc Moffett Field CA 94035 USA
this paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings...
详细信息
ISBN:
(纸本)3540202021
this paper discusses an approach to representing and reasoning about constraints over strings. We discuss how string domains can often be concisely represented using regular languages, and how constraints over strings, and domain operations on sets of strings, can be carried out using this representation.
ABT is the reference algorithm for asynchronous distributed constraint satisfaction. When searching, ABT produces nogoods as justifications of deleted values. When one of such nogoods has an empty left-hand side, the ...
详细信息
ISBN:
(纸本)9783540859574
ABT is the reference algorithm for asynchronous distributed constraint satisfaction. When searching, ABT produces nogoods as justifications of deleted values. When one of such nogoods has an empty left-hand side, the considered value is eliminated unconditionally, once and for all. this value deletion can be propagated using standard arc consistency techniques, producing new deletions in the domains of other variables. this causes substantial reductions in the search effort required to solve a class of problems. We also extend this idea to the propagation of conditional deletions. something already proposed in the past. We provide experimental results that show the benefits of the proposed approach, especially considering communication cost.
the Virtual Arc Consistency (VAC) algorithm by Cooper et al. is a soft local consistency technique that computes, in linear space, a bound on the basic LP relaxation of the Weighted CSP (WCSP). We generalize this tech...
详细信息
Block-coordinate descent (BCD) is a popular method in large-scale optimization. Unfortunately, its fixed points are not global optima even for convex problems. A succinct characterization of convex problems optimally ...
详细信息
Benzenoids are a subfamily of hydrocarbons (molecules that are only made of hydrogen and carbon atoms) whose carbon atoms form hexagons. these molecules are widely studied in theoretical chemistry. then, there is a lo...
详细信息
Testing algorithms across a wide range of problem instances is crucial to ensure the validity of any claim about one algorithm’s superiority over another. However, when it comes to inference algorithms for probabilis...
详细信息
暂无评论