constraintprogramming (CP) has proven useful in several areas, and though the initial impetus came from logic programming frameworks like CLP and CCP, the use of CP and constraint solving is obtaining wider appeal. W...
详细信息
Siu et al. propose stream CSPs (St-CSPs) as a generalisation of finite domain CSPs to cater for constraints on infinite streams, and a solving algorithm that produces a deterministic Buchi automaton recognising the so...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Siu et al. propose stream CSPs (St-CSPs) as a generalisation of finite domain CSPs to cater for constraints on infinite streams, and a solving algorithm that produces a deterministic Buchi automaton recognising the solution language. As a novel application, we demonstrate how St-CSPs can model mathematically and generate a PID controller for driving a self-balancing tray and an inverted pendulum in real-time. We propose and give formally the correctness of an improvement to the implementation that eliminates numerous unnecessary states in the solution automaton for St-CSPs involving the first temporal operator, thereby reducing solving time. We give two St-CSP examples that can benefit from our new implementation techniques. Our approach always generates a solution automaton not bigger than, but potentially exponentially smaller than, that produced by the original implementation. Experimental results show substantial improvements.
Binarized Neural Networks (BNNs) are an important class of neural network characterized by weights and activations restricted to the set {-1, +1}. BNNs provide simple compact descriptions and as such have a wide range...
详细信息
ISBN:
(纸本)9783030300487
Binarized Neural Networks (BNNs) are an important class of neural network characterized by weights and activations restricted to the set {-1, +1}. BNNs provide simple compact descriptions and as such have a wide range of applications in low-power devices. In this paper, we investigate a model-based approach to training BNNs using constraintprogramming (CP), mixed-integer programming (MIP), and CP/MIP hybrids. We formulate the training problem as finding a set of weights that correctly classify the training set instances while optimizing objective functions that have been proposed in the literature as proxies for generalizability. Our experimental results on the MNIST digit recognition dataset suggest that-when training data is limited-the BNNs found by our hybrid approach generalize better than those obtained from a state-of-the-art gradient descent method. More broadly, this work enables the analysis of neural network performance based on the availability of optimal solutions and optimality bounds.
constraint acquisition systems such as QuAcq and MultiAcq can assist non-expert users to model their problems as constraint networks by classifying (partial) examples as positive or negative. For each negative example...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
constraint acquisition systems such as QuAcq and MultiAcq can assist non-expert users to model their problems as constraint networks by classifying (partial) examples as positive or negative. For each negative example, the former focuses on one constraint of the target network, while the latter can learn a maximum number of constraints. Two bottlenecks of the acquisition process where boththese algorithms encounter problems are the large number of queries required to reach convergence, and the high cpu times needed to generate queries, especially near convergence. We propose methods that deal with boththese issues. the first one is an algorithm that blends the main idea of MultiAcq into QuAcq resulting in a method that learns as many constraints as MultiAcq does after a negative example, but with a lower complexity. the second is a technique that helps reduce the number of queries significantly. the third is based on the use of partial queries to cut down the time required for convergence. Experiments demonstrate that our resulting algorithm, which integrates all the new techniques, does not only generate considerably fewer queries than QuAcq and MultiAcq, but it is also by far faster than both of them, both in average query generation time and in total run time.
Given an arbitrary constraint a on 71 variables with domain size d, we show how to generate a custom propagator that establishes GAC in time O(nd) by precomputing the propagation that would be performed on every reach...
详细信息
ISBN:
(纸本)9783642153952
Given an arbitrary constraint a on 71 variables with domain size d, we show how to generate a custom propagator that establishes GAC in time O(nd) by precomputing the propagation that would be performed on every reachable subdomain of scope(c). Our propagators are stateless: they store no state between calls, and so incur no overhead in storing and backtracking state during search. the preprocessing step can take exponential time and the custom propagator is potentially exponential in size. However, for small constraints used repeatedly, in one problem or many, this technique can provide substantial practical gains. Our experimental results show that, compared with optimised implementations of the table constraint;this technique can lead to an order of magnitude speedup;while doing identical search on realistic problems. the technique can also be many times faster than a decomposition into primitive constraints in the Minion solver. Propagation is so fast that, for constraints available in our solver, the generated propagator compares well with a human-optimised propagator for the same constraint.
Most work in constraint satisfaction has concentrated on computing a solution to a given problem. In practice, it often happens that an existing solution needs to be modified to satisfy additional criteria or changes ...
详细信息
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.
there is no standard modelling language for constraintprogramming (CP) problems. Most solvers have their own modelling language. this makes it difficult for modellers to experiment with different solvers for a proble...
详细信息
ISBN:
(纸本)9783540749691
there is no standard modelling language for constraintprogramming (CP) problems. Most solvers have their own modelling language. this makes it difficult for modellers to experiment with different solvers for a problem. In this paper we present MiniZinc, a simple but expressive CP modelling language which is suitable for modelling problems for a range of solvers and provides a reasonable compromise between many design possibilities. Equally importantly, we also propose a low-level solver-input language called FlatZinc, and a straight forward translation from MiniZinc to FlatZinc that preserves all solver-supported global constraints. this lets a solver writer support MiniZinc with a minimum of effort-they only need to provide a simple FlatZinc front-end to their solver, and then combine it with an existing MiniZinc-to-FlatZinc translator. Such a front-end may then serve as a stepping stone towards a full MiniZine implementation that;is more tailored to the particular solver. A standard language for modelling CP problems will encourage experimentation with and comparisons between different solvers. Although MiniZinc is not perfect-no standard modelling language will be-we believe its simplicity, expressiveness, and case of implementation make it a practical choice for a standard language.
constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. the solver state is modified during propagation. But search requires the solver to return to a prev...
详细信息
ISBN:
(纸本)9783642042430
constraint propagation solvers interleave propagation, removing impossible values from variable domains, with search. the solver state is modified during propagation. But search requires the solver to return to a previous state. Hence a, propagation solver must determine how to maintain state during propagation and forward and backward search. this paper sets out the possible ways in which a propagation solver call choose to maintain state, and the restrictions that such choices place on the resulting system. Experiments illustrate the result of various choices for the three principle state components of a solver: variables, propagators, and dependencies between them. this paper also provides the first realistic comparison of trailing versus copying for state restoration.
this book constitutes the refereed proceedings of the 8thinternationalconference on principles and practice of constraintprogramming, CP 2002, held in Ithaca, NY, USA in September 2002.;the 38 revised full papers a...
详细信息
ISBN:
(数字)9783540461357
ISBN:
(纸本)9783540441205
this book constitutes the refereed proceedings of the 8thinternationalconference on principles and practice of constraintprogramming, CP 2002, held in Ithaca, NY, USA in September 2002.;the 38 revised full papers and 6 innovative application papers as well as the 14 short papers presented toghether with 25 abstracts from contributions to the doctoral program were carefully reviewed and selected from 146 submissions. All current issues in constraint processing are addressed, ranging from theoretical and foundational issues to application in various fields.
暂无评论