Questions tagged [constraint-satisfaction]
The constraint-satisfaction tag has no usage guidance.
91
questions
0
votes
1answer
33 views
Why N-Queens Problem is not used as experiment in CSP thesis?
I am studying CSP for my master thesis. I found that many thesis based on CSP described N-Queens as an introductory and they actually do experiment on random CSP problems.
If so,when I do master ...
1
vote
0answers
19 views
Find an algorithm to fully consume items with criteria and produce minimal result
So here are the prerequisites:
There are items to be consumed. Consider an item is just an object with a bunch of properties (e.g. size, weight), and there are tens or hundreds of properties.
Items ...
1
vote
1answer
71 views
+50
Selection over combinatorics that satisfies a distribution
I'm having an exciting problem that I could not manage to find an optimized solution. I actually have no idea if the problem is already known or not.
Here is the problem :
Consider a list of M ...
0
votes
1answer
20 views
Bin Packing variant
I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume ...
1
vote
1answer
56 views
Mutli-Path Collision Avoidance
I need an algorithm which can do the following:
Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
2
votes
2answers
48 views
Need recursive version of Conflict based backjumping
I am implementing conflict directed Backjumping algorithm of prosser in java. But, the algorithm is iterative approach. How can it be built with recursive approach?
In AIMA they give the recursive ...
2
votes
0answers
42 views
Least constraining value heuristic in Sudoku [closed]
I was trying to implement Least Constraining Value Heuristic in Sudoku but wasn't getting the idea on how to do it. Can someone share their idea for the same ?
2
votes
1answer
30 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
48 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
60 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{...
3
votes
1answer
37 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
17 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
355 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
52 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
87 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
27 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
38 views
Need some help implementing backjumping algorithm
I am extending aima csp solver in my project.I have read the AIMA book and the book says Backjumping algorithm can be implemented by with a little modification of Backtracking algorithm.But,I don't ...
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 ...
2
votes
1answer
37 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
32 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
20 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
453 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
73 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
12 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
111 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
365 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
42 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
54 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
140 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
256 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 \...
3
votes
1answer
61 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
72 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
22 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
314 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
29 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
344 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:
...
4
votes
1answer
1k 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
43 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
71 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
97 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
42 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
157 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
350 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
63 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 ...
