A wide range of constraints can be specified using automata or formal languages. the GRAMMAR constraint restricts the values taken by a sequence of variables to be a string from a given context-free language. Based on...
详细信息
ISBN:
(纸本)9783540749691
A wide range of constraints can be specified using automata or formal languages. the GRAMMAR constraint restricts the values taken by a sequence of variables to be a string from a given context-free language. Based on an AND/OR decomposition, we show that this constraint can be converted into clauses in conjunctive normal form without hindering propagation. Using this decomposition, we can propagate the GRAMMAR constraint in O(n(3)) time. the decomposition also provides an efficient incremental propagator. Down a branch of the search tree of length k, we can enforce GAC k times in the same O(n(3)) time. On specialized languages, running time can be even better. For example, propagation of the decomposition requires just O(n|delta|) time for regular languages where |delta| is the size of the transition table of the automaton recognizing the regular language. Experiments on a shift scheduling problem with a constraint solver and a state of the art SAT solver show that we can solve problems using this decomposition that defeat existing constraint solvers.
MQuAcq is an algorithm for active constraint acquisition that has been shown to outperform previous algorithms such as QuAcq and MultiAcq. In this paper, we exhibit two important drawbacks of MQuAcq. First, for each n...
详细信息
ISBN:
(纸本)9783030300487
MQuAcq is an algorithm for active constraint acquisition that has been shown to outperform previous algorithms such as QuAcq and MultiAcq. In this paper, we exhibit two important drawbacks of MQuAcq. First, for each negative example, the number of recursive calls to the main procedure of MQuAcq can be non-linear, making it impractical for large problems. Second, MQuAcq, as well as QuAcq and MultiAcq, does not take into account the structure of the learned problem. We propose MQuAcq-2, a new algorithm based on MQuAcq that integrates solutions to boththese problems. MQuAcq-2 exploits the structure of the learned problem by focusing the queries it generates to quasi-cliques of constraints. When dealing with a negative query, it only requires a linear number of iterations. MQuAcq-2 outperforms MQuAcq, especially on large problems.
In this paper, we consider a problem of management of crisis situations (incidents on nuclear or chemical plants, natural disasters...) that require remote sensing, using a set of ground and aerial robots. In this pro...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
In this paper, we consider a problem of management of crisis situations (incidents on nuclear or chemical plants, natural disasters...) that require remote sensing, using a set of ground and aerial robots. In this problem, sensed data must be transmitted in real-time to an operation center even in case of unavailability of traditional communication infrastructures. this implies that an ad hoc wireless communication network must be deployed, for instance using a fleet of UAVs acting as communication relays. From a technical point of view, we tackle a scheduling problem in which activities of mobile sensing robots and mobile relays must be synchronized both in time and space. Schedules produced must also be flexible and robust to the uncertainty about the duration of robot moves at execution time. the problem is modeled and solved using constraint-based local search, with some calls to graph algorithms that help defining good communication networks.
Elimination of inconsistent values in instances of the constraint satisfaction problem (CSP) conserves all solutions. Elimination of substitutable values conserves at least one solution. We show that certain values wh...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Elimination of inconsistent values in instances of the constraint satisfaction problem (CSP) conserves all solutions. Elimination of substitutable values conserves at least one solution. We show that certain values which are neither inconsistent nor substitutable can also be deleted while conserving at least one solution. this allows us to state novel rules for the elimination of values in a binary CSP. From a practical point of view, we show that one such rule can be applied in the same asymptotic time complexity as neighbourhood substitution but is strictly stronger. An alternative to the elimination of values from domains is the elimination of variables. We give novel satisfiability-preserving variable elimination operations. In each case we show that if the instance is satisfiable, then a solution to the original instance can always be recovered in low-order polynomial time from a solution to the reduced instance.
Distributed and collaborative agents are promising to play an important role in largescale multi-agent applications where such collaborative agents may enter into conflicts over their shared resources. Negotiation via...
ISBN:
(纸本)3540428631
Distributed and collaborative agents are promising to play an important role in largescale multi-agent applications where such collaborative agents may enter into conflicts over their shared resources. Negotiation via argumentation (NVA), where agents provide explicit arguments or justifications for their proposals for resolving conflicts, is a promising approach to collaborative conflict resolution[1]. While previous implemented argumentation systems have performed well in small-size applications, no systematic investigation in large scale has been done. thus, several questions about computational performance of argumentation remain unaddressed; such as understanding if (and when) argumentation actually speeds up conflict resolution convergence and formulating different collaborative NVA strategies to understand their impact on convergence. Answering these questions requires an abstract, well-understood computational model of argumentation, suitable for large-scale experimental investigations.
In distributed resource allocation a set of agents must assign their resources to a set of tasks. this problem arises in many real-world domains such as disaster rescue, hospital scheduling and the domain described in...
详细信息
Large neighbourhood search, a meta-heuristic, has proven to be successful on a wide range of optimisation problems. the algorithm repeatedly generates and searches through a neighbourhood around the current best solut...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
Large neighbourhood search, a meta-heuristic, has proven to be successful on a wide range of optimisation problems. the algorithm repeatedly generates and searches through a neighbourhood around the current best solution. thus, it finds increasingly better solutions by solving a series of simplified problems, all of which are related to the current best solution. In this paper, we show that significant benefits can be obtained by simulating local-search behaviour in constraintprogramming by using phase saving based on the best solution found so far during the search, activity-based search (VSIDS), and nogood learning. the approach is highly effective despite its simplicity, improving the highest scoring solver, Chuffed, in the free category of the MiniZinc Challenge 2017, and can be easily integrated into modern constraintprogramming solvers. We validated the results on a wide range of benchmarks from the competition library, comparing against seventeen state-of-the-art solvers.
the length-lex representation for set variables orders all subsets of a given universe of values according to cardinality and lexicography. To achieve length-lex bounds consistency for Knapsack constraints it has been...
详细信息
ISBN:
(纸本)9783642042430
the length-lex representation for set variables orders all subsets of a given universe of values according to cardinality and lexicography. To achieve length-lex bounds consistency for Knapsack constraints it has been proposed to decompose the constraint into two sum constraints. We provide theoretical and practical evidence which shows that decomposition increases the problem of computing a fixpoint which is intrinsic to the length-lex representation: 1. the fixpoint problem for this domain representation is NP-hard in general. 2. For a tractable sub-family of Knapsack decomposition takes more time than exponential brute-force enumeration. 3. Experimental results on decomposed Knapsack constraints show that exponential-time fixpoint computation is the rule and not some pathological exception.
In this paper we present a hybrid model for the demand acceptance variant of the routing and wavelength assignment problem in directed networks, an important benchmark problem in optical network design. Our solution u...
详细信息
ISBN:
(纸本)9783642042430
In this paper we present a hybrid model for the demand acceptance variant of the routing and wavelength assignment problem in directed networks, an important benchmark problem in optical network design. Our solution uses a decomposition into a MIP model for the routing and optimization aspect, combined with a finite domain constraint model for the wavelength assignment. If a solution to the constraint problem is found, it provides an optimal Solution to the overall problem. If the constraint problem is infeasible, we use an extended explanation technique to find a good relaxation of the problem which leads to a near optimal solution. Extensive experiments show that proven optimality is achieved for more than 99.8% of all cases tested, while run-times are orders of magnitude smaller than the best known MIP solution.
Machine systems for understanding hand-drawn sketches must reliably interpret common but sloppy curvilinear configurations. the task is commonly expressed as finding an image model in the image data, but few approache...
详细信息
暂无评论