the proceedings contain 115 papers. the topics discussed include: a description logic based ontology language;preference reasoning;symmetry definitions for constraint satisfaction problems;dynamic ordering for asynchr...
详细信息
ISBN:
(纸本)3540292381
the proceedings contain 115 papers. the topics discussed include: a description logic based ontology language;preference reasoning;symmetry definitions for constraint satisfaction problems;dynamic ordering for asynchronous backtracking on DisCSPs;incremental algorithms for local search from existential second-order logic;mind the gaps: a new splitting strategy for consistency techniques;a linear-logic semantics for constraint handling rules;ad-hoc global constraints for life;interval analysis in scheduling;planning and scheduling to minimize tardiness;applying constraintprogramming to rigid body protein docking;generating corrective explanations for interactive constraint satisfaction;and depth-first mini-bucket elimination.
Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. this paper strengthens this link. We study t...
详细信息
Recently, a strong link has been discovered between supermodularity on lattices and tractability of optimization problems known as maximum constraint satisfaction problems. this paper strengthens this link. We study the problem of maximizing a supermodular function which is defined on a product of n copies of a fixed finite lattice and given by an oracle. We exhibit a large class of finite lattices for which this problem can be solved in oracle-polynomial time in n. We also obtain new large classes of tractable maximum constraint satisfaction problems.
the eplex library of the (ECLPSe)-P-i constraint Logic programming platform allows the integration of Mathematical programming techniques with its native constraint Logic programming techniques within the same unified...
详细信息
ISBN:
(纸本)3540292381
the eplex library of the (ECLPSe)-P-i constraint Logic programming platform allows the integration of Mathematical programming techniques with its native constraint Logic programming techniques within the same unified framework. It provides an interface to state-of-the-art Mathematical programming solvers, and a set of programming primitives that allow 'hybrid' techniques to be easily expressed. this paper presents these facilities, and discusses some associated implementation issues.
this paper presents a technique for learning parameterized implied constraints. they can be added to a model to improve the solving process. Experiments on implied Gcc constraints show the interest of our approach.
ISBN:
(纸本)3540292381
this paper presents a technique for learning parameterized implied constraints. they can be added to a model to improve the solving process. Experiments on implied Gcc constraints show the interest of our approach.
We present a new and more efficient heuristic by restricting lookahead saturation (LAS) with NVO (neighbourhood variable ordering) and DEW (dynamic equality weighting). We report on the integration of this heuristic i...
详细信息
ISBN:
(纸本)3540292381
We present a new and more efficient heuristic by restricting lookahead saturation (LAS) with NVO (neighbourhood variable ordering) and DEW (dynamic equality weighting). We report on the integration of this heuristic in Satz, a high-performance SAT solver, showing empirically that it significantly improves the performance on an extensive range of benchmark problems that exhibit hard structure.
We combine mixed integer linear programming (MILP) and constraintprogramming (cp) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using cp, and the two are...
详细信息
ISBN:
(纸本)3540292381
We combine mixed integer linear programming (MILP) and constraintprogramming (cp) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using cp, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CR We also obtain much better solutions for problems that cannot be solved to optimality.
One of the attractive features of the constraint Handling Rules (CHR) programming language is its declarative semantics where rules are read as formulae in first-order predicate logic. However, the more CHR is used as...
详细信息
ISBN:
(纸本)3540292381
One of the attractive features of the constraint Handling Rules (CHR) programming language is its declarative semantics where rules are read as formulae in first-order predicate logic. However, the more CHR is used as a general-purpose programming language, the more the limitations of that kind of declarative semantics in modelling change become apparent. We propose an alternative declarative semantics based on (intuitionistic) linear logic, establishing strong theorems on both soundness and completeness of the new declarative semantics w.r.t. operational semantics.
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems aris...
详细信息
ISBN:
(纸本)3540292381
the generalization of the constraint satisfaction problem with universal quantifiers is a challenging PSPACE-complete problem, which is interesting theoretically and also relevant to solving other PSPACE problems arising in AI, such as reasoning with uncertainty, and multiplayer games. I define two new levels of consistency for QCSP, and give an algorithm to enforce consistency for one of these definitions. the algorithm is embedded in backtracking search, and tested empirically. the aims of this work are to increase the facilities available for modelling and to increase the power of constraint propagation for QCSPs. the work is motivated by examples from adversarial games.
this paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. the paper shows how to mak...
详细信息
ISBN:
(纸本)3540292381
this paper introduces an architecture for generic constraint implementations based on variable views and range iterators. Views allow, for example, to scale, translate, and negate variables. the paper shows how to make constraint implementations generic and how to reuse a single generic implementation with different views for different constraints. Applications of views exemplify their usefulness and their potential for simplifying constraint implementations. We introduce domain operations compatible with views based on range iterators to access and modify entire variable domains.
暂无评论