Questions tagged [constraint-satisfaction]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4
votes
2answers
426 views

How could an SMT solver be implemented as simple as possible?

I'm trying to figure out how an SMT solver works as simple as possible. Let's assume we have a simple input program with symbolic values x and ...
1
vote
0answers
40 views

Constraint-based layouts for GUIs

The VPRI institut founded by Alan Kay has some papers on constraint-based layouts for GUIs based on constraint solving. For instance: Wallingford: Toward a Constraint Reactive Programming Language ...
2
votes
1answer
272 views

Binarization of Constraints

I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints. I've been reading ...
3
votes
2answers
978 views

CSP Forward checking with n-ary (and binary) constraints

I have implemented my own CSP solver using a Backtracking algorithm. Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that ...
2
votes
0answers
483 views

Finding multi word anagrams from a set of words

Finding all anagrams for a word $w$ from a set of words is a problem with many well-known solutions (for example make a hash table mapping from the bag of letters of a word to the word). But what ...
6
votes
1answer
57 views

Small world theorem for set constraints

Let $S_1,\dots,S_n$ be variables representing unknown sets. A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions. A ...
0
votes
0answers
47 views

Handling eqaulity constraints in genetic algorithms

I am trying to solve an optimization problem with strength pareto algorithm (SPEA2). My decision variable have lower and upper bounds as well as an equality constraint (sum(dp) = 1). I am unable to ...
4
votes
1answer
180 views

Efficient algorithm for simple constraint satisfaction problem

There are $k$ Boolean variables $x_1, x_2, \dots, x_k$. $m$ arbitrary subsets of these variables such that sum of each set equals to $1$ (i.e., only one variable is $1$, the others are $0$). E.g., ...
0
votes
2answers
189 views

Modeling tiling problems as SAT problems

I read that tiling problems can be modeled as satisfiability problems (2-SAT?), but the author did not explain how. Is this true? What would be an example? By a "tiling problem" I mean you have a ...
1
vote
1answer
53 views

“strongly relational m-consistency when the domains contain at most m elements implies satisfiability” plain wrong?

Wikipedia states A constraint satisfaction problem may be relationally consistent, have no empty domain or unsatisfiable constraint, and yet be unsatisfiable. There are however some cases in ...
5
votes
0answers
413 views

Heuristic Repair and N-Queens Problem

Problem: I am trying to solve the $N$-Queens problem using Constraint Satisfaction and Heuristic Repair (also known as Min-Conflicts). I wrote a program to do this for any given $N$ queens and $N * N$...
4
votes
0answers
66 views

(Historical perspective) CSP and SAT inter-fertilization

[Disclaimer: this is a rather specialized question] It is known that techniques like Conflict-Driven Clause Learning (CDCL) and back-jumping -- which improved the Satisfiability (SAT) strategies ...
1
vote
0answers
129 views

Any reason to use the least-constrained variable heuristic when searching the solution of a CSP?

Is there any (kind of) (well-known) problem which can be expressed as a CSP in which the least constrained variable heuristic seems to give the best results, when employing backtracking with ...
3
votes
3answers
5k views

“Greater than” condition in integer linear program with a binary variable

How can one model the following condition in an integer linear program? $$A = \begin{cases} 1 & \text{if } B > C\\ 0 & \text{otherwise}\end{cases}$$ where $A \in \{0,1\}$ and $B, C \in \...
2
votes
1answer
161 views

Are finite-domain binary constraint satisfaction problems solvable in polynomial time?

Suppose a CSP has $n$ variables with finite domains of maximal size $d$. Furthermore, all constraints on the variables are binary. Can such a CSP be solved in polynomial time in $n$ and $d$? This was ...
0
votes
2answers
342 views

It's necessary to replace all the population each generation in a genetic algorithm?

I'm creating a timetable generator using GA's, and I'm stuck in the crossover part. Each generation, I just basically copy the best individuals (the 50% fittest individuals inside the population), ...
0
votes
0answers
45 views

Using Genetic Algorithms for volatile problems

