Solution Dominance over Constraint Satisfaction Problems
Constraint Satisfaction Problems (CSPs) typically have many solutions that satisfy all constraints. Often though, some solutions are preferred over others, that is, some solutions dominate other solutions. We present solution dominance as a formal framework to reason about such settings. We define Constraint Dominance Problems (CDPs) as CSPs with a dominance relation, that is, a preorder over the solutions of the CSP. This framework captures many well-known variants of constraint satisfaction, including optimization, multi-objective optimization, Max-CSP, minimal models, minimum correction subsets as well as optimization over CP-nets and arbitrary dominance relations. We extend MiniZinc, a declarative language for modeling CSPs, to CDPs by introducing dominance nogoods; these can be derived from dominance relations in a principled way. A generic method for solving arbitrary CDPs incrementally calls a CSP solver and is compatible with any existing solver that supports MiniZinc. This encourages experimenting with different solution dominance relations for a problem, as well as comparing different solvers without having to modify their implementations.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Adapting Stochastic Search For Real-time Dynamic Weighted Constraint Satisfaction
This work presents two new algorithms for performing constraint satisfaction. The first algorithm presented, DMaxWalkSat, is a constraint solver specialized for solving dynamic, weighted constraint satisfaction problems.…
On the Use of Bi-Objective Evolutionary Algorithms for the Stochastic MKP under Dynamic Constraints
The multiple knapsack problem (MKP) generalizes the classical knapsack problem by assigning items to multiple knapsacks subject to capacity constraints. It is used to model many real-world resource allocation and schedul…
Approximating Solutions to the Knapsack Problem using the Lagrangian Dual Framework
The Knapsack Problem is a classic problem in combinatorial optimisation. Solving these problems may be computationally expensive. Recent years have seen a growing interest in the use of deep learning methods to approxima…
Model SelectionSolving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms
A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of…
Towards Improving Solution Dominance with Incomparability Conditions: A case-study using Generator Itemset Mining
Finding interesting patterns is a challenging task in data mining. Constraint based mining is a well-known approach to this, and one for which constraint programming has been shown to be a well-suited and generic framewo…