PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Powiadomienia systemowe
  • Sesja wygasła!

Znaleziono wyników: 9

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  constraint satisfaction problems
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available Models of multimodal networks and transport processes
Bocewicz G., Muszyński W., Banaszak Z.
Bulletin of the Polish Academy of Sciences. Technical Sciences
|
2015
|
Vol. 63, nr 3
635--650
EN
Models of multimodal cyclic processes, i.e. processes realized with synergic utilization of various local and cyclic acting processes, play a determining role in an evaluation of functioning efficiency inter alia in public transport systems, passengers movement, cargo transport, data and energy transmission etc. We assume that the structure of a system determines repertoire of its behaviors. The paper presents a constraints satisfaction problem, which solving enables an evaluation of potential behaviors of the system of concurrently interacting local cyclic processes. Consequently, it is possible to plan and schedule the multimodal processes realized in that system. The constraints satisfaction problem, enabling the search for the structure of inter-position transport system and guaranteeing realization of assumed schedule of multi-assortment production was formulated for a declarative model of the multimodal transportation processes system. The attached calculation example illustrates the computational efficiency of the proposed approach.
2
Content available remote A fine-grained arc-consistency algorithm for non-normalized constraint satisfaction problems
Arangú M., Salido M. A.
International Journal of Applied Mathematics and Computer Science
|
2011
|
Vol. 21, no 4
733-744
EN
Constraint programming is a powerful software technology for solving numerous real-life problems. Many of these problems can be modeled as Constraint Satisfaction Problems (CSPs) and solved using constraint programming techniques. However, solving a CSP is NP-complete so filtering techniques to reduce the search space are still necessary. Arcconsistency algorithms are widely used to prune the search space. The concept of arc-consistency is bidirectional, i.e., it must be ensured in both directions of the constraint (direct and inverse constraints). Two of the most well-known and frequently used arc-consistency algorithms for filtering CSPs are AC3 and AC4. These algorithms repeatedly carry out revisions and require support checks for identifying and deleting all unsupported values from the domains. Nevertheless, many revisions are ineffective, i.e., they cannot delete any value and consume a lot of checks and time. In this paper, we present AC4-OP, an optimized version of AC4 that manages the binary and non-normalized constraints in only one direction, storing the inverse founded supports for their later evaluation. Thus, it reduces the propagation phase avoiding unnecessary or ineffective checking. The use of AC4-OP reduces the number of constraint checks by 50% while pruning the same search space as AC4. The evaluation section shows the improvement of AC4-OP over AC4, AC6 and AC7 in random and non-normalized instances.
3
Content available remote Restoring CSP Satisfiability with MaxSAT
Lynce I., Marques-Silva J.
Fundamenta Informaticae
|
2011
|
Vol. 107, nr 2/3
249-266
EN
The extraction of a Minimal Unsatisfiable Core (MUC) in a Constraint Satisfaction Problem (CSP) aims to identify a subset of constraints that make a CSP instance unsatisfiable. Recent work has addressed the identification of a Minimal Set of Unsatisfiable Tuples (MUST) in order to restore the CSP satisfiability with respect to that MUC. A two-step algorithm has been proposed: first, a MUC is identified, and second, a MUST in the MUC is identified. This paper proposes an integrated algorithm for restoring satisfiability in a CSP, making use of a MaxSAT solver. The proposed approach encodes the CSP instance as a partial MaxSAT instance, in such a way that solving the MaxSAT instance corresponds to identifying the smallest set of tuples to be removed from the CSP instance to restore satisfiability. Experimental results illustrate the feasibility of the approach.
4
Content available remote Deriving Information from Sampling and Diving
Lombardi M., Milano M., Roli A., Zanarini A.
Fundamenta Informaticae
|
2011
|
Vol. 107, nr 2/3
267-287
EN
We investigate the impact of information extracted from sampling and diving on the solution of Constraint Satisfaction Problems (CSP). A sample is a complete assignment of variables to values taken from their domain according to a given distribution. Diving consists in repeatedly performing depth first search attempts with random variable and value selection, constraint propagation enabled and backtracking disabled; each attempt is called a dive and, unless a feasible solution is found, it is a partial assignment of variables (whereas a sample is a –possibly infeasible– complete assignment). While the probability of finding a feasible solution via sampling or diving is negligible if the problem is difficult enough, samples and dives are very fast to generate and, intuitively, even when they are infeasible, they can provide some statistical information on search space structure. The aim of this paper is to understand to what extent it is possible to support the CSP solving process with information derived from sampling and diving. In particular, we are interested in extracting from samples and dives precise indications on the quality of individual variable-value assignments with respect to feasibility. We formally prove that even uniform sampling could provide precise evaluation of the quality of single variable-value assignments; as expected, this requires huge sample sizes and is therefore not useful in practice. On the contrary, diving is much better suited for assignment evaluation purposes. We undertake a thorough experimental analysis on a collection of Partial Latin Square and Car Sequencing instances to assess the quality of information provided by dives. Dive features are identified and their impact on search is evaluated. Results show that diving provides information that can be fruitfully exploited.
5
Content available remote Constraint Satisfaction Problems in Clausal Form I: Autarkies and Deficiency
Kullmann O.
Fundamenta Informaticae
|
2011
|
Vol. 109, nr 1
27-81
EN
We consider the problem of generalising boolean formulas in conjunctive normal form by allowing non-boolean variables, with the goal of maintaining combinatorial properties. Requiring that a literal involves only a single variable, the most general form of literals are the wellknown "signed literals", corresponding to unary constraints in CSP. However we argue that only the restricted form of "negative monosigned literals" and the resulting generalised clause-sets, corresponding to "sets of no-goods" in the AI literature, maintain the essential properties of boolean conjunctive normal forms. In this first part of a mini-series of two articles, we build up a solid foundation for (generalised) clause-sets, including the notion of autarky systems, the interplay between autarkies and resolution, and basic notions of (DP-)reductions. As a basic combinatorial parameter of generalised clause-sets we introduce the (generalised) notion of deficiency, which in the boolean case is the difference between the number of clauses and the number of variables. Autarky theory plays a fundamental role here, and we concentrate especially on matching autarkies (based on matching theory). A natural task is to determine the structure of (matching) lean clause-sets, which do not admit non-trivial (matching) autarkies. A central result is the computation of the lean kernel (the largest lean subset) of a (generalised) clause-set in polynomial time for bounded maximal deficiency.
6
Content available remote Evaluating and Improving Modern Variable and Revision Ordering Strategies in CSPs
Balafoutis T., Stergiou K.
Fundamenta Informaticae
|
2010
|
Vol. 102, nr 3/4
229-261
EN
A key factor that can dramatically reduce the search space during constraint solving is the criterion under which the variable to be instantiated next is selected. For this purpose numerous heuristics have been proposed. Some of the best of such heuristics exploit information about failures gathered throughout search and recorded in the form of constraint weights, while others measure the importance of variable assignments in reducing the search space. In this work we experimentally evaluate the most recent and powerful variable ordering heuristics, and new variants of them, over a wide range of benchmarks. Results demonstrate that heuristics based on failures are in general more efficient. Based on this, we then derive new revision ordering heuristics that exploit recorded failures to efficiently order the propagation list when arc consistency is maintained during search. Interestingly, in addition to reducing the number of constraint checks and list operations, these heuristics are also able to cut down the size of the explored search tree.
7
Content available remote A SAT-based Method for Solving the Two-dimensional Strip Packing Problem
Soh T., Tamura N., Banbara M., Inouey K., Nabeshima H.
Fundamenta Informaticae
|
2010
|
Vol. 102, nr 3/4
467-487
EN
We propose a satisfiability testing (SAT) based exact approach for solving the twodimensional strip packing problem (2SPP). In this problem, we are given a set of rectangles and one large rectangle called a strip. The goal of the problem is to pack all rectangles without overlapping, into the strip by minimizing the overall height of the packing. Although the 2SPP has been studied in Operations Research, some instances are still hard to solve. Our method solves the 2SPP by translating it into a SAT problem through a SAT encoding called order encoding. The translated SAT problems tend to be large; thus, we apply several techniques to reduce the search space by symmetry breaking and positional relations of rectangles. To solve a 2SPP, that is, to compute the minimum height of a 2SPP, we need to repeatedly solve similar SAT problems. We thus reuse learned clauses and assumptions from the previously solved SAT problems. To evaluate our approach, we obtained results for 38 instances from the literature and made comparisons with a constraint satisfaction solver and an ad-hoc 2SPP solver.
8
Content available AND-OR graph with knowledge propagation rules as a model for Constraint Satisfaction Problems
Ligęza A.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2009
|
T. 13, z. 2
411-419
EN
In this paper a model for Constraint Satisfaction Problems based on the concept of AND-OR graph is presented. The graph provides a structure to model search-space for alternative solutions. In order to represent auxiliary constraints it is completed with a set of rules for knowledge propagation. The rules can be used for efficient modelling of constraints for knowledge propagation and for detection of inconsistency. An example from the area of automated diagnosis is used to illustrate the application.
PL
W pracy przedstawiono koncepcję zastosowania grafu AND--OR do rozwiązywania problemów z ograniczeniami. Dla efektywnej eliminacji niepoprawnych rozwiązań zastosowano system regułowy. Jest on wykorzystywany do propagacji wiedzy. W przypadku wykrycia niespójności, potencjalne rozwiązanie jest eliminowane. Rozważania przeprowadzono na przykładzie zastosowania proponowanego podejścia do eliminacji niepoprawnych rozwiązań problemu diagnostycznego.
9
Content available remote Building Constraint Satisfaction Problem solvers using
Castro C.
Fundamenta Informaticae
|
1998
|
Vol. 34, nr 3
263-293
EN
In this paper, we formalize Constraint Satisfaction Problem manipulation using a rule-based approach. Based on the notion of Computational Systems, we associate basic transformations carried out by traditional constraint solving algorithms with rewrite rules, and heuristics with strategies establishing the order of application of the inferences. In this way, a constraint solver can be viewed as a computational system aimed to transform a set of constraints in a particular solved from. The distinction made between deduction rules and strategies, allows to describe constraint handling in a very abstract way, prototype new heuristics almost by modifying only the choice of rules, prove termination in an easier way, and combine constraint solving with other computational systems. To validate our approach we have implemented the system COLETTE which is currently executable in ELAN, an environment for prototyping computational systems. We have realized how easy it is to integrate and reuse solvers developed following this approach. We hope that this work leads the way to integrating the knowledge existing in the domain of Automated Deduction and Constraint Solving
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.