Suppose I am looking at an optimization problem with a large number of interconnected constraints, but the solution is - in some regions - extremely volatile (With volatile I mean: small mutations ...
1
vote
1answer
25 views

Do approximation results for CSPs hold even when domains are of finite but different size?

We need to have a precise definition for what a constraint satisfaction problem (CSP) is to study it formally. Looking at a survey by Libor Barto, titled "The Constraint Satisfaction Problem and ...
3
votes
1answer
77 views

Theoretical CSPs where (in)equality constraints can be expressed as a single constraint?

I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language): ...
3
votes
1answer
76 views

existence of a permutation that satisfies order-constraints

I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints. For example, suppose we have a set (1, 2, 3, 4, 5) and a ...
1
vote
1answer
48 views

Can a $k$-ary relation have polymorphisms of arity greater than $k$?

To quote Hubie Chen's A Rendezvous of Logic, Complexity, and Algebra (2009) on constraint satisfaction and complexity, An operation $f : D^m \to D$ is a polymorphism of a relation $R \subseteq D^k$ ...
8
votes
2answers
253 views

Algorithm for solving planar constraint problem (“Pokemon Go monster finding”)

[Note: This problem was inspired by Pokemon Go. I will first explain the problem in mathematical terms, then explain the connection to Pokemon Go. My goal is not to cheat in the game. If I wanted to ...
2
votes
1answer
33 views

Similarity between Min-Conflicts and Coordinate Descent in CSPs?

I'm currently writing a library that solves a specific type of problem that involves mainly constraint satisfaction. I have came across the Min-Conflicts Algorithm which proved to be rather ...
0
votes
2answers
2k views

AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?

Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm? According to This Link and to ...
3
votes
0answers
40 views

Knowing if I have an optimal ordering for a OBDD

I'm learning about OBDD and I have learned that the size of a reduced OBDD (ROBDD) is dependent on the ordering of the variables, and that finding an optimal ordering is an NP hard problem. Say I ...
4
votes
1answer
358 views

Linear optimization or Constraint Satisfaction Problem with food

I was hoping someone could point me in the right direction in terms of what type of problem I am describing here so I can research it. My initial thought is that it is some form of Constraint ...
1
vote
1answer
551 views

CNF-SAT reduction problem variant

I'm aware of the Cook-Levin theorem. I've also seen how to reduce SAT to 3-CNF SAT to show that the latter is also NP-Complete. The following problem is a variant, though, and I'm not sure how to ...
1
vote
1answer
69 views

If a CSP (over a finite domain) has only linear inequalities as constraints, is it solvable in linear time?

I have an optimization problem in fuzzy logic that I want to model and solve as a CSP. If I could use only linear inequalities in my encoding, is the resulting CSP solvable in linear time? Problem ...
7
votes
0answers
208 views

complexity of a Constraint Satisfaction Promise Problem

Due to curiosity regarding possible extensions of Schaefer's dichotomy theorem, I wound up considering the "promise constraint" with 3 boolean inputs that's given by $C(x,y,z) ​ ​ = \hspace{.1 in}\...
9
votes
2answers
12k views

What is Least-Constraining-Value?

In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are: Minimum-remaining-...
4
votes
2answers
775 views

Contraint with three variables into three binary constraints

I'm having a hard time tackling the following problem (perhaps some key data is missing). We have a constraint: $A+B= C$ One is supposed to represent this one constraint using three binary ...
3
votes
3answers
142 views

Isn't Domain of a variable nothing but a constraint?

In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are ...
6
votes
2answers
1k views

Why don't modern SAT solvers use the notion of a “watched clause”, in the same way they use the notion of a “watched literal”?

Modern SAT solvers use the notion of "watched literals": when a value is chosen for a literal $l$, the solver only checks whether that falsifies clauses with $l$ in them if $l$ is one of the watched ...
1
vote
1answer
138 views

Requiring at least one alldiff constraint to be satisfied converted to SAT

For generating certain hard puzzles, I am trying to model a problem (ultimately) in SAT. I don't know how to do that, so I am starting with CSP because it's more expressive. In CSP, there is a global ...
0
votes
1answer
595 views

Help with understanding Simulated Annealing algorithm

I'm trying to wrap my head around it, but no matter what I read, I still can't fully understand it. I tried to read a little bit about the annealing process in physics, but I have no background ...