Questions tagged [constraint-satisfaction]
The constraint-satisfaction tag has no usage guidance.
0
votes
1answer
29 views
Which BackJumping Algorithm is being used here?
This is the illustration of the Backjumping algorithm for four queens exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem .I am confused whether this is ...
2
votes
1answer
28 views
Proving NP hardness about graph creation problem with triangle number
I have graph creation problem.
Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in ...
2
votes
1answer
29 views
IA network that is path-consistent, but not consistent
I'm studying continuous CSP from the slides of my professor and i got that with the PATH-CONSISTENCY algorithm you can check consistency for PA (Point Algebra), SIA and ORD-Horn; however it cannot be ...
1
vote
0answers
32 views
Big M method for continuous variables
Is there any way to model the big M method for continuous variables?
Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$.
Due to the precision problem, when the $B$ and $C$ ...
2
votes
1answer
13 views
General structure of solutions to 3-SAT circuits
Certain special forms of the SAT problem have solution sets of a special form. For example, given any three solutions to a 2-SAT circuit, their bitwise median is also a solution. Likewise, given any ...
1
vote
1answer
15 views
what does it mean to extend an assignment?
For a constraint satisfaction problem, what does it mean for an assignment x to extend an assignment a?
Sorry if this is super trivial, I did not find an answer
e.g here: No Small Linear ...
1
vote
1answer
68 views
A simple way to find the feasible region of a system with simple constraints
I'm coding something... weird, and I'm running into some constraint satisfaction and graph theory problems, which are fields I'm not too experienced in. Here's the problem:
I start out with this ...
2
votes
1answer
22 views
Is there a “well known” example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable?
I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.
1
vote
0answers
50 views
understanding constraint satisfaction problem: map coloring algorithm
I am trying to implement this recursive-backtracking function for a constraint satisfaction problem from the given algorithm:
...
0
votes
1answer
150 views
Aren’t most constraining variable and least constraining value the exact opposite?
So aren’t MCV and LCV the exact opposite?MCV tries to choose the variable with the most constraints on
remaining variables but LCV is opposite: it tries to rule out as least values for other variables ...
1
vote
1answer
36 views
Algorithm to solve constraint satisfaction problems
I have group of people. Each person can be described by few characteristics:
age, occupation, city, favorite_color
I would like to generate 60 random people and ...
0
votes
1answer
37 views
Algorithm to Assign Values Based on Constraints
I have variables x y and z, and I have the values that they can be assigned to, I.E. x can be assigned 1,2, or 3, y can be 1, and z can be 2. The problem is a constraint that says once a value has ...
0
votes
1answer
12 views
Generating graph with complex structure
I want to generate a bunch of graphs of about 100 nodes, where each node is a categorial variable. I want the graphs to satisfy complex properties, like, "if a node of type A is connected to a node ...
4
votes
1answer
51 views
Subgraph isomorphism on star multi-graphs with labelled edges
My approach to the problem has been to reformulate it into something more recognizable, but I don't know the best way to solve the reformulated problems either. I list the original problem, an example,...
1
vote
2answers
40 views
Does this constraint satisfaction problem have a name
I've been struggling with a particular constraint satisfaction problem, that appears like it should have an easy solution. In fact, I need a very fast solution.
The problem is: I am making a card-...
2
votes
1answer
53 views
Mimimum spanning tree with a constraint on number of certain types of edges
I have the the following problem.
Say we have a graph $G = (V,E)$ where all $e \in E$ have positive weight, and $E$ can be separated in to two disjoint sets $E = A \cup B$. We have to find a spanning ...
1
vote
1answer
52 views
Parameter sharing / weight constraints in Neural Networks
I would like to train a neural network whose parameters (alternatively, weights) are subject to linear constraints such as
$w_{i,j} = w_{i',j'}$,
where $w_{i,j}$ denotes the weight from input node $...
2
votes
1answer
19 views
Is $\Gamma = Inv(Pol(\Gamma))$?
I'm reading A Rendezvous of Logic, Complexity and Algebra, my first introduction to the world of CSP. Let $\Gamma$ be a finite constraint language. It says in Pg. 9 that
$Pol(\Gamma)$ is used to ...
0
votes
1answer
54 views
Objective function and constraint satisfaction over a set of multi-attributes elements
I'm looking for an approach to solve a problem consisting of maximizing an objective function over a set of discrete elements, while respecting a set of constraints.
To illustrate my point, I'll try ...
-1
votes
1answer
40 views
Possible orderings with constraints
Given variables {A, B, ,,,,,Z}
We want to sort these varibles according to given constraints.
The constrains are in below format:
X Y Z
meaning the third variable (Z) is not in the range ...
3
votes
1answer
149 views
Constraint Satisfaction: maximizing total value with no overlaps
Suppose we have a bunch of bars, which can represent anything (time slots, paths, physical items...) and each of them has a start point, an end point, and an associated value.
Out of all the bars ...
1
vote
1answer
87 views
I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem?
There are n girls and n boys. Each girl i has an objective attractiveness constant Pi (a natural number). The bigger the number, the more attractive. Each boy has a range in which he is comfortable ...
3
votes
0answers
73 views
Given two arrays of length n and n - 1, order the first array such that no partial sum is in the second array
Two arrays of natural numbers are given of length $n$ and $n - 1$:
e.g.
$A: [a_0, a_1,..., a_{n-1}, a_n]$
$B: [b_0, b_1, ..., b_{n-2}, b_{n-1}]$
All elements of $A$ are unique (can be in $B$), all ...
3
votes
0answers
31 views
State-of-the-art for Set Constraints?
I've recently stumbled across the field of Set constraints for program analysis, that is, solving equations of the form $exp_1 \subseteq exp_2$, where (depending on the particular variant of the ...
1
vote
1answer
38 views
Checking large number of configurations with multiple constraints
I have a very large number of constraints such as:
$ A1 \land B1 \land C1 \land D1 \land E1 \land F1$
$ A2 \land B2 \land C2 \land D2 \land E2 \land F2$
$ A3 \land B3 \land C3 \land D3 \land E3 \land ...
4
votes
2answers
264 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
35 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
158 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
1answer
549 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
400 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
53 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
37 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
159 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
154 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
51 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
386 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
57 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
91 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 ...
2
votes
3answers
3k 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 \...
3
votes
1answer
143 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
261 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
43 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
76 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
74 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
45 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
248 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
30 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
35 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 ...
