constraintprogramming is rapidly becoming the technology of choice for modelling and solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their proble...
详细信息
ISBN:
(纸本)3540292438
constraintprogramming is rapidly becoming the technology of choice for modelling and solving complex combinatorial problems. However, users of this technology need significant expertise in order to model their problems appropriately. the lack of availability of such expertise is a significant bottleneck to the broader uptake of constraint technology in the real world. We present a new SAT-based version space algorithm for acquiring constraint satisfaction problems from examples of solutions and non-solutions of a target problem. An important advantage is the ease with which domain-specific knowledge can be exploited using the new algorithm. Finally, we empirically demonstrate the algorithm and the effect of exploiting domain-specific knowledge on improving the quality of the acquired constraint network.
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.
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.
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 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 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.
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.
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.
暂无评论