the Distributed constraint Optimization Problem (DCOP) is an elegant paradigm for modeling and solving multi-agent problems which are distributed in nature, and where agents cooperate to optimize a global objective wi...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
the Distributed constraint Optimization Problem (DCOP) is an elegant paradigm for modeling and solving multi-agent problems which are distributed in nature, and where agents cooperate to optimize a global objective within the confines of localized communication. Since solving DCOPs optimally is NP-hard, recent effort in the development of DCOP algorithms has focused on incomplete methods. Unfortunately, many of such proposals do not provide quality guarantees or provide a loose quality assessment. thus, this paper proposes the Distributed Large Neighborhood Search (DLNS), a novel iterative local search framework to solve DCOPs, which provides guarantees on solution quality refining lower and upper bounds in an iterative process. Our experimental analysis of DCOP benchmarks on several important classes of graphs illustrates the effectiveness of DLNS in finding good solutions and tight upper bounds in both problems with and without hard constraints.
the RCC8 language is a widely-studied formalism for describing topological arrangements of spatial regions. Two fundamental reasoning problems that are associated with RCC8 are the problems of satisfiability and reali...
详细信息
ISBN:
(数字)9783319983349
ISBN:
(纸本)9783319983349;9783319983332
the RCC8 language is a widely-studied formalism for describing topological arrangements of spatial regions. Two fundamental reasoning problems that are associated with RCC8 are the problems of satisfiability and realization. Given a qualitative constraint network (QCN) of RCC8, the satisfiability problem is deciding whether it is possible to assign regions to the spatial variables of the QCN in such a way that all of its constraints are satisfied (solution). the realization problem is producing an actual spatial model that can serve as a solution. Researchers in RCC8 focus either on symbolically checking the satisfiability of a QCN or on presenting a method to realize (valuate) a satisfiable QCN. To the best of our knowledge, a combination of those two lines of research has not been considered in the literature in a unified and homogeneous approach, as the first line deals with native constraint-based methods, and the second one with rich mathematical structures that are difficult to implement. In this article, we combine the two aforementioned lines of research and explore the opportunities that surface by interrelating the corresponding reasoning problems, viz., the problems of satisfiability and realization. We restrict ourselves to QCNs that, when satisfiable, are realizable with rectangles. In particular, we propose an incremental SAT-based approach for providing a framework that reasons about the RCC8 language in a counterexample-guided manner. the incrementality of our approach also avoids the usual blow-up and the lack of scalability in SAT-based encodings. Specifically, our SAT-translation is parsimonious, i.e, constraints are added incrementally in a manner that guides the embedded SAT-solver and forbids it to find the same counter-example twice. We experimentally evaluated our approach and studied its scalability against state-of-the-art solvers for reasoning about RCC8 relations using a varied dataset of instances. the approach scales up and is competiti
the Compact-Table (CT) algorithm is the current state-of-the-art algorithm for enforcing Generalized Arc Consistency (GAC) on table constraints during search. Recently, algorithms for enforcing Pairwise Consistency (P...
详细信息
the proceedings contain 36 papers. the special focus in this conference is on theory and practice of Natural Computing. the topics include: A linear constrained optimization benchmark for probabilistic search algorith...
ISBN:
(纸本)9783030040697
the proceedings contain 36 papers. the special focus in this conference is on theory and practice of Natural Computing. the topics include: A linear constrained optimization benchmark for probabilistic search algorithms: the rotated klee-minty problem;the design of (almost) disjunct matrices by evolutionary algorithms;how the “Baldwin Effect” can guide evolution in dynamic environments;landscape-aware constraint handling applied to differential evolution;fuel efficient truck platooning with time restrictions and multiple speeds solved by a particle swarm optimisation;automated design of genetic programming classification algorithms for financial forecasting using evolutionary algorithms;optimizing fleet staging of air ambulances in the Province of Ontario;a Hierarchical approach to grammar-guided genetic programming: the case of scheduling in heterogeneous networks;multi-memetic mind evolutionary computation algorithm based on the landscape analysis;computing preimages and ancestors in reaction systems;DNA-guided assembly of nanocellulose meshes;classically time-controlled quantum automata;mortal organisms rescue immortal organisms from evolutionary inertness: Perspective of the programmed self-decomposition model;integrative biological, cognitive and affective modeling of a drug-therapy for a post-traumatic stress disorder;symbolic analysis of machine behaviour and the emergence of the machine language;it is time to dissolve old dichotomies in order to grasp the whole picture of cognition;network-oriented modeling of the interaction of adaptive joint decision making, bonding and mirroring;network reification as a unified approach to represent network adaptation principles within a network;relating an adaptive network’s structure to its emerging behaviour for Hebbian learning;on capacity with incremental learning by simplified chaotic neural network.
this special issue of theory and practice of Logic programming (TPLP) contains the regular papers accepted for presentation at the 33rd internationalconference on Logic programming (ICLP 2017), held in Melbourne, Aus...
详细信息
this special issue of theory and practice of Logic programming (TPLP) contains the regular papers accepted for presentation at the 33rd internationalconference on Logic programming (ICLP 2017), held in Melbourne, Australia from the 28th of August to the 1st of September, 2017. ICLP 2017 was colocated withthe 23rd internationalconference on principles and practice of constraintprogramming (CP 2017) and the 20thinternationalconference on theory and Applications of Satisfiability Testing (SAT 2017). Since the first conference held in Marseille in 1982, ICLP has been the premier international event for presenting research in logic programming.
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express r...
详细信息
constraintprogramming is a family of techniques for solving combinatorial problems, where the problem is modelled as a set of decision variables (typically with finite domains) and a set of constraints that express relations among the decision variables. One key concept in constraintprogramming is propagation: reasoning on a constraint or set of constraints to derive new facts, typically to remove values from the domains of decision variables. Specialized propagation algorithms (propagators) exist for many classes of constraints. the concept of support is pervasive in the design of propagators. Traditionally, when a domain value ceases to have support, it may be removed because it takes part in no solutions. Arc-consistency algorithms such as AC2001 [in: Proceedings 17thinternational Joint conference on Artificial Intelligence (IJCAI 2001), 2001, pp. 309-315] make use of support in the form of a single domain value. GAC algorithms such as GAC-Schema [in: Proceedings 15thinternational Joint conference on Artificial Intelligence (IJCAI 97), 1997, pp. 398-404] use a tuple of values to support each literal. We generalize these notions of support in two ways. First, we allow a set of tuples to act as support. Second, the supported object is generalized from a set of literals (GAC-Schema) to an entire constraint or any part of it. We design a methodology for developing correct propagators using generalized support. A constraint is expressed as a family of support properties, which may be proven correct against the formal semantics of the constraint. We show how to derive correct propagators from the constructive proofs of the support properties. the framework is carefully designed to allow efficient algorithms to be produced. Derived algorithms may make use of dynamic literal triggers or watched literals [in: Proc. 12thinternationalconference on the principles and practice of constraintprogramming (CP 2006), 2006, pp. 182-197] for efficiency. Finally, three case st
constraint handling rules provide descriptions for constraint solvers. However, they fall short when those constraints specify some binding structure, like higher-rank types in a constraint-based type inference algori...
详细信息
constraint handling rules provide descriptions for constraint solvers. However, they fall short when those constraints specify some binding structure, like higher-rank types in a constraint-based type inference algorithm. In this paper, the term syntax of constraints is replaced by lambda-tree syntax, in which binding is explicit, and a new del generic quantifier is introduced, which is used to create new fresh constants.
the recent series 5 of the Answer Set programming (ASP) system clingo provides generic means to enhance basic ASP withtheory reasoning capabilities. We instantiate this framework with different forms of linear constr...
详细信息
the recent series 5 of the Answer Set programming (ASP) system clingo provides generic means to enhance basic ASP withtheory reasoning capabilities. We instantiate this framework with different forms of linear constraints and elaborate upon its formal properties. Given this, we discuss the respective implementations, and present techniques for using these constraints in a reactive context. More precisely, we introduce extensions to clingo with difference and linear constraints over integers and reals, respectively, and realize them in complementary ways. Finally, we empirically evaluate the resulting clingo derivatives clingo[dl] and clingo[lp] on common language fragments and contrast them to related ASP systems.
We describe an optimization application in the context of steel manufacturing, to design and schedule batches for annealing furnaces. Our solution approach uses a two-phase decomposition. the first phase groups togeth...
详细信息
ISBN:
(纸本)9783319661582;9783319661575
We describe an optimization application in the context of steel manufacturing, to design and schedule batches for annealing furnaces. Our solution approach uses a two-phase decomposition. the first phase groups together orders into batches using a mixed-integer linear programming model. the second phase assigns the batches to furnaces and schedules them over time, using constraintprogramming. Our solution has been developed for operational use in two plants of a steel manufacturer in North America.
constraint handling rules provide descriptions for constraint solvers. However, they fall short when those constraints specify some binding structure, like higher-rank types in a constraint-based type inference algori...
详细信息
constraint handling rules provide descriptions for constraint solvers. However, they fall short when those constraints specify some binding structure, like higher-rank types in a constraint-based type inference algorithm. In this paper, the term syntax of constraints is replaced by lambda-tree syntax, in which binding is explicit, and a new del generic quantifier is introduced, which is used to create new fresh constants.
暂无评论