Questions tagged [constraint-satisfaction]
The constraint-satisfaction tag has no usage guidance.
85
questions
2
votes
1answer
26 views
Non-Boolean SAT
I was wondering about the complexity of SAT tests with variables $x_i = 0 \lor 1 \lor 2 \dots \lor n$, with clauses being of the form $x_i = a \implies x_j \neq b$. When $n=2$, we have 2SAT, which has ...
1
vote
1answer
47 views
Can an optimization algorithm be “universal”?
I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX.
In trying to answer this question, I realized that I don'...
0
votes
1answer
42 views
“Greater than AND smaller than” condition in integer linear program with a binary variable
I found this related question, but that's not quite it
Is it possible to model this with integer programming:
$$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{...
2
votes
1answer
29 views
Sum of unique integers to cnf constraint
As a study project I try to solve the kakuro puzzle problem using SAT SOLVER.
I can't really find an efficient way to convert the sum of k unique integers (1...9) to a CNF constraint.
What I had in ...
1
vote
1answer
15 views
Constraint propagation using Projection rule
I've found this example of constraint propagation using projection rule
We have
C = { x1 ≠ x2, x1 ≥ x2 }
< C; x1 ∈ {1,2,3}, x2 ∈ {1,2,3} >
They say that ...
5
votes
1answer
301 views
SAT algorithm for determining if a graph is disjoint
What are some good algorithms to have a SAT (CNF) solver determine if a given graph is fully-connected or disjoint?
The best one I can think of is this:
Number the nodes 1..N, where N is the number ...
0
votes
0answers
18 views
How to apply AC-3(Arc-consistency 3) algorithm in N-Queen problem?
I am building N-Queen Solver with java.
I confused with AC-3 algorithm.
I heard that AC-3 can be applied with backtracking algorithm before processing and during the search.The latter is called MAC-3 ...
4
votes
0answers
76 views
What is the generating algorithm for the “komb” instances found on satcompetition.org?
For the 2017 and 2018 Random SAT Tracks of the SAT Competition ran by the International Conference on Theory and Applications of Satisfiability Testing there are small, yet difficult, random 3-SAT ...
1
vote
1answer
24 views
How to put elements in allowed bags?
Let's say I have a list of "Items"
I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag.
I want to place ...
0
votes
0answers
16 views
How to calculate constraint check in BT of 4-Queens problem?
I have seen number of constraint check in paper of CSPs.
The constraint checking is counted as followed: when a value of a variable x is checked against a value of variable y, this is counted as ...
0
votes
0answers
17 views
How to make schedules so that each team plays every game?
There are g games (checkers, chess, Monopoly, ...) and there are t teams.
t is odd.
Each ...
0
votes
0answers
20 views
What is the time complexity of FC_MRV algorithm?
I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.
0
votes
0answers
25 views
Channeling Constraints in Constraint Handling Rules (CHR)
Suppose we have a constraint satisfaction problem that can be defined as its constraints in two different viewpoints $V_1$ and $V_2$. Moreover, there are two variables $A$ and $B$ from $V_1$ and $V_2$ ...
1
vote
1answer
19 views
How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length
If I have the following system, I am wondering how to calculate the number of valid strings it contains.
The system is something like this, which can have arbitrary variations.
Only consists of an ...
5
votes
3answers
418 views
How do we place $8n$ objects in a grid of size $n \times n$?
How do we place $8n$ objects on a square of size $n\times n$ in a form of grid such that no 4 of them form a rectangle with sides parallel to those of square? Each object occupies exactly one cell in ...
0
votes
0answers
35 views
Projection operator for constraints
I was looking at HM(X) framework, Hindley-Milner parameterized by a constraint system X, and I was struggling to understand what does the projection operator $\exists \alpha$ does for a constraint. ...
4
votes
1answer
61 views
Is this problem that's similar to integer linear programming also an NP-complete problem?
I've come across this problem while trying to work out a table-formatting algorithm.
It's very similar to standard linear programming (though it uses $>$ instead of $<$; I'm not extremely ...
1
vote
0answers
10 views
How to build an execution graph of concurrency accesses
Sorry If I don't use the right vocabulary, maybe part of my question is due to the fact that I don't know the name of what I'm searching.
I have a bounded set of operations that need to access a ...
3
votes
2answers
95 views
Is every X3SAT instance with no cycles satisfiable?
Exactly 1 in 3 SAT (X3SAT) is a variation of the Boolean Satisfiability problem. Given a set of clauses, where each clause has three literals, is there an assignment such that in each clause exactly ...
0
votes
2answers
159 views
Solving a in/equality constraint problem with graph search
You are given a list of m constraints over n distinct variables x1, ..., xn. Each constraint is of one of the following two types.
An equality constraint of the form xi = xj for some i!=j.
An ...
4
votes
1answer
35 views
Sorting strings with “before” and “after” constraints
I'm trying to solve a constraint-satisfaction problem for a project of mine that seems like it should have a well-known solution, but I can't for the life of me seem to find it described anywhere.
I'...
1
vote
1answer
44 views
Check a variable within a range with a binary variable [closed]
I have a value, a, it can be any value from 0 to 1. In an integer linear program, how can I formulate a constraint that uses a binary variable, y, to determine whether a is within a range of 0 and 1 ...
1
vote
1answer
19 views
Selection of dates respecting delay constraints
I encountered an issue at work that can be derived approximatively to this problem.
Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) ...
0
votes
0answers
61 views
Time complexity of well know constraint satisfaction problem algorithms with heuristics
I have know that complexity of csp algorithms as follow:
Backtracking algorithm for constraint processing
space:O(n) ,Time :O(expn)
Backjumping algorithm for constraint satisfaction problem
...
1
vote
0answers
143 views
“Greater than 0” condition in integer linear program with a binary variable [duplicate]
How can one model the following condition in an integer linear program?
$$
y = \begin{cases} 1 & \text{if } x > 0\\ 0 & \text{otherwise}\end{cases}
$$
Where $y \in \{0,1\}$ and $x \in \...
0
votes
1answer
53 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 ...
3
votes
1answer
57 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
31 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
56 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$ ...
3
votes
1answer
21 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
19 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
235 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
28 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
246 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
675 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
40 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
59 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
13 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 ...
5
votes
1answer
79 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
41 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
108 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 ...
2
votes
1answer
245 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
21 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
61 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
46 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 ...
2
votes
1answer
158 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
90 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
76 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 ...
2
votes
0answers
32 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
40 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 ...
