When the search for a solution to a constraint satisfaction problem backtracks, it is not usually worthwhile to remember the assignment that failed, because the same assignment will not occur again. However, we show t...
详细信息
constraints and preferences are ubiquitous in real-life. Moreover, preferences can be of many kinds: qualitative, quantitative, conditional, positive or negative, to name a few. Our ultimate goal is to define and stud...
详细信息
COMET is an object-oriented language supporting a constraint-based architecture for local search through declarative and search components. this paper proposes three novel and lightweight control abstractions for the ...
详细信息
ISBN:
(纸本)3540202021
COMET is an object-oriented language supporting a constraint-based architecture for local search through declarative and search components. this paper proposes three novel and lightweight control abstractions for the search component, significantly enhancing the compositionality, modularity, and reuse of COMET programs. these abstractions, which includes events and checkpoints, rely on first-class closures as the enabling technology. they are especially useful for expressing, in a modular way, heuristic and meta-heuristics, unions of heterogeneous neighborhoods, and sequential composition of neighborhoods.
Graphical models are a powerful representation framework for automated reasoning tasks. these models use graphs to capture conditional independencies between variables, allowing for a concise representation of the kno...
详细信息
ISBN:
(纸本)3540292381
Graphical models are a powerful representation framework for automated reasoning tasks. these models use graphs to capture conditional independencies between variables, allowing for a concise representation of the knowledge. Optimization tasks defined within this framework are typically tackled with either search or inference. Search methods are time exponential in the number of variables and can operate in linear space. Inference algorithms are time and space exponential in the tree width of the problem. this potentially higher space complexity makes these methods impractical. the AND/OR search space for graphical models is a newly introduced framework for search that is sensitive to the independencies in the model, often resulting in exponentially reduced complexities. the AND/OR search is based on a pseudo-tree which expresses independencies between variables, resulting in a search tree exponential in the depth of the pseudo-tree, rather than the number of variables. the AND/OR Branch-and-Bound algorithm (AOBB) is a new search method that explores the AND/OR search tree for solving optimization tasks in graphical models. In this paper we extend the algorithm for solving combinatorial optimization problems from the class of Mixed Integer Linear Programs (MILP). A MILP instance is a linear program where some of the decision variables are constrained to have only integer values at the optimal solution (we consider only binary integer variables). AOBB can be readily adapted for solving this class of optimization problems by arranging the integer variables into a start pseudo-tree and, then, traversing the corresponding AND/OR search tree. this rather straightforward extension can be further improved. We introduce a dynamic version of AOBB which uses a recursive decomposition of the problem, based on hypergraph separators. the hypergraph of a MILP instance has a vertex for each constraint and a hyperedge, which corresponds to a variable, connects all the constraints t
the availability of commodity multiprocessors offers significant opportunities for addressing the increasing computational requirements of optimization applications. To leverage these potential benefits, it is importa...
详细信息
Distributed constraint satisfaction problems (DisCSPs) with asymmetric constraints reflect the fact that agents may wish to retain their constraints private. Brito and Meseguer proposed a model for asymmetric constrai...
详细信息
ISBN:
(纸本)3540292381
Distributed constraint satisfaction problems (DisCSPs) with asymmetric constraints reflect the fact that agents may wish to retain their constraints private. Brito and Meseguer proposed a model for asymmetric constraints which they term Partially Known constraints (PKC). In the PKC model each binary constraint is divided between the two constraining agents. In order to solve the resulting DisCSP with asymmetric constraints, a two phase asynchronous backtracking algorithm was proposed [?]. In the first phase an asynchronous backtracking algorithm is performed, in which only the constraints held by the lower priority agents are examined. When a solution is reached, a second phase is performed in which the consistency of the solution is checked again, according to the constraints held by the higher priority agents in each binary constraint. the present paper proposes a one phase asynchronous backtracking algorithm which solves DisCSPs with asymmetric constraints. In the proposed asynchronous backtracking for asymmetric constraints algorithm (ABT_ASC) agents send their proposed assignments to all their neighbors in the constraints graph. Agents assign their local variables according to the priority order as in ABT but check the constraints also against the assignment of lower priority agents. When an agent detects a conflict between its own assignment and the assignment of an agent with a lower priority than itself, it sends a Nogood to the lower priority agent but keeps its assignment. Agents which receive a Nogood from higher priority agents, perform the same operations as if they have produced this Nogood themselves. As in ABT [?], they remove their current assignment from their current-domain, store the eliminating N ogood and reassign their variable. the ABT_ASC algorithm is evaluated experimentaly on randomly generated DisCSPs and is shown to outperform the 2-phase ABT with respect to two different distributed performance measures. ABT_ASC performs fewer non-concu
Given a configuration of parameters that satisfies a set of constraints, and given external changes that change and fix the value of some parameters making the configuration invalid, the problem of interactive reconfi...
详细信息
In this paper, we present an algorithm for finding utilitarian optimal solutions to Simple and Disjunctive Temporal Problems with Preferences (STPPs and DTPPs) based on Benders' decomposition and adopting SAT tech...
详细信息
Interactive tasks such as online configuration and e-commerce can be modelled as constraint satisfaction problems (CSPs). these can be solved interactively by a user assigning values to variables. the user may require...
详细信息
We introduce the study of Conditional symmetry breaking in constraintprogramming. this arises in a sub-problem of a constraint satisfaction problem, where the sub-problem satisfies some condition under which addition...
详细信息
暂无评论