the problem of transporting vehicle components in a car manufacturer workshop can be seen as a large scale single vehicle pickup and delivery problem with periodic time windows. Our experimental evaluation indicates t...
详细信息
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...
详细信息
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.
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.
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.
作者:
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.
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...
详细信息
Distributed computing is increasingly important at a time when the doubling of the number of transistors on a processor every 18 months no longer translates in a doubling of speed but instead a doubling of the number ...
详细信息
ISBN:
(纸本)3540462678
Distributed computing is increasingly important at a time when the doubling of the number of transistors on a processor every 18 months no longer translates in a doubling of speed but instead a doubling of the number of cores. Unfortunately, it also places significant conceptual and implementation burden on programmers. this paper aims at addressing this challenge for constraint-based local search (CBLS), whose search procedures typically exhibit inherent parallelism stemming from multistart, restart, or population-based techniques whose benefits have been demonstrated both experimentally and theoretically. the,paper presents abstractions that allows distributed CBLS programs to be close to their sequential and parallel counterparts, keeping the conceptual and implementation overhead of distributed computing minimal. A preliminary implementation in COMET exhibits significant speed-ups in constraint satisfaction and optimization applications. the implementation also scales well withthe number of machines. Of particular interest is the observation that generic abstractions of CBLS and cp, such as models and solutions, and advanced control structures such as events and closures, play a fundamental role to keep the distance between sequential and distributed CBLS programs small. As a result, the abstractions directly apply to cp programs using multistarts or restarts procedures.
Routing problems appear in many practical applications. In the context of constraintprogramming, circuit constraints have been successfully developed to handle problems like the well-known Traveling Salesman Problem ...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Routing problems appear in many practical applications. In the context of constraintprogramming, circuit constraints have been successfully developed to handle problems like the well-known Traveling Salesman Problem or the Vehicle Routing Problem. these kind of constraints are linked to the search for a Hamiltonian circuit in a graph. In this paper we consider a more general multiple tour problem that consists in covering a part of the graph with a set of minimal cost circuits. We define a new global constraint WEIGHTEDSUBCIRCUITS that generalizes the WeightedCircuit constraint by releasing the need to obtain a Hamiltonian circuit. It enforces multiple disjoint circuits of bounded total cost to partially cover a weighted graph, the subsets of vertices to be covered being induced by external constraints. We show that enforcing Bounds Consistency for WeightedSubCircuits is NP-hard. We propose an incomplete but polynomial filtering method based on the search for a lower bound of a weighted Steiner circuit.
Bounded fractional hypertree width is the most general known structural property that guarantees polynomial-time solvability of the constraint satisfaction problem. Fichte et al. (cp 2018) presented a robust and ...
详细信息
暂无评论